精品课程《离散数学》PPT课件(全).ppt
《精品课程《离散数学》PPT课件(全).ppt》由会员分享,可在线阅读,更多相关《精品课程《离散数学》PPT课件(全).ppt(213页珍藏版)》请在三一文库上搜索。
1、1,离散数学,计 算 机 科 学 系 授课教师:王静,2,引 言 1,为什么学习离散数学? 离散数学是现代数学的一个重要分支,是计算机科学与技术的理论基础,所以又称为计算机数学,是计算机科学与技术专业的核心、骨干课程。 离散数学是什么课? 它以研究离散量的结构和相互间的关系为主要目标,其研究对象一般是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。 离散数学的主要内容是什么? 内容包含:数理逻辑、集合论、代数结构与布尔代数、图论等。 离散数学是随着计算机科学的发展而逐步建立的,它形成于七十年代初期,是一门新兴的工具性学科。,3,引 言 2,学习该课程的目的: 一方面,它给后继课,如
2、数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络和人工智能等,提供必要的数学基础; 另一方面,通过学习离散数学,可以培养和提高自己的抽象思维和逻辑推理能力,为以后的软、硬件学习和研究开发工作,打下坚实的数学基础。,4,引 言 3,教学要求: 通过该课程的学习,学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 自学要求: 通过反复看书及做课后习题,来加深对该课程中的一些基本概念的理解,逐步提高自己的抽象思维和逻辑推理能力。,5,第一章 命题逻辑,数理逻辑是研究推理(即研究人类思维的形式结构和规律)的科学,起源于17世纪,它采用数学符号化
3、的方法,因此也称为符号逻辑。 从广义上讲,数理逻辑包括四论、两演算 即集合论、模型论、递归论、证明论和命题演算、谓词演算,但现在提到数理逻辑,一般是指命题演算和谓词演算。本书也只研究这两个演算。,6,数理逻辑的创始人是Leibniz,为了实现把推理变为演算的想法,他把数学引入了形式逻辑。其后,又经多人努力,逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后,数理逻辑进入一个崭新的发展阶段,逻辑学不仅与数学结合,还与计算机科学等密切关联。 1931年Godel不完全性定理的提出,以及递归函数可计算性的引入,促使了1936年tUring机的产生,十年后,第一台电子计算机问世。,第一章 命题
4、逻辑,7,数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展,模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本篇我们只从语义出发,对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍,将不涉及任何公理系统。,第一章 命题逻辑,8,1.1 命题符号化及联结词,基本概念 命题:能够判断真假的陈述句。 命题的真值:命题的判断结果。真值只取 两个值: 真、假。 真命题:真值为真的命题。 假命题:真值为假的命题。 判断命题的两个步骤: 1、是否为陈述句; 2、是否有确定的、唯一的真值。,9,例1:判断下列句子是否为命题。 1、雪是白色的。 2、2是偶
5、数且3也是偶数。 3、陈胜吴广起义那天杭州下雨。 4、大于2的偶数均可分解为两个质数的和(哥德巴赫猜想)。 5、真舒服啊! 6、别的星球上有生物存在。 7、您去学校吗? 8、x+y0 9、我正在说谎。 10、1+101=110,1.1 命题符号化及联结词,10,1.1 命题符号化及联结词,区别 命题都是陈述句,但陈述句不都是命题。只有陈述句所表达的判断结果是唯一确定的(正确的或错误的),它才是命题。,11,命题及其真值的抽象化 在本书中,用小写英文字母p,q,r,p1,p2,p3等表示命题,用“1”、“0”分别表示真值的真、假。 如: p:罗纳尔多是球星。 q:5是负数。 p3:明天天气晴。
6、皆为符号化的命题,其真值依次为1、0、1或0。,1.1 命题符号化及联结词,12,命题的分类 简单/原子命题:由不能再分解为更简单的陈述句的陈述句构成。 如上例中的命题。 复合命题:由简单命题通过联结词联结而成的陈述句。 例2: 1)3不是偶数。 2)2是素数和偶数。 3)林芳学过英语或日语。,1.1 命题符号化及联结词,13,1.1 命题符号化及联结词,命题常项或常元:真值是唯一确定的 即:0,1 命题变项或变元:真值是不确定的 即:p,q,r,区别 命题与命题变项含义是不同的,命题指具体的陈述句,是有确定的真值,而命题变项的真值不定,只当将某个具体命题代入命题变项时,命题变项化为命题,方可
7、确定其真值。,14,1.1 命题符号化及联结词,命题与命题变项象程序语言中常量与变量的关系一样。 例:5是一个常量,是一个确定的数字,而x是一个变量,赋给它一个什么值它就代表什么值,即x的值是不定的。,例3:判断下列句子是否为命题? 1张校长的头发有一万根。 2我所说的是假的。,(是) (否),15,常用联结词 1.否定词 设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作 p,符号称为否定联结词。 运算规则:,1.1 命题符号化及联结词,16,2.合取词 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p q,符号称为合取联结词。 运算规则:,1
8、.1 命题符号化及联结词,17,合取运算特点:只有参与运算的二命题全为真时,运算结果才为真,否则为假。 自然语言中的表示“并且”意思的联结词,如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为 。 注意:不要见到“与”或“和”就使用联结词 !,1.1 命题符号化及联结词,18,1.1 命题符号化及联结词,例4: 将下列命题符号化。 (1) 2既是偶数又是素数。 (2) 6不仅能被2整除,而且能被3整除。 (3) 8能被2整除,但不能被6整除。 (4) 5是奇数,6是偶数。 (5) 2与3的最小公倍数是6。 (6) 王丽和王娟是亲姐妹。,19,1.1 命题符号化及联结词,解:
9、(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:王丽和王娟是亲姐妹。,20,3.析取词 设p,q为二命题,复合命题“p或q” 称为p与q的析取式,记作p q,符号称为析取联结词。 运算规则:,1.1 命题符号化及联结词,21,析取运算特点:只有参与运算的二命题全为假时,运算结果才 为假,否则为真。 相容或:二者至少有一个发生,
10、也可二者都发生 排斥或:二者只有一个发生,即非此即彼 例如: (1)小王爱打球或爱跑步。 设p:小王爱打球。 q:小王爱跑步。 则上述命题可符号化为:p q (2)张晓静是江西人或湖南人。 设p:江西人。 q:湖南人。 则上述命题就不可简单符号化为:p q 而应描述为(p q) ( pq)(也可用异或联接词),1.1 命题符号化及联结词,22,4.蕴涵词 设p,q为二命题,复合命题“如果p,则q” 称为p与q的蕴涵式,记作p q,并称p为蕴涵式的前件,q为蕴涵式的后件,符号称为蕴涵联结词。 运算规则:,1.1 命题符号化及联结词,23,例:一位父亲对儿子说:“如果星期天天气好,就一定带你去动物
11、园。”问:在什么情况下父亲食言? 解:有以下四种可能情况: (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 命题符号化及联结词,25,1.1 命题符号化及联结词,例5: 将下列命题符号化,并指
12、出各复合命题的真值。 (1) 如果3+36,则雪是白色的。 (2) 如果3+36,则雪是白色的。 解: 令p: 3+36, q:雪是白色的。 (1)符号化为 p q (2)符号化为 p q,真值为1 真值为1,26,1.1 命题符号化及联结词,以下命题中出现的a是给定的一个正整数: (3) 只有 a能被2整除, a才能被4整除。 (4) 只有 a能被4整除, a才能被2整除。 解: 令r: a能被4整除, s: a能被2整除。 (3)符号化为 s r (4)符号化为 r s,真值不确定 真值为1,27,5.等价词 设p,q为二命题,复合命题“p当且仅当q” 称为p与q的等价式,记作p q,符号
13、称为等价联结词。 运算规则:,1.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 命题符号化及联结词,29,1.2 命题公式及其分类,1.命题公式 合式公式/命题公式:将命题变项用联结
14、词和圆括号按一定的逻辑关系联结起来的符号串。 当使用联结词集 ,时,合式公式(well formed formula)定义如下:,(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
15、) q)等不是合式公式。,1.2 命题公式及其分类,31,注意:为了方便,下面给出有关省略括号的一些约定。 公式的最外层括号可以省略.并且,( A)的括号可省略,记为 A. 规定联结词的优先级为按, , , ,的顺序递减,若省略括号后按此优先顺序得到的公式与原公式一致,则允许省略. 相同的联接词按从左到右的顺序计算时括号可以省略.,1.2 命题公式及其分类,32,2.公式层次 (1)若公式A是单个的命题变项,则称A为0层合式公式。 (2)称A是n+1(n0)层公式是指下列情况之一: (a) A= B,B是n层公式; (b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j) ; (
16、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,例:公式 p pq (p q) r (pq)( q p) 的层次分别为 0、1、3、4,1.2 命题公式及其分类,34,1.公式赋值 设p1 , p2 , , pn是出现在公式A中的全部的命题变项,给p1 , p2 , , pn各指定一个真值,称为对A的一个赋值或解释。 比如: 对公式(p q) r一组赋值为011
17、(意即令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)
18、若A不是矛盾式,则称A为可满足式。,1.2 命题公式及其分类,37,1.2 命题公式及其分类,用命题形式q1 ,q2,qn 分别替换命题形式A中的命题变项p1 ,p2,pn所得到的命题形式,称为A的一个替换实例(substitution instance)。 注意:一个替换应该是处处替换,而不是部分替换 。 定理1.1 设A命题形式,则 (1)设A是重言式,则A的任何替换实例都是重言式; (2)设A是矛盾式,则A的任何替换实例都是矛盾式。见例1.11,38,1 真值表 将命题公式A在所有赋值下取值情况列成表,称做A的真值表。 对公式A构造真值表的具体步骤为: (1)找出公式中所有的全体命题变项
19、p1 , p2 , , pn,列出2n个赋值。 (2)按从低到高的顺序写出公式的各个层次。 (3)对应各个赋值计算出各层次的真值,直到最后计算出公式的真值。,1.3 真值表和真值函数,39,例:构造公式 (p q) r 真值表。,1.3 真值表和真值函数,40,练习1:构造公式 (pq)( q p)真值表。,1.3 真值表和真值函数,41,练习2:构造公式 (p q) q 真值表。,1.3 真值表和真值函数,42,真值表的作用: (1)表示出公式的成真或成假赋值。 (2)判断公式类型: (a)若真值表最后一列全为1,则为重言式; (b)若真值表最后一列全为0,则为矛盾式; (c)若真值表最后一
20、列至少有一个1,则为可满足式;,1.3 真值表和真值函数,43,考虑:含有n个命题变项的公式的真值表有 ? 种不同的情况? 因此,必有很多公式具有相同的真值表。 如:,1.3 真值表和真值函数,44,1.3 真值表和真值函数,2 真值函数 定义 以真,假为定义域和值域的函数为真值函数。 如由五个逻辑联接词产生的所有wff都是真值函数,因此有无穷多个真值函数,显然最基本而重要的还是六个联接词。 当真值函数的变元为n个时,共有2n个指派,通过列出真值表也可以定义真值函数。,45,1.3 真值表和真值函数,例 确定下列真值表对应的真值函数。,注意:由真值表确定的真值函数不一定是最简单的wff,且不一
21、定只有一个表达式。,46,1.3 真值表和真值函数,例如 列出下列公式的真值表 (P R) ( P Q) ( Q R) 由此可见,这个公式的真值表与f1(P,Q,R)的相比较,可以看出这两个公式代表同一个真值函数。,47,1.4 等值式与等值演算,等值式 设A,B是两个命题公式,若A,B构成的等价式A B为重言式,则称A与B是等值的,记作A B。 即A B的充要条件是A B为重言式。 判断两个公式等值的方法1:真值表法。,48,例:判断公式 p(qr)、(p q) r是否等价。,由真值表可知,两个公式为等值式。,1.4 等值式与等值演算,49,需要记忆的16组重要的等值式 参见课本p13。,等
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 精品课程 PPT 课件
链接地址:https://www.31doc.com/p-3068763.html