Boolean function
Table of contents
 Introduction
 Truth table formation
 Truth table formation
 Sum of product expressions (SOP)
 Product of sum expressions (POS)
 Canonical expressions
 Conversion of canonical forms
 Conversion from minimal to canonical forms
 Example algebraic simplification
 Undefined input & don’tcares
 Try the interactive truth table generator
 Methods to simplify the boolean function
Introduction
Boolean Functions are comprised of two components i.e., Variables and Logic operations(AND, OR, NOT…etc). Any equation with the mixture of these two components forms a Boolean function. The value of variables may or may not be predefined. The shorthand notation for a boolean function is that it is represented with a capital F followed by parenthesis comprising of all variables of that equation separated by comma(‘,’). You can represent any boolean expression in form of a Truth Table. Follow up to know How? Consider the following example:
Example:
Shorthand notation representing the boolean expression
/
F(A,B) = A + B //This is a boolean function comprising of variables A and B
F(A, B, C) = A(B + C(A + B))
\
Boolean Expression
Truth table formation
Truth Table is formed by evaluating the Boolean expression for each and every truth value of a variable. Now truth values of a variable are either ‘true’ or ‘false’. The main point is to evaluate the value of Boolean expression for each and every combination of the Truth values of variables present. Suppose there is only one variable, it implies that it can hold either ‘true’ or ‘false’ but, when there are two variables then you can have a combination of {TT, TF, FT, FF}(T > True, F > False). Implies you need to evaluate the value of expression for each and every Truth value of a variable. The above implications bring us to a conclusion that there can be 2^(number of variables) number of combination for a single boolean expression. Follow up the examples below to learn how to map those values.
Example:
F(A,B) = A + B
Truth Table::
A  B  F(A,B) 
0  0  0 
0  1  1 
1  0  1 
1  1  1 
Here you have 4 combinations for 2 variables, try to grasp the next example where variables are 3 which
implies 8 combinations. Make a note of how Truth values of a variable are written under each column for
every variable.
Example:
F(A,B,C) = A + B.C
Truth table formation
A truth table shows a table having all the combinations of the inputs and their corresponding results.
The switching equation can also be converted into a Truth Table. For example Consider the switching equation: F(A,B,C) = A + BC.
A  B  C  F 

0  0  1  0 
0  1  0  0 
0  1  1  0 
0  1  1  1 
1  0  1  1 
1  1  0  1 
1  1  1  1 
1  1  1  1 
Sum of product expressions (SOP)
Let’s take a look at an more complex expression F(A, B, C, D) = AB'C + BD + CD + D
. Let’s generate the truth table:
F(AB’C+BD+CD+D)  A  B  C  D 

0  0  0  0  0 
1  0  0  0  1 
0  0  0  1  0 
1  0  0  1  1 
0  0  1  0  0 
1  0  1  0  1 
0  0  1  1  0 
1  0  1  1  1 
0  1  0  0  0 
1  1  0  0  1 
1  1  0  1  0 
1  1  0  1  1 
0  1  1  0  0 
1  1  1  0  1 
0  1  1  1  0 
1  1  1  1  1 
In this example an interesting observation is that, you are doing a sum of product evaluation, that is, AB'C + BD + CD + D
is a sum of products. The significance of sum of product is that when you are doing +
, you are in fact invoking the OR
operator.
Moreover, the OR
operator returns true
so long as any one of its arguements returns true
. Therefore, if any of the terms in the sum of product (SOP) expressions is true
, then you know that the final expression is true
for certain.
Product of sum expressions (POS)
Let’s take a look at another expression F(A, B, C, D) = (A + B + C + D')(A + B' + C' + D)(A' + B' + C + D')
. Let’s generate the truth table:
F(A,B,C,D)  A  B  C  D 

1  0  0  0  0 
0  0  0  0  1 
1  0  0  1  0 
1  0  0  1  1 
1  0  1  0  0 
1  0  1  0  1 
1  0  1  1  0 
1  0  1  1  1 
1  1  0  0  0 
0  1  0  0  1 
1  1  0  1  0 
1  1  0  1  1 
1  1  1  0  0 
1  1  1  0  1 
1  1  1  1  0 
1  1  1  1  1 
Judging by the algebraic expression, it is evident that the expression is a product of sums. Such an expression is called a Product of Sum expression or POS in short.
Here the sum terms are defined by using the OR operation and the product term is defined by using AND operation. When two or more sum terms are multiplied by a Boolean OR operation, the resultant output expression will be in the form of productofsums form or POS form.
The productofsums form is also called as Conjunctive Normal Form as the sum terms are ANDed together and Conjunction operation is logical AND. Productofsums form is also called as Standard POS.
Canonical expressions
Before understanding Canonical Expressions, let us understand Minterms and Maxterms first.
Minterms
A minterm is defined as the product term of n variables, in which each of the n variables will appear once either in its complemented or uncomplemented form. The min term is denoted as mi where i is in the range of 0 ≤ i < 2^{n}.
For a 2variable (x and y) Boolean function, the possible minterms are:
x’y’, x’y, xy’ and xy
.
For a 3variable (x, y and z) Boolean function, the possible minterms are:
x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’ and xyz.
1 – Minterms = minterms for which the function F = 1. 0 – Minterms = minterms for which the function F = 0. Any Boolean function can be expressed as the sum (OR) of its 1 min terms. The representation of the equation will be
F(list of variables) = Σ(list of 1min term indices)
Ex: F(x, y, z) = Σ(3, 5, 6, 7)
The inverse of the function can be expressed as a sum (OR) of its 0 min terms. The representation of the equation will be
F(list of variables) = Σ(list of 0min term indices)
Ex: F’(x, y, z) = Σ(0, 1, 2, 4)
Examples of canonical form of sum of products expressions (min term canonical form):

