CODEWITHSUNDEEP
logichardwarexor
Programmer
Programmer

Reputation: 6753

Are the xor and not gates logically complete

Are the xor gate and the not gate logically complete. In other words, can we implement an logic circuit using them?

Upvotes: 7

Views: 16911

Answers (2)

Jefferson Steelflex
Jefferson Steelflex

Reputation: 17

All of the basic logic gates may be created with the NOT gate. An XOR gate acts as a NOT gate if one of the inputs are permanently zero.

AND: NOT(NOT(A) OR NOT(B))
OR: (may be made simply by connecting wires together, and maybe use some diodes)
NAND: NOT(A) OR NOT(B)
XOR: NOT(NOT(A) OR NOT(NOT(A) OR NOT(B))) OR NOT(NOT(NOT(A) OR NOT(B)) OR NOT(B)) ect.

Upvotes: -3

Alexander Serebrenik
Alexander Serebrenik

Reputation: 3577

NOR and NAND are the only functionally complete singleton gate sets. Hence, XOR is not functionally complete on its own (or together with NOT, since as point out above NOT can be created using XOR).

XOR can be complemented to a two-element functionally complete gate sets. One should add (left or right) implication.

You can find more about such sets in Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.

Upvotes: 7

Related Questions