EPFL Fall 2011: Logic and Probability

Doctoral course by Val Tannen

Lecture notes 1 (pdf)

Homework 1 (pdf)

Lecture notes 2 (pdf)

Lecture notes 3 (pdf)

Lecture notes 4 (pdf)

Homework 2 (pdf)

Lecture notes 5 (revised) (pdf)

Lecture notes 6 (pdf)

Lecture notes 7 (pdf)

Course Materials

“Models for Incomplete and Probabilistic Information” Green and Tannen (pdf)

Old lecture notes on computability (pdf)

“On the Unusual Effectiveness of Logic in Computer Science” Halpern, Harper, Immerman, Kolaitis, Vardi, and Vianu“ (pdf)

Syllabus

• Introduction
  • Truth, proof, and computation: some basic results about first-order logic
  • A bit of the story of how Mathematical Logic (and Electronic Technology) gave birth to Computer Science.

• Part I: Probability of Logic
  • Random graphs and random structures
  • 0-1 laws
  • Queries on probabilistic databases

• Part II: Logic of Probability
  • Pearl-Paz logics for reasoning about probabilistic (in)dependence
  • Reasoning about independence in Bayesian and Markov networks; the Hammersley-Clifford theorem
  • Reasoning about independence in relational graphical models (PRMs and RMNs)

Some useful books

I will rely on basic results about computability and complexity that are (usually) covered in a Computer Science undergraduate curriculum. If you need to freshen up on these topics, I can recommend:

• “Introduction to the Theory of Computation”, Sipser, PWS 1997.
• “Introduction to Automata Theory, Languages, and Computability”, Hopcroft, Motwani, and Ullman, 2nd edition, Addison-Wesley 2001.
• “Computational Complexity”, Papadimitriou, Addison-Wesley 1994.
• “Computational Complexity: A Modern Approach”, Arora and Barak, Cambridge University Press 2009.
• I have also made available my own notes on computability (see above).

There many textbooks on logic but let me recommend my favorites:

• “Logic for Computer Science”, J. Gallier, (Wiley 1986), out of print but available here with the latest revisions.
• “A mathematical introduction to logic”, H. B. Enderton, Harcourt/Academic Press, 1972 and 2000.
• “Introduction to mathematical logic”, E. Mendelson, various publishers, 1964, 1979, 1987, and 1997.
• “Computability and logic”, G. Boolos and R. Jeffrey, Cambridge Univ.~Press, 1974 and 1980.

The complete classification of the prefix fragments of FOL from the point of view of the decidability of satisfiability is in:

• “The Classical Decision Problem”, Boerger, Graedel, and Gurevich, Springer 1997.

The story of how mathematical logic gave birth to computer science is told best in:

• “Engines of Logic: Mathematicians and the Origins of the Computer”, Davis, 2nd edition, Norton 2001.

There are many, many textbooks that offer an introduction to probabilities I prefer those that do a good job on discrete probability spaces. Some examples:

• “Probability and Random Processes”, Grimmett, Stirzaker, Oxford U. Press 2001.
• “Probability: Theory and Examples”, Durrett, Thomson (Brooks/Cole) 2005.
• There is also a brief introduction to probability in chapter 2 of Koller-Friedman (mentioned below).

For 0-1 laws, I will consult

• “Elements of Finite Model Theory”, Libkin, Springer 2004.
• “The Strange Logic of Random Graphs”, Spencer, Springer 2001.

For the logic of independence in Bayesian and Markov networks I will follow selected sections from:

• “Probabilistic Graphical Models”, Koller, Friedman, MIT Press 2009.