Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi I am stuck on the following question :

How many non-equivalent formulas that use propositions are there?

I'm not quite sure how to find the non-equivalent formulas here, and could someone also explain why the answer is so?

Any help would be really appreciated

share|cite|improve this question
Define "formula". – Gerry Myerson Oct 2 '12 at 5:56

Two formulas are equivalent if and only if they have the same truth table. And for any conceivable truth table, there is a formula, say in disjunctive normal form, which has that truth table.

For each of the $2^n$ possible combinations of truth values of the $p_i$, we have $2$ choices for the truth value of the formula, for a total of $2^{(2^n)}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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