离散数学数理逻辑

离散数学数理逻辑1第一页，共八十六页，编辑于2023年，星期一教材与参考资料教材：《离散数学》（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：《离散数学》，刘玉珍、刘咏梅编，武汉大学出版社《DiscreteMathematicalStructures》(SixthEdition)，

BernardKolman,FobertC.BusbyandSharonRoss，高等教育出版社有影印版、译本《DiscreteMathematicsandItsApplications》(SixthEdition)，[美]KennethH.Rosen，机械工业出版社影印版、译本2第二页，共八十六页，编辑于2023年，星期一课程主要内容数理逻辑集合论图论代数系统*3第三页，共八十六页，编辑于2023年，星期一目的、意义和要求研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7章重点第9、14章备选第8、11章自学第10、12、13章不要求

4第四页，共八十六页，编辑于2023年，星期一学习要求1、课堂要求：按时上课认真听讲2、课外要求：复习(每次课后，安排半个小时)

认真、按时完成作业(每次课后，安排1个小时)5第五页，共八十六页，编辑于2023年，星期一学习考查方法1、出勤率：10%不定期检查出勤情况2、作业完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共5次4、期末考试（闭卷）：60%6第六页，共八十六页，编辑于2023年，星期一第一篇数理逻辑

第1章导论数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用7第七页，共八十六页，编辑于2023年，星期一（1）定义§1.1数理逻辑的概念数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析符号化研究公式间的关系

推导、演算

8第八页，共八十六页，编辑于2023年，星期一（2）方法

引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为： 甲：C第一，B第二 乙：C第二，D第三 丙：A第二，D第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？1.引入pi,qi,ri,si分别表示“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系

（1）(r1∧┐q2)∨(┐r1

∧q2)1

（2）(r2∧┐s3)∨(┐r2

∧s3)1（3）(p2∧┐s4)∨(┐p2

∧s4)13.通过演算规则，得出结果9第九页，共八十六页，编辑于2023年，星期一（3）内容谓词逻辑命题逻辑10第十页，共八十六页，编辑于2023年，星期一（4）分支模型论证明论公理集合论递归论11第十一页，共八十六页，编辑于2023年，星期一§1.2数理逻辑的发展简史创立阶段起源阶段完善阶段

发展历史12第十二页，共八十六页，编辑于2023年，星期一起源阶段

德国数学家、哲学家G.Leibniz（1646~1716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。13第十三页，共八十六页，编辑于2023年，星期一创立阶段英国数学家G.Bool于1847年发表《逻辑的数学分析》，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。德国数学家G.Frege于1879年在《概念的演算》一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。14第十四页，共八十六页，编辑于2023年，星期一完善阶段英国逻辑学家A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了《数学原理》中，使数理逻辑成为了一门专门的学科。

20世纪30年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。15第十五页，共八十六页，编辑于2023年，星期一§1.3数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计16第十六页，共八十六页，编辑于2023年，星期一第2章命题逻辑2.1命题逻辑基本概念

2.2命题逻辑等值演算

2.3范式2.4命题逻辑推理理论

17第十七页，共八十六页，编辑于2023年，星期一2.1

命题逻辑基本概念

2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(¬,,,,)

2.2.2命题公式及其分类命题公式及其赋值真值表命题公式的分类

