Site Overlay

离散数学笔记:1.5 嵌套量词,量词消去和前束范式

我们看这个量化句:

$$
\forall x\exists y(x+y=0)
$$

它表示:对于所有的 $x$ 存在 $y$ 使得 $x+y = 0$.

这里我们使用了两个量化符号,这就是一种嵌套(nest)。

【例子】量化这个命题:“For every real number x, if x ≠ 0, then there exists a real
number y such that xy = 1”

解:$∀x((x ≠ 0) → ∃y(xy = 1))$

【例子】10. Let F(x,y) be the statement “x can fool y,” where the domain consists of all people in the world. Use quantifiers to express each of these statements.

a) Everybody can fool Fred.

$\forall x F\left(x, Fred\right)$

b) Evelyn can fool everybody.

$\forall x F(Evelyn, x)$

c) Everybody can fool somebody.

$\forall x, \exist y F(x,y)$

d) There is no one who can fool everybody.

$\neg \exist x \forall y F(x, y)$

e) Everyone can be fooled by somebody.

$\exist x \forall y F(x, y)$

f) No one can fool both Fred and Jerry.

$\neg \exist x, F(x, Fred) \wedge F(x, Jerry)$

g) Nancy can fool exactly two people.

$F(Nancy, x) \wedge F(nancy, y) \wedge (x\ne y) \wedge (\forall p F(Nancy, p)\to (p=x\vee p=y))$

h) There is exactly one person whom everybody can fool.

$\exists x, \forall y F(y, x) \wedge (\forall p, \forall y (y,p)\to p = x)$

i) No one can fool himself or herself.

$\neg \exist x F(x,x)$

j) There is someone who can fool exactly one person besides himself or herself.
$\exists x, \exists y F(y, x) \wedge (\exists p, \forall y (y,p)\to p = x \wedge y\ne x)$

量词消去

我们可以通过一些操作,把带量词的公式转化为等价、不带量词的公式。

【例子】设个体域 D={a,b,c}, 消去下列各式的量词:

(1) $\forall x\exist y(F(x)∧G(y))$

解:这其实就是一个循环遍历的嵌套。

$$
((F(a)\and G(a))\or(F(a)\and G(b))(F(a)\and G(c)))\\\\\and ((F(b)\and G(a))\or(F(b)\and G(b))(F(b)\and G(c)))\\\\\and ((F(c)\and G(a))\or(F(c)\and G(b))(F(c)\and G(c)))\\
$$

(2) $ \forall x(F(x,y)\to \exist yG(y))$

$$
(F(a,a)\to \exist aG(a) \vee F(a,b)\to \exist bG(b) \vee F(a,c)\to \exist cG(c))\wedge \\
(F(b,a)\to \exist aG(a) \vee F(c,b)\to \exist bG(b) \vee F(b,c)\to \exist cG(c))\wedge \\
(F(c,a)\to \exist aG(a) \vee F(c,b)\to \exist bG(b) \vee F(c,c)\to \exist cG(c))
$$

附加2、证明等值式:

$\forall x F(x)∨~\exist xG(x)\Leftrightarrow \forall x\forall y(F(x)∨~G(y))$

$$
\forall x F(x)∨~\exist xG(x)\\
= \forall xF(x) \vee \forall xG(x)\\
= \forall x\forall y(F(x)∨~G(y))
$$

前束范式

什么是前束范式?我觉得这个定义比较好理解:

一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式。

求前束范式:

(1) $\forall xF(x) ∨ \exist xG(x)$

这个就是我们前面证明的等值式。答案是:

$\forall x\forall y(F(x)∨~G(y))$

(2)$\forall x P(x)\to \exists x Q(x)$

解:

$$
\forall x P(x)\to \exists x Q(x)\\\equiv \neg (\forall x P(x)) \or \exists x Q(x)\\\equiv (\exists x \neg P(X)) \or \exists x Q(x)\\\equiv \exists x (\neg P(X)\or Q(x) )\\
$$

(3) $(\forall x) (\forall y)((\exist z)(P(x,z)∧P(y,z))\to(\exist u)Q(x,y,u))$

$$
= (\forall x) (\forall y)((\exist z)(P(x,z)∧P(y,z))\to(\exist u)Q(x,y,u)) \\= (\forall x) (\forall y)( \neg (P(x,z)∧P(y,z)) \vee (\exist u)Q(x,y,u) ))\\= (\forall x) (\forall y)(\exist u)( \neg (P(x,z)∧P(y,z)) \vee Q(x,y,u) ))\\
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注