2
$\begingroup$

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

  • 0
    Define "formula".2012-10-02

2 Answers 2

5

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)}$.

0

If there are n variable, the truth table contains 2^n rows. In each row the function can be true or false. There for by product rule the required number of functions = 2 × 2 × 2 × ••••••• upto 2^n times = 2^(2^n)

  • 0
    Your argument is the same the the one given in the previous answer. Your answer is not adding any value and hence I strongly suggest you to delete it.2017-08-01