Statements about the world provide constraints about what could be true. Constraints could be specified extensionally as tables of legal assignments to variables, or intensionally in terms of formulas. For many domains propositions provide a suitable language for providing intensional constraints.

There are a number of reasons for using propositions for specifying constraints and queries:

• •

  It is often more concise and readable to give a logical statement about the relationship among some variables than to use an extensional representation.

• •

  The form of the knowledge can be exploited to make reasoning more efficient.

• •

  They are modular, so small changes to the problem result in small changes to the knowledge base. This also means that a knowledge base is easier to debug than for other representations.

• •

  The kind of queries an agent may have to answer may be richer than single assignments of values to variables.

• •

  This language is extended to reason about individuals and relations in Chapter 13.

We first give the syntax and the semantics of a language called the propositional calculus.