Logic B-Exam May 1996

There are 4 questions worth 10 points each for a total of 40 points.

1. Let add-carry be a 4n-ary connective such that add-carry(p, q, c, r) is true, for p = ⟨p_{1}, …, p_{n}⟩, q = ⟨q_{1}, …, q_{n}⟩, c = ⟨c_{1}, …, c_{n}⟩, and r = ⟨r_{1}, …, r_{n}⟩, when r is the sum of p and q (modulo 2^{n}) with c being the carry. Write a {¬, ∧, ∨}-formula of size O(n) that is logically equivalent to add-carry(p, q, c, r).

2. A propositional theory is a set of propositional formulas closed under logical implication. If S is a set of propositional formulas, then T h(S) = {φ : S ⊧ φ}, i.e., T h(S) is the closure of S under logical implication. Thus, T is a propositional theory if T = T h(T).

Exhibit a strictly increasing sequence T_{1} ⊂ T_{2} ⊂ T_{3} … (i.e., T_{i} is a proper subset of T_{i+1}, for j ≥ 1) of satisfiable theories.

3. Use compactness to show that if a set Σ of sentences has arbitrarily large finite models then it has an infinite model.

4. Consider a vocabulary L for graphs that consists of a single binary relation E (the edge relation). Write a second-order sentence φ over L such that φ is true for a graph G = (V, E) precisely when G is 3-colorable.