Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

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. $\land$ (AND), $\lnot$ (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, $A$ and $B$ , and the logical operator "AND" ( $\land$ ), signifying the conjunction "A and B" or $A \land B$ . In common English, if both A and B are true, then the conjunction " $A \land B$ " is true; under all other possible assignments of truth values to $A \land B$ , the conjunction is false. This relationship is defined as follows:

$A$	$B$	$A \land B$
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 ( $\lnot$ ) relationship is defined as follows:

$A$	$\lnot A$
F	T
T	F

The OR ( $\lor$ ) relationship is defined as follows:

$A$	$B$	$A \lor B$
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 $\lnot ( A \land B )$ , is depicted as follows:

$A$	$B$	$A \land B$	$\lnot ( A \land B )$
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 $\lnot A \land \lnot B$ is:

$A$	$B$	$\lnot A$	$\lnot B$	$A \land B$	$\lnot ( \lnot A \lor \lnot B )$
F	F	T	T	F	F
F	T	T	F	F	F
T	F	F	T	F	F
T	T	F	F	T	T

Since the enumeration of all possible truth-values for $A$ and $B$ yields the same truth-value under both $A \land B$ and $\lnot (\lnot A \lor \land B)$ , the two are logically equivalent, and may be substituted for each other. This equivalence is one of DeMorgan's Laws.