Quantifiers and its Types

QUANTIFIERS
TYPES OF QUANTIFIERS
QUANTIFIERS WITH RESTRICTED DOMAIN
NEGATION AND QUANTIFERS
EXPRESS QUANTIFIER IN ENGLISH
Nested QUANTIFIER

1. Group # 1 Adnan Yousaf 1001 Humayun Naseer 5054 Aiza Mukhtar 1003 Ummema Ali Sher 5064 DS Presentation Discrete Structures

2. OUTLINE: QUANTIFIERS TYPES OF QUANTIFIERS QUANTIFIERS WITH RESTRICTED DOMAIN NEGATION AND QUANTIFERS EXPRESS QUANTIFIER IN ENGLISH Nested QUANTIFIER

3. QUANTIFIERS: In natural languages, a quantifier turns a sentence about something having some property into a sentence about the number (quantity) of things having the property. Examples of quantifiers in English are "all", "some", "many", "few", " most", and "no"; examples of quantified sentences are "all people are mortal", "some people are mortal", and "no people are mortal", they are considered to be true, true, and Quantifiers  are expressions that indicate the scope of the term to which they are attached, here predicates. A  predicate  is a property the subject of the statement can have. For example, in the statement  “the sum of x and y is greater than 5” , the predicate ‘Q’ is- sum is greater than 5, and the statement can be represented as Q(x, y) where x and y are variables

4. TYPES: 1) UNIVERSAL QUANTIFIER: The universal quantification of a predicate P(x) is the proposition “P(x) is true for all values of x in the universe of discourse [ the universe of discourse is the set of all things we wish to talk about; that is, the set of all objects that we can sensibly assign to a variable in a propositional function ] ” We use the notation ∀ xP (x) which can be read “for all x” 2) EXISTENTIAL QUANTIFIER: The existential quantification of P(x) is the proposition “There exists an element x in the universe of discourse such that P(x) is true.”

5. Notation: “There exists x such that P(x)” or “There is at least one x such that P(x)” is written ∃ xP (x). NOTE: Universal( ∀ ) –  The predicate is true for all values of x in the domain. Existential( ∃ ) –  The predicate is true for at least one x in the domain EXAMPLE 1: Suppose P(x) is the predicate x + 2 = 2x, and the universe of discourse for x is the set {1, 2, 3}. Then... • ∀ xP (x) is the proposition “ For every x in {1, 2, 3} x + 2 = 2x.” This proposition is false. • ∃ xP (x) is the proposition “ There exists x in {1, 2, 3} such that x + 2 = 2x. ” This proposition is true.

6. EXAMPLE 2: Let P(x) be the predicate “x must take a discrete mathematics course” and let Q(x) be the predicate “x is a computer science student”. The universe of discourse for both P(x) and Q(x) is all UNL students. Express the statement “Every computer science student must take a discrete mathematics course”. ∀ x(Q(x) → P(x)) Express the statement “Everybody must take a discrete mathematics course or be a computer science student”. ∀ x(Q(x) ∨ P(x))

7. EXAMPLE 3: Express the statement “for every x and for every y, x + y > 10” Let P(x, y) be the statement x + y > 10 where the universe of discourse for x, y is the set of integers. Answer: ∀ x ∀ yP (x, y) Note that we can also use the shorthand ∀ x, yP (x, y) QUANTIFERS WITH RESTRICTED DOMAIN: As we know that quantifiers are meaningless if the variables they bind do not have a domain. The following abbreviated notation is used to restrict the domain of the variables-

8. W hat is the truth value of ∀ x <0 --  (x^2 =1) Domain is all real numbers. Solution: Find just 1 counter example to make ∀ x <0 --  (x^2 =1) FALSE It can be written as ∀ ( x <0 --  x^2 =1) ( -2 <0 ___> (-2)^ 2 =1) ( -2<0 ____> 4=1) T_____> F =F So , ∀ x <0 --  (x^2 =1) is FALSE Q 2 : What is truth value of ∃ x p(x) “x^2 >0 “ domain “ positive integer not exceeding 4? {1,2,3,4} Answer: P(x) : x ^2 > 10 P(1) = (1)^2 > 10 FALSE P(2) =2^2 > 10 FALSE P(3) = 3^2 > 10 FALSE P(4) =4^2 > 10 TRUE Here ∃ x p(x) “x^2 >0 is true

