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

+27 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
0
for

2)say A,B two inputs , x select line  and A=0,B=1

x'A+xB=x ,so how it is functionally complete?
0
We are given multiplexers and we can use it any way we want- there is no restriction on how the inputs/select lines are. Our aim is to make some universal gate out of it- then that can be used to make any GATE.
0
ok some of them , not all
+1
if we make some universal gate- we can make all also :)
0
yes but not for all input , as that example I given previously it will not work
+1
that doesn't matter- we are given multiplexers and we can connect inputs in any way.
0
We can determine OR using XOR ((A⊕1).(B⊕1))⊕1= (A'.B')' = A+B

So XOR,NOT is also functionally complete.
+2
how u r getting AND for (A⊕1).(B⊕1) between (A⊕1)   and   (B⊕1)
0
Ya..my mistake!!

So with the help of 1 and 0 B and C are functionally complete ??

But is it allowed to use 0 or 1 to prove completeness?
0
yeah it is allowed
even universal logic gates nand,nor cant give 1 or 0
+1

@Arjun Sir

http://math.stackexchange.com/questions/333051/any-functionally-complete-sets-with-xor

in this link : {AND , EX-OR }  not functionaly complete 

plz confirm !

+1
Isn't that the set of functions which can derive all boolean functions with the help of 1/0, called partially functionally complete??
+1

how can  {∧,⊕} functionally complete either, because if all the inputs are false, then the output is always false too and hence it will preserve the false value, which is contradictory to the property of functionally complete sets??

+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
+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 ??

+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)
+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
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,514 questions
48,528 answers
155,008 comments
63,366 users