Lecture 1: Introduction to KR, the Course and "Logic Engineering”
Definition of intelligence”
● carry out complex reasoning (solve physics problems, prove theorems)
● draw plausible inferences (diagnose cars, solve a murder mystery)
● use natural language (read stories and answer questions about them, carry out
extended conversation)
● solving novel complex problems (generating plans, designing artifacts)
● social activities that require a theory of mind
● we do not (only) mean: recognize familiar objects, execute motor skills, or navigate
around space; abilities we share with dogs and cats (and fish)
But isn’t modern AI all about Machine Learning ?
● Two main lines of development in AI
○ symbolic representations
○ statistical representation
● There have been alternating cycles of one dominating over the other in different decades
of the history of AI.
Statistical vs. symbolic AI: very different types of applications
● statistical:
○ pattern recognition (images, sound, shapes)
○ motor skills (robots)
○ speech generation (sound)
○ search engines
● symbolic:
○ planning (autonomous space missions)
○ reasoning (diagnosis, design, decision support)
○ language generation (conversations)
○ search engines
Human intelligence = thinking fast & thinking slow Stengths and weaknesses
● Scaleable:
○ Symbolic→worse with more data
○ Connectionist→worse with less data
1
,Symbolic knowledge is (not) a theory of everything!
The goal of logic in KR
● To state statements which are known to be true (the “knowledge base”)
● Some statements that describe the current state of the world (the “premises”)
● To state statements for which we want to check if they are true (the “conclusions”)
● To see if the conclusions can be derived from the knowledge base + the premises
through logical reasoning
● A variety of related tasks
The ingredients of a logic in KR
● How to formulate the statements (Syntax)
● Assign meaning to the statements (Semantics)
● Assign what can be derived (Calculus)
○ And all of this differs from application domain to application domain and even application
to application.
Logic Engineering
● Previously, you might have learned that Logics exist, how they are defined, what their
theoretical properties are, etc.
● Knowledge Representation is
○ The field of using the right logic for the right AI task
○ Evaluating logics w.r.t. a task or in general
■ Analytically (e.g. soundess, completeness, decidability, complexity, etc)
■ Empirically (practical complexity, practical completeness)
○ Adapt existing logics for a task (we do that in the course)
○ Develop new logics if needed
Logic Engineering: A (cooking) receipe
1. How to represent a real world problem with a formal system/logic?
2. Which formal system/logic is suitable?
3. Which reasoning task gives us a solution to our problem?
4. What syntax to use?
5. Which algorithm calculates the intended semantics?
● Is it good, and how long does it take?
2
,A toy example: politics in the news
● How to measure success of a political party in the news?
● Are two campaigns comparable? Do they have the same political impact?
● Assumption: Negative news has a higher impact! I need to be in the news twice to
compensate for one bit of negative news.
KR in a nutshell: (syntax, semantics, calculus)
KR in a nutshell 2 (Theory about Logics)
Problem solving by SAT solving → Checking for (in)consistency can be used to
solve problems:
● Many problems can be formulated as a set of constraints on the solution. The
constraints for Sudoku, e.g., can be stated as Propositional Logic constraints.
● Finding a solution
○ is asking if the set of constraints is satisfiable
○ is finding a satisfying truth assignment
● Thus: Solving the problem = finding satisfying truth assignment (that satisfies all
the constraints
3
, Testcase 1: Sudoku, PL and DPLL
1) Formulate the problem as Constraints:
● all squares must have exactly one number from 1-9
● no number can appear twice in a row, column or square
Propositional Logic for Sudokus
● Truth assignments (propositions) are sufficient: If 136 is true, there is value 1 in cell x=3,
y=6. If it is false, this is not the case.
● At least one number in each square:
○ “position 11 is a 1 or a 2 or 3 or a 4” ....
● Maximally one number true in each square
○ “if 111 then NOT 211 AND NOT 311... ” ....
● PL is not the only logic to represent Sudokus, but it is simple, and fast.
Finding Sudoku solutions with PL
● Remember: If 136 is true, there is value 1 in cell x=3, y=6. All we have to do is to look for
those propositions that are true w.r.t the constraints of the game, and the givens. These
are called the models.
● Searching for a solution to a sudoku will thus become a search for models.
● We will look at efficient methods to find models (SAT solving using Davis Putnam
Algorithms).
Logic Engineering for Sudokus=
1. How to represent a real world problem with a formal system/logic?
● Constraint satisfaction
2. Which formal system/logic is suitable?
● Propositional logic
3. Which reasoning task gives us a solution to our problem?
● SAT solving
4. What syntax to use?
● DMAC (or whatever)
5. Which algorithm calculates the intended semantics?
● Davis Putnam (DPLL)
● Is it good, and how long does it take?
4
Definition of intelligence”
● carry out complex reasoning (solve physics problems, prove theorems)
● draw plausible inferences (diagnose cars, solve a murder mystery)
● use natural language (read stories and answer questions about them, carry out
extended conversation)
● solving novel complex problems (generating plans, designing artifacts)
● social activities that require a theory of mind
● we do not (only) mean: recognize familiar objects, execute motor skills, or navigate
around space; abilities we share with dogs and cats (and fish)
But isn’t modern AI all about Machine Learning ?
● Two main lines of development in AI
○ symbolic representations
○ statistical representation
● There have been alternating cycles of one dominating over the other in different decades
of the history of AI.
Statistical vs. symbolic AI: very different types of applications
● statistical:
○ pattern recognition (images, sound, shapes)
○ motor skills (robots)
○ speech generation (sound)
○ search engines
● symbolic:
○ planning (autonomous space missions)
○ reasoning (diagnosis, design, decision support)
○ language generation (conversations)
○ search engines
Human intelligence = thinking fast & thinking slow Stengths and weaknesses
● Scaleable:
○ Symbolic→worse with more data
○ Connectionist→worse with less data
1
,Symbolic knowledge is (not) a theory of everything!
The goal of logic in KR
● To state statements which are known to be true (the “knowledge base”)
● Some statements that describe the current state of the world (the “premises”)
● To state statements for which we want to check if they are true (the “conclusions”)
● To see if the conclusions can be derived from the knowledge base + the premises
through logical reasoning
● A variety of related tasks
The ingredients of a logic in KR
● How to formulate the statements (Syntax)
● Assign meaning to the statements (Semantics)
● Assign what can be derived (Calculus)
○ And all of this differs from application domain to application domain and even application
to application.
Logic Engineering
● Previously, you might have learned that Logics exist, how they are defined, what their
theoretical properties are, etc.
● Knowledge Representation is
○ The field of using the right logic for the right AI task
○ Evaluating logics w.r.t. a task or in general
■ Analytically (e.g. soundess, completeness, decidability, complexity, etc)
■ Empirically (practical complexity, practical completeness)
○ Adapt existing logics for a task (we do that in the course)
○ Develop new logics if needed
Logic Engineering: A (cooking) receipe
1. How to represent a real world problem with a formal system/logic?
2. Which formal system/logic is suitable?
3. Which reasoning task gives us a solution to our problem?
4. What syntax to use?
5. Which algorithm calculates the intended semantics?
● Is it good, and how long does it take?
2
,A toy example: politics in the news
● How to measure success of a political party in the news?
● Are two campaigns comparable? Do they have the same political impact?
● Assumption: Negative news has a higher impact! I need to be in the news twice to
compensate for one bit of negative news.
KR in a nutshell: (syntax, semantics, calculus)
KR in a nutshell 2 (Theory about Logics)
Problem solving by SAT solving → Checking for (in)consistency can be used to
solve problems:
● Many problems can be formulated as a set of constraints on the solution. The
constraints for Sudoku, e.g., can be stated as Propositional Logic constraints.
● Finding a solution
○ is asking if the set of constraints is satisfiable
○ is finding a satisfying truth assignment
● Thus: Solving the problem = finding satisfying truth assignment (that satisfies all
the constraints
3
, Testcase 1: Sudoku, PL and DPLL
1) Formulate the problem as Constraints:
● all squares must have exactly one number from 1-9
● no number can appear twice in a row, column or square
Propositional Logic for Sudokus
● Truth assignments (propositions) are sufficient: If 136 is true, there is value 1 in cell x=3,
y=6. If it is false, this is not the case.
● At least one number in each square:
○ “position 11 is a 1 or a 2 or 3 or a 4” ....
● Maximally one number true in each square
○ “if 111 then NOT 211 AND NOT 311... ” ....
● PL is not the only logic to represent Sudokus, but it is simple, and fast.
Finding Sudoku solutions with PL
● Remember: If 136 is true, there is value 1 in cell x=3, y=6. All we have to do is to look for
those propositions that are true w.r.t the constraints of the game, and the givens. These
are called the models.
● Searching for a solution to a sudoku will thus become a search for models.
● We will look at efficient methods to find models (SAT solving using Davis Putnam
Algorithms).
Logic Engineering for Sudokus=
1. How to represent a real world problem with a formal system/logic?
● Constraint satisfaction
2. Which formal system/logic is suitable?
● Propositional logic
3. Which reasoning task gives us a solution to our problem?
● SAT solving
4. What syntax to use?
● DMAC (or whatever)
5. Which algorithm calculates the intended semantics?
● Davis Putnam (DPLL)
● Is it good, and how long does it take?
4
