离散数学(5)省公开课一等奖全国示范课微课金奖

1/491/60离散数学

DiscreteMathematics计算机科学与工程学院袁夏E-mail:yxlucker@163.com第1页2/49课程说明课程类型：计算机科学专业基础课学分：4.5学分教学方式：理论教学考评方式：闭卷笔试成绩评定：平时成绩20%，期末成绩80%教材与教学参考书：（1）离散数学（第2版），朱保平，金忠等，北京理工大学出版社，（2）离散数学概念、题解与自测，朱保平，金忠等，北京理工大学出版社，第2页3/49课件与作业参考答案请进入邮箱文件中心下载用户名：cs_lisanshuxue@163.com密码：lisanshuxue

课件每次课后上传更新，作业参考答案不定时上传更新第3页4/49第4页5/49离散数学——研究离散数量关系和离散结构数学模型数学分支统称古代数学——整数、整数比近代数学——连续数量概念（实数），处理连续数量关系数学（微积分）Discrete?第5页6/49对计算机专业系统知识辐射作用胡慧君，刘茂福，武汉科技大学计算机科学与技术学院

《计算机光盘软件与应用》188-189,第6页7/49主要内容数理逻辑(1-5)集合论(6-8)图论(9-10)代数(11-12)没有预修课程。学习数理逻辑时会包括一点中学阶段学习集合知识。第7页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年提出一个抽象计算模型（数学逻辑机），引入图灵机——一个理想计算机第8页9/49数理逻辑学习“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫话，我就不会犯这么多错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁话，我就去学逻辑。”

——Edsger.W.Dijkstra1972年Turing奖取得者

(1930-)带权图最短通路算法第9页10/49数理逻辑第一章命题演算基础第二章命题演算推理理论第三章谓词演算基础第四章谓词演算推理理论第五章递归函数论第10页11/49大数据技术：情感分类现在是晚上十一点，天很暖。假如我考试经过了，那么我很高兴。假如我高兴，那么阳光灿烂。并非假如只有考试经过才能心情好那么我心情好。？QQ心情谜语第11页12/49

(一)命题定义凡是能够判断真假陈说句称为命题。命题值

真,用T(或1)表示假,用F(或0)表示第12页13/49例：以下句子都是命题吗？雪是白。雪是黑。好大雪啊！

8大于12。

1+101=110。

✔✔✔✔✘第13页14/49例：以下句子都是命题吗？21世纪末，人类将住在月球。大于2偶数可表示成两个素数之和。X<0。假如x大于3，则x2大于9。我正在说谎。✔✔✔✘✘悖论第14页15/49命题真假问题在数理逻辑学习中，不能去纠缠各种详细命题真假问题，而是将命题当成数学概念来处理，看成一个抽象形式化概念，把命题定义成非真必假陈说句．第15页16/49带联结词命题今晚我看书。今晚我玩网络游戏。今晚我不看书。今晚我不玩网络游戏。今晚我不看书，我玩网络游戏。今晚我看书，或者我玩网络游戏。否定而且或者第16页17/49(二)原子命题和复合命题原子命题——不可剖开或分解为更简单命题命题，也称为简单命题。复合命题——由原子命题利用联结词组成命题约定用大写字母表示第17页18/49复合命题例子（1）并非雪是白。（2）今晚我看书或者去看电影。（3）假如天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5）2是偶数且3也是偶数。

（6）你去了学校，我去了工厂。第18页19/49(三)命题变元当P表示任意命题时，称P为命题变元。字母P命题——详细、特定命题，有确定真值命题变元——任意命题，没有确定真值

第19页20/49命题变元变域一个命题变元P可能取值有两种情况：真T，或假F。P变域={T，F}两个命题变元P、Q可能取值有几个情况？怎么表示这些情况？P、Q变域={？}第20页21/491.1.2联结词否定词﹁

合取词∧析取词∨蕴含词

等价词

第21页22/49﹁P读作“非P”

，是指命题：“P否定”。P

PTFFT真值表

例P：雪是黑色。

﹁P：并非雪是黑色。雪不是黑色。第22页23/49否定联结词使用标准将真命题变成假命题，将假命题变成真命题。但这并不是简单随意加个不字就能完成。例P:这些人都是学生。

﹃P：这些人不都是学生

≠

这些人都不是学生

第23页24/49P∧Q读作“P合取Q”，是指命题：“P而且Q”。PQP

QTTTTFFFTFFFF

例

P:今天刮风。

Q：今天下雨。

P∧Q：今天刮风，下雨。真值表第24页25/49P∨Q读作“P析取Q”

，是指命题：“P或者Q”。PQP

QTTTTFTFTTFFF例

P:他会英语。

Q：他会法语。

P∨Q：他会英语或者法语。

第25页26/49可兼“或”——不可兼“或”PQP∨QTTTTFTFTTFFF他会英语或法语。PQP∨Q

(P∧﹁

Q)∨(﹁P∧Q)TTTFTFTTFTTTFFFF今晚我去看电影，或去看球赛。第26页27/49P→Q读作“P蕴含Q”

，是指命题：“假如P，则Q”。例假如1+1=3，则雪是黑。PQP

QTTTTFFFTTFFT真值表第27页28/49注1.前件为假时，蕴含式命题为真假如蕴含前件P是假命题，那么不论Q是什么命题，命题P→Q在逻辑中都被认为是真命题。第28页29/49注2.蕴含式前件、后件能够毫不相关在日常语言中“假如……则……”所联结句子之间表现是一个因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题能够是毫不相关。例

P：我心情好。Q：1=2。

P→Q：假如我心情好，那么1＝2。第29页30/49灵活叙述蕴含词例子设R：天下雨，

H：我回家，试表示以下命题：只要天下雨，我就回家。只有天下雨，我才回家。除非天下雨，不然我不回家。仅当日下雨，我才回家。R→HH→R或﹃R→﹃H

能够将蕴含看作充分条件.假如A是充分条件前件,B是后件,那么A蕴含B意思就是有A必有B第30页31/49P

Q读作“P等价于Q”,是指命题：“P当且仅当Q”。PQP

QTTTTFFFTFFFT例

P:2+3＝5

Q:e是无理数

P

Q

：2+3＝5充要条件是e是无理数

第31页32/49是否命题？是否复合命题？例Tom和John是弟兄。例

假如x>0，则x2>0。例

若两圆面积相等，则它们半径相等，反之亦然。

✘✔✘✔✔✔第32页33/49真值函项定义——以真假为定义域并以真假为值域函数（映射）。{T,F}{T,F}2={(T,T),(T,F),(F,T),(F,F)}第33页34/49一元真值函项——一元联结词{T,F}{T,F}fPf0(P)f1(P)f2(P)f3(P)

TTTFFFTFTF永真恒等否定

P永假第34页35/49二元真值函项——二元联结词f4为析取

f2为蕴含f8为等价f11为合取

f14为或非↓f1为与非

第35页36/49三元联结词共有多少个？f0f1f2…………f?(0,0,0)010…………1(0,0,1)001…………1(0,1,0)000…………1(0,1,1)000…………1(1,0,0)000…………1(1,0,1)000…………1(1,1,0)000…………1(1,1,1)000…………128第36页37/491.1.3合式公式合式公式为以下定义式子，简称为公式：任何命题变元均是公式；假如P为公式，则

P为公式；假如P，Q为公式，则

P

Q,P

Q,P

Q,P

Q为公式；当且仅当经过有限次使用①、②、③所组成符号串才是公式，不然不为公式。Wellformedformulae第37页38/49n元公式——有n个不一样命题变元公式。例一元公式P(PP)二元公式(P

Q)

(PQ)三元公式((P

Q)

R)

(PQ)第38页39/49优先级约定∧、∨、、

优先级相同

﹃

比其它联结词有更高优先级括号（）内运算优先第39页40/49命题符号化分析出简单命题，符号化用联结词联结简单命题例将下述命题符号化:

假如只有知道希腊文才能了解柏拉图，那么我不了解柏拉图解：令P表示“我知道希腊文”，Q表示“我了解柏拉图”则原句符号化为(Q

P)

Q第40页41/49真值例令P：北京比天津人口多。

Q：2+2＝4。

R：乌鸦是白色。

求以下公式真值：

(1)(Q∨R)→(P→

R)

(2)(

P∨R)

(P∧

R)

