Discrete Mathematics/Logic/Answers
From Wikibooks, open books for an open world
Contents
Answers to Logic Exercise 1[edit]
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[edit]
1
(a)
p | q | ¬p | ∨ | ¬q |
T | T | F | F | F |
T | F | F | T | T |
F | T | T | T | F |
F | F | T | T | T |
(1) | (3)
output |
(2) |
(b)
p | q | q | ¬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 | (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) |
(c)
p | q | r | (p 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[edit]
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 b 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) ¬(p q)) ¬r
6
- In each case, the result is F, F, F, F, T, T, F, F
7
(z w) ∨ (¬z w) ∨ (z ¬w) | = (z w) ∨ (z ¬w) ∨ (¬z w) | Commutative Law |
= (z (w ∨ ¬w)) ∨ (¬z w) | Distributive Law | |
= (z T) ∨ (¬z w) | Complement Law | |
= z ∨ (¬z w) | Identity Law | |
= (z ∨ ¬z) (z ∨ w) | Distributive Law | |
= T (z ∨ w) | Complement Law | |
= (z ∨ w) T | Commutative Law | |
= z ∨ w | Identity Law |
Back to Logic Exercise 3
Answers to Logic Exercise 4[edit]
1
- (a) ¬p
- (b) ¬s p
- (c) p ⇒ r
- (d) r ⇒ (q 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 (p ⇒ q)) ⇒ q | (p 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[edit]
1 friend(Jimmy)
2 wealthy(Sue) clever(Sue)
3 wealthy(Jane) ¬clever(Jane)
4 friend(Mark) friend(Elaine)
5 friend(Peter) ⇒ ¬boring(Peter)
6 (wealthy(Jimmy) ¬boring(Jimmy)) ⇒ friend(Jimmy)
Back to Logic Exercise 5
Answers to Logic Exercise 6[edit]
1
- (a) ∃ x, friend(x) clever(x)
- (b) ∀x, clever(x) ⇒ boring(x)
- (c) ∀x, friend(x) ⇒ ¬wealthy(x)
- OR: ¬(∃ x, friend(x) wealthy(x))
- (d) ∃x, friend(x) wealthy(x) clever(x)
- (e) ∀x, (clever(x) 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) 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) rolls(x))
- (d) doctor(x) is "x is a doctor"
- write(x) is "x can write legibly"
- ∃ x, doctor(x) ¬write(x)
Back to Logic Exercise 6
Answers to Logic Exercise 7[edit]
1
- (a) Universe of discourse: {people}
- programmer is "… is a computer programmer"
- spreadsheets is "… can understand spreadsheets"
- ∃ x, programmer(x) ¬ 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) palace(x)
- (d) Universe of discourse: {people}
- stupid is "… is stupid"
- curry is "… likes curry"
- ∃ x, stupid(x) ¬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) 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