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 evaluates only the atoms needed for the current branch of the evaluation tree.

It reduces the amount of work compared to a full truth table.

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.