Math 210, Concepts from Discrete Mathematics Worksheet 3 This is a handout. Complete all the proposed numbered exercises . You do not have to submit the examples. Section 1.4 part 2. • Logical equivalences involving quantifiers. Recall: ∗ predicates are statements involving a variable; ∗ the universal quantifier “for all” ∀; ∗ the existential quantifier “there exists” ∃. Definition: Two statements, S and T, involving predicates and quantifiers are logically equvalent (and we write S ≡ T) if and only if they have the same truth value no matter : ∗ which predicates are substituted into these statements; ∗ which domain of discourse is used for the variables in these predicates. The following example is a re-elaboration of Example 19 of your textbook. This example shows how to prove that two statements involving predicates are equivalent. Example. Prove the equivalence: ∀x (P(x) ∧ Q(x)) ≡ (∀x P(x)) ∧ (∀x Q(x)). In other words, we can distribute the ∀ symbol when two predicates are connected by a conjunction. Solution. In this case we are proving that two statements with predicates are equivalent. Even if it is helpful to think of some examples, no example will be enough to prove the statement. This is why we must use only formal logical language. We adopt an ”if and only if” kind of proof, that is to say, we deduce that the right side is true assuming the left one is true and vice-versa. So let us assume that ∀x (P(x) ∧ Q(x)) is true. This means that for any element a in the domain, the proposition P(a) ∧ Q(a) is true. In particular, we must have that P(a) is true for any element a in the domain. This implies that the quantified predicate ∀x P(x) is true. Similarly we get that the quantified predicate ∀x Q(x) is true. On the other hand, let us assume that (∀x P(x))∧(∀x Q(x)) is true. In particular, for any element a in the domain, P(a) is true and for any element b in the domain Q(b) is true. Notice that we used two different symbols a and b since now the “for all x” ∀x symbol is distributed between P(x) and Q(x). However, as your textbook mention, since both statements P(x) and Q(x) are true for every element in the domain, we can choose the same any element a and say that P(a) ∧ Q(a) is true. This implies ∀x (P(x) ∧ Q(x)). 1 Example. Show that the statement ∃x (P(x) ∧ Q(x)) is not equivalent to (∃x P(x)) ∧ (∃x Q(x)). Solution. We need to provide a counterexample. First we choose the domain: {1, 2}. Keep in mind that the simplest domain we can choose to make interesting counterexamples consists of two elements. we call them 1 and 2 but would have also have labeled them α and β. Moreover, we do not need to write complete statements for P(x) and Q(x), we just need to choose their truth values of 1 and 2. Let use choose: P(1) = T, P(2) = F; Q(1) = F, Q(2) = T. Now let us consider the statement ∃x (P(x) ∧ Q(x)). This is false since for both elements of the domain: P(1) ∧ Q(1) is false, since Q(1) is false; P(2) ∧ Q(2) is false, since P(2) is false. Therefore, there is no x in the domain for which ∃x (P(x) ∧ Q(x)) is true. On the other hand, the statement (∃x P(x)) ∧ (∃x Q(x)). is true . As a matter of fact, P(1) is true, therefore the statement ∃x P(x) is true. Also, Q(2) is true, therefore the statement ∃x Q(x) is true. In conclusion the statement (∃x P(x)) ∧ (∃x Q(x)) is true. This implies that the two statements cannot be equivalent since we have shown a case when their truth values are different. Exercise 1. Determine whether ∀x (P(x) → Q(x)) and (∀x P(x)) → (∀x Q(x)) are logically equivalent. Justify your answer. Exercise 2. Determine whether ∃x (P(x) ∨ Q(x)) and (∃x P(x)) ∨ (∃x Q(x)) are logically equivalent. Justify your answer. • Negating quantified expressions. I am now going to explain Table 2 Section 1.4 page 47 of the textbook. To negate a “for all x P(x)” expression it is enough to have at least one x for which P(x) is false, that is to say, ¬P(x) is true. In other words, the statement ¬∀x P(x) is equivalent to ∃x ¬P(x). To negate a “there exists x P(x)” expression we need that for all the x P(x) is false, that is to say, ¬P(x) is true. In other words, the statement ¬∃x P(x) is equivalent to ∀x ¬P(x). You can also think that the ¬ symbol can pass through the quantifiers, but it switches them. 2 Example. Let the domain of x be the students in this class. Let us translate the sentence All the students in this class are studying discrete mathematics. First of all we label the predicate: P(x) = x is studying discrete mathematics. In formal terms we have: ∀x P(x). Now if we want to negate the statement we have: ¬∀x P(x) ≡ ∃x ¬P(x). When translating back into english, we get: There is someone in this class who is not studying discrete mathematics. Exercise 3. 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) All dogs have fleas. (b) There is a horse that can add. (c) Every koala can climb. (d) No monkey can speak French. (e) There exists a pig that can swim and catch fish. Let us now see a more advanced example. Keep in mind that we are going to use the equivalences we have seen in Section 1.3. Example. Let the domain of p be the set of all printers at MSUM, while the domain of j is the set of print jobs. Let us translate the sentence: If there is a printer at MSUM that is out of service and busy, then there is a print job that is lost. Let us label the predicates: F(p) = p is out of order; B(p) = p is busy; L(j) = j is lost. The sentence translates as: (∃p (F(p) ∧ B(p))) → (∃j L(j)) Let us now negate the formal logical expression: ¬ [(∃p (F(p) ∧ B(p))) → (∃j L(j))] ≡ ¬ [¬ (∃p (F(p) ∧ B(p))) ∨ (∃j L(j))] ≡ (∃p (F(p) ∧ B(p))) ∧ (∀j ¬L(j)) 3 When translating back into english, we get: There is a printer at MSUM that is out of order and busy, but no print job is lost. Exercise 4. Translate the given statement into symbolic form. Be sure to define all predicates used. Use the variable a with domain D = {a : a is an animal } as your main variable. Then, negate the symbolic statement. Finally, rewrite the negated statement clearly in plain English. “Every animal that makes a good pet is fluffy and has a tail.” Section 1.5 • Statements involving nested quantifiers. Predicates can have multiple variables. In this case, in order to get a proposition, we need to define the domain for each variable and apply multiple quantifiers. When using quantifiers on more than one variable, we call them nested quantifiers. Example. Let us start with examples from algebra. Consider the following sentence: For every integer n there exists an integer m such that the sum of n and m is 100. In this case we already have the the variables n and m, we just need to state that the domain for both variables is the set of integers. We can now translate the sentence in formal logical terms: ∀n∃m (n + m = 100). We could also have defined a predicate by labeling P(n, m) = n + m = 100. However, when mathematical expressions are precise enough they can be directly written into the logical form. Notice that the statement is true. As a matter of fact, for every integer n we can choose m to be equal to 100 − n. IMPORTANT! The order of the the quantifiers matters! Let us see what happens when we reverse the order of the quantifiers in the previous example: ∃m∀n (n + m = 100). In words this becomes: There exists an integer m such that for every integer n we have that the sum of n and m is 100. This statement is false. As a matter of fact, whenever we choose m, there is a unique n such that n + m = 100 and we cannot have n + m = 100 for every integer n. Exercise 5. Assume that the domain for each variable consists of all real numbers. Translate each of the following statements into English (you can use the variables x and y as long as you do not use any other mathematical, logical symbols). Then state whether the statement is true or false. If it is false, provide a counterexample. 4 (a) ∀x ∃y (x < y) (b) ∀x ∃y (y 2 < x) • Translating from nested quantifiers into English. Example. Let Q(x, y) mean that student x has visited website y, where the domain for x consists of all students at MSUM and the domain for y consists of all websites. Let us express each of the following logical expressions by a simple English sentence. (a) W(Sarah Smith, www.att.com) Sarah Smith has visited www.att.com. (b) ∃x∀y W(x, y) There is a student who has visited all the websites. (c) ∀x∃y W(x, y) Every student has visited at least one website. (d) ∃x1∃x2∀y ((x1 6= x2) ∧ (W(x1, y) ↔ W(x2, y))) There are two different students who have visited the same websites. Exercise 6. Let P(x, y) be the statement “Student x has taken class y,” where the domain for x consists of all students in your class and for y consists of all computer science courses at MSUM. Express each of these quantifications in English. (a) ∃x ∃y P(x, y) (b) ∀x ∃y P(x, y) (c) ∀y ∃x P(x, y) (d) ∃x ∀y P(x, y) (e) ∀x ∀y P(x, y) • Translating English sentences into logical expressions. Example. Let F(x, y) be the statement “x can fool y where the domain for both variables x and y consists of all people in the world. Let us translate the following English sentences into formal logical expressions. (a) Everybody can fool Fred. ∀x F(x, Fred) (b) Evelyn can fool everybody. ∀y F(Evelyn, y) (c) Everybody can fool somebody. ∀x∃y F(x, y) (d) There is no one who can fool everybody. ¬∃x∀y F(x, y) (alternatively ∀x¬∀y F(x, y) or ∀x∃y ¬F(x, y)) 5 Exercise 7. 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) Somebody loves everybody. (d) Nobody loves everybody. (e) There is somebody whom nobody loves. • Negating nested quantifiers. If you understood that the ¬ symbol can pass through the quantifiers, but it switches them, then it should not be too difficult to see how to negate nested quantifiers. If this is still confusing, please ask questions to the forum. Example. Express the negation of each of the following statements so that all negation symbols immediately precede predicates. (a) ∃z∀y∀xT(x, y, z) Solution. ¬ [∃z∀y∀xT(x, y, z)] ≡ ∀z∃y∃x¬T(x, y, z) (b) (∃x∃y P(x, y)) ∧ (∀x∀y Q(x, y)) Solution. In this example we are using equivalence rules seen in Section 1.3. For clarity’s sake we set up a two column proof. Also I am calling Negation of Quantifiers what the textbook calls De Morgan’s Laws for Quantifiers. ¬ [(∃x∃y P(x, y)) ∧ (∀x∀y Q(x, y))] ≡ ¬ [∃x∃y P(x, y)] ∨ ¬ [∀x∀y Q(x, y)] De Morgan’s law ≡ (∀x∀y ¬P(x, y)) ∨ (∃x∃y Q(x, y)) Neg. of Quant. (c) ∃x∃y (Q(x, y) → Q(y, x)) Solution. In this example we are using equivalence rules seen in Section 1.3. For clarity’s sake we set up a two column proof. Also I am calling Negation of Quantifiers what the textbook calls De Morgan’s Laws for Quantifiers. ¬ [∃x∃y (Q(x, y) → Q(y, x))] ≡ ¬ [∃x∃y (¬Q(x, y) ∨ Q(y, x))] Conditional to Disjunction ≡ ∀x∀y ¬ [¬Q(x, y) ∨ Q(y, x)] Negation of Quantifiers ≡ ∀x∀y (Q(x, y) ∧ ¬Q(y, x)) De Morgan’s Law Exercise 8. Write the negation of the following symbolic statements. Your answers should be written in fully simplified form (i.e. so that no negation is outside a quantifier and any negation symbols should only modify a single variable or predicate). Note: no need to justify each step. ∃y∀x [¬S(x, y) → T(x, y)] ∃x∀y [R(x, y) → (S(x, y) ∨ T(x, y))]