# Discrete Mathematics Discrete Mathematics Lecture # 21 Predicates & Quantifiers Introduction Propositional logic, cannot adequately express the meaning of all statements in mathematics and in natural language Example

For example, suppose that we know that Every computer connected to the university network is functioning properly. No rules of propositional logic allow us to conclude the truth of the statement MATH3 is functioning properly,

Predicates Statements involving variables, such as x > 3, x = y + 3, x + y = z, and computer x is under attack by an intruder, and computer x is functioning properly, These statements are neither true nor false when the values of the variables are not

specified. Predicate The statement x is greater than 3 has two parts. The first part, the variable x, is the subject of the statement. The second partthe predicate, is greater than 3refers to a property that the subject of the statement can have.

Predicate We can denote the statement x is greater than 3 by P(x) where P denotes the predicate is greater than 3 and x is the variable. The statement P(x) is also 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. Examples 1. Let P(x) denote the statement x > 3. What are the truth values of P(4) and P(2)? 2.

Let A(x) denote the statement Computer x is under attack by an intruder. Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)? Predicates We can also have statements that involve more than one variable. For instance, consider the statement x = y + 3.

We can denote this statement by Q(x, y), where x and y are variables and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value. Examples 1.

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)? 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 network CAMPUS2, but not to network CAMPUS1. What are the values of A(MATH1, CAMPUS1) and

A(MATH1, CAMPUS2)? Examples 3. 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)? N-place Predicate 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 an n-place predicate or a nary predicate. PRECONDITIONS AND POSTCONDITIONS Predicates are also used to establish the correctness of computer programs, that is,

to show that computer programs always produce the desired output when given valid input. The statements that describe valid input are known as preconditions and the conditions that the output should satisfy when the program has run are known as postconditions. Example Consider the following program, designed to

interchange the values of two variables x and y. temp := x x := y y := temp Find predicates that we can use as the precondition and the post-condition to verify the correctness of this program. Then explain how to use them to verify that for all valid input the program does what is intended. Quantifiers

When the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value. There is another important way, called quantification, to create a proposition from a propositional function.

Quantification expresses the extent to which a predicate is true over a range of elements. Quantifiers The words all, some, many, none, and few are used in quantifications. We will focus on two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration. existential quantification, which tells us that

there is one or more element under consideration for which the predicate is true. The area of logic that deals with predicates and quantifiers is called the predicate calculus. THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain.

The universal quantification of P(x) for a particular domain is the proposition that asserts that P(x) is true for all values of x in this domain. THE UNIVERSAL QUANTIFIER Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification of P(x) changes

when we change the domain. The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined. Universal Quantification 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 xP(x) or for every xP(x). An element for which P(x) is false is called a counterexample of xP(x). Quantifiers Example Let

P(x) be the statement x + 1 > x. What is the truth value of the quantification xP(x), where the domain consists of all real numbers? Remark Generally, an implicit assumption is made that all domains of discourse for quantifiers are non-empty. Note

that if the domain is empty, then xP(x) is true for any propositional function P(x) because there are no elements x in the domain for which P(x) is false. Remark Besides for all and for every, universal quantification can be expressed in many other ways, including all of, for each, given any, for arbitrary, for each, and for any. Example

Let Q(x) be the statement x < 2. What is the truth value of the quantification xQ(x), where the domain consists of all real numbers? Suppose that P(x) is x2 > 0. Show that the statement xP(x) is false where the universe of discourse consists of all integers, we give a counterexample.

Universal Quantifier When all the elements in the domain can be listedsay, x1, x2, . . ., xnit follows that the universal quantification xP(x) is the same as the conjunction P(x1) P(x2) P(xn), because this conjunction is true if and only if P(x1), P(x2), . . . , P (xn) are all true.

Example What is the truth value of xP(x), where P(x) is the statement x2 < 10 and the domain consists of the positive integers not exceeding 4? What does the statement xN(x) mean if N(x) is Computer x is connected to the network and the domain consists of all computers on campus?

Example What is the truth value of x(x2 x) if the domain consists of all real numbers? What is the truth value of this statement if the domain consists of all integers? THE EXISTENTIAL QUANTIFIER Many mathematical statements assert that there is an element with a certain property.

