Discrete Mathematics for Computer Scientists -- Exercises Week 2 - LogicDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Exercises Week 2 - Logic

Book: Chapter 1. Lectures: Thursday+Friday, week 1; Monday, week 2.

Some answers are available.

The idea is that you should prepare these exercises at home, by yourself or with your group. If you have any questions, you can come to the exercise session and ask them to the assistants. (If you do not prepare in advance, there is little point in coming!)

Note: You are encouraged to use logictools.org for any of these exercises where it is applicable!


Basic Exercises from the Book

Make sure you are comfortable with the following before you start the next exercises:

Chapter 1: 1.4, 1.5, 1.6, 1.10, 1.11, 1.16.


Exercises

Now, please think about these.

1. Think of three examples of propositions from your daily life that contain an implication (for example: "if it rains and the sun shines, then there is a rainbow"). Investigate under what conditions these propositions become false, and under what conditions they become true.


2. We are going to look at formulas that have the shape:

∀ x : (A(x) -> B(x))

(a.) Find an example of such a formula that is false. What do you have to do to show that the formula is false?

(b.) Find an example of such a formula that is true. What do you have to do to show that the formula is true?

(Don't forget to think about the universe.)


3. We are going to look at formulas that have the shape:

∃ x : (A(x) /\ B(x))

(a.) Find an example of such a formula that is false. What do you have to do to show that the formula is false?

(b.) Find an example of such a formula that is true. What do you have to do to show that the formula is true?

(Don't forget to think about the universe.)


4. The following formula shape:

∃ x : (A(x) -> B(x))
is not used so commonly in mathematics and logic. Can you investigate why?


5. Show how each of the following formulas can be expressed ONLY in terms of implication (->) and the constant false. Use truth tables to show the equivalences.

(a.) ~p ("not p")

(b.) p \/ q

(c.) p /\ q

(d.) p <-> q


6. The following boolean function:

median : 𝔹 x 𝔹 x 𝔹 -> 𝔹
computes the median of three arguments. (The median of three values is the value that would be in the middle if you put the three values in sorted order. For example, the median of (1,0,1) is 1, because sorting (1,0,1) gives (0,1,1), which puts 1 in the middle.)

(a.) Give the truth-table of the median function.

(b.) Show how the median function can be expressed in terms of the logical connectives we have seen in the course.

(c.) (*) What is the smallest formula expressing the median function?


7. Simplify the following formulas:

(a.) ~(p <-> q)

(b.) ~p <-> ~q

(c.) ~p -> ~q

Show that your answers are correct with a truth table.


8. (a.) Is logical implication (->) commutative and/or associative?

(b.) Is logical equivalence (<->) commutative and/or associative?


9. Are the following valid arguments? Explain.

(a.)
p -> q
q -> p
----------
p <-> q

(b.)
p -> r
~p -> r
----------
r

(c.)
p -> q
----------
q -> p

(d.)
p -> (q \/ r)
p -> ~q
------------
p -> r

(e.)
p -> q
q -> p
---------
p


10. Are the following valid arguments? Explain.

(a.)
∀ x : (A(x) -> B(x))
A(a)
---------------------------
B(a)

(b.)
∀ x : (A(x) -> B(x))
~B(a)
---------------------------
~A(a)

(c.)
∀ x : (A(x) -> B(x))
~A(a)
---------------------------
~B(a)


Starred Exercises

These exercises are for students who are looking for a challenge.

1*. The "MU-puzzle" by Douglas Hofstadter, as described in his book "Gödel, Escher, Bach":

There are three symbols: M, I, and U. From these symbols, we are going to make strings of symbols as follows:

0. We start with the string "MI".

1. If we already have a string that ends with the symbol I, we can form a new one by adding the symbol U at the end. (Example: if we have "MUUI", we can make "MUUIU".)

2. If we already have a string that starts with the symbol M, we can form a new one by duplicating all symbols after the M (copying them and attaching them to the end of the string). (Example: if we have "MUUI", we can make "MUUIUUI".)

3. If we already have a string where the 3 symbols III occur somewhere in a row, we can replace the III by a single U. (Example: if we have "MUIIIU", we can make "MUUU".)

4. If we already have a string where the 2 symbols UU occur somewhere in a row, we can remove those UU. (Example: if we have "MUUU", we can make "MU".)

Question: Can we make the string "MU"?


2*. The "sticks game" works as follows. We start with a pile of N sticks. You and I play against each other. We take turns; you start. You have to remove 1, 2, or 3 sticks from the pile (you choose). Now it's my turn: I have to remove 1, 2 or 3 sticks from the pile (I choose). We keep going until one of us HAS to take the last stick. That person has lost!

(a.) Show that if we start with 5 sticks, there is a way I can always win.

(b.) Show that if we start with 25 sticks, there is a way I can always win.

(c.) For what values of N can I always win? For what values of N can you always win?

(d.) Discuss the relevance of this game to the concept of invariants we learnt about in the lecture.