14.3 First-Order Predicate Calculus
Logic programming is based on a system of symbolic logic called first-order predicate calculus,6 which is a formal system of symbolic logic that uses variables, predicates, quantifiers, and logical connectives to produce propositions involving terms. Predicate calculus is the foundation for logic programming as λ-calculus is the basis for functional programming (Figure 14.1). We refer to first-order predicate calculus simply as predicate calculus in this chapter. The crux of logic programming is that the programmer specifies a knowledge base of known propositions—axioms declared to be true—from which the system infers new propositions using a deductive apparatus:
Figure 14.1 The theoretical foundations of functional and logic programming are λ-calculus and first-order predicate calculus, respectively.
14.3.1 Representing Knowledge as Predicates
In predicate calculus, propositions are represented in a formal mathematical manner as predicates. A predicate is a function that evaluates to true or false based on the values of the variables in it. For instance, Philosopher (Pascal) is a predicate, where Philosopher is the predicate symbol or functor and Pascal is the argument. Predicates can be used to represent knowledge that cannot be reasonably represented in propositional calculus. The following are examples of atomic propositions in predicate calculus:
In the first example, Philosopher is called the functor. In the second example, Lucia, Leisel is the ordered list of arguments. When the functor and the ordered list of arguments are written together in the form of a function as one element of a relation, the result is called a compound term. The following are examples of compound propositions in predicate calculus:
The universal and existential logical quantifiers, ∀ and ∃, respectively, introduce variables into propositions (Table 14.4):
Table 14.4 Quantifiers in Predicate Calculus
Quantifier | Example | Semantics |
|---|---|---|
Universal | ∀X.P | For all X, P is true. |
Existential | ƎX.P | There exists a value of X such that P is true. |
These two logical quantifiers have the highest precedence in predicate calculus. The scope of a quantifier is limited to the atomic proposition that it precedes unless it precedes a parenthesized compound proposition, in which case it applies to the entire compound proposition.
Propositions are purely syntactic and, therefore, have no intrinsic semantics— they can mean whatever you want them to mean. In Symbolic Logic and the Game of Logic, Lewis Carroll wrote:
I maintain that any writer of a book is fully authorised in attaching any meaning he likes to a word or phrase he intends to use. If I find an author saying, at the beginning of his book, “Let it be understood that by the word ‘black’ I shall always mean ‘white,’ and by the word ‘white’ I shall always mean ‘black,”’ I meekly accept his ruling, however injudicious I think it.
14.3.2 Conjunctive Normal Form
A proposition can be stated in multiple ways. While this redundancy is acceptable for pure symbolic logic, it poses a problem if we are to implement predicate calculus in a computer system. To simplify the process by which new propositions are deduced from known propositions, we use a standard syntactic representation for a set of well-formed formulas (wffs). To do so we must convert each individual wff in the set of wffs into conjunctive normal form (CNF), which is a representation for a proposition as a flat conjunction of disjunctions:
Each parenthesized expression is called a clause. A clause is either a (1) term or literal; (2) a disjunction of two or more literals; or (3) the empty clause represented by the symbol ø or □. We convert each wff in our knowledge base to a set of clauses:
a wff → awffin CNF → a set of clauses
Thus, the entire knowledge base is represented as a set of clauses:
While converting a proposition to CNF, we can use the equivalence between p ⊃ q and ¬p ∨ q to eliminate ⊃ in propositions. The commutative, associative, and distributive rules of Boolean algebra as well as DeMorgan’s Laws are also helpful for rewriting propositions in CNF (Table 14.5). For instance, using DeMorgan’s Laws we can express implication using conjunction and negation:
Table 14.5 The Commutative, Associative, and Distributive Rules of Boolean Algebra as Well as DeMorgan’s Laws Are Helpful for Rewriting Propositions in CNF.
Law | Expression |
|---|---|
Commutative | p ᴠ q ≡ q ᴠ p |
Associative | (p ᴠ q) ᴠ r ≡ p ᴠ (q ᴠ r) |
Distributive | (p ∧ q) ᴠ r ≡ (p ᴠ r) ∧ p) ᴠ r) |
DeMorgan’s | ¬(p ᴠ q) ≡ ¬p ∧¬q |
The following are the propositions given previously expressed in CNF:
Additional examples of propositions in CNF include:
The use of CNF has multiple advantages:
Existential quantifiers are unnecessary.
Universal quantifiers are implicit in the use of variables in the atomic propositions.
No operators other than conjunction and disjunction are required.
All predicate calculus propositions can be converted to CNF.
The purpose of representing wffs in CNF is to deduce new propositions from them. The question is: What can we logically deduce from known axioms and theorems (i.e., the knowledge base) represented in CNF (i.e., KB ⊨ α)? To answer this question we need rules of inference, sometimes collectively referred to as a deductive apparatus. A rule of inference particularly applicable to logic programming is the rule of resolution. The purpose of representing a set of propositions as a set of clauses is to simplify the process of resolution.
6. The qualifier first-order implies that in this system of logic, there is no means by which to reason about the predicates themselves.