Truth Table

logic

Definition

Truth Table

A truth table evaluates a formula under all interpretations.

Properties

Completeness

Truth tables are complete: they decide satisfiability, validity, and equivalence by exhaustive evaluation.

They are, however, exponential in the number of atoms.

Compact

Definition

Compact Truth Table

A compact truth table is a truth table method that tests a single target combination of truth values instead of enumerating all $2^n$ rows for $n$ atoms.

The target combination is the one the property rules out: all premises true and the conclusion false to test validity, the formula false to test whether it is a tautology. The method assigns the target values and propagates the values the connectives force, so only the atoms needed for that combination receive values.

Link to original

Example

Running Example

Consider the formula

$$\neg ((p\to q)\wedge (p\wedge q\to r)\to (p\to r))$$

A truth table shows that it is unsatisfiable.