Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/logic-and-proof/1/c/solution

Take the single Boolean clause
This is a 3-CNF formula. Suppose a 2-CNF formula were logically equivalent to . Every Boolean clause of would then be a consequence of .
Consider any nontautological Boolean clause containing at most two Boolean literals. Choose a Boolean valuation falsifying its Boolean literals. At least one of does not occur in ; assign that Boolean variable true. The resulting Boolean valuation satisfies while falsifying . This contradicts . An empty Boolean clause also cannot be a consequence of the satisfiable .
Consequently every Boolean clause of would have to be a tautology. Their logical conjunction would be true under every Boolean valuation, whereas is false when . This proves that no such exists.
The argument even allows additional ordinary Boolean variables in : at most two Boolean literals still leave one of 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.

New to topics? Read the docs here!