3 ms·

There are 16 possible dyadic operators for two-valued logic (two inputs, each with one of two possible values, mapping to a result with two possible values = 2^

by dghf 9y ago

There are 16 possible dyadic operators for two-valued logic (two inputs, each with one of two possible values, mapping to a result with two possible values = 2^(2^2)). If you have either NAND or NOR as a primitive, you can construct the others from it. There are 19,683 possible dyadic operators for three-valued logic (3^(3^2)). I don't know if there's an equivalent minimal set of primitives from which you can construct those.

Simon_says 9y ago
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 system will be able to emulate it just by enumerating all of the possibilities.
- 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?
jacobolus 9y ago
How many of those 20k operators are useful though?
qubex 9y ago
I remember reading about this in Stephen Wolfram’s pretty awful A New Kind Of Science. He attacked exactly this problem (and similar ones) by sampling brute-forced spaces. Not very sophisticated, and written extraordinarily badly.
jeffwass 9y ago
Your comment on dyadic enumeration was really interesting. I hadn't considered it before but it's amazing how fast the space of available "logic gates" blows out from just a simple transition of binary to trinary.

by dghf 9y ago

Simon_says 9y ago

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 system will be able to emulate it just by enumerating all of the possibilities.

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?

jacobolus 9y ago

How many of those 20k operators are useful though?

qubex 9y ago

I remember reading about this in Stephen Wolfram’s pretty awful A New Kind Of Science. He attacked exactly this problem (and similar ones) by sampling brute-forced spaces. Not very sophisticated, and written extraordinarily badly.

jeffwass 9y ago

Your comment on dyadic enumeration was really interesting. I hadn't considered it before but it's amazing how fast the space of available "logic gates" blows out from just a simple transition of binary to trinary.