Z = XY + XZ′

F = XYZ′ + X′YZ + X′YZ′ + XY′Z + XYZ
In standard SOP form, the maximum possible product terms for n number of variables are given by 2^{n}. So, for 2 variable equations, the product terms are 2^{2} = 4. Similarly, for 3 variable equations, the product terms are 2^{3} = 8.
Maxterms
A max term is defined as the product of n variables, within the range of 0 ≤ i < 2^{n}. The max term is denoted as Mi. In max term, each variable is complemented, if its value is assigned to 1, and each variable is uncomplemented if its value is assigned to 0.
For a 2variable (x and y) Boolean function, the possible max terms are:
x + y, x + y’, x’ + y and x’ + y’
For a 3variable (x, y and z) Boolean function, the possible maxterms are:
x + y + z, x + y + z’, x + y’ + z, x + y’ + z’, x’ + y + z, x’ + y + z’, x’ + y’ + z and x’ + y’ + z’
1 – Max terms = max terms for which the function F = 1.
0 – max terms = max terms for which the function F = 0.
Any Boolean function can be expressed the product (AND) of its 0 – max terms. The representation of the equation will be
F(list of variables) = Π (list of 0max term indices)
Ex: F(x, y, z) = Π(0, 1, 2, 4)
The inverse of the function can be expressed as a product (AND) of its 1 – max terms. The representation of the equation will be
F(list of variables) = Π(list of 1max term indices)
Ex: F’(x, y, z) = Π(3, 5, 6, 7)
Examples of canonical form of product of sums expressions (max term canonical form):
1. Z = (X + Y).(X + Y′)
2. F = (X′ + Y + Z′).(X′ + Y + Z).(X′ + Y′ + Z′)
In standard POS form, the maximum possible sum terms for n number of variables are given by 2^{n}. So, for 2 variable equations, the sum terms are 2^{2} = 4. Similarly, for 3 variable equations, the sum terms are 2^{3} = 8.
Having understood minterms and maxterms, you are now in a position to understand canonical forms.
Any Boolean function that is expressed as a sum of minterms or as a product of maxterms is said to be in its canonical form.
When the SOP form of a Boolean expression is in canonical form, then each of its product term is called minterm. So, the canonical form of sum of products function is also known as minterm canonical form or Sumofminterms or standard canonical SOP form.
Similarly, when the POS form of a Boolean expression is in canonical form, then each of its sum term is called maxterm. So, the canonical form of product of sums function is also known as maxterm canonical form or Productof sum or standard canonical POS form.
Conversion of canonical forms
You can represent the one canonical formed equation in other canonical form i.e. you can represent the SOP form of equation in POS form and POS form equation in SOP form. To convert the canonical equations, you interchange the Σ and Π symbols after listing out the index numbers of the equations, which are excluded from the original form of equation.
The important thing to remember about Boolean functions is that, the SOP and POS forms are Duals to each other. There are 2 steps to follow to convert the canonical form of the equations. They are:

Interchanging the operational symbols, Σ and Π in the equation.

Use the De Morgan’s principle of Duality to the index numbers of the Boolean function or writing the indexes of the terms that are not presented in the given form of equation.
For Example:
The SOP function F(A, B, C) = ∑(0, 2, 3, 5, 7) = A’B’C’ + AB’C’ + AB’C + ABC’ + ABC
is written in POS form by

changing the operational sign to Π

