2
$\begingroup$

Definition: A maximal 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any new different 3 disjuctive literals clause, then the formula becomes unsatisfiable.

Please don't confuse with the definition of minimal 3CNF formula from my previous question What is the set of all minimal 3CNF formulas

This is not the same thing!

But my question about minimal 3CNF formulas in the above link is same for maximal 3CNF formulas here, i.e.

For some natural number n, where n is the number of atomic variables, what is the set of all maximal 3CNF formulas? Is it finite? If it is then what is it's cardinality, i.e. how many different maximal 3CNF formulas is possible?

Note that for k-cnf formula n≥k, so in 3CNF formula n≥3.

$\endgroup$
2
$\begingroup$

There are $2^n$ maximal 3CNFs; here I am assuming that each 3-clause contains at most three different literals (corresponding to different variables), and that the clauses are different and unordered (both within each clause, and across the formula). Indeed, I show below that if $\varphi$ is a maximal 3CNF then there is a truth assignment $\alpha$ such that $\varphi$ consists of all 3-clauses consistent with $\varphi$, and conversely, each such formula is maximal.

Indeed, let $\varphi$ be a maximal 3CNF. Suppose first that $\varphi$ has at least two different truth assignments $\alpha,\beta$. There is a variable $x_i$ whose truth value is different in $\alpha$ and $\beta$, say $x_i$ is true in $\alpha$ but false in $\beta$. In particular, the clause $x_i$ is not in $\varphi$ (since $\beta$ doesn't satisfy it), and if we add it then the formula remains satisfiable. We conclude that $\varphi$ has a unique satisfying assignment $\alpha$. If $\varphi$ doesn't contain all 3-clauses consistent with $\alpha$ then we can add the missing ones while keeping the formula satisfiable. Thus $\varphi$ must consist of all 3-clauses consistent with $\alpha$.

Conversely, suppose that $\varphi$ consists of all 3-clauses consistent with $\alpha$. Since $\varphi$ contains all clauses of width 1, $\alpha$ is the unique satisfying assignment. By definition, any other 3-clause is inconsistent with $\alpha$, and so $\varphi$ is maximal.

You might be interested in E3CNFs, in which each 3-clause contain exactly three literals, each corresponding to a different variables. These can probably be analyzed using the same approach - if you're interested, you're welcome to work it through.

$\endgroup$
  • $\begingroup$ WoW! Quick answer! thank you! Glad to see it. $\endgroup$ – Farewell Stack Exchange Jul 26 '17 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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