CS 6764: Reasoning About Knowledge - Spring 2015
- Instructor: Joe Halpern, 414 Gates, halpern@cs.cornell.edu, 5-9562
- Admin:Randy Hess, 323 Gates, rbhess@cs.cornell.edu, 5-0985;
- TAs:, Nan Rong and Samantha Leung
- Office hours
- Halpern: Wednesdays, 1:30 - 2:30, 414 Gates
- Rong and Leung: Tuesdays, 3-4, G17 Gates
- 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.
- 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/29; due 2/12 (hand it in 2/5 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.)
Week 2: handed out 2/5; due 2/19; hand it in 2/12 for a second
chance)
- Read Chapters 3.1 and 3.2
- Do 2.9, 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/12; due 2/26 (hand it in 2/19 for a second
chance)
- Read Chapter 3
- Do 3.13(c),(d),(e),3.16, 3.17, 3.20. (I did 3.13(c) iin class, but it's
a good exercise to write out.)
- If you handed in homework 1 last week, please email Nan
(rongnan@cs.cornell.edu) your grade. (We're going on the honor system,
but Nan does remember most of the grades ...)
Week 4: handed out 2/19; due 3/5 (hand it in 2/26 for a second
chance)
- Read Chapter 4
- Do 4.9, 4.18, 4.20
Week 5: handed out 2/26; due 3/11 (hand it in 3/4 for a second
chance)
- Read Chapter 4
- Do 4.24, 4.25, 4.28. (Warning: some of these problems require
thought. Don't leave it to the last minute!). Note that there is a
typo in 4.24. On line 4 of p.156, it should say r(m'-k), not r(m-k).
A complete list of known typos can be found at
http://mitpress.mit.edu/books/reasoning-about-knowledge. (Click on the
"errata" link on the left-hand side of the page.)
I would be happy to hear about other typos that you find.
Week 6: handed out 3/5; due 3/19 (hand it in 3/12 for a second
chance)
- Read Chapters 5 and 6.1
- Do 5.11, 6.2
- You can now hand in homework on CMS.
Week 7: handed out 3/12; due 3/26 (hand it in 3/19 for a second
chance)
- Read Chapter 6
- Do 6.6, 6.8, 6.13
- You can now hand in homework on CMS.
Week 8: handed out 3/19; due 4/9 (hand it in 3/26 for a second
chance)
- Do 6.14, 6.16, 6.19, 6:23
- The Ariel Rubinstein paper that I talked about in the last class
can be found here.
The paper is short and fun to read. I strongly encourage you to take a look.
Week 9: handed out 3/26; due 4/16 -- three weeks from now, because of
spring break (had it in 4/10 for a second chance).
- Read Chapter 7
- Do 7.3, 7.4, 7.7
- The paper that adds counterfactuals to knowledge-based programs can
be found here;
the slides for a talk on the paper are here.
Week 10: handed out 4/9; due 4/23 (had it in 4/16 for a second chance).
- Read Chapter 8, 9.1-9.3
- Do 8.5, 8.9, 9.8, 9.14
Week 11: handed out 4/16; due 4/30 (had it in 4/23 for a second
chance).
- Read Chapter 9
- Do 9.22, 9.42, 9.45
- The puzzle briefly discussed in class on Tuesday can be found
here.
If elementary school students can do it, you should be able to too
(especially since they don't have the benefit of knowing about Kripke
structures, which really help!)
- Update #1: Apparently, this was not intended for elementary school students,
but was a problem on the Math Olympiad.
(Details can be found here;
thanks to Jun Le for pointing this out.) You should still be able to do
it easily though!
- Update #2:
Here is a version that's not so easy (see me if you'd
like some hints):
Week 12: handed out 4/23; due 4/7 (either email it to Nan or Sam,
post it on CMS or hand or hand it in in class on 4/5; hand it in 4/30
for a second chance). This is the last homework!
- Read Chapters 10 and 11
- Do Do 9.49 [5 points], 10.3 [5 points], 11.2; also show that every
a.m.p and every a.r.m.p has temporal imprecision.
- The slides that I used in the last two classes can be found
here. The material on which the talk is based
can be found
here and
here.
Parting comments:
- You can find some discussion of characterizing solution concepts in
terms of common knowledge of rationality
here.
- As Michael Usher pointed out, for the question asking you to show
that amps and armps display temporal imprecision, you have to assume
that messages take at least one round to arrive. Sorry about that!
- I should be able to post grades sometime towards the end of next
week. I'll send out an email when they're available.
- Thanks again for being a great class!