DHARM
N-COM\APPENDIX.PM5
358 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
- f = (x + y)′′′′′. (x′ + y′)′
Simplification of such Boolean function can be easily done by using involution law (T3)
which states that the complement of the complement is effectless i.e., if we take complement of
complement of Boolean function f then we have,
(f ′)′ = f
Thus f ′ = ((x + y)′. (x′ + y′)′)′
= ((x + y)′)′ + ((x′ + y′)′)′ T5 (De Morgan’s)
= (x + y) + (x′ + y′) T3 (Involution)
= (x + x′) + (y + y′) T4 (Associativity)
= 1 + 1 P2
so f ′ = 1 T2
Further, if we take the complement of f ′ i.e.,
(f ′)′ = (1)′ = 0; then f = 0.
The complement of Boolean function can be obtained through straight forward way by
interchanging the values 0’s for 1’s and 1’s for 0’s.
De Morgan’s law (T5) using two binary variables x and y states that, (x + y)′ = x′. y′ and
also (x. y)′ = x′ + y′ that can be generalized for any number of binary variables i.e.,
(x 1 + x 2 + x 3 + ............ + xk)′ = x 1 ′. x 2 ′. x 3 ′ ........................... xk′
and, (x 1. x 2. x 3. ..................... xk)′ = x 1 ′ + x 2 ′ + x 3 ′ + ...... + xk′
The generalized form of De Morgan’s law states that complement of an expression will
interchange the binary operators ‘+’ into ‘. ’ and vise versa and complement each literal.
Example A.2. Find the complement and simplify the following Boolean functions.
- f = p q′ + r′ s′
Then complement of f is obtain as,
f ′ = (p q′ + r′ s′)′ = (p q′)′. (r′ s′)′ T5 (De Morgan’s)
= (p′ + q). (r + s) T5 & T3
- f = (q r′ + p′ s). (p q′ + r s′)
Then complement of f is given as,
f ′ = [(q r′ + p′ s). (p q′ + r s′)]′
= (q r′ + p′ s)′ + (p q′ + r s′)′ T5
= X + Y
where, we assume, (q r′ + p′ s)′ = X and (p q′ + r s′)′ = Y and solve separately,
So we have,
X = (q r′ + p′ s)′ = (q r′)′. (p′ s)′ T5
= (q′ + r). (p + s′) T5 & T3
= (q′ + r). p + (q′ + r). s′ P4
= q′ p + r p + q′ s′ + r s′
Similarly,
Y = (p q′ + r s′)′ = (p q′)′. (r s′)′ T5
= (p′ + q). (r′ + s) T5 & T3
= (p′ + q). r′ + (p′ + q). s P4
= p′ r′ + q r′ + p′ s + q s
