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

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

一、等值演算

等值演算 :

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

二、等值式

等值式概念 : 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∧A
• 2. 交换律 : 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∧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 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⇔1
• 10. 矛盾律 : 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⇔A
• 12. 蕴涵等值式 : 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↔¬B
• 15. 假言易位 ( 逆否命题 ) : 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