Boolean Expressions

• Boolean expressions are the method using which we save the information about the
Boolean function, that when we get value 1 and when we get value 0 as output. So, we
convert the truth table of the function into an expression, reading which we can
understand where the output is 1 and when it is zero.
• There are two popular approaches for writing these expressions.
o Sum of Product (SOP) (which remember when we get 1)
o Product of Sum (POS) (which remember when we get 0)
• Make a note of this as we are studying Boolean function remembering both 0 and 1 is
not required, so we can either concentrate on 0 or 1.
• Power of SOP and POS bother are same, i.e. any Boolean functions can be represented
using both SOP and POS.
• Mathematically speaking we should choose (0 or 1), whatever is less in number because
then it will be easy to represent.

Q The truth table represents the Boolean function (GATE-2012) (1 Marks)

X Y F (X, Y)
0 0 0
0 1 0
1 0 1
1 1 1
(A) X (B) X+Y (C) X ⊕ Y (D) Y
Answer: (A)
 SOP (sum of product)
• A sum of product form expression contains product terms (AND terms) which are sum
(OR) together, that’s why called sum of product.
• Each product terms (AND terms) consists of one or more literals (variables) appearing
either in complements or uncomplemented form. E.g. a’b + b’c’ + ac
• A product term which contains all the literals (variables) either in complemented or
uncomplemented form is called minterm. In a n variable function, there will be 2n
minterms.

Binary Sequence Minterm Designation

Representation
000 0 a’b’c’ m0
001 1 a’b’c m1
010 2 a’bc’ m2
011 3 a’bc m3
100 4 ab’c’ m4
101 5 ab’c m5
110 6 abc’ m6
111 7 Abc m7
• The result of a product term must always be 1, If a literal is having value 1 then it is ok,
but if not, then we complement those which is 0, it to make it 1.
• There is only 1 input sequence of variables for any minterm on which the output is 1, so
it represents information.
• Then the sum of all product term(minterm) to from a function, and functions will have
value 1, if at least of the product term(minterm) is 1.

Q Consider a function and find no of minterms F (a, b, c) = a + a’b + abc + bc’?

 Canonical logic forms
• Either in POS or SOP form it is not essential that all product or sum terms contains all the
literals.
• Canonical SOP form: - In a sum of product form expression, if each AND term (product
term) consists all the literals(variables) appearing either in complements or
uncomplemented form. E.g. a’bc + ab’c’ + abc. Then the form is said to be canonical SOP.

Q The minterm expansion of f(P, Q, R) = PQ + QR’ + PR’ is (GATE-2010) (2 Marks)

(A) m2 + m4 + m6 + m7 (B) m0 + m1 + m3 + m5
(C) m0 + m1 + m6 + m7 (D) m2 + m3 + m4 + m5
Answer: (A)
 POS (Product of Sum)
• A product of sum (POS) form of expression contains OR (sum) terms which are AND
(product) together, that’s why called product of sum expression.
• Each OR term (sum term) consists of one or more literals(variables) appearing either in
complemented or uncomplemented form. (a’ + b). (b’ + c’). (a + c)
• A OR (sum) term which contains all the literals(variables) either in complemented or
uncomplemented form is called maxterm. In a n variable function, there will be 2n
maxterms.

Binary Sequence Maxterm Designation

Representation
000 0 a+b+c M0
001 1 a + b + c’ M1
010 2 a + b’ + c M2
011 3 a + b’ + c’ M3
100 4 a’ + b + c M4
101 5 a’ + b + c’ M5
110 6 a’ + b’ + c M6
111 7 a’ + b’ + c’ M7

• The result of the OR (sum) term must be 0, so If a variable is having value 0 then it is ok,
but if not then we complement the variable it to make it 0.
• There is only 1 input sequence for which the output of a Maxterm is 0. Because, it
requires all values as zero.
• Then the product of all sum term (maxterm), from a function, and functions will have a
value 0, if any of the sum term(maxterm) is 0.
 Canonical logic forms
• Canonical POS form: - In a product of sum form expression, if each OR term (sum
term) consists all the literals(variables) appearing either in complements or
uncomplemented form. E.g. (a’ + b + c). (a + b’ + c’). (a + b + c). Then the form is said
to be Canonical POS form.

Q Given the function F = P′+QR, where F is a function in three Boolean variables P, Q and R
and P′ =! P, consider the following statements. (GATE-2015) (2 Marks)
S1: F = Σ (4, 5, 6)
S2: F = Σ (0, 1, 2, 3, 7)
S3: F = Π (4, 5, 6)
S4: F = Π (0, 1, 2, 3, 7)
Which of the following is true?
(A) S1-False, S2-True, S3-True, S4-False (B) S1-True, S2-False, S3-False, S4-True
(C) S1-False, S2-False, S3-True, S4-True (D) S1-True, S2-True, S3-False, S4-False
Answer: (A)
 No of functions possible
