《离散数学DiscreteMathematics.ppt》由会员分享，可在线阅读，更多相关《离散数学DiscreteMathematics.ppt（37页珍藏版）》请在三一文库上搜索。
1、,离 散 数 学 Discrete Mathematics,计算机科学与工程学院 金 忠,智能楼(337幢)305室 84317297-305, 13770713373 http:/ 近代数学连续的数量概念（实数），处理连续数量关系的数学（微积分）,如何对离散结构建立离散数学模型?,离散数学及其应用,数理逻辑 (1-5),集 合 论 (6-8),图 论 (9-10),代 数 (11-12),刘嘉忆,对计算机专业系统知识的辐射作用,数理逻辑,第一章 命题演算基础 第二章 命题演算的推理理论 第三章 谓词演算基础 第四章 谓词演算的推理理论 第五章 递归函数论,第一章 命题演算基础,1.1 命题和
2、联结词 1.1.1 命题 (一) 命题定义,定义1 凡是可以判断真假的陈述句称为命题。,例：下列句子都是命题吗？,雪是白的。 雪是黑的。 好大的雪啊！ 8大于12。 1+101=110。,例：下列句子都是命题吗？,上海世博会开幕时天晴 21世纪末，人类将住在月球 大于2的偶数可表示成两个素数之和 X0 如果x大于3，则x2大于9。,例：下列句子都是命题吗？,8大于12吗？ 请勿吸烟。 姚明很帅。 南京很美。 我正在说谎 。,悖论,命题的真假问题,在数理逻辑的学习中， 不能去纠缠各种具体命题的真假问题， 而是将命题当成数学概念来处理， 看成一个抽象的形式化的概念， 把命题定义成非真必假的陈述句,
3、带联结词的命题,今晚我看书。 今晚我玩网络游戏。 今晚我不看书。 今晚我不玩网络游戏。 今晚我不看书， 我玩网络游戏。 今晚我看书，或者我玩网络游戏。,否定,并且,或者,(二) 原子命题和复合命题,原子命题不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。 复合命题由原子命题利用联结词构成的命题,复合命题例子,（1）雪不是白的（并非雪是白的） （2）今晚我看书或者去看电影。 （3）如果天气好，那么我去接你。 （4）偶数a是质数，当且仅当a=2（a是常数）。 （5） 2是偶数且3也是偶数。 （6）你去了学校，我去了工厂。,(三)命题变元,定义2 如果当P表示任意命题时，
4、称P为命题变元。,1.1.2 联结词,否定词 合取词 析取词 蕴含词 等价词 ,P,P 是指命题： “P的否定”， 读作“非P”。,P P T F F T,真值表,例 P：上海是中国的城市。 P：上海不是中国的城市。 例 P：雪是黑色的。 P：并非雪是黑色的。,否定联结词使用的原则,将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。,例 P: 这些都是学生。 P：这些不都是学生 这些都不是学生,PQ,PQ是指命题： “P并且Q”， 读作“ P合取Q”。,例 P: 225 Q：雪是白的。 PQ：225并且雪是白的。 例 P: 今天刮风。 Q：今天下雨。 PQ：今天刮
5、风，下雨。,真值表,PQ,PQ是指命题： “P或者Q” 读作“P析取Q”。,P Q P Q T T T T F T F T T F F F,例 P: 225 Q：雪是白的。 PQ：225或者雪是白的。,例 P:今天刮风。 Q：今天下雨。 PQ ：今天刮风或者今天下雨。,可兼的“或”不可兼的“或”,P Q PQ T T T T F T F T T F F F,他会英语或法语。,PQ,PQ是指命题： “如果P，则Q” 读作“P蕴含Q”。,例 P：1+13 Q：雪是黑的 PQ: 只要1+1=3，雪就是黑的,例 P: 天气不好 Q：我去接你 PQ: 如果天气不好，那么我去接你。,注1. 前件为假时，命
6、题为真,如果蕴含前件P是假命题，那么不管Q是什么命题，命题 PQ在逻辑中都被认为是真命题。 例 如果1=2，那太阳从西边升起。,P Q P Q T T T T F F F T T F F T,真值表,注2. 前件、后件可以毫不相关,在日常语言中“如果则”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。 例 P：235 Q：雪是黑色的 PQ：如果235，则雪是黑色的,灵活叙述蕴含词的例子,设 P：天下雨， Q：我回家， 试表示下列命题： 只要天下雨，我就回家。 只有天下雨，我才回家。 除非天下雨，否则我不回家。 仅当天下雨，我才回家。,PQ,
7、QP,QP,QP,或PQ,PQ,PQ 是指命题： “P当且仅当Q” 读作“P等价于Q”。,P Q P Q T T T T F F F T F F F T,例 P: 2+35 Q: e是无理数 PQ ：2+35的充要条件是 e是无理数,等价词的例子,例 P: 225 Q：雪是白色的。 P Q：225当且仅当雪是白色的。,例 设a为一固定的自然数。 P: a是偶数 Q: a能被3整除。 P Q：a是偶数当且仅当它能被3整除。,是否命题？是否复合命题？,例 Tom和John是兄弟。 例 如果x0， 则 x20。 例 若两圆面积相等，则它们的半径相等。,是否命题？是否复合命题？,例 若两圆的面积相等，
8、则它们的半径相等 。 例 若两圆A、B的面积相等，则它们的半径相等。 例 吃一堑，长一智。,A,B,真值函项的定义,以真假为定义域并以真假为值域的函数,T, F,(T, T), (T,F), (F,T), (F,F),T, F,一元真值函项,二元真值函项,T, F,一元联结词的真值表,一个命题变项P，可取“T”和“F”两种值。可定义四个一元真值函项 f0，f1，f2，f3。,永 真,恒 等,否 定 P,永 假,二元联结词,P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 T T T F T T T F F F T T T T F
9、 F F F T F T T F T T F T T F F T F T F F F F T T T T F T T F T F T F F F T F F F F T T T T F T T F T F F F F F T F,f4 为 析 取 ,f2为 蕴含,f8 为 等价,f11 为 合 取 ,三元联结词共有多少个？,28,1.1.3 合式公式,合式公式为如下定义的式子，简称为公式： 任何命题变元均是公式； 如果P为公式，则P为公式； 如果P，Q为公式，则 PQ, PQ, PQ, PQ 为公式； 当且仅当经过有限次使用、所组成的符号串才是公式，否则不为公式 。,Well formed f
10、ormulae,n 元公式,若公式中有n个不同的命题变元， 就说为n 元公式。,3元公式的例子： （PQ）R）（ PQ）,（PQR）（ PQ）,优先级约定,、 优先级相同 比其它联结词有更高的优先级 括号（）内的运算优先,例 令 P：北京比天津人口多。 Q：2+24。 R：乌鸦是白色的。 求下列公式的真值： (1) (QR)(P R) (2) (PR) (P R),命题符号化,分析出简单命题，符号化 用联结词联结简单命题,提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。,例 将下述命题符号化，并指出真值:,（1）肉包子是由面粉和猪肉做成的。 （2）2是质数且偶数，3是质数或偶数。 （3）如果我只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 （4）如果他喜欢QQ，他就喜欢微信；当小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。,例4(p5)已知三个命题： P：今晚我在家上网； Q：今晚我去球场看足球比赛； R：今晚我在家上网或去球场看足球比赛。 试问PQ和R是否表达同一命题？ 请用真值表说明之。,R=(PQ)(PQ),不可兼 或,