Definition:Truth Table

From ProofWiki
Jump to navigation Jump to search

Definition

A truth table is a tabular array that represents the computation of a truth 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 set of truth values, usually $\set {0, 1}$ or $\set {\T, \F}$.


Characteristic Truth Tables

Let $\circledcirc$ be a logical connective.

The characteristic truth table for $\circledcirc$ is the truth table describing the truth function of $\circledcirc$:

$\begin{array}{|cc||c|} \hline p & q & p \circledcirc q \\ \hline \F & \F & x \\ \F & \T & x \\ \T & \F & x \\ \T & \T & x \\ \hline \end{array}$

where $x$ is replaced by either $\F$ or $\T$ as appropriate on each row.

The characteristic truth tables of the various logical connectives are listed below.


Logical Negation

The characteristic truth table of the negation operator $\neg p$ is as follows:

$\begin {array} {|c||c|} \hline p & \neg p \\ \hline \F & \T \\ \T & \F \\ \hline \end {array}$


Logical Conjunction

The characteristic truth table of the logical conjunction operator $p \land q$ is as follows:

$\begin{array}{|cc||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

The characteristic truth table of the logical disjunction operator $p \lor q$ is as follows:

$\begin{array}{|cc||c|} \hline p & q & p \lor q \\ \hline \F & \F & \F \\ \F & \T & \T \\ \T & \F & \T \\ \T & \T & \T \\ \hline \end{array}$


Biconditional

The characteristic truth table of the biconditional operator $p \iff q$ is as follows:

$\begin{array}{|cc||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

The characteristic truth table of the exclusive or operator $p \oplus q$ is as follows:

$\begin{array}{|cc||c|} \hline p & q & p \oplus q \\ \hline \F & \F & \F \\ \F & \T & \T \\ \T & \F & \T \\ \T & \T & \F \\ \hline \end{array}$


Conditional

The characteristic truth table of the conditional (implication) operator $p \implies q$ is as follows:

$\begin {array} {|cc||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 characteristic truth table of the logical NAND operator $p \uparrow q$ is as follows:

$\begin{array}{|cc||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 characteristic truth table of the logical NOR operator $p \downarrow q$ is as follows:

$\begin {array} {|cc||c|} \hline p & q & p \downarrow q \\ \hline \F & \F & \T \\ \F & \T & \F \\ \T & \F & \F \\ \T & \T & \F \\ \hline \end {array}$


Computing Larger Truth Tables

Let $P$ be a formula we want to compute the truth table of.


We will use Peirce's Law as an example:

$P := \paren {\paren {p \implies q} \implies p} \implies p$


For each boolean interpretation for the set of propositional variables, we write its truth value underneath:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & & \F & & \F & & \F \\ \end{array}$

In the above, we are using the boolean interpretation $v: \set {p, q} \to \set {\T, \F}$ given by:

\(\ds \map v p\) \(=\) \(\ds \F\)
\(\ds \map v q\) \(=\) \(\ds \F\)


Then we fill in the truth value of each of the WFFs on the parsing sequence of $P$, underneath its main connective:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & & \F & & \F & & \F \\ & & & \T & & & & & \\ & & & & & \F & & & \\ & & & & & & & \T & \\ \end{array}$

In the above, this has been done on separate lines, so as to clarify the sequence in which this is done for the example.


In practice we write it like this:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & \T & \F & \F & \F & \T & \F \\ \end{array}$


We repeat this for all other boolean interpretations:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & \T & \F & \F & \F & \T & \F \\ \F & \T & \F & \T & \T & \F & \F & \T & \F \\ \T & \F & \T & \F & \F & \T & \T & \T & \T \\ \T & \T & \T & \T & \T & \T & \T & \T & \T \\ \end{array}$


Structure

Truth tables are constructed of rows and columns.

Row

A row of a truth table is one of the horizontal lines that consists of instances of the symbols $T$ and $F$.

Each row contains the truth values of each of the boolean interpretations of the statement forms according to the propositional variables that comprise them.

There are as many rows in a truth table as there are combinations of $T$ and $F$ for all the propositional variables that constitute the statement forms.


Column

A row of a truth table is one of the vertical lines headed by a statement form presenting all the truth values that the statement form takes.

Each entry in the column corresponds to one specific combination of truth values taken by the propositional variables that the statement form comprises.


Matrix Presentation

A two-element truth table can be presented in matrix form:

$\begin{array}{c|cc} \implies & \T & \F \\ \hline \T & \T & \F \\ \F & \T & \T \\ \end{array}$$\qquad$$\begin{array}{c|cc} \land & \T & \F \\ \hline \T & \T & \F \\ \F & \F & \F \\ \end{array}$$\qquad$$\begin{array}{c|cc} \lor & \T & \F \\ \hline \T & \T & \T \\ \F & \T & \F \\ \end{array}$$\qquad$$\begin{array}{c|cc} \iff & \T & \F \\ \hline \T & \T & \F \\ \F & \F & \T \\ \end{array}$

that is, in the form of a Cayley table.

This, however, can be used only when the operation being displayed has two elements.


Truth Table Number

The truth table number of the truth table of a statement form is a string consisting of the truth values in numerical form of the main connective.

The order in which the truth table number is presented is usually in ascending or descending numerical order of the truth values of the simple statements contributing to that statement form, either:

Ascending order: $00, 01, 10, 11$, that is: $\F\F, \F\T, \T\F, \T\T$

or:

Descending order: $11, 10, 01, 00$, that is: $\T\T, \T\F, \F\T, \F\F$

Which format is being used needs to be specified.

Hence the truth table number can be found by reading either up or down the column holding the main connective in the truth table of the statement form.


Examples

Example: $p \implies \paren {q \lor r}$

The truth table for the WFF of propositional logic:

$p \implies \paren {q \lor r}$:

can be presented as:

$\begin{array}{c|c|c|c|c} p & q & r & q \lor r & p \implies \paren {q \lor r} \\ \hline \F & \F & \F & \F & \T \\ \F & \F & \T & \T & \T \\ \F & \T & \F & \T & \T \\ \F & \T & \T & \T & \T \\ \T & \F & \F & \F & \F \\ \T & \F & \T & \T & \T \\ \T & \T & \F & \T & \T \\ \T & \T & \T & \T & \T \\ \end{array}$


Example: $\paren {\lnot p} \land \paren {\lnot q}$

The truth table for the WFF of propositional logic:

$\paren {\lnot p} \land \paren {\lnot q}$:

can be presented as:

$\begin{array}{cc|c|cc} (\lnot & p) & \land & (\lnot & q) \\ \hline \T & \F & \T & \T & \F \\ \T & \F & \F & \F & \T \\ \F & \T & \F & \T & \F \\ \F & \T & \F & \F & \T \\ \end{array}$


Example: $\lnot \paren {\paren {p \implies q} \implies \paren {\lnot \paren {q \implies p} } }$

The truth table for the WFF of propositional logic:

$\lnot \paren {\paren {p \implies q} \implies \paren {\lnot \paren {q \implies p} } }$:

can be presented as:

$\begin{array}{c|ccc|c|cccc} \lnot & ((p & \implies & q) & \implies & (\lnot & (q & \implies & p))) \\ \hline \T & \F & \T & \F & \F & \F & \F & \T & \F \\ \F & \F & \T & \T & \T & \T & \T & \F & \F \\ \F & \T & \F & \F & \T & \F & \F & \T & \T \\ \T & \T & \T & \T & \F & \F & \T & \T & \T \\ \end{array}$


Also known as

Some sources hyphenate truth table as truth-table.

Some sources refer to this concept as a matrix, but a different meaning has evolved for that word in the context of linear algebra.


Also see

  • Results about truth tables can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Truth_Table&oldid=725399"