Such statements are expressed using existential quantification. With existential quantification, we form a proposition that is true if and only if P(x) is true for at least one value of x in the domain. Existential Quantification 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. THE EXISTENTIAL QUANTIFIER Besides the phrase there exists, we can also

express existential quantification in many other ways, such as by using the words for some, for at least one, or there is. The existential quantification xP(x) is read as There is an x such that P(x), There is at least one x such that P(x), or For some xP(x). Example Let

P(x) denote the statement x > 3. What is the truth value of the quantification xP(x), where the domain consists of all real numbers? Let Q(x) denote the statement x = x + 1. What is the truth value of the quantification xQ(x), where the domain consists of all real numbers? Remark Generally,

an implicit assumption is made that all domains of discourse for quantifiers are nonempty. If the domain is empty, then xQ(x) is false whenever Q(x) is a propositional function because when the domain is empty, there can be no element x in the domain for which Q(x) is true. THE EXISTENTIAL QUANTIFIER

When all elements in the domain can be listedsay, x1, x2, . . . , xnthe existential quantification xP(x) is the same as the disjunction P(x1) P(x2) P(xn), because this disjunction is true if and only if at least one of P(x1), P(x2), . . . , P (xn) is true.

Example What is the truth value of xP(x), where P(x) is the statement x2 > 10 and the universe of discourse consists of the positive integers not exceeding 4? THE UNIQUENESS QUANTIFIER there is no limitation on the number of different quantifiers we can define, such as there are exactly two, there are no more

than three, there are at least 100, and so on. Of these other quantifiers, the one that is most often seen is the uniqueness quantifier, denoted by ! or 1. The notation !xP(x) [or 1xP(x)] states There exists a unique x such that P(x) is true. THE UNIQUENESS QUANTIFIER For instance, !x(x 1 = 0), where the domain is the set of real numbers, states that there is a

unique real number x such that x 1 = 0. This is a true statement, as x = 1 is the unique real number such that x 1 = 0. Observe that we can use quantifiers and propositional logic to express uniqueness, so the uniqueness quantifier can be avoided. Generally, it is best to stick with existential and universal quantifiers so that rules of inference for these quantifiers can be used. Quantifiers with Restricted Domains An

abbreviated notation is often used to restrict the domain of a quantifier. In this notation, a condition a variable must satisfy is included after the quantifier. Example What do the statements x < 0 (x2 > 0), y 0 (y3 0), and z > 0 (z2 = 2) mean, where the domain in each case consists of the real

numbers? Observations Note that the restriction of a universal quantification is the same as the universal quantification of a conditional statement. For instance, x < 0 (x2 > 0) is another way of expressing x(x < 0 x2 > 0). On the other hand, the restriction of an existential quantification is the same as the existential quantification of a conjunction. For instance, z > 0 (z2 = 2) is another way

of expressing z(z > 0 z2 = 2). Precedence of Quantifiers The quantifiers and have higher precedence than all logical operators from propositional calculus. For example, xP(x) Q(x) is the disjunction of xP(x) and Q(x).

In other words, it means (xP(x)) Q(x) rather than x(P(x) Q(x)). Binding Variables 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.

All the variables that occur in a propositional function must be bound or set equal to a particular value to turn it into a proposition. Binding Variables This can be done using a combination of universal quantifiers, existential quantifiers, and value assignments. The part of a logical expression to which a quantifier is applied is called the scope of this quantifier.

Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specify this variable. Example In the statement x(x + y = 1), the variable x is bound by the existential quantification x, but the variable y is free because it is not bound by a quantifier and no value is assigned to this variable. This illustrates that in the statement x(x + y = 1), x is bound, but y is free.

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 S T to indicate that

two statements S and T involving predicates and quantifiers are logically equivalent. Example Show that x(P(x) Q(x)) and xP(x) xQ(x) are logically equivalent (where the same domain is used throughout). This logical equivalence shows that we can distribute a universal quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over a disjunction. However, we cannot distribute

a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction. Solution To show that these statements are logically equivalent, we must show that they always take the same truth value, no matter what the predicates P and Q are, and no matter which domain of discourse is used. Suppose we have particular predicates P and Q, with a common domain.

