Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Multivalued logic

As noted by Jan Łukasiewicz and Emil Post in the early 1920s, it is possible to generalize ordinary logic to allow k values Range[0, 1, 1/(k - 1)], say with 0 being False, and 1 being True. Standard operations in logic can be generalized as Not[a_] = 1 - a, And[a_, b_] = Min[a, b], Or[a_, b_] = Max[a, b], Xor[a_, b_] = Abs[a - b], Equal[a_, b_] = 1 - Abs[a - b], Implies[a_, b_] = 1 - UnitStep[a - b](a - b). An alternative generalization for Not is Not[a_] := Mod[(k - 1) a + 1, k]/(k - 1). The function Nand[a_, b_] := Not[And[a, b]] used in the main text turns out to be universal for any k. Axiom systems can be set up for multivalued logic, but they are presumably more complicated than for ordinary k = 2 logic. (Compare page 1171.)

The idea of intermediate truth values has been discussed intermittently ever since antiquity. Often—as in the work of George Boole in 1847—a continuum of values between 0 and 1 are taken to represent probabilities of events, and this is the basis for the field of fuzzy logic popular since the 1980s.



Image Source Notebooks:

From Stephen Wolfram: A New Kind of Science [citation]