Definition:Truth Table
Contents |
Definition
A truth table is a tabular array that represents the computation of a boolean function, that is, a function of the form:
- $f : \mathbb B^k \to \mathbb B$
where:
- $k$ is a non-negative integer
- $\mathbb B$ is a boolean domain, usually $\left\{{0, 1}\right\}$ or $\left\{{T, F}\right\}$.
Logical negation
Logical negation is an operation on one logical value, typically the value of a proposition, that produces:
The truth table of $\mathsf{NOT}\ p$ (also written $\neg p$ or $\sim p\!$) is as follows:
- $\begin{array}{|c||c|} \hline p & \neg p \\ \hline F & T \\ T & F \\ \hline \end{array}$
Logical conjunction
Logical conjunction is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both its operands are true.
The truth table of $p\ \mathsf{AND}\ q$ (also written $p \land q$, $p \ \And \ q$ or $p \cdot q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \land q \\ \hline F & F & F \\ F & T & F \\ T & F & F \\ T & T & T \\ \hline \end{array}$
Logical disjunction
Logical disjunction, also called logical alternation, is an operation on two logical values, typically the values of two propositions, that produces a value of false if and only if both its operands are false.
The truth table of $p\ \mathsf{OR}\ q$ (also written $p \lor q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \lor q \\ \hline F & F & F \\ F & T & T \\ T & F & T \\ T & T & T \\ \hline \end{array}$
Logical equality
Logical equality is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both operands are false or both operands are true.
The truth table of $p\ \mathsf{EQ}\ q$ (also written $p = q$, $p \iff q$ or $p \equiv q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \iff q \\ \hline F & F & T \\ F & T & F \\ T & F & F \\ T & T & T \\ \hline \end{array}$
Exclusive disjunction
Exclusive disjunction, also known as logical inequality or symmetric difference, is an operation on two logical values, typically the values of two propositions, that produces a value of true just in case exactly one of its operands is true.
The truth table of $p\ \mathsf{XOR}\ q$ (also written $p + q$, $p \oplus q$ or $p \neq q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \oplus q \\ \hline F & F & F \\ F & T & T \\ T & F & T \\ T & T & F \\ \hline \end{array}$
The following equivalents can then be deduced:
| \(\displaystyle \) | \(\displaystyle p \oplus q\) | \(\dashv \vdash\) | \(\displaystyle (p \land \neg q) \lor (\neg p \land q)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\dashv \vdash\) | \(\displaystyle (p \lor q) \land (\neg p \lor \neg q)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\dashv \vdash\) | \(\displaystyle (p \lor q) \land \neg (p \land q)\) | \(\displaystyle \) |
Conditional
The conditional is associated with an operation on two logical values that produces a value of false if and only if the first operand is true and the second operand is false.
The truth table associated with the material conditional (symbolized as $p \implies q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \implies q \\ \hline F & F & T \\ F & T & T \\ T & F & F \\ T & T & T \\ \hline \end{array}$
Logical NAND
The logical NAND is a logical operation on two logical values, typically the values of two propositions, that produces a value of true if and only if at least one of its operands is false. In other words, it produces a value of false if and only if both of its operands are true.
The truth table of $p\ \mathsf{NAND}\ q$ (also written $p~|~q$, $p \uparrow q$ or $p \bar \curlywedge q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \uparrow q \\ \hline F & F & T \\ F & T & T \\ T & F & T \\ T & T & F \\ \hline \end{array}$
Logical NOR
The logical NOR is a logical operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both of its operands are false. In other words, it produces a value of false if and only if at least one of its operands is true.
The truth table of $p\ \mathsf{NOR}\ q$ (also written $p \curlywedge q$ or $p \downarrow q$) is as follows:
- $\begin{array}{|cc||c|c|} \hline p & q & p \downarrow q \\ \hline F & F & T \\ F & T & F \\ T & F & F \\ T & T & F \\ \hline \end{array}$
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 6$
- Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$
- D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.3$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.6$
