Logic for Computer Science
IPM, Spring 2013
Instructor:
Meghdad Ghari
Email: ghari@ipm.ir
Class: Saturday: 13-16:30 pm. In Niavaran Bldg, Hall No. 2.
Teaching Assistant:
Ali Valizadeh
Email: valizadeh.ali@aut.ac.ir
Class: Sunday: 10:30-12:30 am. In Niavaran Bldg, Hall No. 1.
Syllabus:
1. Propositional logic [1].
2. Predicate logic [1].
3. Proof systems for predicate logic: Hilbert-style system, Natural deduction and typed term calculus, Gentzen system [2,3]; Signed tableau system [4]; Resolution [2,4].
4. Modal logic [1].
5. Proof systems for modal logics: Hilbert-style system, Natural deduction for S5 [1]; Gentzen system for S4 [3]; Signed tableau system [4].
6. Epistemic logic [1].
7. Temporal logic [1].
Seminars: sections 1.6, 2.7, 3.3, 3.6, 3.7, and chapters 4, 6 of [1].
Course grade: midterm exam (1-3) 35 %, final exam (4-7) 35%, seminar 15%, and homeworks 15%.
Textbook:
[1] M. Huth, M. Ryan, Logic in Computer Science: Modeling and reasoning about systems, Cambridge University Press, 2nd edition, 2004. [Web Page]
Other resources:
[2] J. H. Gallier, Logic for Computer Science, John Wiley, 1987.
[3] A. Troelstra and H. Schwichtenberg, Basic Proof Theory, Cambridge University Press, Amsterdam, 1996.
[4] A. Nerode, R. A. Shore, Logic for Applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993.
Miscellaneous resources:
- G. Dodig-Crnkovic, History of Computer Science, MRTC report ISSN 1404-3041 ISRN MDH-MRTC-50/2001-1-SE, Mälardalen Real-Time Research Centre, Mälardalen University, September, 2001.
- J. J. Lu, E. Rosenthal, Logic-Based Reasoning for Intelligent Systems, in Computer Science Handbook, Allen B. Tucker (Editor), Chapter 61, Chapman and Hall/CRC, 2nd edition, 2004.
-F. Portoraro, Automated Reasoning, In Edward N. Zalta (Editor), Stanford Encyclopedia of Philosophy, 2010. [http]
- J. Goubault-Larrecq, I. Mackie, Proof Theory and Automated Deduction, Kluwer Academic Publisher, 1997.
- S. Buss, An Introduction to Proof Theory, in Handbook of Proof Theory, S. Buss (Editor), Chapter 1, pages 1-78, Elsevier 1998.
- P. Blackburn, J. van Benthem, Modal Logic: A Semantic Perspective, in Handbook of Modal Logic, P. Blackburn, J. van Benthem, and F. Wolter (Editors), Chapter 1, pages 1-84, volume 3 of Studies in Logic and Practical Reasoning, Elsevier, 2007.
-M. Fitting, Modal Proof Theory, in Handbook of Modal Logic, P. Blackburn, J. van Benthem, and F. Wolter (Editors), Chapter 1, pages 85-138, volume 3 of Studies in Logic and Practical Reasoning, Elsevier, 2007.
-R. Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi, Reasoning about knowledge, MIT Press,1995.
- J.-J.Ch. Meyer, W. van der Hoek, Epistemic logic for AI and computer science. Cambridge University Press, 1995.
- D. Harel, D. Kozen, J. Tiuryn, Dynamic Logic, MIT Press, Cambridge, MA, 2000.
-J. Bradfield, C. Stirling, Modal Mu-calculi, in Handbook of Modal Logic, P. Blackburn, J. van Benthem, and F. Wolter (Editors), Chapter 12, pages 721-756, volume 3 of Studies in Logic and Practical Reasoning, Elsevier, 2007.