[Math] Equivalence classes in the logical equivalence on some finite set of propositional formulas

equivalence-relationslogicpropositional-calculus

I'm having trouble understanding the following problem:

Let $S_n$ be the set of all formulas that can be built up with the
atoms $\{A_1,…,A_n\}$. How many equivalence classes does the
logical equivalence $\equiv$ on the set $S_n$ have?

I know what an equivalence relation and equivalence classes are. However, I can't figure out what 'a logical equivalence on a set of propositional formulas' means.

Does it mean that some formulas $F$ and $G$ from $S_n$ are logically equivalent, that is $F\equiv G$? Then how can we count the number of equivalence classes?

Best Answer

HINT: Your last paragraph suggests that you do have the right idea about what is wanted. Two propositional formulas are logically equivalent if and only if they have the same truth table. How many different truth tables are possible for a set of $n$ atoms? Each one will represent a whole equivalence class of logically equivalent formulas.