提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

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

逻辑 基本 分配 消除 收缩 谓词 等值 扩张
2023-06-13 09:17:44 时间

文章目录

一、 消除量词 等值式

消除量词等值式 :

有限个体域

D = \{a_1 , a_2 , \cdots , a_n\}

, 消除量词 的 等值式 :

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

\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)

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

\exist x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)

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

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

二、 量词否定 等值式

否定全称量词 : 全称量词

\forall

之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 存在量词

\exist

;

\lnot \forall x A(x) \Leftrightarrow \exist x \lnot A(x)

等值式解读 :

\lnot \forall x A(x)

: 不是所有的

x

都有性质

A

;

\exist x \lnot A(x)

: 存在

x

不具有性质

A

;

  • 上述两个公式是等价的 ;

否定存在量词 : 存在量词

\exist

之前 的 否定联结词 , 可以移到 量词 之后 , 量词要变成 全称量词

\forall

;

\lnot \exist x A(x) \Leftrightarrow \forall x \lnot A(x)

等值式解读 :

\lnot \exist x A(x)

: 不存在

x

具有性质

A

;

\forall x \lnot A(x)

: 所有的

x

都不具有性质

A

;

  • 上述两个公式是等价的 ;

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

假设

B

是公式 ,

B

中不含有

x

( 前提很重要 ) ;

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

\forall x ( A(x) \lor B ) \Leftrightarrow \forall x A(x) \lor B
  • 左侧的全称量词
\forall x

的辖域是

( A(x) \lor B )
  • 右侧的全称量词
\forall x

的辖域是

A(x)
  • 从左到右 : 辖域由
( A(x) \lor B )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( A(x) \lor B )

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

\exist x ( A(x) \lor B ) \Leftrightarrow \exist x A(x) \lor B
  • 左侧的存在量词
\exist x

的辖域是

( A(x) \lor B )
  • 右侧的存在量词
\exist x

的辖域是

A(x)
  • 从左到右 : 辖域由
( A(x) \lor B )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( A(x) \lor B )

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

\forall x ( A(x) \land B ) \Leftrightarrow \forall x A(x) \land B
  • 左侧的全称量词
\forall x

的辖域是

( A(x) \land B )
  • 右侧的全称量词
\forall x

的辖域是

A(x)
  • 从左到右 : 辖域由
( A(x) \land B )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( A(x) \land B )

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

\exist x ( A(x) \land B ) \Leftrightarrow \exist x A(x) \land B
  • 左侧的存在量词
\exist x

的辖域是

( A(x) \land B )
  • 右侧的存在量词
\exist x

的辖域是

A(x)
  • 从左到右 : 辖域由
( A(x) \land B )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( A(x) \land B )

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

\forall x ( A(x) \to B ) \Leftrightarrow \exist x A(x) \to B
  • 左侧的全称量词
\forall x

的辖域是

( A(x) \to B )
  • 右侧的存在量词
\exist x

的辖域是

A(x)
  • 从左到右 : 辖域由
( A(x) \to B )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( A(x) \to B )

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

\exist x ( A(x) \to B ) \Leftrightarrow \forall x A(x) \to B
  • 左侧的存在量词
\exist 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) ) \Leftrightarrow B \to \forall x A(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 在左 ) :

\exist x ( B \to A(x) ) \Leftrightarrow B \to \exist x A(x)
  • 左侧的存在量词
\exist x

的辖域是

( B \to A(x) )
  • 右侧的存在量词
\exist x

的辖域是

A(x)
  • 从左到右 : 辖域由
( B \to A(x) )

收缩为

A(x)
  • 从右到左 : 辖域由
A(x)

扩张为

( B \to A(x) )

四、 量词分配 等值式

1. 全称量词 对于 合取

\land

的分配率 :

\forall x ( A(x) \land B(x) ) \Leftrightarrow \forall x A(x) \land \forall x B(x)

理解 : 所有的对象都具有

A , B

两个性质 , 等价于 所有的对象都具有

A

性质 和 所有对象都具有

B

性质 ;

存全称量词 对于 合取联结词

\land

有分配率 , 对于 析取联结词

\lor

不适合分配率 ;

2. 存在量词 对于 析取

\lor

的分配率 :

\exist x ( A(x) \lor B(x) ) \Leftrightarrow \exist x A(x) \lor \exist x B(x)

理解 : 存在对象 要么有

A

性质 , 要么有

B

性质 ;

存在量词 对于 析取联结词

\lor

有分配率 , 对于 合取联结词

\land

不适合分配率 ;

相关文章