Count of Truth Functions

From ProofWiki
Jump to navigation Jump to search

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.

The result follows from Cardinality of Set of All Mappings.

$\blacksquare$


Sources