Fundamental Hardware Elements of Computers: De Morgan's Laws
De Morgan's laws are used to simplify Boolean equations so that you can build equations only involving one sort of gate, generally only using NAND or NOR gates. This can lead to cheaper hardware. There are two laws that you need to remember:
Rule 1  Rule 2 

An easy way to remember De Morgan's Laws is through the rhyme: "break the line, change the sign"!
Let's prove that I'm not lying to you by creating a truth table to prove that:
Answer :
P  Q  

0  0  0  1  1  1  1 
0  1  1  0  1  0  0 
1  0  1  0  0  1  0 
1  1  1  0  0  0  0 
Since the values in the 4th and last columns are the same for all rows (which cover all possible truth value assignments to the variables), we can conclude that the two expressions are logically equivalent.
Now we prove by the same method:
Answer :
P  Q  

0  0  0  1  1  1  1 
0  1  0  1  1  0  1 
1  0  0  1  0  1  1 
1  1  1  0  0  0  0 
There is a rather nice concrete way of thinking about this, with a gate that's padlocked with two padlocks, padlock 1 and padlock 2.
We'll use to stand for padlock 1 is open, and to stand for padlock 2 is open.
You can go through the gate if padlock 1 is open AND padlock 2 is open () You can not go through the gate if padlock 1 is locked OR padlock 2 is locked ()
Since 'You can not go through the gate' is the same as the opposite (negation) of 'You can go through the gate' and, remembering
gate is open = gate is closed = you should be able to see that NOT{gate is open} = or
=
Example: Simplifying boolean equations using boolean algebra
Simplify the following:
From looking at the truth table we can see that it equates to . But we should also know how to get to this result by using boolean identities. Let's give it a go:
Let's try another 
Exercise: Simplifying boolean equations
Simplify the following using De Morgan's Laws and boolean identities. Check your answers by making truth tables:
Answer :
Answer :
If you're catching on to this, you'll notice that this is the equivalent of . But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer.
Answer :
If you're catching on to this, you'll notice that this is the equivalent of . But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer.
