Knowledge Representation and Reasoning
A.Y. 2025/2026
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 can be attended as a single course.
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 inference rules and knowledge bases as aformalism for encoding knowledge and reasoning over large amounts of data.
- Three different ways to provide semantics to inference rules: model-based, fixpoint-based, and proof-based. Equivalence of all three semantics.
- 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.
- 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. Equivalence between model-based semantics and fixpoint-based semantics over any stratification. Stratified inference rules preserve efficiency of reasoning over large amounts of data.
- Beyond stratified negation. Mention to the undecidability of reasoning with unstratified inference rules, and conceptual issues with unstratified negation. Introduction to a more sensible notion of model for practical purposes: stable models. Most common use of inference rules under stable models: the choice operator and the guess and verify paradigm.
- Probabilistic reasoning via inference rules. Probabilistic databases and the possible worlds semantics for inference rules. How can we actually compute the probabilistic inference in practice?
- Provenance semirings as a unifying framework for (probabilistic) reasoning over inference rules. The semiring framework and its connections to reasoning with inference rules. Introduction to the main provenance semirings: which-provenance, why-provenance, and provenance polynomials.
- Combining inference rules with Machine Learning. Using the framework of semirings as tool to interface inference rules with deep learning models: overview of the Scallop inference language.
- 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 inference rules and knowledge bases as aformalism for encoding knowledge and reasoning over large amounts of data.
- Three different ways to provide semantics to inference rules: model-based, fixpoint-based, and proof-based. Equivalence of all three semantics.
- 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.
- 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. Equivalence between model-based semantics and fixpoint-based semantics over any stratification. Stratified inference rules preserve efficiency of reasoning over large amounts of data.
- Beyond stratified negation. Mention to the undecidability of reasoning with unstratified inference rules, and conceptual issues with unstratified negation. Introduction to a more sensible notion of model for practical purposes: stable models. Most common use of inference rules under stable models: the choice operator and the guess and verify paradigm.
- Probabilistic reasoning via inference rules. Probabilistic databases and the possible worlds semantics for inference rules. How can we actually compute the probabilistic inference in practice?
- Provenance semirings as a unifying framework for (probabilistic) reasoning over inference rules. The semiring framework and its connections to reasoning with inference rules. Introduction to the main provenance semirings: which-provenance, why-provenance, and provenance polynomials.
- Combining inference rules with Machine Learning. Using the framework of semirings as tool to interface inference rules with deep learning models: overview of the Scallop inference language.
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 and 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:
- "Logic in Computer Science: Modelling and Reasoning about Systems". Michael Huth and Mark Ryan -- good for basics on propositional and first-order logic.
- "Foundations of Databases". Serge Abiteboul, Richard Hull, Victor Vianu -- good for databases, conjunctive queries, and inference rules (with stratified negation).
- "Knowledge Representation, Reasoning, and the Design of Intelligent Agents". Michael Gelfond and Yulia Kahl -- for stable model semantics, and the choice operator, but also mentions databases and conjunctive queries.
- Books:
- "Logic in Computer Science: Modelling and Reasoning about Systems". Michael Huth and Mark Ryan -- good for basics on propositional and first-order logic.
- "Foundations of Databases". Serge Abiteboul, Richard Hull, Victor Vianu -- good for databases, conjunctive queries, and inference rules (with stratified negation).
- "Knowledge Representation, Reasoning, and the Design of Intelligent Agents". Michael Gelfond and Yulia Kahl -- for stable model semantics, and the choice operator, but also mentions databases and conjunctive queries.
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.
Professor(s)