Logic for CS - WINTER 2008


Announcements:

  • The first tutorial will be held despite the lecturers strike!
  • The exercises should be submitted every Thursday in class, or to the mailbox of Dina Bilchinsky (#378, Shreiber, second floor) by the end of the day.

    Details:

    Lecturer:          Prof. Alexander Rabinovich
                              rabinoa@post.tau.ac.il
                             

    TA:                   Anna Zamansky
                              annaz@post.tau.ac.il
                              mailbox: ???

    HW Checker:   Dina Bilchinsky
                              sdinad@post.tau.ac.il
                              mailbox: 378


    Grading policy:

    The HW is 20% from the final grade, you must submit at least 7 of the exercises to participate in the final test.

    Course Plan:
    • Historical background: Logic and its connection with different fields of science. Different fields of application of Logics.
    • Propositional Logic: Propositional logic its syntax and semantics. Basic properties of Propositional logics. Normal forms. Functional completeness. Decidability. Hilbert propositional Calculus. Deduction theorems. Completeness and compactness. Natural deduction. Tense and modal logics.
    • Predicate Calculus: Syntax and semantics of first order language. Examples of Structures for first-order language. Equivalence transformation and Normal forms. Skolem and Herbrand Theorems. Undecidability. Calculus. Completeness and compactness and some consequences. Incompleteness Theorem.
    • Applications: Sugaring of first order language - many sorted language, applications to database. Temporal logics and their functional completeness. Logics for reasoning about programs; Hoare and Dynamic logics.

    Homework grades:

    Assignments and handouts:

  • Exercise 1
  • Exercise 2
  • Exercise 3
  • Exercise 4 Solution
  • Exercise 5 Solution
  • Exercise 6
  • Exercise 7
  • Exercise 8 Useful Equivalences
  • Exercise 9 Solution of q.5
  • More exercises
  • The HC page as will appear in the test
  • Last tirgul scan 1
  • Last tirgul scan 2

    Recommended reading:

    Logic for CS:

    • V. Sperschneider and G. Antoniou, Logic - a foundation for computer science

    • Nerode and R. Shore, Logic for applications

    • S. Reeves and M. Clarke, Logic for computer science

    • Z. Manna and R. Waldinger, The deductive foundations of computer programming

    • Burris and Stanley, Logic for mathematics and computer science

    Classical texts on Mathematical Logic:

    • Herbert B. Enderton, A mathematical introduction to logic (2-nd edition)

    • D. Van Dalen, Logic and structure (3-rd edition)

    • E. Mendelson, Introduction to mathematical logic

    • J.R. Shoenfield, Mathematical logic

    • H. Ebbinghous, J. Flum and W. Thomas, Mathematical logic

    Handbooks:

    • J. Barwise ed., Handbook of mathematical logic

    • D. Gabbay and F. Guenther ed., Handbook of philosofical logic

    • D. Gabbay ed.,Handbook of logic in computer science

    • D. Gabbay et al ed., Handbook of AI and logic programming

    Useful Links:

  • English-Hebrew dictionary of logical terms by Udi Boker