量词逻辑 - kscarrot/blog GitHub Wiki

全称量词

当且仅当所有x使得P(x)为真则命题为真

forall,全部,值为域中命题的逻辑合取

$$ \forall_{x\in X}P(x) \Longleftrightarrow P(x_{1})\land P(x_{2}) \dots \land P(x_{n})$$

存在量词

当且仅当存在一个x使得P(x)为真则命题为真

exist,存在,有一个 值为域种命题的逻辑析取

$$ \exists_{x\in X}P(x) \Longleftrightarrow P(x_{1})\lor P(x_{2}) \dots \lor P(x_{n})$$

特别的用E加!的方式来表示存在唯一.

• 这里可以 使用循环 的逻辑去思考,量词的嵌套也是循环的嵌套 即 and/or Bool[]
• 反过来,在不计数的情况下,循环可以表达为一个全称命题,带break的循环可以表达为一个存在命题
• 存在命题是不用遍历所有结果的,存在唯一则依然需要遍历所有结果
• 全称命题需要遍历所有的结果,无论举了多少个特例,没有覆盖完全不能证明真

量词嵌套

可以规约元素的作用域然后带入消元.对全称和存在作用相同.

$$\begin{align} \forall x\exists y P(x,y) & = \exists y P_{x_1}(y) \land \exists y P_{x_2}(y) \dots \exists y P_{x_n}(y) \ & = [ P_{x_1}(y1) \lor P_{x_1}(y2) \dots \lor P_{x_1}(yn)] \land ... [ P_{x_n}(y1) \lor P_{x_n}(y2) \dots \lor P_{x_n}(yn)] \end{align} $$

二元嵌套真值

语句	真	假
$\forall x \forall y P(x,y)$	对任意对(x,y)	存在一对(x,y)
$\forall x \exists y P(x,y)$	对任意x存在一个y	存在一个x对任意y
$\exists x \forall y P(x,y)$	存在一个x对任意y	对任意x存在一个y
$\exists x \exists y P(x,y)$	存在一对(x,y)	对任意对 (x,y)

   

$$ \forall x \exists y P(x,y) \neq \exists y\forall x P(x,y) $$

量词否定

$$ \lnot \forall x P(x) = \exists x \lnot P(x)$$

$$ \lnot \exists x P(x) = \forall x \lnot P(x)$$

展开即可证:

$$\begin{align} \lnot \forall x P(x) = & \lnot (P(x_{1}) \land P(x_{2})\dots P(x_{n}))\ = &\lnot P(x_{1}) \lor \lnot P(x_{2}) \lor \dots \lor \lnot P(x_{n}) \
= & \exists \lnot P(x) \end{align} $$ 嵌套量词否定

$$\lnot \forall x \exists y P(x,y) = \exists x\forall y \lnot P(x,y) $$

$$\lnot \exists x \forall y P(x,y) =\forall x \exists y \lnot P(x,y) $$

量词推导补充

$$\exists x\forall y P(x,y) \implies \forall y \exists x P(x,y) $$

• 左推右带入特例x即可.
• 右是推不出左的,因为使右式成立的x可能不唯一.

前束范式

$$ \forall x P(x) \land \exists y Q(x) = \forall x \exists y (P(x) \land Q(y))$$

$$ \forall x P(x) \lor \exists y Q(x) = \forall x \exists y (P(x) \lor Q(y))$$