离散数学与-命题逻辑教学课程 .ppt

(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 ?(Q∧?Q)∧?P E1ノ,E2 ?0 E5ノ,E8ノ 所以Q∧?(?P?(?P∧Q))是矛盾式。 （2） (P?Q)∧?P ?(?P∨Q)∧?P E11 ? ?P E9ノ 于是该公式是可满足式。 三、命题公式的蕴含关系 定义1-11 设A，B是两个公式，若公式A?B是重言式，即A?B?1，则称公式A蕴含公式B，记作A?B。称“A?B”为蕴含式。 注意：符号“?”和 “?”的区别和联系与符号“?”与“?”的区别和联系类似。 “?”不是联结词， “A?B”不是公式，它表示公式A与B之间存在蕴含关系。 “?”是联系词，A?B是一个公式。 A?B当且仅当A?B是永真公式 。 A?B是偏序关系 即 自反性：A?A。 反对称：若A?B，B?A，则A?B。 传递性：若A?B，B?C，则 A?C。 反对称性的证明： 设A?B且B?A， 由定义7-11 A?B?1且B?A?1 于是A?