Truth table

Animation for creating a truth table

A truth table or truth table , also called a truth value table or truth matrix, is a tabular listing of the truth value progression of a logical statement .

The truth table shows for all possible assignments of a finite number (often two) truth values to the sub-statements that cannot be further broken down from a logical point of view, from which the overall statement is composed, which truth value the overall statement assumes under the respective assignment. The truth table is used to represent or define truth value functions or Boolean functions and to carry out simple propositional proofs. For example, truth tables are used to determine the meaning of joiners .

Representation of Boolean functions

For the two-valued case, the truth value “true” is hereinafter referred to as and “false” as . ${\ displaystyle w}$ ${\ displaystyle f}$

For polyvalent cases often are numerical values ranging from to be used (in the trivalent case z. B. the values , and , in the pentavalent case, the values , , , and ). In the multi-valued case, one does not speak of truth values, but of quasi-truth values or pseudo-truth values. ${\ displaystyle 0}$ ${\ displaystyle 1}$ ${\ displaystyle 0}$ ${\ displaystyle {\ tfrac {1} {2}} = 0 {,} 5}$ ${\ displaystyle 1}$ ${\ displaystyle 0}$ ${\ displaystyle {\ tfrac {1} {4}} = 0 {,} 25}$ ${\ displaystyle {\ tfrac {1} {2}} = 0 {,} 5}$ ${\ displaystyle {\ tfrac {3} {4}} = 0 {,} 75}$ ${\ displaystyle 1}$

In general, for m-valued logic, i. H. for a logic with finitely many truth values, the number of which is m, n-place truth-functional connectors or Boolean functions. For the two-valued propositional logic there are therefore single-digit connectors and two-digit connectors. Even for the three-value propositional logic there are single-digit and two-digit connectives. ${\ displaystyle m ^ {m ^ {n}}}$ ${\ displaystyle 2 ^ {2 ^ {1}} = 4}$ ${\ displaystyle 2 ^ {2 ^ {2}} = 16}$ ${\ displaystyle 3 ^ {3 ^ {1}} = 27}$ ${\ displaystyle 3 ^ {3 ^ {2}} = 19 \, 683}$

negation
${\ displaystyle a}$	${\ displaystyle \ lnot a}$
w	f
f	w

The adjacent truth table, which shows the result of applying the negation to the statement in classical propositional logic, serves as an example for a one-digit truth value function of a two-value logic .

{\ displaystyle a}

The following table shows for each truth value of statements and the result of several divalent links to: ${\ displaystyle a}$ ${\ displaystyle b}$

Occupancy		conjunction	Disjunction	material implication	Equivalence biconditional
${\ displaystyle a}$	${\ displaystyle b}$	AND	OR	Conditional	XNOR
w	w	w	w	w	w
w	f	f	w	f	f
f	w	f	w	w	f
f	f	f	f	w	w

