您好,欢迎访问三七文档
离散数学DiscreteMathematics主讲教师:王耀辉wyh_c@mail.nedu.edu.cn教师简介1985年毕业于北京大学数学系计算数学专业专业技术职务:教授、硕士导师主讲课程:计算机类——BASIC、FORTRAN、人工智能原理、C、C++、PASCAL、VisualBASIC、程序设计方法学、SQLserver2000、数据库系统概论、软件工程、VisualFoxPro数学类——数值分析、最优化计算方法、运筹学、离散数学、解题理论、图论及其应用E-mail:wyh_c@mail.nedu.edu.cnTel:665677课程主要内容第一部分数理逻辑第二部分集合论第三部分代数系统第四部分图论离散数学与计算机的关系第一部分数理逻辑计算机是数理逻辑和电子学相结合的产物第二部分集合论集合:一种重要的数据结构关系:关系数据库的理论基础函数:所有计算机语言中不可缺少的一部分第三部分代数系统计算机编码和纠错码理论数字逻辑设计基础,计算机使用的各种运算第四部分图论数据结构、操作系统、编译原理、计算机网络原理的基础参考教材1、《离散数学》耿素云、屈婉玲、张立昂清华大学出版社2、《离散数学题解》耿素云、屈婉玲、张立昂清华大学出版社3、《离散数学导论》徐洁磐高等教育出版社4、《离散数学》洪帆等编电子工业出版社5、《离散数学》李盘林等编人民邮电出版社学习要求出勤思考笔记作业绪论本课程是高校计算机专业学生的必修课之一,是计算机科学与技术专业的核心、骨干课程,也是数学、信息与计算科学、信息管理与信息系统等专业的专业基础课程,是计算机科学与技术的理论基础该课程主要学习数理逻辑、集合论、代数结构、图论等四大方面的内容,包括:命题逻辑、谓词逻辑、集合与关系、函数、代数结构、格与布尔代数、图论等离散数学与计算机科学中的数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构等课程联系紧密本课程重点在于培养和提高大学生的抽象思维、逻辑推理和概括能力,从而为以后专业课程的学习及工作需要打下基础绪论离散数学课程地位:计算机专业(核心课程)信息类专业(必修课程)其它类专业(重要选修课程)离散数学的后继课程:数据结构、操作系统、算法分析与设计、数据库、C++语言……绪论离散数学课程的学习方法:强调:逻辑性、抽象性;注重:概念、方法与应用离散数学的学习要领:概念(正确)必须掌握好离散数学中大量的概念判断(准确)根据概念对事物的属性进行判断推理(可靠)根据多个判断推出一个新的判断例1:说谎者与说真话者问题:N夫妇晚上出门,邀请了W小姐照看他们的4个孩子。在N夫妇离家以前,向W小姐交待了许多注意事项,其中包括4个孩子的情况。N夫妇说他们的4个孩子中只有一个孩子总是说真话,另外3个则总是说谎。N夫妇告诉了W小姐说真话的孩子的名字,但由于注意事项太多,W小姐把名字忘记了。当她在为孩子们准备晚饭时,一个孩子在邻室打碎了一个花瓶。这是孩子们的话:B说:是S干的。S说:是J干的。L说:不是我打碎的。J说:S说是我干的,他在说慌。由于W小姐知道只有一个孩子说真话,她很快就找出了打碎花瓶的孩子。你知道是谁吗?例2:设整数集合为Z设自然数集合为N比较Z与N元素的多少例3:对于给定自然数1~n的任意排列,能否通过反复交换1,2,3,…,n中的元素而得到此排列?σ=(15236)(78)=(15)(12)(13)(16)(78)7812463587654321例4:任意6人聚会中,必有3人彼此相识,或有3人彼此不相识用两种颜色填涂完全图K6的各边,必包含有同色的“三角形”K3第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题:一个土耳其商人想找一个十分聪明的助手协助他经商,有两人前来应聘,这个商人为了试试哪个更聪明些,就把两个人带进一间漆黑的屋子里,他打开灯后说:“这张桌子上有五顶帽子,两顶是红色的,三顶是黑色的,现在,我把灯关掉,而且把帽子摆的位置弄乱,然后我们三个人每人摸一顶帽子戴在自己头上,在我开灯后,请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后,商人将电灯关掉,然后三人都摸了一顶帽子戴在头上,同时商人将余下的两顶帽子藏了起来,接着把灯打开。这时,那两个应试者看到商人头上戴的是一顶红帽子,其中一个人便喊道:“我戴的是黑帽子。”请问这个人说得对吗?他是怎么推导出来的呢?主要内容1命题逻辑基本概念2命题逻辑等值演算3命题逻辑的推理理论4一阶逻辑基本概念5一阶逻辑等值演算与推理1命题逻辑基本概念本章的主要内容:命题、联结词、复合命题命题公式、赋值、命题公式的分类1.1命题与联结词1.2命题公式及其赋值1.1命题与联结词命题及其分类联结词与复合命题复合命题的真假值1.1.1命题及其分类命题:具有真假意义(判断结果唯一)的陈述句命题的真值:判断结果真值的取值:真(1)、假(0)真命题与假命题注意:感叹句、祈使句、疑问句、悖论都不是命题例1.1下列句子中那些是命题?(1)是无理数.(2)2+5=8.(3)x+5>3.(4)你有铅笔吗?(5)这只兔子跑得真快呀!(6)请不要讲话!(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题21.1.1命题及其分类1.1.1命题及其分类命题的分类(1)简单命题(原子命题)(2)复合命题简单命题符号化(1)用小写英文字母等来表示简单命题(2)用1表示真,用0表示假例如::3是无理数,则是假命题,的真值为0,,,,,,,kkkrqprqpppp1.1.2联结词与复合命题例:3是无理数是不对的2是偶素数2或4是素数如果2是素数,则3也是素数2是素数当且仅当3也是素数。上述命题都是通过诸如“或”,“如果…,则…”等连词联结而成,这样命题,称为复合命题。相对地,构成复合命题的命题称为简单命题。1.1.2联结词与复合命题定义1.1设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p,符号┐称作否定联结词。并规定┐p为真当且仅当p为假。定义1.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真。定义1.3设p,q为二命题,复合命题“p或q”称作p与q的析取式,记作p∨q,∨称作析取联结词。并规定p∨q为假当且仅当p与q同时为假。1.1.2联结词与复合命题相容“或”与排斥“或”•例将下列命题符号化。(1)张晓静爱唱歌或爱听音乐。(2)张晓静是江西人或安徽人。(3)张晓静只能挑选202或203房间。•解在解题时,先将原子命题符号化。(1)p:张晓静爱唱歌。q:张晓静爱听音乐。(2)r:张晓静是江西人。s:张晓静是安徽人。(3)t:张晓静挑选202房间。u:张晓静挑选203房间。qpsr)()(utut1.1.2联结词与复合命题思考题:只能在周二说的话某人在周一总是说谎话,而在其它日子总是说真话。那么,有没有他只能在周二才能说的话呢?“今天不是周一就是周二。”1.1.2联结词与复合命题定义1.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作p→q,→称作蕴涵联结词。并规定p→q为假当且仅当p为真q为假。p→q的逻辑关系表示q是p的必要条件。注意在使用联结词→时,特别注意以下几点:1.1.2联结词与复合命题在自然语言里,特别是在数学中,q是p的必要条件有许多不同的叙述方式。例如,“只要p,就q”,“因为p,所以q”,“p仅当q”,“只有q才p”,“除非q才p”,“除非q,否则非p”等等。以上各种叙述方式表面看来有所不同,但都表达的是q是p的必要条件,因而所用联结词均应符号化为→,上述各种叙述方式都应符号化为p→q。在自然语言中,“如果p,则q”中的前件p与后件q往往具有某种内在联系。而在数理逻辑中,p与q可以无任何内在联系。在数学或其它自然科学中,“如果p,则q”往往表达的是前件p为真,后件q也为真的推理关系。但在数理逻辑中,作为一种规定,当p为假时,无论q是真是假,p→q均为真。也就是说,只有p为真q为假这一种情况使得复合命题p→q为假。1.1.2联结词与复合命题定义1.5设p,q为二命题,复合命题“p当且仅当q”称作p与q的等价式,记作,称作等价联结词。并规定为真当且仅当p与q同时为真或同时为假。的逻辑关系为p与q互为充分必要条件。以上定义了五种最基本、最常用、也是最重要的联结词┐,∧,∨,→,,将它们组成一个集合{┐,∧,∨,→,},称为一个联结词集。其中┐为一元联结词,其余的都是二元联结词。qpqpqp1.1.2联结词与复合命题•例将下列命题符号化,并指出各复合命题的真值:•(1)如果3+3=6,则雪是白的。(2)如果3+3≠6,则雪是白的。(3)如果3+3=6,则雪不是白的。(4)如果3+3≠6,则雪不是白的。•以下命题中出现的a是一个给定的正整数:•(5)只要a能被4整除,则a一定能被2整除。(6)a能被4整除,仅当a能被2整除。(7)除非a能被2整除,a才能被4整除。(8)除非a能被2整除,否则a不能被4整除。(9)只有a能被2整除,a才能被4整除。(10)只有a能被4整除,a才能被2整除。1.1.3复合命题真假值联结词可以嵌套使用,在嵌套使用时,规定如下优先顺序:(),┐,∧,∨,→,,对于同一优先级的联结词,先出现者先运算。1.2命题公式及其赋值命题公式的定义公式的层次公式的赋值真值表公式的真假值分类1.2.1命题公式的定义由于简单命题是真值唯一确定的命题逻辑中最基本的研究单位,所以也称简单命题为命题常项或命题常元。从本节开始对命题进一步抽象,首先称真值可以变化的陈述句为命题变项或命题变元,也用p,q,r,…表示命题变项。当p,q,r,…表示命题变项时,它们就成了取值0或1的变项,因而命题变项已不是命题。这样一来,p,q,r,…既可以表示命题常项,也可以表示命题变项。在使用中,需要由上下文确定它们表示的是常项还是变项。1.2.1命题公式的定义定义1.6(1)单个命题变项是合式公式,并称为原子命题公式。(2)若A是合式公式,则(┐A)也是合式公式。(3)若A,B是合式公式,则(A∧B),(A∨B),(A→B),(AB)也是合式公式。(4)只有有限次地应用(1)~(3)形式的符号串才是合式公式。合式公式也称为命题公式或命题形式,并简称为公式。如:(p→q)∧(q→r),(p∧q)∧┐r,p∧(q∧┐r)等都是合式公式,而pq→r,(p→(r→q)等不是合式公式。注意:定义1.6给出的合式公式的定义方式称为归纳定义方式,后面还将多次出现这种定义方式。1.2.2公式的层次1.2.3公式的赋值1.2.3公式的赋值定义1.8设p1,p2,…,pn是出现在公式A中的全部命题符号,给p1,p2,…,pn各指定一个真值,称为对A的一个赋值或解释。若指定的一组值使A的真值为1,则称这组值为A的成真赋值;若使A的真值为0,则称这组值为A的成假赋值。不难看出,含n(n=1)个命题变项的公式共有2n个不同的赋值。1.2.4真值表定义1.9将命题公式A在所有赋值下取值情况列成表,称作A的真值表。构造真值表的具体步骤如下:(1)找出公式中所含的全体命题变项p1,p2,…,pn(若无下角标就按字典顺序排列),列出2n个赋值。本课件规定,赋值从00…0开始,然后按二进制加法依次写出各赋值,直到11…1为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值,直到最后计算出公式的真值。1.2.4真值表•例1.8求下列公式的真值表,并求成真赋值和成假赋值。rqq)(p(3)q)(qq)(p(2)rq)p()1(1.2.4真值表1.2.4真值表1.2.4真值表1.2.5公式的真假值分类定义1.10设A为任
本文标题:离散数学(一)
链接地址:https://www.777doc.com/doc-4796251 .html