左孝凌离散数学课件1.3命题公式和翻译-1.4真值表和等价公式.ppt

* 第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式 1. 真值表法 2. 等值演算法 1. 真值表法 例1. ┐(P?Q) ?(┐P?┐Q) 见真值表例题1. 例2. 证明: P?Q ?(P→Q)?(Q→P) P Q P?Q Q→P P→Q (P→Q)?(Q→P) 0 0 0 1 1 0 1 1 证明公式等价的方法： * 第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式 1. 真值表法 2. 等值演算法 1. 真值表法 例1. ┐(P?Q) ?(┐P?┐Q) 见真值表例题1. 例2. 证明: P?Q ?(P→Q)?(Q→P) P Q P?Q Q→P P→Q (P→Q)?(Q→P) 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 所以： P?Q ?(P→Q)?(Q→P) ?(P∧Q)∨(┐P∧┐Q) 试用等值演算方法证明 另外， P?Q ? (┐P∨Q) ∧(┐Q ∨ P) * 第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式 2. 等值演算法(Equivalent Caculation)（利用P15表1-4.8) 重要的等价式(补充): 11. 蕴涵等值式: P?Q ?┐P?Q ? Q?┐P ? ┐Q ? ┐P（假言易位） 12. 等价等值式: P?Q ?(P→Q)?(Q→P) ? (┐P∨Q) ∧(┐Q ∨ P) ?(P∧Q)∨(┐P∧┐Q) 13. 假言易位: P?Q ? ┐Q ? ┐P 14. 等价否定等值式: P?Q ?┐P?┐Q 15. 归谬论: (P?Q ) ?( P? ┐Q)? ┐P 对合律 ┐┐P ? P 1 幂等律 P∨P ? P，P∧P ? P 2 结合律 (P∨Q）∨R ? P∨（Q∨R） (P∧Q）∧R ? P∧（Q∧R） 3 交换律 P∨Q ? Q∨P P∧Q ? Q∧P 4 分配律 P∨（Q∧R） ? （P∨Q）∧（P∨R） P∧（Q∨R） ? （P∧Q）∨（P∧R） 5 吸收律 P∨（P∧Q） ? P P∧（P∨Q） ? P 6 德摩根律 ┐(P∨Q) ? ┐P∧┐Q ┐(P∧Q) ? ┐P∨┐Q 7 同一律 P∨F ? P，P∧T ? P 8 零律 P∨T ? T，P∧F ? F 9 否定律 P∨┐P ? T，P∧┐P ? F 10 表1-4.8命题定律 任何数与0相或还是任何数 任何数与1相与为1 任何数与1相与还是任何数 与0相与为0 例题6 验证吸收律 P∨（P∧Q）? P P∧（P∨Q） ? P 证明 列出真值表 表1-4.9 P Q P∧Q P∨（P∧Q） P∨Q P∧（P∨Q） T T T T T T T F F T T T F T F F T F F F F F F F 由表1-4.9可知吸收律成立。 练习 18页（4） * 第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式 等值演算中使用的一条重要规则：置换规则。 定义1.4.4 子公式：如果X是wff A的一部分,且X本身也是wff，则称X是A的子公式。 例如, P?(P?Q)为Q? (P?(P?Q))的子公式。 定理1.4.1 置换定理：设X是wff A的子公式，若X?Y，则若将A中的X用Y来置换，所得公式B与A等价，即A?B。 定义1.4.5 等值演算：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算. * 第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式 例1： 证明 Q→（P?（P?Q））?Q→P 证: Q→（P?（P?Q））?Q→P P(吸收律) 例2： 证明 （P?┐Q）?Q ?P?Q 证： (P?┐Q)?Q?(P?Q)?(┐Q?Q)?(P?Q)?T?P?Q 例3：证明（P→Q）→（Q?R）