Many-valued logics

Three-valued Logics

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

Introduction

If we just add one more value U\Undefsource to T\Truesource and F\Falsesource, we get a three-valued logic. Even though there is only one more truth value, the possibilities for defining the truth-functions for ¬\lnotsource, ∧\landsource, ∨\lorsource, and →\lifsource are quite numerous. Then a logic might use any combination of these truth functions, and you also have a choice of making only T\Truesource designated, or both T\Truesource and U\Undefsource.

We present here a selection of the most well-known three-valued logics, their motivations, and some of their properties.

L ukasiewicz logic

One of the first published, worked out proposals for a many-valued logic is due to the Polish philosopher Jan L ukasiewicz in 1921. L ukasiewicz was motivated by Aristotle's sea battle problem: It seems that, today, the sentence “There will be a sea battle tomorrow” is neither true nor false: its truth value is not yet settled. L ukasiewicz proposed to introduce a third truth value, to such “future contingent” sentences.

I can assume without contradiction that my presence in Warsaw at a certain moment of next year, e.g., at noon on 21 December, is at the present time determined neither positively nor negatively. Hence it is possible, but not necessary, that I shall be present in Warsaw at the given time. On this assumption the proposition “I shall be in Warsaw at noon on 21 December of next year,” can at the present time be neither true nor false. For if it were true now, my future presence in Warsaw would have to be necessary, which is contradictory to the assumption. If it were false now, on the other hand, my future presence in Warsaw would have to be impossible, which is also contradictory to the assumption. Therefore the proposition considered is at the moment neither true nor false and must possess a third value, different from “0” or falsity and “1” or truth. This value we can designate by “12\frac{1}{2}source.” It represents “the possible,” and joins “the true” and “the false” as a third value.

We will use U\Undefsource for L ukasiewicz's third truth value.Footnote: L ukasiewicz here uses “possible” in a way that is uncommon today, namely to mean possible but not necessary.

The truth functions for the connectives ¬\lnotsource, ∧\landsource, and ∨\lorsource are easy to determine on this interpretation: the negation of a future contingent sentence is also a future contingent sentence, so ¬~(U)=U\tf{\lnot}(\Undef) = \Undefsource. If one conjunct of a conjunction is undetermined and the other is true, the conjunction is also undetermined---after all, depending on how the future contingent conjunct turns out, the conjunction might turn out to be true, and it might turn out to be false. So

∧~(T,U)=∧~(U,T)=U.\tf{\land}(\True, \Undef) = \tf{\land}(\Undef, \True) = \Undef.source

If the other conjunct is false, however, it cannot turn out true, so

∧~(F,U)=∧~(F,U)=F.\tf{\land}(\False, \Undef) = \tf{\land}(\False, \Undef) = \False.source

