The textbook says that given $n$ atomic wff, there are $2^{2^n}$ truth functions. Is it correct to say that since the set of all the atomic wff is denumerable, there are $2^{2^{\aleph_0}}$ truth functions (that is, truth functions are uncountable)?

  • $\begingroup$ If you define "truth function" in a certain way, then yes. $\endgroup$
    – Karl
    Mar 2 at 6:53
  • $\begingroup$ The text book refers to a standard definition of truthfunction for two-valued propositional logic. $\endgroup$
    – Frank
    Mar 2 at 7:28

1 Answer 1


The set of all truth assignments can be identified with the set of all infinite sequences of $1$'s and $0$'s, since a truth assignment gives a truth value to a countable set of propositional variables.

This in turn can be identified with the set of all subsets of $\mathbf{N}$, since we can think of a sequence of $1$'s and $0$'s as a characteristic function of natural numbers, i.e. a number $n$ is in the subset iff the value of the sequence at the $n$-th place is $1$.

The set of subsets of natural numbers has cardinality $2^{\aleph_0}$.

  • $\begingroup$ If the set of truth functions is non denunerable, and the set of formulas of propositional logic is denunerable, then are there truth functions that cannot be expressed in propositional logic? $\endgroup$
    – Frank
    Mar 4 at 22:57
  • $\begingroup$ What can be expressed in a logic can be found through it's semantics. So, since propositional logic has Boolean algebra semantics, expressible are any terms involving the Boolean operations. Asking whether truth functions can be expressed in propositional logic is easily answered with no, since propositional logic cannot express functions. $\endgroup$
    – Jason
    Mar 6 at 6:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .