精品课程《离散数学》PPT课件(全)

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

1离散数学计算机科学系授课教师:王静2引言1为什么学习离散数学?离散数学是现代数学的一个重要分支,是计算机科学与技术的理论基础,所以又称为计算机数学,是计算机科学与技术专业的核心、骨干课程。离散数学是什么课?它以研究离散量的结构和相互间的关系为主要目标,其研究对象一般是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。离散数学的主要内容是什么?内容包含:数理逻辑、集合论、代数结构与布尔代数、图论等。离散数学是随着计算机科学的发展而逐步建立的,它形成于七十年代初期,是一门新兴的工具性学科。3引言2学习该课程的目的:一方面,它给后继课,如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络和人工智能等,提供必要的数学基础;另一方面,通过学习离散数学,可以培养和提高自己的抽象思维和逻辑推理能力,为以后的软、硬件学习和研究开发工作,打下坚实的数学基础。4引言3教学要求:通过该课程的学习,学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。自学要求:通过反复看书及做课后习题,来加深对该课程中的一些基本概念的理解,逐步提高自己的抽象思维和逻辑推理能力。5第一章命题逻辑数理逻辑是研究推理(即研究人类思维的形式结构和规律)的科学,起源于17世纪,它采用数学符号化的方法,因此也称为符号逻辑。从广义上讲,数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算,但现在提到数理逻辑,一般是指命题演算和谓词演算。本书也只研究这两个演算。6数理逻辑的创始人是Leibniz,为了实现把推理变为演算的想法,他把数学引入了形式逻辑。其后,又经多人努力,逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后,数理逻辑进入一个崭新的发展阶段,逻辑学不仅与数学结合,还与计算机科学等密切关联。1931年Godel不完全性定理的提出,以及递归函数可计算性的引入,促使了1936年tUring机的产生,十年后,第一台电子计算机问世。第一章命题逻辑7数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展,模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。本篇我们只从语义出发,对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍,将不涉及任何公理系统。第一章命题逻辑81.1命题符号化及联结词基本概念命题:能够判断真假的陈述句。命题的真值:命题的判断结果。真值只取两个值:真、假。真命题:真值为真的命题。假命题:真值为假的命题。判断命题的两个步骤:1、是否为陈述句;2、是否有确定的、唯一的真值。9例1:判断下列句子是否为命题。1、雪是白色的。2、2是偶数且3也是偶数。3、陈胜吴广起义那天杭州下雨。4、大于2的偶数均可分解为两个质数的和(哥德巴赫猜想)。5、真舒服啊!6、别的星球上有生物存在。7、您去学校吗?8、x+y09、我正在说谎。10、1+101=1101.1命题符号化及联结词101.1命题符号化及联结词区别命题都是陈述句,但陈述句不都是命题。只有陈述句所表达的判断结果是唯一确定的(正确的或错误的),它才是命题。11命题及其真值的抽象化在本书中,用小写英文字母p,q,r,…p1,p2,p3…等表示命题,用“1”、“0”分别表示真值的真、假。如:p:罗纳尔多是球星。q:5是负数。p3:明天天气晴。皆为符号化的命题,其真值依次为1、0、1或0。1.1命题符号化及联结词12命题的分类简单/原子命题:由不能再分解为更简单的陈述句的陈述句构成。如上例中的命题。复合命题:由简单命题通过联结词联结而成的陈述句。例2:1)3不是偶数。2)2是素数和偶数。3)林芳学过英语或日语。1.1命题符号化及联结词131.1命题符号化及联结词命题常项或常元:真值是唯一确定的即:0,1命题变项或变元:真值是不确定的即:p,q,r区别命题与命题变项含义是不同的,命题指具体的陈述句,是有确定的真值,而命题变项的真值不定,只当将某个具体命题代入命题变项时,命题变项化为命题,方可确定其真值。141.1命题符号化及联结词命题与命题变项象程序语言中常量与变量的关系一样。例:5是一个常量,是一个确定的数字,而x是一个变量,赋给它一个什么值它就代表什么值,即x的值是不定的。例3:判断下列句子是否为命题?1.张校长的头发有一万根。2.我所说的是假的。(是)(否)15常用联结词1.否定词设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作p,符号称为否定联结词。运算规则:pp10011.1命题符号化及联结词162.合取词设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,符号∧称为合取联结词。运算规则:pqp∧q0000101001111.1命题符号化及联结词17合取运算特点:只有参与运算的二命题全为真时,运算结果才为真,否则为假。自然语言中的表示“并且”意思的联结词,如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”等都可以符号化为∧。注意:不要见到“与”或“和”就使用联结词∧!1.1命题符号化及联结词181.1命题符号化及联结词例4:将下列命题符号化。(1)2既是偶数又是素数。(2)6不仅能被2整除,而且能被3整除。(3)8能被2整除,但不能被6整除。(4)5是奇数,6是偶数。(5)2与3的最小公倍数是6。(6)王丽和王娟是亲姐妹。191.1命题符号化及联结词解:(1)(2)(3)(4)都是合取式命题,(5)(6)是简单命题。(1)p∧q,令p:2是偶数,q:2是素数。(2)p∧q,令p:2|6,q:3|6。(3)p∧q,令p:2|8,q:6|8。(4)p∧q,令p:5是奇数,q:6是偶数。(5)p:2与3的最小公倍数是6。(6)p:王丽和王娟是亲姐妹。203.析取词设p,q为二命题,复合命题“p或q”称为p与q的析取式,记作p∨q,符号∨称为析取联结词。运算规则:pqp∨q0000111011111.1命题符号化及联结词21析取运算特点:只有参与运算的二命题全为假时,运算结果才为假,否则为真。相容或:二者至少有一个发生,也可二者都发生排斥或:二者只有一个发生,即非此即彼例如:(1)小王爱打球或爱跑步。设p:小王爱打球。q:小王爱跑步。则上述命题可符号化为:p∨q(2)张晓静是江西人或湖南人。设p:江西人。q:湖南人。则上述命题就不可简单符号化为:p∨q而应描述为(p∧q)∨(p∧q)(也可用异或联接词∨)1.1命题符号化及联结词224.蕴涵词设p,q为二命题,复合命题“如果p,则q”称为p与q的蕴涵式,记作pq,并称p为蕴涵式的前件,q为蕴涵式的后件,符号称为蕴涵联结词。运算规则:pqpq0010111001111.1命题符号化及联结词23例:一位父亲对儿子说:“如果星期天天气好,就一定带你去动物园。”问:在什么情况下父亲食言?解:有以下四种可能情况:(1)星期天天气好,带儿子去了动物园;(2)星期天天气好,却没带儿子去动物园;(3)星期天天气不好,却带儿子去了动物园;(4)星期天天气不好,没带儿子去动物园。24蕴涵运算pq表示的逻辑关系是:p是q的充分条件或者q是p的必要条件。自然语言中可用pq蕴涵式表述命题格式有:“只要p,就q”“因为p,所以q”、“p仅当q”、“只有q才p”、“除非q才p”、“除非q,否则非p”等。与自然语言的不同:前件与后件可以没有任何内在联系!1.1命题符号化及联结词251.1命题符号化及联结词例5:将下列命题符号化,并指出各复合命题的真值。(1)如果3+3=6,则雪是白色的。(2)如果3+3≠6,则雪是白色的。解:令p:3+3=6,q:雪是白色的。(1)符号化为pq(2)符号化为pq真值为1真值为1261.1命题符号化及联结词以下命题中出现的a是给定的一个正整数:(3)只有a能被2整除,a才能被4整除。(4)只有a能被4整除,a才能被2整除。解:令r:a能被4整除,s:a能被2整除。(3)符号化为sr(4)符号化为rs真值不确定真值为1275.等价词设p,q为二命题,复合命题“p当且仅当q”称为p与q的等价式,记作pq,符号称为等价联结词。运算规则:pqpq0010101001111.1命题符号化及联结词28等价运算pq表示的逻辑关系是:p与q互为充分必要条件。相当于(pq)∧(qp)例6:将下列命题符号化,并讨论各命题的真值。(1)雪是白色的当且仅当法国的首都是里昂。(2)n是奇数的充分必要条件是n2是奇数。解:(1)令p:雪是白色的,q:法国的首都是里昂;符号化为pq,因为p为真,q为假,所以真值为0。(2)令p:n是奇数,q:n2是奇数;符号化为pq,因为p和q同真或同假,所以真值为1。1.1命题符号化及联结词291.2命题公式及其分类1.命题公式合式公式/命题公式:将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。当使用联结词集{,∧,∨,,}时,合式公式(wellformedformula)定义如下:(1)单个命题变项是合式公式,并称为原子命题公式。(2)若A是合式公式,则(A),(A∧B),(A∨B),(A∨B),(AB),(AB)也是合式公式。(3)只有有限次地应用(1)~(2)形成的符号串才是合式公式。合式公式也称为命题公式或命题形式,并简称为公式。30例子:(1)(pq),(r∧t)∨e,p,(p)(pq),(r∧t)∨e,p,(p)等均为合式公式。(2)pq∨t,(pw)∧q)pq∨t,(pw)∧q)等不是合式公式。1.2命题公式及其分类31注意:为了方便,下面给出有关省略括号的一些约定。①公式的最外层括号可以省略.并且,(A)的括号可省略,记为A.②规定联结词的优先级为按,∧,∨,∨,,的顺序递减,若省略括号后按此优先顺序得到的公式与原公式一致,则允许省略.③相同的联接词按从左到右的顺序计算时括号可以省略.1.2命题公式及其分类322.公式层次(1)若公式A是单个的命题变项,则称A为0层合式公式。(2)称A是n+1(n≥0)层公式是指下列情况之一:(a)A=B,B是n层公式;(b)A=B∧C,其中B,C分别为i层和j层公式,且n=max(i,j);(c)A=B∨C,其中B,C的层次及n同(b);(d)A=B∨C,其中B,C的层次及n同(b);(e)A=BC,其中B,C的层次及n同(b);(f)A=BC,其中B,C的层次及n同(b);(3)若公式A的层次为k,则称A是k层公式。1.2命题公式及其分类33例:公式ppq(pq)∧r((pq)(qp))的层次分别为0、1、3、41.2命题公式及其分类341.公式赋值设p1,p2,…,pn是出现在公式A中的全部的命题变项,给p1,p2,…,pn各指定一个真值,称为对A的一个赋值或解释。比如:对公式(pq)∧r一组赋值为011(意即令p=0,q=1,r=1)可得真值为1,另一组赋值为010可得真值为0;还有000,001,111……考虑:含有n个命题变项的公式共有多少个不同的赋值?1.2命题公式及其分类35若指定的一组值使A的真值为1,则称这组值为A的成真赋值。如对公式(pq)∧r赋值011,还有…???若指定的一组值使A的真值为0,则称这组值为A的成假赋值。如对公式(pq)∧r赋值010,还有…???1.2命题公式及其分类36公式的又一种分类方式设A为任一命题公式,(1)若A在其各种赋值下的取值均为真,则称A是重言式或永真式。(2)若A在其各种赋值下的取值均为假,则称A是矛盾式或永假式。(3)若A不是矛盾式,则称A为可满足式。1.2命题公式及其分类371.2命题公式及其分类用命题形式q1,q2,…,qn分别替换命题形式A中的命题变项p1,p2,…,pn所得到的命题形式,称为A的一个替换实例(substitutioninstance)。注意:一个替换应该是

1 / 213
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功