文章目录
一、等值演算
二、等值式
三、基本等值式
四、基本运算
五、等值演算
基于上一篇博客 【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 ) ;
一、等值演算
等值演算 :
等值式
基本等值式
等值演算置换规则
二、等值式
等值式概念 : A , B A , BA,B 是两个命题公式 , 如果 A ↔ B A \leftrightarrow BA↔B 是永真式 , 那么 A , B A,BA,B 两个命题公式是等值的 , 记做 A ⇔ B A \Leftrightarrow BA⇔B ;
等值式特点 : A AA 和 B BB 两个命题公式 , 可以 互相代替 , 凡是出现 A AA 的地方都可以替换成 B BB , 凡是出现 B BB 的地方都可以替换成 A AA ;
证明 p → q p \to qp→q 与 ¬ p ∨ q \lnot p \lor q¬p∨q 是等值式 ;
p pp q qq p → q p \to qp→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 00 0 00 1 11 1 11 1 11
0 00 1 11 1 11 1 11 1 11
1 11 0 00 0 00 0 00 1 11
1 11 1 11 1 11 1 11 1 11
写出两个命题公式的真值表 , 从而 计算 ( 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 AA⇔A∨A , A ⇔ A ∧ A A \Leftrightarrow A \land AA⇔A∧A
2. 交换律 : A ∨ B ⇔ B ∨ A A \lor B \Leftrightarrow B \lor AA∨B⇔B∨A , A ∧ B ⇔ B ∧ A A \land B \Leftrightarrow B \land AA∧B⇔B∧A
3. 结合律 : ( 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 AA∨(A∧B)⇔A
后者将前者吸收了 : A ∧ ( A ∨ B ) ⇔ A A \land ( A \lor B ) \Leftrightarrow AA∧(A∨B)⇔A ;
0 , 1 0 , 10,1 相关的运算律 :
7. 零律 : A ∨ 1 ⇔ 1 A \lor 1 \Leftrightarrow 1A∨1⇔1 , A ∧ 0 ⇔ 0 A \land 0 \Leftrightarrow 0A∧0⇔0
1 11 是或运算的 零元 , 0 00 是与运算的 零元 ;
与 零元 进行运算结果是 零元 ;
8. 同一律 : A ∨ 0 ⇔ A A \lor 0 \Leftrightarrow AA∨0⇔A , A ∧ 1 ⇔ A A \land 1 \Leftrightarrow AA∧1⇔A
0 00 是或运算的 单位元 , 1 11 是 与运算的 单位元
与 单位元 进行运算结果是其 本身
9. 排中律 : A ∨ ¬ A ⇔ 1 A \lor \lnot A \Leftrightarrow 1A∨¬A⇔1
10. 矛盾律 : A ∧ ¬ A ⇔ 0 A \land \lnot A \Leftrightarrow 0A∧¬A⇔0
对偶原理适用于上述运算律 , 将两边的 ∧ , ∨ \land , \lor∧,∨ 互换 , 同时 0 , 1 0 ,10,1 互换 , 等价仍然成立 ;
等价蕴含运算规律 :
11. 双重否定率 : ¬ ¬ A ⇔ A \lnot \lnot A \Leftrightarrow A¬¬A⇔A
12. 蕴涵等值式 : A → B ⇔ ¬ A ∨ B A \to B \Leftrightarrow \lnot A \lor BA→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 BA→B ( 蕴含联结词 ) 理解成 A AA 是 B BB 的充分条件 , B BB 是 A AA 的必要条件
B → A B \to AB→A ( 蕴含联结词 ) 理解成 B BB 是 A AA 的充分条件 , A AA 是 B BB 的必要条件
替换等价联结词 : 等价联结词 ↔ \leftrightarrow↔ 不是必要的 , 使用 → , ∨ \to , \lor→,∨ 两个联结词可以替换 等价联结词 ;
14. 等价否定等值式 : A ↔ B ⇔ ¬ A ↔ ¬ B A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot BA↔B⇔¬A↔¬B
15. 假言易位 ( 逆否命题 ) : A → B ⇔ ¬ B → ¬ A A \to B \Leftrightarrow \lnot B \to \lnot AA→B⇔¬B→¬A
A AA 称为 前件 , B BB 称为 后件 ( 结论 ) ;
16. 归谬论 ( 反证法 ) : ( A → B ) ∧ ( A → ¬ B ) ⇔ ¬ A ( A \to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A(A→B)∧(A→¬B)⇔¬A
这是反证法的原理 , 由 A AA 推导出 B BB 和 ¬ B \lnot B¬B , B BB 和 ¬ B \lnot B¬B 是矛盾的 , 则 A AA 是错的 , ¬ 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 rq→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, qp,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
