(C)' = 1

De Morgan's Law.



De Morgan's Law is an extension to the Boolean Logic we touched on when we looked at truth tables.

There are really only three kinds of logic gates, although we can list seven. The three real gates are:

NOT: for which the Boolean expression is  Q= A' (a Not gate has only one input)

AND: for which the Boolean expression is  Q=AB (input values are multiplied together)

OR:    for which the Boolean expression is  Q=A+B (input values are added together).

Q in the above is the  output. Every other gate is a compound based on these three.


If we require a device which has a high output  only when A and B are high, then it is a simple matter:


Digital Logic

Next Topic>

As you can see it is simply an  and gate with two logic inputs. You may notice here that the symbols are not BS 3939 but are in fact American Y32-14. This is because it was drawn on a computerised draughting package, in this case Probe from the University of Wolverhampton, and despite Wolverhampton being most definitely in England they've used American symbols in common with every other maker in the world, and the convenience of being able to instantly analyse the circuit far outweighs that of having to look up the symbols.

This has been a very simple circuit, and so let us now go on to something a little more challenging.


Supposing we have only Nand gates and we wish an output  Q= (A+B)(A+C).

The Boolean expression for a Nand gate is Q=(AB)'  which is to say the inverse of AB and so the truth table is:



 Which in words means to say that the gate only gives a high output if both its inputs are low. If we look at our required output Q, we find the expression in brackets is an Or one, as we are adding together , and the whole is an And, as we are multiplying.

This makes things tricky.

However if we apply De Morgan's Law we can make the whole thing an expression of Or statements and construct our Nand circuit around that.

De Morgan's Law consists of two theorems that state:

And once again because of practical problems in electronic typefacing it is common to write (A+B)'= (AB)' and (AB)' = (A+B)'

This is rather esoteric mathematics and the practical outcome in words in the first theorem is that the complement of the output of  ORing A and B is equal to the output of ANDing the complements of A and B. In the second the complement of the output of ANDing A and B is the same as ORing the complements of A and B. A complement means merely the opposite, and in digital logic there are only two conditions, 0 and 1, and so each is the complement of the other.

Applying De Morgan's Law to (A+B)(A+C) gives us  (A+B)' + (A+C)' and turns the whole thing into an Or. However if we negate only once we get the inverse of what we need and so we double negate.


Our expression becomes:

From this then we need two Or gates and an inversion, and as A is a common factor to both expressions it has to be an input to both gates.  If it is an Or gate  A B and C need a full on/off output and a gate to compare the outputs. It further becomes transparent that as A is a common factor whenever the  input A is 1 the output  Q is high regardless of the condition of B and C and when both B and C are 1 the output Q is high regardless of the condition of  A.  When all gates are low, output Q is low too, and the same condition exists when A is low and either B or C is low too.

All inputs will therefore need a full on/off condition at the first gate, there will need to be another tier to compare, and the third tier will consist of the output gate and an inverter. The circuits are thus:




1. All gate inputs are

low and so is the output.
















2. A is high, B and C low and Q is high.
















3. Only C is high, output is low.
















4. C and B are high, A is low, Q is high.



Conditions satisfied!

The first four Nand gates and the two thereafter comprise our Or gate and because the first four are Nands our first inversion comes about automatically. The last gate in the chain provides our second inversion, providing us with the output required .

(C)' = 1


(A)' = 1

(B)' = 1

(A+C)' = 0

(A+B)' = 0

(A+B)'+(A+C)' = 1

((A+B)'+(A+C)' )' = 0