# Can minimal CNF contain clause longer than initial CNF?

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

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?

The answer was so simple. Formula $(a\lor b\lor t)\land(c\lor d\lor \overline t) = (a\lor b\lor c\lor d)$ which means that minimal CNF can has clauses longer than initial.
• $(a\lor b\lor t)\land(c\lor d\lor \overline t) \neq (a\lor b\lor c\lor d)$<br> Consider variable assignment: a = 0, b = 0, c = 0, d = 1 and t = 0.<br> Thus $(0\lor 0\lor 0)\land(0\lor 1\lor \overline 0) \neq (0\lor 0\lor 0\lor 1)$ – xxx Mar 18 at 11:05