10. Predicate Logic 10.1 Introduction - Harvey Mudd College

[Pages:42]10. Predicate Logic

10.1 Introduction

Predicate logic builds heavily upon the ideas of proposition logic to provide a more powerful system for expression and reasoning. As we have already mentioned, a predicate is just a function with a range of two values, say false and true. We already use predicates routinely in programming, e.g. in conditional statements of the form

if( p(...args ...) )

Here we are using the two possibilities for the return value of p, (true or false). We also use the propositional operators to combine predicates, such as in:

if( p(....) && ( !q(....) || r(....) ) )

Predicate logic deals with the combination of predicates using the propositional operators we have already studied. It also adds one more interesting element, the "quantifiers".

The meaning of predicate logic expressions is suggested by the following:

Expression + Interpretation + Assignment = Truth Value

Now we explain this equation.

An interpretation for a predicate logic expression consists of:

a domain for each variable in the expression

a predicate for each predicate symbol in the expression

a function for each function symbol in the expression

Note that the propositional operators are not counted as function symbols in the case of predicate logic, even though they represent functions. The reason for this is that we do not wish to subject them to interpretations other than the usual propositional interpretation. Also, we have already said that predicates are a type of function. However, we distinguish them in predicate logic so as to separate predicates, which have truth values used by propositional operators, from functions that operate on arbitrary domains. Furthermore, as with proposition logic, the stand-alone convention applies with predicates: We do not usually explicitly indicate == 1 when a predicate expression is true; rather we just write the predicate along with its arguments, standing alone.

380

Predicate Logic

An assignment for a predicate logic expression consists of:

a value for each variable in the expression

Given an assignment, a truth value is obtained for the entire expression in the natural way.

Example

Consider the expression:

x < y || ( y < z && z < x)

^

^

^

predicate symbols

Here || and && are propositional operators and < is a predicate symbol (in infix notation). An assignment is a particular predicate, say the less_than predicate on natural numbers, and values for x, y, and z, say 3, 1, and 2. With respect to this assignment then, the value is that of

3 < 1 || ( 1 < 2 && 2 < 3)

which is

false || ( true && true)

i.e. true.

With respect to the same assignment for ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download