GATE CSE 2021 Set 1 | Question: 42

Question

Consider the following Boolean expression.

$F=(X+Y+Z)(\overline X +Y)(\overline Y +Z)$

Which of the following Boolean expressions is/are equivalent to $\overline F$ (complement of $F$)?

• A. $(\overline X +\overline Y +\overline Z)(X+\overline Y)(Y+\overline Z)$
• B. $X\overline Y + \overline Z$
• C. $(X+\overline Z)(\overline Y +\overline Z)$
• D. $X\overline Y +Y\overline Z + \overline X\; \overline Y \;\overline Z$

Comments

@Arjun Sir, Add Some spaces in option D, third term seems to be whole complement.

---

Fixed 👍

---

The BEST way to solve such questions with $3$ or more boolean variables, is “By Case” method.

Since $X$ is a boolean variables, only two cases are possible; $X = 0 $ OR $X = 1.$

Case 1: When $X = 0:$

When $X= 0,$ we get $\overline{F} = \overline{Z}  ;$

Now check each option by putting $X =0; $ So, option $A$ are eliminated. Options $B,C,D$ hold fine in this case. 

Case 2: When $X = 1:$

When $X= 1,$ we get $\overline{F} = \overline{Y} + \overline{Z}  ;$

Now check option $B,C,D$ by putting $X =1; $ Options $B,C,D$ hold fine in this case also.

So, $B,C,D$ are equivalent to $\overline{F}.$

Answer 1

The easiest way to find complement of a Boolean function   is first  find the  dual of that function (replace + with •  and 1 with 0) then interchange literals with their negations (i.e x with x')

f=(x+y+z).(x'+y).(y'+z)

Dual of f= (x.y.z)+(x'.y)+(y'.z)

f'=(x'.y'.z')+(x.y')+(y.z')

And using some Boolean laws u get 2,3 options also

Comments

This is the way to find complement not dual in dual we don't do the negation of a variable like ( A < -> A')

Answer 2

Following is another solution using k-map. 

Given F$\left (x,y,z \right )$ =  $\left ( x + y + z \right )\left (x’ + y\right )\left ( y’+z \right )$ in P.O.S form

Converting to S.O.P form we get

$\left (x’ y’ z’ \right )+ \left (x y’\right ) + \left ( yz' \right )$.

Now we can plot a k-map and put 0’s for the above S.O.P expression

X\YZ

0	1	1	0
0	0	1	0

 

To understand more about plotting max terms in a k-map, check https://www.allaboutcircuits.com/textbook/digital/chpt-8/minterm-maxterm-solution/

Now, we have marked the max terms in the k-map. 

Now, objective is to find F’

From the above k-map, F’ can be easily computed by grouping 0s instead of 1s. Grouping 0s give the complement of F in S.O.P form. Now, check the options

Option #B is evident from the map by grouping 0’s ( we get S.O.P form )

Option #C is same as option #B but expressed in P.O.S form

Option #D is also possible if we don't do a grouping of 4 0’s

For Option #A , look at the k-map for 1s. Given F can be expressed as a sum of minterms = $\sum$( m1, m3, m7 )

For complement of F, find the missing minterms out of the 2^3=8 minterms possible.We have $\sum$( m0, m2, m4,m5, m6)

F’ = $\sum$(m0,m2,m4,m5,m6)

Expressing this in P.O.S form , $\prod$(M1,M3,M7) which is $\left (x +y’ + z’  \right )\left ( x+ y’ + z’ \right )\left ( x’ + y’ + z’ \right )$ which is not equivalent to option #A. 

So,correct answers are options B, C, D