diff options
Diffstat (limited to '1.5.md')
| -rw-r--r-- | 1.5.md | 56 |
1 files changed, 56 insertions, 0 deletions
@@ -0,0 +1,56 @@ +[\<- 1.4](1.4.md) + +--- + +# 1.5 Nested Quantifiers p1 + +- Let the domain of x and y be the reals + +|Logical Statement|Words| +|-----------------|-----| +|∀x(∀y(xy=xy)) |"For all x∈ℝ (is an element of real numbers) and all y∈ℝ, xy = yx"| +|∀y(∀x(xy=xy)) |"For all y∈ℝ (is an element of real numbers) and all x∈ℝ, xy = yx"| + +- Both columns are true +- `∀x(∀y(xy=xy)) ≡ ∀y(∀x(xy=xy))` + +Quantifiers **inside** the scope of other quantifiers are called **nested quantifiers** + +- Note: `∀s ∀t P(s,t) ≡ ∀t ∀s P(s,t) + +--- + +- Ex. Let the domain of x and y be **positive reals**. Convert the logical statement to words and determine its truth value. + 1. `∀x Ǝy (x=y^2)` + - "For all x>0, there exists y>0 s.t. (such that) x=y^2." + - This statement is **True** since for any x, we would pick y=sqrt(x) + - e.g. if x=4, then y=2 + - e.g. if x=5.72, then y=sqrt(5.72) + 2. `Ǝy ∀x (x=y^2)` + - "There exists a number y>0 s.t. for all x>0, x=y^2." + - This statement is **False** since once y is chosen, y^2 can only be one value. Therefore, only one value of x would satisfy x=y^2 (and not all x). + - Note: `∀x Ǝy P(x,y)` is **not** equivalent to `Ǝy ∀x P(x,y)` + +- Ex. Let the domain of x and y be integers. Convert the logical statement to words and determine its truth value. + 1. `Ǝx Ǝy (x^2 + y^2 = 3)` + - In words: "There is an integer x and there is an integer y s.t. x^2 + y^2 = 3" + 2. `Ǝy Ǝx (x^2 + y^2 = 3)` + - In words: "There is an integer y and there is an integer x s.t. x^2 + y^2 = 3" + - Both of these examples have the same meaning + - `Ǝx Ǝy P(x,y) ≡ Ǝy Ǝx P(x,y)` + - These statements are **False** since no **integer** values of x and y can be plugged in to create a true statement + +--- + +**Careful**: `∀x(Ǝy P(y) -> ...)` is **not** equivalent to `∀x Ǝy(P(y) -> ...)` +- Be careful when moving quantifiers to make sure the meaning is the same + +- Ex. Let P(Y) be "student y turns in their homework". Domain of y is students in our class. Let q be "Luvreet is happy" + - `Ǝy P(y) -> q` + - "If there is a student y who turns in their homework, then Luvreet is happy" + - `Ǝy(P(y) -> q)` + - "There is a student y s.t. if y turns in their homework, then Luvreet is happy" + - These propositional functions are different the first one is basically saying, "Luvreet is happy when **any** student turns in their homework" but the second is basically saying, "Luvreet is happy when y turns in their homework" + - A true statement would be: `Ǝy P(y) -> q ≡ ∀y(P(y) -> q)` + +--- |