= Solution
Take the single <Boolean clause>
$$
\boxed{F=P\lor Q\lor R.}
$$
This is a <3-CNF formula>. Suppose a <2-CNF formula> $K$ were <logically equivalent> to $F$. Every <Boolean clause> $C$ of $K$ would then be a consequence of $F$.
Consider any nontautological <Boolean clause> $C$ containing at most two <Boolean literals>. Choose a <Boolean valuation> falsifying its <Boolean literals>. At least one of $P,Q,R$ does not occur in $C$; assign that <Boolean variable> true. The resulting <Boolean valuation> satisfies $F$ while falsifying $C$. This contradicts $F\models C$. An empty <Boolean clause> also cannot be a consequence of the satisfiable $F$.
Consequently every <Boolean clause> of $K$ would have to be a tautology. Their <logical conjunction> would be true under every <Boolean valuation>, whereas $F$ is false when $P=Q=R=0$. This proves that no such $K$ exists.
The argument even allows additional ordinary <Boolean variables> in $K$: at most two <Boolean literals> still leave one of $P,Q,R$ free to be made true. Introducing extra variables together with <existential quantification> would change the requested notion of <logical equivalence>, so it is not a way around the argument.
Back to article page
