Site Overlay

# 离散数学笔记：1.5 嵌套量词，量词消去和前束范式

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

【例子】量化这个命题：“For every real number x, if x ≠ 0, then there exists a real
number y such that 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 quantiﬁers 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))$$

$\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) ))\\$$