18第十八页，共八十六页，编辑于2023年，星期一§2.1.1命题与联结词1、命题及相关概念（1）命题的定义两者必居其一且只居其一——二值逻辑命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。命题：一个具有真假意义的陈述句。什么是真值：只包含真/假两个值的量。T/1—真F/0—假19第十九页，共八十六页，编辑于2023年，星期一注意：（1）感叹句、祈使句、疑问句都不是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题20第二十页，共八十六页，编辑于2023年，星期一中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。例1判断下列个自然语言是否是命题21第二十一页，共八十六页，编辑于2023年，星期一（2）几个基本概念真命题与假命题命题变元与命题常元真命题:真值为真的命题假命题:真值为假的命题若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。22第二十二页，共八十六页，编辑于2023年，星期一例2真命题假命题真值不确定疑问句感叹句祈使句悖论(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题真值确定,但未知

下列句子中哪些是命题？并指出命题的真值。(1)北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.23第二十三页，共八十六页，编辑于2023年，星期一（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级2.联接词24第二十四页，共八十六页，编辑于2023年，星期一（1）简单命题与复合命题简单命题(原子命题):简单陈述句构成的命题。简单命题的符号化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。

例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q

又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q25第二十五页，共八十六页，编辑于2023年，星期一（2）联结词的定义否定词（┐）定义2.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词,并规定p为真当且仅当p为假。例如p:2是合数,p:2不是合数。p为假,p为真。26第二十六页，共八十六页，编辑于2023年，星期一合取词（∧

）定义2.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词,并规定

p∧q为真当且仅当p与q同时为真.例如p:2是偶数,q:2是素数,p∧q:表示的含义是2是偶素数。

因为p为真,q也为真，所以p∧q为真。27第二十七页，共八十六页，编辑于2023年，星期一例3

将下列命题符号化.解：记p:王晓用功,q:王晓聪明(1)p∧q(2)p∧q(3)q∧p(4)记r:张辉是三好生,s:王丽是三好生,r∧s(5)简单命题,记

t:张辉与王丽是同学(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.28第二十八页，共八十六页，编辑于2023年，星期一析取词（∨）定义2.3设p、q为命题，复合命题“p或q”称作p与q的析取式，记作p∨q,∨称作析取联结词,并规定p∨q为假当且仅当p与q同时为假。例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为p∨q。29第二十九页，共八十六页，编辑于2023年，星期一相容或与排斥或析取词表示的是相容或，即p

和q

均为真时(p∨q)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p

和q

不能同时为真。例如这件事由张三和李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(p∧

q)∨(p∧q)30第三十页，共八十六页，编辑于2023年，星期一例4

将下列命题符号化，并指出其真值解：记p:2是素数,q:3是素数,r:4是素数,s:6是素数(1)p∨r,(2)

p∨q,(3)r∨s,(4)记t:元元拿一个苹果,u:元元拿一个梨真值:1真值:1真值:0(t∧u)∨(t∧u)(5)记v:王晓红生于1975年,w:王晓红生于1976年(v∧w)∨(v∧w)又可形式化为v∨w(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.31第三十一页，共八十六页，编辑于2023年，星期一蕴涵词（）定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为pq32第三十二页，共八十六页，编辑于2023年，星期一蕴涵词的其它表述方式pq的逻辑关系:q为p的必要条件,p为q的充分条件。“如果p,则q”的多种表述方式：若p,就q

只要p,就qp仅当q

只有q

才p除非q,才p

除非q,否则非p当p为假时，pq为真(不管q为真,还是为假)33第三十三页，共八十六页，编辑于2023年，星期一例5

设p:天冷,q:小王穿羽绒服，将下列命题符号化

注意：

pq与qp

等值（真值相同）pqpqqp或pqpqqp

qppq或qpqp(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.34第三十四页，共八十六页，编辑于2023年，星期一等价词（）定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假。

pq的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:pq35第三十五页，共八十六页，编辑于2023年，星期一例6

求下列复合命题的真值：1011(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝5当且仅当美国位于非洲.36第三十六页，共八十六页，编辑于2023年，星期一分析找出简单命题用字母表示简单命题用联接词联接命题符号命题符号化的一般规则37第三十七页，共八十六页，编辑于2023年，星期一分析找出简单命题用字母表示简单命题用联接词联接命题符号解令p:我上街

q:我累

r:我去书店看看则可符号化为：（pq)r例7

将下列命题符号化：如果我上街并且我不累，我就去书店看看。简单命题：我上街。我累。我去书店看看。38第三十八页，共八十六页，编辑于2023年，星期一例8试将下列命题符号化：如果你不看电影，那么我也不看电影小王一边吃饭，一边看书解:（1）设p：你看电影，q：我看电影，则：

p

q（2）设p：小王吃饭，q：小王看书，则：

pq39第三十九页，共八十六页，编辑于2023年，星期一（3）联结词的优先级联结词优先级:(),,,,,同级按从左到右的顺序进行40第四十页，共八十六页，编辑于2023年，星期一1、分析下列各命题的真值（1）2+2=4当且仅当3是奇数（2）2+2=4当且仅当3不是奇数（3）2+2≠4当且仅当3是奇数（4）2+2≠4当且仅当3不是奇数2、将下列命题符号化（1）小王是游泳冠军或者百米赛跑冠军（2）小王现在在宿舍或者在图书馆（3）选小王或者小李中的一人当班长（4）如果我上街，我就去书店看看，除非我很累课堂练习（1）41第四十一页，共八十六页，编辑于2023年，星期一课堂练习（2）3、将下列命题符号化（1）李平既聪明又用功（2）李平虽然聪明，但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功4、将下列命题符号化（1）只要不下雨，我就骑自行车上班（2）只有不下雨，我才骑自行车上班（3）若2+2=4，则太阳从东方升起（4）若2+2≠4,则太阳从东方升起42第四十二页，共八十六页，编辑于2023年，星期一§2.1.2合式公式及其分类1.命题语言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分类43第四十三页，共八十六页，编辑于2023年，星期一1.命题语言的字母表命题语言的字母表：命题常元：T,F(或1，0)命题变元：p1,p2,…,pn联接词：┐，∧，∨，→，辅助符号：（）44第四十四页，共八十六页，编辑于2023年，星期一（1）合式公式(命题公式,公式)的定义定义2.6

合式公式递归定义如下：(1)单个命题常项或变项是合式公式，并称作原子合式公式；(2)若A是合式公式,则(A)也是合式公式；(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式。2、合式公式的基本概念说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r45第四十五页，共八十六页，编辑于2023年，星期一（2）合式公式的层次定义2.7(1)单个命题变项或命题常项是0层公式(2)称A是n+1(n≥0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且

n=max(i,j)(c)A=BC,其中B,C的层次及n同(b)(d)A=BC,其中B,C的层次及n同(b)(e)A=BC,其中B,C的层次及n同(b)例如

p0层

p1层

pq2层(pq)r3层

((pq)r)(rs)4层46第四十六页，共八十六页，编辑于2023年，星期一（3）公式的赋值定义2.8设p1,p2,…,pn是出现在公式A中全部的命题变项，给p1,p2,…,pn指定一组真值，称为对A的一个赋值或解释。使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值。说明:(1)赋值记作=12…n，其中i=0或1，诸i之间不加标点符号；(2)通常赋值与命题变项之间按下标或字母顺序对应,即：当A的全部命题变项为p1,p2,…,pn时,给A赋值12…n是指p1=1,p2=2,…,pn=n;当A的全部命题变项为p,q,r,…时,给A赋值123…是指p=1,q=2,r=3,…47第四十七页，共八十六页，编辑于2023年，星期一实例例8

公式A=(

p1

p2p3)(p1

p2)000是成真赋值,001是成假赋值公式B=(pq)r000是成假赋值,001是成真赋值48第四十八页，共八十六页，编辑于2023年，星期一3、真值表真值表:命题公式在所有可能的赋值下的取值的列表。含n个变项的公式有2n个赋值用0或1表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。49第四十九页，共八十六页，编辑于2023年，星期一基本复合命题真值表汇总

pq

pp∧qp∨qpqpq001001101101101000100110111150第五十页，共八十六页，编辑于2023年，星期一pqqp

(qp)q

(qp)qp

00011011

1011

0001

1111例9

给出公式的真值表(1)

(qp)qp；(2)(pq)q；

(3)(pq)r.例951第五十一页，共八十六页，编辑于2023年，星期一pqppq(pq)(pq)q00011011

1100110100100000(2)(pq)q52第五十二页，共八十六页，编辑于2023年，星期一pqrpq

r

(pq)r

000001010011100101110111

00111111

10101010

11101010(3)(pq)r53第五十三页，共八十六页，编辑于2023年，星期一4、命题公式的分类重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式54第五十四页，共八十六页，编辑于2023年，星期一2、判断下列命题公式的类型（1）（2）课堂练习1、构造下列命题公式的真值表（1）（2）55第五十五页，共八十六页，编辑于2023年，星期一2.2命题逻辑等值演算2.2.1等值式与等值演算等值式基本等值式等值演算2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词56第五十六页，共八十六页，编辑于2023年，星期一§2.2.1等值式与等值演算1、等值式的定义定义2.11

若等价式AB是永真式,则称A与B等值,记作AB,并称AB是等值式。57第五十七页，共八十六页，编辑于2023年，星期一(1)是元语言符号,不要混同于和=。(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表。(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值。说明58第五十八页，共八十六页，编辑于2023年，星期一2、性质(1)AA(2)若AB，则B

A(3)若AB且B

C，则A

C59第五十九页，共八十六页，编辑于2023年，星期一3、真值表法判断公式是否等值结论:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)00110111011010011001100111001001例1

判断(pq)与

pq

是否等值解60第六十页，共八十六页，编辑于2023年，星期一

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)与(pq)r等值,但与(pq)r不等值例2判断下述3个公式之间的等值关系:

p(qr),(pq)r,(pq)r解61第六十一页，共八十六页，编辑于2023年，星期一4、基本等值式（1）双重否定律：（2）等幂律：62第六十二页，共八十六页，编辑于2023年，星期一（3）交换律：（4）结合律：（5）分配律：（6）德·摩根定律：63第六十三页，共八十六页，编辑于2023年，星期一（7）吸收律：（8）蕴含等值式：（9）等价等值式：64第六十四页，共八十六页，编辑于2023年，星期一（10）零律：（11）同一律：（12）排中律：65第六十五页，共八十六页，编辑于2023年，星期一（13）矛盾律：（14）等价否定等值式：（15）归谬律：（16）假言易位：66第六十六页，共八十六页，编辑于2023年，星期一

(1)代入规则

代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。例如F=（pq）↔（qp）是重言式，若用公式r∧s代换命题变元p得公式

F1=（（r∧s）q）↔（q（r∧s）），F1仍是重言式。注意：因为AB当且仅当A↔B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。5、等值演算67第六十七页，共八十六页，编辑于2023年，星期一(2)

置换规则

例如设公式A=（P∨Q）（（PQ）∨（R∧S））。

则P∨Q，PQ，（PQ）∨（R∧S）等均是A的子公式，

置换规则：设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。

子公式：设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。

68第六十八页，共八十六页，编辑于2023年，星期一(3)

等值演算

等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）69第六十九页，共八十六页，编辑于2023年，星期一

例4：证明（┐A→┐B)→(B→A)是永真式。证明:∵(┐A→┐B)→(B→A)蕴涵等值式┐(┐┐A∨┐B)∨(┐B∨A)德·摩根律、双重否定律(┐A∧B)∨(┐B∨A)分配律(┐A∨┐B∨A)∧(B∨┐B∨A)交换律、结合律、补余律

T

∴（┐A→┐B)→(B→A)是永真式70第七十页，共八十六页，编辑于2023年，星期一（同一律）（排中律）（分配律）证明

例5证：71第七十一页，共八十六页，编辑于2023年，星期一例6

用等值演算法判断下列公式的类型(1)q(pq)

解q(pq)

q(pq)（蕴涵等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0（矛盾律）

0（零律）该式为矛盾式.72第七十二页，共八十六页，编辑于2023年，星期一例6(续)(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蕴涵等值式）

(pq)(pq)（交换律）

1该式为重言式.73第七十三页，共八十六页，编辑于2023年，星期一例6(续)(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些74第七十四页，共八十六页，编辑于2023年，星期一例7：应用题某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜乙说：这不是铁，是锡丙说：这不是锡，是铁经过实验鉴定后发现，其中一人2个判断都是正确的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。75第七十五页，共八十六页，编辑于2023年，星期一解：设p：矿样为铁，q：矿样为铜，r：矿样为锡，则可得：76第七十六页，共八十六页，编辑于2023年，星期一77第七十七页，共八十六页，编辑于2023年，星期一78第七十八页，共八十六页，编辑于2023年，星期一等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例8

证明:p(qr)(pq)r方法一真值表法方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.79第七十九页，共八十六页，编辑于2023年，星期一2、证明3、证明是永真式。课堂练习1、证明用等值演算证明：80第八十页，共八十六页，编辑于2023年，星期一§2.2.2联结词完备集1、真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数

p

00011