retagged by
487 views
2 votes
2 votes

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?

  1. Gate $1$ is a universal gate
  2. Gate $2$ is a universal gate
  3. Gate $3$ is a universal gate
  4. None of the gates shown is a universal gate
retagged by

1 Answer

1 votes
1 votes

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 

Answer: