1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
[\<- 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)`
---
# 1.5 Nested Quantifiers p2
### Converting Sentences to Logical Statements
Ex. Let the domains of x and y be SCU students. Let R(x,y) be "x is related to y," let L(x,y) be "x likes y" and let S(x) be "x sleepwalks."
- Translate the following sentences into logical statements
1. There is a student who likes all other students but is related to no others
- "There is a student x s.t. for all students y, if y is different from x, then x likes y and x is not related to y"
- `Ǝx ∀y[(y!=x) -> L(x,y) ^ ┓R(x,y)]`
- **Note**: It's not `Ǝx ∀y[(y!=x) ^ (L(x,y) ^ ┓R(x,y))]`
- "There is a student x s.t. all students are not x, x likes y, and x is not related to y"
- This proposition will always be false
- **Note**: It's not `Ǝx[∀y(y!=x) -> (L(x,y) ^ ┓R(x,y))]`
2. No one likes a sleepwalker (not even themselves)
- "There is no student x for which there is a student who sleepwalks and who x likes"
- `┓Ǝx Ǝy[S(y) ^ L(x,y)]`
- This can be simplified to `∀x ∀y[┓S(y) ∨ ┓L(x,y)]`
3. `∀x Ǝy[(y!=x) ^ ┓L(y,x)]`
- "For every student x, there is a student y s.t. y and x are different and y doesn't like x"
- For every SCU student, there is another student SCU student who doesn't like them
- Why is this not the same as `∀x Ǝy[(y!=x) -> ┓L(y,x)]`?
- Suppose x is liked by everyone and y=x. The statement would be true (doesn't match the sentence)
---
Ex. Let S(x) be "x is a student," A(x,y) be "x has asked y a question," and F(x) be "x is a faculty member." The domain of all variables is people at SCU.
- Use logical symbols to express: "Some student has never been asked a question by a faculty member"
- "There is a person x s.t. x is a student (S(x)), if y is any person who is a faculty member, then y has not asked x a question (F(y) -> ┓A(y,x))"
- `Ǝx[S(x) ^ ∀y[F(y) -> ┓A(y,x)]]`
- Alternatively, `Ǝx ∀y[S(x) ^ (F(y) -> ┓A(y,x))]`
- **Not** `Ǝx ∀y[(S(x) ^ (F(y)) -> ┓A(y,x))]`
- True if S(x) or F(y) is false (contradicts the statement)
---
[1.7 ->](1.7.md)
|
