Home | | Artificial Intelligence | Predicate Calculus

# Predicate Calculus

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

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, . . . , xn)

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Predicate Calculus |