一、 消除量词 等值式

---

消除量词等值式 :

有限个体域 D = { a 1 , a 2 , ⋯   , a n } D = \{a_1 , a_2 , \cdots , a_n\} D={a1​,a2​,⋯,an​} , 消除量词 的 等值式 :

有限个体域 消除 全称量词 :

$$\forall xA(x)\iff A(a_1)\wedge A(a_2)\wedge \cdots \wedge A(a_n)$$

有限个体域 消除 存在量词 :

$$\exists xA(x)\iff A(a_1)\vee A(a_2)\vee \cdots \vee A(a_n)$$

一定要注意前提 : 有限个体域 ;

个体域是无限的时候 , 就需要量词 , 如 全总个体域 ;

二、 量词否定 等值式

---

否定全称量词 : 全称量词 $\forall$ 之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 存在量词 $\exists$ ;

$$\neg \forall xA(x)\iff \exists x\neg A(x)$$

等值式解读 :

• $\neg \forall xA(x)$ : 不是所有的 $x$ 都有性质 $A$ ;
• $\exists x\neg A(x)$ : 存在 $x$ 不具有性质 $A$ ;
• 上述两个公式是等价的 ;

否定存在量词 : 存在量词 $\exists$ 之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 全称量词 $\forall$ ;

$$\neg \exists xA(x)\iff \forall x\neg A(x)$$

等值式解读 :

• $\neg \exists xA(x)$ : 不存在 $x$ 具有性质 $A$ ;
• $\forall x\neg A(x)$ : 所有的 $x$ 都不具有性质 $A$ ;
• 上述两个公式是等价的 ;

三、 量词辖域收缩扩张 等值式

---

假设 $B$ 是公式 , $B$ 中不含有 $x$ ( 前提很重要 ) ;

1. 全称量词 辖域收缩扩张 ( 析取联结词 ) :

$$\forall x(A(x)\vee B)\iff \forall xA(x)\vee B$$

• 左侧的全称量词 $\forall x$ 的辖域是 $(A(x)\vee B)$
• 右侧的全称量词 $\forall x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\vee B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\vee B)$

2. 存在量词 辖域收缩扩张 ( 析取联结词 ) :

$$\exists x(A(x)\vee B)\iff \exists xA(x)\vee B$$

• 左侧的存在量词 $\exists x$ 的辖域是 $(A(x)\vee B)$
• 右侧的存在量词 $\exists x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\vee B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\vee B)$

3. 全称量词 辖域收缩扩张 ( 合取联结词 ) :

$$\forall x(A(x)\wedge B)\iff \forall xA(x)\wedge B$$

• 左侧的全称量词 $\forall x$ 的辖域是 $(A(x)\wedge B)$
• 右侧的全称量词 $\forall x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\wedge B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\wedge B)$

4. 存在量词 辖域收缩扩张 ( 合取联结词 ) :

$$\exists x(A(x)\wedge B)\iff \exists xA(x)\wedge B$$

• 左侧的存在量词 $\exists x$ 的辖域是 $(A(x)\wedge B)$
• 右侧的存在量词 $\exists x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\wedge B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\wedge B)$

5. 全称量词 辖域收缩扩张 ( 蕴含联结词 B 在右 ) :

$$\forall x(A(x)\to B)\iff \exists xA(x)\to B$$

• 左侧的全称量词 $\forall x$ 的辖域是 $(A(x)\to B)$
• 右侧的存在量词 $\exists x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\to B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\to B)$

6. 存在量词 辖域收缩扩张 ( 蕴含联结词 B 在右 ) :

$$\exists x(A(x)\to B)\iff \forall xA(x)\to B$$

• 左侧的存在量词 $\exists x$ 的辖域是 $(A(x)\to B)$
• 右侧的全称量词 $\forall x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(A(x)\to B)$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(A(x)\to B)$

( 使用 蕴含等值式 消去 蕴含联结词 可以证明 )

7. 全称量词 辖域收缩扩张 ( 蕴含联结词 B 在左 ) :

$$\forall x(B\to A(x))\iff B\to \forall xA(x)$$

• 左侧的全称量词 $\forall x$ 的辖域是 $(B\to A(x))$
• 右侧的全称量词 $\forall x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(B\to A(x))$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(B\to A(x))$

8. 存在量词 辖域收缩扩张 ( 蕴含联结词 B 在左 ) :

$$\exists x(B\to A(x))\iff B\to \exists xA(x)$$

• 左侧的存在量词 $\exists x$ 的辖域是 $(B\to A(x))$
• 右侧的存在量词 $\exists x$ 的辖域是 $A(x)$
• 从左到右 : 辖域由 $(B\to A(x))$ 收缩为 $A(x)$
• 从右到左 : 辖域由 $A(x)$ 扩张为 $(B\to A(x))$

四、 量词分配 等值式

---

1. 全称量词 对于 合取 $\wedge$ 的分配率 :

$$\forall x(A(x)\wedge B(x))\iff \forall xA(x)\wedge \forall xB(x)$$

理解 : 所有的对象都具有 $A,B$ 两个性质 , 等价于 所有的对象都具有 $A$ 性质 和 所有对象都具有 $B$ 性质 ;

存全称量词 对于 合取联结词 $\wedge$ 有分配率 , 对于 析取联结词 $\vee$ 不适合分配率 ;

2. 存在量词 对于 析取 $\vee$ 的分配率 :

$$\exists x(A(x)\vee B(x))\iff \exists xA(x)\vee \exists xB(x)$$

理解 : 存在对象 要么有 $A$ 性质 , 要么有 $B$ 性质 ;

存在量词 对于 析取联结词 $\vee$ 有分配率 , 对于 合取联结词 $\wedge$ 不适合分配率 ;