离散数学学习笔记-个人总结(4)

2019-08-29 20:42

[解题过程]

在该语句中出现表示逻辑关系的连词“如果…,则…”,这样我们就很容易联想到条件联结词“示“如果…,则…”,但要注意的是,似乎P

”在语句中表

Q是“因果关系”,但是不一定总有因果关系,只要P,Q是命题,

那么PQ就是命题(即有真值),不管P,Q是否有无因果关系. 因此,设P:所有人今天都去参加活动, Q:明天的会议取消,

于是该语句可翻译成命题公式为: PQ.

[例4] 将语句“如果所有人今天都去参加活动,则明天的会议取消.”翻译成命题公式. [解题过程] P

Q表示的基本逻辑关系是,Q是P的必要条件,P是Q的充分条件,因此复合命题“只要P,就Q”,

Q的形式.

“P仅当Q”,“只有Q才P”等都可以符号化为P 因此可设P:我去旅游, Q:我有时间,

则语句“我去旅游,仅当我有时间.”翻译成命题公式为:PQ. [例5] 将语句“小王去旅游,小李也去旅游.”翻译成命题公式. [解题过程]

合取联结词“”在语句中相当于“并且”,“不但…而且…”,“既…又…”.但要注意“”与 “并且”等是有区别的,“并且”等要考虑语义,而“合取”只考虑命题之间的关系以及复合命题的取值情况,不考虑语义. 因此,可设P:小王去旅游, Q:小李去旅游,

则语句“小王去旅游,小李也去旅游.”翻译成命题公式为:PQ.

一般将命题的合式公式简称为命题公式.要理解合式公式的递归定义: (1)单个命题变元本身是一个合式公式. (2)若A是合式公式,则┐A是合式公式.

(3)若A与B是合式公式,则(A∧B),(A∨B),(A→B)与(AB)是合式公式. (4)当且仅当能够有限次应用(1)、(2)、(3)所得到的包含命题变元,联结词和括号的符号串是合式公式.

显然,如果对一个命题公式中的命题变元不给以真值指派,则命题公式无真值可言.如果对命题公式中的每个命题变元都赋以真值(1或0),则命题公式就变成了一个有真值的命题,并可求出其真值.

对于特殊的命题公式(永真式和永假式),对命题公式中的命题变元不给以真值指派,利用常用的等价公式也可以求出其真值(永真式为1,永假式为0).

对命题公式中的所有命题变元指派各种可能的真值组合,就可确定这个命题公式对应的取值,将命题变元的所有真值组合及命题公式对应的取值汇列成表,就得到命题公式的真值表.

如果一个命题公式有n个命题变元,那么命题变元的真值指派就可能出现种不同的组合.在真值表中是包含了命题变元的所有真值指派.例如,如果一个命题公式有3个命题变元,那么命题变元的真值指派就有8种不同的组合,作其真值表就是将这8种真值组合及命题公式对应的真值汇列成表.

要非常熟练地掌握命题公式的真值表作法,因为利用真值表可以判定命题公式类型,验证等价公式和蕴含式,求命题公式的主析取(合取)范式,在推理理论中判别有效结论. [例1] 命题公式的真值是_______ [解题过程]

依次利用蕴含等价式、结合律和零律,可将该命题公式化为:

因此该公式的真值是1。

对于命题的判断,存在着多种方法,也容易混淆,那我们来仔细分析一下他们的区分方法:

在各种真值指派下均为真的命题公式,称为重言式或永真式;在各种真值指派下均为假的命题公式,称为矛盾式或永假式;不是矛盾式的命题公式,称为可满足式。 判定命题公式类型的方法:

(1) 真值表法:任给命题公式,列出其真值表,若真值表的最后一列全为1,则该公式为永真式;若真值表的最后一列全为0,则该公式是永假式;若真值表的最后一列既非全1,又非全0,则该公式是可满足式。

(2) 等值演算法:利用常用的等价公式,对给定公式进行等值推导,若该公式的真值为1,则该公式为永真式;若该公式的真值为0,则该公式为永假式。既非永真,也非永假,则为非永真的可满足式。 那么在考试中是怎样考的呢?我们来看2道历年真题: [例1] 判断说明题(判断下列各题正误,并说明理由)

为永真

式. (2008年 7月试卷第14题) [答案] 正确. [分析]

因为联结词运算的优先次序为:

和否定律,对给定公式进行等值推导如下:

,再利用等价公式中的蕴含等价式,吸收律

因此该公式是永真式。

以上是利用等值演算法判断公式的类型,也可利用如下真值表法。

由真值表可见该公式在任意真值指派下的真值都是1,因此该公式是永真式。 [例2] 下列公式 ( )为重言式.

[答案] C [分析]

选A.错误. 因为利用蕴含等价式,可将词的定义可知选B.错误.

为矛盾式。

化为

,依据等价联结

因为利用蕴含等价式、分配律和结合律,可将化为

而用分配律和否定律得

依据等价联结词的定义可知选C.正确.

为可满足式。

因为利用蕴含等价式可将化为

。再依据等价联结词的定义可知该式为重言式。

,再利用结合律得

选D.错误. 因为利用分配律可将

依据等价联结词的定义可知

化为

为可满足式。

