Mathematical Foundation of Computer Science

(Chris Devlin) #1
DHARM
N-COM\APPENDIX.PM5

BOOLEAN ALGEBRA 375

To obtain X 1 and X 2 in PoS, combing 0’s so we get the complement of the function that
are expressed in sum of minterms as,
X 1 ′ = (x y′ + y z′ + x′ z)
and X 2 ′ = (x′ y′ + z′)
Applying DeMorgan and involution theorem we get the simplified expressions,
(X 1 ′)′ = (x y′ + y z′ + x′ z)′
X 1 = (x′ + y) (y′ + z) (x + z′); (SoP)
Similarly, (X 2 ′)′ = (x′ y′ + z′)′
X 2 = (x + y) z; (SoP)
Example A.12 Simplify the Boolean expression
f(x, y, z) = Σ (0, 2, 4, 5, 6)
Sol. The K-map of function f is shown in Fig. A.25.


yz′′

yz′′

x′

x

yz′

yz′

yzyz′

yz′

x

yz

11

11

1

Fig. A.25
Since, y′z′ and yz′ are adjacent to each other so their simplification yields z′.
So, f(x, y, z) = z′ + xy′.

EXERCISES


A.1 Obtain the truth table of the following expressions:
(i)xy + xy′ (ii)xy + xy′ + y′z
(iii)xy + x′y′ + y′z (iv)(x′ + y + z′) (y′ + z) x′
(v)w′ + y(x′ + z′)(vi)x′y′z + x′yz′ + xyz′
(vii)xy′ + [(x′ + z) y]
Also show its K-map representation.
A.2 Express the following functions into PDNF and PCNF:
(i)F(x, y, z) = (xy + z) (y + xz)(ii)F(x, y, z) = xy + yz′
(iii)F(p, q, r) = (p′ + q) (q′ + r)(iv)F(w, x, y, z) = y′z + wxy′ + wxz′ + w′x′z
A.3 Expand the following functions into their canonical SoP forms (DNF):
(i)f(x, y, z) = xy + yz′ (ii)f(A, B, C, D) = BC + CA′D
(iii)f(A, B, C, D) = A + C′D + B′C(iv)f(A, B, C, D) = 1.
A.4 Using K-map representation find the minimal DNF expression for each of the following func-
tions:
(i)f(x, y, z) = Σ (0, 1, 4, 6) (ii)f(x, y, z) = Σ (1, 3, 7)
(iii)f(x, y, z) = Σ (0, 2, 3, 7) (iv)f(w, x, y, z) = Σ (0, 1, 2, 3, 13, 15)
(v)f(w, x, y, z) = Σ (0, 2, 6, 7, 8, 9, 13, 15).
Free download pdf