The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
5.1k views

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
+1
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
0

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

+1
@Soumya

NOT,XOR is not Functionally complete

but AND,XOR

and OR,XOR is functionally complete

because XOR can itself create NOT gate
+2

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? 

0

yes u r right.

{XOR,AND} not functionally complete

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

https://www.quora.com/How-do-I-show-XOR-AND-and-the-constant-true-are-functionally-complete

0
+1
@Ayush

{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?
+1
@prince-that is what arjun sir has said in the answer :)
0

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

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

0

@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 1 {OR ,AND  NOT}

PC 2 { NAND }

PC 3 ( NOR )

PC 4 { XOR  AND }  

Note - By Heart  all.
by Boss (45.1k points)
+2
MUX too
0
XOR,OR

NOT,OR

NOT,AND 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)
+1
I think B ,C

can you tell me please why not B????
0
2:1 MUX cant implement binary boolean functions
0
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
189,511 comments
80,751 users