KMI/LGPR Logic Programming

Lecturer: Miroslav Kolařík
Lecture: 2 hours/week + exercise 1 hour/week
Credits: 4
Winter semester
Form of course completion: credit course, exam

The course is an introduction to logic programming and its theoretical foundations based on predicate logic. The course includes theoretical topics on the syntax and semantics of logic programs and their relationship to first-order theories. Further attention is paid to the principles of PROLOG compilers. The course is concluded by showing applications in expert systems.

• Introduction to logic programming. Logic program and its semantics. Logic paradigm as a paradigm of programming.
• Definite programs and their syntax. Clauses, facts, rules, and queries.
• Declarative semantics of of definite programs: herbrand structure, herbrand model, least herbrand models and their constructive description. Semantic entailment of definite programs, Substitution, application, ground instances, sound answers. Pure logic programming vs. PROLOG.
• Operational (procedural) semantics of logic programs. Recursive data structures. Finite and infinite herbrand models. Recursive rules. Unification. Nondeterministic inference. Deterministic methods. Most general unifiers, procedural semantics and its relationship to declarative semantics: sound and computed answers.
• PROLOG as a push-down automaton, backtracking, alternative solutions.
• Cuts, negations, arithmetics, and database modification. Cuts and metalogic annotations. Cuts as nullary predicates. Computation control using cuts. Conditional expressions and loops using cuts.
• Theoretical models of negation: closed world assumption, negation as finite failure. Cut-based negation.
• Applications of logic programming in database and expert systems.