CS代写 | COM2107 Logic in Computer Science Exercise Sheet 1


COM2107 Logic in Computer Science Exercise Sheet 1

Question 1.1 Translate the following sentences into propositional logic. How well do your
translations capture their meaning?
(a) Smith is away or Jones is ill, but not both.
(b) If the sun shines today, it won’t shine tomorrow.
(c) If Fido attacks you he’s either angry or frustrated.
(d) I want vanilla and strawberry ice cream.
(e) I like to program unless it is in Java.
(f) John is nice, but not very clever.
(g) Mary is happy because she passed the exam.
Question 1.2 Use truth tables to determine the meaning of the following formulas. Those for
:, _, ^ and ! can be found in Section 1.4 of Huth and Ryan’s book. A formula ‘ $ is true
if and only if ‘ ! and ! ‘ are both true.
1. p _ :p,
2. p ! (q ! p),
3. (p ! q) _ (:p ! q),
4. (p ! (q ! r)) ! ((p ! q) ! (p ! r)),
5. ((p ^ q) ! r) $ (p ! (q ! r)).
Question 1.3 The object language of propositional logic is propositional logic itself. The
metalanguage in which we speak about propositional logic is English. We can also use English
as a metalanguage to speak about English as an object language; or we can use expressive logics
as a metalanguage for an object logic. As an example, indicate the object and metalanguage
parts in the following sentence, which I found in a Sheeld school some years ago:

Question 1.4 A formula is valid if it is true under all interpretations of its propositional
variables. What about the following formula?
p $ (p $ (p $ (p $ (p $ (p $ (p $ (p $ (p $ (p $ (p $ p))))))))))
[Hint: This looks like a boring exercise, so try to nd a clever solution. Look for patterns be-
tween small subproblems. Then turn what you see into a proof.]
Question 1.5 A line of 50 coins of di erent value is laid out on a table. Alice and Bob take
turns in picking one coin from either end of the line. Alice makes the rst move, and both
players can chose at which end to pick before each of their moves. The game is over when the
table is empty. Can Alice always win at least as much money as Bob?
[Hint: Look for a simple winning strategy that works for all possible games. Don’t try to
maximise Alice’s pro t. We are logicians, not bankers.]