CSIL Courses

Hint for Problem 1, Homework 3.

For variables x_1, x_2, ..., x_n, y_1, y_2, ..., y_n, take S to be the set of all assignments such that for each i from 1 to n, x_i is mapped to true iff y_i is mapped to true. Then, pick variable orderings that ensure small and big BDDs for the function.