Mathematical foundations of Computer Science

Exercise 1:
Let p and q be the propositions
p: I bought a lottery ticket this week.
q: I won the million pound jackpot.
Express each of the following propositions as plain English sentences.

a) ¬p d) p ∧ q g) ¬q ∨ ¬q
b) p ∨ q e) ¬p → ¬q
c) p → q f) ¬p ∧ ¬q h) ¬p ∨ (p ∧ q)

Answer:
a) I did not buy a lottery ticket this week.
b) I bought a lottery ticket this week or I won the million pound jackpot.
c) If I bought a lottery ticket this week then I won the million pound jackpot.
d) I bought a lottery ticket this week and I won the million pound jackpot.
e) If I did not buy a lottery ticket this week then I did not win the million pound
jackpot.
f ) I did not buy a lottery ticket this week and I did not win the million pound
jackpot.
g) I did not win the million pound jackpot or I did not win the million pound
jackpot.
h) I did not buy a lottery ticket this week or I both bought a lottery ticket this week
and won the million pound jackpot.
Exercise 2:
Let p, q and r be the following propositions.
p: Grizzly bears have been seen in the area.
q: Hiking is safe on the trail.
r: berries are ripe along the trail.
Write these propositions using p, q and r and logical connectives.
a) Berries are ripe along the trail, but grizzly bears have not been seen in the area.
Answer: r ∧ ¬p
b) Grizzly bears have not been seen in the area and hiking in the trail is safe, but
berries along the trail are ripe. Answer: ¬p ∧ q ∧ r
c) It is not safe to hike on the trail, but grizzly bears have not been seen in the
area and the berries along the trail are ripe. Answer: ¬q ∧ ¬p ∧ r
d) For hiking on the trail to be safe, it is necessary but not sufficient that berries
not be ripe along the trail and for grizzly bears not to have been seen in the
area. Answer: (q → ¬p ∧ ¬r) ∧ ¬(¬p ∧ ¬r → q)
e) Hiking is not safe on the trail whenever grizzly bears have been seen in the area
and berries are ripe along the trail. Answer: p ∧ r → ¬q

1
Exercise 3:
1) Determine whether each of these conditional statements is true or false.
a) if 1 + 1 = 2 then 2 + 2 = 5 Answer: false
b) if 1 + 1 = 3 then 2 + 2 = 4 Answer: true
c) if 1 + 1 = 3 then 2 + 2 = 5 Answer: true
d) if monkeys can fly, then 1 + 1 = 3 Answer: true
Exercise 4:
1) How many rows will appear in each of the truth tables for the propositions
below?
a) p → ¬q Answer: 4
b) (p ∨ ¬r) ∧ (q ∨ ¬s) Answer: 16
c) q ∨ p ∨ ¬s ∨ ¬r ∨ ¬t ∨ u Answer: 64
d) (p ∧ r ∧ t) ↔ (q ∧ t) Answer: 16
2) Construct the truth table for each of the following compound propositions.

a) p → ¬q f) (p ∨ q) → (p ∧ q)
b) (p ∨ ¬r) ∧ (q ∨ ¬s)
g) (p → q) → (q → p)
c) p ∧ ¬p
h) (p → q) ∧ (q → p)
d) p ∨ ¬p
e) (p ∨ ¬q) → q i) p ∧ ¬p

p q ¬q p → ¬q
F F T T
a) F T F T
T F T T
T T F F
p q r s ¬r (p ∨ ¬r) ¬s (q ∨ ¬s) (p ∨ ¬r) ∧ (q ∨ ¬s)
F F F F T T T T T
F F F T T T F F F
F F T F F F T T F
F F T T F F F F F
F T F F T T T T T
F T F T T T F T T
F T T F F F T T F
b) F T T T F F F T F
T F F F T T T T T
T F F T T T F F F
T F T F F T T T T
T F T T F T F F F
T T F F T T T T T
T T F T T T F T T
T T T F F T T T T
T T T T F T F T T

2
 p ¬p p ∧ ¬p
c) F T F
T F F
p ¬p p ∨ ¬p
d) F T T
T F T
p q ¬q p ∨ ¬q (p ∨ ¬q) → q
F F T T F
e) F T F F T
T F T T F
T T F T T
p q p∨q p∧q (p ∨ q) → (p ∧ q)
F F F F T
f) F T T F F
T F T F F
T T T T T
p q p→q q→p (p → q) → (q → p)
F F T T T
g) F T T F F
T F F T T
T T T T T
p q p→q q→p (p → q) ∧ (q → p)
F F T T T
h) F T T F F
T F F T F
T T T T T
p ¬p p ∧ ¬p
i) F T F
T F F