Q With n-Boolean variables how many different Boolean functions are possible?
Solution: with n binary variable we can generate 2n combinations. And as we know that a
Boolean function can also have only 2 possible values either 0 or 1, so total number of
different functions possible will be 2^(2n).

Similarly, we can generalize this idea as x^(yz) are the total number of functions possible, x
is the nature of the function, y is the nature of the variable and z is the number of variables.

Q What is the maximum number of different Boolean functions involving n Boolean

variables? (GATE-2007) (1 Marks)
a) n2 b) 2n c) 22^n d) 2n^2
Answer: - (C)

Q How many different Boolean functions of degree 4 are there? (NET-JUNE-2013)

(A) 24 (B) 28 (C) 212 (D) 216
Ans: d
 Complementation
• Let us consider a function f(a, b, c, d,……, 0, 1, +, . ), then the complement of the function
is defined as f’(a’, b’, c’,……, z’, 1, 0, +, .). i.e. When all the variables are replaced by their
compliments, 0→1,1→0, or →and, and→or, then we will be called them compliment of
a function.

OR NOR
AND NAND
EX-OR EX-NOR

• We can directly put a bar of the entire Boolean expression to find complement of the
function.
• We can also directly deal in minterms and maxterm to write complement function.
 Duality
• Let us consider a function f(a, b, c, d,……,z,0,1,+,. ), then the dual of the function is
defined as fd(a, b, c,……,z,0,1,..,+).
• When the nature of variable remains same but 0 → 1, 1 → 0, or → and, and → or, then
they are called dual functions.
• When we take dual of a function, then the functionality of a function remains the same
but a positive logic system is transformed to negative logic system.
• If a function works corrects in positive logic system, then it must also work correct in
negative logic system as it do not depends on magnitude.

OR AND
NOR NAND
EX-OR EX-NOR

a b a + b a. b a.b a + b
L0H L0H L0H L0H
L0 H H1L H1L L0H
H1L L0H H1L L0H
H1 L H1L H1L H1L

Q The dual of a Boolean expression is obtained by interchanging (NET-DEC-2013)

(A) Boolean sums and Boolean products
(B) Boolean sums and Boolean products or interchanging 0’s and 1’s
(C) Boolean sums and Boolean products and interchanging 0’s & 1’s
(D) Interchanging 0’s and 1’s
Ans: c

Q The dual of the switching function x + yz is: (NET-DEC-2007) (NET-DEC-2008)

(A) x + yz (B) x’ + y’z’ (C) x (y + z) (D) x’ (y’ + z’)
Ans: c
 Neutral Function
• A function f is said to be neutral if, it has equal number of minterms and maxterms.
• If there is a function f of n-variables, then (2n) C (2n-1) different neutral functions are
possible.
• If a function is self-dual or orthogonal, then it must be neutral, a function can never
be both orthogonal and self-dual because it will imply the function is same to its
compliment, which is never possible.
 Self-Dual
A function f is said to be self-dual if both the functions and its dual are same. f = fD
F (a, b, c) = ab + bc + ca

Q which of the following functions are self-dual?

Ans f (a, b, c) = ∑m (0, 3)

F (a, b, c) = ∑m (0, 1, 6, 7)
F (a, b, c) = ∑m (0, 1, 2, 4)
F (a, b, c) = ∑m (3, 5, 6, 7)

Q how to check weather a function is self-dual or not?

1) check whether function is neutral or not i.e. (minterm = maxterm)
2) A self-dual function does not have any mutually exclusive terms. So in every pair of
mutual exclusion term, we can pick only 1 minterm.
3) for n variable functions total 2n minterms are possible, so we will have 2n-1 pair of
mutually exclusive minterms, in every pair of mutually exclusive minterms we have two
choice so, For n variable function total number of 2^(2n-1) self-dual functions are possible.

0→7
1→6
2→5
3→4

e.g. of Mutual exclusive min terms

Q The dual of a Boolean function F (X1, X2, ..., Xn, +, *, '), written as FD, is the same
expression as that of F with + and * swapped. F is said to be self-dual if F = FD. The number
of self-dual functions with n Boolean variables is. (GATE-2014) (2 Marks)
a) 2n b) 2(n-1) c) 2(20142^n) d) 2(2^n-1)
Answer: - (D)

Q How many Boolean functions of degree n are self-dual? (NET-JUNE-2014)

(A) 2n (B) (2)2n (C) (2) n2 (D) (2) ^ (2 n–1)
Ans: d
 Orthogonal
A function f is said to be orthogonal if the compliment and dual of the function are same.
f’= fd
f(a, b, c) = a’b’c’ + abc + a’bc’ + ab’c

Q how to check weather a function is orthogonal or not?

1) check whether function is neutral or not i.e. (minterm = maxterm)
2) we can choose any pair of mutual exclusive terms, but the minterms and its complement,
both must be present.
3) If there is a function f of n-variables, then (2n-1)C(2n-2) different orthogonal functions are
possible.