Digital Circuits This work is licensed under a Creative Commons Attribution 4.0 License.

Digital Circuits
License: https://creativecommons.org/licenses/by-nc-nd/4.0/

Boolean Algebra  The Duality principle:

George Boole (1815-1864) English mathematician and philosopher. A dual of a logical expression is obtained by replacing, • by +, + by •, 0 by 1, and
a • b (AND) a + b (OR) Complement 1 by 0, without changing the variables.
 Defined on the set B = {0,1} b b a + b + 0 ... ⇔ a • b • 1 ...
0 1 0 1 a a'
 Binary operators: AND, OR { • , + } Example: The dual of the expression a + a⋅b is a⋅(a+b) .
a a (a)
 Unary operation: Complement (NOT) {'} Principle: Duals of all proven theorems (equations) are also valid.
0 0 0 0 0 1 0 1
Another symbol for the NOT operator: a If we know that an equation (theorem) is true, then the dual of this equation
1 0 1 1 1 1 1 0
 Axioms (Laws): (theorem) is also true.
Under assumption a , b ∈ B Note that in the previous slide, axioms were presented with their duals (two
1. Closure: a+b∈B a•b∈B columns).
2. Commutative: a+b=b+a a•b=b•a Example:
3. Associative: a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c Absorption theorem (given in the next slide):
4. Identity: a+0=a a•1=a If we can prove the theorem a + a⋅b = a, then its dual a⋅(a+b) = a is also true.
5. Distributive: a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c) General Duality Principle:
6. Inverse: a+a=1 a•a=0 f (X1, X2, ..., Xn, 0, 1, +, •) ⇔ fD(X1, X2 ,..., Xn, 1, 0, •, +)
• It establishes relation between proofs of theorems.
 Precedence order of operators from higher to lower precedence:
1. Parenthesis, 2. NOT (Complement) (Negation), 3. AND, 4. OR • Duals are not equal.
http://akademi.itu.edu.tr/en/buzluca/ 2.1 http://akademi.itu.edu.tr/en/buzluca/ 2.2
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Theorems: Proving the theorems:

These theorems are derived from the operations and axioms of Boolean algebra.
They can be proven using the axioms.
a) With Axioms
1. Annihilator (or Dominance):
a+1=1 a•0=0 Example:
2. Involution: (a')' = a or a = a Theorem: · ·
Proof:
3. Idempotency: Distributive · · ·
a+a+a+….+a = a a•a•a •… •a = a Inverse (Complement) · · 1
4. Absorption: Identity · 1 
(Proof in 2.4)
a + a⋅b = a a⋅(a+b) = a Example:
5. De Morgan's Theorem: Augustus De Morgan, British mathematician and logician (1806 – 1871) Theorem: X+X•Y = X (Absorption)
(a + b) = a • b (a • b) = a + b Proof:
Identity X + X•Y = X•1 + X•Y
5. General form of De Morgan's Theorem: Distributive X•1 + X•Y = X • (1 + Y)
f (X1, X2, ..., Xn, 0 ,1, + , •) = g(X1, X2 ,..., Xn, 1 , 0, •, +) Annihilator X • (1 + Y) = X • (1)
Identity X • (1) = X
• It establishes relations between binary operations (AND, OR): • and +
http://akademi.itu.edu.tr/en/buzluca/ 2.3 http://akademi.itu.edu.tr/en/buzluca/ 2.4
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Minimizing logical expressions using axioms and theorems:

Proving the theorems: b) Using truth tables Minimizing a logical expression means;
• finding the shortest expression
Note that to denote the negation (NOT), we can also use the notation A. • with less operations and variables
• that generates same output values as the original expression.
Example:
De Morgan:
Z(A,B,C) = A'⋅B⋅C + A⋅B'⋅C + A⋅B⋅C' + A⋅B⋅C Original expression

X Y X Y (X + Y) X • Y = A' B C + A B' C + A B C' + A B C + A B C

