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

Thank you sir

---

@Deepak Poonia sir ,the best method I ever found ,thank you ...

---

Always use case method
Option B,C,D are correct

Answer 1

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

Taking complement of above expression;

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

Applying De-Morgan’s law;

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

$\overline{F}=(\bar X.\bar Y.\bar Z)+\overline{\overline{X}}.\overline Y+\overline{\overline{Y}}.\overline Z$

$\left [\because \overline{\overline{X}}=X, \text{Using double negation law}  \right ]$

$\therefore \overline F=(\bar X.\bar Y.\bar Z)+(X.\overline Y)+(Y.\overline Z)$ $\quad \quad \to \text{Option (D)}$

Taking $\overline Y$ as common we get;

$\overline F=\overline Y \left[ (\bar X \bar Z)+X\right]+Y\overline Z$

$\left [ \because A+BC=(A+B)(A+C) \text{ Applying distributive law here}\right ]$

$\overline F=\overline Y\left[(X+\overline X)(X+\overline Z)\right]+Y\overline Z$

$\overline F=\overline Y\left[X+\overline Z\right]+Y\overline Z$

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

Taking $\overline Z$ as common

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

$\because \text{(Y+$\overline Y$=1) using complement law}$

$\therefore \overline F=X\overline Y+\overline Z$$\quad \quad \to \text{Option (B)}$

Applying distributive law here we get;

$\overline F=(X+\overline Z)(\overline Y+\overline Z)$$\quad \quad \to \text{Option (C)}$

So, correct options are $B,C,D.$

---

Option A is false and can be proved as follows:

Take $X = 0, Y = 1, Z = 0$

Now, $F = 0,$ since $(\bar Y + Z)$ term will be zero. So, $\bar F$ must be $1.$

But option A gives $0$ as the term $X + \bar Y$ evaluates to $0.$ So, option A is not equal to $\bar F.$

Properties of Boolean Algebra

Comments

Actually Option D should contain

X' Y' Z'  and not (XYZ)' .

---

@Lakshman Patel RJIT sir kindly update option D, its not matching with arjun sir’s answer

$\overline{XYZ}$ should be $\overline{X}$.$\overline{Y}$.$\overline{Z}$

---

Done👍

Answer 2

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

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

$ \overline{F} = \overline{X}\overline{Y }\overline{Z}+X\overline{Y}+Y\overline{Z} $   ----- (D)

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

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

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

$ \overline{F} = \overline{Y }\overline{Z}+\overline{Y }X+Y\overline{Z} $    

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

$ \overline{F} =\overline{Y }X+ \overline{Z} $      ----- (B)

$ \overline{F} = (\overline{Y }+\overline{Z}) (X+ \overline{Z}) $     ----– (C)

 

Ans : B,C,D

Comments

why we are taking complement here

---

Read the question properly . It is asked in complement form thats why we are taking complement

---

after the statement ..  D .. instead of taking Y` as common if we take Z` as common we are not able to arrive at the answer.. is there any reasoning behind this can you explain if there is any think  wrong in my question..

---

You will get the same answer. Just combine first and third term  and apply AND and OR  properties result will be same

Answer 3

We can solve this question using k-map.

Since it is a MSQ so we can easily explore all possibilities using k-map and answer correctly.

 

So, correct options are B,C,D.

Answer 4

The simplest way to answer this question is finding the minterms and maxterms in $\bar{F}$ then comparing with each option,

if the given expression is equivalent then its maxterms/minterms as same as $\bar{F}$

 

Given F=$(X + Y + Z)(\bar{X} + Y)(\bar{Y} + Z)$

Lets try to convert this pos form into canonical pos form so that we can find maxterms of function F.

Canonical POS = $(X + Y + Z)(\bar{X} + Y + (Z.\bar{Z}))((X\bar{X}) + \bar{Y} + Z)$

                          =$(X + Y + Z)(\bar{X} + Y + Z)(\bar{X} + Y + \bar{Z})(X + \bar{Y} + Z)(\bar{X} + \bar{Y} + Z)$

We know that, when it comes it maxterms, uncomplemented variable(X) indicates value 0 , complemented variable indicates ($\bar{X} $) indicates value 1.

NOTE: – Minterms of F = Maxterms of $\bar{F}$     and maxterms of F = minterms of $\bar{F}$

So, Maxterms in F = $\prod (0 , 2, 4, 5, 6)$   ,  Minterms of F = $\sum (1, 3, 7)$

From the above note Maxterms of $\bar{F}$ = $\prod (1, 3, 7)$   , Minterms of $\bar{F}$  = $\sum (0 , 2, 4, 5, 6)$  

Now lets verify each option,

 

A)$(\bar{X} + \bar{Y} + \bar{Z})(X + \bar{Y})(Y + \bar{Z})$

So Canonical pos of this expresion is = $(\bar{X} + \bar{Y} + \bar{Z}) (X + \bar{Y} + (Z.\bar{Z})) ((X.\bar{X}) +Y + \bar{Z})$

                                                            =$(\bar{X} + \bar{Y} + \bar{Z}) (X + \bar{Y} + Z) (X + \bar{Y} + \bar{Z})(X+Y + \bar{Z}) (\bar{X} +Y + \bar{Z})$

                                                            =$\prod (7, 2, 3, 1, 5)$

As the maxterms of this expression is not same as $\bar{F}$ , both are not equivalent.

 

B)$X\bar{Y} + \bar{Z}$

Minterms of this Expression = $X\bar{Y}\bar{Z} + X\bar{Y}Z  + \bar{X}\bar{Y}\bar{Z}  + \bar{X}Y\bar{Z}+ X\bar{Y}\bar{Z} + XY\bar{Z} $

                                             =$\sum(0, 2 ,4 , 5, 6)$

which is same as $\bar{F}$, so these two exp are equivalent.

C) Just take $\bar{Z}$ common, then we will get  $X\bar{Y} + \bar{Z}$ which is option B so , These Two are also equivalent.

D)Just find out the minterms, the result is , minterms = $\sum(0, 2 ,4 , 5, 6)$, same as $\bar(F)$ so this is also equivalent.

 

Option B , C , D are correct.

Answer 5

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

Answer 6

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')