文章目录

一、等值演算
二、等值式
三、基本等值式
四、基本运算
五、等值演算

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

一、等值演算

等值演算 :

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

二、等值式

等值式概念 :

A , B

$A, B$ 是两个命题公式 , 如果

↔

A \leftrightarrow B

$A \leftrightarrow B$ 是永真式 , 那么

A,B

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

⇔

A \Leftrightarrow B

$A \Leftrightarrow B$ ;

等值式特点 :

$A$ 和

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

$A$ 的地方都可以替换成

$B$ , 凡是出现

$B$ 的地方都可以替换成

$A$ ;

证明

p

→

q

p \to q

$p \to q$ 与

¬

p

∨

q

\lnot p \lor q

$\neg p \lor q$ 是等值式 ;

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

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

(

→

)

↔

(

∨

)

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

$(p \to q) \leftrightarrow (\neg p \lor q)$ 的真值表 , 计算完成后发现其是永真式 , 根据定义 , 这两个命题公式是等价的 ,

(

→

)

⇔

(

∨

)

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

$(p \to q) \Leftrightarrow (\neg p \lor q)$ ;

三、基本等值式

基本运算规律 :

1. 幂等律 : $\Leftrightarrow A \lor A A⇔A∨A , A ⇔ A ∧ A A \Leftrightarrow A \land A$
$A \Leftrightarrow A \land A$
2. 交换律 : $\lor B \Leftrightarrow B \lor A A∨B⇔B∨A , A ∧ B ⇔ B ∧ A A \land B \Leftrightarrow B \land A$
$A \land B \Leftrightarrow B \land A$
3. 结合律 : $\lor B ) \lor C \Leftrightarrow A \lor (B \lor C) (A∨B)∨C⇔A∨(B∨C) , ( A ∧ B ) ∧ C ⇔ A ∧ ( B ∧ C ) (A \land B ) \land C \Leftrightarrow A \land (B \land C)$
$(A \land B) \land C \Leftrightarrow A \land (B \land C)$
4. 分配律 : $\lor (B \land C) \Leftrightarrow ( A \lor B ) \land ( A \lor C ) A∨(B∧C)⇔(A∨B)∧(A∨C) , A ∧ ( B ∨ C ) ⇔ ( A ∧ B ) ∨ ( A ∧ C ) A \land (B \lor C) \Leftrightarrow ( A \land B ) \lor ( A \land 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 ¬(A∨B)⇔¬A∧¬B , ¬ ( A ∧ B ) ⇔ ¬ A ∨ ¬ B \lnot ( A \land B ) \Leftrightarrow \lnot A \lor \lnot B$
$\neg (A \land B) \Leftrightarrow \neg A \lor \neg B$
- 有了与 ( $\land ∧ ) 非 ( ¬ \lnot ¬ ) , 就可以表示或 ( ∨ \lor ∨ )$
- 有了或 ( $\lor ∨ ) 非 ( ¬ \lnot ¬ ) , 就可以表示与 ( ∧ \land ∧ )$
6. 吸收率 :
- 前者将后者吸收了 : $\lor ( A \land B ) \Leftrightarrow A$
  $A \lor (A \land B) \Leftrightarrow A$
- 后者将前者吸收了 : $\land ( A \lor B ) \Leftrightarrow A$
  $A \land (A \lor B) \Leftrightarrow A$ ;

0

,

1

0 , 1

$0, 1$ 相关的运算律 :

7. 零律 : $\lor 1 \Leftrightarrow 1 A∨1⇔1 , A ∧ 0 ⇔ 0 A \land 0 \Leftrightarrow 0$
$A \land 0 \Leftrightarrow 0$
- 与零元进行运算结果是零元 ;
8. 同一律 : $\lor 0 \Leftrightarrow A A∨0⇔A , A ∧ 1 ⇔ A A \land 1 \Leftrightarrow A$
$A \land 1 \Leftrightarrow A$
- 与单位元进行运算结果是其本身
9. 排中律 : $\lor \lnot A \Leftrightarrow 1$
$A \lor \neg A \Leftrightarrow 1$
10. 矛盾律 : $\land \lnot A \Leftrightarrow 0$
$A \land \neg A \Leftrightarrow 0$

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

∧

,

∨

\land , \lor

$\land, \lor$ 互换 , 同时

0

,

1

0 ,1

$0, 1$ 互换 , 等价仍然成立 ;

等价蕴含运算规律 :

11. 双重否定率 : $\lnot \lnot A \Leftrightarrow A$
$\neg \neg A \Leftrightarrow A$
12. 蕴涵等值式 : $\to B \Leftrightarrow \lnot A \lor B$
$A \to B \Leftrightarrow \neg A \lor B$
- 替换蕴含联结词 : 蕴含联结词 $\to → 不是必要的 , 使用 ¬ , ∨ \lnot , \lor ¬,∨ 两个联结词可以替换蕴含联结词 ;$
13. 等价等值式 : $\leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )$
$A \leftrightarrow B \Leftrightarrow (A \to B) \lor (B \to A)$
- 双箭头 ( 等价联结词 ) 可以理解成重分必要条件
- $\to B A→B ( 蕴含联结词 ) 理解成 A A A 是 B B B 的充分条件 , B B B 是 A A A 的必要条件$
- $\to A B→A ( 蕴含联结词 ) 理解成 B B B 是 A A A 的充分条件 , A A A 是 B B B 的必要条件$
- 替换等价联结词 : 等价联结词 $\leftrightarrow ↔ 不是必要的 , 使用 → , ∨ \to , \lor →,∨ 两个联结词可以替换等价联结词 ;$
14. 等价否定等值式 : $\leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B$
$A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$
15. 假言易位 ( 逆否命题 ) : $\to B \Leftrightarrow \lnot B \to \lnot A$
$A \to B \Leftrightarrow \neg B \to \neg A$
16. 归谬论 ( 反证法 ) : $\to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A$
$(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$
- 这是反证法的原理 , 由 $\lnot B ¬B , B B B 和 ¬ B \lnot B ¬B 是矛盾的 , 则 A A A 是错的 , ¬ A \lnot A ¬A 是对的 ;$

四、基本运算

基本运算 :

等价等值式 : 等价联结词

↔

\leftrightarrow

$\leftrightarrow$ 不是必要的 , 使用

→

∨

\to , \lor

$\to, \lor$ 两个联结词可以替换等价联结词 ;

蕴含等值式 : 蕴含联结词

→

\to

$\to$ 不是必要的 , 使用

∨

\lnot , \lor

$\neg, \lor$ 两个联结词可以替换蕴含联结词 ;

德摩根律 :

有了与 ( $\land ∧ ) 非 ( ¬ \lnot$
$\neg$ ) , 就可以表示或 (

∨

\lor

$\lor$ )
有了或 ( $\lor ∨ ) 非 ( ¬ \lnot$
$\neg$ ) , 就可以表示与 (

∧

\land

$\land$ )

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

五、等值演算

证明

p

→

(

q

→

r

)

p \to ( q \to r )

$p \to (q \to r)$ 与

(

p

∧

q

)

→

r

(p \land q) \to r

$(p \land q) \to r$ 是等价的 ;

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

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

→

(

→

)

p \to ( q \to r )

$p \to (q \to r)$

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

→

q \to r

$q \to r$ 置换为

∨

\lnot q \lor r

$\neg q \lor r$

⇔

→

(

∨

)

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

$\Leftrightarrow p \to (\neg q \lor r)$

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

⇔

∨

(

∨

)

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

$\Leftrightarrow \neg p \lor (\neg q \lor r)$

使用结合律 , 将

p, q

$p, q$ 结合在一起 :

⇔

(

∨

)

∨

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

$\Leftrightarrow (\neg p \lor \neg q) \lor r$

使用德摩根律 , 将

\lnot

$\neg$ 提取到外面 :

⇔

(

∧

)

∨

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

$\Leftrightarrow \neg (p \land q) \lor r$

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

⇔

(

∧

)

→

\Leftrightarrow (p \land q) \to r

$\Leftrightarrow (p \land q) \to r$

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