文章目录

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

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

一、等值演算

等值演算 :

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

二、等值式

等值式概念 :

A

,

B

A , B

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

A

↔

B

A \leftrightarrow B

A↔B 是永真式 , 那么

A

,

B

A,B

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

A

⇔

B

A \Leftrightarrow B

A⇔B ;

等值式特点 :

A

A

A 和

B

B

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

A

A

A 的地方都可以替换成

B

B

B , 凡是出现

B

B

B 的地方都可以替换成

A

A

A ;

证明

p

→

q

p \to q

p→q 与

¬

p

∨

q

\lnot p \lor q

¬p∨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

∨

q

)

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

(p→q)↔(¬p∨q) 的真值表 , 计算完成后发现其是 永真式 , 根据定义 , 这两个命题公式是等价的 ,

(

p

→

q

)

⇔

(

¬

p

∨

q

)

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

(p→q)⇔(¬p∨q) ;

三、基本等值式

基本运算规律 :

1. 幂等律 :

A

⇔

A

∨

A

A \Leftrightarrow A \lor A

A⇔A∨A ,

A

⇔

A

∧

A

A \Leftrightarrow A \land A

A⇔A∧A2. 交换律 :

A

∨

B

⇔

B

∨

A

A \lor B \Leftrightarrow B \lor A

A∨B⇔B∨A ,

A

∧

B

⇔

B

∧

A

A \land B \Leftrightarrow B \land A

A∧B⇔B∧A3. 结合律 :

(

A

∨

B

)

∨

C

⇔

A

∨

(

B

∨

C

)

(A \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∧B)∧C⇔A∧(B∧C)4. 分配律 :

A

∨

(

B

∧

C

)

⇔

(

A

∨

B

)

∧

(

A

∨

C

)

A \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∧(B∨C)⇔(A∧B)∨(A∧C)

新运算规律 :

5. 德摩根律 :

¬

(

A

∨

B

)

⇔

¬

A

∧

¬

B

\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

¬(A∧B)⇔¬A∨¬B

有了 与 (

∧

\land

∧ ) 非 (

¬

\lnot

¬ ) , 就可以表示 或 (

∨

\lor

∨ )有了 或 (

∨

\lor

∨ ) 非 (

¬

\lnot

¬ ) , 就可以表示 与 (

∧

\land

∧ ) 6. 吸收率 :

前者将后者吸收了 :

A

∨

(

A

∧

B

)

⇔

A

A \lor ( A \land B ) \Leftrightarrow A

A∨(A∧B)⇔A后者将前者吸收了 :

A

∧

(

A

∨

B

)

⇔

A

A \land ( A \lor B ) \Leftrightarrow A

A∧(A∨B)⇔A ;

0

,

1

0 , 1

0,1 相关的运算律 :

7. 零律 :

A

∨

1

⇔

1

A \lor 1 \Leftrightarrow 1

A∨1⇔1 ,

A

∧

0

⇔

0

A \land 0 \Leftrightarrow 0

A∧0⇔0

1

1

1 是或运算的 零元 ,

0

0

0 是与运算的 零元 ;与 零元 进行运算结果是 零元 ; 8. 同一律 :

A

∨

0

⇔

A

A \lor 0 \Leftrightarrow A

A∨0⇔A ,

A

∧

1

⇔

A

A \land 1 \Leftrightarrow A

A∧1⇔A

0

0

0 是或运算的 单位元 ,

1

1

1 是 与运算的 单位元与 单位元 进行运算结果是其 本身 9. 排中律 :

A

∨

¬

A

⇔

1

A \lor \lnot A \Leftrightarrow 1

A∨¬A⇔110. 矛盾律 :

A

∧

¬

A

⇔

0

A \land \lnot A \Leftrightarrow 0

A∧¬A⇔0

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

∧

,

∨

\land , \lor

∧,∨ 互换 , 同时

0

,

1

0 ,1

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

等价蕴含运算规律 :

11. 双重否定率 :

¬

¬

A

⇔

A

\lnot \lnot A \Leftrightarrow A

