Logic B-Exam January 1996

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 firstorder theory over L is a set S of first-order sentences over L that is closed under logical implication, i.e., if S ⊧ σ, then σ ∈ S. The theory S is complete if for every first-order sentence σ over L we have that either σ ∈ S or ¬σ ∈ S. Use the Completeness Theorem to show that if S is consistent, complete, and recursively enumerable, then it is recursive.

3. Let α be the first-order sentence ∀x∃yP (x, y). Find a second-order Skolem normalform sentence β for α, that is, β 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 α.

Justify why β is logically equivalent to α.