离散数学与 命题逻辑 .ppt

离散数学命题逻辑2.3命题公式间的关系;主要内容：;一、命题公式的蕴含关系 定义 设A，B是两个公式，若公式A?B是重言式，即A?B?1，则称公式A蕴含公式B，记作A?B。称“A?B”为蕴含式。 ; A?B是偏序关系;传递性的证明： 设A?B，B?C， ;基本的蕴含式 ;编号;二 、蕴含式的判别 判定“A ? B”是否成立的问题可转化为判定A ? B是否为重言式，有下述判定方法：; 公式F对任意的一组真值指派取值均为1，故F是重言式。; ??????????2.?? 等值演算方法 例5 证明 I11：P∧（P?Q）? Q ; ???????????3.? 假定前件A真 假定前件A为真，检查在此情况下，其后件B是否也为真。 ;?? ?4、 假定后件B假 假定后件B为假，检查在此情况下，其前件A是否也为假. ;二、命题公式的等值关系? 定义 设A和B是两个命题公式, P1, P2, …, Pn 是所有出现于A和B中的命题变元，如果对于P1, P2, …, Pn 的任一组真值指派，A和B的真值都相同,则称公式A和B等值，记为A ? B,称 A?B为等值式。;? （2）???可以验证等值关系是等价关系。 即自反性：对任意公式A，有A?A。 对称性：对任意公式A，B，若A?B，则B?A。 可传递性：对任意公式A、B、C，若A?B，B?C，则A?C。 ;二、基本的等值式 设P、Q、R是命题变元，下表中列出了24个最基本的等值式:;编号 ;三、等值式的判别 有两种方法：真值表方法，命题演算方法 1、真值表方法;例2 用真值表方法证明E11：P?Q??P?Q; 例3 用真值表方法判断P?Q??P??Q是否成立.; (1) 代入规则 代入规则 对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。;(2) 置 换规则 定义 设C是命题公式A的一部分(即C是公式A中连续的几个符号)，且C本身也是一个命题公式，则称C为公式A的子公式。 ;*;*;*;*;*;(3)? 等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。 ; 例3 证明下列命题公式的等值关系 (P ? Q ) ? (? P ? ( ? P ? Q ) ) ? ?P ? Q;例4 判别下列公式的类型。 （1） Q∧?(?P?(?P∧Q)) （2）(P?Q)∧?P;练习 2-3 　1．判断下列等值式是否成立 （1）(P?Q)∧(R?Q)?(P∨R)?Q （2）?(P?Q)?(P∧?Q)∨(?P∧Q);2．判定蕴含式P?(Q?R)?(P?Q)?(P?R)是否成立;小结：