离散数学I.ppt
《离散数学I.ppt》由会员分享,可在线阅读,更多相关《离散数学I.ppt(91页珍藏版)》请在三一文库上搜索。
1、离散数学 I,肖明军 Web: http:/ Email: 张浩 ,引言,课程简介 离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程,它研究的对象是有限个或可数的离散量。充分描述了计算机科学离散性的特征。 离散数学是传统的逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。 离散数学是随着计算机科学的发展而逐步建立起来的一门新兴的工具性学科,形成于七十年代。,引言,课程意义 离散数学是计算机科学的数学基础,其基本概念、理论、方法大量地应用在数字电路、编译原
2、理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中,是这些课程的基础课程。 离散数学学习十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高,能够培养提高学生的数学思维能力和对实际问题的求解能力。 教学内容 数理逻辑、集合论、代数结构、图论,引言,教学内容 第一部分 数理逻辑 第一章 命题逻辑 第二章 谓词逻辑 第二部分 集合论 第三章 集合代数 第四章 二元关系,引言,教学内容 第二部分 集合论 第五章 函数 第六章 集合的基数 第三部分 代数结构 第七章 代数系统 第八章 群论,引言,教学内容 第三部分 代数结构 第九章 环与域 第十章 格与布尔代数,第一部
3、分 数理逻辑,逻辑学 是一门研究思维形式和规律的科学。分为辩证逻辑和形式逻辑两种。思维的形式结构包括了概念判断和推理之间的结构和联系,其中概念是思维的基本单位,通过概念对事物是否具有某种属性进行肯定或否定的回答,就是判断。由一个或几个判断推出另一判断的思维形式就是推理。 数理逻辑 用数学方法研究推理的规律称为数理逻辑。所谓数学方法就是引用一套符号体系的方法,所以数理逻辑又称作符号逻辑。,第一部分 数理逻辑,现代数理逻辑 逻辑演算、逻辑演绎、模型论、证明论、递归函数论、公理化集合论等。 我们要介绍的是数理逻辑中最基本的内容:命题逻辑和谓词逻辑。即一般所谓的古典逻辑。 德国数学家莱布尼茨Leibn
4、iz(现代逻辑的首席创始人);布尔Boole (奠基人,逻辑的数学分析);弗雷格(数论的基础),第一章 命题逻辑,命题逻辑也称命题演算或语句逻辑。它研究以“命题”为基本单位构成的前提和结论之间的可推导关系,研究什么是命题?如何表示命题?怎样由一组前提推导一些结论。,概念,判断,推理,1.1 命题与命题联结词,1.1.1命题 定义1.1:具有确切真值的陈述句(或断言)称为命题(Proposition)。 命题的取值称为真值。真值只有“真”和“假”两种,分别用“T”或“1”和“F”或“0”表示。 注意:命题的真值非真即假,只有两种取值,这样的系统为二值逻辑系统。,1.1 命题与命题联结词,例1-1
5、:命题示例。 (a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数 (d):陈胜起义那天,杭州下雨 (e):较大的偶数都可表为两个质数之和 (f):x+y4 (g):真好啊! (h):x=3 (i):你去哪里? (j):我正在说谎。 注意:由定义知,一切没有判断内容的句子如命令,感叹句,疑问句,祈使句,二义性的陈述句等都不能作为命题。,1.1 命题与命题联结词,例1-2:下列句子哪些是命题,判断命题的真假。 (1):2是素数 (2):北京是中国的首都 (3):这个语句是假的 (4):x+y0 (5):我喜欢踢足球 (6):地球外的星球上也有人 (7):明年国庆节是晴天 (8):把门
6、关上 (9):你要出去吗? (10):今天天气真好啊!,注意 命题一定是通过陈述句来表达;反之,并非一切的陈述句都一定是命题。 命题的真值有时可明确给出,有时还需要依靠环境条件,实际情况,时间才能确定其真值。但其真值一定是唯一确定的。,1.1 命题与命题联结词,1.1 命题与命题联结词,命题可分为两种类型: 简单命题:若一个命题已不能分解成更简单的命题,则该命题叫原子命题或本原命题或简单命题(Simple Proposition) 复合命题(Compound Proposition):可以分解为简单命题的命题,而且这些简单命题之间是通过关联词(如“或者”,“并且”,“不”,“如果 则”,“当且
7、仅当”等)和标点符号复合而构成一个复合命题。 例,合肥是安徽的省会当且仅当鸟会飞。 注意: 命题通常用大写英文字母(可带下标)来表示。,1.1.2 命题联结词 命题通常可以通过一些联结词复合而构成新的命题,这些联结词被称为逻辑联结词。用数学方法研究命题之间的逻辑关系时(也就是在命题演算中),这些联结词可以看作是运算符,因此也叫作逻辑运算符。 常用的联结词有以下5个: 定义1.2:设P是任一命题,复合命题“非P”(或“P的否定”)称为P的否定式(Negation),记作P,“”为否定联结词。 P为真当且仅当P为假。 如:P:2是素数,则P:2不是素数。,1.1 命题与命题联结词,1.1 命题与命
8、题联结词,定义1.3:设P Q是任意两个命题,复合命题“P并且Q”(或“P和Q”)称为P与Q的合取式(Conjunction),记作P Q,“ ”为合取联结词。 P Q为真当且仅当P,Q同为真。 例,P:2是素数,Q:2是偶数。则P Q:2是素数并且是偶数。,1.1 命题与命题联结词,定义1.4:设P Q是任意两个命题,复合命题“P或Q” 称为P与Q的析取式(Disjunction),记作P Q,“ ”为析取联结词。 P Q为真当且仅当P,Q至少一个为真。 例,P:2是素数,Q:2是奇数。则P Q:2是素数或是奇数。,1.1 命题与命题联结词,定义1.5:设P Q是任意两个命题,复合命题“如果
9、P则Q” 称为P与Q的蕴含式(Implication),记作PQ,“”为 蕴含联结词,P称为蕴含式的前提,假设或前件,而Q称为结论式后件。PQ为假当且仅当P为真Q为假。 例,P:G是正方形,Q:G的四边相等,则PQ:如果G是正方形,则G的四边相等。 蕴含式PQ可以用多种方式陈述: “若P,则Q”; “P是Q的充分条件”; “Q是P的必要条件”; “Q每当P”; “P仅当Q”等。,1.1 命题与命题联结词,给定命题PQ,我们把QP,PQ, QP分别叫作命题PQ的逆命题,反命题和逆反命题。 定义1.6:设P,Q是任意两个命题,复合命题“P当且仅当Q”称为P与Q的等价式(Equivalence),记
10、作PQ,“”为等价联结词。 PQ为真当且仅当P,Q同为真假。 例如,P:合肥是安徽省会,Q:鸟会飞,则PQ:合肥是安徽省会当且仅当鸟会飞。 如果PQ是真,则PQ和QP是真,反之亦然,因此PQ也读作“P是Q的充要条件”或“P当且仅当Q”。,1.1 命题与命题联结词,五个联结词的真值表,1.1 命题与命题联结词,一般约定: a):运算符(联结词)结合力强弱顺序为:, ,;凡符合此顺序的,括号可省略。 b):相同的运算符,从左到右次序计算时,括号可省去。 c):最外层括号可省。 如,(P Q) R) (R P)Q) (P QR) R PQ,例1.3:符号化下列命题。 a):他既有理论知识又有实践经验
11、 b):i. 如果明天不是雨夹雪则我去学校 ii. 如果明天不下雨并且不下雪,则我去学校 iii. 如果明天下雨或下雪则我不去学校 iv. 明天我将风雨无阻一定去学校 v. 当且仅当明天不下雪并且不下雨时我才去 学校,1.1 命题与命题联结词,1.1 命题与命题联结词,c):说小学生编不了程序,或说小学生用不了个人计算机,那是不对的。 d):若不是他生病了或出差了,我是不会同意他不参加学习的。 e):如果我上街了,我就去书店看看,除非我很累。,1.1 命题与命题联结词,注意: 是自然语言中的“非”“不” 和“没有”等的逻辑抽象 是自然语言中的“并且” “既 又” “且” “和”等的逻辑抽象 是
12、自然语言中的“或”和“或者”等的逻辑抽象;但“或”有“可兼或” “不可兼或” “近似或”三种 PQ是自然语言中的“只要P,就Q” “因为P,所以Q” “P仅当Q”等的逻辑抽象,(5) 是自然语言中的“充分必要条件”和“当且仅当”等的逻辑抽象 (6)联结词连接的是两个命题真值之间的联结,而不是命题内容之间的连接,因此复合命题 的真值只取决于构成他们的各原子命题的真 值 (7) ,具有对称性,而,没有 (8) , 与计算机中的与门,或门,非门电路是相对应的 看P6-7 例1.4-1.5,P9 例1.7,1.1 命题与命题联结词,1.2.1:命题公式 就像在代数学里引入变量一样,为了更广泛的应用命题
13、演算,在数理逻辑中也引入了命题变量。使得在研究时,只需考虑命题的真值,而不知晓命题的具体含义。 定义1.7:一个特定的命题是一个常值命题(Constant Proposition),它不是具有值“T”(“1”),就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题,常称它为命题变量(或命题变元、命题变项)(Proposition Variable)。命题变量无具体的真值,它的值域是集合T,F(或1,0)。,1.2 公式的解释与真值表,原子命题在不指派真值时称为命题变元,而复合命题由原子命题和联结词构成,可以看作是命题变元的函数,且该函数的值仍为“真”或“假”,可以称
14、为真值函数(True Value Function)或命题公式。但不是说原子命题和联结词的一个随便的组合都可以为命题公式,我们用递归的方法来定义命题公式。,1.2 公式的解释与真值表,1.2 公式的解释与真值表,定义1.8:命题公式 (1).命题变元本身是一个公式; (2).如果P是公式,则P也是公式; (3).如果P,Q是公式,则(PQ) PQ PQ PQ也是公式; (4).命题公式(Prepositional Formula)是仅由有限步使用规则(1)(3)后产生的结果。公式常用符号GH等表示。 例,( PQ),(P(P Q) ,(PQ) (R Q) (P R)是命题公式 (P Q ) Q
15、), (P Q, ( PQ (R, PQ 不是命题公式,注意: 如果G是含有n个命题变元 P1, P2, ,Pn的公式,通常记为G(P1, ,Pn)或简记为G。 原子命题变元是最简单的(合式)公式,也叫原子(合式)公式。 合成公式没有真值,只有对其变元进行指派后才有真值。 合成公式无限多。,1.2 公式的解释与真值表,1.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); c). A
16、=BC,其中B,C的层次同b; d). A=BC,其中B,C的层次同b; e). A=BC,其中B,C的层次同b; 从图论的观点来看每个多层公式可以用一个“树”来表示。,1.2 公式的解释与真值表,1.2.2:公式的解释与真值表 公式本身没有真值,只有在对其所有命题变元指定真值后才变成一个具有真值的命题。 定义1.9:设命题变元P1, P2, ,Pn是出现在公式G中的所有命题变元,指定P1, P2, ,Pn一组真值,则这组这组称为G的一个解释(Explanation),并记作I。 一般来说,若有n个命题变元,则应有2n个不同的解释。 定义1.10:公式G在其所有可能的解释下所取真值的表,称作G
17、的真值表(Truth)。,1.2 公式的解释与真值表,例1.4:5个联结词的真值表(T:1,F:0),1.2 公式的解释与真值表,例1.5:设公式G= (PQ) R )(PQ),其中P,Q,R是G的命题变元,则其真值表如下:,1.2 公式的解释与真值表,1.2.3:一些特殊的公式 例1.6:考虑:G1= (PQ) P; G2=(PQ) P; G3= (P Q) (PQ) 公式G1对所有可能的解释都具有“真”值,G3对所有解释都具有“假”值,公式G2则具有“真”和“假”值。,1.2 公式的解释与真值表,1.重言式: 定义1.11: (1). 公式G称为永真公式(重言式),如果在它的所有解释下都为
18、“真”; (2). 公式G称为可满足的,如果它不是永假的; (3). 公式G称为永假公式(矛盾式), 如果在它的所有解释下都为“假”;有时也称永假公式为不可满足公式。 注意: (1). 重言式的否定是矛盾式,矛盾式的否定是重言式,所以研究其一就可以了;,1.2 公式的解释与真值表,(2). 重言式的合取,析取,蕴含,等值等都是重言式; (3). 重言式中有许多非常有用的恒等式叫永真蕴含式。 对任意的公式,判定其是否为永真公式,永假公式,可满足公式的问题称为给定公式的判定问题。由于一个命题公式的解释的数目是有穷的,所以命题逻辑的判定问题是可解的,即命题的永真,永假性是可判定的。其判定方法有真值表
19、法和公式推演法。,1.2 公式的解释与真值表,例1.7: 判定公式: (1).(PQ) ( PQ); (2). (PQ)P) Q; (3). P(Q R)。 2.恒等式: 定义1.12:公式G,H,如果在其任意解释下,其真值相同,则称G是H的等价式(Equivalent)或称G恒等于H,记作GH。,1.2 公式的解释与真值表,定理1.1:对于公式G和H, GH的充分必要条件是公式G H是重言式。 证明: 必要性:假定GH,则G和H在其任意解释I下,或同为真或同为假,由“”的意义知, G H在任意解释I下,其真值为真,即G H为重言式; 充分性:假设公式G H是重言式,I是它的任意解释,在I下,
20、 G H为真,因此,G,H或同为真或同为假,由于I的任意性,故有GH。,1.2 公式的解释与真值表,注意与不同: (1). :逻辑等价关系, G H不是命题公式; (2). :逻辑联结词, G H是命题公式; (3).计算机不能判断G,H是否逻辑等价,而可计算G H是否为重言式。,1.2 公式的解释与真值表,常用逻辑恒等式(P,Q,R为任意命题,T为真命题,F为假命题):,1.2 公式的解释与真值表,1.2 公式的解释与真值表,3.永真蕴含式: 定义1.13:若AB是一永真式,那么称为永真蕴含式,记为AB,读作A永真蕴含B 常用的永真蕴含式,1.2 公式的解释与真值表,4.恒等式和永真蕴含式的
21、两个性质: (1).若AB, BC,则AC;若A=B, B=C,则A=C. (即逻辑恒等和永真蕴含都是可传递的) 证明:AB, BC,即AB, BC为重言式,对任意的解释I,A和B,B和C的真值相同,则A和C的真值相同。 A C为重言式,即AC; A=B, B=C,即AB, BC为真; (AB)(BC)为真,由公式I6: AC为重言式,即A=C。,1.2 公式的解释与真值表,(2).若A=B, A=C,则A=BC. 证明:A为真时,B,C都为真,则BC也为真,即ABC为真;A为假时,则不管BC是真还是假时,ABC均为真,因此A=BC。,1.2 公式的解释与真值表,1.2.4:代入规则和替换规则
22、 当一个公式是永真式或永假式时,其公式的真值完全跟随其命题变元的真值的变化而变化,因此,当用其他公式来取代公式中的命题变元时,不会改变公式的永真性和永假性 定理1.2(代入定理) :设G(P1, ,Pn)是一个命题公式,其中P1, ,Pn是命题变元,G1(P1, ,Pn), Gn(P1, ,Pn)为任意的命题公式,此时若G是永真公式或永假公式,则用G1取代P1,Gn取代Pn后,得到的新的命题公式G(G1,Gn) G(P1, ,Pn)也是一个永真公式或永假公式。,1.2 公式的解释与真值表,例1.8:设G(P, Q) = (PQ) P;用H(P, Q) =(P Q);S(P, Q) =(P Q)
23、代入G验证代入定理。 定理1.3(替换定理) :设G1是G的子公式,H1是任意的命题公式,在G中凡出现G1处都以H1替换后得到的新的命题公式H,若G1H1,则GH。 例1.9:简化开关电路:,S,S,R,Q,P,P,1.2 公式的解释与真值表,例1.10:将下面程序语言进行化简: if A then if B then X else Y else if B then X else Y 例1.11:简化逻辑电路:,R,Q,P,1.2 公式的解释与真值表,例1.12:求证: (1).P(PQ)Q)是永真公式; (2).P(QR)(PQ)R; (3).(P(QR)(PQ R)P; (4).(P(QR
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学
链接地址:https://www.31doc.com/p-2608330.html