Computational Logic

Recommended Prerequisites

Artificial Intelligence, Algorithms and Data Structures

Teaching Methods

Classes will be of a theoretical nature, where all concepts of a more theoretical character will be exposed, and all practical concepts presented, together with practical examples and exercises for a solidification of acquired knowledge.

Learning Outcomes

Students will learn the state-of-the-art principles, methodologies, techniques and tools in the Computational Logic area, as well as the reifications and practical applications that resort to them. They will learn techniques to solve practical problems related to constraint solving and satisfiability, deduction, hypotheses abduction, diagnosis, planning, qualitative preferences, belief revision, knowledge updating, amongst others, using the paradigm of declarative Logic Programming.

By the end of the course, students should have developed skills for abstract reasoning and declarative problem representation, as well as acquired knowledge of concepts related to the declarative languages. They should also have acquired working knowledge of the Prolog language and, more generically, of Answer-Set Programming. Students should be able to apply these skills and concepts in the development of Prolog/ASP applications to solve numerous kinds of problems.

Work Placement(s)

No

Syllabus

1. Introduction
2. Review of First Order Logic — Syntax and Semantics

3. Logic Programming
3.1. Prolog; Facts; Conjunctive normal form; Horn clauses; Rules; Queries; Variables; Instantiation; Resolution
3.2. Inference rules; Unification; Resolution
3.3. Non-Deterministic Programming: Backtracking; Rules and goals order; Termination
3.4. Negation As Failure; Cuts; Floundering

4. Non-Monotonic Logic
4.1. Logic Programs — Defined, Stratified, Normal, Extended, Disjunctive, and Abductive LPs
4.2. Syntactical Notions — Stratification, Layering, Relevant Call-Graph
4.3. Semantics — 2-valued, 3-valued, Paraconsistent and Disjunctive
4.4. Semantics Properties
4.5. Proof procedures
 
5. Applications
5.1. Satisfiability, Constraint Solving
5.2. Diagnostics, Abduction, Planning, Constructive Negation
5.3. Belief Revision; Knowledge Updating
5.4. Qualitative preferences

Assessment Methods

Assessment
Theoretical + one practical assignments: 100.0%

Bibliography

Chitta Baral, Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge University Press, 2003
The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition, Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, Peter F. Patel-Schneider, Cambridge University Press, 2007
L Sterling and E Shapiro, The Art of Prolog: Advanced Programming Techniques (Logic Programming) (2nd ed.), MIT Press, 1994
C J Hogger, Essentials of Logic Programming, Oxford University Press, 1990
I Bratko, Prolog Programming for Artificial Intelligence (3rd ed.), Addison-Wesley, 2001
K Marriott and P J Stuckey, Programming with Constraints: an Introduction, 1998
W F Clocksin, Programming in Prolog, 1994