Number of Boolean Interpretations for Finite Set of Variables

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\PP_0$ be the vocabulary of language of propositional logic.

Let $S \subseteq \PP_0$ be a finite set of $n$ letters from $\PP_0$.


Then there are $2^n$ different partial boolean interpretations for $S$.


Proof

A partial boolean interpretation for $S$ is a mapping from $S$ to the set of truth values $\set {T, F}$.

By Cardinality of Set of All Mappings, the total number of mappings from $S$ to $T$ is:

$\card {T^S} = \card T^{\card S}$

The result follows directly.

$\blacksquare$


Sources