A-level Computing/AQA/Paper 2/Fundamentals of computer systems/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: Template:CPTRuleTab

$\overline{P.Q}=\bar{P}+\bar{Q}$		$\overline{P+Q}=\bar{P}.\bar{Q}$
Rule 1		Rule 2

Template:CPTRuleEnd 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: Template:Nowrap

Now we prove Template:Nowrap by the same method: Template:CPTAnswer 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 $P$ to stand for padlock 1 is open, and $Q$ to stand for padlock 2 is open.

You can go through the gate if padlock 1 is open AND padlock 2 is open ($P.Q$) You can not go through the gate if padlock 1 is locked OR padlock 2 is locked ($\bar{P}+\bar{Q}$)

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 = $P.Q$ gate is closed = $\bar{P}+\bar{Q}$ you should be able to see that NOT{gate is open} = $\bar{P}+\bar{Q}$ or

$\overline{P.Q}$ = $\bar{P}+\bar{Q}$ Template:CPTExample Simplify the following: $\overline{(A.\stackrel{‾}{B})+\stackrel{‾}{A}}$

$A$	$B$	$\bar{A}$	$\bar{B}$	$A.\bar{B}$	$(A.\bar{B})+\bar{A}$	$\overline{(A.\stackrel{‾}{B})+\stackrel{‾}{A}}$
0	0	1	1	0	1	0
0	1	1	0	0	1	0
1	0	0	1	1	1	0
1	1	0	0	0	0	1

From looking at the truth table we can see that it equates to $A.B$. But we should also know how to get to this result by using boolean identities. Let's give it a go:

1. Using De Morgans Law: $\overline{P+Q}=\bar{P}.\bar{Q}$. Where P = $(A.\bar{B})$ and Q = $(\bar{A})$
2. Take each side separately and applying De Morgans Law convert the centre gate to an AND:
   $\overline{(A.\stackrel{‾}{B})+(\stackrel{‾}{A})}=(\overline{A.\stackrel{‾}{B}}).(\overline{\stackrel{‾}{A}})$
3. Now dealing with the left hand side of our new equation ($\overline{A.\stackrel{‾}{B}}$), apply De Morgans Law again ($\overline{P.Q}==\bar{P}+\bar{Q}$) and cancel out the double bars:
   $(\stackrel{‾}{\overline{\stackrel{‾}{A}+\stackrel{‾}{\stackrel{‾}{B}}}}).(A)=(\bar{A}+B).(A)$
4. Multiply out both sides:
   $(\bar{A}.A)+(B.A)$
5. From the Identity $\bar{A}.A=0$ we can replace the left hand side:
   $0+(B.A)$
6. From the Identity $0+X=X$ we can ignore the 0 leaving us with:
   $B.A$
7. From the Identity $X.Y=Y.X$ we can swap the values around:
   $A.B$ = the value we calculated by truth table

Let's try another Template:Robox/Close

Template:CPTExercise Template:CPTQuestionTabSimplify the following using De Morgan's Laws and boolean identities. Check your answers by making truth tables:

$\overline{A.B}+A$

1. Using Demorgans rule that: $\overline{A.B}=\bar{A}+\bar{B}$
2. Making $\overline{A.B}+A=\bar{A}+\bar{B}+A$
3. Using the boolean identity that $\bar{A}+A=1$
4. Making $\bar{A}+\bar{B}+A=\bar{B}+1$
5. Using the boolean identity that $\bar{B}+1=1$
6. We simplify down to $\overline{A.B}+A==1$