Question

Suppose that f: B3 →B is defined by f (x, y, z) = (x + y) + (xz). a) Determine the d.n.f. and c.n.f. for f. b) Write f as a sum of min-terms and as a product of max-terms (utilizing binary labels).

Answer 1

First we need to set up the relevant truth table:

REF	x	y	z	x+y	xz	f=(x+y)+(xz)
a	0	0	0	0	0	0
b	0	0	1	0	0	0
c	0	1	0	1	0	1
d	0	1	1	1	0	1
e	1	0	0	1	0	1
f	1	0	1	1	1	1
g	1	1	0	1	0	1
h	1	1	1	1	1	1

Using REF, we can combine those that result in function f=1: c+d+e+f+g+h.

These correspond to DNF (disjunctive normal form):  x̄yz̄+x̄yz+xȳz̄+xȳz+xyz̄+xyz, which can also be expressed (+ is replaced by OR (∨) and literal multiplication by AND (∧)):

(¬x∧y∧¬z)∨(¬x∧y∧z)∨(x∧¬y∧¬z)∨(x∧¬y∧z)∨(x∧y∧¬z)∨(x∧y∧z). This DNF is also called sums of products (SOP), where the products are within parentheses and the sums join the parenthesised products.

Again, using REF, we combine those that result in f=0 (or ¬f=1): a+b, corresponding to DNF:

x̄ȳz̄+x̄ȳz, or (¬x∧¬y∧¬z)∨(¬x∧¬y∧z).

¬(¬f)=f=1, so we negate the literals and reverse the logic symbols: (x∨y∨z)∧(x∨y∨¬z)=(x+y+z)(x+y+z̄) to get the CNF (conjunctive normal form) or product of sums (POS). Here the sums are parenthesised and the the CNF is the product of these sums.