Discrete Mathematics and its Applications (8th Edition)
2021/03/17 - Nested Quantifiers
Contents
- 1 The Foundations: Logic and Proofs
1 The Foundations: Logic and Proofs
1.5 Nested Quantifiers
1.5.3 Order of Quantifiers
Example: Let P ( x , y ) P(x,y) P(x,y) be the statement “ x + y = y + x . x+y=y+x. x+y=y+x.” Assume that U U U is the real numbers. Then ∀ x ∀ y P ( x , y ) \forall x\ \forall y\ P(x,y) ∀x ∀y P(x,y) and ∀ y ∀ x P ( x , y ) \forall y\ \forall x P(x,y) ∀y ∀xP(x,y) have the same truth value.
Example: Let Q ( x , y ) Q(x,y) Q(x,y) be the statement “ x + y = 0. x+y=0. x+y=0.” Assume that U U U is the real numbers. Then ∀ x ∃ y Q ( x , y ) \forall x\ \exists y\ Q(x,y) ∀x ∃y Q(x,y) is true while ∃ y ∀ x Q ( x , y ) \exists y\ \forall x\ Q(x,y) ∃y ∀x Q(x,y) is false.
1.5.4 Translating Mathematical Statements into Statements
Example: “The sum of two positive integers is always positive.”
∀ x ∀ y ( ( x > 0 ) ∧ ( y > 0 ) ) → ( x + y > 0 ) \forall x\ \forall y\ ((x>0)\wedge(y>0))\rightarrow(x+y>0) ∀x ∀y ((x>0)∧(y>0))→(x+y>0)
1.5.5 Translating from Nested Quantifiers into English
1.5.6 Translating English Sentences into Logical Expressions
| English | Logical Expressions |
|---|---|
| Brothers are siblings | ∀ x ∀ y ( B ( x , y ) → S ( x , y ) ) \forall x\ \forall y\ (B(x,y)\rightarrow S(x,y)) ∀x ∀y (B(x,y)→S(x,y)) |
| Siblinghood is semmetric | ∀ x ∀ y ( S ( x , y ) → S ( y , x ) ) \forall x\ \forall y\ (S(x,y)\rightarrow S(y,x)) ∀x ∀y (S(x,y)→S(y,x)) |
| Everybody loves somebody | ∀ x ∃ y L ( x , y ) \forall x\ \exists y\ L(x,y) ∀x ∃y L(x,y) |
| There is someone who is loved by everyone | ∃ x ∀ y L ( x , y ) \exists x\ \forall y\ L(x,y) ∃x ∀y L(x,y) |
| There is someone who loves someone | ∃ x ∃ y L ( x , y ) \exists x\ \exists y\ L(x,y) ∃x ∃y L(x,y) |
| Everyone loves himself | ∀ x L ( x , x ) \forall x\ \ L(x,x) ∀x L(x,x) |
1.5.7 Negating Nested Quantifiers
Equivalence by Replacement
- ∀ x ( A ( x ) ∨ B ) ≡ ∀ x A ( x ) ∨ B \forall x\ (A(x)\vee B)\equiv \forall x\ A(x) \vee B ∀x (A(x)∨B)≡∀x A(x)∨B
- ∀ x ( A ( x ) ∧ B ) ≡ ∀ x A ( x ) ∧ B \forall x\ (A(x)\wedge B)\equiv\forall x\ A(x)\wedge B ∀x (A(x)∧B)≡∀x A(x)∧B
- ∀ x ( A ( x ) → B ) ≡ ∃ x A ( x ) → B \forall x\ (A(x)\rightarrow B)\equiv{\color{red}\exists} x\ A(x)\rightarrow B ∀x (A(x)→B)≡∃x A(x)→B
- ∀ x ( B → A ( x ) ) ≡ B → ∀ x A ( x ) \forall x\ (B\rightarrow A(x))\equiv B\rightarrow \forall x\ A(x) ∀x (B→A(x))≡B→∀x A(x)
- ∃ x ( A ( x ) ∨ B ) ≡ ∃ x A ( x ) ∨ B \exists x\ (A(x)\vee B)\equiv \exists x\ A(x) \vee B ∃x (A(x)∨B)≡∃x A(x)∨B
- ∃ x ( A ( x ) ∧ B ) ≡ ∃ x A ( x ) ∧ B \exists x\ (A(x)\wedge B)\equiv\exists x\ A(x)\wedge B ∃x (A(x)∧B)≡∃x A(x)∧B
- ∃ x ( A ( x ) → B ) ≡ ∀ x A ( x ) → B \exists x\ (A(x)\rightarrow B)\equiv{\color{red} \forall} x\ A(x)\rightarrow B ∃x (A(x)→B)≡∀x A(x)→B
- ∃ x ( B → A ( x ) ) ≡ B → ∃ x A ( x ) \exists x\ (B\rightarrow A(x))\equiv B\rightarrow \exists x\ A(x) ∃x (B→A(x))≡B→∃x A(x)
- ∀ x ( A ( x ) ∧ B ( x ) ) ≡ ∀ x A ( x ) ∧ ∀ x B ( x ) \forall x\ (A(x)\wedge B(x))\equiv \forall x\ A(x)\wedge \forall x\ B(x) ∀x (A(x)∧B(x))≡∀x A(x)∧∀x B(x)
- ∃ x ( A ( x ) ∨ B ( x ) ) ≡ ∃ x A ( x ) ∨ ∃ x B ( x ) \exists x\ (A(x)\vee B(x))\equiv \exists x\ A(x)\vee \exists x\ B(x) ∃x (A(x)∨B(x))≡∃x A(x)∨∃x B(x)
- ∃ x ( A ( x ) → B ( x ) ) ≡ ∀ x A ( x ) → ∃ x B ( x ) \exists x\ (A(x)\rightarrow B(x))\equiv{\color{red}\forall} x A(x)\rightarrow \exists x\ B(x) ∃x (A(x)→B(x))≡∀xA(x)→∃x B(x)
Rules
Rule of replacement
Given Φ ( A ) \Phi(A) Φ(A), A ≡ B ⟹ Φ ( A ) ≡ Φ ( B ) A\equiv B\implies \Phi(A)\equiv \Phi(B) A≡B⟹Φ(A)≡Φ(B)
Rule of name replacement
∀
x
A
(
x
)
≡
∀
x
′
A
(
x
′
)
,
x
′
does not appear in
A
\forall x\ A(x)\equiv\forall x'\ A(x'),x' \text{ does not appear in } A
∀x A(x)≡∀x′ A(x′),x′ does not appear in A
∃
x
A
(
x
)
≡
∃
x
′
A
(
x
′
)
,
x
′
does not appear in
A
\exists x\ A(x)\equiv\exists x'\ A(x'),x' \text{ does not appear in } A
∃x A(x)≡∃x′ A(x′),x′ does not appear in A
Rule of substitution
A ( x ) ≡ A ( x ′ ) , x ′ does not appear in A A(x)\equiv A(x'),x' \text{ does not appear in } A A(x)≡A(x′),x′ does not appear in A
Assignment
ALL RIGHTS RESERVED © 2021 Teddy van Jerry
This blog is licensed under the CC 4.0 Licence.
See also
Teddy van Jerry’s CSDN Homepage
Teddy van Jerry’s GitHub Homepage