Solutions to selected exercises of Chapters 7–11
Bas Luttik
August 20, 2018
This document contains solutions to the following exercises in the book [1]:
7.2(c), 8.2(e), 8.7(c), 8.9(b),(d), 9.6(b),11.4(c),11.6.
We strongly advise you to first try all these exercises by yourself, before looking
at all at the solutions below. There is not a lot of variation possible in the way
solutions to exercises should be written down. So if your solution in one way or
another deviates from a solution below, then consider discussing the differences with
your instructor.
7.2 (c) The proposition is not valid for all abstract propositions P , Q and R. To
see this, let a and b are distinct propositional variables and let P = a ∧ b,
val val
Q = a and R = b. Then both P |== Q and P |== R hold (by ∧-∨-
val
6=
weakening), but Q == R.
8.2 (e) ∃x [x ∈ M : There is a person that is
Younger(x, Bernard) ∧ younger than Bernard and
Man(x) ∧ male and
∀y [y ∈ M : Child(x, y) ⇔ Child(Bernard, y)]] with the same parents.
Comment: The formula above expresses the predicate “x is a sibling
of y” as ∀z [z ∈ M : Child(x, z) ⇔ Child(y, z)]. This formalisation is
based on the interpretation that x and y are siblings if they have the
same parents, and (implicitly) assumes that every person has parents
(for: people without parents are siblings according to this formula!).
An alternative interpretation of “x is a sibling of y” could be “x and
y have a parent in common”, which can be formalised as ∃z [z ∈ M :
Child(x, z) ∧ Child(y, z)]. Note that this formulation does imply that x
and y are siblings if they only have one parent in common (i.e., they are
actually ‘half-siblings’).
8.7 (c) ∃x [x ∈ D : ∀y [y ∈ D : x = y]].
8.9 (b) The tree associated with ∃m [(m ∈ D) ∧ (m > 2) : m2 < 15] is:
∃m
∧ <
∈ > ( )2 15
m D m 2 m
(d) The tree associated with ∀m [m ∈ N ⇒ m2 > m] ∨ (2 + 2 = 4) is
1
∨
∀m =
+ 4
True ⇒
2 2
∈ >
m N ( )2 m
m
val
9.6 (b) To show that ∃k [P : Q] ∧ ∃k [P : R] = 6=
= ∃k [P : Q ∧ R] we need to find
a counterexample, i.e., concrete predicates P , Q and R for which the
equivalence does not hold.
Let P = (k ∈ Z), let Q = (k > 0) and let R = (k < 0). Then, since
1 ∈ Z and 1 > 0, the proposition ∃k [P : Q] is true, and since −1 ∈ Z and
−1 < 0, the proposition ∃k [P : R] is true. But ∃k [P : Q ∧ R] is not true,
for there does not exist an integer that is both positive and negative.
11.4 (c) The proposition is true, for 29 is a prime number that is 1 plus a multiple
of 7 (29 = 1 + 4 · 7).
11.6 We need to prove that the square of an odd integer is 1 plus a multiple of 8.
To this end, let n be the square of an odd integer. Then there exists x ∈ Z
such that n = (2x + 1)2 = 4x2 + 4x + 1. Clearly, it now remains to establish
that 4x2 + 4x is a multiple of eight; we distinguish two cases:
(a) If x is even, then there exists y ∈ Z such that x = 2y, so
4x2 + 4x = 4(2y)2 + 4 · 2y = 16y 2 + 8y = 8(2y 2 + y) .
(b) If x is odd, then there exists y ∈ Z such that x = 2y + 1, so
4x2 + 4x = 4(2y + 1)2 + 4(2y + 1) = 4(4y 2 + 4y + 1) + 4(2y + 1)
= 16y 2 + 24y + 8 = 8(2y 2 + 3y + 1) .
In both cases it is clear that 4x2 + 4x is indeed a multiple of 8.
References
[1] Rob Nederpelt and Fairouz Kamareddine. Logical Reasoning: A First Course,
volume 3 of Texts in Computing. King’s College Publications, second revised
edition edition, 2011.
