Discrete Math_03_02

Views:

Category: Entertainment

Presentation Description

No description available.

Presentation Transcript

Section 3.2

Negations of Quantified Statements:

Negations of Quantified Statements The negation of a universal statement (“all are”) is logically equivalent to an existential statement (“some are not” or “there is at least one that is not”). “All Jews wear glasses.” “Some Jews don’t wear glasses.”

Negations of Quantified Statements:

Negations of Quantified Statements The negation of an existential statement (“some are”) is logically equivalent to a universal statement (“none are” or “all are not”). “Some Jews wear glasses.” “All Jews don’t wear glasses.”

Example 1 – Negating Quantified Statements:

Example 1 – Negating Quantified Statements Write formal negations for the following statements: a. ∀ primes p , p is odd. b. ∃ a triangle T such that the sum of the angles of T equals 200  . Solution: ∃ a prime p such that p is not odd. b. ∀ triangles T, the sum of the angles of T does not equal 200  .

Example 2 – Negating Quantified Statements:

Example 2 – Negating Quantified Statements Write informal negations for the following statements: a. All computer programs are finite. b. Some people over 40 dress up on Purim. c. The number 1,357 is divisible by some integer between 1 and 37. Solution: There is a computer program that is infinite.. No people over 40 dress up on Purim. The number 1,357 is not divisible by any integer between 1 and 37.

Negations of Universal Conditional Statements:

Negations of Universal Conditional Statements

Example 4 – Negating Universal Conditional Statements:

Example 4 – Negating Universal Conditional Statements Write a formal negation for statement (a) and an informal negation for statement (b). a. ∀ people p , if p is blond then p has blue eyes. b. If a computer program has more than 100,000 lines, then it contains a bug. Solution: a. ∃ a person p such that p is blond and p does not have blue eyes. b. There is at least one computer program that has more than 100,000 lines and does not contain a bug.

The Relation among ∀, ∃, ∧, and ∨:

The Relation among ∀, ∃, ∧, and ∨ If Q ( x ) is a predicate and the domain D of x is the set { x 1 , x 2 , . . . , x n }, then the statements and are logically equivalent.

The Relation among ∀, ∃, ∧, and ∨:

The Relation among ∀, ∃, ∧, and ∨ Similarly, if Q ( x ) is a predicate and D = { x 1 , x 2 , . . . , x n }, then the statements and are logically equivalent.

Vacuous Truth of Universal Statements:

Vacuous Truth of Universal Statements All the balls in the bowl are blue. There exists a ball in the bowl that is not blue . is called vacuously true or true by default if, and only if, P ( x ) is false for every x in D .

Variants of Universal Conditional Statements:

Variants of Universal Conditional Statements

Example 5 – Contrapositive, Converse, and Inverse of a Universal Conditional Statement:

Example 5 – Contrapositive, Converse, and Inverse of a Universal Conditional Statement If a real number is greater than 2, then its square is greater than 4. The formal version of this statement is ∀ x ∈ R , if x > 2 then x 2 > 4. Contrapositive : ∀ x ∈ R , if x 2 ≤ 4 then x ≤ 2. Or: If the square of a real number is less than or equal to 4, then the number is less than or equal to 2. Converse : ∀ x ∈ R , if x 2 > 4 then x > 2. Or: If the square of a real number is greater than 4, then the number is greater than 2. Inverse : ∀ x ∈ R , if x ≤ 2 then x 2 ≤ 4. Or: If a real number is less than or equal to 2, then the square of the number is less than or equal to 4 .

Variants of Universal Conditional Statements:

Variants of Universal Conditional Statements

Variants of Universal Conditional Statements:

Variants of Universal Conditional Statements ∀ x ∈ R , if x > 2 then x 2 > 4 Converse : ∀ x ∈ R , if x 2 > 4 then x > 2 . False (since, for instance, (−3) 2 = 9 > 4 but −3 2). Inverse : ∀x ∈ R , if x ≤ 2 then x 2 ≤ 4 . False (since, for instance, −3 < 2, but (−3) 2 = 9 is NOT ≤ 4 ).

Necessary and Sufficient Conditions, Only If:

Necessary and Sufficient Conditions, Only If The definitions of necessary, sufficient, and only if can also be extended to apply to universal conditional statements.

Example 6 – Necessary and Sufficient Conditions:

Example 6 – Necessary and Sufficient Conditions Rewrite the following statements as quantified conditional statements. Do not use the word necessary or sufficient . a. Squareness is a sufficient condition for rectangularity. b. Being at least 35 years old is a necessary condition for being President of the United States. ∀ x, if x is a square, then x is a rectangle. All squares are rectangles. ∀ people x, if x is younger than 35, then x cannot be President of the United States . Or : ∀ people x, if x is President of the United States, then x is at least 35 years old . All Presidents of the United States are at least 35 years old.