The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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$.

in Digital Logic by Veteran (52.1k points)
edited by | 5.1k views

4 Answers

+32 votes
Best answer
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 = 1$, 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.
by Veteran (416k points)
selected by
And the questions asks "is /are sufficient to implement any boolean function", so using XOR and AND you can implement any boolean function without using any other logic gate

@Arjun sir.
If help of $0 \ or\  1$ is needed to derive any of $(\wedge,\neg) \ or \  (\vee \neg)$- That function is partially functionally complete.
Still, is it considered as functionally complete?
Like in this question, in both B and C options help of 0 or 1 is required.
And in this question too. But they considered them functionally complete. 


NOT,XOR is not Functionally complete


and OR,XOR is functionally complete

because XOR can itself create NOT gate

because XOR can itself create NOT gate

It is possible with the help of 1. That's what I am saying. If input 1 or 0 is not available then? 


yes u r right.

{XOR,AND} not functionally complete

rather {XOR,AND} and the constant TRUE is functionally complete


{XOR , AND } is partially functionally complete set ,as to derive not we are taking the help of 1 ,

But here in question it is asking that Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

So can we say that both B) and C) should be right option?
@prince-that is what arjun sir has said in the answer :)

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

Does this allow us to use external 0 / 1 ??


@Arjun Sir I think in 4 C=0 will get the AND not C=1. Please correct me if I am wrong 

+9 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 2 { NAND }

PC 3 ( NOR )

PC 4 { XOR  AND }  

Note - By Heart  all.
by Boss (45.1k points)
MUX too


+1 vote
Answer is C because Multiplexer is the universal logic circuit that Comprise All the boolean function
by Junior (983 points)
–2 votes
answer - C
by Loyal (8.7k points)
I think B ,C

can you tell me please why not B????
2:1 MUX cant implement binary boolean functions
can you please explain why the answer is c ?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,830 questions
54,802 answers
80,751 users