Instructor:

Joe Halpern, 4144 Upson, halpern@cs, 5-9562

Admin:

Cindy Robinson, 4146 Upson, cindy@cs, 5-0985

Grader:

Riccardo Pucella, 5151 Upson, riccardo@cs, 5-3042

Classes:

Tuesday, Thursday 10:10 - 11:25, Hollister 401

Office hours:

11:30-12:30 Tuesdsay, Thursday (or by appointment)

Text:

Reasoning About Knowledge (Fagin, Halpern, Moses, Vardi). (It should be available in the bookstore.) It will be out in paperback later this year, but too late for this course.

Grading:

There will be no tests or final examination. There will be problems handed out, typically 3 every Thursday, from the book. The grade will be based completely on your performance on the problems. Problems are always due two weeks after they're handed out. If you hand them in one week after they're handed out, I will grade them and return them the following week, and you get to hand them in again, to improve your grade. On a redo, you can get a maximum of 1 point less than the original value of the problem. (That is, if the problem was originally out of 10, the most you can get is 9.) I will take the higher grade.

Academic Integrity:

It's OK to discuss the problems with others, but you MUST write up solutions on your own, and understand what you are writing.

Course Outline:

We will be following the text very closely. Very roughly, we will be covering one chapter per week. Topics include modal logic, common knowledge, applying reasoning about knowledge in distributed systems (and economics, depending on interest), knowledge-based programming, dealing with logical omniscience, algorithmic knowledge.

A puzzle

Here's the puzzle I mentioned in class the other day:

The king's daughter had three suitors and couldn't decide which one to marry. So the king said, "I have three gold crowns and two silver crowns. I will put either a gold or silver crown on each of your heads. The suitor who can tell me which crown he has will marry my daughter." The first suitor looked around and said he could not tell. The second suitor did the same. The third suitor said "I have a gold crown." He was correct, bu the daughter was puzzled: This suitor was blind. How did he know?

Homework

• Week 1: handed out 9/4; due 9/18 (hand it in 9/11 for a second chance)
  • Read Chapters 1 and 2.
  • Do 1.2, 2.4 (ignore the comment in 2(d) about explaning why it's crucial to think of edges, not nodes, as disappearing), 2.11
    • Note that although 2.11 was included in the homework handed out in class, it was not on the web site for a few days. Please do it!
  • Solutions
• Week 2: handed out 9/11; due 9/25 (hand it in 9/18 for a second chance)
  • Read Section 3.1
  • Do 2.9, 2.10, 2.12 (I'm looking for semantic proofs of validity; don't use the axioms).
  • Solutions
• Week 3: handed out 9/18, due 10/2 (hand it in 9/25 for a second chance)
  • Read Sections 3.1-3.3
  • Do 3.10, 3.13, 3.14 (for 3.10 and 3.14, I'd like syntactic proofs, that is, a derivation from the axiom)
  • Solutions
  • Note: I told Riccardo that I didn't prove Kp & Kq => K(p&q) in class, but Piti pointed out that I did. If you lost 2 points for this, let me know and I'll reinstate them.
• Week 4: handed out 9/25; due 10/9 (hand it in 10/2 for a second chance)
  • Read all of Chapter 3 and Section 4.1
  • Do 3.17, 3.19, 3.20
  • Solutions
• Week 5: handed out 10/2; due 10/16 (hand it in 10/9 for a second chance)
  • Read all of Chapter 4
  • Do 4.9, 4.18, 4.20
  • Solutions
• Week 6: handed out 10/9; due 10/23 (hand it in 10/16 for a second chance)
  • Read Chapter 5
  • Do 4.25, 4.28, 5.7
  • Solutions
• Week 7: handed out 10/21; due 11/4 (hand it in 10/28 for a second chance)
  • Read Sections 6.1, 6.2
  • Do 6.2, 6.6, 6.13
  • Solutions
• Week 8: handed out 10/28; due 11/11 (hand it in 11/4 for a second chance)
  • Read Chapter 6
  • Do 6.15, 6.17, 6.21
  • Solutions
• Week 9: handed out 11/4; due 11/18 (hand it in 11/11 for a second chance)
  • Read Chapter 9
  • Do 9.8, 9.14, 9.22
  • Solutions
• Week 10: handed out 11/11 due 11/25 (hand it in 11/18 for a second chance)
  • Read Chapter 8, 9
  • Do 9.45, 8.5, 8.9
  • Solutions
• Week 11: handed out 11/18 due 12/2 (hand it in 11/25 for a second chance)
  • Read Chapter 7
  • Do 7.3, 7.4, 7.7
  • Solutions
• Week 12: handed out 11/25 due 12/4 (hand it in 11/25 for a second chance). NOTE THAT THIS ASSIGNMENT IS DUE THE LAST DAY OF CLASSES
  • Read Chapter 11
  • Do 7.26, 11.2
  • Solutions