writing the missing indexes of the terms, 001, 100 and 110. Now write the sum form for these noted terms.
001 = (A + B + C'), 100 = (A' + B + C), 110 = (A' + B’ + C)
Writing down the new equation in the form of POS form,
F(A, B, C) = Π(1, 4, 6) = (A + B + C') * (A' + B + C) * (A' + B’ + C’)
The POS function F(A, B, C) = Π(2, 3, 5) = (A + B' + C)(A + B' + C')(A' + B + C')
is written in SOP form by

changing the operational sign to Σ

writing the missing indexes of the terms, 000, 001, 100, 110, and 111. Now write the product form for these noted terms.
000 = A’B’C’, 001 = A’B’C, 100 = AB’C’, 110 = ABC’, 111 = ABC
Writing down the new equation in the form of SOP form,
F(A, B, C) = Σ(0, 1, 4, 6, 7) = (A’B'C’) + (A’B’C) + (AB’C’) + (ABC’) + (ABC)
Conversion from minimal to canonical forms
Minimal POS to canonical POS
You can include all the variables in each product term of the POS form equation, which doesn’t have all the variables by converting into standard POS form. The normal POS form function can be converted to standard POS form by using the Boolean algebraic law, (A * A’ = 0) and by following the below steps.

By adding each nonstandard sum term to the product of its missing variable and its complement, which results in 2 sum terms

Applying Boolean algebraic law, A + BC = (A + B) * (A + C)

By repeating the step 1, until all resulting sum terms contain all variables
By these three steps you can convert the POS function into standard POS function.
Example:
F = (A’ + B + C)*(B’ + C + D’) * (A + B’ + C’ + D)
In the first term, the variable D or D’ is missing, so add D*D’ = 1 to it. Then
(A’ + B + C + D*D’) = (A’ + B + C + D) * (A’ + B + C + D’)
Similarly, in the second term, the variable A or A’ is missing, so add A*A’ = 1 to it. Then
(B’ + C + D’ + A*A’) = (A + B’ + C + D’) * (A’ + B’ + C + D’)
The third term is already in the standard form, as it has all the variables. Now the standard POS form equation of the function is
F = (A’ + B + C + D) * (A’ + B + C + D’) * (A + B’ + C + D’) * (A’ + B’ + C + D’) * (A + B’ + C’ + D)
Minimal SOP to canonical SOP
You can include all the variables in each product term of the SOP form equation, which doesn’t have all the variables by converting into standard SOP form. The normal SOP form function can be converted to standard SOP form by using the Boolean algebraic law, (A + A’ = 1) and by following the below steps.

By multiplying each nonstandard product term with the sum of its missing variable and its complement, which results in 2 product terms

By repeating the step 1, until all resulting product terms contain all variables
By these two steps you can convert the SOP function into standard SOP function. In this process, for each missing variable in the function, the number of product terms will double.
Example:
Convert the non standard SOP function F = x y + x z + y z
Sol:
F = x y + x z + y z
= x y (z + z’) + x (y + y’) z + (x + x’) y z
= x y z + x y z’ + x y z + x y’ z + x y z + x’ y z
= x y z + x y z’ + x y’ z + x’ y z
The standard SOP form is F = x y z + x y z’ + x y’ z + x’ y z
Example algebraic simplification
Let’s simplify our expression from the previous truth table example. you can apply ordinary algebra tricks such as factoring. Remember that the +
operator invokes the OR
gate, and that true or x
always returns true
regardless of x
(as shown in our first truth table).
AB'C + BD + CD + D // Initial expression
AB'C + BD + D // Applying Absorption Law on CD + D, which reduces it to D
AB'C + D // Applying Absorption Law on BD + D, which reduces it to D
=> AB'C + D // Final expression
As an exercise to the reader, complete the truth table to show that they are logically equivalent.
Undefined input & don’tcares
The definition of a “don’tcare” is a combination of input values that is not known, and could be either 0
or 1
. For the purposes of variable simplification, we would choose the greedy approach of picking between {0
, 1
} such that the simplified expression has less terms.
Let’s consider the following truthtable:
A  B  F(A,B) 
0  0  1 
0  1  1 
1  0  ? 
1  1  1 
We observe that we have a don’tcare. Let’s observe the differences in cases for F(1,0)
:
Case 1: F(1, 0) = 0
=> F(AB) = A'B' + A'B + AB
Case 2: F(1, 0) = 1
=> F(AB) = A'B' + A'B + AB' + AB
Simplifying the cases...
F(AB) = A'B' + A'B + AB
= A'(B' + B) + AB
= A' + AB
F(AB) = A'B' + A'B + AB' + AB
= A'(B' + B) + A (B' + B)
= A' + A
= 1
You can clearly see, if you set F(1, 0) = 1
, you get a true value for any input. Therefore, for the purposes of variable simplification, you can simply let F(1, 0) = 1
thus implying F(A, B) = 1
.
Try the interactive truth table generator
Truth Table Generator
Enter your boolean logic expression in the following format
AND = AB
OR = A+B
NOT = A'
NAND = (AB)'
NOR = (A+B)'
Methods to simplify the boolean function
The following methods can be used to simplify the the Boolean function:
 The Karnaughmap or Kmap method.
 The NAND gate method.