Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
5.1.1 Syntax of Propositional Calculus
A proposition is a sentence, written in a language, that has a truth value (i.e., it is true or false) in a world. A proposition is built from atomic propositions using logical connectives.
An atomic proposition, or just an atom, is a symbol that starts with a lower-case letter. Intuitively, an atom is something that is true or false.
For example, ai_is_fun, lit_l1, live_outside, and sunny can all be atoms.
In terms of the algebraic variables of the preceding chapter, an atom can be seen as a statement that a variable has a particular value or that the value is in a set of values. For example, the proposition classtimeAfter3 may mean ClassTime>3, which is true when the variable ClassTime has value greater than 3 and is false otherwise. It is traditional in propositional calculus not to make the variable explicit and we follow that tradition. A direct connection exists to Boolean variables, which are variables with domain {true, false}. An assignment X=true is written as the proposition x, using the variable name, but in lower case. So the proposition happy can mean there exists a Boolean variable Happy, where happy means Happy=true.
Propositions can be built from simpler propositions using logical connectives. A proposition is either
- an atomic proposition or
- a compound proposition of the form
¬p (read "not p")--the negation of p
p∧q (read "p and q")--the conjunction of p and q
p∨q (read "p or q")--the disjunction of p and q
p→q (read "p implies q")--the implication of q from p
p←q (read "p if q")--the implication of p from q
p ↔q (read "p if and only if q" or "p is equivalent to q")where p and q are propositions.
The precedence of the operators is in the order they are given above. That is, a compound proposition can be disambiguated by adding parentheses to the subexpressions in the order the operations are defined above. Thus, for example,
¬a ∨ b ∧c →d ∧¬e ∨ f
is an abbreviation for
((¬a) ∨ (b ∧c)) →((d ∧(¬e)) ∨ f).