¬¬A⇔A12. 蕴涵等值式 :

A

→

B

⇔

¬

A

∨

B

A \to B \Leftrightarrow \lnot A \lor B

A→B⇔¬A∨B

替换蕴含联结词 : 蕴含联结词

→

\to

→ 不是必要的 , 使用

¬

,

∨

\lnot , \lor

¬,∨ 两个联结词可以替换 蕴含联结词 ; 13. 等价等值式 :

A

↔

B

⇔

(

A

→

B

)

∨

(

B

→

A

)

A \leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )

A↔B⇔(A→B)∨(B→A)

双箭头 ( 等价联结词 ) 可以理解成重分必要条件

A

→

B

A \to B

A→B ( 蕴含联结词 ) 理解成

A

A

A 是

B

B

B 的充分条件 ,

B

B

B 是

A

A

A 的必要条件

B

→

A

B \to A

B→A ( 蕴含联结词 ) 理解成

B

B

B 是

A

A

A 的充分条件 ,

A

A

A 是

B

B

B 的必要条件替换等价联结词 : 等价联结词

↔

\leftrightarrow

↔ 不是必要的 , 使用

→

,

∨

\to , \lor

→,∨ 两个联结词可以替换 等价联结词 ; 14. 等价否定等值式 :

A

↔

B

⇔

¬

A

↔

¬

B

A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B

A↔B⇔¬A↔¬B15. 假言易位 ( 逆否命题 ) :

A

→

B

⇔

¬

B

→

¬

A

A \to B \Leftrightarrow \lnot B \to \lnot A

A→B⇔¬B→¬A

A

A

A 称为 前件 ,

B

B

B 称为 后件 ( 结论 ) ; 16. 归谬论 ( 反证法 ) :

(

A

→

B

)

∧

(

A

→

¬

B

)

⇔

¬

A

( A \to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A

(A→B)∧(A→¬B)⇔¬A

这是反证法的原理 , 由

A

A

A 推导出

B

B

B 和

¬

B

\lnot B

¬B ,

B

B

B 和

¬

B

\lnot B

¬B 是矛盾的 , 则

A

A

A 是错的 ,

¬

A

\lnot A

¬A 是对的 ;

四、基本运算

基本运算 :

等价等值式 : 等价联结词

↔

\leftrightarrow

↔ 不是必要的 , 使用

→

,

∨

\to , \lor

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

蕴含等值式 : 蕴含联结词

→

\to

→ 不是必要的 , 使用

¬

,

∨

\lnot , \lor

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

德摩根律 :

有了 与 (

∧

\land

∧ ) 非 (

¬

\lnot

¬ ) , 就可以表示 或 (

∨

\lor

∨ )有了 或 (

∨

\lor

∨ ) 非 (

¬

\lnot

¬ ) , 就可以表示 与 (

∧

\land

∧ )

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

五、等值演算

证明

p

→

(

q

→

r

)

p \to ( q \to r )

p→(q→r) 与

(

p

∧

q

)

→

r

(p \land q) \to r

(p∧q)→r 是等价的 ;

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

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

p

→

(

q

→

r

)

p \to ( q \to r )

p→(q→r)

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

q

→

r

q \to r

q→r 置换为

¬

q

∨

r

\lnot q \lor r

¬q∨r

⇔

p

→

(

¬

q

∨

r

)

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

⇔p→(¬q∨r)

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

⇔

¬

p

∨

(

¬

q

∨

r

)

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

⇔¬p∨(¬q∨r)

使用 结合律 , 将

p

,

q

p, q

p,q 结合在一起 :

⇔

(

¬

p

∨

¬

q

)

∨

r

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

⇔(¬p∨¬q)∨r

使用 德摩根律 , 将

¬

\lnot

¬ 提取到外面 :

⇔

¬

(

p

∧

q

)

∨

r

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

⇔¬(p∧q)∨r

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

⇔

(

p

∧

q

)

→

r

\Leftrightarrow (p \land q) \to r

⇔(p∧q)→r