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 ≡.
Best Answer
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?)