We can show that x(P(x) Q(x)) and xP(x) xQ(x) are logically equivalent by doing two things. First, we show that if x(P(x) Q(x)) is true, then xP(x) xQ(x) is true. Second, we show that if xP(x) xQ(x) is true, then x(P(x) Q(x)) is true. Solution So, suppose that x(P(x) Q(x)) is true. This means that if a is in the domain, then P(a) Q(a) is true. Hence, P(a) is true and Q(a) is true. Because P(a) is true and Q(a) is true for every

element in the domain, we can conclude that xP(x) and xQ(x) are both true. This means that xP(x) xQ(x) is true. Next, suppose that xP(x) xQ(x) is true. It follows that xP(x) is true and xQ(x) is true. Hence, if a is in the domain, then P(a) is true and Q(a) is true [because P(x) and Q(x) are both true for all elements in the domain, there is no conflict using the same value of a here]. Solution It follows that for all a, P(a) Q(a) is true. It

follows that x(P(x) Q(x)) is true. We can now conclude that x(P(x) Q(x)) xP(x) xQ(x). Negating Quantified Expressions Consider the negation of the statement Every student in your class has taken a course in calculus. This statement is a universal quantification, namely, xP(x), Its negation is equivalent to There is a student in your class who has not

taken a course in calculus. Namely x P(x). xP(x) x P(x). Negating Quantified Expressions consider the proposition There is a student in this class who has taken a course in calculus. This is the existential quantification xQ(x), where Q(x) is the statement x has taken a course in calculus. This is equivalent to Every student in this

class has not taken calculus, phrased in the language of quantifiers, x Q(x). xQ(x) x Q(x). Negating Quantified Expressions The rules for negations for quantifiers are called De Morgans laws for quantifiers. De Morgans laws for quantifiers. Why these rules are called De Morgans laws for quantifiers?

When the domain has n elements x1, x2, . . . , xn, it follows that xP(x) is the same as (P (x1) P(x2) P(xn)), which is equivalent to P(x1) P(x2) P(xn) by De Morgans laws, and this is the same as x P(x). Similarly, xP(x) is the same as (P (x1) P(x2) P(xn)), which by De Morgans laws is equivalent to P(x1) P(x2) P(xn), and this is the same as x P(x). Example What

are the negations of the statements There is an honest politician and All Americans eat cheeseburgers? What are the negations of the statements x(x2 > x) and x(x2 = 2)? that x(P(x) Q(x)) and x(P(x) Q(x)) are logically equivalent. Show

Translating from English into Logical Expressions Translating from English to logical expressions becomes even more complex when quantifiers are needed. Furthermore, there can be many ways to translate a particular sentence. (As a consequence, there is no cookbook approach that can be followed step by step.)

Example Express the statement Every student in this class has studied calculus using predicates and quantifiers. Solution: First, we rewrite the statement so that we can clearly identify the appropriate quantifiers to use. Doing so, we obtain: For every student in this class, that student has studied calculus.

Solution Next, we introduce a variable x so that our statement becomes For every student x in this class, x has studied calculus. Continuing, we introduce C(x), which is the statement x has studied calculus. Consequently, if the domain for x consists of the students in the class, we can translate our statement as xC(x).

Solution (2) However, there are other correct approaches; different domains of discourse and other predicates can be used. The approach we select depends on the subsequent reasoning we want to carry out. For example, we may be interested in a wider group of people than only those in this class. If we change the domain to consist of all people, we will need to express our statement as For every person x, if person x is a student in this class then x has studied calculus.

Solution (2) If S(x) represents the statement that person x is in this class, we see that our statement can be expressed as x(S(x) C(x)). Example Express the statements Some student in this class has visited Mexico and Every student in this class has visited either Canada or Mexico using predicates and quantifiers.

Solution: The statement Some student in this class has visited Mexico means that There is a student in this class with the property that the student has visited Mexico. Solution We can introduce a variable x, so that our statement becomes There is a student x in this class having the

property that x has visited Mexico. We introduce M(x), which is the statement x has visited Mexico. If the domain for x consists of the students in this class, we can translate this first statement as xM(x). Solution (2) However, if we are interested in people other than those in this class, we look at the statement a little differently. Our statement can be expressed as

There is a person x having the properties that x is a student in this class and x has visited Mexico. In this case, the domain for the variable x consists of all people. We introduce S(x) to represent x is a student in this class. Our solution becomes x(S(x) M(x)) Example Use predicates and quantifiers to express the system specifications Every mail message larger than one megabyte will be compressed Solution Let S(m, y) be Mail message m is larger than y

megabytes, where the variable m has the domain of all mail messages and the variable y is a positive real number, and let C(m) denote Mail message m will be compressed. Then the specification Every mail message larger than one megabyte will be compressed can be represented as m(S(m, 1) C(m)). Example Use predicates and quantifiers to express the system specifications If a user is active, at least one network link will be available. Solution:

Let A(u) represent User u is active, where the variable u has the domain of all users, let S(n, x) denote Network link n is in state x, where n has the domain of all network links and x has the domain of all possible states for a network link. Then the specification If a user is active, at least one network link will be available can be represented by uA(u) nS(n, available). Example Consider these statements. The first two are

called premises and the third is called the conclusion. The entire set is called an argument. All lions are fierce. Some lions do not drink coffee. Some fierce creatures do not drink coffee. Solution Let P(x), Q(x), and R(x) be the statements x is a lion, x is fierce, and x drinks coffee, respectively. Assuming that the domain consists of all creatures, express the statements in the argument using quantifiers and P(x), Q(x),

and R(x). We can express these statements as: x(P(x) Q(x)). x(P(x) R(x)). x(Q(x) R(x)). Example Consider these statements, of which the first three are premises and the fourth is a valid conclusion. 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. Solution Let P(x), Q(x), R(x), and S(x) be the statements x is a hummingbird, x is large, x lives on honey, and x is richly colored, respectively. Assuming that the domain consists of all birds, express the statements in the argument using quantifiers and P(x), Q(x), R(x), and S(x).

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)). Exercise Let P(x) denote the statement x 4. What are these truth values? a) P(0) b) P(4) c) P(6) Let P(x) be the statement x spends more than five hours every weekday in class,

where the domain for x consists of all students. Express each of these quantifications in English. a) xP(x) b) xP(x) c) x P(x) d) x P(x) Exercise Translate these statements into English, where C(x) is x is a comedian and F(x) is x is funny and the domain consists of all people. a) x(C(x) F(x)) b) x(C(x) F(x)) c) x(C(x) F(x)) d) x(C(x) F(x))

Let P(x) be the statement x can speak Russian and let Q(x) be the statement x knows the computer language C++. Express each of these sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school. Exercise a) There is a student at your school who can speak Russian and who knows C++.

b) There is a student at your school who can speak Russian but who doesnt know C++. c) Every student at your school either can speak Russian or knows C++. d) No student at your school can speak Russian or knows C++. Let P(x) be the statement x = x2. If the domain consists of the integers, what are these truth values? a) P(0) b) P(1) c) P(2) d) P(1) e) xP(x) f ) xP(x)

Exercise Determine the truth value of each of these statements if the domain consists of all integers. a) n(n + 1 > n) b) n(2n = 3n) c) n(n = n) d) n(3n 4n) Determine the truth value of each of these statements if the domain for all variables consists of all integers.

a) n(n2 0) b) n(n2 = 2) c) n(n2 n) d) n(n2 < 0) Exercise Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2, 3, and 4. Write out each of these propositions using disjunctions, conjunctions, and negations. a) xP(x) b) xP(x) c) x P(x)

d) x P(x) e) xP(x) f) xP(x) Exercise Suppose that the domain of the propositional function P(x) consists of the integers 1, 2, 3, 4, and 5. Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions.

a) xP(x) b) xP(x) c) xP(x) d) xP(x) e) x((x 3) P(x)) x P(x) Exercise Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people. a) Someone in your class can speak Hindi. b) Everyone in your class is friendly.

c) There is a person in your class who was not born in California. d) A student in your class has been in a movie. e) No student in your class has taken a course in logic programming. Exercise Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives. a) No one is perfect.

b) Not everyone is perfect. c) All your friends are perfect. d) At least one of your friends is perfect. e) Everyone is your friend and is perfect. f ) Not everybody is your friend or someone is not perfect. Exercise Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase It is not the case that.)

