Three-Valued Logic

Re:Three-Valued Logic by dghf on Friday December 15, 2017 @05:30AM (#15930884)

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.

[ Parent | on HN ]

Re:Three-Valued Logic by Simon_says on Friday December 15, 2017 @06:32AM (#15931096)

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.

[ Parent | on HN ]

Re:Three-Valued Logic by lifepillar on Friday December 15, 2017 @08:19AM (#15931566)

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

[ Parent | on HN ]

Re:Three-Valued Logic by dghf on Saturday December 16, 2017 @06:54PM (#15943011)

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

[ Parent | on HN ]

Re:Three-Valued Logic by qubex on Friday December 15, 2017 @07:49AM (#15931384)

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.

[ Parent | on HN ]

Re:Three-Valued Logic by jeffwass on Saturday December 16, 2017 @04:56AM (#15938749)

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.

[ Parent | on HN ]

Re:Three-Valued Logic by jacobolus on Friday December 15, 2017 @07:12AM (#15931246)

How many of those 20k operators are useful though?

[ Parent | on HN ]