Epistemic logic would probably be the appropriate tool; at least that's what I thought when I first saw the problem. Epistemic logic is the logic of knowledge and belief: you use a modal operator to express the knowledge of an agent about a certain statement. The statement could be expressed in propositional or first-order logic depending on the expressiveness required (but of course there is a complexity trade-off).
Translating roughly from the problem statement (x being the variable holding Cheryl's birthday):
Not(Know_Albert(x)) and Know_Albert(Not(Know_Bernard(x)
etc.
Semantically, the possible birthdays correspond to the possible worlds. A reasoner would be able to solve this by process of elimination, somewhat similarly to a constraint-solver.
Translating roughly from the problem statement (x being the variable holding Cheryl's birthday):
Not(Know_Albert(x)) and Know_Albert(Not(Know_Bernard(x) etc.
Semantically, the possible birthdays correspond to the possible worlds. A reasoner would be able to solve this by process of elimination, somewhat similarly to a constraint-solver.
Resources:
Wikipedia entry on Epistemic Logic: http://en.wikipedia.org/wiki/Epistemic_modal_logic
Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge: http://www.amazon.com/Reasoning-About-Knowledge-Ronald-Fagin...
I haven't read the entire book, but the first couple of chapters give you an idea and some great examples not too different from this puzzle.