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.
    • Proving in natural style.
    • Sequents, proof trees, axioms, sequent rules as models of elements from natural-style proving: Sequent-Calculus_25-Oct-2019.pdf.
  • 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.