Chapter 2 Flashcards
Thinking
Can be understood as drawing conclusions from a large collection of sentences called a knowledge base (KB)
Sentences
Uninterpreted symbolic structures
Symbolic manipulation
Computational procedure that involves the manipulation of symbolic structures (sentences) representing propositions.
Back-chaining
One example of symbolic manipulation
Knowledge base
Collection of sentences
Atomic sentences
Simple basic sentences
Conditional sentences
Sentences of the form : if P1 and …. and Pn then Q, where Pi and Q are atomic sentences
What do atomic and conditional sentences contain?
Variables, constants and special keywords (such as “if”, “and”, “then”..)
Logical entailment concept
A sentence cannot not be true if all sentences in the knowledge base are true.
Steps to check for logical entailment:
- Try to locate Q itself in the KB. If you can, return success.
- Otherwise, try to locate a conditional sentence of the form: if P1 and … and Pn, then Q, in the KB. If you cannot, return fail.
- Otherwise, use back-chaining to try to establish P1 and P2 and … Pn. If these are all successful, then return success.
- Otherwise, go back to step 2 and look for another conditional.
Back-chaining
Receives an atomic sentence (the query) as input and its job is to determine if the query is logically entailed by the KB
Even if a query Q can be successfully established, will it be added to the KB?
No, because back-chaining always leaves the KB unchanged
Think of an example of a sentence in a KB that includes variables.
If X is a child of Y, then Y is a parent of X.
Tracing
Simulation fo the execution of the back-chaining procedure
In Prolog, is it important to know what the symbols mean?
No, it isn’t.
In Prolog, is it important to keep track of your place in the procedure?
Yes, it is.
What tracing is used in Prolog to keep track of how deep we are in the procedure?
Indentation
What is the goal of back-chaining when the query Q only contains constants?
The goal is to establish whether Q is logically entailed by the KB
What is the goal of back-chaining when the query Q contains variables?
The goal is to establish for what values of the variable the query Q is logically entailed by the KB
Can we perform “variable renaming” in Prolog?
Yes, since the names of the variables do not really matter.
What happens when there is a query with variables?
The variables in the sentences of the KB are renamed to ensure that they differ from the ones in the query
Back-tracking
The process of going back and reconsidering the choice of values for variables if things do not work out.
Is it possible to have no variables in a top-level query, but to have variables in subqueries?
Yes, it is
Difference between back-chaining and forward-chaining
Back-chaining: only works with KBs with atomic and conditional sentences.
Forward-chaining: starts from atomic sentences and draws new conclusions
Is back-chaining goal directed?
Yes, it starts with a goal and works “its way” towards what is known (the sentences in the KB)
Is back-chaining always logically sound?
Yes, it never makes mistakes (so far)
Is back-chaining always logically complete?
No. It is logically complete UNLESS it gets stuck in a loop
To be logically complete
Any time a query is logically entailed by the knowledge base, the procedure will eventually return success.
Is Prolog based on back-chaining or forward-chaining?
Back-chaining
What kinds of sentecens cause looping?
Sentences in the KB that do not add anything to the KB. An example of such sentences are tautologies.
