离散数学课件

1/49,1/60,离散数学DiscreteMathematics,计算机科学与工程学院袁夏,E-mail:yxlucker,2/49,课程说明,课程类型：计算机科学专业基础课学分：4.5学分教学方式：理论教学考核方式：闭卷笔试成绩评定：平时成绩20%，期末成绩80%教材与教学参考书：（1）离散数学（第2版），朱保平，金忠等，北京理工大学出版社，2014（2）离散数学概念、题解与自测，朱保平，金忠等，北京理工大学出版社，2009,3/49,课件与作业参考答案请进入邮箱文件中心下载用户名：cs_lisanshuxue密码：lisanshuxue课件每次课后上传更新，作业参考答案不定期上传更新,4/49,5/49,离散数学,研究离散数量关系和离散结构数学模型的数学分支的统称,古代数学整数、整数的比近代数学连续的数量概念（实数），处理连续数量关系的数学（微积分）,Discrete?,6/49,对计算机专业系统知识的辐射作用,胡慧君，刘茂福，武汉科技大学计算机科学与技术学院计算机光盘软件与应用188-189,2013,7/49,主要内容,数理逻辑(1-5),集合论(6-8),图论(9-10),代数(11-12),没有预修课程。学习数理逻辑时会涉及一点中学阶段学习的集合知识。,8/49,数理逻辑数学化的逻辑学,德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G.Boole(1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。英国B.Russell(1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。英国AlanM.Turing(1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机一种理想的计算机,9/49,数理逻辑的学习,“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。”Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002),带权图的最短通路算法,10/49,数理逻辑,第一章命题演算基础第二章命题演算的推理理论第三章谓词演算基础第四章谓词演算的推理理论第五章递归函数论,11/49,大数据技术：情感分类,现在是晚上十一点，天很暖。如果我考试通过了，那么我很快乐。如果我快乐，那么阳光灿烂。,并非如果只有考试通过才能心情好那么我心情好。,？,QQ心情谜语,12/49,(一)命题定义,凡是可以判断真假的陈述句称为命题。,13/49,例：下列句子都是命题吗？,雪是白的。雪是黑的。好大的雪啊！8大于12。1+101=110。,14/49,例：下列句子都是命题吗？,21世纪末，人类将住在月球。大于2的偶数可表示成两个素数之和。X0，则x20。例若两圆面积相等，则它们的半径相等，反之亦然。,33/49,真值函项的定义,以真假为定义域并以真假为值域的函数（映射）。,T,F,T,F2=(T,T),(T,F),(F,T),(F,F),34/49,一元真值函项一元联结词,Pf0(P)f1(P)f2(P)f3(P)TTTFFFTFTF,永真,恒等,否定P,永假,35/49,二元真值函项二元联结词,f4为析取,f2为蕴含,f8为等价,f11为合取,f14为或非,f1为与非,36/49,三元联结词共有多少个？,28,37/49,1.1.3合式公式,合式公式为如下定义的式子，简称为公式：任何命题变元均是公式；如果P为公式，则P为公式；如果P，Q为公式，则PQ,PQ,PQ,PQ为公式；当且仅当经过有限次使用、所组成的符号串才是公式，否则不为公式。,Wellformedformulae,38/49,n元公式,有n个不同的命题变元的公式。,例,39/49,优先级约定,、优先级相同比其它联结词有更高的优先级括号（）内的运算优先,40/49,命题符号化,分析出简单命题，符号化用联结词联结简单命题,例将下述命题符号化:,如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图,解：令P表示“我懂得希腊文”，Q表示“我了解柏拉图”则原句符号化为(QP)Q,41/49,真值,例令P：北京比天津人口多。Q：2+24。R：乌鸦是白色的。求下列公式的真值：(1)(QR)(PR)(2)(PR)(PR),42/49,真值表及其应用,？,并非如果只有考试通过就能心情好那么我心情好。,我心情不好。,43/49,真值表及其应用,？,并非如果只有考试通过才能心情好那么我心情不好。,我心情好，并且考试通过。,44/49,1.2真假性,定义：设n元公式中所有的不同的命题变元为P1,P2,Pn,问题：n元公式有多少个完全解释？,1.2.1解释,如果对每个命题变元均给予一个确定的值，则称对公式给了一个完全解释；如果仅对部分变元给予确定的值，则称对公式给了一个部分解释。,45/49,例考察公式=(PQ)R,46/49,成真解释与成假解释,定义：对于任何公式，,凡使得取值真的解释，均称为的成真解释。凡使得取值假的解释，均称为的成假解释。,47/49,例考察公式=(PQ)R,48/49,永真公式与永假公式,定义：如果一个公式的所有完全解释,例,均为成真解释，则称该公式为永真公式或称为重言式。均为成假解释，则称该公式为永假公式或称为予盾式。,49/49,可满足公式与非永真公式,定义：如果一个公式,例PQ可满足公式，非永真公式PQ可满足公式，非永真公式,存在成真解释，则称该公式为可满足公式；存在成假解释，则称该公式为非永真公式。,50/60,1.2.2等价公式,逻辑等值(等价)的概念几组重要的等值(等价)公式利用等值(等价)公式，对公式进行化简，以求解公式的成真解释、成假解释,51/60,逻辑相等=,定义给定两个公式和，设P1，P2，Pn为和的所有命题变元，那么和有2n个解释。如果对每个解释，和永取相同的真假值，则称和是逻辑等价(等值、相等)的，记为=。,真值表相同,52/60,例问：PP=P?,从真值表，可以看出：PP=P,考察真值表如下,53/60,等值公式,54/60,等值公式,55/60,等值变换、否定深入公式,57/60,原命题、逆命题、否命题、逆否命题,设原命题为蕴含式：PQ，则逆命题为：QP，否命题为：PQ，逆否命题为：QP，于是,PQ=QPQP=PQ,真值表法等值变换法,58/60,例判断下列公式的类型Q(PQ)P),解:Q(PQ)P)=Q(PQ)P=Q(PQ)P=(QP)P=Q(PP)=QT=T所以，它是永真的。,59/60,例判断下列公式的类型(PP)(QQ)R),解:(PP)(QQ)R)=T(FR)=FR=F所以，它是永假的。,60/60,例(QP)Q)=(PQ)Q),记P:我考试通过,Q:我心情好,并非如果只有考试通过才能心情好那么我心情好=如果只要考试通过就能心情好那么我心情不好,也可以利用等值公式证明。,61/60,成真解释和成假解释的求解方法,（1）否定深入：即把否定词一直深入至命题变元上；（2）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而得公式；（3）化简；（4）依次类推，直至产生公式的所有解释。,前提是公式中没有蕴含词、等价词,62/60,例(p7)试判定公式(PQ)(QP)R)的永真性和可满足性。,解：对P=F进行解释并化简。原式=(FQ)(QF)R)=F(QR)=QR当Q=T时，原式=TR=R，于是，当R=T时，原式=F；当R=F时，原式=T。因此,存在成真解释(P,Q,R)=(F,T,F);存在成假解释(P,Q,R)=(F,T,T)。故公式可满足但非永真。,63/60,例试求下列公式的成真解释和成假解释(PQ)(Q(RP),解:当P=T时,原式=(TQ)(Q(RT)=Q(Q(R)=QR当P=F时,原式=(FQ)(Q(RF)=T(QF)=Q由上可知:公式不是永真公式,是可满足的。并且,成真解释为(P,Q,R)=(T,F,F),(F,T,*)；成假解释为(T,T,T),(T,F,T),(T,T,F),(F,F*)。,64/49,作业01,教材P161.1(1)(2)(3)(4)(5)补1.求下列公式的真值表，判断其类型:（1）P(QP)（2