【数理逻辑】命题逻辑的等值演算与推理演算 ( 命题逻辑 | 等值演算 | 主合取 ( 析取 ) 范式 | 推理演算 ) ★★

2023-03-28 18:28:20 浏览数 (1)

文章目录

  • 一、 命题逻辑基本概念
  • 二、 等值演算
  • 三、 主合取 ( 析取 ) 范式
  • 四、 推理演算
    • 1、附加律
    • 2、化简律
    • 3、假言推理
    • 4、拒取式
    • 5、析取三段论
    • 6、假言三段论
    • 7、等价三段论
    • 8、构造性两难

参考博客 :

  • 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )
  • 【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )
  • 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )
  • 【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )
  • 【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 )
  • 【数理逻辑】命题逻辑 ( 命题逻辑推理正确性判定 | 形式结构是永真式 - 等值演算 | 从前提推演结论 - 逻辑推理 )

一、 命题逻辑基本概念

命题逻辑基本概念

  • 命题逻辑联结词
  • 真值表
  • 命题逻辑类型 : 可满足式 , 永真式 , 永假式 ;

1 . 命题公式 组成 :

① 单个 命题变元 / 命题常元 是命题公式 ;

② 如果

A

是命题公式 , 则

(lnot A)

也是命题公式 ;

③ 如果

A,B

是命题公式 , 则

(A land B) , (A lor B), (A to B), (A leftrightarrow B)

也是命题公式 ;

④ 有限次 应用 ① ② ③ 形成的符号串 是命题公式 ; ( 无限次不行 )

2 . 联结词 :

原子命题 :

p , q , r

表示 原子命题 , 又称为 简单命题 ;

  • 真 :
1

表示 命题真值 为真 ;

  • 假 :
0

表示 命题真值 为假 ;

联结词 : 上一篇博客 【数理逻辑】谓词逻辑 ( 个体词 | 个体域 | 谓词 | 全称量词 | 存在量词 | 谓词公式 | 习题 ) 三. 联结词 章节讲解了联结词 ;

  • 否定联结词 :
lnot
  • 合取联结词 :
land

,

p land q

,

pq

同真, 结果才为真 , 其余情况为假 ;

  • 析取联结词 :
lor

,

p lor q

,

pq

同假, 结果才为假 , 其余情况为真 ;

  • 蕴涵联结词 :
to

,

p to q

,

p

真

q

假, 结果才为假 , 其余情况为真 ;

  • 等价联结词 :
leftrightarrow

,

p leftrightarrow q

,

pq

真值相同时为真 , 表示等价成立 ,

pq

真值相反时为假 , 等价不成立 ;

联结词优先级 :

“

lnot

” 大于 “

land , lor

” 大于 “

to, leftrightarrow

”

land , lor

优先级相同 ;

to, leftrightarrow

优先级相同 ;

3 . 命题逻辑类型 :

可满足式 : 真值表中 , 至少有一个结果为真 , 可以都为真 ;

矛盾式 ( 永假式 ) : 所有的真值都为假 ;

可满足式 与 矛盾式 , 是 二选一 的 , 复合命题 要么是 可满足式 , 要么是 矛盾式 ;

重言式 ( 永真式 ) 是可满足式的一种 ;

4 . 简单命题形式化 :

参考 : 复合命题 与 命题符号化

定义命题 : 使用

p,q

代表真假必居其一的陈述句 ;

使用联结词 : 然后使用联结词联结这些

p,q

命题 ;

参考博客 :

  • 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )
  • 【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )

二、 等值演算

等值式概念 :

A , B

是两个命题公式 , 如果

A leftrightarrow B

是永真式 , 那么

A,B

两个命题公式是等值的 , 记做

A Leftrightarrow B

;

等值演算置换规则 :

A

和

B

两个命题公式 , 可以 互相代替 , 凡是出现

A

的地方都可以替换成

B

, 凡是出现

B

的地方都可以替换成

A

;

基本运算规律 :

  • 1. 幂等律 :
A Leftrightarrow A lor A

,

A Leftrightarrow A land A
  • 2. 交换律 :
A lor B Leftrightarrow B lor A

,

A land B Leftrightarrow B land A
  • 3. 结合律 :
