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

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

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

3、5个，见书P16（熟记）第6页，共21页。常用的重要等值公式表：1、A A双 重 否 定 律2、AA A3、AA A等幂律4、A BB A5、A B B A交换律第7页，共21页。6、(A B)C7、(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、AB A B 蕴 涵 等 值 式

4、*假言易位等 价 否 定 等 值 式归 谬 论 *21、AB(AB)(BA)等价等值式22、AB B A23、AB 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页。n判断两个公式是否等值：n判断A B是否为重言式n等值演算

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

6、4页，共21页。利用等值演算证明下列等值公式(2)P(P Q)(P Q)解题思想解题思想可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。(1)P(QR)(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(QR)(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页。