Predicate Logic - Stanford University

1 CHAPTER14FF FFPredicateLogicWe now turn our attention to a generalization of propositional Logic , called predi-cate, or first-order, Logic . predicates are functions ofzero or more variables thatreturn Boolean values. Thus predicates can be true sometimes and false sometimes,depending on the values of their arguments. For example, we shall find in predicatelogic atomic operands such ascsg(C, S, G). Here,csgis the Predicate name, andC,S, andGare arguments. We can think of this expression as a representationin Logic of the database relation Course-Student-Grade of Fig.

2 It returns thevalueTRUE whenever the values ofC,S, andGare such that studentSgot gradeGin courseC, and it predicates as atomic operands, instead of propositional variables, givesus a more powerful language than expressions involving onlypropositions. In fact, Predicate Logic is expressive enough to form the basis of a number of useful program-ming languages, such as Prolog (which stands for Programming inlogic ) and thelanguage SQL that we mentioned in Section Predicate Logic is also used in rea-soning systems or expert systems, such as automatic medical diagnosis programsand theorem-proving What This Chapter Is AboutWe introduce predicates in Section As we shall see, predicates provide muchgreater power to express ideas formally than do propositional variables.

3 Much ofthe development of Predicate Logic parallels that of propositional Logic in Chapter12, although there are important of Predicate Logic can be built from predicatesusing the operatorsof propositional Logic (Section ).F Quantifiers are operators of Predicate Logic that have no counterpart inpropositional Logic (Section ). We can use quantifiers to state that anexpression is true for all values of some argument or that there exists at leastone value of the argument that makes the expression LOGICF Interpretations for expressions of Predicate Logic are possible meanings forthe predicates and variables (Section ).

4 They are analogous to truth as-signments in propositional of Predicate Logic are expressions that are true for all interpreta-tions. Some tautologies of Predicate Logic are analogs of tautologies for propo-sitional Logic (Section ), while others are not (Section ).FProofs in Predicate Logic can be carried out in a manner similar to proofs inpropositional Logic (Sections and ).In Section we discuss some of the implications of Predicate Logic as to ourability to compute answers to questions. We shall discover the following:FA statement s being a tautology does not mean that it is provable in certainproof particular, G odel s incompleteness theorem tells us that there is a specializedform of Predicate Logic , dealing with the integers, in whichno proof system canprovide proofs of every , Turing s theorem tells us that there are problems we can state butcannot solve by any computer.

5 An example is whether or not a given C programgoes into an infinite loop on certain PredicatesA Predicate is a generalization of a propositional variable. Recalling Section ,suppose that we have three propositions:r( It is raining ),u( Joe takes hisumbrella ), andw( Joe gets wet ). Suppose further that we have three hypotheses,or expressions that we assume are true:r u( If it rains, then Joe takes hisumbrella ),u w( If Joe takes an umbrella, then he doesn t get wet ), and r w( If it doesn t rain, Joe doesn t get wet ).

6 What is true for Joe is also true for Mary, and Sue, and Bill, and so on. Thuswe might think of the propositionuasuJoe, whilewis the propositionwJoe. If wedo, we have the hypothesesr uJoe,uJoe wJoe, and r wJoeIf we define the propositionuMaryto mean that Mary takes her umbrella, andwMaryto mean that Mary gets wet, then we have the similar set of hypothesesr uMary,uMary wMary, and r wMaryWe could go on like this, inventing propositions to talk about every individualXwe know of and stating the hypotheses that relate the propositionrto the newpropositionsuXandwX, namely,r uX,uX wX, and r have now arrived at the notion of a Predicate .

7 Instead of aninfinite col-lection of propositionsuXandwX, we can define symboluto be a Predicate thattakes an argumentX. The expressionu(X) can be interpreted as saying Xtakeshis or her umbrella. Possibly, for some values ofX,u(X) is true, and for othervalues ofX,u(X) is false. Similarly,wcan be a Predicate ; informallyw(X) says Xgets wet. The propositional variablercan also be treated as a Predicate with zero argu-ments. That is, whether it is raining does not depend on the individualXthe can now write our hypotheses in terms of the predicates as u(X).

8 (For any individualX, if it is raining, thenXtakes his or herumbrella.) (X) NOTw(X). (No matter who you are, if you take your umbrella, thenyou won t get wet.) NOTw(X). (If it doesn t rain, then nobody gets wet.)Atomic FormulasAnatomic formulais a Predicate with zero or more arguments. For example,u(X)is an atomic formula with predicateuand one argument, here occupied by thevariableX. In general, an argument is either a variable or a , inprinciple, we must allow any sort of value for a constant, we shall usually imaginethat values are integers, reals, or character andconstantsVariables are symbols capable of taking on any constant as value.

9 We shouldnot confuse variables in this sense with propositional variables, as used in Chap-ter 12. In fact, a propositional variable is equivalent to a Predicate with no argu-ments, and we shall writepfor an atomic formula with Predicate namepand atomic formula all of whose arguments are constants is called agroundatomic formula. Nonground atomic formulas can have constants or variables asGround atomicformulaarguments, but at least one argument must be a variable. Notethat any proposition,being an atomic formula with no arguments, has all arguments constant, and istherefore a ground atomic Constants From VariablesWe shall use the following convention to distinguish constants from variables.

10 Avariable name will always begin with an upper-case letter. Constants are representedeither by1. Character strings beginning with a lower-case letter,2. Numbers, like 12 or , or3. Quoted character Logic also allows arguments that are more complicated expressions than singlevariables or constants. These are important for certain purposes that we do not discuss inthis book. Therefore, in this chapter we shall only see variables and constants as argumentsof LOGICThus, if we want to represent course CS101 by a constant, we could write it as CS101 , for , like constants, will be represented by character strings beginningwith a lower-case letter.