(X + Y) = X • Y 0 0 1 1 1 1 = A' B C + A B C + A B' C + A B C' + A B C
0 1 1 0 0 0
1 0 0 1 0 0 = (A' + A) B C + A B' C + A B C' + A B C
1 1 0 0 0 0 = (1) B C + A B' C + A B C' + A B C
= B C + A B' C + A B C' + A B C + A B C
X Y X Y (X • Y) X + Y
(X • Y) = X + Y 0 0 1 1 1 1 = B C + A B' C + A B C + A B C' + A B C
0 1 1 0 1 1 = B C + A (B' + B) C + A B C' + A B C
1 0 0 1 1 1
1 1 0 0 0 0 = B C + A (1) C + A B C' + A B C
= B C + A C + A B (C' + C)
Although truth tables may contain many rows, computer programs can fill in
and compare these tables very quickly.
= B C + A C + A B (1)
= BC + AC + AB Minimized expression
http://akademi.itu.edu.tr/en/buzluca/ 2.5 http://akademi.itu.edu.tr/en/buzluca/ 2.6
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

Logical (Boolean) Expressions Value of a logical expression:

A logical expression, is a finite combination of variables, constants, and
operators that are well-formed according to the rules. An expression, E(X), generates for each combination of the input vector
It is represented as E(X), where X= (x1, x2, .... xn) and each xi ∈ {0,1}. X=(x1, .... xn), a value from the set of B={0,1}.
If E1 and E2 are logical expressions than, , , , · , and all possible These values constitute the truth table for the expression.
combinations are also logical expressions.
Example: E(X) = x1x2 + x3
Normal Forms of Logical expressions:
Truth table for the expression
Each logical expression can be written in two special forms.
1. Disjunctive normal form (DNF): ΣΠ X= x1 x2 x3 E(X)
Combinations for
Logical sum of logical products (SOP). OR of ANDs. 0 0 0 0 Set of all input
which E(X)
Example: ̅ 0 0 1 1 combinations
generates ‘1’
0 1 0 0 (X)
The OR operation is also called logical disjunction. (covers)
2. Conjunctive normal form (CNF): ΠΣ 0 1 1 1
Logical product of logical sums (POS). AND of ORs. 1 0 0 0 000 001
Example: ̅ 1 0 1 1 010 011
The AND operation is also called logical conjunction.
1 1 0 1 100 101
1 1 1 1 111 110
Any logical expression can be written in CNF (POS form) and DNF (SOP form).
Any expression in CNF can be converted to DNF and vice versa (ΣΠ ↔ ΠΣ).
http://akademi.itu.edu.tr/en/buzluca/ 2.7 http://akademi.itu.edu.tr/en/buzluca/ 2.8
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

"Order Relation" between expressions: Order relation between expressions:

To explain some properties of the logical expressions, we can use the following E1(X) ≤ E2(X) denotes that, values of E1 generated by combinations of input X are always
order relation: smaller than (or equal to) all values of E2 generated by the same input combinations.

An order relation between elements of set B = {0,1}: 0 < 1 Example : Combinations for which
Set of all input E2(X) generates ‘1’
Read as "0 precedes 1" or "0 is smaller than 1". x1 x2 x3 E1(X) E2(X) combinations (X) (covers)
0 0 0 0 = 0
According to this, an order relation between X vectors can be defined as follows: 0 0 1 1 = 1
Combinations
If all elements of X1 precede (are smaller than) elements in the same order of 0 1 0 0 < 1
E2 for which
vector X2, then X1 ≤ X2 . 0 1 1 1 = 1 000
E1(X)
1 0 0 0 = 0 010 generates ‘1’
100 E1
1 0 1 1 = 1 110 001 (covers)
Example: 1 1 0 0 < 1 011 101
X1=1001 , X2 = 1101 1 1 1 1 = 1 111
X1 ≤ X2. For each input combination where If E1(X) ≤ E2(X)
E1(X) generates "1", E2(X) also
The order relation may not exist between all vectors. E1(X) implies E2(X), E1(X)E2(X),
generates "1". (This is a special case.)
E2(X) covers E1(X).
Example: X1=0011 , X2 = 1001 If E1(X) ≤ E2(X) then
The order relation is not valid between X1 and X2. 1. E1(X) + E2(X) = E2(X)
2. E1(X) • E2(X) = E1(X)
http://akademi.itu.edu.tr/en/buzluca/ 2.9 http://akademi.itu.edu.tr/en/buzluca/ 2.10
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

The order relation (≤) may not be valid between all expressions. Example:
E(a,b,c,d) = abc′ , F(a,b,c,d) = bd An order relation between E and F does not
IF E and F are two logical expressions, the E⋅F = abc′d E+F = abc′ + bd exist.
following inequalities are always true:
F
E E⋅F ≤ E ≤ E+F abcd
0000
E
0
F
0
E⋅F
0
E+F
0
E⋅F < E and E⋅F < F.
Therefore
E⋅F ≤ F ≤ E+F 0001 0 0 0 0
E⋅F + E = E
0010 0 0 0 0
0011 0 0 0 0 abc′d + abc′ = abc′
0100 0 0 0 0 and
Absorption Properties of expressions: 0101 0 1 0 1
0110 0 0 0 0 E⋅F + F = F
· dual 0111 0 1 0 1 abc′d + bd = bd
1000 0 0 0 0
1001 0 0 0 0 E < E+F and F < E+F.
Proof: E(E+F) = EE+EF = E+EF = E(1+F) = E 1010 0 0 0 0
Therefore
1011 0 0 0 0
1100 1 0 0 1 E⋅(E + F) = E
· dual · 1101 1 1 1 1 abc′ (abc′ + bd) = abc′
1110 0 0 0 0
and
Proof: · 1 1111 0 1 0 1
F⋅(E + F) = F
These properties are used to minimize (simplify) logical expressions. bd (abc′ + bd) = bd
http://akademi.itu.edu.tr/en/buzluca/ 2.11 http://akademi.itu.edu.tr/en/buzluca/ 2.12
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

The Consensus Theorem (SOP Form) The Consensus theorem (POS Form)
Assume that E1 and E2 are two expressions that do not include the literal x1 : According to the duality principle, the consensus theorem is also valid for
E1(x2, .... xn) and E2(x2, .... xm) expressions written in product of sums (POS) form.
We can create a new expression by multiplying one term by x1 and the other one by Assume that E1 and E2 are two expressions that do not include the literal x1:
the complement of x1 ( ). E1(x2, .... xn) and E2(x2, .... xm)
We can create a new expression by adding x1 to one term and the complement of x1
Here, x1 is called a biform variable because it occurs both positively (as itself: ) to the other one.
and negatively (as complement: ) in the expression.

Examples: , Here, x1 is a biform variable.

Examples: ,
• Given a pair of product terms that include a biform variable, the consensus term
(SOP) is formed by multiplying (AND) two original terms together, leaving out the • Given a pair of sums that include a biform variable, the consensus term (POS)
selected variable and its complement. is formed by adding (OR) two original terms together, leaving out the selected
• E1E2 is the consensus term of with respect to the variable x. variable and its complement.
• E1 + E2 is the consensus term of with respect to the variable x.
Example: Consensus of (respect to a) is .
Example: Consensus of is: .
Theorem: The consensus term is redundant and can be eliminated.
Theorem: The consensus term is redundant and can be eliminated.

http://akademi.itu.edu.tr/en/buzluca/ 2.13 http://akademi.itu.edu.tr/en/buzluca/ 2.14

http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Logical (Boolean) Functions

Example: Minimization of a logical expression using the consensus theorem
Logical functions are defined on the input set Bn (vectors with n binary variables).
F(A, B, C) = A'B'C + A'BC + AB'C + ABC + ABC' There are 3 types of logical functions:
Consensus (respect to C)
= A'B'C + A'BC + AB'C + ABC + ABC' + AB is added 1. Simple (basic) functions: Multiple inputs, single output
= A'B'C + A'BC + AB'C + ABC + ABC' + AB Absorption y = f(X): Bn → B
= A'B'C + A'BC + AB'C + AB ∀X0∈Bn ; ∃! y0 ∈B ; y=f(X)
Consensus (respect to B)
"There exists a unique..."
= A'B'C + A'BC + A'C + AB'C + AB is added
= A'B'C + A'BC + A'C + AB'C + AB Absorption The truth table for y = f(X)
= A'C + AB'C + AB Example: x1 x2 x3 y
Consensus (B) is added y = f(X) x1 000 1
= A'C + AB'C + AB + AC Absorption
X∈B3
x2
x3
f y 001 1
= A'C + AB + AC 010 0
Consensus (A) is added y∈B
011 0
= A'C + AB + AC + C Absorption 100 1
= AB + C 101 0
110 0
111 1
http://akademi.itu.edu.tr/en/buzluca/ 2.15 http://akademi.itu.edu.tr/en/buzluca/ 2.16
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

The number of basic logical functions for n binary variables: 2. General functions: Multiple inputs, multiple outputs
( 2n)
There are 2 possible basic logical functions for n binary variables (inputs).
For example, Y = f(X): Bn → Bm , X=(x1, .... xn), Y=(y1, .... ym),
there are 16 possible basic logical functions for 2 binary variables (inputs).

x
f z
y
Example: The truth table for Y = f(X)
The truth table for 16 possible basic logical functions for 2 binary variables:
x1 x2 x3 y1 y2
Inputs Functions Y = f(X) x1 y1
000 1 1
X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 X∈B3 x2
x3
f y2 001 1 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Y∈B2
010 0 0
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
011 0 0
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
100 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
101 0 1
0 1 110 0 1
X Y Y' X'
X XOR Y X=Y X NAND Y 111 1 0
X AND Y
X OR Y X NOR Y
(X AND Y)'
(X OR Y)'
http://akademi.itu.edu.tr/en/buzluca/ 2.17 http://akademi.itu.edu.tr/en/buzluca/ 2.18
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

3. Incompletely specified functions:

Representation of Logical (Boolean) Functions
They have unspecified outputs for some input combinations.
There are different ways of representing (expressing) the same logical function.
The input combinations of the function that the designer does not care about are
called the don't-care terms (conditions). When designing logical circuits, we choose the most suitable representation.
A don't-care input combination never occurs as input to the function.
Truth Table Representation :
I8 I4 I2 I1 O8 O4 O2 O1
0 0 0 0 0 0 0 1 We write the output values for all possible input combinations (variables) in a table.
Example: A function that increments
0 0 0 1 0 0 1 0 The input columns are usually constructed in the order of binary counting.
BCD numbers (Slide 1.9)
0 0 1 0 0 0 1 1
I1 O1 0 0 1 1 0 1 0 0 Input variables are encoded as binary numbers.
0 1 0 0 0 1 0 1 (See examples in 2.16-2.19)
I2 BCD O2
0 1 0 1 0 1 1 0
I4 +1 O4 0 1 1 0 0 1 1 1 Numbered (Indexed) Representation:
I8 O8 0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1 Input variables are encoded as binary numbers.
1 0 0 1 0 0 0 0
1 0 1 0 X X X X We can assign a decimal number for each input combination according to its binary
For these input combinations the output values 1 0 1 1 X X X X value.
of the circuit (function) are not specified. 1 1 0 0 X X X X
1 1 0 1 X X X X To represent the function we can list the index (row) number of input combinations
They cannot occur.
1 1 1 0 X X X X for which the function generates the logical value "1" (or logical "0“ or ”Φ”).
An X or Φ represents a don't care.
1 1 1 1 X X X X

http://akademi.itu.edu.tr/en/buzluca/ 2.19 http://akademi.itu.edu.tr/en/buzluca/ 2.20

http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Example: Indexed representation of a completely specified basic logical function: Example: Representation of a completely specified general logical function :
Truth Table: Numbered (Indexed) Representation: We apply the numbered representation to all outputs.
Row Input Output y = f(x1,x2) = ∪1(0,2) ∪ denotes "union" or "set of".
Num x1 x2 y Truth Table: Numbered (Indexed) Representation:
∪1 denotes "set of 1-generating
0 0 0 1
points".
1 0 1 0 Num x1 x2 y1 y2
2 1 0 1 0 0 0 1 1 y1 = f(x1,x2) = ∪1(0,2)
3 1 1 0 The order of the variables (x1,x2) is important.
1 0 1 0 1 y2 = f(x1,x2) = ∪1(0,1)
It must be the same as in the truth table.
2 1 0 1 0
Otherwise the numbers of the combinations will change.
The same function; only 3 1 1 0 0
the order of the variables
(x2,x1) is changed.
Row Input Output y = f(x2,x1) = ∪1(0,1) Representation of the same function with “0”-genereting combinations:
Num x2 x1 y
0 0 0 1
1 0 1 1 y1 = f(x1,x2) = ∪0(1,3)
2 1 0 0 We can represent the same function with “0”-genereting y2 = f(x1,x2) = ∪0(2,3)
3 1 1 0 combinations. y = f(x ,x ) = ∪ (1,3)
1 2 0

y = f(x1,x2) = ∪1(0,2) = f(x2,x1) = ∪1(0,1) = f(x1,x2) = ∪0(1,3)

http://akademi.itu.edu.tr/en/buzluca/ 2.21 http://akademi.itu.edu.tr/en/buzluca/ 2.22
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Example: Representation of an incompletely general logical function: Graphical Representation

The input variables (combinations) of a logical function are elements (vectors) of
In this case, writing only 1-generating or only 0-generating input combinations the set Bn. Example: B3={000, 001, …, 111}
is not sufficient. We can represent these variables as vertices of an n-dimensional hypercube.
We must write at least two of the three different groups (1-generating,
Vertices that correspond to 1-generating combinations are colored (marked).
0-generating, don't care).
The number of inputs of the function determines how many dimensions the
Truth Table: Numbered (Indexed) Representations: hypercube has.
n-bit input → n-dimensional cube
N x1 x2 y1 y2
y1 = f(x1,x2) = ∪1(0) + ∪0(1,3) Boolean Cubes: 01 11
0 0 0 1 1
1 0 1 0 Φ or y1 = f(x1,x2) = ∪1(0) + ∪Φ(2) 0 1
Y
2- dimensional
1-dimensional f(X,Y)
2 1 0 Φ 0 or y1 = f(x1,x2) = ∪0(1,3) + ∪Φ(2) f(X) X
00 10
3 1 1 0 Φ X
y2 = f(x1,x2) = ∪1(0) + ∪0(2) 1111
y2 = f(x1,x2) = ∪1(0) + ∪Φ(1,3) 111 0111
or
or y2 = f(x1,x2) = ∪0(2) + ∪Φ(1,3) 4- dimensional
3- dimensional
f(X,Y,Z) Y Z Y f(W,X,Y,Z)
101 Z
W
000 1000
X 0000 X
http://akademi.itu.edu.tr/en/buzluca/ 2.23 http://akademi.itu.edu.tr/en/buzluca/ 2.24
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

Example: A B F Karnaugh Maps

01 11
F(A,B) 0 0 1 (Maurice Karnaugh (1924-), American physicist and mathematician)
B
0 1 0
The Karnaugh map is a tool for representing and simplifying Boolean functions.
1 0 1 00 10
A The Boolean variables and related output values are transferred (generally from a
1 1 0 truth table) into a table that is in a matrix form.
Example: A B C F
F(A,B,C) 0 0 0 0 Example: F(A,B)
011 111
0 0 1 0
0 1 0 0 Truth table: Boolean Cube: Karnaugh maps:
0 1 1 1 110 Row
Num. A B F F F
1 0 0 0 B C 101 11 B A
01 A 0 1 B 0 1
1 0 1 1 0 0 0 1
1 1 0 1 000 A B 0 1 0 0 1 1
1 1 1 1
1 0 1 0 0 1 or 0 2
2 1 0 1 00 10 1 1 0 1 0 0
As the number of variables (inputs) increases, drawing a Boolean cube becomes A 2 3 1 3
more difficult. 3 1 1 0
A: row, B: column A: column, B: row
Therefore, Boolean cubes are not practical for representing Boolean functions
with many inputs.
We can place different
However, they make it easier to visualize some properties (especially, adjacent variables to columns or rows.
combinations) of the functions and to explain further topics.
http://akademi.itu.edu.tr/en/buzluca/ 2.25 http://akademi.itu.edu.tr/en/buzluca/ 2.26
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Karnaugh map (cont'd) Format of the Karnaugh map of a function with 4 inputs: F(A,B,C,D)
The rows and columns are labeled according to the Gray code property, so that
variables in adjacent squares (horizontal and vertical) of the map differ in only F CD C D
one variable. AB 00 01 11 10 Gray Code
Format of the Karnaugh map for a function with 3 inputs: F(A,B,C) 00
0 1 3 2
For example, we write here the output value 01
Gray Code
F BC F BC
generated for the input combination ABC=010. Gray Code 4 5 7 6

A 00 01 11 10 A 11
12 13 15 14
Inputs

0 000 001 011 010 10

0 1 3 2 Row Adjacent squares.
8 9 11 10
1 Numbers Hamming distance is 1.
100 101 111 110 F CD
4 5 7 6
AB 00 01 11 10
Example: 00 1 0 0 1
Example: Num A B C F Draw the Karnaugh map for the following
0 0 0 0 0 function. 01 0 1 0 0
1 0 0 1 0 F BC F(A,B,C,D) = ∪1 (0,2,5,8,9,10,11,12,13,14,15)
2 0 1 0 0 A 00 01 11 10 11 1 1 1 1
3 0 1 1 1 0 0 0 1 0
4 1 0 0 0 0 1 3 2 1 1 1 1
10
5 1 0 1 1 1
40 51 7 1 6 1
6 1 1 0 1
7 1 1 1 1 We will use Karnaugh maps to simplify Boolean functions in the coming lectures.
http://akademi.itu.edu.tr/en/buzluca/ 2.27 http://akademi.itu.edu.tr/en/buzluca/ 2.28
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Algebraic Representation (Expressions) and Canonical Forms 1st Canonical Form: Sum of Products
The word description of a real-world logic design problem can be translated into a
truth table. • The 1st canonical form is the sum of special products called minterm.
Example: Assume that input variable A represents the phrase ‘’the car door is • In the 1st canonical form, each product in the sum corresponds to a row in the
open’’, B represents ‘’the key is inserted’’, truth table with the output "1".
then the truth table can specify the action Z to be taken, where Z=1 means that • Minterm: For a Boolean function of n variables, a product of n literals in which
the alarm sounds. each variable appears exactly once (in either true or complemented form, but
Num. A B Z
Truth tables of real-world digital problems are more not both) is called a minterm.
0 0 0 0 complicated. For example, a function with 3 variables (a, b, c) has 8 minterms:
1 0 1 0 To handle a logic design problem and implement the solution a'b'c', a'b'c, a'bc', a'bc, ab'c', ab'c, abc', abc
2 1 0 0 using logic gates, we need to obtain an algebraic expression • Each minterm that appears in the 1st canonical form covers only one row of
3 1 1 1 for the output function. Z = f (A,B)
the truth table with the output "1".
Logical expressions of the Boolean functions can be obtained in canonical forms For example; the minterm a'b'c' can generate "1" only for the input value
from their truth tables. abc=000.
There are two types of canonical forms: For all other input combinations the minterm a'b'c' generates "0".
• 1st canonical form: SOP (ΣΠ) form. Example: abc + ab'c • The 1st canonical form of a function is the sum of minterms.
Sum of products, each of which corresponds to a "1"-generating combination.
• 2nd canonical form: POS (ΠΣ) form. Example: (a+b+c') (a+b'+c')
Product of sums, each of which corresponds to a "0"-generating combination.
http://akademi.itu.edu.tr/en/buzluca/ 2.29 http://akademi.itu.edu.tr/en/buzluca/ 2.30
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

Finding minterms: The 1st canonical form of the complement of a function:

Truth Table → Expression in SOP form We can similarly obtain the 1st canonical form of the complement of a function
• To find minterms, we locate all rows in the truth table where the output is "1". by considering the "false" (0) rows.
• To obtain the individual minterms, we substitute variables (for example, A, B, Example:
or C) for ones (of the inputs) and complements of variables (A', B', or C') for
zeros in the truth table. Obtain the 1st canonical form of the complement of a function F from the
previous example.
Example: 1st canonical form of !:
! ", $, % "$% "$% "$%
"True" (1) combinations: 001 011 101 110 111
Sum of Minterms: F(A,B,C) = A'B'C + A'BC + AB'C + ABC' + ABC A B C F F'
0 0 0 0 1
0 0 1 1 0
A B C F 0 1 0 0 1
0 0 0 0 0 1 1 1 0
0 0 1 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 1 1 0 1 0
1 0 0 0 1 1 1 1 0
1 0 1 1
1 1 0 1
1 1 1 1

http://akademi.itu.edu.tr/en/buzluca/ 2.31 http://akademi.itu.edu.tr/en/buzluca/ 2.32

http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Simplification of the expressions in the 1st canonical form: Indexing minterms:

Canonical forms are usually not the simplest (optimal) algebraic expression of the We assign each minterm an index (number) based on the binary encoding of the
function. variables.
They can usually be simplified. This is a decimal number that represents the row number (Row numbers start at 0).
For example, we assign the index 5 to the minterm ab'c (101) and designate it m5.
Minimization:
F(A, B, C) = A'B'C + A'BC + AB'C + ABC + ABC' Inputs:
A B C Minterms
= (A'B' + A'B + AB' + AB)C + ABC' 0 0 0 A'B'C' = m0
= ((A' + A)(B' + B))C + ABC' 0 0 1 A'B'C = m1
= C + ABC' 0 1 0 A'BC' = m2
= ABC' + C 0 1 1 A'BC = m3
= AB + C 1 0 0 AB'C' = m4
• A Boolean function may have many possible logical expressions. They produce 1 0 1 AB'C = m5 Example:
the same result given the same inputs. 1 1 0 ABC' = m6
Expression of function F in (2.31) in 1st canonical form:
1 1 1 ABC = m7
• Since the minterms present in the 1st canonical form are in one-to-one F(A, B, C) = Σm(1,3,5,6,7)
correspondence with the 1’s of the truth table, the 1st canonical (standard)
form expression for a function is unique. Minterms for three variables = m1 + m3 + m5 + m6 + m7
= A'B'C + A'BC + AB'C + ABC' + ABC
• A function can have only one expression in the 1st canonical form.
F = ΣA, B, C (1,3,5,6,7) (Sum of minterms)

http://akademi.itu.edu.tr/en/buzluca/ 2.33 http://akademi.itu.edu.tr/en/buzluca/ 2.34

http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Finding maxterms:
2nd Canonical Form: Product of Sums
Truth Table → Expression in POS form
• The 2nd canonical form is the product of special sum terms called maxterm. • To find the maxterms, we locate all rows in the truth table where the output is
• In the 2nd canonical form, each of the sum terms (or factors) in the product "0".
corresponds to a row in the truth table with the output "0". • To obtain the individual maxterms, we substitute variables (for example, A, B,
• Maxterm: For a Boolean function of n variables, a sum of n literals in which or C) for zeros (of the inputs) and complements of variables (A', B', or C') for
each variable appears exactly once (in either true or complemented form, ones in the truth table.
but not both) is called a maxterm. Example:
• For example, a function with 3 variables (a, b, c) has 8 maxterms: "False" (0) generating combinations: 000 010 100
Product of maxterms: F(A,B,C) = (A + B + C) (A + B' + C) (A' + B + C)
a+b+c, a+b+c', a+b'+c, a+b'+c', a'+b+c, a'+b+c', a'+b'+c, a'+b'+c'
• Each maxterm has a value of "0" for exactly one combination of values for A B C F
the input variables. 0 0 0 0
0 0 1 1
For example; the maxterm a+b+c can generate "0" only for the input value 0 1 0 0
abc=000. 0 1 1 1
1 0 0 0
For all other input combinations the maxterm a+b+c generates "1". 1 0 1 1
1 1 0 1
• The 2nd canonical form of a function is the product of maxterms. 1 1 1 1
Note that this function F is the same as the function in slide 2.31.
Both expressions in 1st and 2nd canonical forms correspond to the same truth
table.
http://akademi.itu.edu.tr/en/buzluca/ 2.35 http://akademi.itu.edu.tr/en/buzluca/ 2.36
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

The 2nd canonical form of the complement of a function: Simplification of the expressions in the 2nd canonical form:
We can similarly obtain the 2nd canonical form of the complement of a function Canonical forms are usually not the simplest (optimal) algebraic expression of the
by considering the "true" (1) rows: function.
They can usually be simplified.
Example:
Obtain the 2nd canonical form of the complement of a function F from the Minimization:
previous example. F(A, B, C) = (A+B+C) (A+B’+C) (A’+B+C)
2nd canonical form of F: = ((A+C)+(B⋅B')) (A'+B+C)
= (A+C) (A'+B+C)
= (A+C) (A'+B+C) (B+C) (consensus)
F'(A,B,C) = (A + B + C') (A + B' + C') (A' + B + C') (A' + B' + C) (A' + B' + C') = (A + C) (B + C)
A B C F
0 0 0 0 • A Boolean function may have many possible logical expressions. They produce
0 0 1 1
0 1 0 0 the same result given the same inputs.
0 1 1 1 • Since the maxterms present in the 2nd canonical form are in one-to-one
1 0 0 0
1 0 1 1 correspondence with the 0’s of the truth table, the 2nd canonical (standard)
1 1 0 1 form expression for a function is unique.
1 1 1 1
• A function can have only one expression in the 2nd canonical form.

http://akademi.itu.edu.tr/en/buzluca/ 2.37 http://akademi.itu.edu.tr/en/buzluca/ 2.38

http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits Digital Circuits

Indexing maxterms: Conversions Between Canonical Forms

We assign each maxterm an index (number) based on the binary encoding of the
 From 1st (sum of minterms) form to 2nd (product to maxterms) form:
variables. This is a decimal number that represents the row number (Row numbers
start at 0). Replace the minterms with maxterms, and assign them numbers of minterms
that don’t appear in the 1st canonical form.
For example, we assign the index 5 to the maxterm a'+b+c' (101) and designate it M5.
Example: F(A,B,C) = Σm(1,3,5,6,7) = ΠM(0,2,4)
Inputs:
A B C Maxterms
F(A,B,C) = m1 + m3 + m5 + m6 + m7 = M0 ⋅ M2 ⋅ M4
0 0 0 A+B+C M0 &, ', ( &̅' ( &̅'( &' ( &'(̅ &'( & ' ( & ' ( &̅ ' (
0 0 1 A+B+C' M1  From 2nd (product to maxterms) form to 1st (sum of minterms) form:
0 1 0 A+B'+C M2
Replace the maxterms with minterms, and assign them numbers of maxterms
0 1 1 A+B'+C' M3
that don’t appear in the 2nd canonical form.
1 0 0 A'+B+C M4
1 0 1 A'+B+C' M5 Example: F(A,B,C) = ΠM(0,2,4) = Σm(1,3,5,6,7)
1 1 0 A'+B'+C M6 Example:
2nd canonical form of F:  Finding the complement of the function in sum of minterms form:
1 1 1 A'+B'+C' M7
F(A, B, C) = ΠM(0,2,4) Select the minterms that don’t appear in the 1st canonical form.
= M0 • M2 • M4 Example: F(A,B,C) = Σm(1,3,5,6,7) F'(A,B,C) = Σm(0,2,4)
Maxterms for 3 variables = (A + B + C) (A + B' + C) (A' + B + C)
 Finding the complement of the function in product of maxterms form:
F = ΠA,B,C(0,2,4) product of maxterms. Select the maxterms that do not appear in the 2nd canonical form.
Example: F(A,B,C) = ΠM(0,2,4) F'(A,B,C) = ΠM(1,3,5,6,7)
http://akademi.itu.edu.tr/en/buzluca/ 2.39 http://akademi.itu.edu.tr/en/buzluca/ 2.40
http://www.buzluca.info 2011-2019 Feza BUZLUCA http://www.buzluca.info 2011-2019 Feza BUZLUCA

Digital Circuits

Canonical Forms and the De Morgan's Theorem

• Applying the De Morgan's theorem to the complement of the function in the
1st canonical form generates the expression in the 2nd canonical form.
Example:
Complement of the function in SOP form (Slide 2.32):
&̅'(̅ &̅'(̅ &'(̅
De Morgan
&̅'(̅ &̅'(̅ &'(̅
& ' ( & ' ( &̅ ' ( 2nd canonical form is obtained (2.36).

• Applying the De Morgan's theorem to the complement of the function in the

2nd canonical form generates the expression in the 1st canonical form.
Example:
Complement of the function in POS form (2.37):
& ' (̅ & ' (̅ &̅ ' (̅ &̅ ' ( &̅ ' (̅
De Morgan
& ' (̅ & ' (̅ &̅ ' (̅ &̅ ' ( &̅ ' (̅
&̅'( &̅'( &'( &'(̅ &'( 1st canonical form is obtained (2.31).
http://akademi.itu.edu.tr/en/buzluca/ 2.41
http://www.buzluca.info 2011-2019 Feza BUZLUCA