DHARM
N-COM\APPENDIX.PM5BOOLEAN ALGEBRA 361Similarly we can obtain,
f 2 (x, y, z) = x′yz + xy′z′ + xy′z + xyz′ + xyz
= m 3 + m 4 + m 5 + m 6 + m 7 ;
or, = Σ (3, 4, 5, 6, 7);
and (f 2 ′(x, y, z))′ = f 2 (x, y, z) = π (0, 1, 2);
Therefore we can say that, mk′ = Mk; that is, maxterm with subscript k is a complement
of the minterms with the same subscript k or conversely, minterms with subscript k is a
complement of the maxterms of same subscript k. Therefore, Boolean function can be converted
from one canonical form to other by simply interchanging the symbols Σ and Π and add the
missing numbers that was not in the original form. One thing must be insured before finding
of the missing terms that, sum of minterms and sum of maxterms should be 2n for an n variables
Boolean function.
Besides the canonical form representation of Boolean functions, there is another form to
express the Boolean functions called standard form, where each term may contain any number
of literals. Standard form is of two types:
- Sum of Product (SoP)
- Product of Sum (PoS)
SoP (PoS) is similar to sum of minterms (product of maxterms) except that in SoP (PoS)
each term of Boolean function may have any number of literals. For example,
f 1 (x, y, z) = x + y z + x′ y z SoP
f 2 (x, y, z) = (x + y) × z × (x + y′ + z) PoS
Any Boolean function expressed in SoP (PoS) where, product terms (sum terms) contains
less literals than minterms (maxterms) could be expressed in sum of minterms (product of
maxterms) by applying following procedure,
Inspect the Boolean function and see, if it is in SoP (PoS) form, and if each term contains
all the literals, then do nothing; Otherwise, missed one or more literals is/are ANDed (ORed)
with an expression such as x + x′ (x. x′) where x is one of the missing literal.
In the context of the statement calculus (discuss in next chapter 6) we may say that any
statement formula can be expressed in either of any form (SoP/PoS). Therefore, it is conven-
ient if we replace the word product by ‘conjunction’ and sum by ‘disjunction’. While, SoP is also
called disjunctive normal form (DNF) and PoS is also called as conjunctive normal form
(CNF). Alternately, the sum of minterms is called ‘principle disjunctive normal form’
(PDNF) and product of maxterms is called ‘principle conjunctive normal form’ (PCNF).
Example A.4 (i) Consider the Boolean function f 1 (x, y, z) = x + y z + x′ y z; which is in
standard form (SoP). Express f in a sum of minterms.
Sol. Since, function contains three variables x, y, and z and the first term is missing of vari-
ables y and z so ANDed (y + y′) and (z + z′) in the first term. Similarly, ANDed (x + x′) in the
second term and nothing ANDed in the third term. Thus, way obtain,
f 1 (x, y, z) = x (y + y′) (z + z′) + (x + x′) y z + x′ y z
= xyz + xy′z + xyz′ + xy′z′ + xyz + x′yz + x′yz
Simplifying and removing those minterms that appears more than once and rearrang-
ing the minterms thus we obtain,
f 1 (x, y, z) = x′yz + xy′z′ + xy′z + xyz′ + xyz
f 1 (x, y, z) = ΣΣΣΣΣ (3, 4, 5, 6, 7); PDNF