Search code examples
computer-sciencehardware

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.

Solution

  • 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