Discrete Mathematics/Logic/Answers

Answers to Logic Exercise 1

1

(a) is not a proposition. (It is a command, or imperative.)

(b) and

(c) are both propositions.

(d) is not a proposition; it's a question.

(e) strictly speaking is a propositional function, but many people would say it is a proposition.

(f) is not a proposition, because the result can be either true or false, it depends on the values of a & b.

2

Noting that p is false (1024 bytes is known as 1KB) and q is true, we have:

(a) "1024 bytes is known as 1MB and a computer keyboard is an example of a data input device". False.

(b) "(Either) 1024 bytes is known as 1MB or a computer keyboard is an example of a data input device". True.

The word Either here is optional; it doesn't have - and doesn't need - an equivalent symbol in Logic.

(c) "1024 bytes is not known as 1MB". True.

3

(a) x ≥ 50

(b) x ≤ 40

(c) 40 < x < 50

(d) x < 50 or x > 40. This is true for all values of x.

(e) x ≥ 50 (Note that we don't need to say, in addition, that x > 40; this must be true whenever x ≥ 50.)

(f) x ≥ 50 and x ≤ 40. This can never be true, whatever the value of x.

So (d) is a tautology – it's always true; and (f) is always false.

4

(a) I don’t like Maths, but I’m going to spend at least 6 hours a week on Maths.

(This sounds much more natural than "I don’t like Maths, and I’m going to spend at least 6 hours a week on Maths.")

(b) Either I don’t like Maths, or I’m going to spend at least 6 hours a week on Maths.

(c) It’s not true that I don’t like Maths. (Or simply: I do like Maths.)

(d) Either I don’t like Maths, or I’m not going to spend at least 6 hours a week on Maths.

(It's not very easy to get a natural sounding sentence here. It probably helps to include the word "Either", but it's not essential.)

(e) It’s not true that either I like Maths or I’m going to spend at least 6 hours a week on Maths. Or, simply: I neither like Maths, nor am I going to spend at least 6 hours a week on Maths.

Alternatively, you can write the answer to (f), which is…

(f) I don’t like Maths and I’m not going to spend at least 6 hours a week on Maths.

5

(a) (ii)

(b) (i) and (iii)

(c) (iii)

Back to Logic Exercise 1

Answers to Logic Exercise 2

1

(a)

p	q	¬p	¬q	¬p ∨ ¬q
T	T	F	F	F
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

(b)

p	q	q $\scriptstyle \wedge$	¬p	∨q
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	F	T	T
		(3) output	(1)	(2)

(c)

p	q	r	p $\scriptstyle \wedge$	(q ∨ r)
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	F	T
F	T	F	F	T
F	F	T	F	T
F	F	F	F	F
			(2) output	(1)

(d)

p	q	r	(p $\scriptstyle \wedge$ q)	∨ r
T	T	T	T	T
T	T	F	T	T
T	F	T	F	T
T	F	F	F	F
F	T	T	F	T
F	T	F	F	F
F	F	T	F	T
F	F	F	F	F
			(1)	(2) output

2

Both results columns are the same: T, T, T, F.

3

Both results are T, F, F, F

Back to Logic Exercise 2

Answers to Logic Exercise 3

1

(a) Yes; both results columns give T, T, T, F

(b) No; first is F, T, T, F; second is T, F, F, T

2

(a) F, T, T, T, T, T, T, T.

This is the negation of T, F, F, F, F, F, F, F which is true only when a, b and c are all true. So the expression is equivalent to ¬(a $\scriptstyle \wedge$ b $\scriptstyle \wedge$ c)

(b) T, T, T, T, F, F, F, F, T, T, T, T, F, F, F, F.

This is identical to the column for b, so the expression is equivalent to b.

3

(a) a ∨ b

(b) a ∨ b

(c) q ∨ p

4

Result is T, T, T, T. So it is always true

5

((p ∨ q) $\scriptstyle \wedge$ ¬(p $\scriptstyle \wedge$ q)) $\scriptstyle \wedge$ ¬r

6

In each case, the result is F, F, F, F, T, T, F, F

7

(z $\scriptstyle \wedge$ w) ∨ (¬z $\scriptstyle \wedge$ w) ∨ (z $\scriptstyle \wedge$ ¬w)	= (z $\scriptstyle \wedge$ w) ∨ (z $\scriptstyle \wedge$ ¬w) ∨ (¬z $\scriptstyle \wedge$ w)	Commutative Law
	= (z $\scriptstyle \wedge$ (w ∨ ¬w)) ∨ (¬z $\scriptstyle \wedge$ w)	Distributive Law
	= (z $\scriptstyle \wedge$ T) ∨ (¬z $\scriptstyle \wedge$ w)	Complement Law
	= z ∨ (¬z $\scriptstyle \wedge$ w)	Identity Law
	= (z ∨ ¬z) $\scriptstyle \wedge$ (z ∨ w)	Distributive Law
	= T $\scriptstyle \wedge$ (z ∨ w)	Complement Law
	= (z ∨ w) $\scriptstyle \wedge$ T	Commutative Law
	= z ∨ w	Identity Law

Back to Logic Exercise 3

Answers to Logic Exercise 4

1

(a) ¬p

(b) ¬s $\scriptstyle \wedge$ p

(c) p ⇒ r

(d) r ⇒ (q $\scriptstyle \wedge$ p)

(e) I shall work for forty hours this week, or I’ll finish my Coursework Assignment.

(f) If I shall not finish my Coursework Assignment, then I shan’t pass Maths.

2

The table shows only the result column in each case:

		(a)	(b)	(c)	(d)	(e)
p	q	p ⇒ (p ∨ q)	(p ⇒ q) ⇒ (q ⇒ p)	(p $\scriptstyle \wedge$ (p ⇒ q)) ⇒ q	(p $\scriptstyle \wedge$ q) ⇒ p	q ⇔ (¬p ∨ ¬q)
T	T	T	T	T	T	F
T	F	T	T	T	T	F
F	T	T	F	T	T	T
F	F	T	T	T	T	F

So the results are:

(a) Yes, always true

(b) No

(c) Yes

(d) Yes

(e) No

3

The result column in each case is T, F, T, T. So the propositions are all logically equivalent.

Answers to Logic Exercise 5

1 friend(Jimmy)

2 wealthy(Sue) $\scriptstyle \wedge$ clever(Sue)

3 wealthy(Jane) $\scriptstyle \wedge$ ¬clever(Jane)

4 friend(Mark) $\scriptstyle \wedge$ friend(Elaine)

5 friend(Peter) ⇒ ¬boring(Peter)

6 (wealthy(Jimmy) $\scriptstyle \wedge$ ¬boring(Jimmy)) ⇒ friend(Jimmy)

Back to Logic Exercise 5

Answers to Logic Exercise 6

1

(a) ∃ x, friend(x) $\scriptstyle \wedge$ clever(x)

(b) ∀x, clever(x) ⇒ boring(x)

(c) ∀x, friend(x) ⇒ ¬wealthy(x)

OR: ¬(∃ x, friend(x) $\scriptstyle \wedge$ wealthy(x))

(d) ∃x, friend(x) $\scriptstyle \wedge$ wealthy(x) $\scriptstyle \wedge$ clever(x)

(e) ∀x, (clever(x) $\scriptstyle \wedge$ friend(x)) ⇒ boring(x)

(f) ∀x, clever(x) ⇒ (boring(x) ∨ wealthy(x))

2

(a) popstar(x) is "x is a pop-star"

overpaid(x) is "x is overpaid"

∀x, popstar(x) ⇒ overpaid(x)

(b) pilot(x) is "x is an RAF pilot"

woman(x) is "x is a woman"

∃x, pilot(x) $\scriptstyle \wedge$ woman(x)

(c) student(x) is "x is a student"

rolls(x) is "x owns a Rolls-Royce"

∀ x, student(x) ⇒ ¬rolls(x)

OR: ¬(∃ x, student(x) $\scriptstyle \wedge$ rolls(x))

(d) doctor(x) is "x is a doctor"

write(x) is "x can write legibly"

∃ x, doctor(x) $\scriptstyle \wedge$ ¬write(x)

Back to Logic Exercise 6

Answers to Logic Exercise 7

1

(a) Universe of discourse: {people}

programmer is "… is a computer programmer"

spreadsheets is "… can understand spreadsheets"

∃ x, programmer(x) $\scriptstyle \wedge$ ¬ spreadsheets(x)

(or if universe of discourse is {computer programmers}, ∃ x, ¬spreadsheets(x))

(b) Universe of discourse: {people}

prisoner is "… is a prisoner"

fairTrial is "… deserves a fair trial"

∀ x, prisoner(x) ⇒ fairTrial(x)

(or if universe of discourse is {prisoners}, ∀ x, fairTrial(x))

(c) Universe of discourse: {people}

intelligent is "… is intelligent"

palace is "… supports Crystal Palace Football Club"

∃ x, intelligent(x) $\scriptstyle \wedge$ palace(x)

(d) Universe of discourse: {people}

stupid is "… is stupid"

curry is "… likes curry"

∃ x, stupid(x) $\scriptstyle \wedge$ ¬curry(x)

(e) Universe of discourse: {university students}

goodLooking is "… is good-looking"

intelligent is "… is intelligent"

∀ x, goodLooking(x) ∨ intelligent(x)

(f) Universe of discourse: {cars}

noisy is "… is noisy"

dirty is "… is dirty"

¬(∀ x, noisy(x) $\scriptstyle \wedge$ dirty(x))

Or: ∃ x, ¬noisy(x) ∨ ¬dirty(x)

2

(a) Some Boy Scouts cheat at cards.

(b) All people with punk hair cheat at cards.

(c) No Boy Scouts have punk hair or cheat at cards.

(d) Some people who cheat at cards don’t have punk hair.

3

(a) Universe of discourse: {cows}

eats is "… eats …"

∀ x, eats(x, grass)

(b) Universe of discourse: {people}

better is "… is better at Maths than …"

∃ x, better(Harry, x)

(c) Universe of discourse: {people}

likes is " … likes …"

∃ x, likes(x, the Rolling Stones)

(d) Universe of discourse: {people}

expects is "… expects …"

¬(∃ x, expects(x, the Spanish Inquisition))

Or: ∀ x, ¬expects(x, the Spanish Inquisition)

Back to Logic Exercise 7