【离散数学】 SEU - 05 - 2021/03/17 - Nested Quantifiers

Discrete Mathematics and its Applications (8th Edition)
2021/03/17 - Nested Quantifiers


Contents


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.

【离散数学】 SEU - 05 - 2021/03/17 - Nested Quantifiers

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

上一篇:一些有意思的极限问题


下一篇:git clone 报错 Please make sure you have the correct access rights and the repository exists.