Belnap's four-valued logic

Belnaps four-valued logic (short:) is a logical system with four truth values, which enables paraconsistent reasoning. It was developed in 1975 by Nuel D. Belnap . Belnaps tetravalent logic used in contrast to classical logic four logical values: , , and . In this system, conclusions can also be drawn from classically logically inconsistent sets. ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle t\!\,}$ ${\displaystyle f\!\,}$ ${\displaystyle \top }$ ${\displaystyle \bot }$

Paraconsistent reasoning

A consequence operation is called paraconsistent if the entire logical language cannot be deduced from an inconsistent set of propositional formulas. Meaningful, logical conclusions from inconsistent formula sets are possible.

Let a propositional language with a signature be a set of formulas of this language. A consequence relation is called para consistent if there is a set of formulas from there, so not that ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \Sigma \!\,}$ ${\displaystyle \models _{p}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {L}}}$

${\displaystyle {\mathcal {F}}\models {\mathcal {L}}}$

applies.

Truth values

In contrast to classical logic , which only knows the truth values and , Belnaps four-valued logic is based on two further truth values and . expresses inconsistency, i.e. an excess of knowledge. however, describes the lack of knowledge, also referred to as incomplete . ${\displaystyle t}$ ${\displaystyle f}$ ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle \top }$ ${\displaystyle \bot }$

${\displaystyle \mathrm {FOUR} =\{t,f,\top ,\bot \}}$

Truth value	representation
${\displaystyle t\!\,}$	(1, 0)
${\displaystyle f\!\,}$	(0, 1)
${\displaystyle \top }$	(1, 1)
${\displaystyle \bot }$	(0, 0)

Analogous to classical logic, these values ​​are represented with the help of numbers.

Two comparison relations are defined on the basis of the four truth values.

${\displaystyle \leq _{t}}$

compares two values ​​regarding their truthfulness,

${\displaystyle \leq _{k}}$

compares the knowledge content.

Comparisons of two truth values ​​using these relations are defined by:

${\displaystyle (x_{1},y_{1})\leq _{t}(x_{2},y_{2})}$iff. and . ${\displaystyle x_{1}\leq x_{2}}$ ${\displaystyle y_{1}\geq y_{2}}$

${\displaystyle (x_{1},y_{1})\leq _{k}(x_{2},y_{2})}$iff. and . ${\displaystyle x_{1}\leq x_{2}}$ ${\displaystyle y_{1}\leq y_{2}}$

So is and . The values and are incomparable with regard to , are analogous and are incomparable with regard to . ${\displaystyle f\leq _{t}t}$ ${\displaystyle \bot \leq _{k}\top }$ ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle \leq _{t}}$ ${\displaystyle t\!\,}$ ${\displaystyle f\!\,}$ ${\displaystyle \leq _{k}}$

evaluation

The evaluation function is defined by ${\displaystyle \mathrm {I} }$

${\displaystyle \mathrm {I} :\Sigma \!\,\rightarrow \mathrm {FOUR} }$

and provides interpretations for atomic logical formulas.

Junctures

In addition to interpretations for atomic formulas, evaluations of the logical joiners , and , and for (strong implication ) are specified recursively . ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \neg \!\,}$ ${\displaystyle \supset }$

Let A and B be formulas.

• ${\displaystyle I(\neg {A})=\!\,\neg {I(A)}}$
• ${\displaystyle I(A\land B)=\!\,I(A)\land I(B)}$
• ${\displaystyle I(A\lor B)=\!\,I(A)\lor I(B)}$
• ${\displaystyle I(A\supset B)=\!\,I(A)\supset I(B)}$

and

• ${\displaystyle \neg {(x,y)}=\!\,(y,x)}$
• ${\displaystyle (x_{1},y_{1})\land (x_{2},y_{2})=(x_{1}\land x_{2},y_{1}\lor y_{2})}$
• ${\displaystyle (x_{1},y_{1})\lor (x_{2},y_{2})=(x_{1}\lor x_{2},y_{1}\land y_{2})}$
• ${\displaystyle (x_{1},y_{1})\supset (x_{2},y_{2})=(\neg {x_{1}}\lor x_{2},x_{1}\land y_{2})}$.

