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!)

Lectures: Thursday and Friday, week 1. Monday, week 2.

Read: Lehman, Leighton, and Meyer: Chapter 1, 3, and 6.1-6.2.

Some answers are available.

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

Chapter 1: Problems 1.3 (a,b), 1.10, 1.11, 1.13, 1.15.

Chapter 3: Problems 3.1, 3.2, 3.3, 3.4, 3.8, 3.11, 3.22, 3.23, 3.26, 3.34, 3.35.

We've made some extra exercises: predikatlogik övningar, skriva och bevis (pdf).

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.

What happens if you take the contrapositive of your implications? Are they still 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 set over which you quantify.)

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 set over which you quantify.)

4. The following formula shape:

∃ x . (A(x) => B(x))

5. Show how each of the following formulas can be expressed ONLY in terms of implication (->) and/or 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 𝔹 -> 𝔹

(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

Simplify: give a formula that means the same but is simpler. 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.) From p => q and q => p, can we conclude that p <=> q?

(b.) From p => r and ~p => r, can we conclude that r?

(c.) From p => q, can we conclude that q => p?

(d.) From p => (q \/ r) and ~p => ~q, can we conclude that p => r?

(e.) From p => q and q => p, can we conclude that p?

10. Are the following valid arguments? Explain.

(a.)From ∀ x . (A(x) => B(x)) and A(a), can we conclude B(a)?

(b.)From ∀ x . (A(x) => B(x)) and ~B(a), can we conclude ~A(a)?

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.