# $\phi$ is a $m$-clause CNF formula. Prove that if $m< 8$, then there is at least 1 satisfying assignment for $\phi$.

$\phi$ is a 3SAT CNF formula. All variables in each clause of $\phi$ are distinct. The expected number of satisfied clauses under the uniform random assignment is given as $\frac{7m}{8}$. A satisfying assignment of the CNF means that all $m$ clauses must be true. (A CNF is defined as a conjunction of disjunction of literals.)

We know that if $m < 8$, then that means $E(X) < 7$. I don't understand how this suggests the existence of at least one satisfying assignment.

Hints will be appreciated, thank you!

## 2 Answers

The idea here is that if there are no satisfying assignments then $X$ can never be more than $m-1,$ and so we must have $E(X)\leq m-1$. When is that true?

• When all the variables $x_1, x_2, x_3$ repeat themselves in all clauses? – user445310 Apr 19 '18 at 12:04
• @user445310 you know $E(X)=7m/8$, so when is that $\leq m-1$? – Especially Lime Apr 19 '18 at 12:24
• When $m \leq 8$? – user445310 Apr 19 '18 at 12:47

HINT

The hardest version of a $7$ clause 3SAT problem would be when all clauses refer to the same $3$ variables. Now, with $3$ variables, how many possible truth-assignments are there?

• $\frac{1}{8}$ ? – user445310 Apr 19 '18 at 12:02
• I meant 8 possible assignments as $2^3$. – user445310 Apr 19 '18 at 12:55
• @user445310 exactly. Now make a connection between those 7 clauses and the 8 truth-assignments ... if I have a specific clause, how many out of those 8 truth-assignments satify it? – Bram28 Apr 19 '18 at 14:46