## Homework 1

Homework 1 is due on Monday, May 24th.

1. Read Chapter 1 and 4.1, 4.2. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:

• Found most difficult
• Found most surprising
• Would like to have discussed in the next lecture

2. Prove or disprove:

$(A \vee B)\wedge(A \vee C \vee \neg B) \equiv (B \wedge C) \vee (A \wedge \neg B) \vee (A \wedge \neg C)$

3. Working at the local pizza parlor, I have a stack of unbaked pizza doughs. For a most pleasing presentation, I wish to arrange them in order of size, with the largest pizza on the bottom. I’m able to place my spatula under one of the pizzas and flip over the whole stack above the spatula (reversing their order). This is the only move I can do to change the order of the stack; however, I am willing to keep repeating this move until I get the stack in order. Is it always possible for me to get the pizzas in order? Prove your answer.

4. Explain what’s wrong with this reasoning: The students set off home for the weekend. Their teacher said: “You shall have an examination at nine in the morning one day next week; but you will not know in advance which day-it will be a surprise.” “Suppose,” thought one to herself with the desperation available only to the damned and the examinable: “Suppose we were still unexamined until Friday. I know there will be an examination some time this week, and so I would be able to expect the Friday examination. Therefore the teacher cannot possibly leave it until Friday.”  “Suppose further,” she thought to herself: “Suppose that I am still unexamined on Thursday. I know the examination cannot be on Friday, so it would have to come on Thursday. But then too I would have been able to predict its day. So, the teacher cannot leave it until Thursday either. Or Wednesday… or Tuesday… or Monday.. In fact, he cannot possibly set any examination at all, since no day would be a surprise!” And when the teacher handed out exam papers at nine o’clock on Wednesday morning — wasn’t she surprised!

5. Project idea: Investigating Automated Theorem Provers.