(A lor B ) lor C Leftrightarrow A lor (B lor C)

,

(A land B ) land C Leftrightarrow A land (B land C)
  • 4. 分配律 :
A lor (B land C) Leftrightarrow ( A lor B ) land ( A lor C )

,

A land (B lor C) Leftrightarrow ( A land B ) lor ( A land C )

新运算规律 :

  • 5. 德摩根律 :
lnot ( A lor B ) Leftrightarrow lnot A land lnot B

,

lnot ( A land B ) Leftrightarrow lnot A lor lnot B
  • 6. 吸收率 :
    • 前者将后者吸收了 :
    A lor ( A land B ) Leftrightarrow A
    • 后者将前者吸收了 :
    A land ( A lor B ) Leftrightarrow A

    ;

0 , 1

相关的运算律 :

  • 7. 零律 :
A lor 1 Leftrightarrow 1

,

A land 0 Leftrightarrow 0
  • 8. 同一律 :
A lor 0 Leftrightarrow A

,

A land 1 Leftrightarrow A
  • 9. 排中律 :
A lor lnot A Leftrightarrow 1
  • 10. 矛盾律 :
A land lnot A Leftrightarrow 0

对偶原理适用于上述运算律 , 将两边的

land , lor

互换 , 同时

0 ,1

互换 , 等价仍然成立 ;

等价蕴含运算规律 :

  • 11. 双重否定率 :
lnot lnot A Leftrightarrow A
  • 12. 蕴涵等值式 :
A to B Leftrightarrow lnot A lor B
  • 13. 等价等值式 :
A leftrightarrow B Leftrightarrow ( A to B ) lor ( B to A )
  • 14. 等价否定等值式 :
A leftrightarrow B Leftrightarrow lnot A leftrightarrow lnot B
  • 15. 假言易位 ( 逆否命题 ) :
A to B Leftrightarrow lnot B to lnot A
  • 16. 归谬论 ( 反证法 ) :
( A to B ) land ( A to lnot B ) Leftrightarrow lnot A

参考博客 : 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )

三、 主合取 ( 析取 ) 范式

1 . 极小项

极小项 : 极小项 是 一种 简单合取式 ;

  • 1.前提 ( 简单合取式 ) : 含有
n

个 命题变项 的 简单合取式 ;

  • 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;
  • 3.命题变项出现位置 : 第
i

(

1 leq i leq n

) 个文字出现在 左起 第

i

个位置 ;

n

是指命题变项个数 ;

  • 4.极小项总结 : 满足上述三个条件的 简单合取式 , 称为 极小项 ;
  • 5.
m_i

与

M_i

之间的关系 : ①

lnot m_i iff M_i

②

lnot M_i iff m_i

每个命题 按照指定顺序 , 且 只出现一次 的 简单合取式 , 称为极小项 ;

极小项列出的是成真赋值 , 因为合取式只有一种情况成真 , 那就是全真 ;

2 . 极大项

关于 极大项 的 说明 :

  • 1.极大项个数 :
n

个 命题变元 会 产生

2^n

个 极大项 ;

  • 2.互不等值 :
2^n

个极大项 均 互不等值 ;

  • 3.极大项 :
m_i

表示 第

i

个极大项 , 其中

i

是该极大项 成假赋值 的 十进制表示 ;

  • 4.极大项名称 : 第
i

个极大项 , 称为

M_i

;

  • 5.
m_i

与

M_i

之间的关系 : ①

lnot m_i iff M_i

②

lnot M_i iff m_i

每个命题 按照指定顺序 , 且 只出现一次 的 简单析取式 , 称为极小项 ;

极大项列出的是成假赋值 , 因为析取式只有一种情况成假 , 那就是全假 ;

3 . 主合取 ( 析取 ) 范式

① 列出要求 主合取 ( 析取 ) 范式 的真值表 ;

p , q , r

三个命题真值从

0,0,0

到

1,1,1

, 有

2^3 = 8

列 , 每一列分别对应

m_0 sim m_8

极小项 ,

M_0 sim M_8

极大项 ;

② 主析取范式 ( 取极小项 ) : 真值表中的真值为

1

