1.  (a) Let ϕ = ((a → b) → (c A d)), ψ 1  = (a V d) and ψ2  = (-e).  Draw the parsing trees for ϕ [ψ1 /a, ψ2 /b, ψ2 /d] and ψ1 [ϕ/a].

(b)  Consider the set of propositions in the language with logical connectives → and

1. Find, for each of the following

●  (-ϕ),

●  (ϕ V ψ),

●  (ϕ A ψ),

a formula equivalent to it which uses only the logical symbols → and 1.

(c) Let PROP be the set of propositions in the language with logical connectives V and -. Define what it means for a function ν : PROP → {0, 1} to be a valuation.

(d)  Show that there is no proposition ϕ using only the logical symbol → and the propositional variable a such that (ϕ → (-a)) is a tautology.

2.  (a)  State and prove Konig’s lemma.  State the compactness theorem for proposi- tional logic.

(b)  Suppose that {Xn  | n ∈ N} is a family of finite subsets of N.  Suppose that for

each finite subset I of N there is a subset DI  ζ N such that |DI  n Xn | = 1 for all n ∈ I .  Show that there exists a subset D ∈ N such that |D n Xn | = 1 for all n ∈ N. Hint:  Consider the set of sequences σ : N → N with the property that σ(n) ∈ Xn .

3.  (a) Define what it means for a set of propositions Γ to be inconsistent. Show that

if Γ is consistent and Γ 上 (ϕ → ψ) then Γ u {ϕ, (-ψ)} is not consistent.

(b) Let PROP be the set of formulas in the language with logical connectives → and

1.  Define what it means for Γ to be a maximal consistent set of propositions, and show that the function ν : PROP → {0, 1} defined by「ϕⅡ]  = 1 iff ϕ ∈ Γ is a valuation when Γ is maximal consistent.

(c)  Show that

{((-ϕ) → ψ), (ϕ → χ), (ψ → χ)} 上 χ

4. Recall that two L–structures A and B are elementarily equivalent, written A = B, if for all sentences ϕ , A 乍 ϕ if and only if B 乍 ϕ .

(a) Find a sentence ϕ in the language of groups such that S3  乍 ϕ but S4   ϕ . (b)  State the compactness theorem for first order logic.

(c) A graph G is connected if, for any pair of distinct vertices a and b, there is a sequence x1 , . . . , xn  of vertices such that a = x1 , b = xn , and xi  is connected by an edge to xi+1  for all i = 1, . . . , n 一 1.  Let E be the graph with vertex set 勿 and an edge between a and b if and only if |a 一 b| = 1.  Show that there is a disconnected graph F such that F = E .

5.  (a) Let X ∈ N. Define what it means for X to be recursively enumerable, and what it means for X to be recursive.

(b)  Show that the following sets are recursive:

(i)  {n2 }

(ii)  {n | gcd(n, 2019)  1}, where gcd(n, m) is the greatest common divisor of

m and n.

(c) Prove that there is a subset of N which is not recursively enumerable.