Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$.

Can $\Phi_{min}$ contain a clause of size $m > k$?

What I have tried:

Let's define the concept of partial assignment: asingnment that has free variables. Example: $x_1 = 0, x_2 = \{0\ ,1\}, x_3 = 1$. Here $x_2$ is a free variable.

If $\Phi$ contains clause $C(p)$, then $\Phi(\overline p) =0$.

Example: $\Phi = (x_1\lor x_2\lor x_3)\land (x_2\lor x_3\lor x_4)$. Here $\Phi(x_1=0,x_2=0,x_3=0)=0$.

  1. Going further, if $\Phi$ is k-CNF, it means that shortest unsatisfied partial assignment has length $l\leq k$.

  2. Also, formula already contains info about all unsatisfied partial assignments.

P.1 and p.2 says, that we don't need to use partial assignment of length $l>k$ to express the formula.

One more statement, $\Phi(p)=0\Rightarrow \Phi(p, x_i)=0$, where $x_i$ is fixed variable that is not in $p$.

Here is where I got stuck: $\Phi_{min}$ contains smallest amount of shortest inverted partial assignments of formula $\Phi$. Let's say that each of partial assignments $p_1, p_2$ has length $l$, such that $\Phi(p_1) =0, \Phi(p_2)=0$. Can we change them to one longer partial assignment $p$?

Restrictions are following: if you'll change or remove any variable in $p_1$ or $p_2$ (we'll call them $p'_1$ and $p'_2$ respectively), then $\Phi(p'_1) = 1$ and $\Phi(p'_2)=1$.

Intuitively it seems that they can't be combined, but what about logic?


Your Answer

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

Browse other questions tagged or ask your own question.