1
$\begingroup$

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? :)

$\endgroup$
  • $\begingroup$ 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\wedge \neg a$ is equivalent to FALSE, not to $\neg a$. $\endgroup$ – Ewan Delanoy Aug 10 '17 at 8:45
  • $\begingroup$ in a∧¬b set a to truth? the gate is, basically, a CNOT and a basis for universal computation in cellular automatons (i.e. glider collision is in accordance to this function) $\endgroup$ – artemonster Aug 10 '17 at 8:48
  • $\begingroup$ You cannot set $a$ to TRUE unless you have previously shown TRUE to be in your generated system (and it isn't, since TRUE is not falsity-preserving ...) $\endgroup$ – Ewan Delanoy Aug 10 '17 at 8:50
  • $\begingroup$ ooooooh. that means that my functionally complete set would be {truth, a∧¬b} ? $\endgroup$ – artemonster Aug 10 '17 at 8:50
  • 1
    $\begingroup$ Yes, indeed. This one is functionally complete $\endgroup$ – Ewan Delanoy Aug 10 '17 at 8:51
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But wait, don't we have T and F values always available to us? There always has to be an input to these operators, right? $\endgroup$ – artemonster Aug 10 '17 at 9:17
  • $\begingroup$ No, T and F are not necessarily available. Notice that the gate which always returns T is not the same thing as the value T itself. $\endgroup$ – Ewan Delanoy Aug 10 '17 at 12:59
  • $\begingroup$ Maybe my understandings of mathematics are very poor, but how values "exist" then? And why there is a difference between value T and gate, that returns T? What is then connected, for instance, to the NAND gate as "nothing", for it initially to produce T? (...which is then used to produce F). Could you recommend something to read on this topic? $\endgroup$ – artemonster Aug 10 '17 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.