C676: Reasoning About Knowledge - Fall 2007
- Instructor:
- Joe Halpern, 4144 Upson, halpern@cs, 5-9562
- Admin:
- Cindy Robinson, 4146 Upson, cindy@cs, 5-0985
- Grader:
- David Martin, 4104 Upson, djm@cs 5-9537
- Classes:
- Tuesday, Thursday 2:55-4:10
- Office hours:
- Halpern: Tuesday, 1:30 - 2:50
- Martin: Wednesday, 4:30 - 6
- Text:
- Reasoning About Knowledge (Fagin, Halpern, Moses, Vardi).
The paperback version corrects some typos and other problems in the
hardcover version, so it's a better choice, all things being equal. If
you're using the hardcover version, let me know.
- 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. List on your solutions everyone you
worked with.
- 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.
Homework
- Week 1: handed out 8/30; due 9/13 (hand it in 9/6 for a second chance)
- Read Chapters 1 and 2.
- Do 1.2, 2.4, 2.11
- Week 2: handed out 9/6; due 9/20 (hand it in 9/13 for a second chance)
- Read Chapter 3
- Do 2.12, 3.10, 3.13, 3.14. (For 2.12 I want a semantic proof; don't
use the axioms. On the other hand, in 3.10(b),(c) and 3.14, I want a
derivation from the axioms, not a semantic proof. In 2.12, you should
assume that the \K_i relations are equivalence relations (because this
is the assumption made throughout Chapter 2.)
- Week 3: handed out 9/13; due 9/27 (hand it in 9/20 for a second chance)
- Read Chapter 4.1, 4.2
- Do 2.9(b), 2.10(d), 3.17, 3.20
- Week 4: handed out 9/20; due 10/4 (hand it in 9/27 for a second chance)
- Read Chapter 4
- Do 4.9, 4.18, 4.20
- Week 5: handed out 9/27; due 10/11 (hand it in 10/4 for a second chance)
- Read Chapter 5 and 6.1
- Do 4.25, 4.28, 5.7 (If you use 4.24 in your proof of 4.25(b), you
should prove it).
- Week 6: handed out 10/4; due
10/18 (hand it in 10/11 for a second chance)
- Read Chapter 6.2 and 6.3
- Do 6.2, 6.6, 6.8, 6.13
- Week 7: handed out 10/11; due
10/25 (hand it in 10/18 for a second chance)
- Read Chapter 6.4 and 6.5
- Do 6.14(a),(c),(e), 6.16, 6.19, 6.23. (If you have the hardcover
version of the book, the numbers are different. You should do 6.12,
6.15, 6.17, and 6.21 in the hardcover version.)
- Week 8: handed out 10/18; due
11/1 (hand it in 10/25 for a second chance)
- Read Chapter 7
- Do 7.3, 7.4, 7.7
- Week 9: handed out 10/25; due
11/1 (hand it in 11/1 for a second chance)
- Read Chapter 8, 9.1-9.2
- Do 8.5, 8.9, 9.8
- Week 10: handed out 11/1; due
11/15 (hand it in 11/8 for a second chance)
- Read Chapter 9
- Do 9.14, 9.22, 9.45
- Week 11: handed out 11/8; due
11/27 (hand it in 11/15 for a second chance)
- Read Chapter 10
- Do 9.10, 9.25, 9.42
- Week 12: handed out 11/15; due
11/29 (hand it in 11/27 for a second chance)
- Read Chapter 11
- Do 9.49 [5 points], 10.3 [5 points], 11.2; also show that every
a.m.p. system and every a.r.m.p system has temporal imprecision.