(i) Find the conjunctive normal form (CNF) of the following Boolean function : $$f(x,y,z,t) = x \cdot y \cdot z + \bar{x} \cdot y \cdot (t + \bar{z})$$ (ii) Express the Boolean function $$f(x,y,z) = x + \overline{(\bar{x} \cdot \bar{y} + \bar{x} \cdot z)} + z$$ in disjunctive normal form (DNF) and construct the truth table for the function.
Divyank Gupta, AIR 21, 2024
Sol$^n$) (i) $f(x,y,z,t) = xyz + \bar{x} \cdot y \cdot (t+\bar{z})$
$\Rightarrow f = xyz(t+\bar{t}) + \bar{x}yt(z+\bar{z}) + \bar{x}y\bar{z}(t+\bar{t})$ [$\because A+\bar{A}=1$]
$\Rightarrow f = xyzt + xyz\bar{t} + \bar{x}ytz + \bar{x}yt\bar{z} + \bar{x}yzt + \bar{x}y\bar{z}\bar{t}$
$\Rightarrow f = xyzt + xyz\bar{t} + \bar{x}ytz + \bar{x}yt\bar{z} + \bar{x}yz\bar{t}$ [?]
Now f is in DNF form.
So [?] CNF [?] form [?]
| zt \ xy | 00 | 01 | 11 | 10 | |---|---|---|---|---| | 00 | | 1 | | | | 01 | | 1 | | | | 11 | | 1 | 1 | | | 10 | | | 1 | |
Now $f = \sum m$ (1, 5, [?], 13, 15) [?]
So f in CNF form will be
$f = \prod M(0, 2,3,4,6,7,8,9,10, 12,14)$
ii) $f(x,y,z)=x+\overline{\bar{x}\cdot\bar{y}+\bar{x}\cdot z}+z$
$=x+\overline{\bar{x}\cdot\bar{y}}\cdot\overline{\bar{x}\cdot z}+z$
$=x+(x+y)(x+\bar{z})+z$
$=x+x+x\bar{z}+xy+y\bar{z}+z$
$=x+x\bar{z}+xy+y\bar{z}+z$
$=x(1+\bar{z})+xy+y\bar{z}+z$
$=x+xy+y\bar{z}+z$ [$\because A\cdot A=A$, $A+1=1$, $A\bar{A}=0$]
$=x(1+y)+y\bar{z}+z$
$\Rightarrow f(x,y,z)=x+y\bar{z}+z$ [using $\overline{A+B}=\bar{A}\cdot\bar{B}$, $A+1=A$]
Now $f=x+y\bar{z}+z$ can be written as
$\Rightarrow f=x(y+\bar{y})(z+\bar{z})+(x+\bar{x})y\bar{z}+(x+\bar{x})(y+\bar{y})z$
$\Rightarrow f=x[yz+y\bar{z}+\bar{y}z+\bar{y}\bar{z}]+xy\bar{z}+\bar{x}y\bar{z}+(xy+x\bar{y}+[?]+\bar{x}\cdot\bar{y})z$
$\Rightarrow f=xyz+xy\bar{z}+x\bar{y}z+x\bar{y}\bar{z}+xy\bar{z}+\bar{x}y\bar{z}+xyz+x\bar{y}z+\bar{x}\bar{y}z+[?]$
$\Rightarrow f=xyz+xy\bar{z}+x\bar{y}z+x\bar{y}\bar{z}+\bar{x}y\bar{z}+\bar{x}\bar{y}z$ Ans
Now $f = x + z + y\bar{z}$
| x | y | z | $y\bar{z}$ | f | |---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 1 | | 1 | 0 | 0 | 0 | 1 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 0 | 1 | 1 | | 1 | 1 | 1 | 0 | 1 |