Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi I am stuck on the following question :

How many non-equivalent formulas that use propositions p1...pn 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|improve this question
    
Define "formula". –  Gerry Myerson Oct 2 '12 at 5:56

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.