View source for A-level Computing/AQA/Paper 2/Fundamentals of computer systems/De Morgan's Laws

<NOINCLUDE>
{{CPTPageNavigationP2|
 | Prev = Boolean identities
 | Next = Gate conversion}}
{{DISPLAYTITLE:Fundamental Hardware Elements of Computers: De Morgan's Laws}}
</NOINCLUDE>
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:
{{CPTRuleTab}}
<center>
{| class="wikitable"
|-
| <math>\overline{P . Q} = \overline{P}+\overline{Q}</math> || || <math>\overline{P + Q} = \overline{P}.\overline{Q}</math>
|-
! Rule 1 !! !! Rule 2
|}
</center>
{{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:
{{nowrap| <math>\overline{P + Q} = \overline{P}.\overline{Q}</math>}}

{{CPTAnswer|1={{{!}} class="wikitable"
{{!}}-
! ''P''
! ''Q''
! <math>{P}+{Q}</math>
! <math>\overline{P + Q}</math>
! <math>\overline{P}</math>
! <math>\overline{Q}</math>
! <math>\overline{P}.\overline{Q}</math>
{{!}}-
{{!}} 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 {{nowrap|<math>\overline{P . Q} = \overline{P}+\overline{Q}</math>}} by the same method:
{{CPTAnswer|1={{{!}} class="wikitable"
{{!}}-
! ''P''
! ''Q''
! <math>{P}.{Q}</math>
! <math>\overline{P . Q}</math>
! <math>\overline{P}</math>
! <math>\overline{Q}</math>
! <math>\overline{P}+\overline{Q}</math>
{{!}}-
{{!}} 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 <math>P</math> to stand for padlock 1 is open, and <math>Q</math> to stand for padlock 2 is open.

You can go through the gate if padlock 1 is open AND padlock 2 is open (<math>P . Q</math>)
You can not go through the gate if padlock 1 is locked OR padlock 2 is locked (<math>\overline{P} + \overline{Q}</math>)

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

	<math>\overline{P . Q}</math>		= <math>\overline{P} + \overline{Q}</math>
{{CPTExample|title=Example: Simplifying boolean equations using boolean algebra}}
Simplify the following: 
<math>\overline{(A . \overline{B})+\overline{A}}</math>
{| class="wikitable"
|-
! <math>A</math>
! <math>B</math>
! <math>\overline{A}</math>
! <math>\overline{B}</math>
! <math>A.\overline{B}</math>
! <math>(A.\overline{B})+\overline{A}</math>
! <math>\overline{(A . \overline{B})+\overline{A}}</math>
|-
| 0
| 0
| <center>1</center>
| <center>1</center>
| <center>0</center>
| <center>1</center>
| <center>0</center>
|-
| 0
| 1
| <center>1</center>
| <center>0</center>
| <center>0</center>
| <center>1</center>
| <center>0</center>
|-
| 1
| 0
| <center>0</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>0</center>
|-
| 1
| 1
| <center>0</center>
| <center>0</center>
| <center>0</center>
| <center>0</center>
| <center>1</center>
|}
From looking at the truth table we can see that it equates to <math>A.B</math>.  But we should also know how to get to this result by using boolean identities. Let's give it a go:
# Using De Morgans Law: <math>\overline{P + Q} = \overline{P}.\overline{Q}</math>. Where P = <math>(A . \overline{B})</math> and Q = <math>(\overline{A})</math>
# Take each side separately and applying De Morgans Law convert the centre gate to an AND:<br /><math>\overline{(A . \overline{B})+(\overline{A})} = (\overline{A . \overline{B}}).(\overline{\overline{A}}) </math>
# Now dealing with the left hand side of our new equation (<math>\overline{A . \overline{B}}</math>), apply De Morgans Law again (<math>\overline{P . Q} == \overline{P}+\overline{Q}</math>) and cancel out the double bars: <br /><math>(\overline{\overline{\overline{A} + \overline{\overline{B}}}}).({A}) = (\overline{A} + {B}).({A})</math>
# Multiply out both sides:<br /><math>(\overline{A}.A) + (B.A)</math>
# From the Identity <math>\overline{A}.A = 0</math> we can replace the left hand side:<br /><math>0 + (B.A)</math>
# From the Identity <math>0 + X = X</math> we can ignore the 0 leaving us with:<br /><math>B.A</math>
# From the Identity <math>X.Y = Y.X</math> we can swap the values around:<br /><math>A.B</math> = the value we calculated by truth table

Let's try another
{{Robox/Close}}

{{CPTExercise|title=Exercise: Simplifying boolean equations}}
{{CPTQuestionTab}}Simplify the following using De Morgan's Laws and boolean identities.  Check your answers by making truth tables:

<math>\overline{A . B}+A</math>

{{CPTQuestionTabEnd}}
{{CPTAnswerTab}}
#Using Demorgans rule that: <math>\overline{A . B} = \overline{A}+\overline{B}</math>
#Making <math>\overline{A . B}+A = \overline{A}+\overline{B}+A</math>
#Using the boolean identity that <math>\overline{A}+A = 1</math>
#Making <math>\overline{A}+\overline{B}+A = \overline{B}+1</math>
#Using the boolean identity that <math>\overline{B}+1 = 1</math>
#We simplify down to <math>\overline{A . B} + A == 1</math>
{{CPTAnswerTabEnd}}

{{CPTQuestion|<math>\overline{(A + \overline{B}).\overline{A}}</math>}}
{{CPTAnswer|1={{{!}} class="wikitable"
{{!}}-
! <math>A</math>
! <math>B</math>
! <math>\overline{A}</math>
! <math>\overline{B}</math>
! <math>A+\overline{B}</math>
! <math>(A+\overline{B}).\overline{A}</math>
! <math>\overline{(A + \overline{B}).\overline{A}}</math>
{{!}}-
{{!}} 0
{{!}} 0
{{!}} <center>1</center>
{{!}} <center>1</center>
{{!}} <center>1</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}}-
{{!}} 0
{{!}} 1
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>0</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}}-
{{!}} 1
{{!}} 0
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}}-
{{!}} 1
{{!}} 1
{{!}} <center>0</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}}}

If you're catching on to this, you'll notice that this is the equivalent of <math>A+B</math>.  But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer.
# Using De Morgans Law: <math>\overline{P . Q} = \overline{P}+\overline{Q}</math>
# Take each side separately and applying De Morgans Law convert the centre gate to an AND:<br /><math>\overline{(A + \overline{B}).(\overline{A})} = {(\overline{A + \overline{B}})+(\overline{\overline{A}})} </math>
# Cancel out the double bars:<br /><math>{(\overline{A + \overline{B}})+(\overline{\overline{A}})} = (\overline{A + \overline{B}})+({A})</math>
# Now dealing with the left hand side of our new equation, apply De Morgans Law again and cancel out the double bars: <br /><math>(\overline{\overline{\overline{A} . \overline{\overline{B}}}})+({A}) = (\overline{A} . {B})+({A})</math>
# Multiply out both sides:<br /><math>(\overline{A}+A) . (B+A)</math>
# From the Identity <math>\overline{A}+A = 1</math> we can replace the left hand side:<br /><math>1 . (B+A)</math>
# From the Identity <math>1 . X = X</math> we can ignore the 1 leaving us with:<br /><math>B+A</math>
# From the Identity <math>X+Y = Y+X</math> we can swap the values around:<br /><math>A+B</math> = the value we calculated by truth table
}}
{{CPTQuestion|<math>\overline{(\overline{A + B})+B}</math>}}
{{CPTAnswer|1={{{!}} class="wikitable"
{{!}}-
! <math>A</math>
! <math>B</math>
! <math>A+B</math>
! <math>\overline{A+B}</math>
! <math>(\overline{A+B})+B</math>
! <math>\overline{(\overline{A+B})+B}</math>
{{!}}-
{{!}} 0
{{!}} 0
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}}-
{{!}} 0
{{!}} 1
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}}-
{{!}} 1
{{!}} 0
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}}-
{{!}} 1
{{!}} 1
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}} <center>1</center>
{{!}} <center>0</center>
{{!}}}

 <math>\overline{(\overline{A+B})+B}</math>
If you're catching on to this, you'll notice that this is the equivalent of <math>A.\overline{B}</math>.  But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer.
# Using De Morgans Law: <math>\overline{P . Q} = \overline{P}+\overline{Q}</math>
# Take each side separately (P=<math>\overline{A+B}</math> and Q=<math>B</math>) and applying De Morgans Law convert the centre gate to an AND:<br /><math>\overline{(\overline{A+B})+B} = (\overline{\overline{A+B}}).\overline{B}</math>
# Cancel out the double bars:<math>(\overline{\overline{A+B}}).\overline{B} = (A+B).\overline{B}</math>
# Multiply out both sides:<br /><math>(A.\overline{B})+(B.\overline{B})</math>
# From the Identity <math>(B.\overline{B}) = 0</math> we can replace the right hand side:<br /><math>(A.\overline{B})+0</math>
# From the Identity <math>X + 0 = X</math> we can ignore the 0 leaving us with:<br /><math>A.\overline{B}</math> = the value we calculated by truth table
}}

{{Robox/Close}}
{{BookCat}}