LearnTronics

Deriving De Morgan's Laws Without a Truth Table

Truth tables are excellent for checking a result, but they are not the only way to understand or prove De Morgan's laws.

Start with:

~(A • B)

This says, “It is not true that A and B are both true.”

If they are not both true, then at least one must be false:

~A + ~B

So:

~(A • B) = ~A + ~B

Start with:

~(A + B)

This says, “Neither A nor B is true.” Therefore A is false and B is false:

~(A + B) = ~A • ~B

Let:

F = A + B

and propose:

X = ~A • ~B

To show X is the complement of F, it is enough to show two things:

F•X = 0 and F + X = 1

(A+B)(~A•~B)

= A•~A•~B + B•~A•~B

= 0 + 0 = 0

Now the OR condition:

(A+B) + (~A•~B)

= [(A+B)+~A] • [(A+B)+~B] (Boolean distributive law)

= (A+~A+B) • (A+B+~B)

= 1 • 1 = 1

Therefore ~A•~B is the complement of A+B, so:

~(A+B) = ~A•~B

Useful memory rule: when a NOT moves through parentheses, invert each term and swap AND ↔ OR.

NOT(A AND B) can be said in ordinary language as: A and B are both true At least one of A or B is false A and B are both false Exactly one is true

If it is not true that both are true, then at least one must be false.

Which is equivalent to ~(A + B)? ~A + ~B ~A • ~B A • B A + B

If neither A nor B is true, then both A and B are false: ~(A+B)=~A•~B.

In the algebraic proof, why do we show X•F=0 and X+F=1? To show X is the complement of F To calculate voltage To prove X=0 To count fan-out

A complement of F must AND with F to give 0 and OR with F to give 1.