Predicate Calculus

Predicate Calculus

Syntax

Predicate calculus allows us to reason about properties of objects and relationships between objects.

In propositional calculus, we could express the English statement “I like cheese” by A. This enables us to create constructs such as ￢A, which means

“I do not like cheese,” but it does not allow us to extract any information about the cheese, or me, or other things that I like.

In predicate calculus, we use predicates to express properties of objects. So the sentence “I like cheese” might be expressed as L(me, cheese) where L is a predicate that represents the idea of “liking.” Note that as well as expressing a property of me, this statement also expresses a relationship between me and cheese. This can be useful, as we will see, in describing environments for robots and other agents.

For example, a simple agent may be concerned with the location of various blocks, and a statement about the world might be T(A,B), which could mean: Block A is on top of Block B.

It is also possible to make more general statements using the predicate calculus.

For example, to express the idea that everyone likes cheese, we might say ( x)(P(x)→L(x, C))

The symbol is read “for all,” so the statement above could be read as “for every x it is true that if property P holds for x, then the relationship L holds between x and C,” or in plainer English: “every x that is a person likes cheese.” (Here we are interpreting P(x) as meaning “x is a person” or, more precisely, “x has property P.”)

Note that we have used brackets rather carefully in the statement above.

This statement can also be written with fewer brackets: x P(x) →L(x, C), is called the universal quantifier.

The quantifier can be used to express the notion that some values do have a certain property, but not necessarily all of them: ( x)(L(x,C))

This statement can be read “there exists an x such that x likes cheese.”

This does not make any claims about the possible values of x, so x could be a person, or a dog, or an item of furniture. When we use the existential quantifier in this way, we are simply saying that there is at least one value of x for which L(x,C) holds.

The following is true: ( x)(L(x,C))→( x)(L(x,C)), but the following is not: ( x)(L(x,C))→( x)(L(x,C))

It is also possible to combine the universal and existential quantifiers, such as in the following statement: ( x) ( y) (L(x,y)).

This statement can be read “for all x, there exists a y such that L holds for x and y,” which we might interpret as “everyone likes something.”

A useful relationship exists between and . Consider the statement “not everyone likes cheese.” We could write this as

￢(  x)(P(x)→L(x,C)) -------------- (1)

As we have already seen, A→B is equivalent to ￢A ∨ B. Using DeMorgan’s laws, we can see that this is equivalent to ￢(A ∧ ￢B). Hence, the statement (1) above, can be rewritten

￢(  x)￢(P(x) ∧ ￢L(x,C)) ------------- (2)

This can be read as “It is not true that for all x the following is not true: x is a person and x does not like cheese.” If you examine this rather convoluted sentence carefully, you will see that it is in fact the same as “there exists an x such that x is a person and x does not like cheese.” Hence we can rewrite it as ( x)(P(x) ∧ ￢L(x,C)) ------------- (3)

In making this transition from statement (2) to statement (3), we have utilized the following equivalence: x ￢( x)￢

In an expression of the form ( x)(P(x, y)), the variable x is said to be bound, whereas y is said to be free. This can be understood as meaning that the variable y could be replaced by any other variable because it is free, and the expression would still have the same meaning, whereas if the variable x were to be replaced by some other variable in P(x,y), then the meaning of the expression would be changed: (  x)(P(y, z)) is not equivalent to (  x)(P(x, y)),

whereas (  x)(P(x, z)) is.

Note that a variable can occur both bound and free in an expression, as in ( x)(P(x,y,z) → ( y)(Q(y,z)))

In this expression, x is bound throughout, and z is free throughout; y is free in its first occurrence but is bound in ( y)(Q(y,z)). (Note that both occurrences of y are bound here.)

Making this kind of change is known as substitution.

Substitution is allowed of any free variable for another free variable.

Functions

In much the same way that functions can be used in mathematics, we can express an object that relates to another object in a specific way using functions.

For example, to represent the statement “my mother likes cheese,” we might use L(m(me),cheese)

Here the function m(x) means the mother of x. Functions can take more than

one argument, and in general a function with n arguments is represented as f(x1, x2, x3, . . . , x_n)