Boolean Functions
Digital Design. M. Morris Mano
Prof. Imane Aly Saroit Ismail 1 Logic Design
Boolean Functions
• A Boolean Function is described by an algebraic expression
that consists of binary variables, the constants 0 and 1 and
the logic operation symbols.
• For a given value of binary variables, the function can be
equal to either 1 or 0.
• Example:
F is a boolean function that depends on three variables
inputs A,B and C. A,B,C and F can only take 0 or 1.
Prof. Imane Aly Saroit Ismail 2 Logic Design
Truth table
• A truth is a presentation of a boolean function.
• For n input variables the number of rows = 2n
• The binary combinations for the truth table are obtained
from the binary numbers by counting from 0 to 2n-1
Prof. Imane Aly Saroit Ismail 3 Logic Design
Truth table
• Example:
Decimal
Value A B C BC F
0 0 0 0 1 0 0 0
1 0 0 1 1 0 0 1
2 0 1 0 0 0 0 0
3 0 1 1 0 0 1 1
4 1 0 0 1 1 0 1
5 1 0 1 1 1 0 1
6 1 1 0 0 0 0 0
7 1 1 1 0 0 1 1
Prof. Imane Aly Saroit Ismail 4 Logic Design
Logic Circuit
• A logic circuit is defined as a collection of coincidence and
mixing gates.
• Voltage‐operated logic circuits respond to two separate voltage
levels that represent a binary variable equal to logic 1 or logic 0.
• A digital logic circuit is defined as the one in which voltages
are assumed to have a finite number of distinct value. Types of
digital logic circuits are combinational logic circuits and
sequential logic circuits.
Prof. Imane Aly Saroit Ismail 5 Logic Design
Logic circuit
• Example:
Prof. Imane Aly Saroit Ismail 6 Logic Design
Minterms and Maxterms
Minterms
• A minterm is a product (AND) of all variables in the
function, in direct or complemented form.
• A minterm has the property that it is equal to 1 on exactly one
row of the truth table, i.e. it gives a true value (i.e., 1) for just
one combination of the input variables.
• Minterms are called products because they are the logical
AND of a set of variables.
Prof. Imane Aly Saroit Ismail 7 Logic Design
Minterms and Maxterms
Minterms
• A minterm is assigned an index (mi) based on a conventional
binary encoding of the complementation pattern of the
variables (where the variables in all the minterms are written
in the same order, usually alphabetical). This convention
assigns the value 1 to the direct form and 0 to the
complemented form.
Prof. Imane Aly Saroit Ismail 8 Logic Design
Minterms and Maxterms
Minterms (Example)
Decimal
Example: Value A B C F
0 0 0 0 0
1 0 0 1 1 m1
2 0 1 0 0
Minterms are 3 0 1 1 1 m3
4 1 0 0 1 m4
m 1 , m 3 , m 4 , m 5, m 7 1 0 1 1
5 m5
6 1 1 0 0
7 1 1 1 1 m7
001, 011, 100, 101, 111
Prof. Imane Aly Saroit Ismail 9 Logic Design
Minterms and Maxterms
Maxterms
• A maxterm is a sum (OR) of all variables in the function, in
direct or complemented form.
• A maxterm has the property that it is equal to 0 on exactly
one row of the truth table, i.e. it gives a false value (i.e., 0) for
just one combination of the input variables.
• Maxterms are called sums because they are the logical OR of
a set of variables.
Prof. Imane Aly Saroit Ismail 10 Logic Design
Minterms and Maxterms
Maxterms
• A maxterm is assigned an index (Mi) based on a
conventional binary encoding of the complementation
pattern of the variables (where the variables in all the
maxterms are written in the same order, usually
alphabetical). The maxterm convention assigns the value 0
to the direct form and 1 to the complemented form.
Prof. Imane Aly Saroit Ismail 11 Logic Design
Minterms and Maxterms
Maxterms (Example)
Decimal
Example: Value A B C F
0 0 0 0 0 M0
1 0 0 1 1
2 0 1 0 0 M2
Maxterms are 3 0 1 1 1
M0, M 2 , M 6 4 1 0 0 1
5 1 0 1 1
6 1 1 0 0 M6
7 1 1 1 1
000, 010, 110
Prof. Imane Aly Saroit Ismail 12 Logic Design
Minterms and Maxterms
Prof. Imane Aly Saroit Ismail 13 Logic Design
Example
Decimal
Example: Value X Y Z F
F = x + y'Z 0 0 0 0
1 0 0 1
Minterms are 2 0 1 0
……. 3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
Prof. Imane Aly Saroit Ismail 14 Logic Design
Example
Decimal
Example: Value X Y Z F
F = x + y'Z 0 0 0 0
1 0 0 1
Maxterms are 2 0 1 0
……. 3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
Prof. Imane Aly Saroit Ismail 15 Logic Design
Canonical Forms
Two dual canonical forms of any Boolean function are used:
• The term "Sum of Products" or "SoP" is used for the
canonical form that is a disjunction (OR) of minterms (sum
of minterms).
• The term "Product of Sums" or "PoS" is used for the
canonical form that is a conjunction (AND) of maxterms
(product of maxterms).
Prof. Imane Aly Saroit Ismail 16 Logic Design
Canonical Forms
SoP (Example)
Example:
F(A,B,C)= m1+m3+m4+m5+m7
F(A,B,C)=∑m(1,3,4,5,7)
Prof. Imane Aly Saroit Ismail 17 Logic Design
Canonical Forms
PoS (Example)
Example:
F(A,B,C)= M0M2M6
F(A,B,C)=ΠM(0,2,6)
Prof. Imane Aly Saroit Ismail 18 Logic Design
Boolean Functions Representation
• Boolean function.
• Truth table.
• Logic circuit.
• Sum of minterms.
• Product of maxterms.
• Sum of Products.
• Product of Sum.
Prof. Imane Aly Saroit Ismail 19 Logic Design