The other values (if the arguments are settled truth values, T\Truesource or F\Falsesource, are like in classical logic.

For the conditional, the situation is a little trickier. Suppose qqsource is a future contingent statement. If ppsource is false, then p→qp \lif qsource will be true, regardless of how qqsource turns out, so we should set →~(F,U)=T\tf{\lif}(\False, \Undef) = \Truesource. And if ppsource is true, then q→pq \lif psource will be true, regardless of what qqsource turns out to be, so →~(U,T)=T\tf{\lif}(\Undef, \True) = \Truesource. If ppsource is true, then p→qp \lif qsource might turn out to be true or false, so →~(T,U)=U\tf{\lif}(\True, \Undef) = \Undefsource. Similarly, if ppsource is false, then q→pq \lif psource might turn out to be true or false, so →~(U,F)=U\tf{\lif}(\Undef, \False) = \Undefsource. This leaves the case where ppsource and qqsource are both future contingents. On the basis of the motivation, we should really assign U\Undefsource in this case. However, this would make A→A!A \lif !Asource not a tautology. L ukasiewicz had not trouble giving up A∨¬A!A \lor \lnot !Asource and ¬(A∧¬A)\lnot(!A \land \lnot !A)source, but balked at giving up A→A!A \lif !Asource. So he stipulated →~(U,U)=T\tf{\lif}(\Undef, \Undef) = \Truesource.

Definition of three valued Lukasiewicz logic

Three-valued L ukasiewicz logic is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource is the only designated value, i.e., V+={T}V^+ = \{\True\}source.

  4. Truth functions are given by the following tables:

    Lukasiewicz negation truth table

    Table for Lukasiewicz negation truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output U. Row three: input false, output true. End table.

    Lukasiewicz negation truth table
    ¬~\tf{\lnot}source
    T\TruesourceF\Falsesource
    U\UndefsourceU\Undefsource
    F\FalsesourceT\Truesource
    source 86

    quad

    Lukasiewicz conjunction truth table

    Table for Lukasiewicz conjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs U, U, false. Row three: first input false, outputs false, false, false. End table.

    Lukasiewicz conjunction truth table
    ∧~Ł3\tf{\land}[\LogLuk[3]]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceU\UndefsourceU\UndefsourceF\Falsesource
    F\FalsesourceF\FalsesourceF\FalsesourceF\Falsesource
    source 94

    \\[2ex]

    Lukasiewicz disjunction truth table

    Table for Lukasiewicz disjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, true, true. Row two: first input U, outputs true, U, U. Row three: first input false, outputs true, U, false. End table.

    Lukasiewicz disjunction truth table
    ∨~Ł3\tf{\lor}[\LogLuk[3]]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceT\TruesourceT\Truesource
    U\UndefsourceT\TruesourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceU\UndefsourceF\Falsesource
    source 102

    quad

    Lukasiewicz conditional truth table

    Table for Lukasiewicz conditional truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs true, true, U. Row three: first input false, outputs true, true, true. End table.

    Lukasiewicz conditional truth table
    →~Ł3\tf{\lif}[\LogLuk[3]]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceT\TruesourceT\TruesourceU\Undefsource
    F\FalsesourceT\TruesourceT\TruesourceT\Truesource
    source 110

As can easily be seen, any formula A!Asource containing only ¬\lnotsource, ∧\landsource, and ∨\lorsource will take the truth value U\Undefsource if all its propositional variables are assigned U\Undefsource. So for instance, the classical tautologies p∨¬pp \lor \lnot psource and ¬(p∧¬p)\lnot(p \land \lnot p)source are not tautologies in Ł3\LogLuk[3]source, since v¯(A)=U\pValue{v}(!A) = \Undefsource whenever v(p)=U\pAssign v(p) = \Undefsource.

On valuations where v(p)=T\pAssign v(p) = \Truesource or F\Falsesource, v¯(A)\pValue v(!A)source will coincide with its classical truth value.

Agreement with classical values on settled assignments

If v(p)∈{T,F}\pAssign v(p) \in \{\True, \False\}source for all ppsource in A!Asource, then v¯Ł3(A)=v¯C(A)\pValue v(!A)[\LogLuk[3]] = \pValue v(!A)[\LogCL]source.

Exercise on the Lukasiewicz biconditional

Suppose we define v¯(A↔B)=v¯((A→B)∧(B→A))\pValue v(!A \liff !B) = \pValue v((!A \lif !B) \land (!B \lif !A))source in Ł3\LogLuk[3]source. What truth table would ↔\liffsource have?

Many classical tautologies are also tautologies in Ł3\LogLuk[3]source, e.g, ¬p→(p→q)\lnot p \lif (p \lif q)source. Just like in classical logic, we can use truth tables to verify this:

Nine row Lukasiewicz tautology verification table

Truth table verifying the Lukasiewicz tautology if not p then, if p then q. Eight source columns, left to right. Column one, p, is the p input. Column two, q, is the q input. Column three, negation, gives negation of p. Column four, p, repeats p. Column five, conditional, gives the main conditional result. Column six, open parenthesis then p, repeats p inside the consequent. Column seven, conditional, gives the inner conditional result. Column eight, q then close parenthesis, repeats q inside the consequent. Row one. p input, true. q input, true. negation of p, false. p repeated, true. main conditional result, true. p inside parentheses, true. inner conditional result, true. q inside parentheses, true. Row two. p input, true. q input, U. negation of p, false. p repeated, true. main conditional result, true. p inside parentheses, true. inner conditional result, U. q inside parentheses, U. Row three. p input, true. q input, false. negation of p, false. p repeated, true. main conditional result, true. p inside parentheses, true. inner conditional result, false. q inside parentheses, false. Row four. p input, U. q input, true. negation of p, U. p repeated, U. main conditional result, true. p inside parentheses, U. inner conditional result, true. q inside parentheses, true. Row five. p input, U. q input, U. negation of p, U. p repeated, U. main conditional result, true. p inside parentheses, U. inner conditional result, true. q inside parentheses, U. Row six. p input, U. q input, false. negation of p, U. p repeated, U. main conditional result, true. p inside parentheses, U. inner conditional result, U. q inside parentheses, false. Row seven. p input, false. q input, true. negation of p, true. p repeated, false. main conditional result, true. p inside parentheses, false. inner conditional result, true. q inside parentheses, true. Row eight. p input, false. q input, U. negation of p, true. p repeated, false. main conditional result, true. p inside parentheses, false. inner conditional result, true. q inside parentheses, U. Row nine. p input, false. q input, false. negation of p, true. p repeated, false. main conditional result, true. p inside parentheses, false. inner conditional result, true. q inside parentheses, false. The main conditional column is true in every source row. End table.

Nine row Lukasiewicz tautology verification table
ppsourceqqsource¬\lnotsourceppsource→\lifsource(p\smash{(}psource→\lifsourceq)q\smash{)}source
T\TruesourceT\TruesourceF\FalsesourceT\TruesourceT\TruesourceT\TruesourceT\TruesourceT\Truesource
T\TruesourceU\UndefsourceF\FalsesourceT\TruesourceT\TruesourceT\TruesourceU\UndefsourceU\Undefsource
T\TruesourceF\FalsesourceF\FalsesourceT\TruesourceT\TruesourceT\TruesourceF\FalsesourceF\Falsesource
U\UndefsourceT\TruesourceU\UndefsourceU\UndefsourceT\TruesourceU\UndefsourceT\TruesourceT\Truesource
U\UndefsourceU\UndefsourceU\UndefsourceU\UndefsourceT\TruesourceU\UndefsourceT\TruesourceU\Undefsource
U\UndefsourceF\FalsesourceU\UndefsourceU\UndefsourceT\TruesourceU\UndefsourceU\UndefsourceF\Falsesource
F\FalsesourceT\TruesourceT\TruesourceF\FalsesourceT\TruesourceF\FalsesourceT\TruesourceT\Truesource
F\FalsesourceU\UndefsourceT\TruesourceF\FalsesourceT\TruesourceF\FalsesourceT\TruesourceU\Undefsource
F\FalsesourceF\FalsesourceT\TruesourceF\FalsesourceT\TruesourceF\FalsesourceT\TruesourceF\Falsesource
source 145

Exercise on three Lukasiewicz tautologies

Show that the following are tautologies in Ł3\LogLuk[3]source:

  1. p→(q→p)p \lif (q \lif p)source

  2. ¬(p∧q)↔(¬p∨¬q)\lnot(p \land q) \liff (\lnot p \lor \lnot q)source

  3. ¬(p∨q)↔(¬p∧¬q)\lnot(p \lor q) \liff (\lnot p \land \lnot q)source

(In the preceding exercise item on the negation of a conjunction and the preceding exercise item on the negation of a disjunction, take A↔B!A \liff !Bsource as an abbreviation for (A→B)∧(B→A)(!A \lif !B) \land (!B \lif !A)source, or refer to your solution to the exercise defining the Lukasiewicz biconditional.)

Exercise on classical tautologies that fail in Lukasiewicz logic

Show that the following classical tautologies are not tautologies in Ł3\LogLuk[3]source:

  1. (¬p∧p)→q)(\lnot p \land p) \lif q)source

  2. ((p→q)→p)→p((p \lif q) \lif p) \lif psource

  3. (p→(p→q))→(p→q)(p \lif (p \lif q)) \lif (p \lif q)source