等价公式:给定两个命题公式A与B,设P1,P2,…,Pn为所有出现于A与B中的原子变元,若给P1,P2,…,Pn任一组真值指派,A与B的真值均相同,则称公式A与B是等价的或逻辑相等,记作,此公式可称为等价公式。

真值表法(验证公式等价):将两个命题公式的真值表列出,在所有的真值指派下,两个公式的真值都对应相同,则说明两个公式等价,否则,就不等价。

等值演算法(证明公式等价):利用教材182页的14个基本等价式对给定公式进行等值演算,可以证明命题公式等价。

那么在考试中是怎样考的呢?我们来看2道历年真题: [例1] 下列等价公式成立的为( ).

[答案] B [分析]

选A.错误.

因为依据德·摩根律, ,所以选B.正确.

因为依次利用蕴含等价式、分配律和蕴含等价式可得,

不等价 。

选C.错误.

其真值不等于1。

因为依次利用蕴含等价式、结合律、否定律和零律可得,

选D.错误.

因为依次利用分配律、否定律和同一律可得,

显然与Q不等价。

[例2] 下列公式成立的为( )。

[答案]D [分析]

选A.错误. 因为依据德·摩根律, 选B.错误.

(2010年 1月试卷第5题)

因为利用蕴含等价式可得,选C.错误.

因为 是一个蕴含式,依据蕴含的定义,该蕴含式成立只需证明蕴含等价式、分配律、否定律和同一律,

为重言式即可。依次利用

显然结果不是重言式,因此选D.正确.

不成立。

为真时,Q一定为真。

也可以利用直接证法来证明该蕴含式,思路是:证明

求范式和主范式,它们之间有什么区别呢,又应该怎么去求呢?我们一起来看一看:

求范式,包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点:其一是准确掌握范式定义;其二是巧妙使用基本等价式中的分配律、同一律和摩根律,结果的前一步适当使用幂等律.

范式的相关定义有:

合取范式:一个命题公式称为合取范式,当且仅当它具有形式: A1∧A2∧…∧An , (n1)

其中A1,A2,…,An均是由命题变元或其否定所组成的析取式. 析取范式:一个命题公式称为析取范式,当且仅当它具有形式: A1∨A2∨…∨An , (n1)

其中A1,A2,…,An均是有命题变元或其否定所组成的合取式.

布尔合取、小项:n个命题变元的合取式,称为布尔合取或小项,其中每个变元与它的否定不能同时存在,但两者必须出现且仅出现一次. 一般n个命题变元共有个小项.

布尔析取、大项:n个命题变元的析取式,称为布尔析取或大项,其中每个变元与它的否定不能同时存在,但两者必须出现且仅出现一次. 一般n个命题变元共有个大项.

主析取范式:对于给定的命题公式,若有一个等价公式,它仅仅由小项的析取组成,则该等价式称为原式的主析取范式.

主合取范式:对于给定的命题变元,如果有一个等价公式,它仅仅由大项的合取组成,则该等价式称为原式的主合取范式. 求析取(合取)范式的步骤: ① 将公式中的联结词都化成

② 将否定联结词消去或移到各命题变元之前;

③ 利用分配律、结合律等,将公式化为析取(合取)范式. 求主析取范式(主合取范式)的方法:

真值表法:在命题公式的真值表中,真值为1的指派所对应的小项的析取,为此命题公式的主析取范式;在命题公式的真值表中,真值为0的指派所对应的大项的合取,为此命题公式的主合取范式.

等值演算法:利用等价公式,求命题公式A的主析取(合取)范式的步骤: ① 将公式A化为析取(合取)范式;

② 除去析取(合取)范式中永假(永真)的析取 (合取) 项,并将析取(合取)式中重复出现的合取项(析取项)和相同变元合并.

③ 对于不是小项(大项)的合取(析取)式,补入没有出现的命题变元,即通过合取(析取)添加

式,然后利用分配律展开公式.

一般地,若命题公式A的主析取范式为则A的主合取范式为

由此可见,命题公式A的主析取范式的小项个数与主合取范式的大项个数之和等于 [例1]求

的析取范式、合取范式、主析取范式、主合取范式.

(2008年7月试卷第

17题) [解题过程]

依据求析取(合取)范式的步骤可得,

(析取范式、合取范式、主合取范式)

因此该公式的主析取范式对应的小项为: 故该公式的主析取范式为:

此外,我们也可利用真值表法求该命题公式的主析取范式和主合取范式. P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 PQR 1 1 1 1 0 1 1 1 小项 ┐P∧┐Q∧┐R ┐P∧┐Q∧R ┐P∧Q∧┐R ┐P∧Q∧R P∧┐Q∧R P∧Q∧┐R P∧Q∧R 大项 ┐P∨Q∨R

表中所有小项的析取就是公式的主析取范式,所有大项的合取就是公式的主合取范式,从真值表中可以看出所得结果与用上述等值演算法所得结果相同.

[例2] 命题公式(P∨Q)→R的析取范式是 ( )

(2008年9月试卷第3题)

[答案]D [分析]

依据求析取范式的步骤可得, 这就是命题公式(P∨Q)→R的析取范式,虽然命题公式的析取范式不唯一,但这个结论与选项D相同,故选择D。


离散数学学习笔记-个人总结(4).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:8年级下学期英语期中模拟考试试题

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: