PREDICATES AND QUANTIFIERS Given the following statements: 1. x > 3 2. x = y + 3. 3. x + y = z. 4. Computer x is under attack by an intruder 5.

Computer x is functioning properly

P(x) is said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value. Example 1 Let P(x) denote the statement x > 3. Determine the truth value of the propositional function at P(4), P(2). At P(4): 4 > 3 = true At P(2) 2 > 3 = false

Example 2 Let x denote the statement Computer x is under attack by an intruder. Suppose that of the computers on the campus, only CS2 and Math1 are currently under attack by intruders. What are the truth values of A(CS1), A(CS2), A(Math1)? Example 3 Let Q(x,y) denote the statement x = y + 3. What are the truth values of the propositions Q(1,2) and Q(3,0). Example 4 Let A(c,n) denote the statement Computer c is connected to network n where c is a variable representing a computer and n is a variable representing a network. Suppose that the computer MATH1 is connected to the network CAMPUS2 but not to network CAMPUS1. What are the values of A(MATH1,CAMPUS1) and A(MATH1,CAMPUS2)? Example 5 Let R(x,y,z) denote the statement x + y = z. What are the truth values of the propositions R(1,2,3) and R(0,0,1)? Example 6 If x > 0 then x:= x + 1

Example 7
1

Temp := x x := y y := temp

In general, a statement involving the n variables x1, x2,...xn can be denoted by P(x1,x2,...xn) A statement of the form P(x1,x2,...xn) is the value of the propositional function P at the n-tuple (x1,x2...xn), and P is also called a n-place predicate or n-ary predicate. QUANTIFIERS

expresses the extent to which a predicate is true over a range of elements. universal quantification, which tells us that a predicate is true for every element under consideration existential quantification, tells us that there is one or more elements under consideration for which the predicate is true. The area that deals with predicates and quantifiers is called predicate calculus. Universal Quantifier

The universal quantification of P(x) is the statement P(x) for all values of x in the domain. The notation xP(x) denotes the universal quantification of P(x). Here is called the universal quantifier. We read xP(x) as for all x P(x) or for every x P(x). An element for which P(x) is false is called a counterexample of xP(x).

QUANTIFIERS

Statement xP(x)

When true? P(x) is true for every x

When false? There is an x for which P(x) is false. P(x) is false for every x.

xP(x)

There is an x for which P(x) is true

Example 1 Let P(x) be the statement x + 1 > x xP(x), x + 1 > x , for all real numbers. True

Example 2 xP(x), x < 2, for all real numbers. False

by setting x = 3.

counterexample.

Example 3 xP(x), x > 0, for all integers. Example 4 xP(x), x < 10, for positive integers not execeeding 4. Example 5 xN(x), computer x is connected to the network, domain consists of all computers on campus. Example 6 xP(x), x x, all real numbers. Existential Quantifier The existential quantification of P(x) is the proposition there exists an element x in the domain such that P(x). We use the notation xP(x) for the existential quantification of P(x). Here is called the existential quantifier. Could be read as There is an x, such that P(x) or there is at least one x such that P(x), or For some x, P(x). Example 1 xP(x), x > 3, all real numbers. Example 2 xP(x), x =x + 1, all real numbers. Example 3 xP(x), x 10, all real numbers. Other Quantifiers There are exactly two There are no more than three There are at least 100 There are exactly two Uniqueness quantifier Denoted by ! or 1 !xP(x) or 1xP(x) states there exists a unique x such that P(x) is true. Other phrases for uniqueness There is exactly one There is one and only one Binding Variable When a quantifier is used on the variable x, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free. x(x + y =1) Variable x is bound Variable y is free
3

Logical Equivalences Involving Quantifiers Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation ST to indicate that the two statements S and T involving predicates and quantifiers are logically equivalent. Negating Quantified Expressions Consider the negation of the statement Every student in your class has taken a course in calculus. When represented as quantifier will become: xP(x) P(x) is the statement: x has taken a course in calculus Domain student in your class

Negation:

It is not the case that every student in your class has taken a course in calculus. xP(x) There is a student in your class who has not taken a course in calculus. xP(x) xP(x)

This illustrates the following logical equivalence: xP(x)

Consider the proposition: There a student in this class who has taken a course in calculus. xP(x) P(x) is the statement: x has taken a course in calculus Negation: It is not the case that there is a student in this class who has taken a course in calculus. xP(x) Every student in this class has not taken a course in calculus. xP(x)

This example illustrates the equivalence xP(x) xP(x)

