1.   (a) Define the language of propositional logic, and define PROP, the set of propo- sitions. Show that -p1  is not an element of PROP.

(b) Let σ be the signature with propositional variables p1 , p2 , . . . and logical sym- bols -, → , and l. Define what it means for a function ν : PROP(σ) → {0, 1} to be a valuation.

(c) Let ϕ = (q1  → ((-q2 ) → q1 )), ψ 1  = ((p1 A p2 ) →l), and ψ2  = (p5  → p7 ). Draw the parsing trees for ϕ , ψ 1 , ψ2 , and ϕ[ψ1 /q1 , ψ2 /q2].

(d) Let σ be the signature with propositional variables p1 , p2 , . . . and logical sym- bols -, → ,  and l,  and let σ \  be the signature with propositional variables q1 , . . . , qn , p1 , p2 , . . . and logical symbols -, → , and l.  Give an inductive defi- nition of ϕ[ψi /qi]. State and prove the substitution theorem for σ and σ \ .

2.   (a) Define what it means for a proposition to be satisfiable, for a set of propositions to be satisfiable, and for a proposition to be a tautology. State the compactness

theorem for propositional logic.

(b)  Show the following:

(i) If {ϕ, ψ} 上 χ then ϕ 上 (ψ → χ).

(ii) If ϕ 上 (ψ1 v ψ2 ), ψ 1  上 χ, and ψ2  上 χ, then ϕ 上 χ .

(c) Let B  = {s: N → {0, 1}} be the set of infinite binary strings.  A sequence sn   converges to s, written limn→o sn   =  s,  if for all i there exists Ni   such that for all n > Ni , sn (i) = s(i).  A function f : B → {0, 1} is continuous if limn→o f (sn ) = f (limn→o sn ).  Show that if f is continuous then there exists K such that: if s(i) = s\ (i) for i ≤ K then f (s) = f (s\ ).

3.   (a)   (i) Define what it means for a set Γ of propositions to be consistent.

(ii)  Show that if Γ is consistent and Γ 上 (ϕ v ψ) then at least one of Γ u {ϕ} or Γ u {ψ} is consistent.

(iii)  Show that if Γ is consistent then at least one of Γ u {ϕ} or Γ u {-ϕ} is consistent.

(b)  Give natural deduction proofs of the following:

(i)  ((ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)))

(ii)  ((-((-ϕ) v ψ)) → (-ψ))

(iii)  ((ϕ → ψ) → ((-ϕ) v ψ))

4.   (a) Define what it means for two L structures U and s to be elementary equivalent. Show that two finite groups are elementary equivalent if and only if they are isomorphic.

(b) Is there a set of sentences Γ in the language of groups such that if G is a group then G 上 Γ if and only if G is finite? Justify your answer.

(c) Find a sentence ϕ in the language of groups such that ϕ e Th(B2 ) and ϕ e/ Th(B3 ).

5.   (a) Define the class of register machines.

(b) Define what it means for a function f : N0(k)  → N0  to be computable.

(c) Find register machines which compute each of the following functions:

(i)  f : N0(2)  → N0 , f(n, m) = n + m.

(ii)  f : N0(2)  → N0 , f(n, m) = n - m, n > m, f(n, m) = 0 otherwise.   (iii)  f : N0(2)  → N0 , f(n, m) = n - 2m, n > 2m, f(n, m) = 0 otherwise.