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 substatements 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 twovalued case, the truth value “true” is hereinafter referred to as and “false” as .
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 multivalued case, one does not speak of truth values, but of quasitruth values or pseudotruth values.
In general, for mvalued logic, i. H. for a logic with finitely many truth values, the number of which is m, nplace truthfunctional connectors or Boolean functions. For the twovalued propositional logic there are therefore singledigit connectors and twodigit connectors. Even for the threevalue propositional logic there are singledigit and twodigit connectives.

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 onedigit truth value function of a twovalue logic . 
The following table shows for each truth value of statements and the result of several divalent links to:

The following twovalued 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:

In a threevalue logic, 19,683 twodigit 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).

A fourvalued logic has up to two possible twodigit 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).

Evidence and decisionmaking 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 :


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 decisionmaking 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 KarnaughVeitch diagram .
An alternative: Truth value analysis according to Quine
In many cases, truth tables are a rational and easytouse 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 timeconsuming.
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):

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:

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 treelike 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 decisionmaking 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 0198247737 (English, history).
Web links
 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 3518276654 , pp. 49–56 (§5 truth value analysis).
 ↑ " The device of tabulation was not introduced until recently, but the idea of truthfunctional dependence was obviously quite clear to Philo. ”(Martha Kneale, William Kneale : The Development of Logic . Clarendon Press, 1962, ISBN 0198247737 , 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 truthfunctional 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 0520023684 , 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. 163185 .
 ↑ Ludwig Wittgenstein: Tractatus LogicoPhilosophicus . 1921 (section 4.31).