1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ the DNF in $n$ variables has up to $2^n$ "clauses". $\endgroup$
    – David C. Ullrich
    Jun 10, 2021 at 22:11
  • $\begingroup$ It is not clear what you mean by expressions like $6 \land 4 \land 2$. $\endgroup$
    – Rob Arthan
    Jun 10, 2021 at 22:23
  • $\begingroup$ @Rob Arthan 6 options for the first literal, 4 for the second, 2 for the third $\endgroup$
    – ngc1300
    Jun 10, 2021 at 22:35
  • $\begingroup$ 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. $\endgroup$
    – Rob Arthan
    Jun 10, 2021 at 22:41

1 Answer 1

Reset to default
1
$\begingroup$

A full DNF for a propositional function (i.e., a DNF in which every disjunct includes all the variables) is essentially the same as a truth table representation of the propositional function. Here's how the correspondence between truth tables and full DNFs goes:

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.

(If you apply the simplifications above to a full DNF and then sort the literals in each disjunct and then the disjuncts into some agreed order, then you get a unique standard equivalent of the full DNF. You can use a combinatorial argument to count those standard full DNF forms, but this is just like counting the truth tables.)

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .