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

韩曙亮

发布于 2023-03-28 17:43:10

2K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

基于上一篇博客【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表可满足式矛盾式重言式 ) ;

一、等值演算

等值演算 :

等值式
基本等值式
等值演算置换规则

二、等值式

等值式概念 :

A , B

是两个命题公式 , 如果

A \leftrightarrow B

是永真式 , 那么

A,B

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

A \Leftrightarrow B

;

等值式特点 :

A

和

B

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

A

的地方都可以替换成

B

, 凡是出现

B

的地方都可以替换成

A

;

证明

p \to q

与

\lnot p \lor q

是等值式 ;

p p p	q q q	p → q p \to q p→q	¬ p ∨ q \lnot p \lor q ¬p∨q	( p → q ) ↔ ( ¬ p ∨ q ) (p \to q) \leftrightarrow (\lnot p \lor q) (p→q)↔(¬p∨q)
0 0 0	0 0 0	1 1 1	1 1 1	1 1 1
0 0 0	1 1 1	1 1 1	1 1 1	1 1 1
1 1 1	0 0 0	0 0 0	0 0 0	1 1 1
1 1 1	1 1 1	1 1 1	1 1 1	1 1 1

p

q

p \to q

\lnot p \lor q

(p \to q) \leftrightarrow (\lnot p \lor q)

0

1

0

1

0

1

写出两个命题公式的真值表 , 从而计算

(p \to q) \leftrightarrow (\lnot p \lor q)

的真值表 , 计算完成后发现其是永真式 , 根据定义 , 这两个命题公式是等价的 ,

(p \to q) \Leftrightarrow (\lnot p \lor q)

;

三、基本等值式

基本运算规律 :

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

四、基本运算

基本运算 :

等价等值式 : 等价联结词

\leftrightarrow

不是必要的 , 使用

\to , \lor

两个联结词可以替换等价联结词 ;

蕴含等值式 : 蕴含联结词

\to

不是必要的 , 使用

\lnot , \lor

两个联结词可以替换蕴含联结词 ;

德摩根律 :

有了与 (

\land

) 非 (

\lnot

) , 就可以表示或 (

\lor

)

有了或 (

\lor

) 非 (

\lnot

) , 就可以表示与 (

\land

)

因此得出结论 , 与非或者或非 ( 二选一 ) , 可以表示所有的命题 ;

五、等值演算

证明

p \to ( q \to r )

与

(p \land q) \to r

是等价的 ;

证明上述两个命题是等价的 , 有两种方法 :

一个是列出真值表
另外一个就是进行等值演算

p \to ( q \to r )

使用蕴含等值式 , 进行置换 : 将

q \to r

置换为

\lnot q \lor r

\Leftrightarrow p \to ( \lnot q \lor r )

继续使用蕴含等值式 , 将外层的蕴含符号置换 :

\Leftrightarrow \lnot p \lor ( \lnot q \lor r )

使用结合律 , 将

p, q

结合在一起 :

\Leftrightarrow ( \lnot p \lor \lnot q ) \lor r

使用德摩根律 , 将

\lnot

提取到外面 :

\Leftrightarrow \lnot ( p \land q ) \lor r

使用蕴含等值式 , 进行置换 ;

\Leftrightarrow (p \land q) \to r

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

原理

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

原理

登录后参与评论

0 条评论

热度