De Morgans Laws for Quantifiers Negation Equivalent Statement When is Negation true? When is Negation False?

xP(x)

xP(x)

For every x, P(x) is false

There is an x for which P(x) is true P(x) is true for every x.

xP(x)

xP(x)

There is an x for which P(x) is false

Example 1 There is an honest politician. Let H(x) denote x is honest. There is an honest politician is represented xH(x) The negation of this statement is xH(x) xP(x) All politicians are dishonest. Example 2 All Americans eat cheeseburger. Let C(x) denote x eat cheeseburger. All Americans eat cheeseburger is represented as xC(x) The negation of this statement is xC(x) xC(x) There is an American who does not eat cheeseburger or Some Americans does not eat cheeseburger.

What are the negations of the statements x(x > x) and x(x=2)? x(x > x) is the statement x(x > x) which is equivalent to x(x>2) and can be rewritten as x(x 2) .

x(x=2) is the statement x(x=2) which is equivalent to x(x=2) and can be written as x(x2). Translating from English to Logical Expressions

1. Every student in this class has studied calculus. a) For every student in this class, that student has studied calculus. For every student x in this class, x has studied calculus. Let C(x) denote x has studied calculus xC(x). b) For every person x, if person x is a student in this class, then x has studied calculus.
5

x(S(x) C(x))

2. Some student in this class has visited Mexico. a) There is a student in this class with the property that the student has visited Mexico. There is a student x in this class having the property that x has visited Mexico. Domain all student in this class Let M(x) x has visited Mexico xM(x) b) Domain all people other than those in this class There is a person x having the properties that x is a student in this class and x has visited Mexico. x( S(x) ^ M(x)) 3. Every student in this class has visited either Canada or Mexico. a) For every x in this class, x has the property that x has visited Mexico or x has visited Canada. C(x) V M(x)) x( b) If the domain for x consists of all people: For every person x, if x is a student in this class, then s has visited Mexico or x has visited Canada. S(x) (C(x) V M(x))) x( Sample Arguments All lions are fierce. Some lions do not drink coffee. Some fierce creatures do not drink coffee. The first two statements are called premises and the third is called conclusion. The entire set is called an argument. By setting: P(x) x is a lion Q(x) x is fierce R(x) x drink coffee We can set the statements as: x(P(x) Q(x)). x(P(x) ^ R(x)). x(Q(x) ^ R(x)).

All hummingbirds are richly colored. No large birds live on honey. Birds that do not live on honey are dull in color. Hummingbirds are small Let P(x) x is a hummingbird
6

Q(x)- x is large R(x) x lives on honey S(x) x is richly colored Solution: we can express the statements in the argument as: x (P(x)S(x)) x(Q(x) ^ R(x)) x(R(x) S(x)) x(P(x) Q(x))

Quiz #1 Name: ______________________________________ Rating:________ Date:_____________________

In exercises 1-7, restate each proposition in the form pq of a conditional proposition.

1. hard.
2.

Joey will pass the discrete mathematics exam if he studies Rosa may graduate if she has 160 quarter-hours of credit. A necessary condition for Fernando to buy a computer is that he obtain $2000. A sufficient condition for Katrina to take the algorithms course is that she pass discrete mathematics. When better cars are built, Buick will build them. The audience will go to sleep if the chairperson gives the lecture. The program is readable only if it is well structured. Write the converse of each proposition in exercises 1-2. Write the contrapositive of each proposition in exercises 34.

3. 4. 5. 6. 7. 8. 9.

II. Assuming that p and r are false and that q and s are true, find the truth value of each proposition in exercises 10-14.

10. 11. 12. 13. 14.

pq p q pq (p q) ( qr) (p q) r

III.

Represent the given statement symbolically by letting p: 4 < 2 q:7 < 10, r:6<6.

15. 16.

If 4 < 2, then 7 < 10. If ( 4 < 2 and 6 < 6), then 7 < 10.
8

17.

If it is not the case that (6 < 6 and 7 is not less than 10), then 6<6.

IV. In exercises 18-22, formulate the symbolic expression in words using p: q: r: Today is Monday. It is raining. It is hot.

18. 19. 20. 21.

pq q ( r ^ p ) p ( q V r ) (p V q )

For each pair of propositions P and Q in exercises 22 25, state whether or not PQ.
V.

22. 23. 24. 25.

P=p, Q=p V q P=pq, Q=p V q P=p (q V r), Q= (p V q) ( p V r ) P=(pq) (qr), Q=pr