To be handed in at the beginning of your support class in week 5 (27 – 31 Mar)
Show your working and give full explanations for all questions.
(1) Let P(x,y) be the predicate “y = 3x”. Consider the statements
(a) ∀x∃yP(x,y)
(b) ∀y∃xP(x,y) (c) ∃y∀xP(x,y) where x and y range over the integers.
Write whether each statement is true or false and give a very short explanation of why.
(2) Are the sentences
¬(∃xA(x) → ∀x∃yB(x,y)) and ∃xA(x) ∧ ∃x∀y¬B(x,y)
logically equivalent? If they are equivalent, prove that they are. If not, give an interpretation under which they have different truth values.
(3) Is the sentence
(∃xQ(x) ∧ ∃xR(x)) ↔ ∃x(Q(x) ∧ R(x))
valid? If it is, explain why. If it isn’t, give an interpretation under which it is false.
(4) Prove using simple induction that, for each integer n ≥ 1,
.
