GATE CSE 2021 Set 2 | Question: 52

Question

Consider a Boolean function $f(w,x,y,z)$ such that $$\begin{array}{lll} f(w,0,0,z) & = & 1 \\ f(1,x,1,z) & =& x+z \\  f(w,1,y,z) & = & wz +y \end{array}$$The number of literals in the minimal sum-of-products expression of $f$ is _________

Comments

output is 6

---

BOOLEAN function is the key to solve this question.

Answer 1

We can see $3$ squares, so number of literals $=3\times2 = 6.$

Comments

People confused in Boolean function thinking we know Boolean function can be present in sop --->1. And pos --->0  here function-1 is present in sop because f()=1 make possibility in w,z  x=y=0. fixed but twist in second function x+z should be 1 but you will make possiblity for x & z --- 10, 01 ,11 00 Here 00 will make x+z=0 that will be not in sop so ignore 00 combination of xz were wy is fixed as 1 same thin do for f3 =wx+y were if y=1 then wx can be combination of either 0 or 1 and part two break for wx if wx is 11 then y=0/1  then only f3. =1 and come in sop   make k-map for all these possiblity carefully you will get k-map same as in upper figure which choosen best answer by GOF.   Group k map you will get 3 terms 6 literals.   Thanks for reading my answer please  wear mask and all the best 🙏🙏🙏🙏

---

 

      TRUTH TABLE for f:-

w	x	y	z	f
0	0	0	0	1
0	0	0	1	1
0	0	1	0	X
0	0	1	1	X
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

 

*X is don’t care.

---

Yes it should be don't care. But had those terms been don't care, even in that case we would have got 3 squares only as same as that of the above kmap.

Answer 2

To Understand the question :

Over boolean variables $w,x,y,z,$ we have been given the definition of a Boolean function $f.$

Over $4 $ boolean variables, we have $2^4 = 16$ different combinations (rows in truth table of $f$), and the value of function $f$ is given using three equations.

From equation $1,$ $i.e. f(w,0,0,z) = 1$ , We can find the value of  function $f$ to be $1$ for the combinations/rows in which $x=y=0.$

So,  $f(0,0,0,0) = 1 ;$ $f(0,0,0,1) = 1 ;$ $f(1,0,0,0) = 1 ;$ $f(1,0,0,1) = 1 ;$

From equation $2,$ $i.e. f(1,x,1,,z) = x+z$ , We can find the value of  function $f$ to be $x+z$ for the combinations/rows in which $w=y=1.$

So,  $f(1,0,1,0) = 0+0 = 0 ;$ $f(1,0,1,1) = 0+1 = 1;$ $f(1,1,1,0) = 1+0 = 1;$ $f(1,1,1,1) = 1+1 = 1;$

From equation $3,$ $i.e. f(w,1,y,z) = wz+y$ , We can find the value of  function $f$ to be $wz+y$ for the combinations/rows in which $x=1.$

So,  $f(0,1,1,0) = 0.0+1 = 1 ;$ and so on.

NOTE that from the given definition of function $f,$ we cannot find the value of function $f$ for the two combinations $0011,0010.$ Hence, we consider $(0011) , (0010) $ as “Don’t Cares Combinations” for which the value of function $f$ is “Don’t Care”.

Once understood the question, make K-map, and do minimization.

Comments

Thanks for this explanation @Deepak Poonia

---

@Deepak Poonia Sir from the three equations given in question we will not get value of f(0,0,1,0) and f(0,0,1,1) . So there are to be considered don’t cares . Am I correct @Deepak Poonia Sir ?? 

Although the final answer will still remain the same . 

---

@abir_banerjee, Yes, It will be Don’t Care. I have now mentioned it in my answer above. 

Answer 3

let’s convert these equations into miniterms 

Equation 1 | x’y’

Equation 2 | wy(x+z)

Equation 3 | x(wz+y)

Adding all three together we have x’y’+wxy+wyz+wxz+xy. 2nd term is redundant because of the last term.

by removing and reordering we have xy+x’y’+wz(x+y)

 Now, if both x and y are false function equates true, if both false again true, only case remaining is either one of them is true in that case output is dependent on wz

so the final miniterms are xy+x’y’+wz – In total we have 6 literals