a) Some old dogs can learn new tricks. b) No rabbit knows calculus. c) Every bird can fly. d) There is no dog that can talk. e) There is no one in this class who knows French and Russian. Exercise Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all

integers. a) x(x2 x) b) x(x > 0 x < 0) c) x(x = 1) Nested Quantifiers One quantifier is within the scope of another, such as xy(x + y = 0). Note that everything within the scope of a quantifier can be thought of as a propositional function. For example,

xy(x + y = 0) is the same thing as xQ(x), where Q(x) is yP(x, y), where P(x, y) is x + y = 0. Example Assume that the domain for the variables x and y consists of all real numbers. The statement xy(x + y = y + x) says

that x + y = y + x for all real numbers x and y. This is the commutative law for addition of real numbers. Example The statement xy(x + y = 0)

says that for every real number x there is a real number y such that x + y = 0. This states that every real number has an additive inverse. Example Translate into English the statement xy((x > 0) (y < 0) (xy < 0)), where the domain for both variables consists of all real numbers.

Solution This statement says that for every real number x and for every real number y, if x > 0 and y < 0, then xy < 0. That is, this statement says that for real numbers x and y, if x is positive and y is negative, then xy is negative. This can be stated more succinctly as The product of a positive real number and a negative real number is always a negative real number.

QUANTIFICATION AS LOOPS Quantifications of more than one variable, it is sometimes helpful to think in terms of nested loops. To see whether xyP(x, y) is true, we loop through the values for x, and for each x we loop through the values for y. If we find that P(x, y) is true for all values for x and y, we have determined that xyP(x, y) is true. If we ever hit a value x for which we hit a value

y for which P(x, y) is false, we have shown that xyP(x, y) is false. QUANTIFICATION AS LOOPS Similarly, to determine whether xyP(x, y) is true, we loop through the values for x. For each x we loop through the values for y until we find a y for which P(x, y) is true.

If for every x we hit such a y, then xyP(x, y) is true; if for some x we never hit such a y, then xyP(x, y) is false. QUANTIFICATION AS LOOPS To see whether xyP(x, y) is true, we loop through the values for x until we find an x for which P(x, y) is always true when we loop through all values for y.

Once we find such an x, we know that xyP(x, y) is true. If we never hit such an x, then we know that xyP(x, y) is false. QUANTIFICATION AS LOOPS Finally, to see whether xyP(x, y) is true,

we loop through the values for x, where for each x we loop through the values for y until we hit an x for which we hit a y for which P(x, y) is true. The statement xyP(x, y) is false only if we never hit an x for which we hit a y such that P(x, y) is true. The Order of Quantifiers Many

mathematical statements involve multiple quantifications of propositional functions involving more than one variable. It is important to note that the order of the quantifiers is important, unless all the quantifiers are universal quantifiers or all are existential quantifiers. Example Let

P(x, y) be the statement x + y = y + x. What are the truth values of the quantifications xyP(x, y) and yxP(x, y) where the domain for all variables consists of all real numbers? Solution The quantification

xyP(x, y) denotes the proposition For all real numbers x, for all real numbers y, x + y = y + x. Because P(x, y) is true for all real numbers x and y, the proposition xyP(x, y) is true. Note that the statement yxP(x, y) says For all real numbers y, for all real numbers x, x + y = y + x. Solution This has the same meaning as the

statement For all real numbers x, for all real numbers y, x + y = y + x. That is, xyP(x, y) and yxP(x, y) have the same meaning, and both are true. This illustrates the principle that the order of nested universal quantifiers in a statement without other quantifiers can be changed without changing the meaning of the quantified statement. Example

Let Q(x, y) denote x + y = 0. What are the truth values of the quantifications yxQ(x, y) and xyQ(x, y), where the domain for all variables consists of all real numbers? Solution The

quantification yxQ(x, y) denotes the proposition There is a real number y such that for every real number x, Q(x, y). No matter what value of y is chosen, there is only one value of x for which x + y = 0. Because there is no real number y such that x + y = 0 for all real numbers x, the statement yxQ(x, y) is false. Solution The

