I was given the following question for homework:

Let P denote the set of all compound propositions involving the simple/atomic propositions p, q, and r and the logical connectives ∨, ∧, and ¬ (complementation). (Included in P are the tautology proposition true and the contradiction proposition false.) Define a binary relation R on P by: s R t if and only if s ≡ t, where ≡ denotes the logical equivalence in propositional logic.

How many equivalence classes of R are there? [ For every element p ∈ P, the equivalence class (of the equivalence relation R on P) containing p, denoted by [p]R, is the set {t ∈ P | t R p} — the set of all elements in P that are related to p under R. The index of an equivalence relation is the number of its equivalence classes. ]

Currently I'm completely stumped as we only talked about relations for around 45 minutes in class and I've never had formal teaching from a previous class (the same professor is in charge of this class as well as the Discrete Math class where he was suppose to teach this material).

From the notes I've taken, I gather that I'm supposed to be able to define the amount by putting a number into [p]R and seeing if it has a relation, and if so adding one to the total amount. So my best educated guess would be infinite since there are infinite possibilities for ≡.


No, the number of equivalence classes is finite, because there are only finitely many propositional variables, namely $p,q,r$. Any propositional formula in $P$ represents (or induces) a truth function — a function from $n$ tuples of truth values to truth values. The truth table of a formula defines this truth function. The formulas of $P$ define 3-ary truth functions.

Two formulas are equivalent iff their corresponding truth functions (truth tables) are the same. Furthermore, every possible truth table is represented by some formula: consider disjunctive normal form (DNF).

So, how many truth tables are there involving 3 variables? (Can you take it from here?)

  • $\begingroup$ I kind of glanced over the whole p,q,r and focused more on the bit of information in the brackets, thanks for clearing it up for me! $\endgroup$ Jan 26 '16 at 6:29
  • $\begingroup$ You're welcome, & thank you. $\endgroup$
    – BrianO
    Jan 26 '16 at 6:36

Hint: in this example, you can test to see if two propositions are equivalent by computing their truth tables. If the final answers are identical (intermediate working being irrelevant), then they are equivalent; if the final answers are different, they are not.

So the question is in effect the same as asking: how many possible final answers are there for a truth table in three variables?

See if you can now answer the question.

  • $\begingroup$ One might also want to demonstrate that every possible truth table is realizable by some proposition. That is, given a truth table $T$, show there is a proposition whose truth table is $T$. $\endgroup$ Jan 25 '16 at 4:18
  • 1
    $\begingroup$ @AustinMohr well... that's really part of counting possible truth tables - if it's not realisable then it's not possible. I agree that there is work to be done here beyond just a naive counting argument. I was only giving a hint, not a complete solution. $\endgroup$
    – David
    Jan 25 '16 at 4:21
  • $\begingroup$ Consider $ E(p)=\{p,\neg p, T, F\}.$ Show that if $a , b \in E(p)$ then $a\lor b$ and $a\land b$ are equiv to members of $E(p).$ And that $a$ is equiv to a member of $E(p)$ iff $\neg a$ is also. Now if $s$ is not equiv to a member of $E(p)$, take such an $s$ with the least number of symbols. Then $s$ is not $\neg t.$ If $s$ is $t\lor u,$ or if $s$ is $t\land u$, then $t$ and $u$ cannot both be equiv to members of $E(p)$ contrary to the minimal length of $s$ . So $s$ is atomic & not equal to $p$. Suppose $s=q$. Now consider what $E(p,q)$ should be. $\endgroup$ Jan 25 '16 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.