Knowledge Representation and Reasoning
A.Y. 2026/2027
Learning objectives
The course aims to provide students with an in-depth understanding of the theoretical foundations and algorithms for knowledge representation and reasoning, focusing on the use of logical languages for encoding knowledge and symbolic inference techniques. Key symbolic AI concepts will be covered, such as formal explainability, the integration of deductive reasoning with AI approaches based on Machine Learning, and modern neuro-symbolic reasoning techniques. Practical applications of these techniques will also be explored.
Expected learning outcomes
The student will be able to use the main knowledge representation languages and encode various reasoning tasks using these languages. The student will be capable of modeling real-world scenarios with the learned languages and identifying the right trade-offs between expressiveness and computational complexity of the different languages. The student will also acquire an in-depth understanding of deductive reasoning algorithms and be able to use real systems for knowledge representation and reasoning, as well as integrate logic-based deduction techniques with inductive AI (i.e., ML) systems through neuro-symbolic reasoning approaches.
Lesson period: First four month period
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
First four month period
Course syllabus
- Representing data and reasoning over data using logic. What is knowledge representation and reasoning? Basic introduction to propositional logic as a simple knwoledge representation language. Models as a way to give meaning to our representation. Difference between "truth" and "provability". How we can use logic to perform inference and derive new knowledge from the existing one. Why propositional logic is not adequate.
- Basics of logic. Syntax and Semantics of propositional logic and resolution. Syntax and semantics of First-Order (FO) logic as a more powerful language for reasoning over data.
- Computational limits of first-order logic. Undecidability of reasoning under first-order logic. More practical formalisms that can work in practice with large amounts of data. The simplest knowledge representation and reasoning framework: databases as the theory, and conjunctive queries as the inference target.
- Complexity of inferring conjunctive queries over databases, and the limitations of simple databases as a knowledge representation mechanism. Introduction to negation and its expressive power.
- Introduction to inference rules and knowledge bases as a formalism for encoding knowledge and reasoning over large amounts of data.
- Implementing reasoning with inference rules in practice. The naive and the semi-naive algorithms for fixpoint-based reasoning. Complexity of the algorithms, and inherent complexity of reasoning with inference rules.
- Magic-Set rewriting technique to make inference with knowledge base more efficient.
- Expressiveness limitations of inference rules. Knowledge bases with inference rules cannot express non-monotonic concepts. Introduction to syntax and semantics of semi-positive inference rules: a strictly more expressive formalism. Adaptation of the fixpoint-based procedures for reasoning.
- Extending semi-positive rules with a more flexible notion of negation. Stratified inference rules with negation and the precedence graph. Stratified inference rules preserve efficiency of reasoning over large amounts of data.
- Brief overview on probabilistic reasoning with inference rules and neuro-symbolic approaches.
- Basics of logic. Syntax and Semantics of propositional logic and resolution. Syntax and semantics of First-Order (FO) logic as a more powerful language for reasoning over data.
- Computational limits of first-order logic. Undecidability of reasoning under first-order logic. More practical formalisms that can work in practice with large amounts of data. The simplest knowledge representation and reasoning framework: databases as the theory, and conjunctive queries as the inference target.
- Complexity of inferring conjunctive queries over databases, and the limitations of simple databases as a knowledge representation mechanism. Introduction to negation and its expressive power.
- Introduction to inference rules and knowledge bases as a formalism for encoding knowledge and reasoning over large amounts of data.
- Implementing reasoning with inference rules in practice. The naive and the semi-naive algorithms for fixpoint-based reasoning. Complexity of the algorithms, and inherent complexity of reasoning with inference rules.
- Magic-Set rewriting technique to make inference with knowledge base more efficient.
- Expressiveness limitations of inference rules. Knowledge bases with inference rules cannot express non-monotonic concepts. Introduction to syntax and semantics of semi-positive inference rules: a strictly more expressive formalism. Adaptation of the fixpoint-based procedures for reasoning.
- Extending semi-positive rules with a more flexible notion of negation. Stratified inference rules with negation and the precedence graph. Stratified inference rules preserve efficiency of reasoning over large amounts of data.
- Brief overview on probabilistic reasoning with inference rules and neuro-symbolic approaches.
Prerequisites for admission
Although not strictly required, students should have basic notions of set theory, logic, and algorithms.
Teaching methods
The theory lectures will be mainly given using the whiteboard in order to let students follow the key concepts at the right pace. Several exercises will also be discussed to help students consolidate the concepts they have learned. The exercises will be carried out using state-of-the-art knowledge representation and reasoning tools, such as Clingo/DLV and Scallop.
Teaching Resources
- Lecture notes of the course.
- Books (these are not mandatory, but complement the Lecture notes):
- Brachman, R. J., & Levesque, H. J. (2004). Knowledge Representation and Reasoning. Morgan Kaufmann. ISBN: 978-1-55860-932-7, DOI: https://doi.org/10.1016/B978-1-55860-932-7.X5083-3.
- Genesereth, M. R., & Kao, E. (2017). Introduction to Logic (3nd ed.). Stanford University. ISBN: 978-3-031-01801-5, DOI: https://doi.org/10.1007/978-3-031-01801-5.
- Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison-Wesley. ISBN: 0-201-53771-0.
- Greco, S., & Molinaro, C. (2016). Datalog and Logic Databases. Springer. ISBN: 978-3-031-01854-1, DOI: https://doi.org/10.1007/978-3-031-01854-1.
- Books (these are not mandatory, but complement the Lecture notes):
- Brachman, R. J., & Levesque, H. J. (2004). Knowledge Representation and Reasoning. Morgan Kaufmann. ISBN: 978-1-55860-932-7, DOI: https://doi.org/10.1016/B978-1-55860-932-7.X5083-3.
- Genesereth, M. R., & Kao, E. (2017). Introduction to Logic (3nd ed.). Stanford University. ISBN: 978-3-031-01801-5, DOI: https://doi.org/10.1007/978-3-031-01801-5.
- Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison-Wesley. ISBN: 0-201-53771-0.
- Greco, S., & Molinaro, C. (2016). Datalog and Logic Databases. Springer. ISBN: 978-3-031-01854-1, DOI: https://doi.org/10.1007/978-3-031-01854-1.
Assessment methods and Criteria
Students will be evaluated with a written exam with open questions on the topics of the course. The main goal of the exam is to assess that students are able to encode knowledge given in natural language text by means of the logical formalisms presented throughout the course, that they can recover proofs of the main theoretical results discussed in the course, and that they understand the different reasoning processes that are required by the logical formalisms. Students succesfully passing the main written exam may have to take an oral exam, at the lecturer's discretion.
INFO-01/A - Informatics - University credits: 6
Lessons: 48 hours
Professor:
Calautti Marco
Shifts:
Turno
Professor:
Calautti MarcoProfessor(s)