 Search: Lycos Tripod King Kong Share This Page Report Abuse Edit your Site Browse Sites  « »  # Chapter 5 - Notation

This lesson was a lot easier for me to write than the previous ones. Want to know why? Well, I didn't have to draw quite as many diagrams as before! The whole idea of this lesson is to show you a way of writing the circuits that we have seen up to now in the form of an algebra - something that looks rather like mathematics. In fact, it has quite a lot in common with ordinary mathematics, as you will find out!

## The notation itself

We represent the AND operation using a dot . and the OR operation using a + so that A.B represents A "ANDed" with B and A + B represents A "ORed" with B:

 A.B A + B The other symbol is for NOT. In this case, we put a line above the letter or expression as follows:

 _A _____A + B That's a little difficult to do on a typewriter or computer (I should know!) so an alternative is to use the Ø notation. The item that follows Ø is inverted. You may also need brackets if it applies to a complicated expression:

 ØB Ø(A.B) What about something like A + B.C ? Does this mean that we do the OR first (the +), or the AND first (the .) or do we just do them in whichever order we come across them?

The rule is that AND takes precedence over OR, i.e. A + B.C is equivalent to A + (B.C) (where the brackets mean "do me first" as they do in ordinary mathematics) rather than (A + B).C. Of course, if you want the OR done before the AND, you would enclose it within brackets:  Also, note that NOT (Ø or a line above the symbol) takes precedence over both AND and OR, so ØX.Y would be equivalent to (ØX).Y rather than Ø(X.Y). However, when we put the line above some complex expression to show that it is inverted, we assume that the complex expression has invisible brackets round it (i.e. the expression is worked out, then inverted). Note the difference between the following:

 _____X + Y is equivalent to Ø(X + Y) ___X.Y is equivalent to Ø(X.Y) _ _X.Y is equivalent to (ØX).(ØY)

As far as I know, there is no special notation for NAND, NOR and XOR. In the case of A NAND B we just say Ø(A.B). In the case of A NOR B we just say Ø(A + B), and in the case of A XOR B we just say ØA.B + A.ØB (which gives exactly the same result, if you work it out).

## Axioms

An axiom is a statement of fact that is considered too simple to prove. For instance, in mathematics, it is an axiom that 1 + 1 = 2. Everyone older than about 2 years old knows this, but I bet you couldn't actually prove it. Neither could I. It's just too simple to prove.

In the following axioms A is any binary signal, 1 or 0:

• A + A = A (Any signal ORed with itself remains unchanged).
• A.A = A (Any signal ANDed with itself remains unchanged).
• A + 1 = 1 (Any signal ORed with 1 automatically produces 1)
• A + 0 = A (Any signal ORed with 0 remains unchanged)
• A.1 = A (Any signal ANDed with 1 remains unchanged)
• A.0 = 0 (Any signal ANDed with 0 automatically produces 0).
• Ø(ØA) = A (Any signal that is inverted and then inverted again will remain unaltered)
• A.ØA = 0 (Any signal ANDed with the opposite produces 0, i.e. 1 ANDed with 0, or 0 ANDed with 1)
• A + ØA = 1 (Any signal ORed with the opposite always produces 1, i.e. 0 ORed with 1, or 1 ORed with 0).

The operations of AND and OR are also distributative, commutative and associative:

Commutative means that it doesn't matter which way round you do them - the answer is the same:

A.B = B.A
A + B = B + A

Associative means that when you are ANDing three items, it doesn't matter which order you do them in, and similarly for ORing three items:

A.B.C = A.(B.C) = (A.B).C
A + B + C = A + (B + C) = (A + B) + C

Distributative means that they obey this rule:

A.(B + C) = (A.B) + (A.C)

I'm sure that you will have noticed the similarity between this notation and normal algebraic notation in mathematics. If we treat AND (.) as if it were multiply and OR (+) as if it were add, then the two are almost identical. The only difference is that A + 1 = 1, which is not automatically true in mathematics (but if A = 0 ...) However, if we treated "anything apart from from 0" as being the same, then the rule becomes A + (non-zero number) = (non-zero number), which makes perfect sense in mathematics providing that A is 0 or 1.

## AND-OR networks in this notation

We can express our AND-OR networks using the notation. Consider this network: In the syntax, this becomes A.ØB.C + ØA.B.C + A.ØB.ØC. What a relief! No more drawing those long, tedious diagrams!

