Computational Logic

Winter Semester 2018

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

Purpose

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

Contents

The principles of Computational 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 Computational Logic in Mathematics (building theories, proving), and in Computer Science (automatic reasoning, programming, describing and proving properties of programs, algorithm synthesis).

Organization

The schedule and the place of the lecture is shown in KUSSS.

Lectures (may change depending on the concrete progress)

• Oct. 8: 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: Mathematica programs.
    • Termination of programs.
  • Introduction: The role of Mathematics and Logic in science.
    • Intelectual problem solving: observe - solve - apply.
    • The role of Mathematics, Mathematical Logic, and Computational 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 1: logic-hw-1.pdf, logic-hw-1.tex.

• Oct. 15: 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.
  • Homework 2: logic-hw-2.pdf, logic-hw-2.tex.

• Oct. 29: Lecture 3: :
  • Propositional Logic: Pragmatics.
    • The main goals of pragmatics: prove validity, inconsistency, equivalence, logical consequence. The relations between the goals.
    • Systematic exploration of interesting equivalences.
    • Conjunction applied to sets: syntax, semantics, properties.
    • Proving equivalence by rewriting: normal forms.
    • Negation Normal Form (NNF) and demo, Conjunctive Normal Form (CNF).
  • Homework 3: logic-hw-3.pdf, logic-hw-3.tex.

• Nov. 5: Lecture 4: :
  • Propositional Logic: Rewriting.
    • Disjunctive sets.
    • Using CNF, DNF for proving equivalences, combinatorial growth, incompleteness.
    • Completeness of DNF for unsatisfiability.
  • Homework 4: logic-hw-4.pdf, logic-hw-4.tex.

• Nov. 12: Lecture 5: :
  • Propositional Logic: Resolution.
    • The resolution inference rule and proof method, proof of correctness, statement of completeness.
    • Subsumption, level saturation, termination.
    • The DPLL method, efficient implementation (Chaff).
  • Homework 5: logic-hw-5.pdf, logic-hw-5.tex.

• Nov. 19: Lecture 6: :
  • Propositional Logic: Sequent calculus.
    • Natural-style proving: proof situation, inference rules, proof.
    • Sequent calculus: sequent, sequent rule, proof tree.
    • The "Not-And" sequent calculus.
    • Correctness, completeness.
  • Homework 6: logic-hw-6.pdf, logic-hw-6.tex.

• Dec. 3: Lecture 7: :
  • Propositional Logic: Sequent calculus.
    • Expanding the sequent calculus for the other logical connectives.
    • Special rules: modus ponens, modus tollens, resolution, subsumption, implied goal.
    • Unique-goal sequent calculus.
    • Sequent calculus with unit propagation.
  • First order predicate logic.
    • Examples of formulae.
  • Homework 7: logic-hw-7.pdf, logic-hw-7.tex.

• Dec. 10: Lecture 8: :
  • First order predicate logic.
    • Examples of formulae.
    • Informal definition of syntax: terms, formulae.
    • Quantifiers, bound variables, free variables.
    • Semantics: interpretation with domain, truth evaluation using assigments.
    • Validity, satisfiability, logical consequence, equivalence.
    • Rewriting using equivalence, special equivalences for quantifiers.
    • Normal forms: CNF, prenex, Skolem.
  • Homework 8: logic-hw-8.pdf, logic-hw-8.tex.

• Jan. 7: Lecture 9: :
  • First order predicate logic: Resolution.
    • Resolution in FOL: substitution, unification, examples.
    • Correctness of resolution in FOL.
    • Completeness: Herbrand universe, semantic tree, example.
  • Homework 9: logic-hw-9.pdf, logic-hw-9.tex.

• Jan. 14: Lecture 10: :
  • First order predicate logic: Sequent calculus.
    • Quantifier rules.
    • Correctness.
  • Reasoning with equality
    • Equality as a predicate: properties.
    • First order logic with equality: semantics.
    • Computation by substitution and replacement.
    • Programs as sets of conditional equalities.
  • Homework 9: logic-hw-10.pdf, logic-hw-10.tex.

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 with the subject "Computational Logic Homework " + nr. of homework + last name (example: "Computational Logic Homework 3 Mayr").

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 and do not forget to write in the text your name and the number of the homework. 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.