Truth table
|
|
Truth tables are a type of mathematical table used in logic to determine whether an expression is true or valid. (Expressions may be arguments; i.e., a conjunction of expressions, each conjunct of which is a premise with the last being the conclusion.)
Truth tables derive from the work of Gottlob Frege, Charles Peirce and others from about the 1880s. They came to their present form in 1922 through the work of Emil Post and Ludwig Wittgenstein. Wittgenstein's Tractatus Logico-Philosophicus uses them to place truth functions in a series. The wide influence of this work led to the spread of the use of truth tables.
Truth tables are used to compute the values of truth-functional expressions (i.e., it is a decision procedure). A truth-functional expression is either atomic (i.e., a propositional variable (or placeholder) or a propositional function — e.g. Px) or built up from atomic formulas from logical operators (i.e. <math>\land<math> (AND), <math>\lnot<math> (NOT) — e.g. Fx & Gx).
The column headings on a truth table show (i) the propositional functions and/or variables, and (ii) the truth-functional expression built up from those propositional functions or variables and operators. The rows show each possible valuation of T or F assignments to (i) and (ii). In other words, each row is a distinct interpretation of (i) and (ii).
Truth tables for classical (i.e., bivalent) logic are limited to Boolean logic systems where only two truth values are possible, true or false, usually denoted simply T and F in the tables (as remarked above).
For example, take two propositional variables, <math>A<math> and <math>B<math>, and the logical operator "AND" (<math>\land<math>), signifying the conjunction "A and B" or <math>A \land B<math>. In common English, if both A and B are true, then the conjunction "<math>A \land B<math>" is true; under all other possible assignments of truth values to <math>A \land B<math>, the conjunction is false. This relationship is defined as follows:
| <math>A<math> | <math>B<math> | <math>A \land B<math> |
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
In a boolean logic system, all the operators can be explicitly defined this way. For example, the NOT (<math>\lnot<math>) relationship is defined as follows:
| <math>A<math> | <math>\lnot A<math> |
| F | T |
| T | F |
The OR (<math>\lor<math>) relationship is defined as follows:
| <math>A<math> | <math>B<math> | <math>A \lor B<math> |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Compound expressions can be constructed, using parenthesis to denote precedence. The negation of conjunction <math>\lnot ( A \land B )<math>, is depicted as follows:
| <math>A<math> | <math>B<math> | <math>A \land B<math> | <math>\lnot ( A \land B )<math> |
| F | F | F | T |
| F | T | F | T |
| T | F | F | T |
| T | T | T | F |
Truth tables can be used to prove logical equivalence. The truth table for the disjunction of <math>\lnot A \lor \lnot B<math> is:
| <math>A<math> | <math>B<math> | <math>\lnot A<math> | <math>\lnot B<math> | <math> \lnot A \lor \lnot B <math> |
| F | F | T | T | T |
| F | T | T | F | T |
| T | F | F | T | T |
| T | T | F | F | F |
Comparing the above two truth tables, since the enumeration of all possible truth-values for <math>A<math> and <math>B<math> yields the same truth-value under both <math>\lnot (A \land B)<math> and <math>\lnot A \lor \lnot B<math>, the two are logically equivalent, and may be substituted for each other. This equivalence is one of DeMorgan's Laws.
Here is a truth table giving definitions of the most commonly used 5 of the 16 possible truth functions of 2 binary variables (P,Q are thus boolean variables):
| <math>P<math> | <math>Q<math> | <math>P \land Q<math> | <math>P \lor Q<math> | <math>P \oplus Q<math> | <math>P \rightarrow Q<math> | <math>P \leftrightarrow Q<math> |
| F | F | F | F | F | T | T |
| F | T | F | T | T | T | F |
| T | F | F | T | T | F | F |
| T | T | T | T | F | T | T |
Key:
- T = true, F = false
- <math>\land<math> = AND (logical conjunction)
- <math>\lor<math> = OR (logical disjunction)
- <math>\oplus<math> = XOR (exclusive disjunction)
- <math>\rightarrow<math> = conditional or "if-then"
- <math>\leftrightarrow<math> = biconditional or "if-and-only-if"
Johnston diagrams, similar to Venn diagrams and Euler diagrams, provide a way of visualizing truth tables. An interactive Johnston diagram illustrating truth tables is at LogicTutorial.com (http://logictutorial.com)
See also
es:Tabla de la verdad fr:Table de vérité nl:Waarheidstabel sv:Sanningstabell