One might therefore perhaps think that although not all classical tautologies are tautologies in Ł3\LogLuk[3]source, they should at least take either the value T\Truesource or the value U\Undefsource on every valuation. This is not the case. A counterexample is given by

¬(p→¬p)∨¬(¬p→p)\lnot(p \lif \lnot p) \lor \lnot(\lnot p \lif p)source

which is F\Falsesource if ppsource is U\Undefsource.

Exercise on five Lukasiewicz consequence relations

Which of the following relations hold in L ukasiewicz logic? Give a truth table for each.

  1. p,p→q⊨qp, p \lif q \Entails qsource

  2. ¬¬p⊨p\lnot\lnot p \Entails psource

  3. p∧q⊨pp \land q \Entails psource

  4. p⊨p∧pp \Entails p \land psource

  5. p⊨p∨qp \Entails p \lor qsource

L ukasiewicz hoped to build a logic of possibility on the basis of his three-valued system, by introducing a one-place connective ◇A\Diamond !Asource (for “A!Asource is possible”) and a corresponding □A\Box !Asource (for “A!Asource is necessary”):

Possibility truth table

Table for Possibility truth table. Two columns: input, then output. Row one: input true, output true. Row two: input U, output true. Row three: input false, output false. End table.

Possibility truth table
◇~\tf{\Diamond}source
T\TruesourceT\Truesource
U\UndefsourceT\Truesource
F\FalsesourceF\Falsesource
source 206

quad

Necessity truth table

Table for Necessity truth table. Two columns: input, then output. Row one: input true, output true. Row two: input U, output false. Row three: input false, output false. End table.

Necessity truth table
□~\tf{\Box}source
T\TruesourceT\Truesource
U\UndefsourceF\Falsesource
F\FalsesourceF\Falsesource
source 214

In other words, ppsource is possible iff it is not already settled as false; and ppsource is necessary iff it is already settled as true.

Exercise on possibility and necessity duality

Show that □p↔¬◇¬p\Box p \liff \lnot\Diamond \lnot psource and ◇p↔¬□¬p\Diamond p \liff \lnot \Box \lnot psource are tautologies in Ł3\LogLuk[3]source, extended with the truth tables for □\Boxsource and ◇\Diamondsource.

