Transcript CH3

DeMORGAN’s LAWS
De Morgan’s Laws provide an easy way to find the inverse of
a boolean expression:
(X + Y)’ = X’ Y’
(X Y)’ = X’ + Y’
An easy way to remember this is that each TERM is
complemented, and that OR’s become AND’s; AND’s
become OR’s.
(Easy to prove this via a truth table, see textbook p. 47.)
The complement of the product is the sum of complements
The complement of the sum is the product of complements.
-- Can easily generalize to n variables using above rules
1
APPLYING DeMORGAN’S LAW
Apply De Morgan’s Law to a more complex expression:
(AB + C’D)’ = (AB)’ (C’D)’
= (A’+B’)(C + D’)
Note that De Morgan’s law was applied twice.
Another example:
[(A’ + B)C’]’ =
=
=
(A’ + B)’ + (C’)’
(A’)’ (B)’ + C
AB’ + C
2
NAND, NOR GATES
Why do we care about De Morgan’s Law?
There are two other gate types that produce the complement
of a boolean function!
AB Y
0 0 1
0 1 1
1 0 1
1 1 0
A
B
AB Y
0 0 1
0 1 0
1 0 0
1 1 0
(AB)’
NAND
(A+B)’
A
B
NOR
3
NAND, NOR (cont.)
NAND (NOT AND) - can be thought of as an AND gate
followed by an inverter.
A
B
(AB)’
A
NAND
B
AB
(AB)’
NOR (NOT OR) - can be thought as an OR gate followed
by an inverter.
A
(A+B)’
B
NOR
A
A+B
(A+B)’
B
4
Actually….
In the real world, an AND gate is made from an NAND gate
followed by an inverter.
An OR gate is made from a NOR gate followed by an inverter.
A
B
A
(AB)’
AB
B
NAND
(A+B)’
B
NOR
A
A+B
A
B
AB
AND
A+B
OR
5
What is this logic function in SOP form?
A
(AB)’
B
F = ((AB)’ (CD)’)’
C
D
(CD)’
Lets use De Morgan’s Law
F = ((AB)’ (CD)’)’ = ((AB)’)’ + ((CD)’)’ = AB + CD
An interesting result……………
SOP Form
6
NAND-NAND form = AND-OR form
A
(AB)’
B
F = ((AB)’ (CD)’)’
C
D
(CD)’
Same logic function
A
(AB)
B
F = AB + CD
C
D
(CD)
7
DeMORGAN’S THEOREM
• Symbolic DeMorgan’s duals exist for all gate
primitives
nand
nor
and
or
not
8
DeMORGAN’S THEOREM (cont’d)
Can save you time in evaluating/designing combinatorial logic
– Align bubbles and non-bubbles whenever possible
9
SHORTCUTS for MULTIPLYING
A short cut theorem for Distribution (Multiplication)
(X + Y) (X’ + Z) = XZ + X’Y
Only works when you have a variable (X) and its
complement (X’). To PROVE this, lets do the distribution
the long way.
(X + Y)(X’ + Z) = X X’ + XZ + X’Y + YZ
0
Redundant by consensus
theorem p.40 #17
= 0 + XZ + X’Y = XZ + X’Y
10
EXAMPLE: CONVERT to SOP FORM (p. 51)
(A+B+C’) (A+B+D) (A+B+E) (A+D’+E)(A’+C)
Let X=A+B, Y=C’, Z=D  (X+Y)(X+Z) = X+YZ (#8D p.40)
=(A+B+C’D) (A+B+E) (A+D’+E) (A’+C)
Let X=A, Y=D’+E, Z=C,  (X+Y)(X’+Z) = XZ+X’Y (#16 p.40)
=(A+B+C’D)(A+B+E) (AC+A’(D’+E))
=(A+B+C’D)(A+B+E) (AC+A’D’+A’E))
by distr. law
Let X=A+B, Y=C’D, Z=E,  (X+Y)(X+Z) = X+YZ
=(A+B+C’DE) (AC+A’D’+A’E))
Mult. out by distr. law and eliminate terms such as AA’D’
=AAC+AA’D’+AA’E +ABC+A’BD’+A’BE +C’DEAC+C’DEA’D+C’DEA’E
= AC + ABC + A’BD + A’BE + A’C’DE
Let X=AC, Y=B  X+XY = X
= AC + A’BD’ + A’BE + A’C’DE
(#10 p.40)
11
EXAMPLE: CONVERT to POS FORM (p. 51)
AC + A’BD’ + A’BE + A’C’DE
(A’ is common to three terms)
= AC + A’(BD’ + BE + C’DE) by distr. law
Let X=A, X’=A’, Y=BD’ + BE + C’DE, Z=C XZ+X’Y=(X+Y)(X’+Z)
=(A+BD’+BE+C’DE)(A’+C)=(A+C’DE+BD’+BE)(A’+C) -re-arranging
= A+C’DE +B(D’+E ) (A’+C) by distr. law
Let X= A+C’DE, Y=B, Z=D’+E  X+YZ=(X+Y)(X+Z)
(8D)
= (A+B+C’DE)(A+C’DE +D’+E)(A’+C)
But E+C’DE = E (using X+XY=X) so C’DE is redundant
= (A+B+C’DE) (A+D’+E)(A’+C)
Let X=A+B, Y=C’, Z=DE  X+YZ=(X+Y)(X+Z)
=(A+B+C’)(A+B+DE) (A+D’+E)(A’+C)
Let X=A+B, Y=D, Z=E  X+YZ=(X+Y)(X+Z)
=(A+B+C’) (A+B+D)(A+B+E) (A+D’+E)(A’+C)
12
EXCLUSIVE-OR FUNCTION
One last gate type is the XOR Gate (Exclusive OR gate).
A
XOR
F=AB
AB Y
0 0 0
0 1 1
1 0 1
1 1 0
B
XOR gate is common in logic circuits that do
binary addition/subtraction.
Note that:
-- see eqns. 3-17 to 3-24
p. 52 for XOR theorems
F =AB
= A’B + AB’
= (A+B) (AB)’
13
EQUIVALENCE FUNCTION (
Equivalence is the complement of XOR.
A

AB Y
0 0 1
0 1 0
1 0 0
1 1 1
F = (A  B)’= A  B
B
A
-- alternate symbol
B

AB
Note: In order to simplify expressions containing
AND and OR as well as XOR and , it is usually desirable
to eliminate XOR and  by subst. defns. in terms of
AND and OR.
14
POSITIVE and NEGATIVE LOGIC
• General Concept
– Positive Logic
• High Voltage => Logic 1
• Low Voltage => Logic 0
– Negative Logic
• High Voltage => Logic 0
• Low Voltage => Logic 1
15
POSITIVE and NEGATIVE LOGIC (cont’d)
• Implication
– Positive Logic 
Voltage
A
B
F
Low Low Low
Low High Low
High Low Low
High High High
High Voltage => Logic 1
Low Voltage => Logic 0
Logic
A
B
0
0
0
1
1
0
1
1
F
0
0
0
1
- Equivalent gate: AND
16
POSITIVE and NEGATIVE LOGIC (cont’d 2)
• Implication
– Negative Logic  High Voltage => Logic 0
Low Voltage => Logic 1
Voltage
A
B
F
Low Low Low
Low High Low
High Low Low
High High High
Logic
A
B
1
1
1
0
0
1
0
0
F
1
1
1
0
- Equivalent gate: OR
17
POSITIVE and NEGATIVE LOGIC (cont’d 3)
• Implication
– Positive Logic 
High Voltage => Logic 1
Low Voltage => Logic 0
Voltage
A
B
F
Low Low Low
Low High High
High Low High
High High High
Logic
A
B
0
0
0
1
1
0
1
1
F
0
1
1
1
- Equivalent gate: OR
18
POSITIVE and NEGATIVE LOGIC (cont’d 4)
• Implication
– Negative Logic  High Voltage => Logic 0
Low Voltage => Logic 1
Voltage
A
B
F
Low Low Low
Low High High
High Low High
High High High
Logic
A
B
1
1
1
0
0
1
0
0
- Equivalent gate: AND
F
1
0
0
0
-- Negative logic Thm.
p. 56 (skip proof) 19
What do you need to know?
•
•
•
•
•
•
De Morgan’s Laws
Duality (covered in previous presentation)
NAND, NOR gates
Multiplying Out and Factoring Expressions
XOR Gate, Equivalence Gate
Positive and Negative Logic
20