Hint for Problem 1, Homework 3.
For variable x_1,...,x_n, choose S as the set of all valuations that map an odd number of the variables evaluate to 1 (i.e. choose the set describing the parity set).
