离散数学1-11-2资料

《离散数学1-11-2资料》由会员分享，可在线阅读，更多相关《离散数学1-11-2资料（53页珍藏版）》请在金锄头文库上搜索。

1、离散数学,离 散 数 学 Discrete Mathematics,陈明 Mobile: 15806574587 Email: mingchen_gang,信息科学与工程学院，J13-108,二零一三年九月,离散数学,课程简介,离散数学，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是整个计算机学科的专业基础课。 离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。,离散数学,离散数学的应用,关系型数据库的设计

2、（关系代数） 表达式解析（树） 编译技术、程序设计语言（代数结构） 人工智能、自动推理、机器证明（数理逻辑） 网络路由算法（图论） 游戏中的人工智能算法（图论、树、博弈论） 专家系统（集合论、数理逻辑知识和推理规则的计算机表达） 软件工程团队开发时间和分工的优化（图论网络、划分） (各种)算法的构造、正确性的证明和效率的评估（离散数学的各分支）,离散数学,教材,左孝凌，李为鉴，刘永才编著离散数学上海：上海科学技术文献出版社,1982 主要参考教材: 孙吉贵，杨凤杰，欧阳丹彤，李占山编著离散数学高等教育出版社，2002,离散数学,学习要求,本课程特点 定义+定理+例题 多做习题，认真独立完成作业

3、,离散数学,本课程主要内容,第一篇 数理逻辑 命题逻辑、谓词逻辑 第二篇 集合论 集合与关系、函数 第三篇 代数系统 代数结构、格和布尔代数 第四篇 图论 图论,离散数学,第一篇 数理逻辑,离散数学,思维的形式结构包括了概念，判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。 研究推理有很多方法，用数学方法来研究推理的规律称为数理逻辑，即通过引入表意符号研究推理，因此，数理逻辑又名符号逻辑。现代数理逻辑可分为四论、两演算：证明论、模型论、递归函数论、公理化集合论，以及命题演算和

4、谓词演算，这里介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。,离散数学,设有下列情况，结论是否有效？ (a)或者是天晴，或者是下雨。 (b)如果是天晴，我去看电影。. (c)如果我去看电影，我就不看书。 结论：如果我在看书则天在下雨。,解 若设M：天晴。 Q：下雨。 S：我看电影。R：我看书。,故本题即证：M Q，MS，S R，推出RQ,离散数学,逻辑学中著名的三段论方法，是由一个大前提，一个小前提推出结论的方法。例如： 所有的人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,离散数学,第一章 命题逻辑,目标语言：就是表达判断的一些语言的汇集。 目标语言和一些符号公式构成了数理逻辑的

5、形式符号体系。,离散数学,一、命题 1、定义 能表达判断的陈述句，称作命题（Proposition）。 例：判断下列语句是否为命题: (1)地球外存在智慧生物。 (2)11=10。 (3)今天下雨。 (4)你今年暑假去旅行吗？（疑问句） (5)克里特岛人说：“克里特岛人是说谎话者”。（悖论）,陈述句：述说一件事情的句子，句末用句号。 祈使句：要求或者希望别人做什么事或者不做什么事时用的句子，句末用句号或感叹号。 疑问句：提出问题的句子，句末用问号。 感叹句：带有浓厚感情的句子，句末用感叹号。 悖：相反。悖论：自相矛盾的陈述。,1-1 命题及其表示法,离散数学,命题所表达的判断结果称为命题的真值

6、（值）。 真值只有“真”和“假”两种，记作True（真）和False（假），分别用符号T（1）和F（0）表示。 由于命题只有两种真值，所以称这种逻辑为二值逻辑。 命题的真值是具有客观性质的，而不是由人的主观决定的。,2、真值（truth value）,离散数学,下面的语句中，哪些语句是命题，如果是命题，指出它的真值： （1）能整除7的正整数只有1和7本身。 （2）对于每一个正整数n存在一个大于n的素数。 （3）煤是白的。 （4）雪是黑的。 （5）在宇宙中地球是唯一有生命的星球。 （6）1+101=110 （7）买两张星期六的电影票。（祈使句） （8）全体立正！（祈使句） （9）明天是否开会？（

7、疑问句） （10）天气多好啊！（感叹句） （11）我正在说谎。（悖论）,（3）和（4）是命题，真值为F。,（1）、（2）是命题，真值为T。,祈使句、疑问句、感叹句等都不能作为命题，悖论无真值，也不能作为命题。语句（7）（11）都不是命题。,（5）是命题，有确定真值，只是目前还不知道。,（6）不是命题，在二进制中为T，在十进制中为F，故需根据上下文才能确定其真假 。,离散数学,命题有两种类型：原子命题和复合命题 原子命题：不能分解为更简单的陈述句。 复合（分子）命题：由联结词、标点符号和原子命题复合构成的命题。 前面例子中： （15）是原子命题； “我学英语，或者我学日语”是复合命题。,3、分类

8、,离散数学,练习：指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。（见教材第8页习题（1）,a）离散数学是计算机科学系的一门必修课。 b）小李有空吗？ c）明天我去看电影。 d）请勿随地吐痰！ e）不存在最大质数。 f）如果我掌握了英语、法语，那么学习其他欧洲语言就容易的多。 g）x=3 h）我们要努力学习。,离散数学,解：,a）离散数学是计算机科学系的一门必修课。 是命题，真值为T。 b）小李有空吗？ 疑问句，不是命题。 c）明天我去看电影。 是命题，真值要根据具体情况确定。 d）请勿随地吐痰！ 祈使句，不是命题。 e）不存在最大质数。 是命题，真值为T。 f）如果我掌握了英

