Q:

Reduce Max-Cut to Max-2SAT

I would like to find a reduction from Max-Cut to Max-2Sat. 
Could someone shed light on this problem, preferably spiced with some intuition? 
Thanks,
Matan. 

A:

Given an instance $G = (V,E)$ for Max-Cut, we create an instance of Max-2Sat with one variable $x_v$ per vertex $v \in V$, and two clauses per edge $(v,w) \in E$:
$$ x_v \lor x_w, \qquad\overline{x_v} \lor \overline{x_w}.  $$
Every subset of $V$ corresponds to a truth assignment for the $x_v$ in a natural way.  Furthermore, the number of clauses satisfied is exactly
$$ |E| + |E(V,\overline{V})|.  $$
Intuitively, the edge $(v,w)$ is cut iff $(x_v \lor x_w) \land (\overline{x_v} \lor \overline{x_w})$, and this is why this reduction works.