Discrete Mathematics - Lecture 1.5 Nested Quantifiers PDF

Preview

Summary

Discrete Mathematics - Lecture 1.5 Nested Quantifiers...

Description

Math 3336 Section 1.5 Nested Quantifiers Nested quantifiers • Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics. ), where the

Example: “Every real number has an additive inverse” is domains of ฀฀ and ฀฀ are the real numbers. Example: Translate into English the statement ∀฀฀∀฀฀((฀ ฀ < 0) ∧ (฀ ฀ < 0) → (฀฀฀฀ > 0)) where the domains of ฀฀ and ฀฀ are the real numbers. Order of quantifiers Examples: 1. Let ฀฀(฀฀, ฀฀) be the statement “฀฀ numbers. Determine the truth

฀฀

฀฀

฀฀

฀฀

eal ).

2. Let ฀฀(฀฀, ฀฀) be the statement “ ” Assume that ฀฀ is the real numbers. Determine the truth value of ∀฀฀∃฀฀฀฀ (฀฀, ฀฀) and ∃฀฀∀฀฀฀฀(฀฀, ฀฀).

Example: Let U be the real numbers. Define P(x,y) : x · y = 0 What is the truth value of the following? 1. ∀x∀yP(x,y)

3. ∃x∀y P(x,y)

Example: Let U be the real numbers. Defin What is the truth value of the following? 1. ∀x∀yP(x,y) 2. ∀x∃yP(x,y) Study Table 1 on page 60 from 1.5! Page 1 of 4

Translating Mathematical Statements into Statements with Nested Quantifiers Example: Express the following statement using mathematical and logical operators, predicates, and quantifiers. The domain consists of . 1. The sum of two negative integers is negative.

2. The difference of two positive integers is not necessarily positive.

Translating Nested Quantifiers into English Example: Translate the statement ∀x (C(x ) ∨ ∃y (C(y ) ∧ F(x, y))) where x and y consists of all students in your school.

s,” and the domain for both

Example: Translate the statement ∃x ∀ y ∀z ((F(x, y) ∧ F(x,z) ∧ (y ≠z))→¬F(y,z))

Page 2 of 4

Negating Nested Quantifiers •

Use De Morgan’s Laws to mov

.

Example: Express the negation of the quantifier.

ation precedes a

Page 3 of 4

More Practice with Nested Quantifiers Suppose the variable ฀฀ represents students, ฀฀ represents courses, and ฀฀(฀฀, ฀฀) means “ ฀฀”. Match each sentence to logical statements. 6. 1. Every course is being taken by at least one student. 7. 2. Some student is taking every course 8. 3. No student is taking all courses. 4. There is a course that all students are 9. taking. 5. Every student is taking at least one 10. No student is taking any cour course. (A) ∃฀฀∀฀฀ ฀฀(฀฀, ฀฀) (B) ∃฀฀∀฀฀ ฀฀(฀฀, ฀฀) (C) ∀฀฀∃฀฀ ฀฀(฀฀, ฀฀) (D) ¬∃฀฀∃฀฀ ฀฀(฀฀, ฀฀)

(E) ∃฀฀∀฀฀ ¬฀฀(฀฀, ฀฀) (F) ∀฀฀∃฀฀ ฀฀(฀฀, ฀฀) (G) ∃฀฀∀฀฀ ¬฀฀(฀฀, ฀฀) (H) ¬∀฀฀∃฀฀ ฀฀(฀฀, ฀฀)

Page 4 of 4

(I) ¬∃฀฀∀฀฀ ฀฀(฀฀, ฀฀) (J) ¬∀฀฀∃฀฀ ¬฀฀(฀฀, ฀฀) (K) ¬∀฀฀ ¬∀฀฀ ¬฀฀(฀฀, ฀฀) (L) ∀฀฀∃฀฀ ¬฀฀(฀฀, ฀฀)...