In addition, derived connectives are defined, similar to the propositional material implication:

• ${\displaystyle A\Rightarrow B\equiv \neg {A}\lor B}$
• ${\displaystyle A\rightarrow B\equiv (A\supset B)\land (\neg {B}\supset \neg {A})}$

With the help of the interpretation function , logical expressions in Belnap's four-valued logic can be evaluated by assigning a truth value to each atomic formula and interpreting the formulas recursively. ${\displaystyle I\!\,}$

Truth tables

negation

${\displaystyle \neg }$
${\displaystyle t\!\,}$	${\displaystyle f\!\,}$
${\displaystyle f\!\,}$	${\displaystyle t\!\,}$
${\displaystyle \top }$	${\displaystyle \top }$
${\displaystyle \bot }$	${\displaystyle \bot }$

conjunction

${\displaystyle \land }$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle f\!\,}$	${\displaystyle f\!\,}$	${\displaystyle f\!\,}$	${\displaystyle f\!\,}$	${\displaystyle f\!\,}$
${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle f\!\,}$
${\displaystyle \bot }$	${\displaystyle \bot }$	${\displaystyle f\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \bot }$

Disjunction

${\displaystyle \lor }$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$
${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle \bot }$
${\displaystyle \top }$	${\displaystyle t\!\,}$	${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle t\!\,}$
${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle \bot }$

Strong implication

${\displaystyle \supset }$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$
${\displaystyle \top }$	${\displaystyle \bot }$	${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$

Material implication

${\displaystyle \Rightarrow \!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$
${\displaystyle \top }$	${\displaystyle t\!\,}$	${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle t\!\,}$
${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle \bot }$

implication

${\displaystyle \rightarrow \!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \bot }$
${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle f\!\,}$	${\displaystyle f}$	${\displaystyle \bot }$
${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$
${\displaystyle \top }$	${\displaystyle t\!\,}$	${\displaystyle f}$	${\displaystyle \top }$	${\displaystyle \bot \!\,}$
${\displaystyle \bot }$	${\displaystyle t\!\,}$	${\displaystyle \bot }$	${\displaystyle \bot \!\,}$	${\displaystyle t}$

Fulfillment

Two values ​​from are interpreted as true and combined into a set of designated values: ${\displaystyle \mathrm {FOUR} }$

${\displaystyle {\mathcal {D}}=\{t,\top \}}$

An interpretation satisfies a formula , ${\displaystyle I\!\,}$ ${\displaystyle F\!\,}$

${\displaystyle I\models _{4}F}$,

if applies

${\displaystyle I(F)\in {\mathcal {D}}}$.

It is also said to be a model of . The set of all models of a set of propositional formulas is called. ${\displaystyle I\!\,}$ ${\displaystyle F\!\,}$ ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle Mod_{4}({\mathcal {F}})}$

Inference

As in classical propositional logic, an inference relation is defined by means of which new knowledge can be inferred from existing knowledge. ${\displaystyle \mathrm {FOUR} }$

Be , a lot of -formulae, or a formula. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A\!\,}$ ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle \mathrm {FOUR} }$

${\displaystyle F\models _{4}A}$

applies if every -Model of is also a -Model of , i.e. if ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle A\!\,}$

${\displaystyle Mod_{4}({\mathcal {F}})\subseteq A}$.

The consequence relation is monotonous , compact and paraconsistent . ${\displaystyle \models _{4}}$

properties

The logical system has similar properties to classical propositional logic. ${\displaystyle \mathrm {FOUR} }$

De Morgan's rule

${\displaystyle \neg ((x_{1},y_{1})\land (x_{2},y_{2}))=\neg (x_{1},x_{2})\lor \neg (x_{2},y_{2})}$