However, the shortcomings of this proposed modal logic soon became evident: However things turn out, p∧¬pp \land \lnot psource can never turn out to be true. So even if it is not now settled (and therefore undetermined), it should count as impossible, i.e., ¬◇(p∧¬p)\lnot \Diamond(p \land \lnot p)source should be a tautology. However, if v(p)=U\pAssign v(p) = \Undefsource, then v¯(¬◇(p∧¬p))=U\pValue v(\lnot \Diamond(p \land \lnot p)) = \Undefsource. Although L ukasiewicz was correct that two truth values will not be enough to accommodate modal distinctions such as possiblity and necessity, introducing a third truth value is also not enough.

Kleene logics

Stephen Kleene introduced two three-valued logics motivated by a logic in which truth values are thought of the outcomes of computational procedures: a procedure may yield T\Truesource or F\Falsesource, but it may also fail to terminate. In that case the corresponding truth value is undefined, represented by the truth value U\Undefsource.

To compute the negation of a proposition A!Asource, you would first compute the value of A!Asource, and then return the opposite of the result. If the computation of A!Asource does not terminate, then the entire procedure does not either: so the negation of U\Undefsource is U\Undefsource.

To compute a conjunction A∧B!A \land !Bsource, there are two options: one can first compute A!Asource, then B!Bsource, and then the result would be T\Truesource if the outcome of both is T\Truesource, and F\Falsesource otherwise. If either computation fails to halt, the entire procedure does as well. So in this case, the if one conjunct is undefined, the conjunction is as well. The same goes for disjunction.

However, if we can evaluate A!Asource and B!Bsource in parallel, we can do better. Then, if one of the two procedures halts and returns F\Falsesource, we can stop, as the answer must be false. So in that case a conjunction with one false conjunct is false, even if the other conjunct is undefined. Similarly, when computing a disjunction in parallel, we can stop once the procedure for one of the two disjuncts has returned true: then the disjunction must be true. So in this case we can know what the outcome of a compound claim is, even if one of the components is undefined. On this interpretation, we might read U\Undefsource as “unknown” rather than “undefined.”

The two interpretations give rise to Kleene's strong and weak logic. The conditional is defined as equivalent to ¬A∨B\lnot !A \lor !Bsource.

Definition of strong Kleene logic

Strong Kleene logic Ks\LogKssource is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource is the only designated value, i.e., V+={T}V^+ = \{\True\}source.

  4. Truth functions are given by the following tables:

    Strong Kleene negation truth table

    Table for Strong Kleene negation truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output U. Row three: input false, output true. End table.

    Strong Kleene negation truth table
    ¬~\tf{\lnot}source
    T\TruesourceF\Falsesource
    U\UndefsourceU\Undefsource
    F\FalsesourceT\Truesource
    source 54

    quad

    Strong Kleene conjunction truth table

    Table for Strong Kleene conjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs U, U, false. Row three: first input false, outputs false, false, false. End table.

    Strong Kleene conjunction truth table
    ∧~Ks\tf{\land}[\LogKs]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceU\UndefsourceU\UndefsourceF\Falsesource
    F\FalsesourceF\FalsesourceF\FalsesourceF\Falsesource
    source 62

    \\[2ex]

    Strong Kleene disjunction truth table

    Table for Strong Kleene disjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, true, true. Row two: first input U, outputs true, U, U. Row three: first input false, outputs true, U, false. End table.

    Strong Kleene disjunction truth table
    ∨~Ks\tf{\lor}[\LogKs]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceT\TruesourceT\Truesource
    U\UndefsourceT\TruesourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceU\UndefsourceF\Falsesource
    source 70

    quad

    Strong Kleene conditional truth table

    Table for Strong Kleene conditional truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs true, U, U. Row three: first input false, outputs true, true, true. End table.

    Strong Kleene conditional truth table
    →~Ks\tf{\lif}[\LogKs]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceT\TruesourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceT\TruesourceT\Truesource
    source 78

Definition of weak Kleene logic

Weak Kleene logic Kw\LogKwsource is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource is the only designated value, i.e., V+={T}V^+ = \{\True\}source.

  4. Truth functions are given by the following tables:

    Weak Kleene negation truth table

    Table for Weak Kleene negation truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output U. Row three: input false, output true. End table.

    Weak Kleene negation truth table
    ¬~\tf{\lnot}source
    T\TruesourceF\Falsesource
    U\UndefsourceU\Undefsource
    F\FalsesourceT\Truesource
    source 98

    quad

    Weak Kleene conjunction truth table

    Table for Weak Kleene conjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs U, U, U. Row three: first input false, outputs false, U, false. End table.

    Weak Kleene conjunction truth table
    ∧~Kw\tf{\land}[\LogKw]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceU\UndefsourceU\UndefsourceU\Undefsource
    F\FalsesourceF\FalsesourceU\UndefsourceF\Falsesource
    source 106

    \\[2ex]

    Weak Kleene disjunction truth table

    Table for Weak Kleene disjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, true. Row two: first input U, outputs U, U, U. Row three: first input false, outputs true, U, false. End table.

    Weak Kleene disjunction truth table
    ∨~Kw\tf{\lor}[\LogKw]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceT\Truesource
    U\UndefsourceU\UndefsourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceU\UndefsourceF\Falsesource
    source 114

    quad

    Weak Kleene conditional truth table

    Table for Weak Kleene conditional truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs U, U, U. Row three: first input false, outputs true, U, true. End table.

    Weak Kleene conditional truth table
    →~Kw\tf{\lif}[\LogKw]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceU\UndefsourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceU\UndefsourceT\Truesource
    source 122

