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

$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.