Meeting 12: Predicate Calculus (First-Order Logic)

Reading: AIAMA 8.1-8.3

As we have seen, propositional logic alone is quite limited in power and expressiveness. In particular it can refer only to specific entities and relationships among them. This makes it cumbersome to express generic rules. Combining propositional logic with feedback via flip-flops gives the ability to express finite state machines. Add in infinite memory and we have turing machines. This is the bread and butter of CPE. However, there is another approach to increasing the power of logic, moving to higher-order logic, meaning the language supports representation of more abstract concepts directly. This chapter covers the next step up, first-order logic or predicate calculus [1].

Questions you should be able to answer after reading are:

  1. What are the components of FOL syntax?
  2. Can you provide examples expressing natural language concepts using FOL?
  3. Can you describe environments like the Wumpus World using FOL?
  4. What is a variable? Quantifiers?
  5. What are predicates?
  6. What are functions?
  7. How does FOL differ from PL?
  8. What kind of information can be expressed with FOL but not PL?

[1] Actually there is an intermediate step called Herbrand logic, but I will gloss over that.