Gates and Logic:
From Transistors to Logic Gates and
Logic Circuits
Prof. Hakim Weatherspoon
CS 3410
Computer Science
Cornell University
[Weatherspoon, Bala, Bracy, and Sirer]
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Understanding the foundations of
• Computer Systems Organization and Programming
2
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Understanding the foundations of
• Computer Systems Organization and Programming
• e.g. Galaxy Note 9
3
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Understanding the foundations of
• Computer Systems Organization and Programming
• e.g. Galaxy Note 9
• with the [Link] DynamicIQ 8-core ARM processor
4
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Understanding the foundations of
• Computer Systems Organization and Programming
• e.g. Galaxy Note 9
• with the [Link] DynamicIQ 8-core ARM processor
big Quad Core LITTLE Quad Core
Architecture ARM v8 ARM v8
Process Samsung 10nm Samsung 10nm
Frequency 2.9GHz+ 1.9GHz
Area 3.5mm2
Power-ratio 1 0.17
L1 Cache Size 64 KB I/D Cache 64 KB I/D Cache
L2 Cache Size 2 MB Data Cache 512 KB Data Cache
5
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
• From switches
• Truth Tables
• Logic Circuits
• From Truth Tables to Circuits (Sum of Products)
• Identity Laws
• Logic Circuit Minimization
• Algebraic Manipulations
• Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
6
A switch
Acts as a conductor
or insulator.
Can be used to build
amazing things…
The Bombe used to break the German
Enigma machine during World War II 7
Basic Building Blocks: Switches to Logic Gates
+
Truth Table
A A B Light
- OFF OFF
OFF ON
B ON OFF
ON ON
8
Basic Building Blocks: Switches to Logic Gates
+
Truth Table
A A B Light
- OFF OFF OFF
OFF ON ON
B ON OFF ON
ON ON ON
+ A A A B B Light
Light
- OFF
OFFOFF
OFF
OFF
OFFONON
ONON OFF
B OFF
ON ON
9
Basic Building Blocks: Switches to Logic Gates
+ • Either (OR)
Truth Table
A A B Light
- OFF OFF OFF
OFF ON ON
B ON OFF ON
ON ON ON
• Both (AND)
+ A A A B B Light
Light
-
OFFOFF
OFF OFF OFF
OFFONON OFF
OFF
B ONON OFF
OFF OFF
ON ON ON
10
Basic Building Blocks: Switches to Logic Gates
• Either (OR)
Truth Table
A
A B Light
- OFF OFF OFF
OR OFF ON ON
B ON OFF ON
ON ON ON
• Both (AND)
A - A A B B Light
Light
OFFOFF
OFF OFF OFF
AND OFFONON OFF
OFF
B ONON OFF
OFF OFF
ON ON ON
11
Basic Building Blocks: Switches to Logic Gates
• Either (OR)
Truth Table
A
A B Light
- 0
OFF 0
OFF 0
OR 0
OFF 1
ON 1
0 = OFF
B 1 = ON
1
ON 0
OFF 1
1
ON 1
ON 1
• Both (AND)
A - A B Light
0 0 0
AND 0 1 0
B 1 0 0
1 1 1
12
Basic Building Blocks: Switches to Logic Gates
OR
B
George Boole (1815-1864)
A • Did you know?
• George Boole: Inventor of the
AND idea of logic gates. He was born
B in Lincoln, England and he was
the son of a shoemaker in a low
class family.
13
Takeaway
• Binary (two symbols: true and false) is the
basis of Logic Design
14
Building Functions: Logic Gates
• NOT: A Out
A
• AND: A B Out
0 0 0
A
0 1 0
B 1 0 0
• OR: 1 1 1
A B Out
A
0 0 0
B 0 1 1
1 0 1
• Logic Gates 1 1 1
digital circuit that either allows a signal to pass through it or not.
Used to build logic functions
There are seven basic logic gates:
AND, OR, NOT,
15
Building Functions: Logic Gates
• NOT: A Out
A 0 1
1 0
• AND: A B Out
0 0 0
A
0 1 0
B 1 0 0
• OR: 1 1 1
A B Out
A
0 0 0
B 0 1 1
1 0 1
• Logic Gates 1 1 1
digital circuit that either allows a signal to pass through it or not.
Used to build logic functions
There are seven basic logic gates:
AND, OR, NOT,
NAND (not AND), NOR (not OR), XOR, and XNOR (not XOR) [later] 16
Building Functions: Logic Gates
• NOT: A Out
A 0 1
1 0 A B Out
• AND: A B Out NAND: A
0 0
0 1
1
1
0 0 0
A B 1 0 1
0 1 0
B 1 0 0
1 1 0
• OR: 1 1 1 NOR: A B Out
A
0 0 1
A B Out
A B 0 1 0
0 0 0
B 1 0 0
0 1 1
1 1 0
1 0 1
• Logic Gates 1 1 1
digital circuit that either allows a signal to pass through it or not.
Used to build logic functions
There are seven basic logic gates:
AND, OR, NOT,
NAND (not AND), NOR (not OR), XOR, and XNOR (not XOR) [later] 17
Which Gate is this? iClicker Question
Function:
Symbol:
a b Out
Truth Table:
a
(A) NOT
b
(B) OR Out
(C) XOR
(D) AND
(E) NAND 18
Which Gate is this? iClicker Question
• XOR: out = 1 if a or b is 1, but not both;
• out = 0 otherwise.
• out = 1, only if a = 1 AND b = 0
• OR a = 0 AND b = 1
a b Out
0 0 0
0 1 1
1 0 1
1 1 0
a
(A) NOT
b
(B) OR Out
(C) XOR
(D) AND
(E) NAND 19
Which Gate is this? iClicker Question
• XOR: out = 1 if a or b is 1, but not both;
• out = 0 otherwise.
• out = 1, only if a = 1 AND b = 0
• OR a = 0 AND b = 1
a b Out
0 0 0
0 1 1
1 0 1
1 1 0
a
(A) NOT Out
b
(B) OR
(C) XOR
(D) AND
(E) NAND 20
Activity#2: Logic Gates
• Fill in the truth table, given the following Logic
Circuit made from Logic AND, OR, and NOT
gates.
• What does the logic circuit do?
a b d Out
0 0 0
0 0 1
0 1 0 a
0 1 1
1 0 0 d Out
1 0 1
1 1 0 b
1 1 1 21
Activity#2: Logic Gates
• Multiplexor: select (d) between two inputs (a
and b) and set one as the output (out)?
• out = a, if d = 0
• out = b, if d = 1
a b d Out
0 0 0 0
0 0 1 0
0 1 0 0 a
0 1 1 1
1 0 0 1 d Out
1 0 1 0
1 1 0 1 b
1 1 1 1 22
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
• From switches
• Truth Tables
• Logic Circuits
• From Truth Tables to Circuits (Sum of Products)
• Identity Laws
• Logic Circuit Minimization
• Algebraic Manipulations
• Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
23
Next Goal
• Given a Logic function, create a Logic Circuit
that implements the Logic Function…
• …and, with the minimum number of logic gates
• Fewer gates: A cheaper ($$$) circuit!
24
Logic Gates
A Out
NOT: A 0 1
1 0
A B Out
0 0 0
A
AND: B
0 1 0
1 0 0
1 1 1
A B Out
A
OR: 0 0 0
B 0 1 1
1 0 1
1 1 1
XOR: A B Out
A 0 0 0
0 1 1
B
1 0 1
1 1 0
25
Logic Gates
A Out
NOT: A 0 1
1 0
A B Out
A B Out
0 0 1
0 0 0
A NAND: A 0 1 1
AND: B
0 1 0
B 1 0 1
1 0 0
1 1 0
1 1 1
A
A B Out NOR: A
A B Out
OR: 0 0 0
0 0 1
B 0 1 1 B 0 1 0
1 0 0
1 0 1
1 1 0
1 1 1
XNOR: A B Out
XOR: A B Out
0 0 1
A 0 0 0 A
0 1 0
0 1 1
B B 1 0 0
1 0 1
1 1 1
1 1 0
26
Logic Implementation
• How to implement a desired logic function?
a b c out
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
27
Logic Implementation
• How to implement a desired logic function?
a b c out minterm 1) Write minterms
0 0 0 0 a b c 2) sum of products:
• OR of all minterms where out=1
0 0 1 1 abc
0 1 0 0 abc
0 1 1 1 abc
1 0 0 0 abc
1 0 1 1 abc
1 1 0 0 abc
1 1 1 0 abc
28
Logic Implementation
• How to implement a desired logic function?
a b c out minterm 1) Write minterms
0 0 0 0 a b c 2) sum of products:
• OR of all minterms where out=1
0 0 1 1 abc �
• E.g. out = abc + a�bc + abc
0 1 0 0 abc
a
0 1 1 1 abc b
c
1 0 0 0 abc out
1 0 1 1 abc
1 1 0 0 abc
1 1 1 0 abc
corollary: any combinational circuit can be implemented
in two levels of logic (ignoring inverters) 29
Logic Equations
• NOT:
out = ā = !a = ¬a
• AND:
out = a ∙ b = a & b = a ∧ b
• OR:
out = a + b = a | b = a ∨ b
• XOR:
out = a ⊕ b = ab� + āb
• Logic Equations
Constants: true = 1, false = 0
Variables: a, b, out, …
Operators (above): AND, OR, NOT, etc.
30
Logic Equations
• NOT:
out = ā = !a = ¬a
• AND: NAND:
out = a ∙ b = a & b = a ∧ b • out = a ∙ b = !(a & b) = ¬ (a ∧ b)
• OR: NOR:
out = a + b = a | b = a ∨ b • out = a + b = !(a | b) = ¬ (a ∨ b)
• XOR: XNOR:
• out = a ⊕ b = ab + ab
out = a ⊕ b = ab� + āb
• Logic Equations
Constants: true = 1, false = 0
Variables: a, b, out, … • .
Operators (above): AND, OR, NOT, etc.
31
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
a+0=
a+1=
a+ā=
a∙0 =
a∙1 =
a∙ā =
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
a+0= a
a
a+1= 1
a+ā= 1
b
a∙0 = 0
a∙1 = a
a∙ā = 0 a
b
33
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
(a + b) =
(a � b) =
a+ab =
a(b+c) =
a(b + c) =
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
A A
(a + b) = a� ∙ b� B
↔ B
A A
(a � b) = a� + b� B
↔ B
a+ab = a
a(b+c) = ab + ac
�c
a(b + c) = a� + b∙�
35
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
• From switches
• Truth Tables
• Logic Circuits
• From Truth Tables to Circuits (Sum of Products)
• Identity Laws
• Logic Circuit Minimization – why?
• Algebraic Manipulations
• Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
36
Minimization Example
a+0=a Minimize this logic equation:
a+1=1
a+ā=1
(a+b)(a+c) = (a+b)a + (a+b)c
a·0 =0 = aa + ba + ac + bc
a·1 =a = a + a(b+c) + bc
a·ā =0
= a + bc
a+ab =a
a (b+c) = ab + ac
37
iClicker Question
a+0=a (a+b)(a+c) a + bc
a+1=1
a+ā=1
a·0 =0 How many gates were
a·1 =a required before and after?
a·ā =0
a+ab =a BEFORE AFTER
a (b+c) = ab + ac (A) 2 OR 1 OR
(B) 2 OR, 1 AND 2 OR
(C) 2 OR, 1 AND 1 OR, 1 AND
(D) 2 OR, 2 AND 2 OR
(E) 2 OR, 2 AND 2 OR, 1 AND
38
iClicker Question
a+0=a (a+b)(a+c) a + bc
a+1=1
a+ā=1
a·0 =0 How many gates were
a·1 =a required before and after?
a·ā =0
a+ab =a BEFORE AFTER
a (b+c) = ab + ac (A) 2 OR 1 OR
(B) 2 OR, 1 AND 2 OR
(C) 2 OR, 1 AND 1 OR, 1 AND
(D) 2 OR, 2 AND 2 OR
(E) 2 OR, 2 AND 2 OR, 1 AND
39
Checking Equality w/Truth Tables
circuits ↔ truth tables ↔ equations
Example: (a+b)(a+c) = a + bc
a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 40
Checking Equality w/Truth Tables
circuits ↔ truth tables ↔ equations
Example: (a+b)(a+c) = a + bc
a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Checking Equality w/Truth Tables
circuits ↔ truth tables ↔ equations
Example: (a+b)(a+c) = a + bc
a b c a+b a+c LHS bc RHS
0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 1 1 1 1
1 0 0 1 1 1 0 1
1 0 1 1 1 1 0 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1 42
Takeaway
• Binary (two symbols: true and false) is the basis
of Logic Design
• More than one Logic Circuit can implement
same Logic function. Use Algebra (Identities) or
Truth Tables to show equivalence.
43
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
• From switches
• Truth Tables
• Logic Circuits
• From Truth Tables to Circuits (Sum of Products)
• Identity Laws
• Logic Circuit Minimization
• Algebraic Manipulations
• Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
44
Karnaugh Maps
How does one find the most efficient equation?
– Manipulate algebraically until…?
– Use Karnaugh Maps (optimize visually)
– Use a software optimizer
For large circuits
– Decomposition & reuse of building blocks
45
Minimization with Karnaugh maps (1)
Sum of minterms yields
�
out = abc + a� bc + abc + abc
a b c out
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
46
Minimization with Karnaugh maps (2)
Sum of minterms yields
�
out = abc + a� bc + abc + abc
a b c out
0 0 0 0
0 0 1 1
0 1 0 0 Karnaugh maps identify
0 1 1 1
1 0 0 1
which inputs are (ir)relevant
1 0 1 1 to the output
1 1 0 0
1 1 1 0
ab
c 00 01 11 10
0 0 0 0 1
1 1 1 0 1
47
Minimization with Karnaugh maps (2)
Sum of minterms yields
�
out = abc + a� bc + abc + abc
a b c out
0 0 0 0
0 0 1 1
0 1 0 0 Karnaugh map minimization
0 1 1 1
1 0 0 1
Cover all 1’s
1 0 1 1 Group adjacent blocks of 2n
1 1 0 0
1 1 1 0
1’s that yield a rectangular
shape
ab
c 00 01 11 10 Encode the common features
of the rectangle
0 0 0 0 1
out = ab� + a� c
1 1 1 0 1
48
Karnaugh Minimization Tricks (1)
ab
c 00 01 11 10
Minterms can overlap
0 0 1 1 1
out = b�c + a�c + ab
1 0 0 1 0
ab
c 00 01 11 10
0 1 1 1 1 Minterms can span 2, 4, 8
1 0 0 1 0
or more cells
out = c� + ab
49
Karnaugh Minimization Tricks (2)
ab
cd 00 01 11 10
00 0 0 0 0 • The map wraps around
01 1 0 0 1 �
out = bd
11 1 0 0 1
10 0 0 0 0
ab
cd 00 01 11 10
00 1 0 0 1 out = b� d�
01 0 0 0 0
11 0 0 0 0
10 1 0 0 1
50
Karnaugh Minimization Tricks (3)
ab
cd 00 01 11 10
00 0 0 0 0 • “Don’t care” values can be
01 1 x x x interpreted individually in
11 1 x x 1 whatever way is convenient
10 0 0 0 0 assume all x’s = 1
out = d
ab
cd 00 01 11 10
00 1 0 0 x assume middle x’s = 0
01 0 x x 0 assume 4th column x = 1
11 0 x x 0 out = b� d�
10 1 0 0 1
51
Minimization with K-Maps
ab
c 00 01 11 10 (1) Circle the 1’s (see below)
0 0 0 0 1 (2) Each circle is a logical
component of the final equation
1 1 1 0 1
= ab� + a� c
Rules:
• Use fewest circles necessary to cover all 1’s
• Circles must cover only 1’s
• Circles span rectangles of size power of 2 (1, 2, 4, 8…)
• Circles should be as large as possible (all circles of 1?)
• Circles may wrap around edges of K-Map
• 1 may be circled multiple times if that means fewer
circles
52
Multiplexer
• A multiplexer selects
a between multiple inputs
b out = a, if d = 0
out = b, if d = 1
d
a b d out • Build truth table
0 0 0
0 0 1
• Minimize diagram
0 1 0 • Derive logic diagram
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
53
Multiplexer Implementation
b • Build a truth table
d
out = a� bd + abd + abd� + abd
a b d out
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
54
Multiplexer Implementation
b • Build the Karnaugh map
d
ab
d 00 01 11 10
a b d out
0
0 0 0 0
0 0 1 0 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
55
Multiplexer Implementation
b • Build the Karnaugh map
d
ab
d 00 01 11 10
a b d out
0 0 0 1 1
0 0 0 0
0 0 1 0 1 0 1 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
56
Multiplexer Implementation
b • Derive Minimal Logic
d
Equation
ab
d 00 01 11 10
a b d out
0 0 0 1 1
0 0 0 0
0 0 1 0 1 0 1 1 0
0 1 0 0
0 1 1 1 • out = ad� + bd
1 0 0 1 a
1 0 1 0
1 1 0 1 d
1 1 1 1
b 57
Takeaway
• Binary (two symbols: true and false) is the basis
of Logic Design
• More than one Logic Circuit can implement
same Logic function. Use Algebra (Identities) or
Truth Tables to show equivalence.
• Any logic function can be implemented as “sum
of products”. Karnaugh Maps minimize number
of gates.
58
Administrivia
• Dates to keep in Mind
• Prelims: Tue Mar 5th and Thur May 2nd
• Proj 1: Due Fri Feb 15th
• Proj 2: Due Fri Mar 11th
• Proj 3: Due Thur Mar 28th before Spring break
• Final Project: Due Tue May 16th
59
iClicker
• Attempt to balance the iClicker graph
• Register iClicker
• [Link]
60
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
• From switches
• Truth Tables
• Logic Circuits
• From Truth Tables to Circuits (Sum of Products)
• Identity Laws
• Logic Circuit Minimization
• Algebraic Manipulations
• Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
61
Silicon Valley & the Semiconductor Industry
• Transistors:
• Youtube video “How does a transistor work”
[Link]
• Break: show some Transistor, Fab, Wafer photos
62
Transistors 101
Source Gate Drain Source Gate Drain
—
Insulator Insulator
- + + + + + + + + - - + + + + -
+ + channel created
+ + P-type
- + + + - - - + + + - - + + + - +- - + ++ -
P-type - P-type P-type - P-type
- N-type - - N-type -
- - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
Off
P-Transistor P-Transistor On
N-Type Silicon: negative free-carriers (electrons)
P-Type Silicon: positive free-carriers (holes)
P-Transistor: negative charge on gate generates electric field
that creates a (+ charged) p-channel connecting source &
drain
N-Transistor: works the opposite way
Metal-Oxide Semiconductor (Gate-Insulator-Silicon)
• Complementary MOS = CMOS technology uses both p- & n-
type transistors
63
CMOS Notation
N-type Off/Open On/Closed
0 1
gate
P-type
Off/Open On/Closed
1 0
gate
Gate input controls whether current can flow between
the other two terminals or not.
Hint: the “o” bubble of the p-type tells you that this gate
wants a 0 to be turned on
64
iClicker Question
Which of the following statements is false?
(A) P- and N-type transistors are both used in
CMOS designs.
(B) As transistors get smaller, the frequency of
your processor will keep getting faster.
(C) As transistors get smaller, you can fit more
and more of them on a single chip.
(D) Pure silicon is a semi conductor.
(E) Experts believe that Moore’s Law will soon
end.
65
2-Transistor Combination: NOT
• Logic gates are constructed by combining
transistors in complementary arrangements
• Combine p&n transistors to make a NOT gate:
CMOS Inverter :
power source (1) power source (1) power source (1)
p-gate — p-gate + p-gate
closes stays open
0 1 1 0
input output
n-gate
n-gate n-gate
— + closes
stays open
ground (0) ground (0) ground (0)
66
Inverter
Vsupply (aka logic 1)
Function: NOT
Symbol:
in out
in out
(ground is logic 0)
Truth Table:
In Out
0 1
1 0
67
NOR Gate
Vsupply
Function: NOR
A Symbol:
B a out
b
out
A B
Truth Table:
A B out
0 0 1
0 1 0
1 0 0
1 1 0 68
iClicker Question
Which Gate is this? Function:
Vsupply Vsupply
Symbol:
A B
out
B Truth Table:
A A B out
0 0
(A) NOT
0 1
(B) OR
(C) XOR 1 0
(D) AND 1 1
(E) NAND 69
iClicker Question
Which Gate is this? Function:
Vsupply Vsupply
Symbol:
A B
out
B Truth Table:
A A B out
0 0 1
(A) NOT
0 1 1
(B) OR
(C) XOR 1 0 1
(D) AND 1 1 0
(E) NAND 70
Building Functions (Revisited)
• NOT:
• AND:
• OR:
• NAND and NOR are universal
Can implement any function with NAND or just NOR gates
useful for manufacturing 71
Building Functions (Revisited)
a
• NOT:
a
• AND: b
a
• OR: b
• NAND and NOR are universal
Can implement any function with NAND or just NOR gates
useful for manufacturing 72
Logic Gates
• One can buy gates
separately
• ex. 74xxx series of
integrated circuits
• cost ~$1 per chip, mostly
for packaging and testing
• Cumbersome, but
possible to build devices
using gates put together
manually
73
Then and Now
[Link]
• The first transistor • Intel Haswell
• One workbench at AT&T Bell Labs • 1.4 billion transistors, 22nm
• 1947 • 177 square millimeters
• Bardeen, Brattain, and Shockley • Four processing cores
74
[Link]
Then and Now
[Link]
• The first transistor • Intel Broadwell
• One workbench at AT&T Bell Labs • 7.2 billion transistors, 14nm
• 1947 • 456 square millimeters
• Bardeen, Brattain, and Shockley • Up to 22 processing cores
75
[Link]
Big Picture: Abstraction
• Hide complexity through simple abstractions
Simplicity
• Box diagram represents inputs and outputs
Complexity
• Hides underlying NMOS- and PMOS-transistors and
atomic interactions
Vdd a
in out d out
Vss b
a
d out
in out
b 76
Summary
• Most modern devices made of billions of transistors
• You will build a processor in this course!
• Modern transistors made from semiconductor materials
• Transistors used to make logic gates and logic circuits
• We can now implement any logic circuit
• Use P- & N-transistors to implement NAND/NOR gates
• Use NAND or NOR gates to implement the logic circuit
• Efficiently: use K-maps to find required minimal terms
77