CS 6764: Reasoning About Knowledge - Spring 2012
- Instructor: Joe Halpern, 4130 Upson, halpern@cs, 5-9562
- Admin: Michelle Eighmey, 4130B Upson, meigh68@cs, 4-6559;
Gina Miller, 4130 Upson, gina@cs, 5-0983
- TA: Adam Bjorndahl, Malott 218, abjorndahl@math.cornell.edu.
- Classes:Tuesday, Thursday 10:10 - 11:25; Upson 215
- Office hours
- Halpern: Wednesdays, 4:30 - 5:30
- Bjorndahl: Tuesdays, 1-2 [Note change!]
- Text: Reasoning About Knowledge (Fagin, Halpern, Moses, Vardi).
(It should be available in the bookstore. The paperback version is
best, but the hardcover version is OK too. The paperback version
corrects a number of typos and minor errors in the hardcover version.)
- 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. You can then redo any problem that
you
seriously attempted and hand it 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.
- Webpage: The course URL is
http://www.cs.cornell.edu/courses/cs6764/2012fa. Assignments will be
posted there, as well as other class information.
- 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
Note: you can find your grades and solutions to the homework at
CMS.
Week 1: handed out 1/26; due 2/9 (hand it in 2/2 for a second chance)
- Read Chapters 1 and 2.
- Do 1.2, 2.4, 2.11. (If you have the hardcover version of the text,
ignore the comment in part 2.4(d) about edges disappearing; this comment
does not appear in the paperback version (for good reason).
- In class I said that the homework was 1.2, 2.4, and 2.9 (not
2.11). You can do either of 2.9 or 2.11 this week; the other one will
be homework next week. Sorry about the confusion.
- If you haven't gotten a copy of the text, Chapters 1 and 2 can be
found here.
Week 2: handed out 2/2; due 2/16 (hand it in 2/9 for a second
chance)
- Do whichever of 2.9 or 2.11 you haven't done yet, 2.12, 3.10, and
3.14. For 2.12 I want a semantic proof. Don't use the axioms.
Rather, you should do proofs in the style of the other proofs in Chapter
2, where you talk about what formulas are true at various states.
You can assume that the \K_i relations are equivlaence relations,
because that's what's assumed in Chapter 2. On the other hand, for
3.10(b), (c) and 3.14, I want a syntactic proof. That is, you should
show explicitly how the relevant formulas are derivable from the axioms
(without appealing to any of the soundness and completeness theorems).
Week 3: handed out 2/9; due 2/23 (hand it in 2/16 for a second
chance)
- Read Chapter 3
- Do 3.13, 3.17, 3.20.
Week 4: handed out 2/16; due 3/1 (hand it in 2/23 for a second
chance)
- Read Chapter 4
- Do 4.9, 4.18, 4.20
Week 5: handed out 2/23; due 3/8 (hand it in 3/1 for a second
chance)
- Read Chapter 4
- Do 4.24, 4.25, 4.28
Week 6: handed out 3/1; due 3/15 (hand it in 3/8 for a second
chance)
- Read Chapter 6.1, 6.2
- Do 6.2, 6.6, 6.8, 6.13
Week 7: handed out 3/8; due 3/29 (hand it in 3/15 for a second
chance)
- Read Chapter 6.3 - 6.6
- 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 3/15; due 4/5 (hand it in 3/29 for a second
chance)
- Read Chapter 7
- Do 7.3, 7.4, 7.7
Week 9: handed out 3/29; due 4/12 (hand it in 4/5 for a second
chance)
- Read Chapter 8
- Do 8.5, 8.9
Week 10: handed out 4/5; due 4/19 (hand it in 4/12 for a second
chance)
- Read Chapter 9.1 - 9.4
- Do 9.8, 9.14, 9.22
Week 11: handed out 4/12; due 4/26 (hand it in 4/19 for a second
chance)
- Read Chapters 9 and 10, 11.1
- Do 9.25, 9.42, 9.45
Week 12: handed out 4/19; due 5/3 (hand it in 4/26 for a second
chance -- note that this is the last homework)
- Read Chapters 11
- Do 9.49 [5 points], 10.3 [5 points], 11.2; also show that every
a.m.p and a.r.m.p has temporal imprecision.