1 Predicate Logic • Predicate logic is an extension of propositional logic that permits concisely reasoning about whole classes of entities. E.g., “x>1”, “x+y=10” • Such statements are neither true or false when the values of the variables are not specified.
2 Applications of Predicate Logic • It is the formal notation for writing perfectly clear, concise, and unambiguous mathematical definitions, axioms, and theorems for any branch of mathematics. • Supported by some of the more sophisticated database query engines. • Basis for automatic theorem provers and many other Artificial Intelligence systems.
3 Subjects and Predicates • The proposition “The dog is sleeping” has two parts: ° “the dog” denotes the subject - the object or entity that the sentence is about. ° “is sleeping” denotes the predicate- a property that the subject can have.
4 Propositional Functions • A predicate is modeled as a function P(·) from objects to propositions. ° P(x) = “x is sleeping” (where x is any object). • The result of applying a predicate P to an object x=a is the proposition P(a). ° e.g. if P(x) = “x > 1”, then P(3) is the proposition “3 is greater than 1.” • Note: The predicate P itself (e.g. P=“is sleeping”) is not a proposition (not a complete sentence).
5 Propositional Functions • Predicate logic includes propositional functions of any number of arguments. e.g. let P(x,y,z) = “x gave y the grade z”, x=“Mike”, y=“Mary”, z=“A”, P(x,y,z) = “Mike gave Mary the grade A.”
• example: Q(x,y) = ( x=y+3 ).
Q(1,2) = ( 1=2+3 ) = F Q(3,0) = ( 3=0+3) = T
6 Universe of Discourse • The collection of values that a variable x can take is called x’s universe of discourse. e.g., let P(x)=“x+1>x”. we could define the course of universe as the set of integers.
7 Quantifier Expressions • Quantifiers allow us to quantify (count) how many objects in the universe of discourse satisfy a given predicate: - “"” is the FOR"LL or universal quantifier. "x P(x) means for all x in the u.d., P holds.
- “$” is the $XISTS or existential quantifier.
$x P(x) means there exists an x in the u.d. (that is, one or more) such that P(x) is true. 8 Universal Quantifier ": Example • Let P(x) be the predicate “x is full.” • Let the u.d. of x be parking spaces at UNR. • The universal quantification of P(x), "x P(x), is the proposition: ° “All parking spaces at UNR are full.” or ° “Every parking space at UNR is full.” or ° “For each parking space at UNR, that space is full.”
9 The Universal Quantifier " • To prove that a statement of the form "x P(x) is false, it suffices to find a counterexample (i.e., one value of x in the universe of discourse such that P(x) is false)
° e.g., P(x) is the predicate “x>0”
° See p.32 ex:10 & 12 & 17 in your book.
10 Existential Quantifier $ Example • Let P(x) be the predicate “x is full.” • Let the u.d. of x be parking spaces at UNR. • The universal quantification of P(x), $x P(x), is the proposition: ° “Some parking space at UNR is full.” or ° “There is a parking space at UNR that is full.” or ° “At least one parking space at UNR is full.”
11 Quantifier Equivalence Laws • Definitions of quantifiers: If u.d.=a,b,c,… "x P(x) Û P(a) Ù P(b) Ù P(c) Ù … $x P(x) Û P(a) Ú P(b) Ú P(c) Ú … • We can prove the following laws: "x P(x) Û ¬$x ¬P(x) $x P(x) Û ¬"x ¬P(x) • Which propositional equivalence laws can be used to prove this? 12 More Equivalence Laws • ¬$x P(x) Û "x ¬ P(x) It is not true that there exists an x for which P(x) is true Or ¬"x P(x) Û $x ¬ P(x) P(x) must be false for all x
It is not the case that for all x P(x) is true or
there must be an x for which P(x) is not true
• "x "y P(x,y) Û "y "x P(x,y)
$x $y P(x,y) Û $y $x P(x,y)
• "x (P(x) Ù Q(x)) Û ("x P(x)) Ù ("x Q(x))
$x (P(x) Ú Q(x)) Û ($x P(x)) Ú ($x Q(x)) 13 Scope of Quantifiers • The part of a logical expression to which a quantifier is applied is called the scope of this quantifier. • The scope of a quantifier is the part of the statement on which it is acting e.g., ("x P(x)) Ù ($y Q(y)) e.g., scope x scope y $x ( P( x) Ù Q( x)) Ú "y R( y )
e.g., ("x P(x)) Ù ($x Q(x)) scope x scope y
14 Free and Bound Variables • An expression like P(x) is said to have a free variable x (meaning x is undefined). • A quantifier (either " or $) operates on an expression having one or more free variables, and binds one or more of those variables, to produce an expression having one or more bound variables.
15 Examples of Binding • P(x,y) has 2 free variables, x and y. • "x P(x,y) has 1 free variable, and one bound variable. [which is which?] • “P(x), where x=3” is another way to bind x. • An expression with zero free variables is an actual proposition. • An expression with one or more free variables is still only a predicate: "x P(x,y)
16 More to Know About Binding • "x $x P(x) - x is not a free variable in $x P(x), therefore the "x binding isn’t used. • ("x P(x)) Ù Q(x) - The variable x is outside of the scope of the "x quantifier, and is therefore free. Not a proposition. • ("x P(x)) Ù ($x Q(x)) - Legal because there are 2 different x’s! • Quantifiers bind as loosely as needed: parenthesize "x (P(x) Ù Q(x) ) 17 Nested Quantifiers Exist within the scope of other quantifiers • Let the u.d. of x & y be people. • Let P(x,y)=“x likes y” (a predicate with 2 f.v.’s) • Then $y P(x,y) = “There is someone whom x likes.” (a predicate with 1 free variable, x) • Then "x ($y P(x,y)) = “Everyone has someone whom they like.” (A __________ with ___ free variables.)
18 Order of Quantifiers Is Important!!
If P(x,y)=“x relies upon y,” express the
following in unambiguous English: "x($y P(x,y))= $y("x P(x,y))= $x("y P(x,y))= "y($x P(x,y))= "x("y P(x,y))= 19 Natural language is ambiguous! • “Everybody likes somebody.” ° For everybody, there is somebody they like, • "x $y Likes(x,y) [Probably more likely.] ° or, there is somebody (a popular person) whom everyone likes? • $y "x Likes(x,y)
20 Notational Conventions • Consecutive quantifiers of the same type can be combined: "x "y "z P(x,y,z) Û "x,y,z P(x,y,z) or even "xyz P(x,y,z) • Sometimes the universe of discourse is restricted within the quantification, e.g., ° "x>0 P(x) is shorthand for “For all x that are greater than zero, P(x).” ° $x>0 P(x) is shorthand for “There is an x greater than zero such that P(x).”
21 Defining New Quantifiers As per their name, quantifiers can be used to express that a predicate is true of any given quantity (number) of objects. Define $!x P(x) to mean “P(x) is true of exactly one x in the universe of discourse.” $!x P(x) Û $x (P(x) Ù ¬$y (P(y) Ù y¹ x)) “There is an x such that P(x), where there is no y such that P(y) and y is other than x.” 22 Some Number Theory Examples • Let u.d. = the natural numbers 0, 1, 2, … • “A number x is even, E(x), if and only if it is equal to 2 times some other number.” "x (E(x) « ($y x=2y)) • “A number is prime, P(x), iff it isn’t the product of two non-unity numbers.” "x (P(x) « (¬$y,z x=yz Ù y¹1 Ù z¹1))
23 Calculus Example • Precisely defining the concept of a limit using quantifiers: (lim f ( x) = L)Û x®a
æ "e > 0 : $d > 0 : "x : ö
çç ÷÷ è (| x - a |< d ) ® (| f ( x) - L |< e )ø
• See Example 15 on page 49.
24 Study!
25 • Solve the exercises on pages 40-44: #’s: 7, 12, 25, 33, 37, 40, 48, 49.
