Skip to content
Coordinates of ThoughtHome of Philosophy
Join
Question · Explain

Strong Kleene, weak Kleene, Łukasiewicz: what actually differs between the tables?

Pieter van Dijkhuizen Fellow
· 4 replies
Modal & non-classical logicAnalyticModern EuropeanJan ŁukasiewiczStephen Kleene#kleene#partial-functions#three-valued-logic
Follow

I've been reading about how to reason with partially evaluated expressions, where some sub-expressions haven't been computed yet or failed. That led me to three-valued logics, and now I have three sets of truth tables on my desk that look almost identical.

Specifically: strong Kleene, weak Kleene and Łukasiewicz's three-valued logic. All three have true, false and a third value. They seem to agree most of the time.

Where do they actually come apart? And why would anyone want weak Kleene, where (if I read it right) any input with the third value makes the whole output the third value? That seems to throw away information.

LikeAnswer
Follow4 answers

Join the conversation: members reply here, and joining is free. Reading is always free.

Join free to reply Sign in

4 answers

Accepted answer

  1. Tomasz Szewczak

    ✓ Accepted answer Fellow

    The differences are small in the tables and large in what they mean. Call the third value U.

    Strong Kleene. Read U as "not yet determined". If one disjunct is true, the disjunction is true no matter what the other turns out to be: T or U = T. Likewise F and U = F. Only when the known values don't settle it do you get U.

    Weak Kleene. U is infectious: any connective with a U input gives U. Read U as "meaningless" or as a computation that never returns. If evaluating the left side never halts, you never get to discover the right side is true. Kleene's own motivation was partial recursive functions, in his Introduction to Metamathematics (1952), and earlier Bochvar had a similar system with "nonsense" as the third value.

    Łukasiewicz. Same as strong Kleene for and, or and not. The difference is the conditional: in Łukasiewicz's logic, U → U is true, while in strong Kleene it's U. That one cell matters a lot. It makes "if P then P" a tautology in Łukasiewicz's logic, whereas strong Kleene has no tautologies at all: give every atom the value U and every formula comes out U.

    So weak Kleene doesn't throw away information carelessly. It refuses to pretend you have information you can't get.

Other answers

  1. Pieter van Dijkhuizen

    Fellow

    That's very clarifying. Weak Kleene is basically NaN propagation in floating point: once a NaN gets into your arithmetic, everything downstream is NaN.

    Helpful · 1
    1. Derek Hollis

      Fellow

      Mostly, Pieter, but careful: NaN comparisons return false, not NaN, so IEEE floating point mixes weak-Kleene arithmetic with two-valued comparisons. And real programming languages often use a fourth pattern: short-circuit evaluation. "False AND (something that crashes)" returns false, but "(something that crashes) AND false" crashes. That's order-sensitive, which none of the three tables are. McCarthy wrote about these sequential connectives in the early 1960s.

      Helpful · 2
  2. Ana Clara Ferreira

    Fellow

    And a philosophical afterlife: Kripke's 1975 theory of truth builds a hierarchy of partial interpretations of "true", and the third value there is handled with strong Kleene (he discusses weak Kleene and supervaluation as alternatives). The liar sentence just never gets a classical value. So the choice between these tables isn't only an engineering preference. It's tied to what you think a truth-value gap is.

    Helpful · 3