quantification xyQ(x, y) denotes the proposition For every real number x there is a real number y such that Q(x, y). Given a real number x, there is a real number y such that x + y = 0; namely, y = x. Hence, the statement xyQ(x, y) is true. Remarks The statements

yxP(x, y) and xyP(x, y) are not logically equivalent. The statement yxP(x, y) is true if and only if there is a y that makes P(x, y) true for every x. So, for this statement to be true, there must be a particular value of y for which P(x, y) is true regardless of the choice of x. Remarks On

the other hand, xyP(x, y) is true if and only if for every value of x there is a value of y for which P(x, y) is true. So, for this statement to be true, no matter which x you choose, there must be a value of y (possibly depending on the x you choose) for which P(x, y) is true. In other words, in the second case, y can depend on x, whereas in the first case, y is a constant independent of x. Remarks From

these observations, it follows that if yxP(x, y) is true, then xyP(x, y) must also be true. However, if xyP(x, y) is true, it is not necessary for yxP(x, y) to be true. Example Quantification of Two Variables Example

Let Q(x, y, z) be the statement x + y = z. What are the truth values of the statements xyzQ(x, y, z) and zxyQ(x, y, z), where the domain of all variables consists of all real numbers? Solution Suppose that x and y are assigned values. Then, there exists a real number z such that x + y = z.

Consequently, the quantification xyz Q(x, y, z), which is the statement For all real numbers x and for all real numbers y there is a real number z such that x + y = z, is true. Solution The order of the quantification here is important, because the quantification zxyQ(x, y, z), which is the statement There is a real number z such that for all real numbers x and for all real numbers y it is

true that x + y = z, is false, because there is no value of z that satisfies the equation x + y = z for all values of x and y. Translating Mathematical Statements into Statements Involving Nested Quantifiers Example Translate

the statement The sum of two positive integers is always positive into a logical expression. Solution To translate this statement into a logical expression, we first rewrite it so that the implied quantifiers and a domain are shown: For every two integers, if these integers are both positive, then the sum of these integers is positive.

Next, we introduce the variables x and y to obtain For all positive integers x and y, x + y is positive. Consequently, we can express this statement as xy((x > 0) (y > 0) (x +y > 0)), where the domain for both variables consists of all integers. Solution Note that we could also translate this using the positive integers as the domain.

Then the statement The sum of two positive integers is always positive becomes For every two positive integers, the sum of these integers is positive. We can express this as xy(x +y > 0), where the domain for both variables consists of all positive integers. Example Translate the statement Every real number except zero has a multiplicative inverse. (A

multiplicative inverse of a real number x is a real number y such that xy = 1.) Solution We first rewrite this as For every real number x except zero, x has a multiplicative inverse. We can rewrite this as For every real number x, if x 0, then there exists a real number y such that xy = 1. This

can be rewritten as x((x 0) y(xy = 1)). Translating from Nested Quantifiers into English Example Translate x(C(x) into the statement y(C(y) F(x, y)))

English, where C(x) is x has a computer, F(x, y) is x and y are friends, and the domain for both x and y consists of all students in your school. Solution The statement says that for every student x in your school, x has a computer or there is a student y such that y has a computer and x and y are friends.

In other words, every student in your school has a computer or has a friend who has a computer. Example Translate the statement xyz((F into

(x, y) F(x, z) (y z)) F(y,z)) English, where F(a,b) means a and b are friends and the domain for x, y, and z consists of all students in your school. Solution We first examine the expression (F (x, y) F(x, z) (y z)) F(y, z). This expression says that if students x and y are friends, and students x and z are friends, and

furthermore, if y and z are not the same student, then y and z are not friends. It follows that the original statement, which is triply quantified, says that there is a student x such that for all students y and all students z other than y, if x and y are friends and x and z are friends, then y and z are not friends. In other words, there is a student none of whose friends are also friends with each other. Translating English Sentences into Logical Expressions Example

Express the statement If a person is female and is a parent, then this person is someones mother as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives.

Solution The statement If a person is female and is a parent, then this person is someones mother can be expressed as For every person x, if person x is female and person x is a parent, then there exists a person y such that person x is the mother of person y. We introduce the propositional functions F(x) to represent x is female, P(x) to represent x is a parent, and M(x, y) to represent x is the mother of y. The original statement can be

