(1p) What is the contrapositive of “if n is non-zero, then pigs can fly”?
If pigs can fly, then n is non-zero.
If pigs cannot fly, then n is non-zero.
If pigs can fly, then n is not non-zero.
If pigs cannot fly, then n is not non-zero.
(1p) Which of the following proof methods are correct? (Here ℕ stands for the set of natural numbers, {0, 1, 2, …}, and ℤ stands for the set of integers, {…, − 2, − 1, 0, 1, 2, …}. The variable P stands for an arbitrary integer predicate.)
Proof by cases: P(0) ∧ (∀n ∈ ℕ.P(n + 1)) ⇒ ∀n ∈ ℕ.P(n).
Proof by cases: (∀n ∈ ℕ.P( − (n + 1))) ∧ (∀n ∈ ℕ.P(n + 1)) ⇒ ∀i ∈ ℤ.P(i).
Induction: P(0) ∧ (∀n ∈ ℕ.P(n) ⇒ P(n + 1)) ⇒ ∀n ∈ ℕ.P(n).
Induction: P(0) ∧ (∀i ∈ ℤ.P(i) ⇒ P(i + 1)) ⇒ ∀i ∈ ℤ.P(i).
(2p) Where is the error in the following “proof” of “All horses have the same colour”?
(This question is based on an example that seems to be due to George Pólya.)
(1p) Define the set T inductively by the following rules:
If n ∈ ℕ, then leaf(n) ∈ T.
If l, r ∈ T, then node(l, r) ∈ T.
Define the function f ∈ T → ℕ by recursion on the structure of its argument in the following way:
f(leaf(n)) = n
f(node(l, r)) = f(r) − f(l)
What is the value of f(node(node(leaf(1), leaf(2)), leaf(3)))?