← 2020 Paper 2

UPSC 2020 Maths Optional Paper 2 Q5c — Step-by-Step Solution

10 marks · Section B

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

Question

Let $g(w,x,y,z)=(w+x+y)(x+\bar y+z)(w+\bar y)$ be a Boolean function. Obtain the conjunctive normal form (CNF) for $g(w,x,y,z)$. Also express $g(w,x,y,z)$ as a product of maxterms.

Technique

Expand each incomplete sum to full maxterms via $A=(A+t)(A+\bar t)$; collect distinct maxterms; identify zero-rows for indices.

Solution

The function is already a product of sums (POS), but the sum terms are not full — each must contain all four variables $w,x,y,z$ to be a maxterm. The CNF (canonical POS) is obtained by inflating each factor to full maxterms.

Step 1 — Inflate each factor using $A=A+0=A+(t\,\bar t)$ and $A+BC=(A+B)(A+C)$

Factor 1: $(w+x+y)$ is missing $z$:

Factor 2: $(x+\bar y+z)$ is missing $w$:

Factor 3: $(w+\bar y)$ is missing $x$ and $z$. First add $x$:

then add $z$ to each:

Step 2 — Collect the distinct maxterms

Listing every distinct full sum term produced (using $w+x+\bar y+z$ only once even though it appears in factors 2 and 3):

Step 3 — CNF (canonical product of sums)

Step 4 — As a product of maxterms

A maxterm $M_i$ corresponds to the row $i$ (binary $wxyz$) where it evaluates to $0$; a variable appears uncomplemented if its bit is $0$ and complemented if its bit is $1$. The seven maxterms have indices:

Answer