represented as x((F (x) P(x)) yM(x, y)). And further as xy((F (x) P(x)) M(x, y)). Example Express the statement Everyone as has exactly one best friend

a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives. Solution The statement Everyone has exactly one best friend can be expressed as For every person x, person x has exactly one best friend.

Introducing the universal quantifier, we see that this statement is the same as x(person x has exactly one best friend), where the domain consists of all people. Solution To

say that x has exactly one best friend means that there is a person y who is the best friend of x, and furthermore, that for every person z, if person z is not person y, then z is not the best friend of x. When we introduce the predicate B(x, y) to be the statement y is the best friend of x, the statement that x has exactly one best friend can be represented as y(B(x, y) z((z y) B(x, z))). Consequently, our original statement can be expressed as xy(B(x, y) z((z y) B(x, z))).

Example Use quantifiers to express the statement There is a woman who has taken a flight on every airline in the world. Solution Let P(w, f ) be w has taken f and Q(f, a) be f is a flight on a. We can express the statement as

waf (P(w, f ) Q(f, a)), where the domains of discourse for w, f , and a consist of all the women in the world, all airplane flights, and all airlines, respectively. The statement could also be expressed as wafR(w, f, a), where R(w, f, a) is w has taken f on a. Exercise Translate

these statements into English, where the domain for each variable consists of all real numbers. a) xy(x < y) b) xy(((x 0) (y 0)) (xy 0)) c) xyz(xy = z) Exercise Let Q(x, y) be the statement x has sent an e-mail message to y, where the domain for both x and y consists of all students in your class.

Express each of these quantifications in English. a) xyQ(x, y) b) xyQ(x, y) c) xyQ(x, y) d) yxQ(x, y) e) yxQ(x, y) f ) xyQ(x, y) Exercise Let L(x, y) be the statement x loves y, where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statements. a) Everybody loves Jerry.

b) Everybody loves somebody. c) There is somebody whom everybody loves. d) Nobody loves everybody. e) There is somebody whom Lydia does not love. f ) There is somebody whom no one loves. g) There is exactly one person whom everybody loves. h) There are exactly two people whom Lynn loves. i) Everyone loves himself or herself. j) There is someone who loves no one besides himself or herself. Exercise Let

S(x) be the predicate x is a student, F(x) the predicate x is a faculty member, and A(x, y) the predicate x has asked y a question, where the domain consists of all people associated with your school. Use quantifiers to express each of these statements. a) Lois has asked Professor Michaels a question. b) Every student has asked Professor Gross a question. c) Every faculty member has either asked Professor Miller a question or been asked a question by Professor Miller. d) Some student has not asked any faculty member a question. e) There is a faculty member who has never been asked a question by a student. f ) Some student has asked every faculty member a question. g) There is a faculty member who has asked every other faculty member a question.

h) Some student has never been asked a question by a faculty member. Exercise Let M(x, y) be x has sent y an e-mail message and T (x, y) be x has telephoned y, where the domain consists of all students in your class. Use quantifiers to express each of these statements. (Assume that all e-mail messages that were sent are received, which is not the way things often work.) a) Chou has never sent an e-mail message to Koko. b) Arlene has never sent an e-mail message to or telephoned Sarah. c) Jos has never received an e-mail message from Deborah. d) Every student in your class has sent an e-mail message to

Ken. e) No one in your class has telephoned Nina. f ) Everyone in your class has either telephoned Avi or sent him an e-mail message. Exercise g) There is a student in your class who has sent everyone else in your class an e-mail message. h) There is someone in your class who has either sent an e-mail message or telephoned everyone else in your class. i) There are two different students in your class who have sent each other

e-mail messages. j) There is a student who has sent himself or herself an e-mail message. k) There is a student in your class who has not received an e-mail message from anyone else in the class and who has not been called by any other student in the class. l) Every student in the class has either received an email message or received a telephone call from another student in the class. m) There are at least two students in your class such that one student has sent the other e-mail and the second student has telephoned the first student. n) There are two different students in your class who between them have sent an e-mail message to or telephoned everyone else in the class.