Predicates and quantifiers

Discrete mathematics

1. Predicates and Quantifiers Discrete Mathematics Page 1 1

2. Slide Owner Istiak Ahmed Email- [email protected] Page 2 2

3. Propositional Logic Atomic propositions: p , q , r , … Boolean operators:       Compound propositions: ( p   q )  r Equivalences: p  q ≡  ( p  q ) Proving equivalences using: Truth tables. Symbolic derivations (Laws). Page 3 3

4. Predicate Logic Predicate logic is an extension of propositional logic It permits concisely reasoning about whole classes of entities. Examples of a class is an integer class, a student in CSE Dept , etc. Page 4 4

5. 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. Statements like x > 5 are neither true nor false when the value of x is not specified. Predicate logic can be used to make propositions from such statements. Page 5 5

6. Subjects and Predicates Example “The dog is sleeping”: In predicate logic, a predicate is modeled as a function P ( ) from objects to propositions. P ( x ) = “ x is sleeping” (where x is any object). Page 6 6

7. More About Predicates Convention: Lowercase variables x , y , z... denote objects/entities; uppercase variables P , Q , R … denote propositional functions (predicates). The result of applying a predicate P to an object x is the proposition P ( x ). The predicate P itself ( e.g. P =“is sleeping”) is not a proposition (not a complete sentence). Page 7 7

8. Propositional Functions Predicate logic can also involve statements with more than one variable or argument. E.g. let P ( x , y,z ) = “ x gave y the grade z ”, then if x= “Mike”, y =“Mary”, z =“A”, then P ( x , y , z ) = “Mike gave Mary the grade A.” E.g. let Q( x , y,z ) = “ x + y > z ”, then what is the truth value of Q(1,2,3)? – False Q(3,2,1)? -True Page 8 8

9. Universes of Discourse A mathematical function may be valid for all values of a variable in a particular domain, called the universe of discourse. E.g., let P ( x )=“ x +1> x ”. We can then say, “For any number x , P ( x ) is true” instead of ( +1> )  ( 1 +1> 1 )  ( 2 +1> 2 )  ... Page 9 9

10. Quantifier Expressions “” is the FOR LL or universal quantifier.  x P ( x ) means “P(x) is true for all values of x in the universe of discourse”. “” is the XISTS or existential quantifier.  x P ( x ) means “there exists an x in the u.d . (that is, 1 or more) such that P ( x ) is true”. Page 10 10

11. The Universal Quantifier  Example: Let the u.d . of x be parking spaces at BU. Let P(x) be the predicate “x is full.” Then the universal quantification of P(x), x P(x), is the proposition: “All parking spaces at BU are full.” “Every parking space at BU is full.” “For each parking space at BU, that space is full.” Page 11 11

12. The Existential Quantifier  Example: Let the u.d . of x be parking spaces at BU . Let P ( x ) be the predicate “ x is full.” Then the existential quantification of P ( x ),  x P ( x ), is the proposition : “There is a parking space at BU that is full.” “At least one parking space at BU is full.” “Some parking spaces at BU is full.” Page 12 12

13. 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)  …  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 ) ) Page 13 13

14. Negation Example  x P ( x ) ≡  x  P ( x ) P(x)=“x is a student of cse ” where u.d . is the students of this class So,  x P ( x ) = “All students in this class is a student of cse ” The negation of this  x P ( x ) = “Not every student in this class is a student of cse ” This is the same as  x  P ( x ) = “There is a student x who is not a student of cse ” Page 14 14

15. Thanks To All Page 15 15