Section 1 : Propositional logic and reasoning

Commentary

Section Goals

• To discuss syntax, semantics and inference of propositional logic.
• To introduce reasoning patterns and effective propositional inference.
• To exemplify a reasoning agent based on propositional logic

Section Notes

• Parts of this section may be skipped by those who have studied propositional logic and inference in an undergraduate AI course. However, even for those students, further study of the in-depth issues in this section is encouraged to pave the way for the future sections and units.

Learning Objectives

Learning Objective 1

• Exemplify logical agents in the context of the wumpus world.
• Outline the syntax and semantics of propositional logic.
• Outline the basic principles of propositional entailment.
• Explain the following concepts or terms:
  • Syntax
  • Semantics
  • Possible world
  • Model
  • Entailment
  • Model checking
  • Derive
  • Truth table
  • Sound and complete
  • Equivalence, validity, and satisfiability

Objective Readings

Reading topics:

Knowledge-Based Agents, Wumpus World, Logic Foundations, and Propositional Logic (see Sections 7.1-7.4 of AIMA3ed)

Objective Questions

• Why do we need to define the semantics of a logical system?
• Why are soundness and completeness important characteristics of a logic system?

Objective Activities

• Explore the following truth-table enumeration algorithm for deciding propositional entailment from the textbook's website.
  • TT-Entails
• Complete Exercise 7.1 of AIMA3ed.

Learning Objective 2

• Explain the principles of reasoning patterns and reasoning algorithms, such as resolution, and forward and backward chaining.
• Analyse and implement the above algorithms.
• Explain the following concepts or terms:
  • Proof
  • Resolution
  • Monotonicity
  • Conjunctive normal form or CNF
  • Horn clause
  • Refutation completeness
• AND-OR graph

Objective Readings

Required readings:

Reading topics:

Propositional Theorem Proving (see Section 7.5 of AIMA3ed).

Objective Questions

• Is resolution complete?
• What will affect the effectiveness of a resolution algorithm?

Objective Activities

• Explore the following programs of propositional inference from the textbook's website.
  • PL-Resolution
  • PL-FC-Entails
• Complete Exercise 7.5 of AIMA3ed.

Learning Objective 3

• Discuss the methodologies that would lead to an effective propositional inference.
• Explain DPLL algorithms.
• Explain the use of local search for propositional inference.
• Analyse and implement the above algorithms.
• Outline the solution and algorithm of a logical agent in the wumpus world, based on propositional reasoning.

Objective Readings

Required readings:

Reading topics:

Effective Propositional Inference, Agents Based on Propositional Logic(see Sections 7.6 - 7.7 of AIMA3ed).

Objective Questions

• What improvements have been embodied in the complete backtracking algorithm, when compared to a simple enumeration of possible models?

Objective Activities

• Explore the following programs of propositional inference from the textbook's website.
  • DPLL-Satisfiable
  • WalkSAT
  • Hybrid-Wumpus-Agent
• Complete Exercise 7.24 of AIMA3ed.