Logic 1

326.019, 326.021 - Mathematical Logic 1

Winter Semester 2016

The course is an introduction to logic for students in Computer Science and Mathematics.

The contents of the lecture is very similar to the transcript by Martin Koehler of previous lectures: pdf file. (May contain some typos and small errors.)

For more details (some of which are not covered in the lecture) I recommend: Bruno Buchberger: Logic for Computer Science pdf file. This material is copyrighted and is available only for the students of this lecture and only for the purpose of study related to it.

Purpose

Understand the principles of Mathematical Logic and its mathematical models, aquire the skills for using it in Mathematics and Computer Science.

Contents

The principles of Mathematical Logic and its role in human activity.

Main models: propositional logic, first-order predicate logic, higher-order logic. Proof systems: correctness, completeness.

Practical use of Mathematical Logic in Mathematics (building theories, proving), and in Computer Science (automatic reasoning, programming, describing and proving properties of programs).

Organization

The schedule and the place of the lecture is shown in KUSSS. The home page of the lecture in WS 2015 may give you an idea about the contents and the homeworks, although the current lecture will not be exactly the same.

Lectures (may change depending on the concrete progress)

• Oct. 6: No lecture.

• Oct. 13: Lecture 1: Introduction:
  • Examples relating Logic to Mathematics and Computer Science.
    • Simple law text.
    • Russel's paradox.
    • Sorting by pattern matching.
    • Pattern based matching using Mathematica: GCD, Sum, Sorting: Mma-programs.pdf.
    • Termination of programs.
  • The role of Mathematics and Logic in science.
    • Intelectual problem solving: observe - solve - apply.
    • The role of Mathematics and of Mathematical Logic and their importance.
    • The intelectual problem solving cycle in our profesion, the role computer and of automated reasoning.
    • Applications of logic: verification of systems, semantic web.
  • Propositional Logic: Syntax.
    • The main parts of a logic model: syntax, semantics, pragmatics.
    • The definition of syntax as a language: alphabet, composition rules.
    • The inductive principle in the definition of syntax and its applications: defining functions, proving statements.
  • Homework: logic-hw-1.pdf, logic-hw-1.tex.

• Oct. 20: Lecture 2:
  • Propositional Logic: Semantics, Semantics based notions.
    • The main principle of semantics: interpretations, truth value, truth valuation function.
    • Semantics based notions: validity, consistency, semantical logical consequence, semantic equivalence.
    • Proving semantical logical consequence by validity of implication.
    • Semantic equivalence as validity of syntactical equivalence, and as double semantic consequence.
  • Homework : logic-hw-2.pdf, logic-hw-2.tex.

• Oct. 27: Lecture 3:
  • Propositional Logic: Semantics based notions.
    • Proving semantical logical consequence by refutation.
    • The use of semantic equivalence for rewriting formulae.
    • Some basic properties of conjunction: idempotence, commutativity, associativity. Embedding these properties at syntactic level by considering conjunctive sets.
    • Systematic exploration of interesting equivalences.
    • Using equivalences for transforming formulae: Negation Normal Form, Conjunctive Normal Form, Disjunctive Normal Form.
    • Proving equivalences by reduction to CNF.
    • The resolution principle: inference rule, proof method.
    • Correctness of resolution. Definition of completeness.
  • Homework : logic-hw-3.pdf, logic-hw-3.tex.

• Nov 3: Lecture 4:
  • Propositional Logic: More proof methods.
    • The DPLL algorithm.
    • Sequent calculus, the "Not-And" calculus.
  • Homework : logic-hw-4.pdf, logic-hw-4.tex.

• Nov 10: Lecture 5:
  • Propositional Logic: Sequent calculus.
    • Correctness and completeness of the "Not-And" calculus.
    • Extending sequent calculus to the other connectives.
    • Using unit propagation in sequent calculus.
  • Homework : logic-hw-5.pdf, logic-hw-5.tex.

• Nov 17: Lecture 6:
  • Propositional Logic: Sequent calculus.
    • "Unique goal" sequent calculus.
    • Special rules ("modus" ponens, resolution, subsumption).
    • Unsafe rules, proof trees with "or" nodes.
  • First Order Predicate Logic: Syntax and semantics.
    • Syntax: terms, formulae.
    • Semantics: interpretations, truth value, domain value.
  • Homework : logic-hw-6.pdf, logic-hw-6.tex.

• Nov 24: Lecture 7:
  • First Order Predicate Logic: Semantics. and Pragmatics.
    • Semantically defined notions: valid, consistent, satisfiable, consequence, equivalence.
    • Interesting equivalences, rewriting, normal forms: negation, prenex, CNF, Skolem.
    • The resolution method, unification, substitution.
  • Homework : logic-hw-7.pdf, logic-hw-7.tex.

• Dec 1: Lecture 8:
  • First Order Predicate Logic: Resolution.
    • Example of proof by refutation and resolution.
    • Correctness of resolution.
    • Completeness of resolution: basic idea by example.
    • The Herbrand universe and its universality, Herbrand interpretations.
    • Semantic tree, closed semantic tree.
    • The Herbrand theorem, the Herbrand proving procedure, semidecidability of first order predicate logic.
  • No homework .

• Dec 15: Lecture 9:
  • First Order Predicate Logic: Sequent calculus.
    • Example of natural-style proof in predicate logic: convergence of sum of convergent sequences.
    • The four rules for quantifiers in natural-style proving.
    • The four rules for quantifiers in sequent calculus.
    • Correctnes of the quantifier rules, discussion about completeness.
    • The use of equality in predicate logic.
  • Homework : logic-hw-8.pdf, logic-hw-8.tex.

• Jan 12: Lecture 10:
  • First Order Predicate Logic: Reasoning with equality.
    • Equality as usual predicate.
    • Equality as special predicate: FOL with equality.
    • Substitution and replacement.
    • Universal computation by substitution and replacement.
    • Predicate logic as programming language reverse.pdf.
    • Verification of imperative programs Logical-program-verification_Jebelean-Erascu.pdf.

• Jan 19: Lecture 11:
  • Review of the material.
  • The relationship between logic and programming.

• Jan 26: Examination.

Homeworks:

Each exercise counts for your final grade. In particular the grade for exercises is based on the homework and on your activity in the class room.

In case you send your homeworks by e-mail, please use my address Tudor.Jebelean@jku.at.

Also please use as name of the file[s] your name and the number of the homework, e. g. like Mayer-3.pdf or Schreiner-J-4.ps. Please do not use Windows Word files (*.doc) because the special symbols are not shown correctly on different systems. If you do not have alternative to Word, then please print the file using the option "Print to file" and send this file too.