MATH3801 Exam 2018
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
1. (a) Let ϕ = (q1 → ((-q2 ) → q1 )), ψ 1 = (p1 → p2 ) and ψ2 = (p1 A p2 ). Draw the parsing trees for ϕ [ψi /qi] and ψ1 [ϕ/p1 , ϕ/p2].
(b) Consider the set of propositions in the language with logical connectives A and
-. Define what it means for a function ν : PROP → {0, 1} to be a valuation.
(c) Suppose that ϕ is a formula using only the connectives A and ^. Show that if ν is a valuation such that Ipi冂 = 1 for all i then Iϕ冂v = 1.
2. (a) Define what it means for a proposition to be satisfiable, for a set of propositions to be satisfiable, for a set of propositions to be finitely satisfiable, and for a proposition to be a tautology.
(b) Show that if a set of propositions Γ is finitely satisfiable and ϕ is a proposition
then at least one of Γ n ϕ or Γ n (-ϕ) is finitely satisfiable.
(c) Let Γ be a maximal satisfiable set of propositions in the language with logical
connectives - and ^. Show that the function ν : PROP → {0, 1} defined by Iϕ冂v = 1 iff ϕ e Γ
is a valuation.
3. (a) (i) Explain what it means for a set of propositions Γ to be inconsistent.
(ii) Show that if Γ is consistent and Γ b (ϕ ^ ψ) then at least one of Γ n ϕ or Γ n ψ is consistent.
(iii) Give an example of an infinite rooted tree without an infinite path. (b) Prove the following using natural deduction:
{((p → q) → ((r → s) → t)), q, ((s → r) → s)} b t
4. (a) State the soundness and completeness theorems for first order predicate logic. (b) State and prove the countable L_os-Vaught Theorem.
(c) Let c have the following nonlogical symbols:
● a binary predicate symbol E; and
● two unary predicate symbols P and Q.
For each n ≥ 1, let ϕ. be the sentence which says that there are at least n distinct elements satisfying the predicate P , and for each n ≥ 1 let ψ. be the sentence which says there are at least n distinct elements satisfying the predicate Q. Let T be the theory in c with the following axioms:
● (Vx)(Px V Qx)
● (Vx)-(Px A Qx)
● ϕ. and ψ. for all n ≥ 1
● (Vx)(Vy)(Exy 4 (Px A Qy))
Prove that T is consistent and complete.
5. (a) Define the class of register machines, and give a description of their operation.
Define what it means for a function f : 冈0(k) → 冈0 to be computable. (b) Find register machines which compute each of the following functions:
(i) f : 冈0(2) → 冈0 , f(n, m) = n + m.
(ii) f : 冈0(2) → 冈0 , f(n, m) = n - m if n ≥ m, and f(n, m) = 0 otherwise.
(c) Prove that the following functions are computable:
(i) f(n) = 2.
(ii) f(n) = |log2 (n)|, where |x| is the floor function.
Justify your answers. You may quote without proof any relevant results from the course.
2023-04-12