4

I was wondering how might one go about solving the question: How many different last columns occur among all the truth tables with propositional variables p, q, r, s? (In other words, how many equivalence classes are there under the relation of logical equivalence?) Is the parentheses asking how many ways can pqrs be related via: and, or, not

Matemáticos Chibchas
  • 6,061
Lorenzo Alamillo
  • 41
  • You can get any last column you want. Taking all ands with well-chosen nots will give you just a single true in any given row of the last column. Then using or you can make any desired subset of the rows true and the others false. So if you have $n$ variables, there are $2^n$ possibilities for the last column. – almagest May 29 '16 at 05:03
  • An equivalence class partitions a Set. Is the set a collection of some kind of atomic sentences? Can you at least qualify this set? I think some sets would result in pardox. Edit: or is the set { $p, q, r, s$}atomic sentences? Seems like the answer may be a basic result of model theory. – marshal craft May 29 '16 at 05:14

1 Answers1

4

This question just asks, How many different Boolean-valued functions of 4 Boolean variables are there? Because $\land, \lor, \neg$ is a complete set of connectives, they can express every Boolean function.

The set of truth values is, let's say, $\{\mathsf{F}, \mathsf{T}\}$. Then the question asks: $$\text{ How many functions are there $\{\mathsf{F}, \mathsf{T}\}^4 \to \{\mathsf{F}, \mathsf{T}\}$ } ? $$ Because $\lvert \{\mathsf{F}, \mathsf{T}\} \rvert = 2$, the answer is $$\begin{align} \lvert \{\mathsf{F}, \mathsf{T}\}\rvert ^ {\lvert\{\mathsf{F}, \mathsf{T}\}^4 \rvert} &= 2 ^ {2^4} \\ &= 2 ^ {16} \\ &= 64 \sf K \qquad\text{($1\mathsf{K} = 1024$)}. \\ \end{align}$$ Looked at another way: a truth table with 4 variables will have $2^4 = 16$ rows, so the last column will be a 16-tuple of $0$s and $1$s, and there are $2^{16}$ possibilities. Furthermore, you can realize every possibility, using disjunctive normal form.

BrianO
  • 16,579
  • @marshalcraft Sure it does (account for contradictions): that's just the constantly-false function. In your comment to the original question and your comment here, you've really gone off the end talking about models, axioms, atomic sentences, paradox (?!), etc. All of this is distraction, and/or confused. There are just formulas, built up of $\land, \lor, \neg$, countably many propositional variables, and assignments of values to those variables. There aren't 4 "axioms", there are 4 variables. – BrianO May 29 '16 at 07:05
  • @marshalcraft You can construct infinitely many formulas using only $n$ variables, but there are only $2^{2^n}$ equivalence classes of formulas, $2^{2^n}$ Boolean functions of $n$ variables, and $2^{2^n}$ possible last columns of truth tables involving $n$ variables. – BrianO May 29 '16 at 07:07
  • Thanks for explaining that to me. I apologize. – marshal craft May 29 '16 at 07:30
  • @marshalcraft Not to worry, no apology needed. In any case, you're welcome :) – BrianO May 29 '16 at 08:59