Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

BOOLEAN ALGEBRA 359

Then, f ′ = X + Y = q′ p + r p + q′ s′ + r s′ + p′ r′ + q r′ + p′ s + q s

= 1 (reader may solve the remaining part of

the expression to verify the result).

3. f = [(p q′) p] × [(p q)′ q]
   Then complement of f will be obtain as,
   f ′ = {[(p q′) p]. [(p q)′ q]}′
   = [(p q′) p]′ + [(p q)′ q]′ T5
   = [(p q′)′ + p′] + [(p q) + q′] T5 & T3
   = [p′ + q + p′] + [p q + q′] T5 & T3
   = [p′ + q] + [p q + q′] T1
   = [p′ + p q] + [q + q′] T4
   = [p′ + p q] + 1 P2
   = [p′ + p q] + 1 P2
   = 1 T2
   Hence, f ′ = 1.

A.6 Forms of Boolean Functions...........................................................................................

A Boolean function can be expressed in any of the two forms, (1) Canonical form, or (2) Standard
form. The class of canonical form further slices into (1.1) sum of minterms, or (1.2) product of
maxterms. In the sum of minterms form, by ‘sum’ meant ORing of minterms, where each
minterm is obtained from an AND term of the n variables that are either prime (true) or
unprimed (false). Similarly, in the product of maxterms form, by ‘product’ meant ANDing of
maxterms, where each maxterm is obtained from an OR term of n variables that are being
prime or unprimed.
So in general, n variables can be combined to form 2n minterms and 2n maxterms. The
2 n different minterms and maxterms can be determined by the method similar to one shown
in Fig. A.6 for three variables that has 8 (= 2^3 ) minterms and 8 (= 2^3 ) maxterms.
x y z Minterms Maxterms
Term Symbol Term Symbol
000 m 0 x′. y′. z′ M 0 x + y + z
001 m 1 x′. y′. z M 1 x + y + z′
010 m 2 x′. y. z′ M 0 x + y′ + z
011 m 3 x′. y. z M 0 x + y′ + z′
100 m 4 x. y′. z′ M 0 x′ + y + z
101 m 5 x. y′. z M 0 x′ + y + z′
110 m 6 x. y. z′ M 0 x′ + y′ + z
111 m 7 x. y. z M 0 x′ + y′ + z′
Fig. A.6