12. First-Order Logic 2 Flashcards
What is the purpose of reducing First-Order Logic (FOL) to Propositional Logic (PL)?
To simplify inference by converting FOL statements into propositional statements while preserving entailment.
What is Herbrand’s theorem?
It states that if a FOL knowledge base entails a sentence, then it is also entailed by a finite subset of its propositionalized version.
What steps are involved in propositionalizing a FOL knowledge base?
- Remove existential quantifiers, 2. Instantiate universal quantifiers, 3. Ground functions, 4. Treat formulas as propositional sentences.
How do you eliminate existential quantifiers?
By replacing the existential variable with a new constant, called a Skolem constant.
How do you eliminate universal quantifiers?
By instantiating the universal statement for every object in the domain.
What is grounding in FOL?
Replacing function terms with their corresponding values to create fully instantiated sentences.
Why is propositionalizing FOL often impractical?
Because universal quantification generates too many sentences, and functions can create infinitely large knowledge bases.
What is unification in FOL?
A pattern-matching procedure that finds substitutions to make different logical expressions identical.
What is the most general unifier (MGU)?
The simplest substitution that makes two logical statements identical.
What is Generalized Modus Ponens (GMP)?
An extension of Modus Ponens that uses unification to derive new facts in FOL.
What is the forward chaining inference method?
A data-driven approach that applies inference rules to known facts to deduce new facts.
How does forward chaining work?
It starts from known facts and applies rules iteratively until the query is found or no more rules can be applied.
What type of search does forward chaining resemble?
Breadth-First Search (BFS) since it explores all possible deductions level by level.
What is backward chaining?
A goal-driven inference method that starts with a query and works backward to determine if it can be derived from known facts.
How does backward chaining work?
It starts with the goal and searches for rules that can produce it, checking subgoals recursively.
What type of search does backward chaining resemble?
Depth-First Search (DFS) since it works backward through the inference chain.
What is an example of backward chaining in action?
Determining if “Colonel West is a criminal” by working backward through the knowledge base.
What are the advantages of forward chaining?
Efficient for data-driven problems where new information continuously arrives.
What are the advantages of backward chaining?
Efficient for goal-driven problems where only specific queries need to be answered.
How are inference algorithms used in intelligent agents?
Forward chaining is used for real-time knowledge updates, while backward chaining is used for goal-oriented reasoning.
