# How many formulas can you make (up to equivalence) with $n$ propositions?

I know from this answer what the answer to this question should be. What bothers me is that I haven't been able to solve this working with just the sentences themselves.

If I am not mistaken, every formula can be written in full disjunctive normal form, where each proposition (as a literal) exactly once in each clause. So if we have $$3$$ propositions, that gives $$6$$ literals so for one clause we know we $$6 \times 4 \times 2$$ as the number of way to build a clause. I say $$6 \times 4 \times 2$$ and not $$6 \times 6 \times 6$$ since the latter counts $$\top$$ and $$\bot$$ more than once. As far as how many clauses are needed to write any sentence, I am not sure. My guess is that the maximum number of clauses needed is the equal to the number of propositions. This is based on the example that XOR can only be written as $$(A \land \lnot B) \lor (\lnot A \lor B)$$. But no matter what I try I cannot get this combinatoric method to yield the correct answer $$2^{2^n}$$.

• the DNF in $n$ variables has up to $2^n$ "clauses". Jun 10, 2021 at 22:11
• It is not clear what you mean by expressions like $6 \land 4 \land 2$. Jun 10, 2021 at 22:23
• @Rob Arthan 6 options for the first literal, 4 for the second, 2 for the third Jun 10, 2021 at 22:35
• I see you have used a more natural notationnow. You are overcounting because you can assume the literals are in a standard order, you can discard inconsistent disjuncts and remove redundant literals and disjuncts. See my answer for more details. Jun 10, 2021 at 22:41

For a given truth table, the corresponding DNF has one disjunct for each row in the truth table where the result is $$\top$$ and that disjunct is the conjunction of literals that defines the input values in that row. For a given full DNF, if you simplify it by (i) discarding inconsistent disjuncts, (ii) removing redundant literals from each disjunct and (iii) removing duplicate disjuncts, you can recover the truth table.
Examples (with variables $$a$$, $$b$$ and $$c$$)
1. Given the truth table that has result $$\top$$ for the following combinations of inputs and no others: $$\matrix{a & b & c \\ \top & \bot & \top\\ \top & \top & \top}$$ Then the full DNF is $$(a \land \lnot b \land c) \lor (a \land b \land c)$$.
2. The full DNF $$(a \land b \land c \land \lnot a) \lor (a \land b \land c \land c) \lor (a \land b \land c)$$ simplifies to $$a \land b \land c$$, which corresponds to the truth table that results in $$\top$$ for the following combination of inputs and no others: $$\matrix{a & b & c \\ \top & \top & \top}$$