9、语、法语，那么学习其他欧洲语言就容易的多。 是命题，真值为T。 g）x=3 不是命题，x=3的真假由x确定，当x取3时句子为真，当x取其他值时句子为假。 h）我们要努力学习。 祈使句，不是命题。,a），c），e）是原子命题，f）是复合命题。,离散数学,1、命题标识符：表示命题的符号称为命题标识符。在数理逻辑中，使用大写字母，或带下标的大写字母，或用方括号括起的数字表示命题。 例：P： 今天下雨。 “今天下雨”是一个命题，P是命题标识符。 A1： 今天下雨。 12：今天下雨。 A1 、 12也是命题标识符。 2、命题常量：一个命题标识符如表示确定的命题，就称为命题常量。 3、命题变元：如果命题标

10、识符只表示任意命题的位置标志，就称为命题变元。 命题变元可以表示任意命题，所以它不能确定真值，故命题变元不是命题。当命题变元用一个特定命题取代时，才能确定真值，这称为对命题变元进行指派。 4、原子变元：当命题变元表示原子命题时，该变元称为原子变元。,二、命题的表示法,离散数学,1-2 联结词,在数理逻辑中，复合命题是由原子命题与逻辑联结词组合而成，命题的连接方式叫做命题联结词或命题运算符。联结词是复合命题中的重要组成部分，为了便于书写和进行推演，必须对联结词作出明确规定并符号化。我们主要讨论下述五种联结词（亦称真值联结词，逻辑联结词或逻辑运算符），借助它们组成复合命题。,离散数学,（1）否定（

11、Negation） （一元联结词）,1.定义 定义1-2.1 设P为一命题，P的否定是一个新的命题，记作 P。若P为T，P为F；若P为F，P为T。 联结词“”表示命题的否定，称为否定联结词或否定词，读作“非”或“not”。否定联结词有时亦可记作“”。,2.真值表（truth table） 表1-2.1,命题P与其否定P的关系如表 1-2.1所示。,1/2,离散数学,“否定”的意义仅是修改了命题的内容，它是一个一元运算，我们仍把它看作为联结词。 自然语言中的“不”、“无”、“没有”等词在命题演算中常与“非”相当。 例：P：今天下雨。 P：今天不下雨。 P：今天无雨。 P：今天没有下雨。 P：上海

12、是一个大城市。 P：上海不是一个大城市。 P：上海是一个不大的城市。 练习：P：一个世纪是一百年。写出P。,2/2,离散数学,（2）合取（Conjunction） （二元联结词）,1.定义 定义1-2.2 两个命题P和Q的合取是一个复合命题，记作PQ。当且仅当P、Q同时为T时，PQ为T，在其他情况下，PQ的真值都是F。联结词“”称为合取词，读作“和”或“and”。,2.真值表 联结词“”的定义如表1-2.2所示。,表1-2.2,表1-2.2中给出复合命题PQ为T当且仅当P、Q同时为T。,1/7,离散数学,与“和”有相同意义的汉字还有“与”、“以及”、“并且”、“而且”等。 例：P：今天下雨。

13、Q：明天下雨。 上述命题的合取为 PQ：今天下雨而且明天下雨。 PQ：今天与明天都下雨。 PQ：这两天都下雨。 显然只有当“今天下雨”与“明天下雨”都是真时，“这两天都下雨”才是真的。,2/7,离散数学,合取的概念与自然语言中的“与”意义相似，但并不完全相同。例如 P：我们去看电影。 Q：房间里有十张桌子。 上述命题的合取为 PQ：我们去看电影与房间里有十张桌子。 在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P和Q的合取PQ来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，PQ的真值也必确定。,3/7,离散数学,例如 P：雪是白的 Q：地球是行星

14、。 PQ：雪是白的与地球是行星。 PQ的真值为T。 P：雪是白的 Q：地球是恒星。 PQ：雪是白的与地球是恒星。 PQ的真值为F。,4/7,离散数学,P：雪是黑的 Q：地球是行星。 PQ：雪是黑的与地球是行星。 PQ的真值为F。 P：雪是黑的 Q：地球是恒星。 PQ：雪是黑的与地球是恒星。 PQ的真值为F。,5/7,离散数学,命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。 P：今天下雨。 Q：今天不下雨。（此时Q既是P） PQ：今天下雨与今天不下雨。 PQ的真值为F。 命题联结词“合取”也可以将若干个命题联结在一起。 “合取”是一个二元运算。,6/7,离散数学,

15、注意，并非所有的“和”、“与”、“并且”均可用“”表示。 例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“”表示。 练习：1）P：一个世纪是一百年。 Q：4是偶数。 写出PQ并确定其真值。 2）P：5是一个整数，Q：5不是一个奇数 P Q：5是一个整数且5不是一个奇数 P Q：5是一个整数但5不是一个奇数,7/7,离散数学,（3）析取（Disjunction） （二元联结词）,1.定义 定义1-2.3 两个命题P和Q的析取是一个复合命题，记作PQ。当且仅当P、Q同时为F时，PQ为F，否则PQ的真值为T。联结词“”称

16、为合取词，读作“或”或“or”。,2.真值表 联结词的定义如表1-2.3所示。,表1-2.3,表1-2.3中给出复合命题PQ为F当且仅当P、Q同时为F。,1/4,离散数学,例：P：灯泡坏了。 Q：开关坏了。 上述命题的析取为 PQ：灯泡坏了或开关坏了。,2/4,离散数学,注意，并非所有的“或”可用“”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。 析取“”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里 P：他可能是100米赛跑的冠军。 Q：他可能是400米赛跑的冠军。 PQ：他可能是100米或400米赛跑的冠军。,3/4,离散数学,还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三