离散数学等值演算.ppt

Discrete Mathematics * 1.3 等值演算 等值式 基本等值式 等值演算 置换规则 * 等值式 p q p?q ?p∨q 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 观察下面的等值表： * 等值式 定义 若等价式 A?B 是重言式，则称A与B 等值，记作A?B，并称A?B是等值式. 注意: 符号?不是联结词，不能将它与 “?” 或 “ = ” 混淆 任意含 2 个命题变项的公式，可以产生 ？ 个不同的取值。 * 例1.10 用真值表判断下面两个公式是否等值。 p q ? p q?p ?(q?p) ? p ?q ?(q?p) ? ? p?q 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 (1) ? (q?p) 与 ? p ? q 0 1 0 0 1 1 1 1 * (2) p?(q?r) 与 (p?q) ?r p q r q?r p?q p?(q?r) (p?q) ?r 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 * (3) (p?q)?r 与 (p?q) ?r p q r p?q p?q (p?q)?r (p?q) ?r 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 * 基本等值式 1、双重否定律 : ??A ? A 2、等幂律： A?A ? A, A?A ? A 3、交换律: A?B ? B?A, A?B ? B?A 4、结合律: (A?B)?C ? A?(B?C) (A?B)?C ? A?(B?C) 5、分配律: A?(B?C) ? (A?B)?(A?C) A?(B?C) ? (A?B)?(A?C) * 6、德·摩根律: ?(A?B) ? ?A??B ?(A?B) ? ?A??B 7、吸收律: A?(A?B) ? A A?(A?B) ? A 8、零律: A?1 ? 1, A?0 ? 0 9、同一律: A?0 ? A, A?1 ? A 10、排中律: A??A ? 1 11、矛盾律: A??A ? 0 * 12、蕴涵等值式: A?B ? ?A?B 13、等价等值式: A?B ? (A?B)?(B?A) 14、假言易位: A?B ? ?B??A 15、等价否定等值式: A?B ? ?A??B 16、归谬论: (A?B)?(A??B) ? ?A A, B, C代表任意的命题公式，牢记这些等值式是继续学习的基础. 注意: * 等值演算与置换规则 等值演算: 由已知的等值式推演出新的等值式的过程。 置换规则：设? (A)是含公式A的命题公式， 若B?A，则? (B)?? (A) . 等值演算的基础： (1)基本的等值式 (2)置换规则 * 应用举例——证明两个公式等值 例1.12 证明 p?(q?r) ? (p?q)?r . 证 p?(q?r) ??p?(?q?r) （蕴涵等值式，置换规则） ?(?p??q)?r （结合律，置换规则） ??(p?q)?r （德摩根律，置换规则） ?(p?q) ?r （蕴涵等值式，置换规则）? 说明: 也可以从右边开始演算（请做一遍）, 因为每一步