According to the Wikipedia and other sources only NAND/NOR make one-element sets that are functionally complete. Then, there are also a lot of two-element functional complete sets.
Question: why $a{\wedge\neg}b$ (and similarly ${\neg}a{\wedge}b$ and duals like $a{\vee\neg}b$ and ${\neg}a{\vee}b$) are not considered universal gates? Yes, they violate at least one of Post's criterion for universality (i.e. $a{\wedge\neg}b$ is falsity-preserving), but, is this so important? You can build a NOT gate and an AND gate out of one any above mentioned gates, thus, making them universal.
Where am I mistaken? :)
2026-04-07 06:36:20.1775543780
Universality of $a{\wedge\neg}b$ gate and similar
58 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
You are mistaken. You cannot build a NOT gate, because NOT is not falsity-preserving ... Try building a NOT gate and you'll see. Notice that a∧¬a is equivalent to FALSE, not to ¬a