Neither Kleene logic has a tautology

Ks\LogKssource and Kw\LogKwsource have no tautologies.

Proof

If v(p)=U\pAssign v(p) = \Undefsource for all propositional variables ppsource, then any formula A!Asource will have truth value v¯(A)=U\pValue v(!A) = \Undefsource, since

¬~(U)=∨~(U,U)=∧~(U,U)=→~(U,U)=U\tf{\lnot}(\Undef) = \tf{\lor}(\Undef, \Undef) = \tf{\land}(\Undef, \Undef) = \tf{\lif}(\Undef, \Undef) = \Undefsource

in both logics. As U∉V+\Undef \notin V^+source for either Ks\LogKssource or Kw\LogKwsource, on this valuation, A!Asource will not be designated.

Although both weak and strong Kleene logic have no tautologies, they have non-trivial consequence relations.

Exercise comparing strong and weak Kleene consequence

Which of the following relations hold in (a) strong and (b) weak Kleene logic? Give a truth table for each.

  1. p,p→q⊨qp, p \lif q \Entails qsource

  2. p∨q,¬p⊨qp \lor q, \lnot p \Entails qsource

  3. p∧q⊨pp \land q \Entails psource

  4. p⊨p∧pp \Entails p \land psource

  5. p⊨p∨qp \Entails p \lor qsource

Dmitry Bochvar interpreted U\Undefsource as “meaningless” and attempted to use it to solve paradoxes such as the Liar paradox by stipulating that paradoxical sentences take the value U\Undefsource. He introduced a logic which is essentially weak Kleene logic extended by additional connectives, two of which are “external negation” and the “is undefined” operator:

Bochvar external negation truth table

Table for Bochvar external negation truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output true. Row three: input false, output true. End table.

Bochvar external negation truth table
∼~\tf{\sim}source
T\TruesourceF\Falsesource
U\UndefsourceT\Truesource
F\FalsesourceT\Truesource
source 171

quad

Bochvar is undefined truth table

Table for Bochvar is undefined truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output true. Row three: input false, output false. End table.

Bochvar is undefined truth table
+~\tf{+}source
T\TruesourceF\Falsesource
U\UndefsourceT\Truesource
F\FalsesourceF\Falsesource
source 179

Exercise defining Bochvar external negation

Can you define ∼\simsource in Bochvar's logic in terms of ¬\lnotsource and ++source, i.e., find a formula with only the propositional variable ppsource and not involving ∼\simsource which always takes the same truth value as ∼p\mathord{\sim}psource? Give a truth table to show you're right.

Gödel logics

Kurt Gödel introduced a sequence of nnsource-valued logics that each contain all formulas valid in intuitionistic logic, and are contained in classical logic. Here is the first interesting one:

Definition of three valued Goedel logic

33source-valued Gödel logic G\LogGodsource is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ⊥\lfalsesource, ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource is the only designated value, i.e., V+={T}V^+ = \{\True\}source.

  4. For ⊥\lfalsesource, we have ⊥~=F\tf{\lfalse} = \Falsesource. Truth functions for the remaining connectives are given by the following tables:

    Goedel negation truth table

    Table for Goedel negation truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output false. Row three: input false, output true. End table.

    Goedel negation truth table
    ¬~G\tf{\lnot}[\LogGod]source
    T\TruesourceF\Falsesource
    U\UndefsourceF\Falsesource
    F\FalsesourceT\Truesource
    source 28

    quad

    Goedel conjunction truth table

    Table for Goedel conjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs U, U, false. Row three: first input false, outputs false, false, false. End table.

    Goedel conjunction truth table
    ∧~G\tf{\land}[\LogGod]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceU\UndefsourceU\UndefsourceF\Falsesource
    F\FalsesourceF\FalsesourceF\FalsesourceF\Falsesource
    source 36

    \\[2ex]

    Goedel disjunction truth table

    Table for Goedel disjunction truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, true, true. Row two: first input U, outputs true, U, U. Row three: first input false, outputs true, U, false. End table.

    Goedel disjunction truth table
    ∨~G\tf{\lor}[\LogGod]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceT\TruesourceT\Truesource
    U\UndefsourceT\TruesourceU\UndefsourceU\Undefsource
    F\FalsesourceT\TruesourceU\UndefsourceF\Falsesource
    source 44

    quad

    Goedel conditional truth table

    Table for Goedel conditional truth table. The first column is the first input. The other three columns have second inputs, in order, true, U, false. Read outputs in that column order. Row one: first input true, outputs true, U, false. Row two: first input U, outputs true, true, false. Row three: first input false, outputs true, true, true. End table.

    Goedel conditional truth table
    →~G\tf{\lif}[\LogGod]sourceT\TruesourceU\UndefsourceF\Falsesource
    T\TruesourceT\TruesourceU\UndefsourceF\Falsesource
    U\UndefsourceT\TruesourceT\TruesourceF\Falsesource
    F\FalsesourceT\TruesourceT\TruesourceT\Truesource
    source 52

