《计算机数学基础(1)—离散数学》学习辅导
发布人： 日期：2007-03-21 00:00浏览次数：4973点赞次数：1
湛江开大,米兰app入口站官网,湛江市财政职业技术学校,湛江市广播电视大学,湛江电大,中专教育,中职教育,成人教育,成人大专,成人本科，官网,教育部电子注册，国际学历绿卡。米兰app入口站官网（湛江市广播电视大学）办学三十年来...
《计算机数学基础(1)—离散数学》学习辅导
《计算机数学基础（1）—离散数学》是中央广播电视大学开放本科教育计算工程类计算机科学与技术专业教学中重要的核心基础课程，它是学习专业理论中不可少的数学工具。
通过本课程的学习，要使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。
本课程包括数理逻辑、集合论、图论和代数系统。这是一门理论性较强，应用性较广的课程。因此，通过本课程的学习，使学生：掌握离散数学的基本概念和基本原理，进一步提高抽象思维和逻辑推理的能力。
按照教学大纲，我们逐次分章进行辅导，供师生学习参考。
第1章 命题逻辑
一、教学基本要求
1. 理解命题概念，会判断语句是不是命题。
2. 了解六个联结词概念，掌握由它们构成的公式及真值表：①ØP(否定式); ②PÙQ(合取式);③PÚQ(析取式);④P®Q(蕴含式);⑤P«Q(等价式)；⑥P`VQ[不可兼或式(异或式)]。
熟练掌握求给定公式真值表的方法。
3. 理解公式、公式解释、永真式(重言式)、永假式(矛盾式)和可满足式等概念。
记住基本等值式，掌握用真值表法和等值演算法判别公式类型和公式等值变换的方法。
4. 理解析取(合取)范式概念，熟练掌握利用基本等值式或真值表将公式化为析取(合取)范式的方法。
5. 了解极小(大)项的概念，掌握求主析取(合取)范式的方法。
6. 了解有效结论(逻辑结果)的概念，掌握判断重言蕴含式(推理是否有效)的五种方法
(1) 真值表法；(2) 等值演算法(记住基本等值式)；(3) 主析取(合取)范式法；
(4) 直接证法：掌握P规则和T规则，及常用重言蕴含式、等值式。
(5) 间接证法(反证法)：掌握PC规则。
本章重点：命题与联结词，公式与解释，真值表，(主)析取(合取)范式，重言式的判定。
二、学习辅导
1.1 命题与联结词
命题是推理的基本要素。自然语言将命题表述为具有确定真假意义的陈述句。若该语句表述的意义符合事实，则称其为真命题。若该语句表述的意义不符合事实，则称其为假命题。我们用0或F表示假命题；用1或T表示真命题。判断一个句子是否为命题，应首先判断它是否为陈述句。再判断它是否有唯一的真值。可见命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义。
例如，考察下列语句
“雪是黑的”，“北京是中国的首都”是陈述句，都有确定的真假意义，是命题，前者为假命题；后者为真命题。
“21世纪时有人住在月球上”是陈述句，今后若干年，可以证明它要么是真，要么是假，故是命题。
“你是谁?” 不是命题，它是疑问句，不是陈述句；
“x+y<7”不是命题。它的真假意义不确定。如x=100，y=-84，则“x+y<7”为假；而x=－91，y=78，则“x+y<7”为真。
以上所举各陈述中都是简单陈述句，它们不能再分解成更简单的句子，这就是原子命题(简单命题)。本章不再进一步分析原子命题的内部结构，下一章讨论谓词逻辑时再分析它的内部结构。
由若干个原子命题通过联结词构成的命题就是复合命题。
我们讲了六个联结词。
1. “Ø”否定联结词，P是命题，ØP是P的否命题。是由联结词 Ø 和命题P组成的复合命题。
例如，P：猩猩是人。
ØP：猩猩不是人。
P：上海是中国最大的城市。
ØP：上海不是中国最大的城市。
P与ØP的真假是相互对立的，P为真，则ØP为假；反之P为假，则ØP为真。
2. “Ù”合取联结词，P，Q是命题，PÙQ是P，Q的合取式，是联结词Ù和命题P，Q组成的复合命题。“Ù”在语句中相当于“不但…而且…”，“既…又…”。PÙQ取值1，当且仅当P，Q均取1；PÙQ取值为0，只要P，Q之一取0。
例如，丘玉学习很好，而且非常努力。就可以符号化为：P：“丘玉学习很好”Q：“丘玉学习非常努力”，记作PÙQ。
3. “Ú”析取联结词，“`Ú”不可兼析取(异或)联结词，P，Q是命题，PÚQ是P，Q的析取式，是联结词Ú和命题P，Q组成的复合命题。P`ÚQ是P，Q的不可兼析取式，是联结词`Ú和命题P，Q组成的复合命题。联结词“Ú”或“`Ú”在一个语句中都表示“或”的含义，可以表示相容或，也可以表示排斥或。`Ú表示不相容的或。即“P`ÚQ”«“ØPÙQÚPÙØQ”。
如“赵志宏学习俄语或英语”，是相容或，记P：“赵志宏学习俄语”，Q：“赵志宏学习英语”，命题符号化为“PÚQ”；
又如“李宏生于1978年或1980年”，是排斥或，不可兼或，记P：“李宏生于1978年”，Q：“李宏生于1980年”，命题符号化为P`ÚQ。
PÚQ取值为1，只要P，Q之一取值为1，只有P，Q均取值为0时，PÚQ取值为0。
P`ÚQ取值为1当且仅当P，Q取值不同；P`ÚQ取值为0当且仅当P，Q取值相同。
4. “«” 等价联结词，P，Q是命题，P«Q是P，Q的等价式，是联结词«和命题P，Q组成的复合命题。“«”在语句中相当于“…当且仅当…”，P«Q取值1当且仅当P，Q取值相同。
例如，“长城是中国的古代的伟大建筑”，“长江是中国最长的河流”。它们的真值是相同的，可记作P：“长城是中国古代的伟大建筑”，Q：“长江是中国最长的河流”，有P«Q真值是1。
又如A：“3×5＝12”，B：“石家庄是河南省会”，有A«B真值是1，
再如，P1：“北京的1月份最冷”，P2：“北方的7月份最热”，有P1«P2真值为0。
5. “®”蕴含联结词，P，Q是命题，P®Q是P，Q的蕴含式，是联结词®和命题P，Q组成的复合命题。P®Q取值为0，只有P取值为1，Q取值为0时；其余各种情况，均有P®Q取值为1。
注意：在语句中，P®Q，有时也解释为“若P，则Q”。似乎P®Q是“因果关系”，但是不一定总有因果关系。只要P，Q是命题(即有真值)，那么P®Q就是命题(即有真值)。
不管P，Q是否有无因果关系。
例如，P：今晚开会，Q：今晚我到校。
有P®Q，如果今晚开会，我今晚到校(有因果关系)。它的真值是1。
又如，A：雪是白的，B：太阳从西边出来。
有A®B，如果雪是白的，太阳从西边出来(没有因果关系)，它的真值是0。
1.2 命题公式、永真性的判定或命题公式的分类
命题公式的永真性包括判定命题公式是永真的(重言式)、永假的(矛盾式)。具体判定方法有两种：
其一是真值表法，对于任给一个公式，列出该公式的真值表，观察真值表的最后一列是否全为1(或全为0)，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全为1，又非全为0，则该公式是可满足式。
例1.1 判定公式P®Q与ØPÚQ是否等值。
解 列公式P®Q与ØPÚQ的真值表。如表1－1。
表1－1 公式P®Q与ØPÚQ的真值表
|
P |
Q |
P®Q |
ØP |
ØPÚQ |
P®Q«ØPÚQ |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
1 |
由表可知，公式P®Q与公式ØPÚQ是等值的。
由表的最后一列可知，P®Q«ØPÚQ是重言式。
其二是推导法。利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式。
1.3 范式
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律。
在范式中只有联结词Ù和Ú，命题变项或其否定用联结词Ú，Ù把联结起来。主范式要求命题变项齐全，按极小(大)项排列起来。
于是有求范式的步骤。
求析取(合取)范式的步骤：
① 将公式中的联结词都化成Ø，Ù，Ú，在析取(合取)范式中不能有联结词®，«，`Ú；
② 将否定联结词Ø消去或移到各命题变项之前；
③ 利用分配律、结合律等，将公式化为析取(合取)范式。
求命题公式A的主析取(合取)范式的步骤
① 求公式A的析取(合取)范式；
② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如PÙØP(PÚØP)用0(1)替代。用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如PÙP(PÚP)用P替代，miÚmi(MiÙMi)用mI(Mi)替代。
③ 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或ØPi，则添加PiÚØPi(PiÙØPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；
④ 将极小(极大)项按由小到大的顺序排列，用S(P)表示。
1.4 命题演算的推理理论
掌握演绎或形式证明，进行逻辑推理时一是要理解并掌握14个重言蕴含式(即I1～I14)，17个等值式(E1～E17)；二是会使用三个规则(P规则、T规则和CP规则)。
要多做一些练习，重言蕴含式和等值式要靠练习加以记忆，而不能靠死记。
例 判别下列语句是否命题？如果是命题，指出其真值。
(1) 是无理数；
(2) 存在最大的质数；
(3) 中国是一个人口众多的国家；
(4) 这座楼可真高啊！
(5) 你喜欢黄河吗？
(6) 请你跟我走；
(7) 火星上也有人。
解 (1) 是命题，真值为1；
(2) 是命题，真值为0；
(3) 是命题，真值为1；
(4),(5),(6)不是命题。(4)，(5)不是陈述句,它们没有确定的真值。(6)的真值无法确定。
(7) 是命题。真值是唯一的，迟早会被指出。
例8 将下列命题符号化：
(1) 虽然交通堵塞，但是老王还是准时到达火车站；
(2) 黎明是计算机系的学生，他住在2号楼305室或412室；
(3) 张三和李四是好朋友；
(4) 张力是三好学生或优秀共青团员
(5) 老李或小刁中有一个人去广州出差。
解 (1) 首先用字母表示原子(简单)命题。
P：交通堵塞，Q：老王准时到达火车站。
因为本小题强调“交通堵塞”和“老王准时到达火车站”这两件事，因此该命题可以符号化为：PÙQ。
(2) 首先用字母表示原子(简单)命题。
P：黎明是计算机系的学生； Q：黎明住在2号楼305室。
R：黎明住在2号楼412室。
因为黎明只能住在一个房间，305室或412室的“或”是排斥或。因此该命题符号化为
(3) “张三和李四是好朋友”是一个简单命题。如果把它拆成“张三是好朋友”，“李四是好朋友”，就不成为完整的语句了。该命题符号化为P：张三和李四是好朋友。
(4) 首先用字母表示原子(简单)命题。
P：张力是三好学生； Q：张力是优秀共青团员。
此处的“或”是相容或，故该命题符号化为PÚQ。
(5) 首先用字母表示原子(简单)命题。
P：老李去上海出差； Q：小刁去上海出差。
要求只能一个人出差，因此此处的“或”是排斥或，该命题符号化为P`ÚQ，也可以表示成(PÙØQ)Ú(ØPÙQ)