《离散数学完整版课件全套ppt教学教程最全整套电子讲义幻灯片最新)》由会员分享，可在线阅读，更多相关《离散数学完整版课件全套ppt教学教程最全整套电子讲义幻灯片最新)（201页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 命题逻辑命题逻辑离散数学有何用？离散数学有何用？:1计算机的基础是计算机的基础是0-1组成的组成的2进制进制.0-false,1-true 2进制进制-布尔代数即命题逻辑布尔代数即命题逻辑 George Boole 19世纪世纪 英国数学老师，它首次将英国数学老师，它首次将数数学学与与逻辑逻辑联系起来。联系起来。1938 香农香农在其在其硕士论文硕士论文中用布尔代数实现开关电路，中用布尔代数实现开关电路，布尔代数布尔代数(命题逻辑命题逻辑)成为成为数字电路数字电路基础基础 由于所有内容由于所有内容(整数，实数，字符，汉字，图片，声整数，实数，字符，汉字，图片，声音，视频，网页，音
2、，视频，网页，)进入电脑后，全是进入电脑后，全是01组成的字组成的字符串符串，从而都可以用，从而都可以用布尔运算布尔运算即即逻辑运算逻辑运算实现，命题逻实现，命题逻辑成为辑成为计算机计算机的基础。的基础。命题逻辑命题逻辑将将数学数学由由连续连续变到变到离散离散，由，由高数高数进入进入离散离散。Google采用逻辑运算进行搜索：采用逻辑运算进行搜索：数字之美数字之美 吴军吴军杨圣洪杨圣洪 000100010001110000 两者对应位置两者对应位置与与运算。运算。离散数学离散数学 100100000000100001 000100000000100000 逻辑运算逻辑运算 1秒秒10亿亿离散数
3、学有何用？离散数学有何用？:哥尼斯堡哥尼斯堡 康德老家康德老家 2七桥问题，可用于网络爬虫去搜索下载网页七桥问题，可用于网络爬虫去搜索下载网页.图中图中ABCD看成网站，桥就是看成网站，桥就是“超链接超链接”。图论是离散数学非常重要的内容。图论是离散数学非常重要的内容。Euler 通过互联网或图书馆通过互联网或图书馆,查看离散数学与计算机哪些课程查看离散数学与计算机哪些课程相关，数字电路设计，计算理论，数据库，编译原理，相关，数字电路设计，计算理论，数据库，编译原理，操作系统，体系结构操作系统，体系结构，所有计算机专业。，所有计算机专业。目的目的:1掌握离散数学掌握离散数学五大核心五大核心内容
4、（集合论、数内容（集合论、数理逻辑、代数结构、图论、组合数学）的基本概理逻辑、代数结构、图论、组合数学）的基本概念、基本理论、基本方法，训练提高学生的概括念、基本理论、基本方法，训练提高学生的概括抽象能力、逻辑思维能力、归纳构造能力，培养抽象能力、逻辑思维能力、归纳构造能力，培养学生严谨、完整、规范的科学态度和学习思维习学生严谨、完整、规范的科学态度和学习思维习惯。惯。2通过通过课程实验课程实验的训练，应用所学理论锻炼的训练，应用所学理论锻炼学生在数学建模、设计算法、编写程序和调试方学生在数学建模、设计算法、编写程序和调试方面的能力。面的能力。学习方法学习方法:1勤查资料掌握每章的发展历史，与
5、其他课勤查资料掌握每章的发展历史，与其他课程的横向联系，想明白为什么要学这些内容，在程的横向联系，想明白为什么要学这些内容，在整个整个 计算机学科中处于什么位置计算机学科中处于什么位置用途？用途？2、提高听堂效率，课后立马看懂例题，争取、提高听堂效率，课后立马看懂例题，争取当日做完习题，不过当日做完习题，不过23点，越拖越学不下去。点，越拖越学不下去。3、勤于用程序解题，解能解之题！写程序是、勤于用程序解题，解能解之题！写程序是将你的算法，告诉计算机，让电脑解放人脑，你将你的算法，告诉计算机，让电脑解放人脑，你会发现电脑真的好蠢！人脑想办法让脑聪明起来。会发现电脑真的好蠢！人脑想办法让脑聪明起
6、来。4、多交流，同一道较难的题，往往有多种解法，、多交流，同一道较难的题，往往有多种解法，有这本书的，其那本书的，有我的，有你的，有有这本书的，其那本书的，有我的，有你的，有他的。他的。考核方法考核方法:总评成绩总评成绩=25%*期中考试期中考试+35%*（程序设计（程序设计*40+小班讨论小班讨论*20%+20%*作业作业+20%*课堂测试）课堂测试）+40%*期末考试。期末考试。小班课实为习题讲解课。小班课实为习题讲解课。小班课上课前交作业，小班讨论由老师抽查作小班课上课前交作业，小班讨论由老师抽查作业决定哪位同学上来讲，在讲的过程中老师予以业决定哪位同学上来讲，在讲的过程中老师予以打分。
7、打分。程序设计在课后完成，实验课期间，助教与程序设计在课后完成，实验课期间，助教与任课老师验收程序，学生直接讲解程序如何设计任课老师验收程序，学生直接讲解程序如何设计及当面改动程序。及当面改动程序。实验课时间：实验课时间：跟助教商定跟助教商定引言引言 逻辑学逻辑学是推理的基础，在是推理的基础，在社会学社会学、自然科学自然科学尤其计算机学科中得到普遍应用。尤其计算机学科中得到普遍应用。数理逻辑数理逻辑是逻辑学的一个分支，也是数学的分是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规方法来描
8、述和处理思维形式、思维过程和思维规律，它在律，它在程序设计程序设计、数字电路数字电路设计、设计、计算机计算机原理、原理、人工智能人工智能等计算机课程得到了广泛应用。等计算机课程得到了广泛应用。命题逻辑命题逻辑是是数理逻辑数理逻辑的基础部分，的基础部分，但究竟什么是但究竟什么是命题命题？如何如何表示表示命题？命题？如何如何构造构造出复杂的命题？出复杂的命题？在本章将在本章将讨论讨论这些问题。这些问题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述语句陈述语句称为命题称为命题。如：。如：(1)湖南大学是湖南大学是985学校。学校。(2)命题逻辑是计算机科学的基础课程。命题逻辑是计算机科
9、学的基础课程。(3)命题逻辑是数字电路的基础。命题逻辑是数字电路的基础。(4)4是素数。是素数。(5)湖南大学坐落于湘江以东。湖南大学坐落于湘江以东。(6)地铁地铁4号线号线湖南大学站湖南大学站2018年建成。年建成。其中其中(1)、(2)、(3)与事实相符，是对的、正确的，称与事实相符，是对的、正确的，称为为真命题真命题，或者称命题的值为，或者称命题的值为“真真”，简记为，简记为T或数字或数字1。而而(4)、(5)明显与事实不相符，是错的、不正确，称为明显与事实不相符，是错的、不正确，称为假命题假命题，或称命题的值为，或称命题的值为“假假”，简记为，简记为F或数字或数字0。陈述句陈述句(6)
10、的正确性，到的正确性，到2018年年12月时能确定的，若月时能确定的，若届时建成了则它是对的、为真命题，否为假命题。届时建成了则它是对的、为真命题，否为假命题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(7)x与与y之和为之和为100，其中，其中x为整数，为整数，y为整数为整数 (8)1加加1等于等于10 (7)的对错的对错不确定不确定。当。当x为为50、y为为50时是对的，当时是对的，当x为为51、y为为52时是错的。时是错的。(8)的对错是的对错是不确定不确定的，为二进制时正确，当为八进制、的，为二进制时正确，当为八进制、十进制时是错
11、的，因此这两个陈述句十进制时是错的，因此这两个陈述句不是命题不是命题。(9)青枫峡青枫峡的红叶真美呀！的红叶真美呀！(10)动作快点！动作快点！(11)你是杨老师吗？你是杨老师吗？这三个语句这三个语句不是陈述语句不是陈述语句，因此不是命题。，因此不是命题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(12)我在说假话。我在说假话。(13)派出所说派出所说:必须先房子再能上户口必须先房子再能上户口 单位后勤说单位后勤说:必须先有户口才能分房必须先有户口才能分房 你能上到户口与要到房子吗你能上到户口与要到房子吗?这些是这些是悖论悖论，其真值不能
12、确定，故不是命题。，其真值不能确定，故不是命题。左右为难左右为难！1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(12)我在说假话。我在说假话。(13)派出所说派出所说:必须先房子再能上户口必须先房子再能上户口 单位后勤说单位后勤说:必须先有户口才能分房必须先有户口才能分房 你能上到户口与要到房子吗你能上到户口与要到房子吗?某市仅一位理发师，某市仅一位理发师，“本人的理发技艺十分高超，誉本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎
13、！只给这些人刮脸。我对各位表示热诚欢迎！”有一天理发师从镜子里看见自己的胡子长了，他本有一天理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，能给他自己刮脸呢？能地抓起了剃刀，能给他自己刮脸呢？若不刮自己，属于若不刮自己，属于“不给自己刮脸的人不给自己刮脸的人”，他就要给，他就要给自己刮脸，自己刮脸，真给自己刮脸呢？根据其所订规矩，不给自己刮。真给自己刮脸呢？根据其所订规矩，不给自己刮。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(13)我既要学程序设计，又要学离散数学。我既要学程序设计，又要学离散数学。(14)我们早餐在公寓食堂或外面
14、早点摊上吃。我们早餐在公寓食堂或外面早点摊上吃。(15)我不是数学院的学生我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命这三个陈述句都与事实相符，是对的，是真命题，其值为真题，其值为真(T/1)。其中其中(13)与与(14)可分解为另外二句话的组合，可分解为另外二句话的组合，而而(15)是对是对“我是数学院学生我是数学院学生”的否定，这些的否定，这些语句称为语句称为“复合命题复合命题”，不能再分解的语句称为，不能再分解的语句称为“简单命题简单命题”或或“原子命题原子命题”，为了便于推理与，为了便于推理与书写，常用书写，常用小写字母小写字母表示表示简单命题简单命题或或原子命题原子命
15、题。1.1 命题及联结词命题及联结词 简单命题简单命题组合成组合成复杂命题复杂命题时所使用的辅助词称时所使用的辅助词称为为“联结词联结词”。命题逻辑中的联结词归纳为以下命题逻辑中的联结词归纳为以下5种。种。合取合取：C语言中语言中&and 并且并且 析取析取：C语言中语言中|or 或或 否定否定：C语言中语言中!not 非非,不是不是,否定否定 条件式条件式：C语言中语言中 if()如果如果那么那么 若若p则则q 双条件式双条件式：若若p则则q且若且若q则则p,当且仅当当且仅当1.1 命题及联结词命题及联结词 定义定义1.1合取合取：当当p、q都对都对，即取值为真，即取值为真(T或或1)时，时
16、，“p合取合取q”的值为的值为真真.1.1 命题及联结词命题及联结词 定义定义1.1合取合取：当当p、q都都对对，都为，都为真真(T或或1)时，时，“p合取合取q”的值为的值为真真，其他情况为，其他情况为假假。逻辑运算符逻辑运算符“合取合取”，与汉语中与汉语中“并且、并且、而且、同时而且、同时”含义相含义相当当1.1 命题及联结词命题及联结词 定义定义1.2析取析取：当当p、q都都不对不对，都为，都为假假(F或或0)时，时，“p析取析取q”的值为的值为假假，其他情况为，其他情况为真真。逻辑运算符逻辑运算符“析取析取”，与汉语中与汉语中“或或”含含义相当，但有细微的义相当，但有细微的区别区别1.1 命题及联结词命题及联结词 运算符运算符“析取析取”与汉语的与汉语的“或或”几乎一致但有几乎一致但有区别：区别：哪些老师讲离散数学哪些老师讲离散数学？有人回答如下：？有人回答如下：(16)“讲离散数学的老师是杨老师或吴老师讲离散数学的老师是杨老师或吴老师”，分解为分解为 “讲离散数学的老师是杨老师讲离散数学的老师是杨老师”或或 “讲离散数学的老师是吴老师讲离散数学的老师是吴老师”，这两个原子命题