You'll notice that the truth tables for ∧\landsource and ∨\lorsource are the same as in L ukasiewicz and strong Kleene logic, but the truth tables for ¬\lnotsource and →\lifsource differ for each. In Gödel logic, ¬~(U)=F\tf{\lnot}(\Undef) = \Falsesource. In contrast to L ukasiewicz logic and Kleene logic, →~(U,F)=F\tf{\lif}(\Undef, \False) = \Falsesource; in contrast to Kleene logic (but as in L ukasiewicz logic), →~(U,U)=T\tf{\lif}(\Undef, \Undef) = \Truesource.

As the connection to intuitionistic logic alluded to above suggests, G3\LogGod[3]source is close to intuitionistic logic. All intuitionistic truths are tautologies in G3\LogGod[3]source, and many classical tautologies that are not valid intuitionistically also fail to be tautologies in G3\LogGod[3]source. For instance, the following are not tautologies:

p∨¬p(p→q)→(¬p∨q)¬¬p→p¬(¬p∧¬q)→(p∨q)((p→q)→p)→p¬(p→q)→(p∧¬q)& p \lor \lnot p && (p \lif q) \lif (\lnot p \lor q) \\ & \lnot\lnot p \lif p && \lnot(\lnot p \land \lnot q) \lif (p \lor q) \\ & ((p \lif q) \lif p) \lif p && \lnot(p \lif q) \lif (p \land \lnot q)source

However, not every tautology of G3\LogGod[3]source is also intuitionistically valid, e.g., ¬¬p∨¬p\lnot\lnot p \lor \lnot psource or (p→q)∨(q→p)(p \lif q) \lor (q \lif p)source.

Exercise on four Goedel tautologies

Give truth tables to show that the following are tautologies of G3\LogGod[3]source:

¬¬p∨¬p(p→q)∨(q→p)¬(p∧q)→(¬p∨¬q)(p→q)∨(q→r)∨(r→s)& \lnot\lnot p \lor \lnot p\\ & (p \lif q) \lor (q \lif p) \\ & \lnot(p \land q) \lif (\lnot p \lor \lnot q) \\ & (p \lif q) \lor (q \lif r) \lor (r \lif s)source

Exercise on four failures of Goedel validity

Give truth tables that show that the following are not tautologies of G3\LogGod[3]source

(p→q)→(¬p∨q)¬(¬p∧¬q)→(p∨q)((p→q)→p)→p¬(p→q)→(p∧¬q)& (p \lif q) \lif (\lnot p \lor q) \\ & \lnot(\lnot p \land \lnot q) \lif (p \lor q) \\ & ((p \lif q) \lif p) \lif p \\ & \lnot(p \lif q) \lif (p \land \lnot q)source

Exercise on five Goedel consequence relations

Which of the following relations hold in Gödel logic? Give a truth table for each.

  1. p,p→q⊨qp, p \lif q \Entails qsource

  2. p∨q,¬p⊨qp \lor q, \lnot p \Entails qsource

  3. p∧q⊨pp \land q \Entails psource

  4. p⊨p∧pp \Entails p \land psource

  5. p⊨p∨qp \Entails p \lor qsource

Designating not just T\Truesource

So far the logics we've seen all had the set of designated truth values V+={T}V^+ = \{\True\}source, i.e., something counts as true iff its truth value is T\Truesource. But one might also count something as true if it's just not F\Falsesource. Then one would get a logic by stipulating in the matrix, e.g., that V+={T,U}V^+ = \{\True, \Undef\}source.

Definition of the logic of paradox

The logic of paradox LP\LogLPsource is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource and U\Undefsource are designated, i.e., V+={T,U}V^+ = \{\True, \Undef\}source.

  4. Truth functions are the same as in strong Kleene logic.

Definition of Hallden logic of nonsense

Halldén's logic of nonsense Hal\LogHalsource is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource and a 11source-place connective ++source.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource and U\Undefsource are designated, i.e., V+={T,U}V^+ = \{\True, \Undef\}source.

  4. Truth functions are the same as weak Kleene logic, plus the “is meaningless” operator:

    Hallden is meaningless truth table

    Table for Hallden is meaningless truth table. Two columns: input, then output. Row one: input true, output false. Row two: input U, output true. Row three: input false, output false. End table.

    Hallden is meaningless truth table
    +~\tf{+}source
    T\TruesourceF\Falsesource
    U\UndefsourceT\Truesource
    F\FalsesourceF\Falsesource
    source 40

