3 ms·

The answer is yes; either NAND or NOR will work. You're just mapping a finite list of input configurations to a finite number of outputs. Any Turing complete

• lifepillar 9y ago
  Surely there are minimal subsets of functionally complete operators, in general different ones for different three-valued logics. E.g., for Łukasiewicz's logic (L3), ∧ (conjunction) and ⟶ (implication) will do (implication is not definable using other operators). I doubt that you could define, L3's operators just with NAND (or NOR). In L3, "N implies N" is T, and "not N" is N (where N is the third truth value). So, in one case, a formula whose components are all evaluated with N has truth value T, and in the other has truth value N. This is not a proof, of course, but I'd like to see such a definition of NAND :) Interestingly enough, with F571 SQL's propositional fragment is functionally complete: any three-valued truth table can be defined. For instance, Łukasiewicz's P ⟶ Q can be expressed with (not P or Q) or (P is unknown and Q is unknown) and the Słupecki operator, which is needed to obtain a functional complete system from L3, can be expressed with: (P or unknown) and unknown
• dghf 9y ago
  > You're just mapping a finite list of input configurations to a finite number of outputs. Any Turing complete system will be able to emulate it just by enumerating all of the possibilities. I don't follow. How does that bear on what minimal set of operators have to exist as givens in order to construct all the operators necessary to provide such a mapping?