10. Predicate Logic 10.1 Introduction - Harvey Mudd College

1 10. Predicate IntroductionPredicate Logic builds heavily upon the ideas of proposition Logic to provide a morepowerful system for expression and reasoning. As we have already mentioned, apredicate is just a function with a range of two values, say false and true. We alreadyuse predicates routinely in programming, in conditional statements of the formif( p(..args ..) )Here we are using the two possibilities for the return value of p, (true or false). Wealso use the propositional operators to combine predicates , such as in:if( p(.))

2 && ( !q(..) || r(..) ) ) Predicate Logic deals with the combination of predicates using the propositionaloperators 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 ValueNow we explain this interpretation for a Predicate Logic expression consists of:a domain for each variable in the expressiona Predicate for each Predicate symbol in the expressiona function for each function symbol in the expressionNote that the propositional operators are not counted as function symbols in the case ofpredicate Logic , even though they represent functions .

3 The reason for this is that we donot wish to subject them to interpretations other than the usual propositionalinterpretation. 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 truthvalues used by propositional operators, from functions that operate on arbitrary , as with proposition Logic , the stand-alone convention applies withpredicates: We do not usually explicitly indicate == 1 when a Predicate expression istrue.

4 Rather we just write the Predicate along with its arguments, standing Predicate LogicAn assignment for a Predicate Logic expression consists of:a value for each variable in the expressionGiven an assignment, a truth value is obtained for the entire expression in the the expression:x < y || ( y < z && z < x) ^ ^ ^ Predicate symbolsHere || and && are propositional operators and < is a Predicate symbol (in infix notation).

5 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 valueis that of3 < 1 || ( 1 < 2 && 2 < 3)which isfalse || ( true && true) respect to the same assignment for <, but 3, 2, 1 for x, y, z, the value would be thatof3 < 2 || ( 2 < 1 && 1 < 3)which would be false. As long as we have assigned meanings to all variables andpredicates in the expression, we can derive a false or true value.

6 Now we give anexample where function symbols, as well as Predicate symbols, are present.( (u + v) < y ) || ( (y < (v + w)) && v < x) ^ ^ function symbolswould be an example of an expression with both function and Predicate symbols. If weassign + and < their usual meanings and u, v, w, x, y the values 1, 2, 3, 4, 5 respectively,this would evaluate to the value of( (1 + 2) < 4 ) || ( (4 < (2 + 3)) && 2 < 4 )which is, of course, Logic 381 ValidityIt is common to be concerned with a fixed interpretation (of domains, predicates , andfunctions) and allow the assignment to vary over individuals in a domain.

7 If a formulaevaluates to true for all assignments, it is called valid with respect to the a formula is valid with respect to every interpretation, it is called valid. A special caseof validity is where sub-expressions are substituted for proposition symbols in atautology. These are also called tautologies. However, not every valid formula is atautology, as is easily seen when we introduce quantifiers later A Database ApplicationAn important use of Predicate Logic is found in computer databases and the more generalnotion of "knowledge base", defined to be a database plus various computation rules.

8 Inthis application, it is common to use Predicate expressions containing variables as aboveas "queries". The predicates themselves represent the underlying stored data, computablepredicates, or combinations thereof. A query asks the system to find all individualscorresponding to the variables in the expression such that the expression is satisfied(evaluates to 1). Next we demonstrate the idea of querying a database using the Prologlanguage as an example. Prolog is not the most widely-used database query language; alanguage known as SQL (Structured Query Logic ) probably has that distinction.

9 ButProlog is one of the more natural to use in that it is an integrated query language andprogramming Database ExampleThere are many ways to represent the predicates in a database, such as by structured filesrepresenting tables, spreadsheet subsections, etc. In the language Prolog, one of the waysto represent a Predicate is just by enumerating all combinations of values for which thepredicate is true. Let us define the predicates mother and father in this fashion. Thesepredicates provide a way of modeling the family "tree" on the Predicate Logicmother(alice, tom).

10 Mother(alice, carol).mother(carol, george).mother(carol, heather).mother(susan, hank).father(john, tom).father(john, carol).father(fred, george).father(fred, heather).father(george, hank).alicecaroltomgeorgesusanhankjohnfr edheatherFigure 163: A family "tree" modeled as two predicates , mother and is possible for a query to contain no variables, in which case we would expect ananswer of 1 or 0. For example,mother(susan, hank) truemother(susan, tom) falseMore interestingly, when we put variables in the queries, we expect to get values forthose variables that satisfy the Predicate :mother(alice, X) X = tom; X = carol (two alternatives for X)father(tom, X) false (no such X exists)mother(X, Y) (several alternative combinations for X, Y)X = alice, Y = tom;X = alice, Y = carol;X = carol, Y = george;X = carol, Y = heather.