工业大学稿第讲.ppt

离 散 数 学,2023年6月24日星期六,教师：陈雅颂,简介,离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。,通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。,随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。,由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。,离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。,离散数学课程的教学目的，不但作为计算机科学与技术及相关专业的理论基础及核心主干课，对后续课程提供必需的理论支持。更重要的是旨在“通过加强数学推理，组合分析，离散结构，算法构思与设计，构建模型等方面专门与反复的研究、训练及应用，培养提高学生的数学思维能力和对实际问题的求解能力。”,请根据下面事实，找出凶手：,1.清洁工或者秘书谋害了经理。2.如果清洁工谋害了经理，则谋害不会发生在午夜前。3.如果秘书的证词是正确的，则谋害发生在午夜前。4.如果秘书的证词不正确，则午夜时屋里灯光未灭。5.如果清洁工富裕，则他不会谋害经理。6.经理有钱且清洁工不富裕。7.午夜时屋里灯灭了。,解：令A:清洁工谋害了经理。B:秘书谋害了经理。C:谋害发生在午夜前。D:秘书的证词是正确的.E:午夜时屋里灯光灭了。H:清洁工富裕.G:经理有钱.命题符号为：,AB,AC,BC,DC,DE,HAEDEDDDCCACAABB结果是秘书谋害了经理。,第一部分 数理逻辑第二部分 集合论第五部分 图论第三部分 代数结构第四部分 组合数学（选讲）第六部分 初等数论（选讲）,第一部分 数理逻辑,第一章 命题逻辑基本概念第二章 命题逻辑等值演算 第三章 命题逻辑的推理理论第四章 一阶（谓词）逻辑基本概念 第五章 一阶（谓词）逻辑等值演算与推理,第二部分 集合论,第六章 集合代数第七章 二元关系第八章 函数（选讲）,第五部分 图论,第十四章 图的基本概念第十五章 欧拉图与哈密顿图第十六章 树第十七章 平面图第十八章 支配集、覆盖集、独立集与匹配与着色(选讲),第三部分 代数结构,第九章 代数系统第十章 群与环第十一章 格与布尔代数（选讲）,第四部分 组合数学（选讲）,第十二章 基本组合计数公式（选讲）第十三章 递推方程与生成函数（选讲）,第六部分 初等数论（选讲）,第十九章 初等数论（选讲）,第一部分 数理逻辑,逻辑：是人的一种抽象思维，是人通过概念、判断、推理、论证来理解和区分客观世界的思维过程。主要分为：制约逻辑；形式逻辑；演绎逻辑；归纳逻辑。本篇数理逻辑，是形式逻辑的一部分。,2023/6/24,数理逻辑（Mathematical Logic）-是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。,第一部分 数理逻辑,所谓数学方法就是指数学采用的一般方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。用数学的方法研究逻辑的系统思想一般追溯到莱布尼茨，他认为经典的传统逻辑必须改造和发展，是之更为精确和便于演算。后人基本是沿着莱布尼茨的思想进行工作的。,简而言之，数理逻辑就是精确化、数学化的形式逻辑。它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。,数理逻辑的产生,利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。,1847年，英国数学家布尔发表了逻辑的数学分析，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了数论的基础一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。,数理逻辑的发展,数理逻辑这门学科建立以后，发展比较迅速，促进它发展的因素也是多方面的。比如，非欧几何的建立，促使人们去研究非欧几何和欧氏几何的无矛盾性。,集合论的产生是近代数学发展的重大事件，但是在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发现了集合论的悖论引起。什么是悖论呢？悖论就是逻辑矛盾。集合论本来是论证很严格的一个分支，被公认为是数学的基础。,1903年，英国唯心主义哲学家、逻辑学家、数学家罗素却对集合论提出了以他名字命名的“罗素悖论”，这个悖论的提出几乎动摇了整个数学基础。,罗素悖论中有许多例子，其中一个很通俗也很有名的例子就是“理发师悖论”：某乡村有一位理发师，有一天他宣布：只给不自己刮胡子的人刮胡子。那么就产生了一个问题：理发师究竟给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他又不该给自己刮胡子；如果他不给自己刮胡子，那么他就是不自己刮胡子的人，按照他的原则，他又应该给自己刮胡子。这就产生了矛盾。,悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支-公理集合论。,数理逻辑新近还发展了许多新的分支，如递归论、模型论等。递归论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。模型论主要是研究形式系统和数学模型之间的关系。,数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新近形成的计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。,数理逻辑论的体系,数理逻辑的主要分支包括：逻辑演算(包括命题演算和谓词演算)、模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，这是因为许多计算机科学的先驱者既是数学家、又是逻辑学家，如阿兰图灵、邱奇等。简介：阿兰麦席森图灵，1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。阿隆佐邱奇（1903年6月14日1995年8月11日）是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。,程序语言学、语义学的研究从模型论衍生而来，而程序验证则从模型论的模型检测衍生而来。,数理逻辑的内容,数理逻辑包括哪些内容呢？这里我们先介绍它的两个最基本的也是最重要的组成部分，就是“命题演算”和“谓词演算（在本教材中也称作一阶逻辑演算）”。,学习逻辑学的意义 学习逻辑学的根本意义，是训练和提高人们的逻辑思维能力，促进其自觉地运用逻辑知识，提高学习和工作的质量。具体来说，学习逻辑学的意义主要有：第一，有助于正确认识事物，从已知进到未知。第二，有助于准确、严密地表达和论证思想。第三，有助于揭露谬误，驳斥诡辩。第四，有助于培养分析理性精神和创新意识。,2023/6/24,主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。,2023/6/24,什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？程序算法数据 算法逻辑控制,小结,2023/6/24,2023/6/24,第一章 命题逻辑的基本概念,命题逻辑也称命题演算，或语句逻辑。研究内容：（1）研究以命题为基本单位构成的前提和结论之间的可推导关系（2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？,2023/6/24,第一章 命题逻辑的基本概念,命题逻辑的特征：在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。,2023/6/24,1.0 本章学习要求,深刻理解:命题、联结词、复合命题、命题公式、等值（等价）式、等值（等价）演算、推理及证明等概念。熟练进行:等值（等价）演算与构造证明。,2023/6/24,1.1.1 命题定义1.1.0具有非真即假的陈述句称为命题,该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“1”(或“T”)和“0”(或“F”)表示。,1.1 命题与命题联结词,2023/6/24,（1）太阳是圆的；（2）成都是一个旅游城市；（3）北京是中国的首都；（4）这个语句是假的；（5）1110；（6）+y；（7）我喜欢踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中国是世界上人口最多的国家；（11）今天是晴天；,例1.1.1,T,T,T/F,非命题,T/F,F,T/F,T,T,T,非命题,2023/6/24,例1.1.1（续）,（12）把门关上；（13）你快上学去！（14）你要出去吗？（15）今天天气真好啊！,非命题,非命题,非命题,非命题,注意：一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。,2023/6/24,命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况、时间才能确定其真值。,结论：,在数理逻辑中像字母“x”、“y”、“z”等字母总是表示变量。,约定：,2023/6/24,下列语句是否是命题？并判断其真值结果？（1）四川不是一个国家；（2）3既是素数又是奇数；（3）张谦是大学生或是运动员；（4）如果周末天气晴朗，则我们将到郊外旅游；（5）2+24当且仅当雪是白的。,例1.1.2,2023/6/24,一般来说，命题可分两种类型：原子命题(简单命题)：不能再分解为更为简单命题的命题。复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,命题的分类,2023/6/24,今天天气很冷。今天天气很冷并且刮风。今天天气很冷并且刮风，但室内暖和。,例1.1.3,通常用大写（或小写的）的带或不带下标的英文字母、.P、Q、R、.Ai、Bi、Ci、.Pi、Qi、Ri、.等表示命题,2023/6/24,定义：1.1.1 命题联结词,设命题P,Q表示任意两个命题,则最常见的命题联结词有：,3.析取,P或者Q,P与Q的析取,PQ,PQ1P1或Q1,2.合取,P并且Q,P与Q的合取,PQ,PQ1P1且Q1,1.否定,非P,P的否定,P,P1 P0,4.蕴涵,若P,则Q,P蕴涵Q,PQ,PQ0 P1,Q0,5.等价,P当且仅当Q,P等价于Q,PQ,PQ1P1,Q1或P0,Q0,2023/6/24,总结,2023/6/24,说明,1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；,2023/6/24,说明,3、联结词与自然语言之间的对应并非一一对应；,1.否定式与否定联结词“”记作p，符号称作否定联结词，并规定p 为真当且仅当p为假.2.合取式与合取联结词“”使用合取联结词时要注意两点：(1)描述合取式的灵活性与多样性(2)分清简单命题与复合命题,例 将下列命题符号化.吴颖既用功又聪明.吴颖不仅用功而且聪明.吴颖虽然聪明，但不用功.张辉与王丽都是三好生.张辉与王丽是同学.（1）（3）说明描述合取式的灵活性与多样性（4）（5）要求分清联结词“与”，联结的复合命 题与简单命题将各命题符号化,3.析取式与析取联结词“”记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假.注意：此“或”，称作相容或，也称可兼或。还有一种“或”，称作排斥或，也称作不可兼或。,例 将下列命题符号化（1）2或4是素数.（2）2或3是素数.（3）4或6是素数.（4）小元元只能拿一个苹果或一个梨.（5）王小红生于1975年或1976年.（1）（3）为相容或（4）（5）为排斥或,4.蕴涵式与蕴涵联结词“”定义1.4 设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.,说明：（1）pq的逻辑关系：q为p的必要条件（2）“如果p,则q的不同表述法很多：若p，就q；只要p，就q；p仅当q；只有q，才p；除非q，才p；除非q，否则非p，,（3）当p为假时，pq为真，可称为空证明（4)常出现的错误：不分充分与必要条件,例 设p：天冷，q：小王穿羽绒服，将下列命题符号化（1）只要天冷，小王就穿羽绒服.（2）因为天冷，所以小王穿羽绒服.（3）若小王不穿羽绒服，则天不冷.（4）只有天冷，小王才穿羽绒服.（5）除非天冷，小王才穿羽绒服.（6）除非小王穿羽绒服，否则天不冷.（7）如果天不冷，则小王不穿羽绒服.（8）小王穿羽绒服仅当天冷的时候.,注意：pq与qp等值（真值相同）（1），（2），（3），（6）符号化为pq其余的符号化为qp 思考，为什么？,5.等价式与等价联结词“”定义1.5 设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并规定为真当且仅当p与q同时为真或同时为假.（1）pq的逻辑关系：p与q互为充分必要条件（2）pq为真当且仅当p与q同真或同假,例 符号化，并求下列复合命题的真值（1）2+2 4当且仅当3+3 6.（2）2+2 4当且仅当3 是偶数.（3）2+2 4当且仅当太阳从东方升起.（4）2+2 4当且仅当美国位于非洲.（5）函数f(x)在x0 可导的充要条件是它在x0连续.它们的真值是显而易见的.,什么是必要条件，充分条件，充分必要条件。,必要：PQ 字面理解很容易，没它不行的意思。用你的题目，P要成立，Q必须要成立，可能还需要其他的条件，P才能成立，但是没有Q，P肯定是不成立。比如，人活着，喝水这两件事，喝水就是人活着的必要条件，没水不行活不了，有水也不一定能活着（必要条件强调必须要有，没有不成立，至于有了以后的事情就不关心了）。人活着要喝水,充分：PQ P是Q的充分条件，字面去理解（有它就行），有P就一定会有Q发生。联想：人活着要喝水,首先，对以下三个词的释意要有所明确:(摘自金山词霸)。只要：表示具有充分的条件,正句常用“就”、“也”、“都”、“便”相呼应,表明由这种条件产生的一种结果。只有：表示必需的条件,下文常用“才”、“方”呼应。除非：表示唯一的条件,常跟“才”、“否则”、“不然”等合用,相当于“只有”。,继续解释：,由于“只要”表充分条件（即前件），相当于“如果”，根据定义：“只要p就q”的数理逻辑表示是p-q，而“只有”表必要条件（即后件），根据命题逻辑中相关的证明（如形式系统N）:p-q等价于!q-!p（!表联结词非），你也可以通过真值表进行验证。从而，“只有q才p”的表示是：p-q,根据“除非”与“只有”的等价性即“除非q，否则p”等价于“只有q,才p”。再根据“除非”与“如果不”、“否则”与否“则”的等价性（unlessif not），“除非q，否则p”即可表为!q-!p，那么，“只有q，才p”也可以表示为!q-!p，这就证明了“只要p就q”和“只有q才p”的等价性。至于“p仅当q”它是“只有q才p”的另一种表述，自然也等价了。,符号化：,A：下雨，B：骑车上班。1、只有不下雨，我才骑自行车上班。B-A2、如果下雨，我就不骑自行车上班。A-B3、除非下雨，否则我骑自行车上班。B-A,2023/6/24,符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。,例1.1.4,2023/6/24,例1.1.4 解,（1）设：四川是人口最多的省份。则命题（1）可表示为。（2）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；R：王超是一个体育成绩好的学生。则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了：教室的灯不亮可能是停电了 则命题（3）可表示为。,2023/6/24,（4）设：周末天气晴朗；：学院将组织我们到石像湖春游。则命题（4）可表示为。（5）设：两个三角形全等；：三角形的三条边全部相等。则命题（5）可表示为。,例1.1.4 解(续),2023/6/24,为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：,否定合取析取蕴涵等价同级的联结词，按其出现的先后次序(从左到右)若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。,约 定,2023/6/24,设命题P：明天上午七点下雨；Q：明天上午七点下雪；R：我将去学校。符号化下述语句：如果明天上午七点不是雨夹雪，则我将去学校如果明天上午七点不下雨并且不下雪，则我将去学校如果明天上午七点下雨或下雪，则我将不去学校明天上午我将雨雪无阻一定去学校,可符号化为：(PQR)(PQR)(PQR)(PQR)。或(PQ)(PQ)(PQ)(PQ)R。,例1.1.5,可符号化为：(PQ)R。,可符号化为:(PQ)R。,可符号化为:(PQ)R。,2023/6/24,例1.1.6,设命题P：你陪伴我；Q：你代我叫车子；R：我将出去。符号化下述语句：除非你陪伴我或代我叫车子，否则我将不出去 如果你陪伴我并且代我叫辆车子，则我将出去 如果你不陪伴我或不代我叫辆车子，我将不出去,R(PQ)或(PQ)R,(PQ)R,(PQ)R,2023/6/24,例,设P:雪是白色的;Q:2+24。将下列命题符号化：（1）因为雪是白色的，所以2+24；（2）如果2+24，则雪是白色的；（3）只有雪是白色的，才有2+24；（4）只有2+24，雪才是白色的；（5）只要雪不是白色的，就有2+24；（6）除非雪是白色的，否则2+24；（7）雪是白色的当且仅当2+24；,2023/6/24,例,设P:雪是白色的;Q:2+24。将下列命题符号化：（1）因为雪是白色的，所以2+24；PQ（2）如果2+24，则雪是白色的；QP（3）只有雪是白色的，才有2+24；QP（4）只有2+24，雪才是白色的；PQ（5）只要雪不是白色的，就有2+24；PQ（6）除非雪是白色的，否则2+24；P Q或QP（7）雪是白色的当且仅当2+24；P Q,2023/6/24,1.1.4 命题联结词的应用,例 1.2.7 用复合命题表示如下图所示的开关电路：,图1.2.1 图1.2.2 图1.2.3,AB,AB,A,设：开关闭合；：开关闭合。,第一节 小结,1.本小节中p,q,r,A,B,C,均表示命题.2.联结词集为,，每个联结词联结的p,pq,pq,pq,pq为基本复合命题.其中pq最难理解，要特别注意.反复使用,中的联结词组成更为复杂的复合命题.3.设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转 则复合命题(pq)(rs)p)是假命题.4.联结词的运算顺序：,同级按先出现者先运算.,练习：,课本 P12-14114题,2023/6/24,第一章 第二节 命题公式及其赋值,定义1.2.0 一个特定的命题是一个命题常项，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变项(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1)注意(1)常项与变项均用p,q,r,pi,qi,ri,等表示.(2)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。(3)真值函数或命题公式，没有确切真值。,真值函数,2023/6/24,1.2.1命题公式,定义1.2.1(命题公式/合式公式)1.命题变元本身是一个公式；2.如G是公式，则(G)也是公式；3.如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式；4.有限次地应用（1）-（3）形成的符号串是公式。,2023/6/24,符号串：(P(QR)(Q(SR)；(PQ)；(P(PQ)；(PQ)(RQ)(PR)。等都是命题公式。,例1.2.1,例1.2.2符号串：(PQ)Q)；(PQ；(PQ(R；PQ。等都不是合法的命题公式。,2023/6/24,例1.2.3,试用符号形式写出下列命题：（1）虽然今天天气晴朗，老陈还是不来；（2）除非你陪伴我或代我叫车子，否则我将不出去；（3）停机的原因在于语法错误或者程序错误；（4）若a和b是偶数，则a+b是偶数；（5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,2023/6/24,例1.2.3 解,（1）P：今天天气晴朗,Q：老陈要来,则有：PQ；（2）P：你陪伴我；Q：你代我叫车子；R：我出去。则有：RPQ或PQR；（3）P：停机的原因在于语法错误，Q：停机的原因在于程序错误，则有：PQ；（4）P：a是偶数；Q：b是偶数，R：a+b是偶数，则有：PQR；（5）P：我们要做到身体好,Q：我们要做到学习好,R：我们要做到工作好，S：我们要为祖国四化建设而奋斗，则有：PQR S。,2023/6/24,公式(P(QR)(Q(SR)可表示如下：,(P(QR)(Q(SR),P(QR)Q(SR),P QR Q SR,Q R S R,S,例1.2.4,注意：,几点说明：归纳或递归定义 元语言与对象语言 外层括号可以省去,定义1.2.2：合式公式的层次（1）若公式A是单个的命题变项，则称A为0层合式.（2）称A是n+1(n0)层公式是指下面情况之一：(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).（3）若公式A的层次为k,则称A为k层公式.,例如：公式A=p,B=p,C=pq,D=(pq)r,E=(pq)r)(rs)分别为0层，1层，2层，3层，4层公式.,2023/6/24,1.2.2 公式的解释与真值表,定义1.2.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn一组真值，则这组真值称为G的一个赋值或解释,常记为。一般来说，若有个命题变元，则应有2n个不同的解释。如果公式G在解释下是真的，则称成真赋值；如果G在解释下是假的，则称成假赋值。,定义1.2.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。,易知 000,010,101,110是(pq)r的成真赋值，而001,011,100,111是成假赋值.,构造真值表的方法：,见P9,定义1.91）找出所含全部命题变元，从000开始，直到111为止，进行赋值。2）从低到高顺序写出公式的各个层次。3）对应各个赋值，计算各层次的真值。注意：公式A与公式B最后一列相同，称两公式的真值表相同。,2023/6/24,例1.2.5,求下面公式的真值表：(P(PQ)R)Q 其中，、是的所有命题变元。,2023/6/24,例1.2.5（续）,进一步化简为：,2023/6/24,例1.2.6,求下面这组公式的真值表：1()；2()；3()(Q)。,2023/6/24,从这三个真值表可以看到一个非常有趣的事实：,公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值,结论,2023/6/24,定义1.2.5,公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足的，如果它不是永假的。,2023/6/24,从上述定义可知三种特殊公式之间的关系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式可满足式的否定不一定为不可满足式(即为矛盾式),结论,问题？,（1）如何判断公式的类型？（2）如何求出公式A的全部成真与成假赋值？,几点说明1）熟练之后，真值表的中间有些层次可不写2）真值表的用途 有了公式A的真值表就知道了A的一切信息,习题课,第一章的内容与要求1.主要内容命题、真值、命题的分类、命题符号化联结词,及复合命题符号化命题公式及层次公式的类型真值表及应用2.要求深刻理解各联结词的逻辑关系会求复合命题的真值熟练地将复合命题符号化准确地求公式的真值表，并用它求公式成真与成假赋值及判断公式类型,二、练习题1.将下列命题符号化 1）豆沙包是由面粉和红小豆做成的.2）苹果树和梨树都是落叶乔木.3）王小红或李大明是物理组成员.4）王小红或李大明中的一人是物理组成员.5）由于交通阻塞，他迟到了.6）如果交通不阻塞，他就不会迟到.7）他没迟到，所以交通没阻塞.8）除非交通阻塞，否则他不会迟到.9）他迟到当且仅当交通阻塞.,提示：分清复合命题与简单命题 分清相容或与排斥或 分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）-（4）的符号化形式设p:交通阻塞，q:他迟到（5）pq,（6）pq或qp（7）qp 或pq,（8）qp或pq（9）pq 或pq可见（5）与（7），（6）与（8）相同（等值）,2.设p:2是素数 q:北京比天津人口多 r:美国的首都是旧金山求下面命题的真值:(pq)r(qr)(pr)(qr)(pr)(qp)(pr)(rq),提示：p,q为真命题，r是假命题反复用基本复合命题的真值求解（心算即可）答案：真值分别为0,1,0,0,3.用真值表判断下面公式的类型1）pr(qp)2）(pq)(qp)r3）(pq)(pr)提示：按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式,第二章 命题逻辑等值（等价）演算,1.本章的主要内容：等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集2.本章与其他各章的联系 是第一章的抽象与延伸 是后续各章的先行准备,第二章 命题逻辑等值（等价）演算,2.0 等值式（等价式）补充定义：哑元（新定义）设公式A,B中含有命题变元P1，P2，Pn。而A或B不全含有这些变元，比如，A中不含Pi，Pi+1，Pn,i5，称这些变元为A的哑元。从而，A的取值与哑元无关，在讨论A与B是否有相同真值表时，可将A,B都看成P1，P2，Pn的公式。,2023/6/24,例 2.0,写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1()()；（2）G2(Q)(Q)(Q)；（3）G3(PQ)Q。,2023/6/24,例 2.0 解,三个公式的真值表如下：,2023/6/24,若将其看成两个公式，分别令：，。则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：,分析公式,定义2.1 若式AB是重言式，则称A与B等值（等价），记作AB，并称AB是等值式（等价式）。,几点说明：定义中，A,B,均为元语言符号 A或B中可能有哑元出现.例如，在(pq)(pq)(rr)中，r为左边公式的哑元.用真值表可验证两个公式是否等值。请验证：p(qr)(pq)r p(qr)(pq)r,2023/6/24,首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。,注意：“”与“”的区别,2023/6/24,2.1“”的性质,由于“”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性 GG；（2）对称性 若GH，则HG；（3）传递性 若GH，HS，则GS。这三条性质体现了“”的实质含义。,基本的等值（等价）式,E1双重否定律 AAE2幂等律 AAA,AAAE3交换律 ABBA,ABBAE4结合律(AB)CA(BC),(AB)CA(BC)E5分配律 A(BC)(AB)(AC),A(BC)(AB)(AC)E6德摩根律(AB)AB(AB)ABE7吸收律 A(AB)A,A(AB)A,E8零律 A11,A00E9同一律 A0A.A1AE10排中律 AA1E11矛盾律 AA0E12蕴涵等值式 ABABE13等价等值式 AB(AB)(BA)E14假言易位 ABBAE15等价否定等值式 ABABE16归谬论(AB)(AB)A注意：要牢记各个等值式，这是继续学习的基础。,2023/6/24,例 2.1 证明公式G1=()与公式G2=(PQ)(QP)之间是逻辑等价的。解：根据定理3.3.1，只需判定公式G3=()(PQ)(QP)为永真公式。,2023/6/24,这种图是将G，H理解为某总体论域上的子集合，而规定GH为两集合的公共部分（交集合），GH为两集合的全部（并集合），G为总体论域（如矩形域）中G的补集，将命题中的真值“1”理解为集合中的总体论域（全集），将命题中的真值“0”理解为集合中的空集，则有：,命题与集合之间的关系，加深演算的理解,“”对“”与“”对“”的对比,2.2 等值演算与置换规则,1.等值演算由已知的等值式推演出新的等值式的过程2.等值演算的基础：（1）等值关系的性质：自反、对称、传递性（2）基本的等值式（3）置换规则（见3）3置换规则 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中的所有的A后得到的命题公式，若BA，则(B)(A),2.3 等值演算的应用举例,1证明两个公式等值（等价）例 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）,几点说明：也可以从右边开始演算因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出用等值演算不能直接证明两个公式不等值,例 证明 p(qr)(pq)r证 方法一 真值表法（自己证）方法二 观察赋值法.易知000,010等是左边的成真赋值，是右边的成假赋值方法三 用等值演算先化简两个公式，再观察,2.判断公式类型例 用等值演算法判断下列公式的类型（1）q(pq)（2）(pq)(qp)（3）(pq)(pq)r)解（1）q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，（1）为矛盾式.,（2）(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.,（3）(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101,111是成真赋值，000,010等是成假赋值.总结：从此例可看出A为矛盾式当且仅当A 0A为重言式当且仅当A 1,3解判定问题见书上P21，例2.6,2023/6/24,例,利用基本的等价关系，完成如下工作：（1）判断公式的类型：证明()()()()是一个永真公式。（2）证明公式之间的等价关系：证明()()（3）化简公式：证明(P(R)(R)(PR)R,2023/6/24,证明,（1）()()()()()()()()()()()()()()()()()()()()()()T 即:()()()()为永真公式；,2023/6/24,证明（续）,（2）P(QR)P(QR)P(QR)(PQ)R(PQ)R(PQ)R 即有:P(QR)(PQ)R；（3）(P(QR)(QR)(PR)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R TR R 即有:(P(QR)(QR)(PR)R。,2023/6/24,实际应用举例,例 利用基本的等价关系，化简下列电路图,解：上述电路图可描述为：（1）(PQR)(PQS)(PR)(PS),2023/6/24,例（续）,利用基本等价关系，化简公式(1)可得：（1）(PQR)(PQS)(PR)(PS)(PQ(RS)(P(RS)PQ(RS)；,2023/6/24,例,将下面程序语言进行化简。If A then if B then X else Y else if B then X else Y,解：执行X的条件为：()(),执行Y的条件为：()(),2023/6/24,例(续）,执行X的条件可化简为：()()()执行Y的条件可化简为：()()(),程序可简化为：If B then X else Y,2023/6/24,2.4析取范式与合取范式,一、析取范式与合取范式1.基本概念（1）文字命题变项及其否定的总称（2）简单析取式有限个文字构成的析取式 p,q,pq,pqr,（3）简单合取式有限个文字构成的合取式 p,q,pq,pqr,（4）析取范式由有限个简单合取式组成的析取式 A1A2Ar(r1)（5）合取范式由有限个简单析取式组成的合取式 A1A2Ar(r1)（6）范式析取范式与合取范式的总称,说明：单个文字既是简单析取式，又是简单合取式形如pqr,pqr的公式既是析取范式，又是合取范式主要性质：简单析取式与简单合取式的性质，见定理2.1析取范式与合取范式的性质，见定理2.2,2.命题公式的范式(1)公式A的析取范式：由有限个简单合取式的析取构成的命题公式称为析取范式(2)公式A的合取范式：由有限个简单析取式的合取构成的命题公式称为合取范式(3)公式范式存在定理：定理2.3 任何命题公式都存在着与之等值的析取范式与合取范式,(4)求公式A的范式的步骤：a.消去A中的,（若存在）b.否定联结词的内移或消去 c.使用分配律 对分配（析取范式）对分配（合取范式）(5)公式的范式存在，但不惟一，这是它的局限性,