There are 3 questions worth 10 points each for a total of 30 points.

1. The 3-colorability problem is as follows. You are given a finite undirected graph G = (V,E). You have to decide whether G has a 3-coloring, i.e., an assignment of one of three colors (say, red, green, and blue) to each node so that no edge connect two nodes of the same color.

   Show that this problem can be polynomially reduced to satisfiability of propositional formulas.

2. Fix a finite vocabulary L that consists of predicate and function symbols. A first-order theory over L is a set S of first-order sentences over L that is closed under logical implication, i.e., if S(logically implies)s, then s(is an element of)S. The theory S is complete if for every first-order sentence s over L we have that either s(is an element of)S or ~s(is an element of)S. Use the Completeness Theorem to show that if S is consistent, complete, and recursively enumerable, then it is recursive.

3. Let a be the first-order sentence (for All)x(there Exists)yP(x,y). Find a second-order Skolem normal-form sentence b for a. That is, b should:
   • have a quantifier prefix consisting of a string of existential second-order quantifiers, followed by a string of universal first-order quantifiers, followed by a quantifier-free formula,
   • be logically equivalent to a
   Justify why b is logically equivalent to a.