By contrast to the Kleene logics with which they share truth tables, these do have tautologies.

The logic of paradox has the classical tautologies

The tautologies of LP\LogLPsource are the same as the tautologies of classical propositional logic.

Proof

By the earlier proposition comparing many valued and classical validity, if ⊨LPA\Entails[\LogLP] !Asource then ⊨CA\Entails[\LogCL] !Asource. To show the reverse, we show that if there is a valuation v:At0→{F,T,U}\pAssign v\colon \PVar \to \{\False, \True, \Undef\}source such that v¯Ks(A)=F\pValue v(!A)[\LogKs] = \Falsesource then there is a valuation v′:At0→{F,T}\pAssign {v'}\colon \PVar \to \{\False, \True\}source such that v′¯C(A)=F\pValue {v'}(!A)[\LogCL] = \Falsesource. This establishes the result for LP\LogLPsource, since Ks\LogKssource and LP\LogLPsource have the same characteristic truth functions, and F\Falsesource is the only truth value of LP\LogLPsource that is not designated (that is the only difference between LP\LogLPsource and Ks\LogKssource). Thus, if ⊭LPA\Entails/[\LogLP] !Asource, for some valuation v\pAssign vsource, v¯LP(A)=v¯Ks(A)=F\pValue v(!A)[\LogLP] = \pValue v[\LogKs](!A) = \Falsesource. By the claim we're proving, v′¯C(A)=F\pValue{v'}[\LogCL](!A) = \Falsesource, i.e., ⊭CA\Entails/[\LogCL] !Asource.

