Hacker News Reader

Comment by dghf | Hacker News Reader

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.

View on HN

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.

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

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

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.

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.

How many of those 20k operators are useful though?

Reply on news.ycombinator.com