DMMR Tutorial sheet 1

Propositional Logic, Predicate Logic, Proof techniques

September 19th, 2019

1. Construct the truth table for the formula (A → B) → [((B → C) ∧ ¬C) → ¬A].
Solution:

A B C ¬A ¬C (A → B) (B → C) (B → C) ∧ ¬C ((B → C) ∧ ¬C) → ¬A X
T T T F F T T F T T
T T F F T T F F T T
T F T F F F T F T T
T F F F T F T T F T
F T T T F T T F T T
F T F T T T F F T T
F F T T F T T F T T
F F F T T T T T T T

X is the formula (A → B) → [((B → C) ∧ ¬C) → ¬A] 

2. Let P (m, n) be the statement “m divides n”, where the domain for both variables is the positive
integers (that is, integers m, n > 0). By “m divides n” we mean that n = km for some integer k.
Determine the truth values of each of these statements.

(a) P (4, 5)
(b) P (2, 4)
(c) ∀m ∀n P (m, n)
(d) ∃n ∀m P (m, n)
(e) ∃m ∀n P (m, n)
(f) ∀n ∃m P (m, n)

Solution:

(a) False, since 4 does not divide 5

(b) True, since 4 = 2 · 2
(c) False, see (a)
1
(d) False, for all n we get that P (2n, n) is not True, since 2 6∈ Z
(e) True: m = 1 see (f)
(f) True as we can always choose m = 1

3. Assume the following predicates: B(x) is “x is a baby”, C(x) is “x can manage crocodiles”,
“D(x) is “x is despised” and L(x) is “x is logical”.

1
 (a) Assume the domain consists of people. Express each of the following statements using
quantifiers, logical connectives and the predicates B(x), C(x), D(x) and L(x).
i. Babies are illogical
ii. Nobody is despised who can manage crocodiles
iii. Illogical people are despised
iv. Babies cannot manage crocodiles
(b) Prove that iv follows from i, ii and iii.

Solution:

(a) The following are expressed as follows:

i. Babies are illogical ∀x(B(x) → ¬L(x))
ii. Nobody is despised who can manage crocodiles ¬∃x(D(x) ∧ C(x))
iii. Illogical people are despised ∀x(¬L(x) → D(x))
iv. Babies cannot manage crocodiles ∀x(B(x) → ¬C(x))
(b) To show iv follows from i, ii and iii notice that ii is equivalent to ∀x(D(x) → ¬C(x)) using
duality of quantifiers, ¬∃xP (x) is equivalent to ∀x¬P (x); De Morgans law ¬(P ∧ Q) is
equivalent to ¬P ∨ ¬Q; and ¬P ∨ Q is equivalent to P → Q. Using transitivity i and iii
implies ∀x(B(x) → D(x)) which with the reformulation of ii implies iv.

4. (a) Assume m and n are both integers. Prove by contraposition, if mn is even then m is even or
n is even.
Solution:
We have to prove
mn even → (m even ∨ n even)
The contrapositive is
¬(m even ∨ n even) → ¬(mn even)
which can be transformed using DeMorgan’s law and even ≡ ¬ odd

(m odd ∧ n odd) → mn odd

We assume m is odd and by the definition of odd there exists a k ∈ Z with m = 2k + 1.

Similar there exists a l ∈ Z with n = 2l + 1. Therefore we get

mn = (2k + 1) · (2l + 1)
= 4lk + 2k + 2l + 1
= 2(2lk + k + l) + 1
= 2l0 + 1

where l0 = 2lk + k + l ∈ Z. By definition mn is therefore odd.


(b) Prove by contradiction that the sum of an irrational number and a rational number is irra-
tional.
Solution:
Assume that the sum of an irrational number i and a rational number ab is rational. Then, let

2
 c and d be integers such that i + ab = dc . Therefore i = dc − ab = bc−dadb . Given that a, b, c
and d are integers, bc − da and db are also integers, this shows that i is rational and therefore
contradicts our initial assumption. Therefore, the sum of a rational and an irrational number
must be irrational. 
(c) Prove that there is not a rational number r such that r3 + r + 1 = 0.
Solution:
We prove it by contradiction. Assume that r = ab is a solution where a, b are in lowest terms,
3
so have no common factors other than 1. So, ab3 + ab + 1 = 0; therefore, a3 + b2 a + b3 = 0.
If a and b are both odd then LHS is a sum of odd numbers; if one is odd and the other even
then LHS is odd. That just leaves that both are even which contradicts that ab is in lowest
terms. (We are using here various properties that you may wish to prove such as if n is odd
(even) then n2 and n3 are odd (even).) 

5. (a) Assume that the positive integers 1, 2, . . . , 2n are written on a blackboard, where n is an odd
integer. Choose any two of the integers j and k that are present on the blackboard and write
|j − k| on the board and erase j and k. Continue this process until only one integer is on the
board. Prove that this integer must be odd.
Solution:
We consider what happens to the parity of the combined sum of the numbers that are left on
the blackboard at each stage. If j and k are both even or both odd, then their sum and their
difference are both even, and we are replacing the even sum j + k by the even difference
|j − k|, leaving the parity of the total unchanged. If j and k have different parities, then
erasing them changes the parity of the total, but their difference |j − k| is odd, so adding this
difference restores the parity of the total. Therefore the integer we end up with at the end of
the process must have the same parity as 1 + 2 + . . . + (2n). It is easy to compute this sum.
If we add the first and last terms we get 2n + 1; if we add the second and next-to-last terms
we get 2 + (2n − 1) = 2n + 1; and so on. In all we get n sums of 2n + 1, so the total sum
is n(2n + 1). If n is odd, this is the product of two odd numbers and therefore is odd, as
desired. 
(b) Prove that if the first 10 positive integers are placed around a circle, in any order, there exists
three integers in consecutive locations around the circle that have a sum greater than or equal
to 17.
Solution:
Consider the numbers 1 to 10 placed around the circle. Let x denote the sum, over all
consecutive triples, of the sum of those three consecutive numbers. Note that each number
from 1 to 10 will appear exactly three times in the sum x. Since 1 + 2 + ... + 10 = 55, this
means that x = 165.
Suppose (for showing a contradiction) that every consecutive triple sums to at most 16. Then
clearly the sum x of all consecutive triples will be at most 160 (because there are 10 such
triples). But this contradicts the prior calculation of x as 165.