9. NEGATION AND QUANTIFIERS: EXAMPLE : All Dogs Barks ______  ∀ dogs , d barks _____> ¬ ( ∀ dogs , d barks) ____> ∃ dogs , ¬ d barks ______> ∃ dogs , d does not bark ______> “Some Dogs does not bark” Example : Problem: • Express the statement “Not everybody can ride a bike” as a logical expression. Solution: • Let P(x)=“x can ride a bike.” • The statement “everybody can ride a bike,” can be expressed as ∀ x P(x). • We want the negation of this, which is ¬ ∀ x P(x). • Another way to say this is “There is somebody that cannot ride a bike,” which can be expressed as ∃ x ¬ P(x).

10. EXAMPLE : • Express the statement “Nobody can fly.” as a logical expression. Solution : • Let P(x)=“x can fly.” • The statement “somebody can fly,” can be expressed as ∃ x P(x). • We want the negation of this, which is ¬ ∃ x P(x). • Another way to say this is “Everybody can not fly,” which can be expressed as ∀ x ¬ P(x).

11. EXPRESS QUANTIFIER IN ENGLISH STATEMENTS : QUESTION 1: ∀ x P(x). mean if p(x) “ x is perfect “ Domain is “of people in your locality” ANSWER: AS we know that ∀ x P(x). For all x P(x). For every x P(x). For each x P(x). All of x P(x). For any x P(x). It can be written as : All people in your locality are perfect . Every people in your locality are perfect Each people in your locality are perfect

12. QUESTION 2: There is a student who has taken more than 21 credit hour in a semester and received all A grade   ANSWER: Domain: “All student” P(x) = x student who has taken more than 21 credit hour in a semester And S(x) = received all A grade So; ∃ x[ P(x) ^ s(x)]   QUESTION 3: Let N(x) be the statement “ x has visited north korea “ where the domain is : consist of the students in your school “ .. Express ∀ x N(x) in English ? ANSWER: For every x in the domain of the students in your school , x has visited North korea . All students in your school has visited north korea .

13. NESTED QUANTIFIER : Two quantifiers are nested if one is within the scope of the other . Example: ∀ x ∃ y (x + y = 0) ∀ x Q(x) Q(x) is ∃ y P( x,y ) P( x,y ) is (x + y = 0) EXAMPLE: Translate the following statement into English. x y (x + y = y + x) Domain: real numbers

14. Domain: real numbers Solution: For all real numbers x and y, x + y = y + x Example-1: ∀ x ∃ y ( x+y =5) Here ‘ ∃ ’ (read as-there exists) and ‘ ∀ ’ (read as-for all) are quantifiers for variables x and y. The statement can be represented as- ∀ x Q(x) Q(x) is ∃ y P(x, y)   Q(x)-the predicate is a function of only x because the quantifier applies only to variable x. P(x, y) is (x + y = 5)

15. EXAMPLE : Let x and y be the real numbers and p( x,y ) denotes “ x+y =0” Find the truth value of : ∀ x ∀ y p( x,y ) ∀ x ∃ y p( x,y ) ∃ y ∀ x p( x,y ) ∃ x ∃ y p( x,y )   SOLUTION : Domain : All real numbers a) ∀ x ∀ y p( x,y ) ≡ ∀ x ∀ y (x=y=0) “for all real numbers x and y , x+y =0” It is not TRUE e.g 2+1 not equal to 0 so it is FALSE

16. b) ∀ x ∃ y p( x,y ) “for ever real numbers x ,there exist a real number y such that x+y =0” IT IS TRUE: For example: X=1 ,-1 , 1/2 Y =-1 ,1 ,-1/2 STEPS : Consider all different value of x. Find just 1 value of y for each of x such that p( x,y ) becomes true. Value of y depend on the value of x

17. c) ∃ y ∀ x p( x,y ) “there exist some real number y such that for every real number x , x+y =0” IT IS not TRUE Prove: It is asking us to find a real number y for which p( x,y ) becomes true by plugging in every real number x. As we know that : P( x,y ) = x+y =0 First take sum real number y=1 P(x,1) =x+1 =0 Now , plug in all real numbers of x P(1/2,1) is false , p(1,1) is false and soo on… No matter what y you choose , p( x,y ) is always false for all real numbers SO IT IS FALSE

18. d) ∃ x ∃ y p( x,y ) “there exist some real numbes x and y such that x+y =0:” Surely : There exist some combination of real numbers x and y exist for which x +y=0 For example : Take x=1 and y=-1 1+(-1) =0 is True So this is true