This is an old revision of the document!

====== EPFL Fall 2011: Logic and Probability ====== **Doctoral course by Val Tannen** Lecture notes 1 [[http://www.cis.upenn.edu/~val/LogicProbEPFL2011files/ln1.pdf|(pdf)]] //Course Materials// Old lecture notes on computability [[http://www.cis.upenn.edu/~val/LogicProbEPFL2011files/compNotes.pdf|(pdf)]] "On the Unusual Effectiveness of Logic in Computer Science" Halpern, Harper, Immerman, Kolaitis, Vardi, and Vianu" [[http://www.cis.upenn.edu/~val/LogicProbEPFL2011files/UnusualEffectiveness.pdf|(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 will also make available my own notes on computability on the website. There many textbooks on logic but let me recommend my favorites: ``Logic for Computer Science'', J. Gallier, (Wiley 1986), out of print but available online with the latest revisions at \verb|http://www.cis.upenn.edu/~jean/gbooks/logic.html| ``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, 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, and ``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.