Logic and Foundations

MATH3065 LOGIC AND FOUNDATIONS
Semester 1 First Assignment 2013
This assignment comprises a total of 60 marks, and is worth 15% of the overall
assessment. It should be completed, accompanied by a signed cover sheet, and handed
in at the lecture on Monday 22 April. Acknowledge any sources or assistance.
1. Construct truth tables for each of (a) and (b), and find all counterexamples in
each case.
(a) (Q ⇒ P ) ⇒ (P ⇒ Q) (b) (Q ∨ P ) ⇒ (Q ∧ P )
(6 marks)
2. Use the rules of deduction in the Propositional Calculus to find formal proofs
for the following sequents:
(a) (R ⇒ P ) ∧ (R ⇒ Q) ⊢ R ⇒ (P ∧ Q)
(b) (Q ⇒ R) ∧ (P ⇒ R) ⊢ (Q ∨ P ) ⇒ R
(c) P ⇒ R , Q ⇒ S ⊢ (P ∨ Q) ⇒ (R ∨ S )
(12 marks)
3. Find a formal proof in the Propositional Calculus for the sequent
∼ R , Q ⇒ R ⊢ ∼ Q
without using Modus Tollens (MT). (This shows that MT may be deleted from
the rules of deduction without compromising provability.)
(4 marks)
4. Use truth values to determine which one of the following is a theorem (in the
sense of always being true).
(a)

Q ∧ ∼ P ⇒ ∼ Q

⇒ P (b)

P ∧ ∼ P ⇒ ∼ Q

⇒ Q
For the one that isn’t a theorem, produce a counterexample. F or the one
that is a theorem, provide a formal proof also using rules of deduction in the
Propositional Calculus.
(8 marks)
5. Consider well-formed formulae Wn
, for each positive integer n, defined as follows, where P1, P
2
, . . . are propositional variables:
W1 = P1
and Wk+1 = (Wk ⇔ Pk+1) for each k ≥ 1 .
(a) Write out W2
, W3
and W4
explicitly in terms of P1
, P2
, P3
and P4
.
(b) Prove that Wn
contains 4n − 3 symbols, for each n, where a propositional
variable (including its subscript) counts as one symbol.
(c) Prove that Wn
has truth value T if and only if an even number of the
propositional variables P1, . . . , P
n
have truth value F , for each n.
(15 marks)
6. Recall that if X is a set then P (X ) is the set of all subsets of X , called the
power set of X .
(a) Suppose that A and B are sets and that there is a surjective function h :
A → B. Prove carefully that there exists an injective function g : B → A.
(b) For any real number x ∈ [0, 1], denote its decimal expansion by
x = 0. d
1
d
2
. . . d
n
. . .
where each d
i
is a digit from 0 to 9. The following rules for functions
f, h : [0, 1] → P(Z
+
) are not quite well-defined:
f (x) = { d
i × 10
i
| d
i
6 = 0 } and h(x) = { i ∈ Z
+
| d
i
= 0 } .
Explain how to modify them so that both f and h become well-defined.
Prove carefully that f then becomes injective and that h then becomes
surjective.
(c) Use parts (a) and (b) and the Schr¨oder-Bernstein Theorem to deduce that
the interval [0, 1] and the power set P (Z
+
) have the same cardinality.
(15 marks)