【文档说明】计算机数学基础上离散数学课件.ppt，共(21)页，572.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5407.html

以下为本文档部分文字说明：

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命题公式与赋值构造命题公式的真值表例子：P12课堂练习：用真值表判定公式PQ与PQ是否等值第3页，共21页。1.2命题公式与赋值命题公式的分类重言式或永真式矛盾式或永假式可满足式仅可满足式第4页，共21页。

重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均为假。可满足式：命题公式A至少存在一组赋值为成真赋值。仅可满足式：既不是矛盾式也不是重言式若A在各种赋值下取值恒为真,则A为重言式。设A是一个命题公式，命题公式的类型第5页，共21页。1.3命题定理基本等值式：也称为命题定律或

命题定理，一共16组25个，见书P16（熟记）第6页，共21页。常用的重要等值公式表：1、AA双重否定律2、AAA3、AAA等幂律4、ABBA5、ABBA交换律第7页，共21页。6、(AB)C7、(AB)C结合律8、A

(BC)9、A(BC)分配律10、(AB)11、(AB)德·摩根律A(BC)A(BC)(AB)(AC)(AB)(AC)ABAB第8页，共21页。12、A(AB)A13、A(AB)A吸收律*14、A1

115、A00零律16、A0A17、A1A同一律第9页，共21页。19、AA0矛盾律20、ABAB蕴涵等值式*假言易位等价否定等值式归谬论*21、AB(AB)(BA)等价等值式22、ABBA23、ABBA24、(AB)

(AB)A18、AA1排中律第10页，共21页。以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。利用24个基本等值式，不

用真值表法也可以推演很多的等值式来。第11页，共21页。置换定理：(A)是含命题公式A的命题公式,(B)是用B置换了(A)中的A之后得到的命题公式。如果AB,则(A)(B)第12页，共21页。判断

两个公式是否等值：判断AB是否为重言式等值演算法:可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。第13页，共21页。1.3命题定理判定命题公式类型的方法：真值表法:对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公

式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.推导法:利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、

否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.第14页，共21页。例利用等值演算证明下列等值公式(2)P(PQ)(PQ)解题思想可以从左或右的

任一个公式开始演算；演算的每一步都要用置换定理。(1)P(QR)(PQ)R第15页，共21页。解：(1)P(QR)¬P(QR)¬P(¬QR)(¬P¬Q)R¬(PQ)R(PQ)R)蕴涵等值公式蕴涵等值公式结合律德·摩

根律蕴涵等值公式(1)P(QR)(PQ)R第16页，共21页。解：(2)PP1P(Q¬Q)(PQ)(P¬Q)同一律排中律分配律(2)P(PQ)(PQ)第17页，共21页。例判别下列公式的类型(1)Q¬

((¬PQ)P)(2)(P¬P)((Q¬Q)R)(3)(PQ)¬P解题分析真值表法可以判别公式类型(重言、永假、可满足)，但等值演算的方法更简捷。第18页，共21页。解：(1)Q¬((¬

PQ)P)Q¬(QP)分配律矛盾律同一律(1)Q¬((¬PQ)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(？)(？)(？)(？)(？)(？)(3)类似(1),(2)可知：(PQ)¬P¬P(自己做做)(2)(P¬P)((Q¬Q)R)解：(2)(P¬P)((Q¬Q)R)1((Q

¬Q)R)1(0R)第21页，共21页。