Count of Truth Functions

Theorem

There are $2^{\paren {2^k} }$ distinct truth functions on $k$ variables.

Proof

Let $f: \mathbb B^k \to \mathbb B$ be a truth function.

The domain of $f$ has $2^k$ elements, from Cardinality of Cartesian Product of Finite Sets.

The result follows from Cardinality of Set of All Mappings.

$\blacksquare$

Sources

• 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic (3rd ed.) ... (previous) ... (next): $\S 3.8$: The Total Number of Truth-Functional Expressions
• 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $6 \ \text{(ii)}$
• 1988: Alan G. Hamilton: Logic for Mathematicians (2nd ed.) ... (previous) ... (next): $\S 1$: Informal statement calculus: $\S 1.2$: Truth functions and truth tables
• 1993: M. Ben-Ari: Mathematical Logic for Computer Science ... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.1$: Boolean operators
• 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous) ... (next): $\S 2.4.1$