Count of Rows of Truth Table

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $P$ be a WFF of propositional logic.

Suppose $\PP$ is of finite size such that it contains $n$ different letters.


Then a truth table constructed to express $P$ will contain $2^n$ rows.


Proof

In a truth table, one row is needed for each boolean interpretation of $P$.

Let $S$ be the set of different letters used in $P$.

The result then follows from applying Number of Boolean Interpretations for Finite Set of Variables to $S$.

$\blacksquare$


Sources