${\displaystyle \neg ((x_{1},y_{1})\lor (x_{2},y_{2}))=\neg (x_{1},x_{2})\land \neg (x_{2},y_{2})}$

cut

As in propositional logic:

${\displaystyle Mod_{4}(A\land B)=Mod_{4}(A)\cap Mod_{4}(B)}$

Tautologies

In no tautologies exist. In particular is ${\displaystyle \mathrm {FOUR} }$

${\displaystyle A\lor \neg {A}\!\,}$

no tautology.

Material implication

As defined in propositional logic can also be in the material implication ${\displaystyle \mathrm {FOUR} }$

${\displaystyle A\Rightarrow B\equiv B\lor \neg A}$

be used. However, it loses its strength and formula amount

${\displaystyle \{A,A\Rightarrow B\}\!\,}$

can be designated (true) even if B is not designated. The law of the excluded middle applies not so. The strong implication was introduced in to remedy this shortcoming. ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle \mathrm {FOUR} }$

Strong implication

There is a similar relationship between the strong implication and the inference relation as in propositional logic between and . ${\displaystyle \supset }$ ${\displaystyle \models _{4}}$ ${\displaystyle \Rightarrow \!\,}$ ${\displaystyle \models }$

Let be a set of formulas; , Formulas. The following applies: ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \mathrm {FOUR} }$

${\displaystyle {\mathcal {F}},A\models _{4}B}$ iff. ${\displaystyle F\models _{4}A\supset B}$

Examples

In the following the three atoms , and are used, which can be interpreted with the following meanings: ${\displaystyle F}$ ${\displaystyle P}$ ${\displaystyle V}$

atom	meaning
${\displaystyle F}$	can fly
${\displaystyle P}$	penguin
${\displaystyle V}$	bird

Paraconsistency

The formula

${\displaystyle \phi =P\land (P\Rightarrow V)\land (V\Rightarrow F)\land (P\Rightarrow \neg {F})}$

is inconsistent in classical logic.

In, however, there are interpretations with which is designated, i.e. ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle \mathrm {FOUR} }$ ${\displaystyle \phi \!\,}$

${\displaystyle I\models _{4}\phi }$

Examples of such assignments are:

${\displaystyle I_{1}(P)=t,I_{1}(V)=t,I_{1}(F)=\top }$

${\displaystyle I_{2}(P)=\top ,I_{2}(V)=\top ,I_{3}(F)=\top }$

Strong implication

With the help of material and strong implication, different types of inference can be modeled. The material implication models conclusions with exceptions, while the strong implication models knowledge without exception.

${\displaystyle {\mathcal {F}}=\{V,P,V\Rightarrow F,P\supset V,P\supset \neg {F}\}}$

The formula set has 6 models: ${\displaystyle \mathrm {FOUR} }$

model	F.	P	V
M1	${\displaystyle \top }$	${\displaystyle t\!\,}$	${\displaystyle \top }$
M2	${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle \top }$
M3	${\displaystyle f\!\,}$	${\displaystyle t\!\,}$	${\displaystyle \top }$
M4	${\displaystyle f\!\,}$	${\displaystyle \top }$	${\displaystyle \top }$
M5	${\displaystyle \top }$	${\displaystyle t\!\,}$	${\displaystyle t\!\,}$
M6	${\displaystyle \top }$	${\displaystyle \top }$	${\displaystyle t\!\,}$

literature

• ND Belnap: A useful four-valued logic . In: JM Dunn, G. Epstein (Eds.): Modern uses of multiple-valued logic . Reidel, Dordrecht 1977, pp. 8-37.
• S. Weber: Investigations in Belnap's Logic of Inconsistent and Unknown Information . (PDF; 1.1 MB) Dissertation, Faculty of Mathematics and Computer Science, University of Leipzig, 1998

Web links

• Gabriele Kern-Isberner: Paraconsistency . (PDF; 472 kB) In: Comonsense Reasoning 2008 .