Lecturer(s)


Vychodil Vilém, doc. RNDr. Ph.D.

Course content

Introduction to logic programming. Definite program and its semantics: Logic as a paradigm of programming. Definite programs and their syntax. Clauses, facts, rules and queries. Declarative semantics of definite programs: herbrand structures, herbrand models, least herbrand models and their computation. Semantic entailment form definite programs. Substitutions, application of substitutions, ground instances of formulas, correct answers. Pure logic programming vs. logic programming vs. PROLOG. Procedural semantics of definite programs. Recursive data structures: Finite and infinite herbrand models. Recursive rules. Unification. Indeterministic inference. Deterministic methods to automated deduction. Most general unifiers and its determination. Procedural semantics of definite programs. The relationship between declarative and procedural semantics of programs: correct answers vs. computed answers. Stack model of a deterministic PROLOG, backtracking, alternative solutions. Cuts and negations in logic programs: Metalogical predicate ``cut''. Efficiency of computation and cuts. Pruning the computation by cuts. Stack model of computation enriched by cuts. Conditional expressions and loops expressed using builtin predicates. Theoretical models of negation: closed world assumption; negation as finite failure. The problem of nonexistence of herbrand models for programs with (logical) negation. SLDNFresolution. Definition of negation using cuts. Logic programming and mathematical logic: Connection between logic programming and predicate logic. Definite programs as firstorder theories. Herbrand structures as firstorder structures. The principles of the general resolution method and its particularization for definite programs: SLDresolution. Soundness and completeness of SLDresolution.

Learning activities and teaching methods

Lecture, Demonstration
 Preparation for the Exam
 120 hours per semester

Learning outcomes

The students become familiar with basic concepts of logic programming.
1. Knowledge Describe and understand comprehensively principles and methods of logic programming.

Prerequisites

unspecified

Assessment methods and criteria

Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.

Recommended literature


Bratko I. (2001). PROLOG Programming for Artificial Intelligence. Addison Wesley (third edition).

Brož, M. (2004). Microsoft Office Word 2003 : podrobná uživatelská příručka. Brno : Computer Press.

Jirků P. a kol. (1991). Programování v jazyku Prolog. SNTL, Praha.

Lloyd, J. W. (1987). Foundations of Logic Programming. SpringerVerlag, New York (second edition).

Nerode A., Shore R. A. (1997). Logic for Applications. SpringerVerlag, New York (second edition).

Nilsson U., Maluszynski J. (1995). Logic, programming and PROLOG, el. verze: http://www.ida.liu.se/~ulfni/lpp/. John Wiley & Sons Ltd., Chichester (druhé vydání).
