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

asked in Digital Logic by Veteran (59.6k points)
edited by | 3.6k views

4 Answers

+26 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.
answered by Veteran (362k points)
selected by
+2
@sushmita, with XOR gate, if one input is set to 1, then XOR gate behaves as NOT gate.

So, with AND and XOR gate we have AND and NOT gate, which is sufficient to realise any boolean function.
+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. 

0
@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
0
@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?
0
@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 ??

+8 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.
answered by Boss (45.3k points)
+1
MUX too
+1 vote
Answer is C because Multiplexer is the universal logic circuit that Comprise All the boolean function
answered by Junior (973 points)
–2 votes
answer - C
answered by Loyal (9.1k 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

42,455 questions
48,492 answers
154,710 comments
63,079 users