Computational Logic
Winter Semester 2019
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. 7: Seminar 1, Lectures 1, 2.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.
- 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.
- Example of showing equivalence by truth table.
- Homework:
logic-hw-1.pdf,
logic-hw-1.tex.
- Oct. 14: Seminar 2, Lectures 2.2, 3:
- Propositional Logic: Pragmantics.
- The main goals of pragmatics:
prove validity, inconsistency, equivalence, logical consequence.
The relations between the goals.
- Propositional Logic: Rewriting.
- Systematic exploration of interesting equivalences.
- Conjunction applied to sets: syntax, semantics, properties:
Conjunctive-Disjunctive-Sets_19-Apr-2020.pdf.
- Proving equivalence by rewriting: normal forms.
- Negation Normal Form (NNF) and demo,
Conjunctive Normal Form (CNF), combinatorial growth.
- Completeness of CNF for proving validity.
- Homework:
logic-hw-2.pdf,
logic-hw-2.tex.
- Oct. 21: Seminar 3, Lectures 4, 5.1
- Propositional Logic: Resolution.
- The resolution principle: the inference rule, the proof method.
- Correctness of the proof method.
- Definition of completeness of resolution.
- Unit resolution and unit subsumption.
- The Davis-Putnam-Logemann-Loveland (DPLL) algorithm.
- DPLL efficient implementation: the Chaff algorithm.
- Propositional Logic: Sequent Calculus.
- Homework:
logic-hw-3.pdf,
logic-hw-3.tex.
- Overview of the previous lectures: Overview-of-Propositional-Logic_25-Oct-2019.pdf.
- Oct. 28: Seminar 4, Lectures 5.1, 6
- Propositional Logic: Sequent Calculus.
- The "Not-And" calculus: correctness, completeness.
- Extending the calculus for the other logical connectives.
- Special rules: modus ponens, implied goal, unit resolution, unit subsumption.
- Sequent calculus with unit propagation.
- Homework:
logic-hw-4.pdf,
logic-hw-4.tex.
- Nov. 4: No lecture.
- Nov. 11: Seminar 5, Lecture 7:
- Propositional Logic: Sequent Calculus.
- The rules for truth constants.
- The rules for conjunctive and for disjunctive sets.
- Unique goal sequent calculus.
- Implementation of sequent calculus in Theorema.
- Homework:
logic-hw-5.pdf,
logic-hw-5.tex.
- Nov. 18: Seminar 6, 7, Lecture 8
- Propositional Logic: Sequent Calculus.
- Implementation of sequent calculus in Theorema.
- First Order Predicate Logic.
- Syntax: term, formula.
- Semantics: interpretation.
- Homework:
logic-hw-6.pdf,
logic-hw-6.tex.
- Nov. 25: No lecture.
- Dec. 2: Seminar 8, Lecture 9
- First Order Predicate Logic.
- Semantics: truth value, domain value.
- Validity, satisfiability, equivalence, semantical logical consequence.
- Interesting equivalences for quantified formulae.
- Normal forms: NNF, prenex, CNF, DNF.
- Skolem normal form.
- Homework:
logic-hw-7.pdf,
logic-hw-7.tex.
Dec. 9: No lecture
Dec. 16: Seminar 9, 10, Lecture 10
Jan. 13: Seminar 11, Lecture 11, 12.1
Jan. 20: Seminar 12, Lecture 12.2, 13
- Review of the material.
- First order logic.
- Completeness of resolution.
Jan. 27: Consultation, Examination
Additional material on First Order Predicate Logic:
Homeworks received:
CL-HW-2019-c.pdf.
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.
T. Jebelean