第一章数理逻辑

离散数学,中北大学,2020年5月11日星期一,引言,1.计算机专业的学生为什么要学习离散数学？2.离散数学包含的内容?3.怎样学习离散数学？,1什么是离散数学？,离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。,2离散数学与计算机科学,计算机学科的一个重要特点离散性,硬件软件（系统软件、应用软件）,模型,算法（程序运行逻辑）,数据表示、存储,程序编写、执行,离散数学,2离散数学与计算机科学,离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学”！计算机科学知识掌握的过程：“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”！需要如下三个方面的能力：构造模型、算法设计、程序设计的能力。思维训练：构造性思维,3关于课程学习,课程特点知识点集中，概念和定理多方法性强阅读，思考，练习，阅读，总结，学习内容数理逻辑、集合论、抽象代数、图论,4.计算科学与数学的关系,至于计算机技术专业的学生为何要学习数学这个问题的答案：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。,4计算学科与离散数学的关系,在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。构造模型的能力；算法设计的能力；程序设计的能力。,6.离散数学在国外的状况,纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的离散数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。,6.离散数学在国外的状况,美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值A=(pr)(qr)(pq)(pq),主范式的应用,求A的主析取范式A=(pr)(qr)(pq)(pq)(pr)(qr)(pq)(pq)(pq)(pr)(rq)(rr)(pq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pqr)(pqr)成真赋值:101,010;结论:方案1派A与C去,方案2派B去,主范式的应用,由主析取范式确定主合取范式例10设A有3个命题变项,且已知A=m1m3m7,求A的主合取范式.解A的成真赋值是1,3,7的二进制表示,成假赋值是在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示,它们恰好是A的主合取范式的极大项的下角标,故AM0M2M4M5M6,用成真赋值和成假赋值确定主范式,1-6推理理论,逻辑的一个重要功能是研究推理。推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，即它所关心的是论证的有效性，而对推理的实际内容（即命题表示的实际含义）并不关心。,推理的有效性和结论的真实性,所谓推理有效，指的是它的结论是它前提的合乎逻辑的结果。即，如果它的前提都为真，那么所得的结论也必然为真；如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。,1.6.1定义：设A，C是两个命题公式。当且仅当AC为重言式，即AC，称C是A的有效结论，或C可由A逻辑推出。推广：设H1,Hn，C是命题公式。当且仅当公式H1HnC，称C是一组前提H1,Hn的有效结论。,1-6推理理论,判断有效结论的常用方法,（1）真值表法：设P1，P2，Pn是出现于前提H1，H2，Hm和结论C中的全部命题变元，假定对P1，P2，Pn作了全部的真值指派，这样就能对应地确定H1，H2，Hm和C的所有真值，列出这个真值表，即可看出（A）式是否成立。,1-6推理理论,其方法：(1)给出各个前提和结论中的变元的各个指派，确定在各个指派下前提H1,Hn和结论C的真值；(2)找出前提H1,Hn均为1的行，若对应的结论C也为1，则H1HnC或找出结论C为0的行，若前提H1,Hn中至少有一个为0，则H1HnC,1-6推理理论,1-6推理理论,（1）真值表法例1.6.1：（PQ）（PQ）P,由此可以得出：在数理逻辑中，并不关心结论是真或假，而关心的是能否由前提推出结论，也即论证是否有效。对于真值表法，仅适用于命题变元少的情况。,1-6推理理论,2直接证法（演绎法）,直接证法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。,引入事实,引入推理规则,在数理逻辑中，主要的推理规则有：P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提；规则（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。,例1.6.2：H：（PQ）（PR）（QS）C：SR证法1：（1）PQP(2)PQT(1)E(3)QSP(4)PST(2),(3)I(5)SPT(4)E(6)PRP(7)SRT(5),(6)I(8)SRT(7)E,1-6推理理论,例1.6.3：H：（PQ）（PR）（QS）C：SR证法2：(1)PRP(2)PQRQT(1)I(3)QSP(4)RQRST(3)I(5)PQRST(2),(4)I(6)PQP(7)RST(5),(6)I,1-6推理理论,3.间接证法,(1)反证法(归谬法）(2)CP规则,方法一（反证法）：设要证H1,HmC，只要证C（H1,Hm）为永假式即可。因为要证H1,HmC，只要证C（H1,Hm）即可，C（H1,Hm）为永真式，即证C（H1,Hm)为永假式即可。,3间接证法,例1.6.4：（AB）（BC）A证明：（1）ABP(2)AP(附加前提)(3)（BC）P(4)BCT(3)E(5)BT(1),(2)I(6)BT(4),I(7)BBT(5),(6)I,1-6推理理论,例1.6.5H：(pq)r,rs,s,pC：q证明:用归缪法qP（附加前提）rsPsPrT(2),(3)I(pq)rP(pq)T(4),(5)IpqT(6)EpT(1),(7)IpPppT(8),(9)I,1-6推理理论,方法二(CP)规则：要证H1,Hm（RC），只要将R作为附加前提推证出C即可。此规则为CP规则。因为要证H1,Hm（RC），即证（H1,Hm）（RC）为永真式，即证（H1,Hm）R）C）为永真式，（H1,Hm）R）C为永真式，即（H1,Hm）R）C例：H：P（QS），RP，QC：RS,1-6推理理论,例1.6.8构造下面推理的证明2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数。所以，如果4是素数，则2是合数。解用附加前提证明法构造证明(1)设p：2是素数，q：2是合数，r：是无理数，s：4是素数(2)推理的形式结构前提：pq,pr,rs结论：sq,附加前提