离散数学左孝陵版第一章答案.ppt

例3 用真值表方法判断P?Q??P??Q是否成立. 解 令A=P?Q，B=?P??Q 构造A，B以及A?B的真值表 P Q ?P ?Q ?P??Q P?Q A?B 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 由于公式A?B所标记的列不全为1，A?B不是永真公式，因此A?B不成立。 1 0 1 1 0 0 1 1 1 (1) 代入规则 代入规则 对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。 2．等值演算方法 例如 F=（P?Q）?（?Q??P）是重言式，若 用公式A∧B代换命题变元P得公式 F1=（（A∧B）?Q）?（?Q??（A∧B））， F1仍是重言式。 注意：因为A ? B当且仅当A ? B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。 (2) 置 换规则 定义7-10 设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。 例如 设公式A=（?P∨Q）?（（P?Q）∨（R∧?S））。 则?P∨Q，P?Q，（P?Q）∨（R∧?S）等均是A的子公式， 但?P∨，P?和?Q等均不是A的子公式， 置换规则 设C是公式A的子公式，C?D。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则A?B。 (3)? 等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。 由代入规则知前述的基本等值式，不仅对任意的命题变元P，Q，R是成立的，而且当P，Q，R分别为命题公式时，这些等值式也成立 例2 证明命题公式的等值关系： （P?Q）∧（R?Q）?（P∨R）?Q； 证明 （P?Q）∧（R?Q） ?（? P∨Q）∧(? R∨Q) E11 ?（? P∧? R）∨Q E3ˊ( 分配律) ? ? (P∨R)∨Q E10(德.摩根定律) ? (P∨R) ? Q E11 所以（P?Q）∧（R?Q）?（P∨R）?Q 例3 证明下列命题公式的等值关系 (P ? Q ) ? (? P ? ( ? P ? Q ) ) ? ?P ? Q 证明 (P?Q)?( ?P?(?P?Q)) ? (P?Q)?( (?P? ? P ) ? Q ) E2(结合律) ? (P?Q)?( ?P?Q) E7(等幂律) ? (?P ? Q )? ( P?Q ) E1 (交换律) ? ? P?(Q?(P?Q)) E2(结合律) ? ?P?Q E?1，E9(交换律，吸收律) 例4 判别下列公式的类型。 （1） Q∧? (?P?（?P∧Q）) （2）（P?Q）∧?P 解（1） Q∧?（?P?（?P∧Q）） ?Q∧?（P∨（?P∧Q）） E11,E6 ?Q∧?（（P∨?P）∧（P∨Q）） E3ノ ?Q∧?（1∧（P∨Q）） E5 ?Q∧?（P∨Q） E4ノ ?Q∧?P∧?Q E10 ?