Chapter 2
Logic Gates
Gates
A gate is a device that performs a basic
operation on electrical signals
Gates are combined into circuits to perform
more complicated tasks
NOT Gate
A NOT gate accepts one input value
and produces one output value
input output
Sometimes called an inverter because it inverts the
input
AND Gate
An AND gate accepts two input signals
A B
OR Gate
If both inputs are 0, output is 0
Otherwise, output is 1
XOR Gate
An XOR gate produces 0 if its inputs are match, and a 1
otherwise
NAND Gates
The NAND gates are essentially the opposite of
the AND gates.
NOR GATES
The NOR gates are essentially the
opposite of the OR gates.
n-input Gates
Because + and * are binary operations, they can be
cascaded together to OR or AND multiple inputs.
A A
B A+B+C B ABC
C
A A
B A+B+C B ABC
C C
NAND and NOR as Universal Logic Gates
Any logic circuit can
be built using only
NAND gates, or only
NOR gates. They are
the only logic gate
needed.
Here are the NAND
equivalents:
NAND and NOR as Universal Logic Gates (cont)
Here are the NOR
equivalents:
NAND and NOR
can be used to
reduce the number
of required gates
in a circuit.
Digital systems
Two main types 1
Combinational
7
3
• Outputs dependent only on
current input
Sequential
• Outputs dependent on both
past and present inputs
Digital Electronics
Two general categories
In a combinational circuit, the input values explicitly
determine the output
In a sequential circuit, the output is a function of the input
values as well as the existing state of the circuit
As with gates, we can describe the operations of entire
circuits using three notations
Boolean expressions
logic diagrams
truth tables
Logic Notation
Boolean algebra:
expressions in this algebraic notation are an elegant and
powerful way to demonstrate the activity of electrical circuits
Logic diagram:
a graphical representation of a circuit
Each type of gate is represented by a specific symbol
Truth table:
defines the function of a gate by listing all possible input
combinations that the gate could encounter, and the
corresponding output
Combinational Circuits
Gates are combined into circuits by using the output of one
gate as the input for another
(AB + AC)
Truth Table
Since this circuit has 3 inputs, eight rows are required to describe all
possible input combinations: (23=8)
This same circuit using Boolean algebra:
(AB + AC)
Combinational Logic
Consider the following Boolean expression: A(B + C)
• Now compare the final result column in this truth
table to the truth table for the previous example
• They are identical
Circuit Equivalence
We have therefore just demonstrated circuit
equivalence
That is, both circuits produce the exact same output for each
input value combination
Boolean algebra allows us to apply provable
mathematical principles to help us design logical
circuits
Exercise 1
Find the output of the following circuit
x x+y
y
(x+y)y
Answer: (x+y)y _
Exercise 2
Find the output of the following circuit
x
x xy xy
y
y
___
_ _
Answer: xy
Exercise 3
Write the circuits for the following Boolean
algebraic expressions
__
a) x+y
x
x x+y
y
Exercise 4
Sketch the circuits for the following Boolean
algebraic
_____
expressions
b) (x+y)x
x x+y
x+y (x+y)x
y
Exercise 5
Implement the following truth table.
A B C
0 0 0
0 1 1
1 0 1
1 1 0
3-26
Exercise 5
Writing xor using and/or/not
____
x y (x + y)(xy) x
1
y
1
xy
0
1 0 1
0 1 1
0 0 0
x x+y (x+y)(xy)
y
xy xy
Exercise 6
Complete the truth A B A.B A.B A+B P
table for this circuit
and name the
0 0
equivalent primitive
function/gate.
0 1
1 0
1 1
Exercise 7
Can implement ANY truth table with AND, OR,
NOT.
A B C D
0 0 0 0 1. AND combinations
that yield a "1" in the
0 0 1 0
truth table.
0 1 0 1
0 1 1 0
1 0 0 0 2. OR the results
1 0 1 1 of the AND gates.
1 1 0 0
1 1 1 0
Example
Consider a buzzer which sounds when :
• The lights are on and
• The door is open and A
Alarm
• No key is in the ignition B system P
Active
C
Variable Value Situation
A 1 Lights are on
0 Lights are off
B 1 Door is open
0 Door is closed
C 1 Key is in ignition
0 Key is out of ignition
P 1 Buzzer is on
0 Buzzer is off
Example
Truth Table
A B C P
0 0 0 0
0 0 1 0
A Truth Table can be
0 1 0 0
used to show the
0 1 1 0
relationships between : 1 0 0 0
• the 3 inputs and 1 0 1 0
• the single output 1 1 0 1
1 1 1 0
lights A
Implementation as a
circuit using logic gates door B P buzzer
keys C
How to add binary numbers
Consider adding two 1-bit binary numbers x and y
0+0 = 0
0+1 = 1
1+0 = 1 x y Carry Sum
1+1 = 10 0 0 0 0
0 1 0 1
1 0 0 1
Carry is x AND y
1 1 1 0
Sum is x XOR y
The circuit to compute this is called a half-adder
The half-adder
Sum = x XOR y
Carry = x AND y
x
y Sum
Carry
Definition: Minterm
Product term in which all variables appear once
(complemented or not)
For n variables, there will be 2n minterms
34
Maxterms
Sum term in which all variables appear once
(complemented or not)
35
Minterm related to Maxterm
Minterm and maxterm with same subscripts are
complements
Example
m j Mj
m3 XYZ X Y Z M 3
36
Sum of Product (SOP)
OR all of the minterms of truth table row with a
1
37
Product of Maxterms
Recall that maxterm is true except for its own
case
So M1 is only false for 001
38
Product of Sum (POS)
Can express F as AND of all rows that should
evaluate to 0
F M1 M 3 M 4 M 6
or
F ( X Y Z )( X Y Z )
( X Y Z )( X Y Z )
39
Canonical and Standard Forms
We need to consider formal techniques for the
simplification of Boolean functions.
Minterms and Maxterms
Sum-of-Minterms and Product-of-Maxterms
Product and Sum terms
Sum-of-Products (SOP) and Product-of-Sums (POS)
Dec 8, 2021 40
Definitions
Minterm: a product term in which all the variables
appear exactly once, either complemented or
uncomplemented
Maxterm: a sum term in which all the variables
appear exactly once, either complemented or
uncomplemented
Dec 8, 2021 41
Truth Table notation for Minterms
and Maxterms
Minterms and x y z Minterm Maxterm
Maxterms are easy 0 0 0 x’y’z’ = m0 x+y+z = M0
to denote using a 0 0 1 x’y’z = m1 x+y+z’ = M1
truth table. 0 1 0 x’yz’ = m2 x+y’+z = M2
Example: 0 1 1 x’yz = m3 x+y’+z’= M3
Assume 3 variables1 0 0 xy’z’ = m4 x’+y+z = M4
x,y,z 1 0 1 xy’z = m5 x’+y+z’ = M5
(order is fixed) 1 1 0 xyz’ = m6 x’+y’+z = M6
1 1 1 xyz = m7 x’+y’+z’ = M7
Dec 8, 2021 Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5) 42
Canonical Forms (Unique)
Any Boolean function F( ) can be expressed as
a unique sum of minterms and a unique
product of maxterms (under a fixed variable
ordering).
In other words, every function F() has two
canonical forms:
Canonical Sum-Of-Products (sum of minterms)
Canonical Product-Of-Sums (product of
maxterms)
Dec 8, 2021 Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5) 43
Example
Truth table for f1(a,b,c) at right
a b c f1
The canonical sum-of-products form for f1
is 0 0 0 0
f1(a,b,c) = m1 + m2 + m4 + m6 0 0 1 1
= a’b’c + a’bc’ + ab’c’ + abc’
The canonical product-of-sums form for f1
0 1 0 1
is 0 1 1 0
f1(a,b,c) = M0 • M3 • M5 • M7 1 0 0 1
= (a+b+c)•(a+b’+c’)•
(a’+b+c’)•(a’+b’+c’). 1 0 1 0
Observe that: mj = Mj’ 1 1 0 1
1 1 1 0
Dec 8, 2021 Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5) 44
Conversion Between Canonical Forms
Example:
f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’
= m1 + m2 + m4 + m6
= ∑(1,2,4,6)
= ∏(0,3,5,7)
= (a+b+c)(a+b’+c’)(a’+b+c’)(a’+b’+c’)
Dec 8, 2021 45
Read
Lab 1
Quick read
Just to see if it all makes sense
http://www.cs.unc.edu/~lastra/comp160/Labs/index.html
46
C
A F
B
C
A G