The following two-valued functions named after Henry Maurice Sheffer and Charles Sanders Peirce have a special position (see functional completeness and Sheffer's stroke ), to which the NAND and NOR gates correspond:

${\ displaystyle a}$	${\ displaystyle b}$	Sheffer's Stroke (NAND, ) ${\ displaystyle \|}$	Peirce arrow (NOR, ) ${\ displaystyle \ downarrow}$
w	w	f	f
w	f	w	f
f	w	w	f
f	f	w	w

In a three-value logic, 19,683 two-digit links are possible. Two of them are shown in the following table: The conjunction from the logical language Ł3 by Jan Łukasiewicz (1920) and the conjunction from the calculus B3 by Dmitrij Anatol'evič Bočvar (1938).

Occupancy		conjunction
${\ displaystyle a}$	${\ displaystyle b}$	in £ 3	in B3
1	1	1	1
1	½	½	½
1	0	0	0
½	1	½	½
½	½	½	½
½	0	0	½
0	1	0	0
0	½	0	½
0	0	0	0

A four-valued logic has up to two possible two-digit operators. Here as an example the truth table for the conditional or the material implication in the logical system G4 by Kurt Gödel (1932). ${\ displaystyle 4 ^ {4 ^ {2}} = 4 \, 294 \, 967 \, 296}$

Occupancy		Conditional
${\ displaystyle a}$	${\ displaystyle b}$	in G4
1	1	1
1	² ⁄ ₃	² ⁄ ₃
1	¹ ⁄ ₃	¹ ⁄ ₃
1	0	0
² ⁄ ₃	1	1
² ⁄ ₃	² ⁄ ₃	1
² ⁄ ₃	¹ ⁄ ₃	¹ ⁄ ₃
² ⁄ ₃	0	0
¹ ⁄ ₃	1	1
¹ ⁄ ₃	² ⁄ ₃	1
¹ ⁄ ₃	¹ ⁄ ₃	1
¹ ⁄ ₃	0	0
0	1	1
0	² ⁄ ₃	1
0	¹ ⁄ ₃	1
0	0	1

Evidence and decision-making process

Truth tables are suitable for carrying out simple propositional proofs on the semantic model level, especially for the validity of fundamental laws on which logical proof procedures are based. For example, the logical equivalence of the 3rd and 4th columns in the following truth tables shows the validity of De Morgan's laws :

{\ displaystyle \ lnot (a \ land b) = (\ lnot a) \ lor (\ lnot b)}

${\ displaystyle a}$	${\ displaystyle b}$	${\ displaystyle \ lnot (a \ land b)}$	${\ displaystyle (\ lnot a) \ lor (\ lnot b)}$
w	w	f	f
w	f	w	w
f	w	w	w
f	f	w	w

{\ displaystyle \ lnot (a \ lor b) = (\ lnot a) \ land (\ lnot b)}

${\ displaystyle a}$	${\ displaystyle b}$	${\ displaystyle \ lnot (a \ lor b)}$	${\ displaystyle (\ lnot a) \ land (\ lnot b)}$
w	w	f	f
w	f	f	f
f	w	f	f
f	f	w	w

In practice, however, this type of reasoning is only suitable for statements with a small number of statement variables, since the size grows exponentially with the number of variables.

For propositional logic with a finite number of truth values and the classic concept of inference (see Classical Logic ), truth tables are a decision-making process for many important questions, i.e. a process with which the respective question can be mechanically decided for each statement in a finite time. With the help of truth tables the question can be decided whether a given statement is satisfiable, unsatisfiable or tautological (see satisfiability problem of propositional logic ); you can also decide whether an argument is valid or invalid.

Transformation into other forms of representation

For further processing or simplification, the content of a truth table can be converted into other, equivalent representations, for example into a Karnaugh-Veitch diagram .

An alternative: Truth value analysis according to Quine

In many cases, truth tables are a rational and easy-to-use method of truth value analysis. However, they have the disadvantage that you always have to go through all cases. The number of cases increases with the number of variables (sentence letters) in proportion . With 2 variables there are 4 cases, with 3 variables 8 cases, with 4 variables 16 cases, etc. With many variables, the truth value analysis using truth tables can be quite time-consuming. ${\ displaystyle 2 ^ {n}}$

That is why Quine proposes an alternative form of truth value analysis in his book Grundzüge der Logic . On page 54, Quine gives the following example with three variables or sentence letters (P, Q and R):

(P ∧ Q) ∨ (¬P ∧ ¬R) → (Q ↔ R)

(w ∧ Q) ∨ (f ∧ ¬R) → (Q ↔ R)

(f ∧ Q) ∨ (w ∧ ¬R) → (Q ↔ R)

Q ∨ (f ∧ ¬R) → (Q ↔ R)

f ∨ (w ∧ ¬R) → (Q ↔ R)

(Q ∨ f) → (Q ↔ R)

(w ∧ ¬R) → (Q ↔ R)

Q → (Q ↔ R)

¬R → (Q ↔ R)

w → (w ↔ R)

f → (f ↔ R)

f → (Q ↔ w)

w → (Q ↔ f)

w ↔ R

w

Q ↔ f

R.

¬Q

w

f

w

The example term (P ∧ Q) ∨ (¬P ∧ ¬R) → (Q ↔ R) is wrong in two cases: for P / w | Q / w | R / f and for P / f | Q / w | R / f. The truth table looks like this:

P	Q	R.	(P	∧	Q)	∨	(¬P	∧	¬R)	→	(Q	↔	R)
w	w	w	w	w	w	w	f	f	f	w	w	w	w
w	w	f	w	w	w	w	f	f	w	f	w	f	f
w	f	w	w	f	f	f	f	f	f	w	f	f	w
w	f	f	w	f	f	f	f	f	w	w	f	w	f
f	w	w	f	f	w	f	w	f	f	w	w	w	w
f	w	f	f	f	w	w	w	w	w	f	w	f	f
f	f	w	f	f	f	f	w	f	f	w	f	f	w
f	f	f	f	f	f	w	w	w	w	w	f	w	f

A simpler example is the definition of the implication:

(A → B) ↔ (¬A ∨ B)

The truth table looks like this:

A.	B.	(A	→	B)	↔	(¬A	∨	B)
w	w	w	w	w	w	f	w	w
w	f	w	f	f	w	f	f	f
f	w	f	w	w	w	w	w	w
f	f	f	w	f	w	w	w	f

The Quine truth value analysis in this example looks like this:

(A → B) ↔ (¬A ∨ B)

(w → B) ↔ (f ∨ B)

(f → B) ↔ (w ∨ B)

(w → w) ↔ (f ∨ w)

(w → f) ↔ (f ∨ f)

(w ↔ w)

(w → w)

(f ↔ f)

w

In the method of truth value analysis proposed by Quine, the variables or sentence letters are gradually replaced by their truth values. Case distinctions are then made line by line so that a tree-like structure is created. In both examples, that of Quine and the definition of the implication, it can also be seen that not all cases have to be gone through, which can be an advantage over truth tables for many variables. With both methods, the cases in which a term becomes true or false can be determined exactly. Therefore, both methods do the same thing and are therefore equivalent.

About history

If a truth table is understood to mean the homomorphic assignment of truth values to the atomic statements occurring in a statement , then the truth table goes back to Philo of Megara , who defined the truth function for the material implication in this way in the 4th century BC . Truth tables were also used extensively in this sense in the stoic logic coined by Chrysippus von Soloi .

In modern logic, George Boole used truth tables in 1847 under the name “modules of a function” for the semantic decidability of logical terms (functions). Gottlob Frege and Charles Sanders Peirce later also used this decision-making process, with Peirce emphasizing the purpose of determining tautologies more clearly. Truth tables in the literal sense as tables were not introduced until 1921 by Emil Leon Post and Ludwig Wittgenstein ; their influence has made truth tables commonplace as a method of deciding on tautologies.

literature

Martha Kneale , William Kneale : The Development of Logic . Clarendon Press, 1962, ISBN 0-19-824773-7 (English, history).

Web links

Wikibooks: Math for Non-Freaks: Truth Table - Learning and Teaching Materials

PHP script for outputting truth tables (open source)
Truth table trainer in JavaScript

Individual evidence

↑ Quine, Willard Van Orman: Principles of Logic . 6th edition. Suhrkamp, Frankfurt am Main 1988, ISBN 3-518-27665-4 , pp. 49–56 (§5 truth value analysis).
↑ " The device of tabulation was not introduced until recently, but the idea of truth-functional dependence was obviously quite clear to Philo. ”(Martha Kneale, William Kneale : The Development of Logic . Clarendon Press, 1962, ISBN 0-19-824773-7 , pp. 130 (in English). ); in this sense also Bocheński "based on antiquity" (Bocheński: Formal Logic . 2nd edition. 1962, p. 384 ff . )
↑ “ The Stoics gave truth-functional definitions of all the more important propositional connectives […] ” ( Benson Mates : Stoic Logic (= University of California Publications in Philosophy . No. 26 ). University of California Press, Berkeley 1953, ISBN 0-520-02368-4 , pp. 42 (English, ISBN of 1973 reprint). )
^ Boole: The Mathematical Analysis of Logic . 1847, p. 60 ff .
^ Emil Leon Post: Introduction to a General Theory of Elementary Propositions . In: American Journal of Mathematics . tape 43 , 1921, pp. 163-185 .
↑ Ludwig Wittgenstein: Tractatus Logico-Philosophicus . 1921 (section 4.31).

[1] Quine, Willard Van Orman: Principles of Logic . 6th edition. Suhrkamp, Frankfurt am Main 1988, ISBN 3-518-27665-4 , pp. 49–56 (§5 truth value analysis).

[2] " The device of tabulation was not introduced until recently, but the idea of truth-functional dependence was obviously quite clear to Philo. ”(Martha Kneale, William Kneale : The Development of Logic . Clarendon Press, 1962, ISBN 0-19-824773-7 , pp. 130 (in English). ); in this sense also Bocheński "based on antiquity" (Bocheński: Formal Logic . 2nd edition. 1962, p. 384 ff . )

[3] “ The Stoics gave truth-functional definitions of all the more important propositional connectives […] ” ( Benson Mates : Stoic Logic (= University of California Publications in Philosophy . No. 26 ). University of California Press, Berkeley 1953, ISBN 0-520-02368-4 , pp. 42 (English, ISBN of 1973 reprint). )

[4] Boole: The Mathematical Analysis of Logic . 1847, p. 60 ff .

[5] Emil Leon Post: Introduction to a General Theory of Elementary Propositions . In: American Journal of Mathematics . tape 43 , 1921, pp. 163-185 .

[6] Ludwig Wittgenstein: Tractatus Logico-Philosophicus . 1921 (section 4.31).

P	Q	R.	(P	∧	Q)	∨	(¬P	∧	¬R)	→	(Q	↔	R)
w	w	w	w	w	w	w	f	f	f	w	w	w	w
w	w	f	w	w	w	w	f	f	w	f	w	f	f
w	f	w	w	f	f	f	f	f	f	w	f	f	w
w	f	f	w	f	f	f	f	f	w	w	f	w	f
f	w	w	f	f	w	f	w	f	f	w	w	w	w
f	w	f	f	f	w	w	w	w	w	f	w	f	f
f	f	w	f	f	f	f	w	f	f	w	f	f	w
f	f	f	f	f	f	w	w	w	w	w	f	w	f

P	Q	R.	(P	∧	Q)	∨	(¬P	∧	¬R)	→	(Q	↔	R)
w	w	w	w	w	w	w	f	f	f	w	w	w	w
w	w	f	w	w	w	w	f	f	w	f	w	f	f
w	f	w	w	f	f	f	f	f	f	w	f	f	w
w	f	f	w	f	f	f	f	f	w	w	f	w	f
f	w	w	f	f	w	f	w	f	f	w	w	w	w
f	w	f	f	f	w	w	w	w	w	f	w	f	f
f	f	w	f	f	f	f	w	f	f	w	f	f	w
f	f	f	f	f	f	w	w	w	w	w	f	w	f

P	Q	R.	(P	∧	Q)	∨	(¬P	∧	¬R)	→	(Q	↔	R)
w	w	w	w	w	w	w	f	f	f	w	w	w	w
w	w	f	w	w	w	w	f	f	w	f	w	f	f
w	f	w	w	f	f	f	f	f	f	w	f	f	w
w	f	f	w	f	f	f	f	f	w	w	f	w	f
f	w	w	f	f	w	f	w	f	f	w	w	w	w
f	w	f	f	f	w	w	w	w	w	f	w	f	f
f	f	w	f	f	f	f	w	f	f	w	f	f	w
f	f	f	f	f	f	w	w	w	w	w	f	w	f