Seminar Seminar "Puzzles and Paradoxes in Logic and Probability"
[go to overview]Winter Terms 2019 / 2020
Introduction
Research in logicbased artificial intelligence regularly draws inspiration from puzzles and paradoxes. Puzzles sharpen our understanding of what it takes to reason towards a solution, and are therefore excellent points of reference for developing and applying logical formalisms. This is especially true for the study of epistemic reasoning, or reasoning about knowledge, which abounds in thought provoking puzzles, often with surprising solutions. Paradoxes occur when seemingly sound reasoning leads to absurd conclusions. Paradoxes provide valuable insights, as they highlight the pitfalls and limitations that are inherent in the enterprise of formal reasoning. The bestknown paradox is perhaps the liarparadox: consider the statement "This statement is false". If this statement is true, then it must be false, and if it's false, then it must be true. This paradox teaches us about the dangers of selfreference and reasoning about truth.
Above all, puzzles and paradoxes are fun! They not only have academic value, but also serve as excellent topics for discussion among friends and family.
In this seminar you will give a presentation and write a report on one of the available topics. Each topic is about a puzzle or paradox. You are expected to present the puzzle or paradox and explain how it relates to logic or reasoning, how it is formalised, and what its relevance is in the broader context of AI.
This seminar is suitable for all students with basic knowledge of knowledge representation and reasoning (for example those who followed Artificial Intelligence 1). A number of topics furthermore require basic knowledge of probability theory.
Topics
The list of topics below is preliminary. Additional topics and references will be added later.
Puzzles and paradoxes that involve epistemic reasoning (reasoning about knowledge):

The Sum Product Puzzle Also called the impossible puzzle because it appears to be impossible. But epistemic reasoning provides the solution [10].

The Muddy Children Puzzle This puzzle is based on the effect of what is called common knowledge [9].

The Russian Cards Problem Epistemic reasoning with applications to secure communica tions and cryptographic protocols [8, 9].

The Surprise Examination Paradox (also called Unexpected Hanging Paradox) Epistemic reasoning gone astray. But where’s the mistake? [4, 9]
Puzzles and paradoxes of logic:

The Lottery Paradox A paradox that demonstrates a fundamental problem in modelling a wellbehaved notion of belief (as opposed to knowledge) in logic [11]. (Optional: also discuss Preface Paradox)

Paradoxes of Material Implication The material implication φ → ψ (which is equivalent to ¬φ ∨ ψ) is often thought mean “if φ then ψ” but behaves in counterintuitive ways! [1].
Puzzles and paradoxes of probability:

The Monty Hall and Three Prisoner paradoxes These paradoxes are similar and deal with problems you run into when you update probabilities in a naive way. [2, 5]

Simpson’s Paradox A wellknown phenomenon in statistics that is very relevant to AI and data science [6, 7].
Organization
The introductory meeting will take place on 25/10/2019, 10:0012:00 in room F522.
The seminar will be held in two or three seminar slots (depending on number of participants) on:
 18/02/2020, 10:0013:00, in room F522
 19/02/2020, 09:0012:00, in room F522
 20/02/2020, 10:0013:00, in room C209
Attendance of the meeting as well as all seminar slots is obligatory.
References

[1] Lewis Carroll and Margaret Washburn. A logical paradox. Mind, 3(11):436–438, 1894.

[2] Wikipedia Contributors. Monty hall problem, 2019. https://en.wikipedia.org/wiki/Monty_Hall_problem

[3] Eugene Curtin and Max Warshauer. The locker puzzle. The Mathematical Intelligencer, 28 (1):28–31, 2006.

[4] Jelle Gerbrandy. The surprise examination in dynamic epistemic logic. Synthese, 155(1): 21–33, 2007.

[5] Peter D Grunwald and Joseph Y Halpern. Updating probabilities. Journal of Artificial Intelligence Research, 19:243–278, 2003.

[6] Eric Neufeld. Simpson’s paradox in artificial intelligence and in real life. Computational intelligence, 11(1):1–10, 1995.

[7] Judea Pearl. Comment: understanding simpson’s paradox. The American Statistician, 68(1): 8–13, 2014.

[8] Hans Van Ditmarsch. The russian cards problem. Studia logica, 75(1):31–62, 2003.

[9] Hans Van Ditmarsch and Barteld Kooi. The secret of my success. Synthese, 151(2):201–232, 2006.

[10] Hans P van Ditmarsch, Ji Ruan, and Rineke Verbrugge. Sum and product in dynamic epistemic logic. Journal of Logic and Computation, 18(4):563–588, 2007.

[11] Gregory Wheeler. A review of the lottery paradox. Probability and inference: Essays in honour of Henry E. Kyburg, Jr, pages 1–31, 2007.