GATE ECE 2015 Set 3 | Question: 37

Question

A universal logic gate can implement any Boolean function by connecting sufficient number of them appropriately. Three gates are shown.

Which one of the following statements is TRUE?

• A. Gate $1$ is a universal gate
• B. Gate $2$ is a universal gate
• C. Gate $3$ is a universal gate
• D. None of the gates shown is a universal gate

Answer 1

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , With best way to check functional completeness:}}$

https://youtu.be/MJgwNj8y3tw?t=1985&feature=shared

For Digital Circuits, we always assume that 0 and 1 are available as gate inputs. Explained HERE.

So, to check if Gate 3 is functionally complete Or not, we need to check $\{ F_3 = \overline{X} + Y, 0, 1 \}$ is functionally complete Or not. 

Now apply Post’s functional completeness theorem on the set $\{ F_3 = \overline{X} + Y, 0, 1 \}.$

Do the same for Gate 1 & Gate 2. i.e. apply Post’s functional completeness theorem on the sets $\{ F_1 = X + Y, 0, 1 \}$ and $\{ F_2 = XY, 0, 1 \}.$  

Functional Completeness Complete Playlist: Functional Completeness - Complete Playlist - Post's Theorem 

---

This question (Implication gate) has come in GATE 3 Times:

https://gateoverflow.in/1696/gate-cse-1998-question-5

https://ec.gateoverflow.in/762/gate-ece-2015-set-3-question-37

https://ec.gateoverflow.in/1665/gate-ece-2022-question-39