= Solution
Let $r$ be the number of true values among $a,b,c$. Count the ten <clause> occurrences for the two choices of $d$. With $d=0$, the three positive singletons contribute $r$, the three negated-pair <clauses> contribute $3-\binom r2$, and the last three <clauses> all hold. With $d=1$, the four singleton <clauses> contribute $r+1$, the negated pairs again contribute $3-\binom r2$, and the last three contribute $r$. Therefore
$$
\begin{array}{c|cc|c}
r&d=0&d=1&\text{maximum}\\\hline
0&6&4&6\\
1&7&6&7\\
2&7&7&7\\
3&6&7&7
\end{array}
$$
The original three-<literal> <clause> is satisfied exactly when $r\ge1$, and then a value of $d$ satisfies exactly seven gadget <clauses>. If $r=0$, no choice reaches seven. Thus \b[the required equivalence holds, and seven is also an upper bound for every assignment to the gadget.] This is the <seven-clause gadget for MAX-2SAT>.
Back to article page
