Week 5 Introduction to Logic

T. Colclough Intro to logic: Fall 2021 Week 5
Assignment 5
Write your answers to each question on paper (I’d use a pencil). You do not need to copy out
answers by Friday, November 5th, 5pm Irvine time.
Make your answers legible, and clearly indicate the question/part of the question you are answering. You must submit your own work. Include your name and ID number at the top of each
page. You may refer to your notes. The assignment is worth 40 points.
(1) (4 pts each): Find a conjunctive normal form and a disjunctive normal form for each of the
following.
(a) ϕ → (ψ → χ).
(b) (ϕ → ψ) → χ.
(c) ¬ϕ → (ϕ → ψ).
(2) Let ϕ have a conjunctive normal form
ϕ
∧ =
^^
i≤n
__
j≤mi
ϕij .
Let ϕ have a disjunctive normal form
ϕ
∨ =
__
i≤n
^^
j≤mi
ϕij .
Assume n ≥ 0 and mi ≥ 0 for each i ≤ n, so we are not considering “empty” conjuncts/disjuncts. Consider the following conditions.
(I) For all valuations v: for all i ≤ n and for all j ≤ mi
, Jϕij Kv = 1.
(II) For all valuations v: there exists i ≤ n and there exists j ≤ mi such that Jϕij Kv = 1.
(III) For all valuations v: for all i ≤ n there exists j ≤ mi such that Jϕij Kv = 1.
(IV) For all valuations v: there exists i ≤ n such that for all j ≤ mi
, Jϕij Kv = 1.
(a) (2 pts): Which of the conditions (I)–(IV) imply that ϕ
∧ is a tautology?
(b) (2 pts): If ϕ
∧ is a tautology, then which of conditions (I)–(IV) hold?
(c) (2 pts): Which of the conditions (I)–(IV) imply that ϕ
∨ is a tautology?
(d) (2 pts): If ϕ
∨ is a tautology, then which of conditions (I)–(IV) hold?
There may be more than one condition for each part (a), (b), (c) and (d). You do not need
(3) (6 pts, 6 pts, 8 pts):
(a) Derive ϕ → ϕ.
(b) Derive ⊥ → ϕ.
(c) Derive (ϕ → ¬ϕ) → ¬ϕ.
Page 1