量词

量词换序

• $\forall x\forall yA(x,y)⟺\forall y\forall xA(x,y)$
• $\exists x\exists yA(x,y)⟺\exists y\exists xA(x,y)$

量词否定

• $\neg \forall xA(x)⟺\exists x\neg A(x)$
• $\neg \exists xA(x)⟺\forall x\neg A(x)$

量词辖域收缩扩张等值式

以下结论都可通过对$B$的真值分类讨论来证明

• $\forall x(A(x)\vee B)⟺\forall xA(x)\vee B$
• $\forall x(A(x)\wedge B)⟺\forall xA(x)\wedge B$
• $\forall x(A(x)\to B)⟺\exists xA(x)\to B$
• $\forall x(B\to A(x))⟺B\to \forall xA(x)$
• $\exists x(A(x)\vee B)⟺\exists xA(x)\vee B$
• $\exists x(A(x)\wedge B)⟺\exists xA(x)\wedge B$
• $\exists x(A(x)\to B)⟺\forall xA(x)\to B$
• $\exists x(B\to A(x))⟺B\to \exists xA(x)$

量词分配等值式

对$\forall xA(x)$的真值分类讨论来证明

• $\forall x(A(x)\wedge B(x))⟺\forall xA(x)\wedge \forall xB(x)$
• $\exists x(A(x)\vee B(x))⟺\exists xA(x)\vee \exists xB(x)$

蕴含否定

• $\neg \forall (A(x)\to B(x))⟺\exists x(A(x)\wedge \neg B(x))$
• $\neg \exists (A(x)\wedge B(x))⟺\forall x(A(x)\to \neg B(x))$

举例

1. 函数复合的结合律的证明(量词辖域收缩扩张等值式，量词交换)

$f:A\to B,g:B\to C,h:C\to D$, 证明$(h\circ g)\circ f=h\circ (g\circ f)$

$(a,d)\in (h\circ g)\circ f⟺\exists b((a,b)\in f\wedge (b,d)\in g\circ f)⟺\exists b((a,b)\in f\wedge \exists c(c\in C\wedge (b,c)\in g\wedge (c,d)\in h))⟺\exists b\exists c((a,b)\in f\wedge (b,c)\in g\wedge (c,d)\in h)$

$(a,d)\in h\circ (g\circ f)⟺\exists c((a,c)\in g\circ f\wedge (c,d)\in h)⟺\exists c(\exists b((a,b)\in f\wedge (b,c)\in g)\wedge (c,d)\in h)⟺\exists c\exists b((a,b)\in f\wedge (b,c)\in g\wedge (c,d)\in h)$

$\exists b\exists c((a,b)\in f\wedge (b,c)\in g\wedge (c,d)\in h)⟺\exists b\exists c((a,b)\in f\wedge (b,c)\in g\wedge (c,d)\in h)$

2. $R$上的一致连续函数的定义(蕴含否定)

一致连续：$\forall ϵ>0,\exists \delta >0,\forall x,y\in R,(|x-y|<\delta \to |f(x)-f(y)|<ϵ)$ (is true)
一致连续的否定：$\exists ϵ>0,\forall \delta >0,\exists x,y\in R,(|x-y|<\delta \wedge |f(x)-f(y)|\ge ϵ)$ (is ture)

即只需要把任意和存在互换，然后否定最内层的命题。