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

4 Answers

+25 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 (357k 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.
+1
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 !

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

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
+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)
0
MUX too
+1 vote
Answer is C because Multiplexer is the universal logic circuit that Comprise All the boolean function
answered by Junior (963 points)
–2 votes
answer - C
answered by Loyal (9k 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 ?


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

39,584 questions
46,707 answers
140,136 comments
57,866 users