02命题逻辑等值演算.ppt

第2章命题逻辑等值演算离散数学中国地质大学本科生课程凌常拓焚会吉罐回弗裔歼棠誓留艘谣戊糠错锻骄巩抗云呐亩黎涕扁棵痘澡02命题逻辑等值演算02命题逻辑等值演算本章说明本章的主要内容等值式与基本的等值式等值演算与置换规则析取范式与合取范式、主析取范式与主合取范式联结词完备集(不讲)可满足性问题与消解法(不讲)?抽象地看,它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项,可能对A或B有哑元,若A与B有相同的真值表,则说明在2n个赋值的每个赋值下,A与B的真值都相同。于是等价式AB应为重言式。,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记作AB。说明定义中,A,B,都是元语言符号。A或B中可能有哑元出现。p→q(┐p∨q)∨(┐r∧r)r为左边公式中的哑元。用真值表可以验证两个公式是否等值。 ┐(p∨q)与┐p∧┐q解答说明在用真值表法判断AB是否为重言式时,真值表的最后一列可以省略。(1)p→(q→r)与(p∧q)→r(2)(p→q)→r与(p∧q)→ A┐┐ AA∨A, AA∧ A∨BB∨A, A∧BB∧(A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)         A∨(B∧C)(A∨B)∧(A∨C) (∨对∧的分配律) A∧(B∨C)(A∧B)∨(A∧C) (∧对∨的分配律)·摩根律      ┐(A∨B)┐A∧┐B ┐(A∧B)┐A∨┐         A∨(A∧B)A,A∧(A∨B)        A∨11,A∧0          A∨0A,A∧1         A∨┐A    A∧┐A     A→B┐A∨    AB(A→B)∧(B→A)       A→B┐B→┐      AB┐A┐       (A→B)∧(A→┐B)┐A月精裔皱乎幌嘻矩巧呛乙摄曝警睛西邵递条肄稳驱弃协枯及坟膛踢呕巾敬02命题逻辑等值演算02命题逻辑等值演算对偶原理一个逻辑等值式,如果只含有┐、∨、∧、0、1那么同时把∨和∧互换 把0和1互换得到的还是等值式。亿谆缉狸埠令阜蹲滞历见踌塔喝维尊掌垄尹岂恩垣肤千蹲桅吮悯挪冉选谤02命题逻辑等值演算02命题逻辑等值演算等值演算与置换规则各等值式都是用元语言符号书写的,其中A,B,C可以代表任意的公式,称这样的等值式为等值式模式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如,在蕴涵等值式A→B┐A∨B中,取A=p,B=q时,得等值式p→q┐p∨q取A=p∨q∨r,B=p∧q时,得等值式 (p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)这些具体的等值式都被称为原来的等值式模式的代入实例。由已知的等值式推演出另外一些等值式的过程为等值演算。置换规则设Φ(A)是含公式A的命题公式,Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式,若BA,则Φ(B)Φ(A)。仍雷轩末元摘滋粥霍湃驳耘永腔鲁喻架捎疡鹤廊幅棠努延恤荐悠散颂椒慑02命题逻辑等值演算02命题逻辑等值演算