文章目录
一、 消除量词 等值式
二、 量词否定 等值式
三、 量词辖域收缩扩张 等值式
四、 量词分配 等值式
一、 消除量词 等值式
消除量词等值式 :
有限个体域 D = { a 1 , a 2 , ⋯ , a n } D = \{a_1 , a_2 , \cdots , a_n\}D={a
1
,a
2
,⋯,a
n
} , 消除量词 的 等值式 :
有限个体域 消除 全称量词 :
∀ x A ( x ) ⇔ A ( a 1 ) ∧ A ( a 2 ) ∧ ⋯ ∧ A ( a n ) \forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)
∀xA(x)⇔A(a
1
)∧A(a
2
)∧⋯∧A(a
n
)
有限个体域 消除 存在量词 :
∃ x A ( x ) ⇔ A ( a 1 ) ∨ A ( a 2 ) ∨ ⋯ ∨ A ( a n ) \exist x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)
∃xA(x)⇔A(a
1
)∨A(a
2
)∨⋯∨A(a
n
)
一定要注意前提 : 有限个体域 ;
个体域是无限的时候 , 就需要量词 , 如 全总个体域 ;
二、 量词否定 等值式
否定全称量词 : 全称量词 ∀ \forall∀ 之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 存在量词 ∃ \exist∃ ;
¬ ∀ x A ( x ) ⇔ ∃ x ¬ A ( x ) \lnot \forall x A(x) \Leftrightarrow \exist x \lnot A(x)
¬∀xA(x)⇔∃x¬A(x)
等值式解读 :
¬ ∀ x A ( x ) \lnot \forall x A(x)¬∀xA(x) : 不是所有的 x xx 都有性质 A AA ;
∃ x ¬ A ( x ) \exist x \lnot A(x)∃x¬A(x) : 存在 x xx 不具有性质 A AA ;
上述两个公式是等价的 ;
否定存在量词 : 存在量词 ∃ \exist∃ 之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 全称量词 ∀ \forall∀ ;
¬ ∃ x A ( x ) ⇔ ∀ x ¬ A ( x ) \lnot \exist x A(x) \Leftrightarrow \forall x \lnot A(x)
¬∃xA(x)⇔∀x¬A(x)
等值式解读 :
¬ ∃ x A ( x ) \lnot \exist x A(x)¬∃xA(x) : 不存在 x xx 具有性质 A AA ;
∀ x ¬ A ( x ) \forall x \lnot A(x)∀x¬A(x) : 所有的 x xx 都不具有性质 A AA ;
上述两个公式是等价的 ;
三、 量词辖域收缩扩张 等值式
假设 B BB 是公式 , B BB 中不含有 x xx ( 前提很重要 ) ;
1. 全称量词 辖域收缩扩张 ( 析取联结词 ) :
∀ x ( A ( x ) ∨ B ) ⇔ ∀ x A ( x ) ∨ B \forall x ( A(x) \lor B ) \Leftrightarrow \forall x A(x) \lor B
∀x(A(x)∨B)⇔∀xA(x)∨B
左侧的全称量词 ∀ x \forall x∀x 的辖域是 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B)
右侧的全称量词 ∀ x \forall x∀x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B)
2. 存在量词 辖域收缩扩张 ( 析取联结词 ) :
∃ x ( A ( x ) ∨ B ) ⇔ ∃ x A ( x ) ∨ B \exist x ( A(x) \lor B ) \Leftrightarrow \exist x A(x) \lor B
∃x(A(x)∨B)⇔∃xA(x)∨B
左侧的存在量词 ∃ x \exist x∃x 的辖域是 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B)
右侧的存在量词 ∃ x \exist x∃x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) ∨ B ) ( A(x) \lor B )(A(x)∨B)
3. 全称量词 辖域收缩扩张 ( 合取联结词 ) :
∀ x ( A ( x ) ∧ B ) ⇔ ∀ x A ( x ) ∧ B \forall x ( A(x) \land B ) \Leftrightarrow \forall x A(x) \land B
∀x(A(x)∧B)⇔∀xA(x)∧B
左侧的全称量词 ∀ x \forall x∀x 的辖域是 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B)
右侧的全称量词 ∀ x \forall x∀x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B)
4. 存在量词 辖域收缩扩张 ( 合取联结词 ) :
∃ x ( A ( x ) ∧ B ) ⇔ ∃ x A ( x ) ∧ B \exist x ( A(x) \land B ) \Leftrightarrow \exist x A(x) \land B
∃x(A(x)∧B)⇔∃xA(x)∧B
左侧的存在量词 ∃ x \exist x∃x 的辖域是 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B)
右侧的存在量词 ∃ x \exist x∃x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) ∧ B ) ( A(x) \land B )(A(x)∧B)
5. 全称量词 辖域收缩扩张 ( 蕴含联结词 B 在右 ) :
∀ x ( A ( x ) → B ) ⇔ ∃ x A ( x ) → B \forall x ( A(x) \to B ) \Leftrightarrow \exist x A(x) \to B
∀x(A(x)→B)⇔∃xA(x)→B
左侧的全称量词 ∀ x \forall x∀x 的辖域是 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B)
右侧的存在量词 ∃ x \exist x∃x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B)
6. 存在量词 辖域收缩扩张 ( 蕴含联结词 B 在右 ) :
∃ x ( A ( x ) → B ) ⇔ ∀ x A ( x ) → B \exist x ( A(x) \to B ) \Leftrightarrow \forall x A(x) \to B
∃x(A(x)→B)⇔∀xA(x)→B
左侧的存在量词 ∃ x \exist x∃x 的辖域是 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B)
右侧的全称量词 ∀ x \forall x∀x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( A ( x ) → B ) ( A(x) \to B )(A(x)→B)
( 使用 蕴含等值式 消去 蕴含联结词 可以证明 )
7. 全称量词 辖域收缩扩张 ( 蕴含联结词 B 在左 ) :
∀ x ( B → A ( x ) ) ⇔ B → ∀ x A ( x ) \forall x ( B \to A(x) ) \Leftrightarrow B \to \forall x A(x)
∀x(B→A(x))⇔B→∀xA(x)
左侧的全称量词 ∀ x \forall x∀x 的辖域是 ( B → A ( x ) ) ( B \to A(x) )(B→A(x))
右侧的全称量词 ∀ x \forall x∀x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( B → A ( x ) ) ( B \to A(x) )(B→A(x)) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( B → A ( x ) ) ( B \to A(x) )(B→A(x))
8. 存在量词 辖域收缩扩张 ( 蕴含联结词 B 在左 ) :
∃ x ( B → A ( x ) ) ⇔ B → ∃ x A ( x ) \exist x ( B \to A(x) ) \Leftrightarrow B \to \exist x A(x)
∃x(B→A(x))⇔B→∃xA(x)
左侧的存在量词 ∃ x \exist x∃x 的辖域是 ( B → A ( x ) ) ( B \to A(x) )(B→A(x))
右侧的存在量词 ∃ x \exist x∃x 的辖域是 A ( x ) A(x)A(x)
从左到右 : 辖域由 ( B → A ( x ) ) ( B \to A(x) )(B→A(x)) 收缩为 A ( x ) A(x)A(x)
从右到左 : 辖域由 A ( x ) A(x)A(x) 扩张为 ( B → A ( x ) ) ( B \to A(x) )(B→A(x))
四、 量词分配 等值式
1. 全称量词 对于 合取 ∧ \land∧ 的分配率 :
∀ x ( A ( x ) ∧ B ( x ) ) ⇔ ∀ x A ( x ) ∧ ∀ x B ( x ) \forall x ( A(x) \land B(x) ) \Leftrightarrow \forall x A(x) \land \forall x B(x)
∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)
理解 : 所有的对象都具有 A , B A , BA,B 两个性质 , 等价于 所有的对象都具有 A AA 性质 和 所有对象都具有 B BB 性质 ;
存全称量词 对于 合取联结词 ∧ \land∧ 有分配率 , 对于 析取联结词 ∨ \lor∨ 不适合分配率 ;
2. 存在量词 对于 析取 ∨ \lor∨ 的分配率 :
∃ x ( A ( x ) ∨ B ( x ) ) ⇔ ∃ x A ( x ) ∨ ∃ x B ( x ) \exist x ( A(x) \lor B(x) ) \Leftrightarrow \exist x A(x) \lor \exist x B(x)
∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)
理解 : 存在对象 要么有 A AA 性质 , 要么有 B BB 性质 ;
存在量词 对于 析取联结词 ∨ \lor∨ 有分配率 , 对于 合取联结词 ∧ \land∧ 不适合分配率 ;
