Register

GATE CSE 1999 | Question: 2.9

• edited by
24,163 views
48 48 votes

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

  1. XOR gates, NOT gates

  2. $2$ to $1$ multiplexers

  3. AND gates, XOR gates

  4. Three-input gates that output $(A.B) + C$ for the inputs $A, B$ and $C$.

5 Answers

Best answer
70 70 votes
1. XOR and NOT gates can only make XOR and XNOR which are not functionally complete- $a \oplus \bar a = 1, a \oplus a = 0.$

2. 2-1 multiplexer is functionally complete provided we have external 1 and 0 available. For NOT gate, use $x$ as select line and use 0 and 1 as inputs. For AND gate, use $y$ and 0 as inputs and $x$ as select. With {AND, NOT} any other gate can be made.

3. XOR can be used to make a NOT gate ($a \oplus 1 = \bar a$) and {AND, NOT} is functionally complete. Again this requires external 1.

4. We have $AB + C$. Using $C = 0$, we get an AND gate. Using $B = 1$ we get an OR gate. But we cannot derive a NOT gate here.

So, options B and C are true provided external 1 and 0 are available.
• selected by
14 14 votes
Functionally complete operation set is a set of Logic from which any arbitrary Boolean function can be realized .

Exp of Functionally complete set operation are

PC 1 {OR ,AND  NOT}

PC 2 { NAND }

PC 3 ( NOR )

PC 4 { XOR  AND }  

Note - By Heart  all.
2 2 votes
Answer is B because Multiplexer is the universal logic circuit that Comprise All the boolean function
• edited by
–1 –1 vote
answer - C
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 1999 | Ques...Next → · GATE CSE 1999 | Ques...
← Previous in category · GATE CSE 1999 | Ques...Next in category → · GATE CSE 1999 | Ques...
Position:
Show:

Related questions

43 43 votes
6 answers 6 answers
16.9k
16.9k views
Kathleen asked Sep 23, 2014
16,886 views
GATE CSE 1999 | Question: 1.3
The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is$^{n-1}C_k$$^nC_k$$^nC_{k+1}$None of the above
62 62 votes
8 answers 8 answers
32.6k
32.6k views
Kathleen asked Sep 23, 2014
32,582 views
GATE CSE 1999 | Question: 2.16
The number of full and half-adders required to add $16$-bit numbers is$8$ half-adders, $8$ full-adders$1$ half-adder, $15$ full-adders$16$ half-adders, $0$ full-adders$4$...
42 42 votes
4 answers 4 answers
13.2k
13.2k views
Kathleen asked Sep 23, 2014
13,178 views
GATE CSE 1999 | Question: 2.8
Consider the circuit shown below. In a certain steady state, the line $Y$ is at $'1'$. What are the possible values of $A, B$ and $C$ in this state?$A=0, B=0, C=1$$A=0, B...
35 35 votes
3 answers 3 answers
17.7k
17.7k views
Kathleen asked Sep 23, 2014
17,667 views
GATE CSE 1999 | Question: 1.21
The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is$O(n^2)$$O(n)$$O(\log n)$$O(1)$