Take a look at the first and last terms: A.ØB.C + A.ØB.ØC. If you cast your mind back to the distributative property, then you will see that we can "factorise" these terms into brackets, as follows:

A.ØB.C + A.ØB.ØC = A.ØB.(C + ØC)

because they have the A.ØB part in common. Now we can apply another axiom, C + ØC = 1, to reduce the expression further:

A.ØB.(C + ØC) = A.ØB.1 = A.ØB

Effectively, we have reduced those two terms to one, and the whole expression becomes

 ØA.B.C + A.ØB You can see from the table below that the truthtables are the same for both the original and the simplified version - they are equivalent.

 A B C A.ØB.C + ØA.B.C + A.ØB.ØC ØA.B.C + A.ØB 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0

Effectively the terms A.ØB.C + A.ØB.ØC tells us that the circuit produces a 1 if A is on and B is off, regardless of the state of C.

Now consider this AND-OR network:

X.ØY.Z + X.Y.Z + ØX.Y.Z

(and not a diagram in sight!) The expression could be simplified as follows:

 X.ØY.Z + X.Y.Z + ØX.Y.Z = X.Z.(ØY + Y) + ØX.Y.Z = X.Z.1 + ØX.Y.Z = X.Z + ØX.Y.Z = Z.(X + ØX.Y)

This relies on the fact that the first two terms can be collapsed into one. Alternatively, we can go back to the original expression and simplify it a different way:

 X.ØY.Z + X.Y.Z + ØX.Y.Z = X.ØY.Z + (X + ØX).Y.Z = X.ØY.Z + 1.Y.Z = X.ØY.Z + Y.Z = Z.(X.ØY + Y)

This relies on the fact that the last two terms can be collapsed into one. Both these simplified expressions are equivalent to the original, so they must both be equivalent to each other. If you don't believe me, construct the truth table for each version and compare them. I'm not doing it - I'm far too lazy!

## de Morgan's Laws

There are two rules which I should mention:
 ___ _ _ A.B = A + B
and
 _____ _ _ A + B = A . B
On the left side of each equation, the ANDing and ORing is done before the inverting. On the right side of each equation, the inverting is done before the ANDing or ORing. Here are de Morgan's rules written using the alternative notation:

Ø(A.B) = ØA + ØB
Ø(A + B) = ØA.ØB

The easiest way to prove these rules is to construct a truthtable for each half of the equations and compare them. Of course, there is no reason why you should apply de Morgan's rule just to individual letters. Try a combination of signals, such as

 Ø(Ø(A.B).Ø(C.D)) = Ø(Ø(A.B)) + Ø(Ø(C.D)) (according to the first rule above) = A.B + C.D

Incidentally, we have just proved that a NAND-NAND network is exactly equivalent to an AND-OR network. Ø(Ø(A.B).Ø(C.D)) is equivalent to A NANDed with B, C NANDed with D, and the output of these two NANDings being NANDed themselves. You can see that applying de Morgan's first rule turns the expression into A ANDed with B, C ANDed with D and the results ORed together.

## Some More Examples

Just to finish off, here are some more expressions which are equivalent to each other.

 (A + B.C).(C + ØA.D) = A.(C + ØA.D) + B.C.(C + ØA.D) = A.C + A.ØA.D + B.C.C + B.C.ØA.D = A.C + B.C + ØA.B.C.D = C.(A + B + ØA.B.D)

 X.Y.(X + Y + Z) = X.Y.X + X.Y.Y + X.Y.Z = X.Y + X.Y + X.Y.Z = X.Y + X.Y.Z = X.Y.1 + X.Y.Z = X.Y.(1 + Z) = X.Y.1 = X.Y

 P.Q.R + P.ØQ.ØR + P.Q.ØR + P.ØQ.R = P.Q.(R + ØR) + P.ØQ.(ØR + R) = P.Q.1 + P.ØQ.1 = P.Q + P.ØQ = P.(Q + ØQ) = P.1 = P

Here's that last example again, this time simplified a slightly different way:

 P.Q.R + P.ØQ.ØR + P.Q.ØR + P.ØQ.R = P.R.(Q + ØQ) + P.ØR.(ØQ + Q) = P.R.1 + P.ØR.1 = P.R + P.ØR = P.(R + ØR) = P.1 = P

(We got to the same place by a slightly different route!)