Are the xor and not gates logically complete

Question

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

Solution

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.

Comments

[PleaseHelp]

Umm.. NOT cannot be created using XOR

[Paul R]

@AtulGangwar: of course it can - an XOR gate with one input set to 1 is an inverter.

[PleaseHelp]

@PaulR see my comment below the question.

[Paul R]

See my further comment above.

[Sam]

Are you saying NOT gate alone is functionally complete? But the examples you gave need more than just NOT gate