第41页42/49真值表及其应用？P:我考试经过Q:我心情好

((QP)Q)TTFTFTFTFFFT并非假如只有考试经过就能心情好那么我心情好。我心情不好。第42页43/49真值表及其应用？P:我考试经过Q:我心情好

((QP)

Q)TTTTFFFTFFFF并非假如只有考试经过才能心情好那么我心情不好。我心情好，而且考试经过。第43页44/491.2真假性定义：设n元公式

中全部不一样命题变元为

P1,P2,

…,Pn

问题：n元公式

有多少个完全解释？1.2.1解释假如对每个命题变元均给予一个确定值，则称对公式

给了一个完全解释；假如仅对部分变元给予确定值，则称对公式

给了一个部分解释。第44页45/49例考查公式

=(P

Q)

R

PQR(PQ)R真值(P,Q,R)TTTT完全解释TTFF完全解释TT*?部分解释F**T第45页46/49成真解释与成假解释定义：对于任何公式

，PQR(PQ)R真值(P,Q,R)TTTT成真解释TTFF成假解释TT*?F**T成真解释凡使得

取值真解释，均称为

成真解释。凡使得

取值假解释，均称为

成假解释。第46页47/49例考查公式

=(P

Q)

R

PQR(PQ)R真值(P,Q,R)TTTT1个成真解释TTFF1个成假解释TT*?1个成真解释1个成假解释F**T?个成真解释*F*T第47页48/49永真公式与永假公式定义：假如一个公式全部完全解释例

永假公式P∧

P永真公式P∨

PP

P(P

Q)

(

Q

P)均为成真解释，则称该公式为永真公式或称为重言式。均为成假解释，则称该公式为永假公式或称为予盾式。第48页49/49可满足公式与非永真公式定义：假如一个公式例P

Q可满足公式，非永真公式PQ可满足公式，非永真公式存在成真解释，则称该公式为可满足公式；存在成假解释，则称该公式为非永真公式。第49页50/601.2.2等价公式逻辑等值(等价)概念几组主要等值(等价)公式利用等值(等价)公式，对公式进行化简，以求解公式成真解释、成假解释第50页51/60逻辑相等=定义给定两个公式

和

，设P1，P2，……，Pn为

和

全部命题变元，那么

和

有2n个解释。假如对每个解释，

和

永取相同真假值，则称

和

是逻辑等价(等值、相等)，记为

=

。真值表相同第51页52/60例问：PP=

P?从真值表，能够看出：PP=

PP

PPPTFTF=FFTFT=T考查真值表以下第52页53/60等值公式第53页54/60等值公式第54页55/60⑥等值变换、否定深入公式第55页第56页57/60原命题、逆命题、否命题、逆否命题设原命题为蕴含式：PQ，则逆命题为：QP，

否命题为：

P

Q，

逆否命题为：

Q

P，于是PQ=QPQP=PQ真值表法等值变换法第57页58/60例判断以下公式类型

Q∨((P∨Q)∧P)解:Q∨

((P∨Q)∧P) =Q∨(

(P∨Q))∨

P =Q∨(P

∧

Q))∨

P=(Q∨P)∨P

=Q

∨(P∨P)

=Q∨T=

T所以，它是永真。

第58页59/60例判断以下公式类型

(P∨P)((Q∧Q)∧R)解:(P∨P)((Q∧Q)∧R) =T(F∧R) =F∧R =F所以，它是永假。第59页60/60例((QP)Q)=(PQ)

Q)记P:我考试经过,Q:我心情好PQ

((QP)Q)(PQ)

Q)TTFFTFTTFTFFFFTT并非假如只有考试经过才能心情好那么我心情好=假如只要考试经过就能心情好那么我心情不好也能够利用等值公式证实。第60页61/60成真解释和成假解释求解方法（1）否定深入：即把否定词一直深入至命题变元上；（2）部分解释：选定某个出现次数最多变元对它作真或假两种解释从而得公式；（3）化简；（4）依次类推，直至产生公式全部解释。前提是公式中没有蕴含词、等价词第61页62/60例(p7)试判定公式

(PQ)

((

Q

P)

R)

永真性和可满足性。解：对P=F进行解释并化简。

原式=

(FQ)

(