的列 取 极小项 ; 极小项 成真赋值 ; 根据极小项下标与成真赋值可以列出极小项的命题公式 ;

③ 主合取范式 ( 取极大项 ) : 真值表中的真值为

0

的列 取 极大项 ; 极大项 成假赋值 ; 根据极大项下标与成假赋值可以列出极大项的命题公式

4 . 总结 :

极小项 : 合取式 , 成真赋值 , 计算时取真值表 真 列 ;

极大项 : 析取式 , 成假赋值 , 计算时取真值表 假 列 ;

参考博客 : 【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )

四、 推理演算

推理的形式结构

前提 :

A_1 , A_2 , cdots , A_k

结论 :

B

推理的形式结构为 :

(A_1 land A_2 land cdots land A_k) to B

推理定律 :

A,B

是两个命题 , 如果

A to B

是永真式 , 那么

A Rightarrow B

;

1、附加律

附加律 :

A Rightarrow (A lor B)

根据 推理定律 ,

A to (A lor B)

蕴含式 是 永真式 ;

前提 :

A

结论 :

A lor B
A

是对的 , 那么

A lor B

也是对的 , 后者是在前者基础上附加了一个

B

;

2、化简律

化简律 :

( A land B ) Rightarrow A

,

( A land B ) Rightarrow B

根据 推理定律 ,

( A land B ) to A

,

( A land B ) to B

蕴含式 是 永真式 ;

前提 :

A land B

结论 :

A

或

B
A land B

是对的 , 那么

A

或

B

也是对的 , 后者是在前者基础上进行了化简 ;

3、假言推理

假言推理 :

( A to B ) land A Rightarrow B

根据 推理定律 ,

( A to B ) land A to B

蕴含式 是 永真式 ;

前提 :

A to B

,

A

结论 :

B

这是个典型的小三段论 ;

4、拒取式

拒取式:

( A to B ) land lnot B Rightarrow lnot A

根据 推理定律 ,

( A to B ) land lnot B to lnot A

蕴含式 是 永真式 ;

前提 :

A to B

,

lnot B

结论 :

lnot A

可以理解为是反证法 ;

5、析取三段论

析取三段论 :

( A lor B ) land lnot A Rightarrow B

,

( A lor B ) land lnot B Rightarrow A

根据 推理定律 ,

( A lor B ) land lnot A to B

,

( A lor B ) land lnot B to A

蕴含式 是 永真式 ;

前提 :

A lor B

,

lnot A

结论 :

B
(A lor B)

是正确的 , 其中

A

是错误的 , 那么

B

肯定是正确的 ;

(A lor B)

是正确的 , 其中

B

是错误的 , 那么

A

肯定是正确的 ;

警察破案常用推理方式 , 逐一排除嫌疑人 ;

6、假言三段论

假言三段论 :

( A to B ) land ( B to C ) Rightarrow ( A to C )

根据 推理定律 ,

( A to B ) land ( B to C ) to ( A to C )

蕴含式 是 永真式 ;

前提 :

A to B

,

B to C

结论 :

A to C

7、等价三段论

等价三段论:

( A leftrightarrow B ) land ( B leftrightarrow C ) Rightarrow ( A leftrightarrow C )

根据 推理定律 ,

( ( A leftrightarrow B ) land ( B leftrightarrow C ) ) to ( A leftrightarrow C )

蕴含式 是 永真式 ;

前提 :

A leftrightarrow B

,

B leftrightarrow C

结论 :

A leftrightarrow C

8、构造性两难

等价三段论:

( A to B ) land ( C to D ) land ( A lor C ) Rightarrow ( B lor D )

根据 推理定律 ,

( ( A to B ) land ( C to D ) land ( A lor C ) ) to ( ( B lor D ) )

蕴含式 是 永真式 ;

前提 :

A to B

,

C to D

,

A lor C

结论 :

B lor D

理解方式 :

A

是发展经济 ,

B

是污染

C

是不发展经济 ,

D

是贫穷

A lor B

要么发展经济 , 要么不发展经济 结果是

B lor D

, 要么产生污染 , 要么忍受贫穷

参考博客 : 【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 )

博客 基础 原理

0 人点赞