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

x'A+xB=x ,so how it is functionally complete?

The Gateway to Computer Science Excellence

+36 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 = 0$, 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.

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 = 0$, 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.

0

+1

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

We can determine OR using XOR ((A⊕1).(B⊕1))⊕1= (A'.B')' = A+B

So XOR,NOT is also functionally complete.

So XOR,NOT is also functionally complete.

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?

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?

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

+4

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

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.

+1

@Soumya

NOT,XOR is not Functionally complete

but AND,XOR

and OR,XOR is functionally complete

because XOR can itself create NOT gate

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?

+1

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

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

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

+10 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.

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.

+1

@shekhar chauhan {XOR, AND} are partially functionally complete. You need external 1 to get the NOT gate.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,241 answers

198,009 comments

104,601 users