文章目录

一、 消除量词 等值式二、 量词否定 等值式三、 量词辖域收缩扩张 等值式四、 量词分配 等值式

一、 消除量词 等值式

消除量词等值式 :

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

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

∀xA(x)⇔A(a1)∧A(a2)∧⋯∧A(an)\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)∀xA(x)⇔A(a1​)∧A(a2​)∧⋯∧A(an​)

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

∃xA(x)⇔A(a1)∨A(a2)∨⋯∨A(an)\exist x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)∃xA(x)⇔A(a1​)∨A(a2​)∨⋯∨A(an​)

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

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

二、 量词否定 等值式

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

¬∀xA(x)⇔∃x¬A(x)\lnot \forall x A(x) \Leftrightarrow \exist x \lnot A(x)¬∀xA(x)⇔∃x¬A(x)

等值式解读 :

¬∀xA(x)\lnot \forall x A(x)¬∀xA(x) : 不是所有的 xxx 都有性质 AAA ;∃x¬A(x)\exist x \lnot A(x)∃x¬A(x) : 存在 xxx 不具有性质 AAA ;上述两个公式是等价的 ;

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

¬∃xA(x)⇔∀x¬A(x)\lnot \exist x A(x) \Leftrightarrow \forall x \lnot A(x)¬∃xA(x)⇔∀x¬A(x)

等值式解读 :

¬∃xA(x)\lnot \exist x A(x)¬∃xA(x) : 不存在 xxx 具有性质 AAA ;∀x¬A(x)\forall x \lnot A(x)∀x¬A(x) : 所有的 xxx 都不具有性质 AAA ;上述两个公式是等价的 ;

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

假设 BBB 是公式 , BBB 中不含有 xxx ( 前提很重要 ) ;

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

∀x(A(x)∨B)⇔∀xA(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)⇔∃xA(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)⇔∀xA(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)⇔∃xA(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)⇔∃xA(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)⇔∀xA(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→∀xA(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→∃xA(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))⇔∀xA(x)∧∀xB(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,BA , BA,B 两个性质 , 等价于 所有的对象都具有 AAA 性质 和 所有对象都具有 BBB 性质 ;

存全称量词 对于 合取联结词 ∧\land∧ 有分配率 , 对于 析取联结词 ∨\lor∨ 不适合分配率 ;

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

∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(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)

理解 : 存在对象 要么有 AAA 性质 , 要么有 BBB 性质 ;

存在量词 对于 析取联结词 ∨\lor∨ 有分配率 , 对于 合取联结词 ∧\land∧ 不适合分配率 ;

【数理逻辑】谓词逻辑 ( 谓词逻辑基本等值式 | 消除量词等值式 | 量词否定等值式 | 量词辖域收缩扩张等值式 | 量词分配等值式 )