10. Propositional Logic 2 Flashcards
What is logical inference?
A process that derives new sentences that logically follow from a given knowledge base.
What are the two main types of search in logical inference?
Forward chaining and backward chaining.
What is Modus Ponens?
If p and p→q are true, then q is true.
What is Modus Tollens?
If ¬q and p→q are true, then ¬p is true.
What is forward chaining?
A method that starts with known facts and applies inference rules to derive new facts until the query is found or no more inferences can be made.
What are the advantages of forward chaining?
It reaches correct conclusions and is easy to design.
What are the disadvantages of forward chaining?
It may generate facts inefficiently, leading to unnecessary computations.
What is backward chaining?
A method that starts with the query and works backward using inference rules to determine if the query can be derived from known facts.
What are the advantages of backward chaining?
It is optimal for finding specific conclusions and reduces unnecessary fact generation.
What are the disadvantages of backward chaining?
It may fail to conclude if there are not enough facts.
What is the Davis-Putnam-Logemann-Loveland (DPLL) algorithm?
A complete search algorithm for deciding the satisfiability of propositional logic formulas.
What are the key optimizations of DPLL?
Early termination, pure symbol heuristic, and unit clause heuristic.
What is the pure symbol heuristic?
A heuristic that assigns a truth value to symbols appearing only with one polarity (either always positive or always negative).
What is the unit clause heuristic?
A heuristic that assigns values to unit clauses (single literals) to reduce the number of clauses in a formula.
What is the time complexity of DPLL?
O(2^n), where n is the number of variables.
Is DPLL a complete algorithm?
Yes, it is complete, meaning it will always find a solution if one exists.
