CODEWITHSUNDEEP
computer-sciencehardware
Math.anony
Math.anony

Reputation: 97

What other logic gates can be added to the set {XOR} to form a universal set?

I am having problem with the following question:

The set {XOR} is not a complete set, that is, XOR is not a universal gate. Add another logic gate into the set to make the new set a complete set, and prove that it is complete.

A NOT gate can be achieved through the use of XOR and a And gate can be represented through the a combination of a NOT gate and XOR gate.

I cannot figure out the second gate that I should use. Do I simply add an OR gate to the set because I feel that it is not answering the question.

Additionally, I would like to know if my understanding of a Universal Set is correct: A universal set should be able to represent {AND, OR, NOT}

Edit: It's not possible to create an And gate with XOR gate alone.

Upvotes: 4

Views: 1467

Answers (1)

Yom B
Yom B

Reputation: 238

You can't create an AND gate (or an OR gate for that matter) with XOR alone, hence it is not a universal set. XOR with AND is a universal set though - which means you can create any Boolean expression with this set.

You can find more info here: https://cseweb.ucsd.edu//classes/sp14/cse140-b/slides/140-sp14-lec6.pdf

Upvotes: 2

Related Questions