计算机数学基础上离散数学课件

1、1.2命题公式与赋值真值指派定义：命题公式与赋值，命题P含有n个命题变项P1，P2,Pn，给P1，P2,Pn各指定一个真值0或1，称为对P的一个赋值(真值指派). 若指定的一组值使P的值为1，则这组值为P的真指派；若使P的值为0，则称这组值称为P的假指派. 真值表：一个公式P在所有赋值下取值情况列成的表第1页，共21页。构造真值表的步骤(1) 将变元按一定顺序排出，再按从内到外的顺序列出公式的各个运算层次，将它们排在表头上；(2) 如有n个变元，则所有可能的赋值有2n组，每组可用n位的二进制数表示，按字典顺序每行排一组(3) 在表上由左到右填写相应的真值。第2页，共21页。1.2命题公式与赋值

2、构造命题公式的真值表例子：P12课堂练习：用真值表判定公式PQ与PQ是否等值 第3页，共21页。1.2命题公式与赋值命题公式的分类重言式或永真式矛盾式或永假式可满足式仅可满足式第4页，共21页。重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均为假。可 满 足 式：命题公式A至少存在一组赋值为成真赋值。仅可满足式：既不是矛盾式也不是重言式若A在各种赋值下取值恒为真, 则A为重言式。设A是一个命题公式，命题公式的类型第5页，共21页。1.3 命题定理基本等值式：也称为命题定律或命题定理，一共16组25个，见书P16（熟记）第6页，共21页。常用的重要等值公式表：1、A A双重否定律2、

3、AAA3、AAA等幂律4、ABBA5、AB BA交换律第7页，共21页。6、(AB) C7、(AB)C 结合律8、A(B C ) 9、A(B C ) 分配律10、 (AB) 11、 (AB) 德 摩根律A(BC)A(BC)(AB) ( AC)(AB) (AC) A B A B第8页，共21页。12、 A(AB) A13、 A(AB) A吸收律 *14、 A1 115、 A0 0零律16、 A0 A17、 A1 A同一律第9页，共21页。19、 A A 0矛盾律20、 AB AB 蕴涵等值式 *假言易位等价否定等值式归谬论 *21、 AB(AB)(BA )等价等值式22、 ABB A23、 AB

4、B A24、 (AB)(AB ) A18、 A A 1排中律第10页，共21页。以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。利用24个基本等值式，不用真值表法也可以推演很多的等值式来。第11页，共21页。置换定理：(A)是含命题公式A的命题 公式, (B)是用B置换了(A)中的A之后得到的命题公式。如果AB, 则(A) (B) 第12页，共21页。判断两个公式是否等值：判断A B是否为重言式等值演算法:可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。第13页，共21页。1.3 命题定理判定

5、命题公式类型的方法：真值表法:对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式. 推导法: 利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.第14页，共21页。例 利用等值演算证明下列等值公式(2) P(PQ)(P Q)解题思想可以从左或右的任一个公式开始演算；演算

6、的每一步都要用置换定理。(1) P(QR)(PQ)R第15页，共21页。解：(1) P (Q R ) P (Q R ) P ( Q R) ( P Q ) R ( P Q ) R ( P Q ) R )蕴涵等值公式蕴涵等值公式结合律德 摩根律蕴涵等值公式(1) P(QR)(PQ)R第16页，共21页。解：(2) P P 1 P (Q Q) ( P Q ) (P Q)同一律排中律分配律(2) P(PQ)(P Q)第17页，共21页。例 判别下列公式的类型(1) Q ( PQ ) P )(2) ( P P ) (Q Q) R)(3) ( P Q ) P解题分析真值表法可以判别公式类型(重言、永假、可满足)，但等值演算的方法更简捷。第18页，共21页。解：(1) Q ( PQ ) P ) Q (Q P)分配律矛盾律同一律(1) Q ( PQ ) P ) Q ( Q P)德 摩根律结合律排中律 Q ( P P ) (Q P) Q ( 0 (Q P) 1 P (Q Q) P第19页，共21页。故(1)是重言式 1零律第20页，共21页。 1 0 0 0 0 1 0( ？)( ？)( ？)( ？)( ？)( ？)(