离散数学数理逻辑

离散数学数理逻辑*第1页，共86页。教材与参考资料教材：《离散数学》（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：《离散数学》，刘玉珍、刘咏梅编，武汉大学出版社《DiscreteMathematicalStructures》(SixthEdition)，BernardKolman,FobertC.BusbyandSharonRoss，高等教育出版社有影印版、译本《DiscreteMathematicsandItsApplications》(SixthEdition)，[美]KennethH.Rosen，机械工业出版社影印版、译本*第2页，共86页。课程主要内容数理逻辑集合论图论代数系统**第3页，共86页。目的、意义和要求研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7章重点第9、14章备选第8、11章自学第10、12、13章不要求*第4页，共86页。学习要求1、课堂要求：按时上课认真听讲2、课外要求：复习(每次课后，安排半个小时)认真、按时完成作业(每次课后，安排1个小时)*第5页，共86页。学习考查方法1、出勤率：10%不定期检查出勤情况2、作业完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共5次4、期末考试（闭卷）：60%*第6页，共86页。第一篇数理逻辑第1章导论数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用*第7页，共86页。（1）定义§1.1数理逻辑的概念数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析符号化研究 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 间的关系推导、演算*第8页，共86页。（2）方法引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比赛结束后发现甲乙丙每人 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 的情况都各对一半，试问实际名次如何？1.引入pi,qi,ri,si分别 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示“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页，共86页。（3）内容谓词逻辑命题逻辑*第10页，共86页。（4）分支模型论证明论公理集合论递归论*第11页，共86页。§1.2数理逻辑的发展简史创立阶段起源阶段完善阶段发展历史*第12页，共86页。起源阶段德国数学家、哲学家G.Leibniz（1646~1716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。*第13页，共86页。创立阶段英国数学家G.Bool于1847年发表《逻辑的数学分析》，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。德国数学家G.Frege于1879年在《概念的演算》一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。*第14页，共86页。完善阶段英国逻辑学家A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了《数学原理》中，使数理逻辑成为了一门专门的学科。20世纪30年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。*第15页，共86页。§1.3数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计*第16页，共86页。第2章命题逻辑2.1命题逻辑基本概念2.2命题逻辑等值演算2.3范式2.4命题逻辑推理理论*第17页，共86页。2.1命题逻辑基本概念2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(¬,,,,)2.2.2命题公式及其分类命题公式及其赋值真值表命题公式的分类*第18页，共86页。§2.1.1命题与联结词1、命题及相关概念（1）命题的定义两者必居其一且只居其一——二值逻辑命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。命题：一个具有真假意义的陈述句。什么是真值：只包含真/假两个值的量。T/1—真F/0—假*第19页，共86页。注意：（1）感叹句、祈使句、疑问句都不是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题*第20页，共86页。中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。例1判断下列个自然语言是否是命题*第21页，共86页。（2）几个基本概念真命题与假命题命题变元与命题常元真命题:真值为真的命题假命题:真值为假的命题若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。*第22页，共86页。例2真命题假命题真值不确定疑问句感叹句祈使句悖论(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题真值确定,但未知下列句子中哪些是命题？并指出命题的真值。(1)北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.*第23页，共86页。（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级2.联接词*第24页，共86页。（1）简单命题与复合命题简单命题(原子命题):简单陈述句构成的命题。简单命题的符号化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q*第25页，共86页。（2）联结词的定义否定词（┐）定义2.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词,并规定p为真当且仅当p为假。例如p:2是合数,p:2不是合数。p为假,p为真。*第26页，共86页。合取词（∧）定义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页，共86页。例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页，共86页。析取词（∨）定义2.3设p、q为命题，复合命题“p或q”称作p与q的析取式，记作p∨q,∨称作析取联结词,并规定p∨q为假当且仅当p与q同时为假。例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为p∨q。*第29页，共86页。相容或与排斥或析取词表示的是相容或，即p和q均为真时(p∨q)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p和q不能同时为真。例如这件事由张三和李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(p∧q)∨(p∧q)*第30页，共86页。例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页，共86页。蕴涵词（）定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为pq*第32页，共86页。蕴涵词的其它表述方式pq的逻辑关系:q为p的必要条件,p为q的充分条件。“如果p,则q”的多种表述方式：若p,就q只要p,就qp仅当q只有q才p除非q,才p除非q,否则非p当p为假时，pq为真(不管q为真,还是为假)*第33页，共86页。例5设p:天冷,q:小王穿羽绒服，将下列命题符号化注意：pq与qp等值（真值相同）pqpqqp或pqpqqpqppq或qpqp(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.*第34页，共86页。等价词（）定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假。pq的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:pq*第35页，共86页。例6求下列复合命题的真值：1011(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝5当且仅当美国位于非洲.*第36页，共86页。分析找出简单命题用字母表示简单命题用联接词联接命题符号命题符号化的一般规则*第37页，共86页。分析找出简单命题用字母表示简单命题用联接词联接命题符号解令p:我上街q:我累r:我去书店看看则可符号化为：（pq)r例7将下列命题符号化：如果我上街并且我不累，我就去书店看看。简单命题：我上街。我累。我去书店看看。*第38页，共86页。例8试将下列命题符号化：如果你不看电影，那么我也不看电影小王一边吃饭，一边看书解:（1）设p：你看电影，q：我看电影，则：pq（2）设p：小王吃饭，q：小王看书，则：pq*第39页，共86页。（3）联结词的优先级联结词优先级:(),,,,,同级按从左到右的顺序进行*第40页，共86页。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页，共86页。课堂练习（2）3、将下列命题符号化（1）李平既聪明又用功（2）李平虽然聪明，但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功4、将下列命题符号化（1）只要不下雨，我就骑自行车上班（2）只有不下雨，我才骑自行车上班（3）若2+2=4，则太阳从东方升起（4）若2+2≠4,则太阳从东方升起*第42页，共86页。§2.1.2合式公式及其分类1.命题语言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分类*第43页，共86页。1.命题语言的字母表命题语言的字母表：命题常元：T,F(或1，0)命题变元：p1,p2,…,pn联接词：┐，∧，∨，→，辅助符号：（）*第44页，共86页。（1）合式公式(命题公式,公式)的定义定义2.6合式公式递归定义如下：(1)单个命题常项或变项是合式公式，并称作原子合式公式；(2)若A是合式公式,则(A)也是合式公式；(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式。2、合式公式的基本概念说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r*第45页，共86页。（2）合式公式的层次定义2.7(1)单个命题变项或命题常项是0层公式(2)称A是n+1(n≥0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j)(c)A=BC,其中B,C的层次及n同(b)(d)A=BC,其中B,C的层次及n同(b)(e)A=BC,其中B,C的层次及n同(b)例如p0层p1层pq2层(pq)r3层((pq)r)(rs)4层*第46页，共86页。（3）公式的赋值定义2.8设p1,p2,…,pn是出现在公式A中全部的命题变项，给p1,p2,…,pn指定一组真值，称为对A的一个赋值或解释。使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值。说明:(1)赋值记作=12…n，其中i=0或1，诸i之间不加标点符号；(2)通常赋值与命题变项之间按下标或字母顺序对应,即：当A的全部命题变项为p1,p2,…,pn时,给A赋值12…n是指p1=1,p2=2,…,pn=n;当A的全部命题变项为p,q,r,…时,给A赋值123…是指p=1,q=2,r=3,…*第47页，共86页。实例例8公式A=(p1p2p3)(p1p2)000是成真赋值,001是成假赋值公式B=(pq)r000是成假赋值,001是成真赋值*第48页，共86页。3、真值表真值表:命题公式在所有可能的赋值下的取值的列表。含n个变项的公式有2n个赋值用0或1表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。*第49页，共86页。基本复合命题真值表汇总pqpp∧qp∨qpqpq0010011011011010001001101111*第50页，共86页。pqqp(qp)q(qp)qp00011011101100011111例9给出公式的真值表(1)(qp)qp；(2)(pq)q；(3)(pq)r.例9*第51页，共86页。pqppq(pq)(pq)q000110111100110100100000(2)(pq)q*第52页，共86页。pqrpqr(pq)r000001010011100101110111001111111010101011101010(3)(pq)r*第53页，共86页。4、命题公式的分类重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式*第54页，共86页。2、判断下列命题公式的类型（1）（2）课堂练习1、构造下列命题公式的真值表（1）（2）*第55页，共86页。2.2命题逻辑等值演算2.2.1等值式与等值演算等值式基本等值式等值演算2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词*第56页，共86页。§2.2.1等值式与等值演算1、等值式的定义定义2.11若等价式AB是永真式,则称A与B等值,记作AB,并称AB是等值式。*第57页，共86页。(1)是元语言符号,不要混同于和=。(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表。(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值。说明*第58页，共86页。2、性质(1)AA(2)若AB，则BA(3)若AB且BC，则AC*第59页，共86页。3、真值表法判断公式是否等值结论:(pq)(pq)pqpqpq(pq)pq(pq)(pq)00110111011010011001100111001001例1判断(pq)与pq是否等值解*第60页，共86页。pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)与(pq)r等值,但与(pq)r不等值例2判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解*第61页，共86页。4、基本等值式（1）双重否定律：（2）等幂律：*第62页，共86页。（3）交换律：（4）结合律：（5）分配律：（6）德·摩根定律：*第63页，共86页。（7）吸收律：（8）蕴含等值式：（9）等价等值式：*第64页，共86页。（10）零律：（11）同一律：（12）排中律：*第65页，共86页。（13）矛盾律：（14）等价否定等值式：（15）归谬律：（16）假言易位：*第66页，共86页。(1)代入规则代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。例如F=（pq）↔（qp）是重言式，若用公式r∧s代换命题变元p得公式F1=（（r∧s）q）↔（q（r∧s）），F1仍是重言式。注意：因为AB当且仅当A↔B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。5、等值演算*第67页，共86页。(2)置换规则例如设公式A=（P∨Q）（（PQ）∨（R∧S））。则P∨Q，PQ，（PQ）∨（R∧S）等均是A的子公式，置换规则：设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。子公式：设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。*第68页，共86页。(3) 等值演算等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）*第69页，共86页。例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页，共86页。（同一律）（排中律）（分配律）证明例5证：*第71页，共86页。例6用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.*第72页，共86页。例6(续)(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.*第73页，共86页。例6(续)(3)((pq)(pq))r)解((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值. 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf :A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些*第74页，共86页。例7：应用题某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜乙说：这不是铁，是锡丙说：这不是锡，是铁经过实验鉴定后发现，其中一人2个判断都是正确的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。*第75页，共86页。解：设p：矿样为铁，q：矿样为铜，r：矿样为锡，则可得：*第76页，共86页。*第77页，共86页。*第78页，共86页。等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本 思想 教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿 是找到一个赋值使一个成真,另一个成假.例8证明:p(qr)(pq)r方法一真值表法方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.*第79页，共86页。2、证明3、证明是永真式。课堂练习1、证明用等值演算证明：*第80页，共86页。§2.2.2联结词完备集1、真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数p0001110101定义2.12称F:{0,1}n{0,1}为n元真值函数*第81页，共86页。2元真值函数pq0000000000010000111110001100111101010101pq0011111111010000111110001100111101010101*第82页，共86页。定义2.13设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}2、联结词完备集*第83页，共86页。举例AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)BAB*第84页，共86页。与非、或非与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q同时为假定理2.2{},{}是联结词完备集证p(pp)pppq(pq)(pq)(pq)(pq)得证{}是联结词完备集.对于{}可类似证明.*第85页，共86页。P80-81：2.10，2.12，2.13（2），2.15（1），2.16，2.18（1），2.19（2），2.20，2.21（1），2.22（2），2.23（1）（3）本节习题*第86页，共86页。