UPSC 2023 Maths Optional Paper 2 Q7a-i — Step-by-Step Solution

7.5 marks · Section B

Boolean algebra · Numerical Analysis · asked 15× in 13 yrs · Read the full method →

Question

Find the conjunctive normal form (CNF) of the following Boolean function:

f(x,y,z,t)=x\cdot y\cdot z+\overline{x}\cdot y\cdot(t+\overline{z}).

Factor common literal $y$ ; build truth table of the reduced 3-variable function $g$ ; read off maxterms; simplify by consensus.

f=y\bigl[xz+\bar x(t+\bar z)\bigr]=y\bigl[xz+\bar x t+\bar x\bar z\bigr].

So $f=y\cdot g$ where $g(x,z,t)=xz+\bar x t+\bar x\bar z$ .

$g=1$ iff $xz=1$ or $\bar x t=1$ or $\bar x\bar z=1$ , i.e.

$x=1$ : $g=z$ (need $xz=1$ , which requires $z=1$ ; the other two minterms have $\bar x=0$ ).
$x=0$ : $g=1$ iff $t=1$ or $z=0$ , i.e. $g=t+\bar z$ .

Zeros at $(x,z,t)=(0,1,0),(1,0,0),(1,0,1)$ — three maxterms.

Recall the maxterm for a zero row complements the literal where the variable is $1$ (and keeps it where it’s $0$ ):

g=(x+\bar z+t)(\bar x+z+t)(\bar x+z+\bar t).

Simplify (consensus on the last two):

(\bar x+z+t)(\bar x+z+\bar t)=(\bar x+z)+t\bar t=\bar x+z.

Hence the minimal CNF of $g$ is

g=(\bar x+z)(x+\bar z+t).

\boxed{\;f=y\cdot(\bar x+z)\cdot(x+\bar z+t)\;\text{(minimal CNF, 3 clauses).}\;}