To establish the claim, we first define v′\pAssign {v'}source as

v′(p)={Tif v(p)∈{T,U}Fotherwise\pAssign {v'}(p) = \begin{cases} \True & \text{if } \pAssign {v}(p) \in \{\True, \Undef\}\\ \False & \text{otherwise} \end{cases}source

We now show by induction on A!Asource that (a) if v¯Ks(A)=F\pValue v(!A)[\LogKs] = \Falsesource then v′¯C(A)=F\pValue {v'}(!A)[\LogCL] = \Falsesource, and (b) if v¯Ks(A)=T\pValue v(!A)[\LogKs] = \Truesource then v′¯C(A)=T\pValue {v'}(!A)[\LogCL] = \Truesource

  1. Induction basis: A≡p!A \ident psource. By the definition of the value of a formula under an assignment, v¯Ks(A)=v(p)=v′¯C(A)\pValue v(!A)[\LogKs] = \pAssign v(p) = \pValue {v'}(!A)[\LogCL]source, which implies both (a) and (b).

    For the induction step, consider the cases:

  2. A≡¬B!A \ident \lnot !Bsource.

    1. Suppose v¯Ks(¬B)=F\pValue v(\lnot!B)[\LogKs] = \Falsesource. By the definition of ¬~Ks\tf{\lnot}[\LogKs]source, v¯Ks(B)=T\pValue v(!B)[\LogKs] = \Truesource. By inductive hypothesis, case (b), we get v′¯C(B)=T\pValue {v'}(!B)[\LogCL] = \Truesource, so v′¯C(¬B)=F\pValue {v'}(\lnot !B)[\LogCL] = \Falsesource.

    2. Suppose v¯Ks(¬B)=T\pValue v(\lnot!B)[\LogKs] = \Truesource. By the definition of ¬~Ks\tf{\lnot}[\LogKs]source, v¯Ks(B)=F\pValue v(!B)[\LogKs] = \Falsesource. By inductive hypothesis, case (a), we get v′¯C(B)=F\pValue {v'}(!B)[\LogCL] = \Falsesource, so v′¯C(¬B)=T\pValue {v'}(\lnot !B)[\LogCL] = \Truesource.

  3. A≡(B∧C)!A \ident (!B \land !C)source.

    1. Suppose v¯Ks(B∧C)=F\pValue v(!B \land !C)[\LogKs] = \Falsesource. By the definition of ∧~Ks\tf{\land}[\LogKs]source, v¯Ks(B)=F\pValue v(!B)[\LogKs] = \Falsesource or v¯Ks(B)=F\pValue v(!B)[\LogKs] = \Falsesource. By inductive hypothesis, case (a), we get v′¯C(B)=F\pValue {v'}(!B)[\LogCL] = \Falsesource or v′¯C(C)=F\pValue {v'}(!C)[\LogCL] = \Falsesource, so v′¯C(B∧C)=F\pValue {v'}(!B \land !C)[\LogCL] = \Falsesource.

    2. Suppose v¯Ks(B∧C)=T\pValue v(!B \land !C)[\LogKs] = \Truesource. By the definition of ∧~Ks\tf{\land}[\LogKs]source, v¯Ks(B)=T\pValue v(!B)[\LogKs] = \Truesource and v¯Ks(B)=T\pValue v(!B)[\LogKs] = \Truesource. By inductive hypothesis, case (b), we get v′¯C(B)=T\pValue {v'}(!B)[\LogCL] = \Truesource and v′¯C(C)=T\pValue {v'}(!C)[\LogCL] = \Truesource, so v′¯C(B∧C)=T\pValue {v'}(!B \land !C)[\LogCL] = \Truesource.

The other two cases are similar, and left as exercises. Alternatively, the proof above establishes the result for all formulas only containing ¬\lnotsource and ∧\landsource. One may now appeal to the facts that in both Ks\LogKssource and C\LogCLsource, for any v\pAssign vsource, v¯(B∨C)=v¯(¬(¬B∧¬C))\pValue v(!B \lor !C) = \pValue v(\lnot(\lnot!B \land \lnot !C))source and v¯(B→C)=v¯(¬(B∧¬C))\pValue v(!B \lif !C) = \pValue v(\lnot(!B \land \lnot !C))source.

Exercise completing the logic of paradox proof

Complete the proof the proposition that the logic of paradox has exactly the classical tautologies, i.e., establish (a) and (b) for the cases where A≡(B∨C)!A \ident (!B \lor !C)source and A≡(B→C)!A \ident (!B \lif !C)source.

Exercise on Hallden tautologies

Prove that every classical tautology is a tautology in Hal\LogHalsource.

Although they have the same tautologies as classical logic, their consequence relations are different. LP\LogLPsource, for instance, is paraconsistent in that ¬p,p⊭q\lnot p, p \Entails/ qsource, and so the principle of explosion ¬A,A⊨B\lnot !A, !A \Entails !Bsource does not hold in general. (It holds for some cases of A!Asource and B!Bsource, e.g., if B!Bsource is a tautology.)

Exercise comparing consequence in paradox and nonsense logics

Which of the following relations hold in (a) LP\LogLPsource and in (b) Hal\LogHalsource? Give a truth table for each.

  1. p,p→q⊨qp, p \lif q \Entails qsource

  2. ¬q,p→q⊨¬p\lnot q, p \lif q \Entails \lnot psource

  3. p∨q,¬p⊨qp \lor q, \lnot p \Entails qsource

  4. ¬p,p⊨q\lnot p, p \Entails qsource

  5. p⊨p∨qp \Entails p \lor qsource

  6. p→q,q→r⊨p→rp \lif q, q\lif r \Entails p \lif rsource

What if you make U\Undefsource designated in Ł3\LogLuk[3]source?

Source definition named three valued R Mingle

The logic 3-valued R-Mingle RM3\LogRM[3]source is defined using the matrix:

  1. The standard propositional language L0\Lang L_0source with ⊥\lfalsesource, ¬\lnotsource, ∧\landsource, ∨\lorsource, →\lifsource.

  2. The set of truth values V={T,U,F}V = \{\True, \Undef, \False\}source.

  3. T\Truesource and U\Undefsource are designated, i.e., V+={T,U}V^+ = \{\True, \Undef\}source.

  4. Truth functions are the same as L ukasiewicz logic Ł3\LogLuk[3]source.

Exercise on the matrix named R Mingle

Which of the following relations hold in RM3\LogRM[3]source?

  1. p,p→q⊨qp, p \lif q \Entails qsource

  2. p∨q,¬p⊨qp \lor q, \lnot p \Entails qsource

  3. ¬p,p⊨q\lnot p, p \Entails qsource

  4. p⊨p∨qp \Entails p \lor qsource

Different truth tables can sometimes generate the same logic (entailment relation) just by changing the designated values. E.g., this happens if in Gödel logic we take V+={T,U}V^+ = \{\True, \Undef\}source instead of {T}\{\True\}source.

Designating true and U in Goedel logic gives classical logic

The matrix with V={F,U,T}V = \{\False, \Undef,\True\}source, V+={T,U}V^+=\{\True, \Undef\}source, and the truth functions of 33source-valued Gödel logic defines classical logic.

Proof

Exercise.

Exercise proving classical consequence after changing Goedel designation

Prove the proposition that designating true and U in Goedel logic gives classical consequence by showing that for the logic L\Log Lsource defined just like Gödel logic but with V+={T,U}V^+=\{\True,\Undef\}source, if Γ⊭LB\Gamma \Entails/[\Log L] !Bsource then Γ⊭CB\Gamma \Entails/[\LogCL] !Bsource. Use the ideas of the proposition that the logic of paradox has exactly the classical tautologies, except instead of proving properties (a) and (b), show that v¯G(A)=F\pValue v(!A)[\LogGod] = \Falsesource iff v′¯C(A)=F\pValue {v'}(!A)[\LogCL] = \Falsesource (and hence that v¯G(A)∈{T,U}\pValue v(!A)[\LogGod] \in \{\True,\Undef\}source iff v′¯C(A)=T\pValue {v'}(!A)[\LogCL] = \Truesource). Explain why this establishes the proposition.

Source disclosures