工业大学稿第讲

《工业大学稿第讲》由会员分享，可在线阅读，更多相关《工业大学稿第讲（229页珍藏版）》请在金锄头文库上搜索。

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1-理学院理学院 离散数学课程组离散数学课程组TJPU-SS Discrete mathematics离 散 数 学7/22/2024教师：陈雅颂教师：陈雅颂沼蛤颂捂系养她洽晨囊梢衬虐苫衅扮铭川罪紧霞涅萧散汾试怎既嘛窖淹耘工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组2简介简介 离散数学离散数学(Discrete mathematics)(Discrete mathematics)是研究离是研究离散量的结构及其相互关系的数学学科，是现代数散量的结构及其相互关

2、系的数学学科，是现代数学的一个重要分支。学的一个重要分支。 它在各学科领域，特别在计算机科学与技术它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如专业的许多专业课程，如程序设计语言、数据结程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础算法设计与分析、理论计算机科学基础等必不可等必不可少的少的先行课程先行课程。 珐络倚贝踪吐碍寝炮吵屯炎赦僧骑簿粳吴馏碘撬枪耳谰灌状夸叔贵幢郁十工业大学稿第讲工业大学稿第讲天津工业

3、大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组3 通过离散数学的学习，不但可以掌握处理离通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打理能力，为将来参与创新性的研究和开发工作打下坚实的基础。下坚实的基础。巧遵眶罐屡然幼菱痪泽绎蛰拢抡吸锈猩隋窒章量威疵堰虑又族荤睦谅拎有工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课

4、程组4 随着信息时代的到来，工业革命时代以随着信息时代的到来，工业革命时代以微积微积分分为代表的连续数学占主流的地位已经发生了变为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知从计算机软件到计算机硬件，从人工智能到认知系统，无

5、不与离散数学密切相关。系统，无不与离散数学密切相关。气锰逾碗吭烈厨弄逢疵掣蹋跌杠仓蚤粮辣用午拴肥借手狭掇埔揽杆键锚晚工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组5 由于数字电子计算机是一个离散结构，它只由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，能处理离散的或离散化了的数量关系， 因此，因此，无论计算机科学本身，还是与计算机科学及其应无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用对离

6、散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。可由计算机加以处理。蛇筹拿割奥恕补四恨唁篮个血质膘鹤矫朽暑踩盗傻亚果矽填孩缆虏扒篱未工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组6 离散数学是传统的离散数学是传统的逻辑学逻辑学，集合论集合论（包括函（包括函数），数），数论数论基础，算法设计，组合分析，离散概基础，算法设计，组合分析，离散概率，关系理论，率，关系理论，图论图论与与树树，抽象代数抽象代数（包括代数（包括代数系统，群、环、域等），

7、系统，群、环、域等），布尔代数布尔代数，计算模型，计算模型（语言与自动机）等汇集起来的一门综合学科。（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。离散数学的应用遍及现代科学技术的诸多领域。唱抒拢淌乔铅升踩隐双呈伎痔肝休懊粕垫卧腻购柜谅涛醋粕尺窜峡牺蟹腮工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组7 离散数学课程的教学目的，不但作为计算机离散数学课程的教学目的，不但作为计算机科学与技术及相关专业的理论基础及核心主干课，科学与技术及相关专业的理论基础及核心主干课，对后续课程提供必需的理论支持。更重

8、要的是旨对后续课程提供必需的理论支持。更重要的是旨在在“通过加强数学推理，组合分析，离散结构，通过加强数学推理，组合分析，离散结构，算法构思与设计，构建模型等方面专门与反复的算法构思与设计，构建模型等方面专门与反复的研究、训练及应用，培养提高学生的数学思维能研究、训练及应用，培养提高学生的数学思维能力和对实际问题的求解能力。力和对实际问题的求解能力。”蓝么牙式名宇杆迂湾痉持货夹丈涎轧杉链已申愿宅霞懒涟酣夷绎兆永慷柠工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组8请根据下面事实，找出凶手：请根据下面事实，找出凶手：1.1.清洁工或者秘

9、书谋害了经理。清洁工或者秘书谋害了经理。2.2.如果清洁工谋害了经理，则谋害不会发生在午夜前。如果清洁工谋害了经理，则谋害不会发生在午夜前。3.3.如果秘书的证词是正确的，则谋害发生在午夜前。如果秘书的证词是正确的，则谋害发生在午夜前。4.4.如果秘书的证词不正确，则午夜时屋里灯光未灭。如果秘书的证词不正确，则午夜时屋里灯光未灭。5.5.如果清洁工富裕，则他不会谋害经理。如果清洁工富裕，则他不会谋害经理。6.6.经理有钱且清洁工不富裕。经理有钱且清洁工不富裕。7.7.午夜时屋里灯灭了。午夜时屋里灯灭了。濒拂搬偷匙斤砂储迟佰猴垂临夯冉酷忘初葱芥隶谆玻戈卖闺铬檀析们朗顷工业大学稿第讲工业大学稿第讲

10、天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组9解：解：令令A:A:清洁工谋害了经理。清洁工谋害了经理。B:B:秘书谋害了经理。秘书谋害了经理。C:C:谋害发生在午夜前。谋害发生在午夜前。D:D:秘书的证词是正确的秘书的证词是正确的. . E: E:午夜时屋里灯光灭了。午夜时屋里灯光灭了。H:H:清洁工富裕清洁工富裕. . G: G:经理有钱经理有钱. .命题符号为：命题符号为：份崔扯迂汉反翌盖肯墟操嘛后荡镑浸鲁辞哉朔综您滔靳抬镑神特饭康翅坡工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组10A A

11、B,AB,AC,BC,BC,DC,C,DC,DDE,HE,HAAE EDDEEDDD DDCDCC CAACCAAA A B BB Bn结果是秘书谋害了经理。结果是秘书谋害了经理。 粘芜屉灭献颓残甸牟涅云举卵罐锻到潮把歪滚前触淳泥第琐粉劣询烦骑士工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组11n第一部分第一部分 数理逻辑数理逻辑n第二部分第二部分 集合论集合论n第五部分第五部分 图图论论n第三部分第三部分 代数结构代数结构n第四部分第四部分 组合数学组合数学（选讲）（选讲）n第六部分第六部分 初初等数论（选讲）等数论（选讲）了减蜜

12、憋仲炬痪茂罢耪隙刺屯俗膜界渺绒鬃费岂重衡盒剩服吉懦今盯仗谨工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组12第一部分第一部分 数理逻辑数理逻辑第一章第一章 命题逻辑基本概念命题逻辑基本概念第二章第二章 命题逻辑等值演算命题逻辑等值演算 第三章第三章 命题逻辑的推理理论命题逻辑的推理理论第四章第四章 一阶（谓词）逻辑基本概念一阶（谓词）逻辑基本概念 第五章第五章 一阶（谓词）逻辑等值演算与推理一阶（谓词）逻辑等值演算与推理观雇甜杜竣佐灰福副酝蚜僚喝辑涟谦模捷玛蓄译燃促造十翔膨初否富模值工业大学稿第讲工业大学稿第讲天津工业大学天津工业大

13、学 理学院理学院 数学系离散数学课程组数学系离散数学课程组13第二部分第二部分 集合论集合论第六章第六章 集合代数集合代数第七章第七章 二元关系二元关系第八章第八章 函数函数（选讲）（选讲）馏栏氛巧京去彤哼难录绢妻帐沦且伙哑曳愤泉泼克氦钉怯稀七掩艰肩袋扬工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组14第五部分第五部分 图图论论第十四章第十四章 图的基本概念图的基本概念第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图第十六章第十六章 树树第十七章第十七章 平面图平面图第十八章第十八章 支配集、覆盖集、独立集与匹配与着色支配集、覆盖

14、集、独立集与匹配与着色 ( (选讲选讲) )祥缚护蔑幽獭连况呵哎图槐聘杖抉渍恼饰扬卧冰床震凡酒免朱承茫韦揣盲工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组15第三部分第三部分 代数结构代数结构第九章第九章 代数系统代数系统第十章第十章 群与环群与环第十一章第十一章 格与布尔代数（选讲）格与布尔代数（选讲）凯抿脉成释组珐逛茬阐考射炉诅插笼篓徐揪趟鸡蔽谢狡夕桌把施瞄谰约绝工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组16第四部分第四部分 组合数学组合数学（选讲）（选讲）n第十

15、二章第十二章 基本组合计数公式基本组合计数公式 （选讲）（选讲）n第十三章第十三章 递推方程与生成函数（选讲）递推方程与生成函数（选讲）雹姜簧炬摆示寒圆匈啊桐佐楞钾匀泞爽码斩陈谭狡伊崖业媒宦辐鼻俗撮掩工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组17第六部分第六部分 初等数论初等数论 （选讲）（选讲）n第十九章第十九章 初等数论初等数论 （选讲）（选讲）草拳双贺霓佳巫敞寅题辗土找我蒲郭冷降蹄淑拄宪边端劫贪杯暑曰樊炬炳工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组18第一部

16、分第一部分 数理逻辑数理逻辑逻辑：逻辑： 是人的一种抽象思维，是人通过概念、判断、是人的一种抽象思维，是人通过概念、判断、推理、论证来理解和区分客观世界的思维过程。推理、论证来理解和区分客观世界的思维过程。主要分为：主要分为：制约逻辑制约逻辑；形式逻辑形式逻辑；演绎逻辑演绎逻辑；归纳逻辑归纳逻辑。本篇本篇数理逻辑数理逻辑，是，是形式逻辑形式逻辑的一部分。的一部分。烂搐候颈稽亭联换窘氟效雍毙际囊康秧羔片诽褂莹寇宽昨膝农仿嘛足砌淑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组197/22/20247/22/2024数理逻辑数理逻辑（Ma

17、thematicalLogic） -是研究演绎推理的一门学科，用是研究演绎推理的一门学科，用数学的方数学的方法法来研究来研究推理的规律推理的规律统称为数理逻辑。统称为数理逻辑。第一部分第一部分 数理逻辑数理逻辑茄奋于谭存撕讽仪葱沦土绥锐镐邓粤迎捏凌阅吩侦亏忿肿丧力胺咽埃俊崔工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组20n 所谓数学方法就是指数学采用的一般方法，所谓数学方法就是指数学采用的一般方法，包括使用符号和公式，已有的数学成果和方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。特别是使用形式的公理方法

18、。n用数学的方法研究逻辑的系统思想一般追溯用数学的方法研究逻辑的系统思想一般追溯到到莱布尼茨莱布尼茨，他认为经典的传统逻辑必须改造和，他认为经典的传统逻辑必须改造和发展，是之更为精确和便于演算。后人基本是沿发展，是之更为精确和便于演算。后人基本是沿着莱布尼茨的思想进行工作的。着莱布尼茨的思想进行工作的。新郡件至签莱矿俱嗽卧旭宇春薄熙妆良驻怒禁燃侣身邀臣金拐饮轮豫拯轻工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组21n 简而言之，数理逻辑就是精确化、数学化的简而言之，数理逻辑就是精确化、数学化的形式逻辑。形式逻辑。n 它是现代计算机技

19、术的基础。新的时代将是它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。很关键的作用。炊为泳吩鸽招坑毒哩蕴怒蒸立躯讣拜屉谷叉查挫伤攘区口锐铂谍或鼠偷荐工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组22数理逻辑的产生数理逻辑的产生 n 利用计算的方法来代替人们思维中的逻辑推利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。理过程，这种想法早在十七世纪就有人提出过。莱布尼茨莱布尼茨就曾经设想过能不能创造一种就曾经设想过能不

20、能创造一种“通用的通用的科学语言科学语言”，可以把推理过程象数学一样利用公，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。式来进行计算，从而得出正确的结论。n 由于当时的社会条件，他的想法并没有实现。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。先驱。谓匈荤横爱芥孟邯凛期拾亲珊挡渤滨娩司琵奢绝仰掀藐侵俩摄冠痰闸圈软工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系

21、离散数学课程组23n18471847年，英国数学家年，英国数学家布尔布尔发表了逻辑的数学分析，发表了逻辑的数学分析，建立了建立了“布尔代数布尔代数”，并创造一套符号系统，利用符号，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。辑的基础。n十九世纪末二十世纪初，数理逻辑有了比较大的发十九世纪末二十世纪初，数理逻辑有了比较大的发展，展，18841884年，年，德国德国数学家数学家弗雷格弗雷格出版了数论的基础出版了数论

22、的基础一书，在书中引入量词的符号，使得数理逻辑的符号系一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学理逻辑最基本的理论基础逐步形成，成为一门独立的学科。科。 词洪宣扑左烘监细厦切晰洪莽蔷避奔迹辛典周褒冲孪互菱狗芦帛肺昏痉烂工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组24数理逻辑的发展数理逻辑的

23、发展 n 数理逻辑这门学科建立以后，发展比较迅速，数理逻辑这门学科建立以后，发展比较迅速，促进它发展的因素也是多方面的。比如，促进它发展的因素也是多方面的。比如，非欧几非欧几何何的建立，促使人们去研究非欧几何和欧氏几何的建立，促使人们去研究非欧几何和欧氏几何的无矛盾性。的无矛盾性。欲粱宜揣历瞄乙箭斡永漓谐洲掇脸洪棋研并伏前蜒燃贿督纂鲸吱刀即凰纱工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组25n 集合论的产生是近代数学发展的重大事件，集合论的产生是近代数学发展的重大事件，但是在集合论的研究过程中，出现了一次称作数但是在集合论的研究过

24、程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发现了学史上的第三次大危机。这次危机是由于发现了集合论的悖论引起。什么是悖论呢？悖论就是逻集合论的悖论引起。什么是悖论呢？悖论就是逻辑矛盾。集合论本来是论证很严格的一个分支，辑矛盾。集合论本来是论证很严格的一个分支，被公认为是数学的基础。被公认为是数学的基础。隋腑隧早决头纸青鞠矛干牢舞攫她水袍絮朝琢糠檬戒达奢鸯盅昂间绝力材工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组26n 1903 1903年，英国唯心主义哲学家、逻辑学家、年，英国唯心主义哲学家、逻辑学家、数学家数学家罗素

25、罗素却对集合论提出了以他名字命名的却对集合论提出了以他名字命名的“罗素悖论罗素悖论”，这个悖论的提出几乎动摇了整个数，这个悖论的提出几乎动摇了整个数学基础。学基础。关搪绵谴默望贮单捎甫刁发日敲膝岳藩哥拌军臂火悉祭蔷祸摇沽棱枉扯劳工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组27 罗素悖论中有许多例子，其中一个很通俗也罗素悖论中有许多例子，其中一个很通俗也很有名的例子就是很有名的例子就是“理发师悖论理发师悖论”： 某乡村有一位理发师，有一天他宣布：只给某乡村有一位理发师，有一天他宣布：只给不自己刮胡子的人刮胡子。那么就产生了一个问不自

26、己刮胡子的人刮胡子。那么就产生了一个问题：理发师究竟给不给自己刮胡子？如果他给自题：理发师究竟给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原己刮胡子，他就是自己刮胡子的人，按照他的原则，他又不该给自己刮胡子；如果他不给自己刮则，他又不该给自己刮胡子；如果他不给自己刮胡子，那么他就是不自己刮胡子的人，按照他的胡子，那么他就是不自己刮胡子的人，按照他的原则，他又应该给自己刮胡子。原则，他又应该给自己刮胡子。 这就产生了矛盾。这就产生了矛盾。钙像闻濒范把抢棺垢衔巍卤因骄鄙宇疙赡禾遣浩蛙奏艇炉孙柳坛召罪卞溢工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学

27、系离散数学课程组数学系离散数学课程组28n 悖论的提出，促使许多数学家去研究集合论悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重的无矛盾性问题，从而产生了数理逻辑的一个重要分支要分支-公理集合论。公理集合论。讲缄损介寿该猴矾椿羊庭亢词螺勉翟琵混葵聚仰凤土诈里舞誉敖肖烁苦畸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组29n 数理逻辑新近还发展了许多新的分支，如递数理逻辑新近还发展了许多新的分支，如递归论、模型论等。递归论主要研究可计算性的理归论、模型论等。递归论主要研究可计算性的理论，它和计算机的发

28、展和应用有密切的关系。模论，它和计算机的发展和应用有密切的关系。模型论主要是研究形式系统和数学模型之间的关系。型论主要是研究形式系统和数学模型之间的关系。逻鸦颇委源憋以盆拿馆漳稍坐琢滑巩鹊喀霓扭迟裔瞻凉明停吝皑盎恢颗谊工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组30n 数理逻辑近年来发展特别迅速，主要原因是数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新数、拓扑学等的发展有重大的影响，特别是对新近形成的近形成的计算机

29、科学计算机科学的发展起了推动作用。反过的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。来，其他学科的发展也推动了数理逻辑的发展。遵馆段柜殉屏柠软沛颐看塌附狈钧舍通胎针场梭父脆匹宋鞭叛块富硫痢尿工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组31数理逻辑论的体系数理逻辑论的体系 n数理逻辑的主要分支包括：逻辑演算数理逻辑的主要分支包括：逻辑演算( (包括包括命题演算和谓词演算命题演算和谓词演算) )、模型论模型论、证明论证明论、递归递归论论和和公理化集合论公理化集合论。n 数理逻辑和数理逻辑和计算机科学计算机科学有许多

30、重合之处，这有许多重合之处，这是因为许多计算机科学的先驱者既是数学家、又是因为许多计算机科学的先驱者既是数学家、又是逻辑学家，如是逻辑学家，如阿兰阿兰图灵图灵、邱奇等。、邱奇等。 简介：阿兰简介：阿兰麦席森麦席森图灵，图灵，19121912年生于英国伦敦，年生于英国伦敦，19541954年死于英国的年死于英国的曼彻斯特曼彻斯特，他是，他是计算机计算机逻逻辑的奠基者，许多辑的奠基者，许多人工智能人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是他提出的有限状态自动机也就是图灵机图灵机的概念，

31、对于人工智能，它提出了重要的衡量标准的概念，对于人工智能，它提出了重要的衡量标准“图灵图灵测试测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。 阿隆佐阿隆佐邱奇（邱奇（19031903年年6 6月月1414日日19951995年年8 8月月1111日）是美国数学家，日）是美国数学家，19361936年发表可计算函数年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿受教并工作四十年，的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿受教

32、并工作四十年，曾任数学与哲学教授。曾任数学与哲学教授。19671967年迁往加利福尼亚大学洛杉矶分校。年迁往加利福尼亚大学洛杉矶分校。 膨人赫溢神诵笆岩牺乞铡兜所堰蕉七纠谭勃犀群斑恤舞流词凛赵唐尉檀廊工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组32n 程序语言学、语义学程序语言学、语义学的研究从模型论衍生的研究从模型论衍生而来，而而来，而程序验证程序验证则从模型论的模型检测衍生而则从模型论的模型检测衍生而来。来。 虎掂挖螺肥恨淄筷法股船镐腊胚轿榔易眷惟鳖撂埂亢糯褒弟坐急先褐稠间工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学

33、理学院理学院 数学系离散数学课程组数学系离散数学课程组33数理逻辑的内容数理逻辑的内容 n 数理逻辑包括哪些内容呢？这里我们先介绍数理逻辑包括哪些内容呢？这里我们先介绍它的两个最基本的也是最重要的组成部分，就是它的两个最基本的也是最重要的组成部分，就是“命题演算命题演算”和和“谓词演算谓词演算（在本教材中也称作一在本教材中也称作一阶逻辑演算阶逻辑演算）”。 瘪锨簇报睬宗掖浆瓤柿借吏淮袄阉蛙队钟铆橙咋亲稗回钞昼尔亢刘调倾嘿工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组34 学习逻辑学的意义学习逻辑学的意义 学习逻辑学的根本意义，是训学

34、习逻辑学的根本意义，是训练和提高人们的逻辑思维能力，促进其自觉地运用练和提高人们的逻辑思维能力，促进其自觉地运用逻辑知识，提高学习和工作的质量。逻辑知识，提高学习和工作的质量。 具体来说，学具体来说，学习逻辑学的意义主要有：习逻辑学的意义主要有：第一，有助于正确认识事物，从已知进到未知。第一，有助于正确认识事物，从已知进到未知。 第二，有助于准确、严密地表达和论证思想。第二，有助于准确、严密地表达和论证思想。 第三，有助于揭露谬误，驳斥诡辩。第三，有助于揭露谬误，驳斥诡辩。 第四，有助于培养分析理性精神和创新意识。第四，有助于培养分析理性精神和创新意识。 柿美闺赏狗阑佛盂匀贯摸貌垛醋鞍迅旋赞尔

35、郊奈镊篇池把鞍轮催揖吩甩搂工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组357/22/20247/22/2024主要研究内容：主要研究内容：推理推理 着重于着重于推理过程是否正确推理过程是否正确 着重于着重于语句之间的关系语句之间的关系主要研究方法：主要研究方法：数学的方法数学的方法 就是引进一套符号体系的方法，所以数就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（理逻辑又叫符号逻辑（Symbolic LogicSymbolic Logic）。）。 蜡贸斩蛮躇贰弥圈刃葡多隙曳橡响仁笆那弱孰钵逞开芳谁詹谬藻痉结邻逗工业大学稿第讲

36、工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组367/22/20247/22/2024什么是数理逻辑什么是数理逻辑 ？用数学的方法来研究用数学的方法来研究推理的规律推理的规律统称为数理逻辑。统称为数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？ 程序程序算法数据算法数据 算法算法逻辑控制逻辑控制小结小结芥驻驳零验哩呛谚残遁胰栅年迸讫臼皂份疮雇潭藉硼旦空渗裂厉销幕顶雕工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组377/22/20247/22/2024命题逻辑命题逻辑命题逻辑基本概

37、念命题逻辑基本概念命题逻辑等值演算命题逻辑等值演算命题逻辑推理理论命题逻辑推理理论主要研主要研究内容究内容一阶逻辑一阶逻辑（谓词逻辑）（谓词逻辑）一阶逻辑基本概念一阶逻辑基本概念一阶逻辑等值演算一阶逻辑等值演算一阶逻辑一阶逻辑推理理论推理理论俐蛾炒甚衡哲车绵生住臼酌抗询甥晦澄荚拭妆藻淑脐阎吗啥箔狞祖匡鞠壕工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组387/22/20247/22/2024第一章第一章 命题逻辑的基本概念命题逻辑的基本概念 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。 研究内容：研究内容： （

38、1 1）研究以）研究以命题为基本单位命题为基本单位构成的构成的前提和结论前提和结论之间的可推导关系之间的可推导关系 （2 2）研究）研究什么是命题什么是命题？ （3 3）研究）研究如何表示命题如何表示命题？ （4 4）研究）研究如何由一组前提推导一些结论如何由一组前提推导一些结论？考咆扎昂朱驰细雄阑穗姬曲桌鹏庄讶铝交垢恃衙焊濒风骤括贤拙素仍垃浑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组397/22/20247/22/2024第一章第一章 命题逻辑的基本概念命题逻辑的基本概念命题逻辑的命题逻辑的特征：特征： 在研究逻辑的形式时，我

39、们在研究逻辑的形式时，我们把一个命题只把一个命题只分析到其中所含的命题成份为止，不再分析下分析到其中所含的命题成份为止，不再分析下去去。不把一个简单命题再分析为非命题的集合，不不把一个简单命题再分析为非命题的集合，不把把谓词谓词和和量词量词等非命题成份分析出来。等非命题成份分析出来。 总渡砸勘炔怔狭元鹅缘午绳劲禽色翠参幻丸咽糠纶扭帕搜抠辅倍卑臭真畔工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组407/22/20247/22/20241.0 1.0 本章学习要求本章学习要求 深刻理解深刻理解: :命题、联结词、复合命题、命题公式、命题

40、、联结词、复合命题、命题公式、等值（等价）式、等值（等价）演算、推理及证明等等值（等价）式、等值（等价）演算、推理及证明等概念。概念。 熟练进行熟练进行: :等值（等价）演算与构造证明。等值（等价）演算与构造证明。捕泳苍酒痔蜒虎戮梅脂萄宁隶贾塌密她沤兜画叠涉挂眨髓裤先握腆遥胳獭工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组417/22/20247/22/20241.1.1 1.1.1 命题命题定义定义1.1.01.1.0具有具有非真即假非真即假的陈述句称为的陈述句称为命题命题, , 该命题可以取一个该命题可以取一个“值值”，称为，称

41、为真值真值。真值只有真值只有“真真”和和“假假”两种，两种，分别用分别用“1 1”( (或或“T T”) )和和“0 0”( (或或“F F”) )表示。表示。1.1 1.1 命题与命题联结词命题与命题联结词执屑掳岛诸租议硒醇遇齐液庚腔竟粤很危剔埔痊旺沥所带曾造敛驹澄球糟工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组427/22/20247/22/2024（1 1）太阳是圆的；）太阳是圆的； （2 2）成都是一个旅游城市；）成都是一个旅游城市；（3 3）北京是中国的首都；）北京是中国的首都；（4 4）这个语句是假的；）这个语句是假的

42、；（5 5）1 1110110；（6 6）+y+y；（7 7）我喜欢踢足球；）我喜欢踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中国是世界上人口最多的国家；）中国是世界上人口最多的国家；（1111）今天是晴天；）今天是晴天；例例1.1.11.1.1TTT/F非命题非命题T/FFT/FTTT非命题非命题暂路版顾吐皇滨驯嫁度烬捞坟睡屁甄伐彪鞘张掏钢宁堤眺辐绦绝浮比波虞工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组437/22/20247/22/2024例例1.1.

43、11.1.1（续）（续）（1212）把门关上；）把门关上；（1313）你快上学去！）你快上学去！（1414）你要出去吗？）你要出去吗？（1515）今天天气真好啊！）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。 涝哈靴邱剃舔橡殖恋凛寓扁尸谱姥架窃尔彤冗季各闲的别逐煞推谜煎垄麓工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组447

44、/22/20247/22/2024命题一定是陈述句，但并非一切陈述句都是命题。命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠命题的真值有时可明确给出，有时还需要依靠环境、环境、条件、实际情况、时间条件、实际情况、时间才能确定其真值。才能确定其真值。结论：结论：在在数数理理逻逻辑辑中中像像字字母母“x x”、“y y”、“z z”等等字字母总是母总是表示表示变量。变量。约定：约定：篓欢她两乳截协园撞旁盼卓需鲁畜方摇落个甩肋跪辕让石突闽庶厨励母缅工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组457/

45、22/20247/22/2024下列语句是否是命题？下列语句是否是命题？并判断其真值结果？并判断其真值结果？（1 1）四川）四川不不是一个国家；是一个国家；（2 2）3 3既既是素数是素数又又是奇数；是奇数；（3 3）张谦是大学生）张谦是大学生或是或是运动员；运动员；（4 4）如果如果周末天气晴朗，周末天气晴朗，则则我们将到郊外旅游；我们将到郊外旅游；（5 5）2+242+24当且仅当当且仅当雪是白的。雪是白的。例例1.1.21.1.2牵挽什乍奶刁弓吝订胚调喧轿杉苗暖费霍漓掏膏危侮旺蔫仙填沁戈卤妻晴工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离

46、散数学课程组467/22/20247/22/2024一般来说，命题可分两种类型：一般来说，命题可分两种类型：1)1)原子命题原子命题( (简单命题简单命题) )：不能再：不能再分解分解为更为简单为更为简单命题的命题。命题的命题。2)2)复合命题复合命题：可以：可以分解分解为更为简单命题的命题。为更为简单命题的命题。而且这些简单命题之间是通过如而且这些简单命题之间是通过如“或者或者”、“并且并且”、“不不”、“如果如果.则则.”、“当且当且仅当仅当”等这样的关联词和标点符号复合而构成等这样的关联词和标点符号复合而构成一个复合命题。一个复合命题。命题的分类命题的分类轧替言孤咖滤惦吩吾襄肢谅攒塑揭哉

47、尝撮楚贷娜陛经娜撒莉荫享屏写亿榜工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组477/22/20247/22/20241)1)今天天气很冷。今天天气很冷。2)2)今天天气很冷并且刮风。今天天气很冷并且刮风。3)3)今天天气很冷并且刮风，但室内暖和。今天天气很冷并且刮风，但室内暖和。例例1.1.31.1.3 通常用通常用大写（或小写的）的带或不带下标的英文字大写（或小写的）的带或不带下标的英文字母母、.P.P、Q Q、R R、. A. Ai i、B Bi i 、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表

48、示命题吊粳饲麻穷冈搽祖垂鄙处朔够稿鄂出啦猛纹统赁互煞丸兢促秦惟脯悠锋青工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组487/22/20247/22/2024定义：定义：1.1.1 1.1.1 命题联结词命题联结词设命题设命题P,QP,Q表示任意两个命题表示任意两个命题, ,则则最常见的命题联结词有：最常见的命题联结词有：联接词联接词记号记号 复合命题复合命题读法读法 记法记法真值结果真值结果 3.3.析取析取 P P或者或者Q QP P与与Q Q的析取的析取P P Q QPQ1PQ1P1P1或或Q1Q12.2.合取合取 P P并且并

49、且Q QP P与与Q Q的合取的合取PQPQPQ1PQ1P1P1且且Q1Q11.1.否定否定 非非P PP P的否定的否定PPP1P1 P0P04.4.蕴涵蕴涵若若P,P,则则Q QP P蕴涵蕴涵Q QP PQQPQ0PQ0 P1,Q0P1,Q05.5.等价等价 P P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ1Q1P P1,Q1,Q1=1或或P P0,Q00,Q0徒刁谎般念咨屋恰盘井舷碱疗狠睦般糙剂瞅埋芭宠羌街朋忆舅佣捉迈姑凡工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组497/22/20247/22/20

50、24总结总结P QP QP PPQPQPQPQPQPQP PQ Q0 00 01 10 00 01 11 10 10 11 10 01 11 10 01 01 00 00 01 10 00 01 11 10 01 11 11 11 1谢蜡几脏把雌勒腑测窜眉节泰娟乐冗孵站颖够植恬轿腥尘颜拐萄蛛炼迎菏工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组507/22/20247/22/2024说明说明1 1、联结词是句子与句子之间的联结，而非单纯的联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2

51、 2、联结词是两个句子真值之间的联结，而非句子、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在联系；地内在联系；蕴秆撒刽令驶峭环葫霜庭垒飞惊微筐蘸镇患斜铲慈尤胀牟助怜舔闭讲飘瞪工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组517/22/20247/22/2024说明说明3 3、联结词与自然语言之间的对应、联结词与自然语言之间的对应并非一一对应并非一一对应；联结词联结词自然语言自然语言既既又又、不仅、不仅而且而且、虽然、虽然但是但是、并且、和、与，等等；、

52、并且、和、与，等等；PQPQ若若P P则则Q Q、只要、只要P P就就Q Q、P P仅当仅当Q Q、只有、只有Q Q才才P P、除非、除非Q Q否则否则 P P，等等，等等等价、当且仅当、充分必要、等等；等价、当且仅当、充分必要、等等； 相容（可兼）的或相容（可兼）的或令揪徘贮敌彪政舞皿钦菜筷譬袖舟萨朽爪槽斋过轩钓榨兄肃谱魁林褪嵌把工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组521.1.否定式与否定联结词否定式与否定联结词“ ” 记作记作 p p，符号，符号 称作否定联结词，并规定称作否定联结词，并规定 p p 为真当且仅当为真当

53、且仅当p p为假为假. .2.2.合取式与合取联结词合取式与合取联结词“”“” 使用合取联结词时要注意两点：使用合取联结词时要注意两点： (1) (1) 描述合取式的灵活性与多样性描述合取式的灵活性与多样性 (2) (2) 分清简单命题与复合命题分清简单命题与复合命题营追搬蓑仗涧伤蔬堕云扎径肌尚有拧志玻赃爆翌酮菇军渊豁稼区烷筑膊浊工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组53例例 将下列命题符号化将下列命题符号化. . 吴颖既用功又聪明吴颖既用功又聪明. . 吴颖不仅用功而且聪明吴颖不仅用功而且聪明. . 吴颖虽然聪明，但不用功

54、吴颖虽然聪明，但不用功. . 张辉与王丽都是三好生张辉与王丽都是三好生. . 张辉与王丽是同学张辉与王丽是同学. .（1 1）（）（3 3）说明描述合取式的灵活性与多样性）说明描述合取式的灵活性与多样性（4 4）（）（5 5）要求分清联结词）要求分清联结词“与与”，联结的复合命，联结的复合命 题与简单命题将各命题符号化题与简单命题将各命题符号化湛淳寇拖屉农腹住蔬庆镐寺态划胎册丫恩筏腔诫逞承屯销脚炔傅社群节梧工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组543. 3. 析取式与析取联结词析取式与析取联结词“”“” 记作记作p pq q

55、，称作析取联结词，并规定称作析取联结词，并规定p pq q为假当且仅当为假当且仅当p p与与q q同时为假同时为假. . 注意：注意：此此“或或”，称作，称作相容或相容或，也称，也称可兼或可兼或。还有一种还有一种“或或”，称作，称作排斥或排斥或，也称作，也称作不可兼或不可兼或。宛刽处汹辰氯砂旱快借肃侈殆皇两斟扒戏吼炬垫冀屉俏门釉孩抓呜习下蛾工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组55例例 将下列命题符号化将下列命题符号化（1 1）2 2或或4 4是素数是素数. .（2 2）2 2或或3 3是素数是素数. .（3 3）4 4或或

56、6 6是素数是素数. .（4 4）小元元只能拿一个苹果或一个梨）小元元只能拿一个苹果或一个梨. .（5 5）王小红生于）王小红生于19751975年或年或19761976年年. .n（1 1）（3 3）为相容或）为相容或n（4 4）（5 5）为排斥或）为排斥或炬赖荆终邻塞鹃站倦枝琅隆伶逻渤蛛埔正棵此揽摧竣塔赏旋揩军号宪萍梅工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组56n4. 4. 蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“” 定义定义1.4 1.4 设设p p, , q q为二命题，复合命题为二命题，复合命题“如果如果p p, ,

57、则则q q”称作称作p p与与q q的蕴涵式，记作的蕴涵式，记作p pq q，并称，并称p p是蕴涵是蕴涵式的前件，式的前件，q q为蕴涵式的后件，为蕴涵式的后件，称作蕴涵联结称作蕴涵联结词，并规定，词，并规定，p pq q为假当且仅当为假当且仅当p p为真为真q q为假为假. .暑筐漾政搜瑟活惹餐白奎克尔烃莆迎羊子娠垛蓬俭霉耸夏屁击厌六蓑郭来工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组57说明：说明：（1 1）p pq q的逻辑关系：的逻辑关系：q q为为p p的必要条件的必要条件（2 2）“如果如果p p, , 则则q q的不

58、同表述法很多：的不同表述法很多：n 若若p p，就，就q q；n 只要只要p p，就，就q q；n p p仅当仅当q q；n 只有只有q q，才，才p p；n 除非除非q q， 才才p p；n 除非除非q q，否则非，否则非p p， 刃呵绚系伎闭恃嘱缓覆皂姻熬滇督沦廓糊坠孺嚷晰踊蚌族躯潭豁擅垦营病工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组58（3 3）当）当p p为假时，为假时，p pq q为真，可称为空证明为真，可称为空证明（4) 4) 常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件疑蹲糊政饰钦滨辨挤唐滔颖惺

59、桔营研婚呈瞪绳沿挤涉午捷皋窟幻琵晤删凑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组59例例 设设p p：天冷，：天冷，q q：小王穿羽绒服，将下列命题符：小王穿羽绒服，将下列命题符号化号化（1 1）只要天冷，小王就穿羽绒服）只要天冷，小王就穿羽绒服. .（2 2）因为天冷，所以小王穿羽绒服）因为天冷，所以小王穿羽绒服. .（3 3）若小王不穿羽绒服，则天不冷）若小王不穿羽绒服，则天不冷. .（4 4）只有天冷，小王才穿羽绒服）只有天冷，小王才穿羽绒服. .（5 5）除非天冷，小王才穿羽绒服）除非天冷，小王才穿羽绒服. .（6 6）

60、除非小王穿羽绒服，否则天不冷）除非小王穿羽绒服，否则天不冷. .（7 7）如果天不冷，则小王不穿羽绒服）如果天不冷，则小王不穿羽绒服. .（8 8）小王穿羽绒服仅当天冷的时候）小王穿羽绒服仅当天冷的时候. .扫汉凶闰倾骗份纽素环颖窜缅赢暑揭苗日孟甄绷侧疮扶零郸彬颂周熄颂戈工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组60n注意：注意： p pq q与与 q qp p等值（真值相同）等值（真值相同）（1 1），（），（2 2），（），（3 3），（），（6 6）符号化为）符号化为p pq q其余的符号化为其余的符号化为q qp p 思

61、考，为什么？思考，为什么？荆噬秉遣梢敢词目毗塌思内箔丘蓑仓祷绩溺彝蝶老十揭赐赔胃揣扭决挎藐工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组61n5. 5. 等价式与等价联结词等价式与等价联结词“”定义定义1.5 1.5 设设p p，q q为二命题，复合命题为二命题，复合命题“p p当且仅当当且仅当q q”称作称作p p与与q q的等价式，记作的等价式，记作p pq q，称作等价称作等价联结词联结词. . 并规定并规定为真当且仅当为真当且仅当p p与与q q同时为真同时为真或同时为假或同时为假. .（1 1）p pq q的逻辑关系：的逻

62、辑关系：p p与与q q互为充分必要条件互为充分必要条件（2 2）p pq q为真当且仅当为真当且仅当p p与与q q同真或同假同真或同假萝匡凳须刀唁摇主夕投侥萧贩铺窥撑螺雹涡肋社圃僚敢成蠢赘漏研属用勘工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组62例例 符号化，并求下列复合命题的真值符号化，并求下列复合命题的真值（1 1）2 + 2 2 + 2 4 4当且仅当当且仅当3 + 3 3 + 3 6. 6.（2 2）2 + 2 2 + 2 4 4当且仅当当且仅当3 3 是偶数是偶数. .（3 3）2 + 2 2 + 2 4 4当且仅当

63、太阳从东方升起当且仅当太阳从东方升起. .（4 4）2 + 2 2 + 2 4 4当且仅当美国位于非洲当且仅当美国位于非洲. .（5 5）函数）函数f(x)f(x)在在x x0 0 可导的充要条件是它在可导的充要条件是它在x x0 0连续连续. . n它们的真值是显而易见的它们的真值是显而易见的. .渡苟著都扫侵懈码保钧焰康氟犯蜒位九傀迭漂喉索梭回斌羊浊角保保析颅工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组707/22/20247/22/2024例例1.1.4 1.1.4 解解（1 1）设：四川是人口最多的省份。）设：四川是人口最

64、多的省份。 则命题（则命题（1 1）可表示为）可表示为。（2 2）设：王超是一个思想品德好的学生；）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生； R R：王超是一个体育成绩好的学生。：王超是一个体育成绩好的学生。 则命题（则命题（2 2）可表示为）可表示为RR。（3 3）设：教室的灯不亮可能是灯管坏了）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了 则命题（则命题（3 3）可表示为）可表示为。迎援粤讹旋俯底允绵仰哥猾获及饮鱼猜胰捂淑釉邑膛匪僵帧锐苇鸯姚炳嘴工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学

65、 理学院理学院 数学系离散数学课程组数学系离散数学课程组717/22/20247/22/2024（4 4）设：周末天气晴朗；）设：周末天气晴朗； ：学院将组织我们到石像湖春游。：学院将组织我们到石像湖春游。 则命题（则命题（4 4）可表示为）可表示为。（5 5）设：两个三角形全等；）设：两个三角形全等； ：三角形的三条边全部相等。：三角形的三条边全部相等。 则命题（则命题（5 5）可表示为）可表示为。例例1.1.4 1.1.4 解解( (续续) )承标涛淑癌边鱼况蓑验棒炒卿屈于腆脾拇酒婉赖孜歇含砾堪兜汛李贰逾移工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课

66、程组数学系离散数学课程组727/22/20247/22/2024 为了不使句子产生混淆，作如下约定，为了不使句子产生混淆，作如下约定，命题联结命题联结词之优先级词之优先级如下：如下：1.1.否定否定合取合取析取析取蕴涵蕴涵等价等价2.2.同同级级的的联联结结词词，按按其其出出现现的的先先后后次次序序( (从从左左到右到右) )3.3.若若运运算算要要求求与与优优先先次次序序不不一一致致时时，可可使使用用括括号号；同同级级符符号号相相邻邻时时，也也可可使使用用括括号号。括括号号中的运算为最优先级中的运算为最优先级。约约 定定刊打覆苹迭诫幼课绿迄乖塘都弦稿咒举颠酌缘开贝姚硷零派钓额凌琐郡财工业大学

67、稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组737/22/20247/22/2024设命题设命题P P：明天上午七点下雨；：明天上午七点下雨；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1)1)如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校2)2)如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去我将去学校学校3)3)如果如果明天上午七点下雨明天上午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校4)4)明

68、天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。 或或 (PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)R(PQ)R。例例1.1.51.1.5可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。败良龄莽怕骗男芦做承酚鞘辆狗刷崖陛贩桑垮柑娱荆鉴回陨终竿炳循酶恳工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组747/22/2024

69、7/22/2024例例1.1.61.1.6设命题设命题P P：你陪伴我；：你陪伴我； Q Q：你代我叫车子；：你代我叫车子； R R：我将出去。：我将出去。 符号化下述语句：符号化下述语句： 除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，则则我将出去我将出去 如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，我将代我叫辆车子，我将不不出去出去R(PQ) R(PQ) 或或 (PQ)R(PQ)R(PQ)R(PQ)R(PQ)R(PQ)R拇瞅级铭屏诲身橙缀斋称课铃杠泛果趁函帐搔贷亿和械陨党己连雄磷别辖工业大

70、学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组757/22/20247/22/2024例例设设P:P:雪是白色的雪是白色的;Q:2+24;Q:2+24。将下列命题符号化：。将下列命题符号化：（1 1）因为雪是白色的，所以）因为雪是白色的，所以2+242+24；（2 2）如果）如果2+242+24，则雪是白色的；，则雪是白色的；（3 3）只有雪是白色的，才有）只有雪是白色的，才有2+242+24；（4 4）只有）只有2+242+24，雪才是白色的；，雪才是白色的； （5 5）只要雪不是白色的，就有）只要雪不是白色的，就有2+242+24；（

71、6 6）除非雪是白色的，否则）除非雪是白色的，否则2+242+24； （7 7）雪是白色的当且仅当）雪是白色的当且仅当2+242+24；蠢苫气迷鼠艾烹耕札替丹身宅浇哎备分螟延庶肇派航牵客胜丹定孙绞遣袍工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组767/22/20247/22/2024例例设设P:P:雪是白色的雪是白色的;Q:2+24;Q:2+24。将下列命题符号化：。将下列命题符号化：（1 1）因为雪是白色的，所以）因为雪是白色的，所以2+242+24； PQ PQ （2 2）如果）如果2+242+24，则雪是白色的；，则雪是白色

72、的； QP QP（3 3）只有雪是白色的，才有）只有雪是白色的，才有2+242+24； QP QP（4 4）只有）只有2+242+24，雪才是白色的；，雪才是白色的； PQ PQ（5 5）只要雪不是白色的，就有）只要雪不是白色的，就有2+242+24； PQ PQ（6 6）除非雪是白色的，否则）除非雪是白色的，否则2+242+24； P P Q Q或或QPQP（7 7）雪是白色的当且仅当）雪是白色的当且仅当2+242+24； P P Q Q宴拯患得界杏玫栖啪砸峻弹咳哈返胯谗切聚酮浇棠馆峭汇曰弧柜申企箔帆工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学

73、系离散数学课程组777/22/20247/22/20241.1.4 1.1.4 命题联结词的应用命题联结词的应用例例 1.2.7 1.2.7 用复合命题表示如下图所示的开关用复合命题表示如下图所示的开关电路：电路： 图图1.2.1 1.2.1 图图1.2.2 1.2.2 图图1.2.31.2.3ABABABABA A设：设：开关闭合；：开关闭合。：开关闭合；：开关闭合。 茎伦丧击庆阀荤早验涛吉忙舒又瘪驳促安二讯笼送斜企翌被棱虾迫贼躲益工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组78第一节第一节 小结小结1.1.本小节中本小节中p

74、p, , q q, , r r, , A,B,C, A,B,C,均表示命题均表示命题. .2.2.联结词集为联结词集为 , , , , , , , , ，每个联结词联，每个联结词联结的结的 p p, , p p q q, , p p q q, , p pq q, , p pq q为基本复合命为基本复合命题题. . 其中其中p pq q最难理解，要特别注意最难理解，要特别注意. . 反复使用反复使用 , , , , , , , , 中的联结词组成更为复杂的中的联结词组成更为复杂的复合命题复合命题. .3. 3. 设设p p: : 是无理数，是无理数， q q: 3: 3是奇数，是奇数， r r:

75、 : 苹果是方的，苹果是方的， s s: : 太阳绕地球转太阳绕地球转 则复合命题则复合命题( (p pq q) ) (r rs s) ) p p) )是假命题是假命题. . 4.4.联结词的运算顺序：联结词的运算顺序： , , , , , , , , , , 同级按同级按先出现者先运算先出现者先运算. .望轴五丘障崩馈瓜丁潭虚腥绣如锄插代婉隔喘共决侍艺非摊宗札涤樱达吸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组79练习：练习：n课本课本 P12-14 P12-14n1 11414题题揽杆荒夯又宗栗卫姚凄滚吞辩提蔼逼僚美骨混凳喝屎

76、聘卧顶酣脱氰酪首弘工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组807/22/20247/22/2024第一章第一章 第二节第二节 命题公式及其赋值命题公式及其赋值定义定义1.2.01.2.0 一个特定的命题是一个一个特定的命题是一个命题常项命题常项，它不是具有值，它不是具有值“T T”( (“1 1”) )，就是具有值，就是具有值“F F”( (“0 0”) )。而一个任意的没有赋予具体内容的原子命题是一个变量命题，而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为常称它为命题变项命题变项( (或或命题变元命题变元)

77、)，该命题变量无具体的真值，该命题变量无具体的真值，它的变域是集合它的变域是集合TT，F(F(或或00，1)1)注意注意(1)(1)常项与变项均用常项与变项均用p p, , q q, , r r, , , , pipi, , qiqi, , riri, , , , 等表示等表示. . (2) (2) 复合命题为命题变元的复合命题为命题变元的“函数函数”, ,其函数值仍为其函数值仍为 真真 或或“假假”值。值。( (3 3) )真值函数或命题公式，没有确切真值。真值函数或命题公式，没有确切真值。真值函数真值函数刨福郎程祥烹删虚诽蕴正盗牲臀卒嫡锻应灿牙菱何批一哲酱熟颜买可速垄工业大学稿第讲工业大学

78、稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组817/22/20247/22/20241.2.11.2.1命题公式命题公式定义定义1.1.2.12.1 ( (命题公式命题公式/ /合式公式合式公式) )1.1.命题变元本身是一个公式；命题变元本身是一个公式；2.2.如如G G是公式，则是公式，则(G)(G)也是公式；也是公式；3.3.如如G G，H H是公式，则是公式，则(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH)H)也是公式；也是公式；4. 4. 有限次地应用（有限次地应用（1 1）- -（3 3）形成的符号串是公式）形成的符号串

79、是公式。升缺凌梯茸胺梯锈刺琶厉用煽遣肚绅垢颜结也糟签腺杨册级勃儒彻奴队玫工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组827/22/20247/22/2024符号串：符号串：(P(QR)(Q(SR)(P(QR)(Q(SR)； (PQ)(PQ)； (P(PQ) (P(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命题公式。等都是命题公式。例例1.2.11.2.1例例1.2.21.2.2符号串：符号串：(PQ)Q)(PQ)Q)； (PQ(PQ；(PQ(R(PQ(R； PQ PQ。等都不是合法的命题公式。等都不是合

80、法的命题公式。瞻疤细旧嚷零届疲麻低城袭涩篓垫澳该钝悄办紧肉甚炕艘善愧笛狂朽霞或工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组837/22/20247/22/2024例例1.2.31.2.3试用符号形式写出下列命题：试用符号形式写出下列命题：（1 1）虽然今天天气晴朗，老陈还是不来；）虽然今天天气晴朗，老陈还是不来；（2 2）除非你陪伴我或代我叫车子，否则我将不出去；）除非你陪伴我或代我叫车子，否则我将不出去；（3 3）停机的原因在于语法错误或者程序错误；）停机的原因在于语法错误或者程序错误；（4 4）若）若a a和和b b是偶数，则

81、是偶数，则a+ba+b是偶数；是偶数；（5 5）我们要做到身体好、学习好、工作好，为祖国四）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。化建设而奋斗。 涧名戍扩涂党熄苗统扣蹿壮管规屏堡如咀郎孺秤狮银探睛兆舆五郴挞提牌工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组847/22/20247/22/2024例例1.2.3 1.2.3 解解（1 1）P P：今天天气晴朗：今天天气晴朗,Q,Q：老陈要来：老陈要来, ,则有：则有：PQPQ；（2 2）P P：你陪伴我；：你陪伴我； Q Q：你代我叫车子；：你代我叫车子；R R：我出

82、去。：我出去。则有：则有：RPQRPQ或或PQRPQR；（3 3）P P：停机的原因在于语法错误，：停机的原因在于语法错误，Q Q：停机的原因在：停机的原因在于程序错误，于程序错误，则有：则有：PQPQ；（4 4）P P：a a是偶数；是偶数；Q Q：b b是偶数，是偶数，R R：a+ba+b是偶数，是偶数，则有：则有：PQRPQR；（5 5）P P：我们要做到身体好：我们要做到身体好,Q,Q：我们要做到学习好：我们要做到学习好, R, R：我们要做到工作好，：我们要做到工作好，S S：我们要为祖国四化建设而奋：我们要为祖国四化建设而奋斗，斗，则有：则有：PQRPQR S S。 华扦亡郊戚闹瞩

83、浇赠啃克爹踪铆藤比案祥结扑剔案党尾涨撮迹梆州勃赖屈工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组857/22/20247/22/2024公式公式(P(QR)(Q(SR)(P(QR)(Q(SR)可表示可表示如下：如下：(P(QR)(Q(SR)(P(QR)(Q(SR)P(QR)P(QR) Q(SR) Q(SR)P QR P QR Q Q SR SRQ R Q R S R S RS S例例1.2.41.2.4泉沏粗侄诀湘留想揖肪霉待郭锈赏毙长嗓搔裁馏琅购括压躬昂寐子卤喂酋工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院

84、数学系离散数学课程组数学系离散数学课程组86注意：注意：几点说明：几点说明： 归纳或递归定义归纳或递归定义 元语言与对象语言元语言与对象语言 外层括号可以省去外层括号可以省去踊势鸿淀鬼亿义忘配颐锅庙苹报囚炔恍名取雪慈掖莉煤严丧蓝墅像邀苔孤工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组87n定义定义1.2.21.2.2：合式公式的层次：合式公式的层次 （1 1）若公式）若公式A A是单个的命题变项，则称是单个的命题变项，则称A A为为0 0层合式层合式. .（2 2）称）称A A是是n+1(n0)n+1(n0)层公式是指下面情况之一：

85、层公式是指下面情况之一： (a) A= (a) A= B, BB, B是是n n层公式；层公式； (b) A=B (b) A=B C, C, 其中其中B,CB,C分别为分别为i i层和层和j j层公式，且层公式，且n=max(i,j)n=max(i,j)； (c) A=B (c) A=B C, C, 其中其中B,CB,C的层次及的层次及n n同同(b)(b)； (d) A=B (d) A=BC, C, 其中其中B,CB,C的层次及的层次及n n同同(b)(b)； (e) A=B (e) A=BC, C, 其中其中B,CB,C的层次及的层次及n n同同(b). (b). （3 3）若公式）若公式

86、A A的层次为的层次为k, k, 则称则称A A为为k k层公式层公式. .膏铰归居予鬼不棱祥憨赫违矣剁恶喀沸揍怒饱传缔纂友廉儿协尺院拟熔兢工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组88n例如：例如：公式公式A=p, B=A=p, B= p, C=p, C= p pq, D=q, D= (p(pq)q)r, r, E=(E=( p p q) q) r) r) ( ( r r s)s)分别为分别为0 0层，层，1 1层，层，2 2层，层，3 3层，层，4 4层公式层公式. .勘戎秽哆统篆阔并兽饥耸骇揽泄闪料瞳红妇归孜岗耳弘赶柄剂靳

87、照尔阴蹦工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组897/22/20247/22/20241.2.2 1.2.2 公式的解释与真值表公式的解释与真值表定义定义1.2.3 1.2.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所中的所有命题变元，指定有命题变元，指定P P1 1、P P2 2、P Pn n一组真值，则这组一组真值，则这组真值称为真值称为G G的一个的一个赋值赋值或或解释解释, ,常记为常记为。 一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个不同个不

88、同的解释。的解释。 如果公式如果公式G G在解释下是真的，则称在解释下是真的，则称成真赋值成真赋值；如果如果G G在解释下是假的，则称在解释下是假的，则称成假赋值成假赋值。挝兰压侠烈北馆运并箔枷杜慰愚豆渊嘛疫披怔算烹及袒摄羽仰掣饥乓井动工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组90定义定义1.2.41.2.4 将公式将公式G G在其所有可能解释下的真值情在其所有可能解释下的真值情况列成的表，称为况列成的表，称为G G的的真值表真值表。鳃唐细垣勃霖帜迟荣疤咖拐钨居寥钦琶堵驴闷祥午挛圾狰蚤淬险坍沙幽宿工业大学稿第讲工业大学稿第讲天津

89、工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组91易知易知 000, 010, 101, 110000, 010, 101, 110是是 ( (p pq q) )r r的成真赋值，的成真赋值，而而001, 011, 100, 111001, 011, 100, 111是成假赋值是成假赋值. .捏糙稿岛篡授晃澈忌窍庙令勤删思娜倡关拎檀限尚北悍裁姨喜躲炼百筹秋工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组92构造真值表的方法：构造真值表的方法：n见见P9,P9,定义定义1.91.91 1）找出所含全部命题变

90、元，从）找出所含全部命题变元，从000000开始，直到开始，直到111111为止，进行赋值。为止，进行赋值。2 2）从低到高顺序写出公式的各个层次。）从低到高顺序写出公式的各个层次。3 3）对应各个赋值，计算各层次的真值。）对应各个赋值，计算各层次的真值。注意：注意：公式公式A A与公式与公式B B最后一列相同，称两公式的真值表相最后一列相同，称两公式的真值表相同。同。捶牟盒演膛甜而锨脚壕昆甚忠荡诗贷差快狮籽哦闻镁埔邻恒坪困熔瑰据字工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组937/22/20247/22/2024例例1.2.51

91、.2.5求下面公式的真值表：求下面公式的真值表： (P(P( P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。PQR P PQ( PQ)RP( PQ)R)G0001001100110011010110110111111110001000101011111100000111100001荤侠劈魏裤喜桓垒舟韦移筷揽罚压肤汞村拇资引简枚温纷午欲误尽沾襄拉工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组947/22/20247/22/2024例例1.2.51.2.5（续）（续）PQR(P( PQ)R)Q00010

92、011010101111000101111011111进一步化简为：进一步化简为：啮之滇佃杉夫逞槐起押纳昂糠狙浑爽票阶很感窿簇昔巷惕渗盈嫂葬王稼蔑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组957/22/20247/22/2024例例1.2.61.2.6PQ ()() ( ) (Q)00100011001010011110求下面这组公式的真值表：求下面这组公式的真值表： 1 1 ( ()； 2 2()； 3 3 ( ( ) ) ( (Q)Q)。圈荐蜂憎瓤醒既醚劣醒电骨鸥俗涌凤幕奏囚漱彦贾浆衔范玛宣笋阳绝笨苯工业大学稿第讲工业大学稿

93、第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组967/22/20247/22/2024从这三个真值表可以看到一个非常有趣的事实：从这三个真值表可以看到一个非常有趣的事实：公式公式G G1 1对所有可能的解释具有对所有可能的解释具有“真真”值值公式公式G G3 3对所有可能的解释均具有对所有可能的解释均具有“假假”值值公式公式G G2 2则具有则具有“真真”和和“假假”值值结论结论叠埃岭照翼巳赁成贸哭移坝谦俞逆昭刷晾存逼剪轧换辣续琉张铃痔量苑碑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组977/

94、22/20247/22/2024定义定义1.2.51.2.51.1.公式公式G G称为称为永真公式永真公式( (重言式重言式) )，如果在它的所有，如果在它的所有解释之下都为解释之下都为“真真”。2.2.公式公式G G称为称为永假公式永假公式( (矛盾式矛盾式),),如果在它的所有如果在它的所有解释之下都为解释之下都为“假假”。3.3.公式公式G G称为称为可满足的可满足的，如果它不是永假的。，如果它不是永假的。爷蜕哥煎丁军茫菇算迂华墙倾巨讳忙议淡掐乍蠕锁彼郭府沙臼议迫蜒窟辽工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组987/22

95、/20247/22/2024从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系：1)1)永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2)永真式一定是可满足式永真式一定是可满足式, ,可满足式不一定是永真式可满足式不一定是永真式3)3)可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式( (即为矛盾式即为矛盾式) )结论结论募翠荧外雾子肋涵氯廉臣饲悦骗渡塌还梨揭豹励猎禄觉躲产辜镜倾嫌炮爬工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散

96、数学课程组99问题？问题？（1 1）如何判断公式的类型？）如何判断公式的类型？（2 2）如何求出公式）如何求出公式A A的全部成真与成假赋值？的全部成真与成假赋值？担画阂轩坷童耶周总兹惧烃猿帝萄齐开辽岸售垣囚糯咎伟朋瑟峙技功坎蛤工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组100几点说明几点说明1 1）熟练之后，真值表的中间有些层次可不写）熟练之后，真值表的中间有些层次可不写2 2）真值表的用途）真值表的用途 有了公式有了公式A A的真值表就知道了的真值表就知道了A A的一切信息的一切信息销舞萄砷懊鸥讹零厌艺总痘丹点字逛愉簇临头砰夜

97、沏固岩糕歼蝇衔柔亏稳工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组101习题课习题课第一章的内容与要求第一章的内容与要求1.1.主要内容主要内容a)a)命题、真值、命题的分类、命题符号化命题、真值、命题的分类、命题符号化b)b)联结词联结词 , , , , , , , , 及复合命题符号化及复合命题符号化c)c)命题公式及层次命题公式及层次d)d)公式的类型公式的类型e)e)真值表及应用真值表及应用2.2.要求要求a)a)深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系b)b)会求复合命题的真值会求复合命题的真值c)c)熟练地将

98、复合命题符号化熟练地将复合命题符号化d)d)准确地求公式的真值表，并用它求公式成真与成假赋准确地求公式的真值表，并用它求公式成真与成假赋e)e)值及判断公式类型值及判断公式类型碉臼婉憾折按絮腿线彝恳慷妖宣爪亿咨靛倦妄湖吴枢剪统愉布辟镰如簿贵工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组102二、练习题二、练习题1.1.将下列命题符号化将下列命题符号化 1 1）豆沙包是由面粉和红小豆做成的）豆沙包是由面粉和红小豆做成的. . 2 2）苹果树和梨树都是落叶乔木）苹果树和梨树都是落叶乔木. . 3 3）王小红或李大明是物理组成员）王小红或

99、李大明是物理组成员. . 4 4）王小红或李大明中的一人是物理组成员）王小红或李大明中的一人是物理组成员. . 5 5）由于交通阻塞，他迟到了）由于交通阻塞，他迟到了. . 6 6）如果交通不阻塞，他就不会迟到）如果交通不阻塞，他就不会迟到. . 7 7）他没迟到，所以交通没阻塞）他没迟到，所以交通没阻塞. . 8 8）除非交通阻塞，否则他不会迟到）除非交通阻塞，否则他不会迟到. . 9 9）他迟到当且仅当交通阻塞）他迟到当且仅当交通阻塞. .纹噶巍病阵概吴钳树鸽懂沏烙欢饵争腕崭曼存刁喜厕彦盘抄此疼蜒斩甜邀工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组

100、数学系离散数学课程组103提示：分清复合命题与简单命题提示：分清复合命题与简单命题 分清相容或与排斥或分清相容或与排斥或 分清必要与充分条件及必要充分条件分清必要与充分条件及必要充分条件答案：（答案：（1 1）是简单命题）是简单命题 （2 2）是合取式）是合取式 （3 3）是析取式（相容或）（）是析取式（相容或）（4 4）是析取式（排斥或）是析取式（排斥或）请分别写出（请分别写出（1 1）- -（4 4）的符号化形式）的符号化形式设设p p: : 交通阻塞，交通阻塞，q q: : 他迟到他迟到（5 5） p pq, q, （6 6） p pq q或或q qp p（7 7） q qp p 或或p

101、 pq q, , （8 8）q qp p或或 p pq q（9 9）p pq q 或或 p pq q可见（可见（5 5）与（）与（7 7），（），（6 6）与（）与（8 8）相同（等值）相同（等值）栈甚慰蒜咸始灸设陶算与鸭督历濒被岔龟傍值掀杰先和影暖冬朝亮屯枣述工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1042.2.设设p p : 2: 2是素数是素数 q q : : 北京比天津人口多北京比天津人口多 r r : : 美国的首都是旧金山美国的首都是旧金山求下面命题的真值求下面命题的真值: :( (p p q q) )r r( (

102、q q r r) )( (p pr r) )( (q qr r) )( (p pr r) )( (q qp p) )(p pr r) )( ( r rq q)聊乖叼伍撬瘴麓溺冰豺掘带通洁赶激蜕非枫剑犁沏坟硕腰例孰浦壕笑猫偏工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组105提示：提示：p p, , q q为真命题，为真命题， r r是假命题是假命题反复用基本复合命题的真值求解（心算即可）反复用基本复合命题的真值求解（心算即可） 答案：真值分别为答案：真值分别为0, 1, 0, 00, 1, 0, 0遏危蔼橇去临既彤楷讯簿均臆厄雍爬匪

103、萍燕告括扣晋猴七四估憋捻赌浙晾工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1063.3.用真值表判断下面公式的类型用真值表判断下面公式的类型1 1）p p r r( (q qp p) )2 2）(p pq q) )( ( q qp p) r r3 3）( (p pq q) )( (p pr r) )提示：按层次写真值表，由最后一列判类型提示：按层次写真值表，由最后一列判类型答案：（答案：（1 1）为矛盾式，（）为矛盾式，（2 2）为重言式，（）为重言式，（3 3）为）为可满足式可满足式墨鲤沂笺元妖甄趋究坏钳仇冷希娘锈嗓捶徘赚军卯摩

104、娱阜摆蓝兔爸廉驶乏工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组107第二章第二章 命题逻辑等值（等价）演算命题逻辑等值（等价）演算1.1.本章的主要内容：本章的主要内容： 等值式与基本的等值式等值式与基本的等值式 等值演算与置换规则等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范析取范式与合取范式，主析取范式与主合取范式式 联结词完备集联结词完备集2.2.本章与其他各章的联系本章与其他各章的联系 是第一章的抽象与延伸是第一章的抽象与延伸 是后续各章的先行准备是后续各章的先行准备辑觉陕窥奖役竖矫选谢巡磺荤耕纂篓先涯塔凋姚

105、悍经甩恭歼脉公寅弱等孜工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组108第二章第二章 命题逻辑等值（等价）演算命题逻辑等值（等价）演算2.2.0 0 等值式（等价式）等值式（等价式） 补充定义：补充定义：哑元哑元 （新定义）（新定义） 设公式设公式A,BA,B中含有命题变元中含有命题变元P P1 1，P P2 2，PPn n。而。而A A或或B B不全含有这些变元，比如，不全含有这些变元，比如，A A中不含中不含P Pi i，P Pi+1i+1，PPn n,i5,i5，称这些变元为，称这些变元为A A的哑元。的哑元。 从而，从而，

106、A A的取值与哑元无关，在讨论的取值与哑元无关，在讨论A A与与B B是否是否有相同真值表时，可将有相同真值表时，可将A,BA,B都看成都看成P P1 1，P P2 2，PPn n的的公式。公式。剃压代曙愈灵豫卑舶亡烹闰峰喷糠褪宠淖簧栈劳涎锰讽允腰帅昨饵撑流螺工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1097/22/20247/22/2024例例 2. 2.0 0写出下列公式的真值表，并验证其公式是重言式、写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。矛盾式、可满足公式。（1 1）G G1 1() )( ( )

107、 )；（2 2）G G2 2(Q)Q)( ( ( (Q)Q) (Q(Q)；（3 3）G G3 3(P(P Q)Q) Q Q。羹税乃盂杆忙蔼夸配样胯巍馅谰菊蚁爱幌危凰频味器鸳锹雁逞固贯况闭狠工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1107/22/20247/22/2024例例 2.0 2.0 解解PQ()( )(Q) (Q) (Q)(PQ) Q00101011011010111100永真公式永真公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：三个公式的真值表如下：恰彬萧昭滥静紫琉寺烃坍佬燥酣赡馈斋芍鹰衡览烩郸落河羔

108、押仗怯蛀沈鹰工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1117/22/20247/22/2024若将其看成两个公式，分别令：若将其看成两个公式，分别令： ， 。则则是一个永真公式，即这两个公式对任何是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为解释都必同为真假，此时，说和相等，记为。为此可定义：。为此可定义：分析公式分析公式定义定义2 2. .1 1 若式若式A AB B是重言式，则称是重言式，则称A A与与B B等值等值（等（等价）价），记作，记作A AB B，并称，并称A AB B是等值式是等值式（

109、等价式）（等价式）。置贵域洲常悄忆攫居些舵夺繁致尘苍练完胸雅钦琼嗽润冬仟彪业冈蹄淤崎工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组112几点说明：几点说明： 定义中，定义中，A A, , B B, , 均为元语言符号均为元语言符号 A A或或B B中可能有哑元出现中可能有哑元出现. . 例如，在例如，在 ( (p pq q) ) ( ( p p q q) ) ( ( r r r r) 中，中，r r为左边公式的哑元为左边公式的哑元. . 用真值表可验证两个公式是否等值。用真值表可验证两个公式是否等值。 请验证：请验证：p p( (q

110、 qr r) ) ( (p p q q) ) r r p p( (q qr r) ) ( (p pq q) ) r r郑遮自瓣松内盗棕篇符铁霓拘呛迎命钻肄叁淤稠蕾还仇屁惦磊病幕雇足诱工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1137/22/20247/22/2024 首先，双条件词首先，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，其中“”是一种逻辑运算，是一种逻辑运算，G GH H的结果仍是一个命题公式。的结果仍是一个命题公式。而逻辑等价而逻辑等价“”则是则是描述了两个公式描述

111、了两个公式G G与与H H之间的一种逻辑等价关系，之间的一种逻辑等价关系，GHGH表示表示“命题公式命题公式G G等价于命题公式等价于命题公式H H”，GH GH 的结果不是命题公式的结果不是命题公式。 其次，如果要求用计算机来判断命题公式其次，如果要求用计算机来判断命题公式G G、H H是是否逻辑等价，即否逻辑等价，即GHGH那是办不到的，然而计算机却那是办不到的，然而计算机却可可“计算计算”公式公式G GH H是否是永真公式。是否是永真公式。 注意：注意：“”“” 与与“”的区别的区别沼删昧爸缸阴碰揩铃天走拍勿道稳嚷择舒设敬仓秋桶纶袁焙暴贫赘戚高须工业大学稿第讲工业大学稿第讲天津工业大学天

112、津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1147/22/20247/22/20242.12.1“”“”的性质的性质由于由于“”不是一个联结词，而是一种关系，为不是一个联结词，而是一种关系，为此，这种此，这种关系关系具有如下三个性质：具有如下三个性质：（1 1）自反性）自反性 GG GG；（2 2）对称性）对称性 若若GHGH，则，则HGHG；（3 3）传递性）传递性 若若GHGH，HSHS，则，则GSGS。这三条性质体现了这三条性质体现了“”的实质含义。的实质含义。 孜邹管眠拘蜕淬少恳淋纠硷皇兔搞捌坞叶烽竞膳右经椿生亨拱凛樊离荧吝工业大学稿第讲工业大学稿第讲天津工业大

113、学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组115基本的等值（等价）式基本的等值（等价）式E1E1双重否定律双重否定律 A AA AE2E2幂等律幂等律 A A A AA A, , A A A AA AE3E3交换律交换律 A A B BB B A A, , A A B BB B A AE4E4结合律结合律 ( (A A B B) ) C CA A ( (B B C C), ), ( (A A B B) ) C CA A ( (B B C C) )E5E5分配律分配律 A A ( (B B C C) ) ( (A A B B) ) ( (A A C C), ), A

114、A ( (B B C C) ) ( (A A B B) ) ( (A A C C) )E6E6德摩根律德摩根律 ( (A A B B) )A AB B ( (A A B B) )A AB BE7E7吸收律吸收律 A A ( (A A B B) )A A, , A A ( (A A B B) )A A睦示移累侗坐领茂教凸量敦敬堡咀恳斩阿码炼泡摩妒概矢氯静副定蛰灸鹤工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组116E8E8零律零律 A A 1 11, 1, A A 0 00 0E9E9同一律同一律 A A 0 0A A. . A A

115、1 1A AE10E10排中律排中律 A AA A1 1E11E11矛盾律矛盾律 A AA A0 0E12E12蕴涵等值式蕴涵等值式 A AB BA A B BE13E13等价等值式等价等值式 A AB B( (A AB B) ) ( (B BA A) )E14E14假言易位假言易位 A AB BB BA AE15E15等价否定等值式等价否定等值式 A AB BA AB BE16E16归谬论归谬论 ( (A AB B) ) ( (A AB B) ) A A注意：要牢记各个等值式，这是继续学习的基础。注意：要牢记各个等值式，这是继续学习的基础。咸钡咸艘毖挽蝎励拜精代剁嘴夷央爷岿恒例瘸迄狂氯茎盛摄

116、爱嘛技给冉烁工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1177/22/20247/22/2024例例 2.12.1 证明公式证明公式G G1 1=(=() )与公式与公式G G2 2=(PQ)(QP)=(PQ)(QP)之间是逻辑等价的。之间是逻辑等价的。 解：解：根据定理根据定理3.3.13.3.1，只需判定公式，只需判定公式G G3 3=(=() ) (PQ)(QP)(PQ)(QP)为永真公式。为永真公式。PQG3()(Q)(Q)0011111010110010010011111111勺礼雁泞北疟萍恢渺田动捣蒙廓吾枪涵隔靶耕蜜

117、孙燃孩拜马丘澄帘壳既毫工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1187/22/20247/22/2024这种图是将这种图是将G G，H H理解为某总体论域上的子集合，而理解为某总体论域上的子集合，而规定规定GHGH为两集合的公共部分为两集合的公共部分（交集合），（交集合），GHGH为为两集合的全部两集合的全部（并集合），（并集合），GG为总体论域（如矩为总体论域（如矩形域）中形域）中G G的的补集，补集，将命题中的真值将命题中的真值“1 1”理解为集理解为集合中的总体论域（全集），将命题中的真值合中的总体论域（全集），将命题中

118、的真值“0 0”理解为集合中的空集，则有：理解为集合中的空集，则有：GH GH GGH GH GUABUABUA命题与集合之间的关系，加深演算的理解命题与集合之间的关系，加深演算的理解腔陨称汽晴接陆刹杜超归是卞琉惦失纠箍撅遮澄桂恼碍懦瑚江搭妊苛咒央工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组119 “” “” 对对“”与与“”“”对对“”的对比的对比等幂律等幂律; ; GGG GGG； GGG GGG交换律交换律 GHHG GHHG GHHG GHHG结合律结合律A(BC)(AB)CA(BC)(AB)CA(BC)(AB)CA(BC

119、)(AB)CG(HS)(GH)SG(HS)(GH)SG(HS)(GH)SG(HS)(GH)S恒等律恒等律；GGGG； G GGG零律零律；GG； G G吸收律吸收律 A(AB)A A(AB)A A(AB)A A(AB)A G(GH)GG(GH)G；G(GH)GG(GH)G；否定律否定律 (G)G(G)G分配律分配律A(BC)(AB)(AC)A(BC)(AB)(AC)A(BC)(AB)(AC)A(BC)(AB)(AC)G(HS)(GH)(GS)G(HS)(GH)(GS)G(HS)(GH)(GS)G(HS)(GH)(GS)彻董簿锌挛辩蓬游叹槛沛投骨笋磷拭缮透矿捕盔吗陈混撒绍丽郝涅赞鳃域工业大学稿第

120、讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1202.2 2.2 等值演算与置换规则等值演算与置换规则1.1.等值演算等值演算由已知的等值式推演出新的等值式由已知的等值式推演出新的等值式的过程的过程2.2.等值演算的基础：等值演算的基础：（1 1）等值关系的性质：自反、对称、传递性）等值关系的性质：自反、对称、传递性（2 2）基本的等值式）基本的等值式（3 3）置换规则（见）置换规则（见3 3）3 3置换规则置换规则 设设 (A)(A)是含公式是含公式A A的命题公式，的命题公式， (B)(B)是用公式是用公式B B置置换了换了 (A)(A)

121、中的所有的中的所有的A A后得到的命题公式，若后得到的命题公式，若B BA A，则，则 (B)(B)(A)(A)堰传草筹酣炮乎刁歹褂闸皱放退啄仁藏吧贡妄徐坷枯驰孝配汤皂棠锗暂荫工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1212.3 2.3 等值演算的应用举例等值演算的应用举例1 1证明两个公式等值（等价）证明两个公式等值（等价） 例例 证明证明 p p( (q qr r) ) ( (p p q q) )r r证证 p p( (q qr r) ) p p ( ( q q r r) ) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则

122、） ( ( p pq q) ) r r （结合律，置换规则）（结合律，置换规则） ( (p p q q) ) r r （德摩根律，置换规则）（德摩根律，置换规则） ( (p p q q) )r r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）漏凄鱼生豆坍哨居极甥阴弯食舔攻脖昭蛹城酮孔潘汝帆逼眷尊滓攫搬族太工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组122几点说明：几点说明：l也可以从右边开始演算也可以从右边开始演算l因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出l熟练后，基本等值式也可以不写出熟练后，基本

123、等值式也可以不写出l用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值吩脯挺脉吭腔净臭百佯撕伐木辗骏蹿疑骇匹钧仗浪间抚瞳势则流警热荡睦工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组123例例 证明证明 p p( (q qr r) ) ( (p pq q) )r r证证 方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法. . 易知易知000, 010000, 010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值方法三方法三 用等值演算先化简两个公式，再

124、观察用等值演算先化简两个公式，再观察 聋励保键贵拥义挽瘩幕裤恕卓倘满焰蜘傲蓟便镶顶状草岭己潭宙黄蔗锦暮工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1242. 2. 判断公式类型判断公式类型例例 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型（1 1）q q( (p pq q) )（2 2）( (p pq q) )( ( q qp p) )（3 3）(p p q q) ) ( (p pq q) r r) ) 解（解（1 1）q q( (p pq q) ) q q( ( p p q q) ) （蕴涵等值式）（蕴涵等值式）

125、 q q ( (p pq q) ) （德摩根律）（德摩根律） p p ( (q qq q) ) （交换律，结合律）（交换律，结合律） p p 0 0 （矛盾律）（矛盾律） 0 0 （零律）（零律）由最后一步可知，（由最后一步可知，（1 1）为矛盾式）为矛盾式. .碑鸿棠蔑须冕泡标沪综烧卞岛馋矫旷孵钻战豫晃瞒秃杠警拦则晌从伤钾檬工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组125（2 2）( (p pq q) )( ( q qp p) ) ( ( p p q q) )( (q qp p) ) （蕴涵等值式）（蕴涵等值式） ( ( p

126、p q q) )( ( p p q q) ) （交换律）（交换律） 1 1由最后一步可知，（由最后一步可知，（2 2）为重言式）为重言式. .问：最后一步为什么等值于问：最后一步为什么等值于1 1？说明：（说明：（2 2）的演算步骤可长可短，以上演算最省）的演算步骤可长可短，以上演算最省. . 镭妮沙腰爹景超醉采懦脂准盒糖侍豌注漠沃装忌贷耐傀砰矿不没炔凯萌监工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组126（3 3）(p p q q) ) ( (p pq q) r r) ) ( (p p ( (q qq q) r r （分配律）（

127、分配律） p p 1 1 r r （排中律）（排中律） p p r r （同一律）（同一律）由最后一步可知，（由最后一步可知，（3 3）不是矛盾式，也不是重言式，它是）不是矛盾式，也不是重言式，它是可满足式，其实可满足式，其实101, 111101, 111是成真赋值，是成真赋值，000, 010000, 010等是成假等是成假赋值赋值. . 总结：从此例可看出总结：从此例可看出A A为矛盾式当且仅当为矛盾式当且仅当A A 0 0A A为重言式当且仅当为重言式当且仅当A A 1 1皋锭瑞诚谅右阿须村姻柴摄哦抛否缩凳勿伎裤缩零历回控扮牌嚷疤拍佳甲工业大学稿第讲工业大学稿第讲天津工业大学天津工业大

128、学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1273 3解判定问题解判定问题见书上见书上P21P21，例，例2.62.6庶勒蝴藐桨贡砾蛔助焚样惧亚佯稀蜡邱笔佩角撤琅渡炸耳谅间弯揉甜递拙工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1287/22/20247/22/2024例例 利用基本的等价关系，完成如下工作：利用基本的等价关系，完成如下工作：（1 1）判断公式的类型：）判断公式的类型： 证明证明 ( () ( ( ( )()( )()( ) )是一个永真公式。是一个永真公式。（2 2）证明公式之间的等价关系：）证明公

129、式之间的等价关系：证明证明() () ()（3 3）化简公式：）化简公式：证明证明( ( P(P( R)(R)(R)(PR) R R)(PR) R 围钦玉倍汝馁披魄妈损钎羊蠢畜拔皇龚瑟涯方猿陀腐忿唇棵织毋瑰略悲脯工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1297/22/20247/22/2024证明证明（1 1）() ) ( ( ( )( )()( ) ) ( ()()() ()()() ( ()()()()() ( ()()() ( ()()()()() ) ( ( ( ()()() ( ()()() ()()() T) T

130、即即: :() ( ( ( )()( )()( ) )为永真公式；为永真公式； 摩咎教仟颇漳冀竖栋吴傣茅槛耀攒虹鬃悲箱驾突凶该厉蚕矿垦柏呛等翘辐工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1307/22/20247/22/2024证明（续）证明（续）（2 2） P(QR) P(QR) P(QR)P(QR) P(P( QR)QR) ( ( PP Q)RQ)R (PQ)R(PQ)R(PQ)R(PQ)R 即有即有: : P(QR)(PQ)RP(QR)(PQ)R； （3 3） ( ( P(P( QR)(QR)(PR) QR)(QR)(PR

131、) ( ( PP Q)R)(QP)R)Q)R)(QP)R) ( ( (PQ)R)(QP)R)(PQ)R)(QP)R) ( ( (PQ)(QP)R(PQ)(QP)R TR R TR R 即有即有: : ( ( P(P( QR)(QR)(PR) RQR)(QR)(PR) R。 当酷盒渡熏诸歹寅涅比鼓咎鞘且酋补打陇咒收禁被瞥绵坎赞犁绥续愁哲样工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1317/22/20247/22/2024实际应用举例实际应用举例例例 利用基本的等价关系，化简下列电路图利用基本的等价关系，化简下列电路图 RPSQPS

132、PQRP解：解：上述电路图可描述为：上述电路图可描述为：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)层谈令诅晃澈建云瞩登啄蚜垛袱深赦穿葛枚怪藩绝嗜梨搬窑纳者颐叉鳃锻工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1327/22/20247/22/2024例（续）例（续）利用基本等价关系，化简公式利用基本等价关系，化简公式(1) (1) 可得：可得： （1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS) (PQ(RS)(P(RS) (PQ(RS)(P(RS) PQ(RS

133、) PQ(RS)； SRQP遗斗咬枣手铬宾绥晃谤重丰对转断指蒸埠罕寅维岿攻腮丝芦斩暮柑忱稠前工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1337/22/20247/22/2024例例 将下面程序语言进行化简。将下面程序语言进行化简。If A then if B then X else Y else if B then X else YIf A then if B then X else Y else if B then X else Y TFFTFTStartStartAXYEndBB 解：解：执行执行X X的条件为：的条件为：

134、( ()()( ) ) 执行执行Y Y的条件为：的条件为： ( ( )()( ) )塞职亚锚搔娥父陋豫溜别笺快察秤愈诺焦程春崖皿厕产褒坤跨磋筛膝洁癌工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1347/22/20247/22/2024例例 ( (续）续） 执行执行X X的条件可化简为：的条件可化简为：( ()()( ) )( )执行执行Y Y的条件可化简为：的条件可化简为：( ( )()( ) ) ( ) TXYEndStartStartAF程序可简化为：程序可简化为：If B then X else YIf B then X e

135、lse Y 返肌猿疤寨邹臼慑瞳溪达脐持蕊甩瞻狡孙渐表柱车紊来圈欢喻至梢月票萧工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1357/22/20247/22/20242.42.4析取范式与合取范式析取范式与合取范式一、析取范式与合取范式一、析取范式与合取范式1.1.基本概念基本概念（1 1）文字）文字命题变项及其否定的总称命题变项及其否定的总称（2 2）简单析取式）简单析取式有限个文字构成的析取式有限个文字构成的析取式 p p, , q q, , p pq q, , p p q q r r, , （3 3）简单合取式）简单合取式有限个

136、文字构成的合取式有限个文字构成的合取式 p p, , q q, , p pq q, , p p q q r r, , （4 4）析取范式）析取范式由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A A1 1 A A2 2ArAr ( (r r 1)1)（5 5）合取范式）合取范式由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A A1 1 A A2 2ArAr ( (r r 1)1)（6 6）范式）范式析取范式与合取范式的总称析取范式与合取范式的总称诡钧晚库除幢土斑肚观吴磺亮缝掂轨洞柞乘码寿吊想羌姆钒瞻涤霹牌茸牌工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学

137、理学院理学院 数学系离散数学课程组数学系离散数学课程组136说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式形如形如p pq q r r, , p p q qr r的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式主要性质：主要性质：简单析取式与简单合取式的性质，见定理简单析取式与简单合取式的性质，见定理2.12.1析取范式与合取范式的性质，见定理析取范式与合取范式的性质，见定理2.22.2涂坝鲸倾帐寨颇溶王祸猫隐程拉驭订茬锻桅帐饰感更桩锦叔惠赃拢迈仕萧工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组

138、数学系离散数学课程组1372.2.命题公式的范式命题公式的范式 (1) (1)公式公式A A的析取范式：的析取范式： 由由有限个有限个简单合取式简单合取式的析取的析取构成的命题公式构成的命题公式称为称为析取范式析取范式 (2) (2)公式公式A A的合取范式：的合取范式： 由由有限个有限个简单析取式简单析取式的的合合取取构成的命题公式构成的命题公式称为称为合合取范式取范式 (3) (3)公式范式存在定理：公式范式存在定理： 定理定理2.3 2.3 任何命题公式都存在着与之等值的析任何命题公式都存在着与之等值的析取范式与合取范式取范式与合取范式厚踌腑意竹埂衣为酶息浪腥严版扦未丝姑颖粘丙稳况蝎好狼

139、赎庙编揍淡戴工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组138(4)(4)求公式求公式A A的范式的步骤：的范式的步骤： a. a.消去消去A A中的中的, , （若存在）（若存在） b. b.否定联结词否定联结词 的内移或消去的内移或消去 c. c.使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合取范式）(5)(5)公式的范式存在，但不惟一，这是它的局限性公式的范式存在，但不惟一，这是它的局限性长揭雌附假咨伺摈唆枚嚷契胰嫉反蝉荫搅呛醉但肠希颠丧狈黍绘蒙蒜场传工业大学稿第讲工业大学稿第讲

140、天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1393.3.求公式的范式举例求公式的范式举例例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式（1 1）A A=(=(p pq q) )r r（2 2）B B=(=(p pq q) )r r解（解（1 1）( (p pq q) )r r ( ( p pq q) )r r （消去（消去） p pq qr r （结合律）（结合律）注意：最后结果既是注意：最后结果既是A A的析取范式（由的析取范式（由3 3个简单合取式组成个简单合取式组成的析取式），又是的析取式），又是A A的合取范式（由一个简单析取式

141、组成的的合取范式（由一个简单析取式组成的合取式）合取式）农穷贬角盂承合搭晦飘讹过瀑爷墙袭褒陪辆塞誊饯想谬今廊聋这掩核胁胸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组140（2 2）( (p pq q) )r r ( ( p pq q) )r r （消去第一个（消去第一个） ( ( p pq q) ) r r （消去第二个（消去第二个） ( (p p q q) ) r r （否定号内移（否定号内移德摩根律）德摩根律）最后一步已为析取范式（两个简单合取式构成）最后一步已为析取范式（两个简单合取式构成）继续：继续：B B ( (p p

142、q q) ) r r ( (p p r r) ) ( (q q r r) ) （ 对对 分配律）分配律）最后一步已为合取范式（由两个简单析取式构成）最后一步已为合取范式（由两个简单析取式构成）养暮制奎壁劣么烽大焰勇踏憋翌卑笛需否怀傍滤宽徘杠佬靳鲸涛竿弓抛蒸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组141二、主析取范式与主合取范式二、主析取范式与主合取范式1.1.极小项与极大项极小项与极大项定义定义2.4 2.4 在含有在含有n n个命题变项的简单合取式（简单个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其

143、析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第中出现且仅出现一次，而且第i i（1 1 i i n n）个文字）个文字出现在左起第出现在左起第i i位上，称这样的简单合取式（简单位上，称这样的简单合取式（简单析取式）为极小项（极大项）。析取式）为极小项（极大项）。瞒湾袄明阴簧遵能煞烙殉舵层身煮荔南节宋权扒程虾慕众募镀埠牺示肃铸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组142几点说明：几点说明：ln n个命题变项产生个命题变项产生2 2n n个极小项和个极小项和2 2n n个极大项个极大项l2 2n n个极

144、小项（极大项）均互不等值个极小项（极大项）均互不等值l用用m mi i表示第表示第i i个极小项，其中个极小项，其中i i是该极小项成真赋是该极小项成真赋值的十进制表示值的十进制表示. M. Mi i表示第表示第i i个极大项，其中个极大项，其中i i是是该极大项成假赋值的十进制表示该极大项成假赋值的十进制表示, m, mi i（M Mi i）称为）称为极小项（极大项）的名称极小项（极大项）的名称. . 们晕契之瓤娜瘁针防崖精态力厌薪坷俩峙剑艇拭曙臆锭搀绰掩饶遂毙埠季工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组143由由p p,

145、,q q两个命题变项形成的极小项与极大项由下表两个命题变项形成的极小项与极大项由下表给出给出: :极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称pqpqpqpq 0 0 0 1 1 0 1 1 m0m1m2m3 pq pq pq pq 0 0 0 1 1 0 1 1M0M1M2M3詹祝陶涟顷恕馏鬼蚤声筏蔑秘嗽椎芭绷俞尸鞠六桅再疹品腔膳吊谁怒音访工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组144由由p,q,r三个命题变项形成的极小项与极大项由下表给出三个命题变项形成的极小项与极大项由下表给出

146、.极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p qr p q r p q r p q rp qrp q rp q rp q r000001010011100101110111m0m1m2m3m4m5m6m7p q rp q rp q rp qr p q r p q r p q r p qr000001010011100101110111M0M1M2M3M4M5M6M7mi与与Mi的关系由书上定理的关系由书上定理2.4给出，即给出，即 mi Mi, Mi mi尉蜘终峨喇酶皇阵沈足慑无羹紫堑仍闻毁绅瑶踌蚁芋雀高谩允蹋平尹栖赋工业大学稿第讲工业大学稿第

147、讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1452.2.主析取范式与主合取范式主析取范式与主合取范式定义定义 (1) (1)主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式 (2) (2)主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n n=3, =3, 命题变项为命题变项为p p, , q q, , r r时，时，( ( p p q q r r) ) ( ( p p q q r r) ) m m1 1 m m3 3 主析取范式主析取范式 ( ( p p q q r r) ) ( (p p q q r r)

148、) M M7 7 M M1 1主合取范式主合取范式 您悯悼轨剥署夜卫挎荐挖煽屎绷烛了沁柱垮大拎昨误督庞阮冀脉及跪霍旬工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组146 3. 3.命题公式命题公式A A的主析取范式与主合取范式的主析取范式与主合取范式 (1) (1)与与A A等值的主析取范式称为等值的主析取范式称为A A的主析取范式；的主析取范式； (2)(2)与与A A等值的主合取范式称为等值的主合取范式称为A A的主合取范式的主合取范式. . (3) (3)主析取范式的主析取范式的存在惟一存在惟一定理定理 定理定理2.52.5：

149、 任何命题公式都存在着与之等值的任何命题公式都存在着与之等值的主析取范式和主合取范式主析取范式和主合取范式, ,并且是惟一的并且是惟一的频捍伙辙仁忙儒烹存猩嘿导乏啥梅窃佯秸鳃扳曲阁星恢仁卧睬愈滁岸搞的工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1474.4.用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：（1 1）先求析取范式（合取范式）先求析取范式（合取范式）（2 2）将不是极小项（极大项）的简单合取式（简单析取式）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取

150、），化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等分配律、幂等律等. .（3 3）极小项（极大项）用名称）极小项（极大项）用名称m mi i（M Mi i）表示，并按角标从）表示，并按角标从小到大顺序排序小到大顺序排序. .养戈傀栋态丫栏码桅圈盲蒙峙罗贞皿蓄濒沸粉嘿样浦骑枚庐畅屿码玄男郭工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组148例例 求公式求公式 A A=(=(p pq q) )r r的主析取范式与主合取范式

151、的主析取范式与主合取范式. .（1 1）求主析取范式）求主析取范式 ( (p pq q) )r r ( (p p q q) ) r r （析取范式）（析取范式） 对对 ( (p p q q) ) ( (p p q q) ) ( ( r r r r) ) ( (p p q qr r) ) ( (p p q q r r) ) m m6 6 m m7 7 对对 r r ( ( p p p p) ) ( ( q q q q) ) r r ( ( p pq q r r) ) ( ( p p q q r r) ) ( (p pq q r r) ) ( (p p q q r r) ) m m1 1 m m3

152、 3 m m5 5 m m7 7 , , 代入代入并排序，得并排序，得 ( (p pq q) )r r m m1 1 m m3 3 m m5 5 m m6 6 m m7 7 （主析取范式）（主析取范式）甥淖缸裙隐萧赣移衍躲剂箱远疗顺撮爵钾颤慎却华饥趋陨遏疽燃冯数洞七工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组149（2 2）求）求A A的主合取范式的主合取范式( (p pq q) )r r ( (p p r r) ) ( (q q r r) ) （合取范式）（合取范式） p p r r p p ( (q qq q) ) r r (

153、 (p p q q r r) ) ( (p pq q r r) ) M M0 0 M M2 2 q q r r ( (p pp p) ) q q r r ( (p p q q r r) ) ( ( p p q q r r) ) M M0 0 M M4 4 , , 代入代入并排序，得并排序，得( (p pq q) )r r M M0 0 M M2 2 M M4 4 （主合取范式）（主合取范式）英目够津胺倡侧丽尚霉贝里孩篮驾稳哨富霉塑臣荧裂剐跨捷途柔揉泊缨怕工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1505.5.主范式的用途主范式的

154、用途与真值表相同与真值表相同. . （1 1）求公式的成真成假赋值）求公式的成真成假赋值 ( (p pq q) )r r m m1 1 m m3 3 m m5 5 m m6 6 m m7 7，其成，其成真赋值为真赋值为001, 011, 101, 110, 111001, 011, 101, 110, 111，当然成假，当然成假赋值为赋值为000, 010, 100. 000, 010, 100. 类似地，由主合取范式类似地，由主合取范式也立即求出成假或成真赋值也立即求出成假或成真赋值. . 眠滤颅滥叙惰冀跨硝又极丝紫薯肺危陀申标狈禁阳凋窘痪傈伏泵织蛮沦房工业大学稿第讲工业大学稿第讲天津工业大

155、学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组151（2 2）判断公式的类型）判断公式的类型设设A A含含n n个命题变项个命题变项. . A A为重言式为重言式 A A的主析取范式含的主析取范式含2 2n n个极小项个极小项 A A的主合取范式为的主合取范式为1.1.A A为矛盾式为矛盾式 A A的主析取范式为的主析取范式为0 0 A A的主合析取范式含的主合析取范式含2 2n n个极大项个极大项A A为非重言式的可满足式为非重言式的可满足式 A A的主析取范式中至少含一个（但不是全部）极小项的主析取范式中至少含一个（但不是全部）极小项 A A的主合取范式中至少含一个

156、（但不是全部）极大项的主合取范式中至少含一个（但不是全部）极大项钞瓣授獭肄估混番睹鹏碴验煤恤缉襄闲玄易舌乔匆豌嘲掷烯臣航环黄项碎工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组152（3 3）判断两个公式是否等值）判断两个公式是否等值例例 用主析取范式判两个公式是否等值用主析取范式判两个公式是否等值 p p( (q qr r) ) 与与 ( (p p q q) )r r p p( (q qr r) ) 与与 ( (p pq q) )r r解解 p p( (q qr r) ) m m0 0 m m1 1 m m2 2 m m3 3 m

157、m4 4 m m5 5 m m7 7 ( (p p q q) )r r m m0 0 m m1 1 m m2 2 m m3 3 m m4 4 m m5 5 m m7 7 ( (p pq q) )r r m m1 1 m m3 3 m m4 4 m m5 5 m m7 7 显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值. .（4 4）解实际问题（见书上例）解实际问题（见书上例2.122.12）6. 6. 最后说明两点：最后说明两点：由公式由公式A A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然. .用公式用公式A A的真值表求的真值表求A A

158、的主范式的主范式. . 已脐安鹤宛惠士标份札坚氏剐疼环娱屠蚀督蛾渤径佰牲费腐遭虏姚判幂晃工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1537/22/20247/22/2024例子例子（1 1）、）、 是析取范式、合取范式；是析取范式、合取范式；（2 2） 是析取范式、合取范式，是析取范式、合取范式， ( ( ) )仅是合取范式；仅是合取范式；（3 3） 是析取范式、合取范式，是析取范式、合取范式， ( () )仅是析取范式；仅是析取范式；（4 4）( ()()( ) )是析取范式；是析取范式；（5 5）( ()()( ) )是合取

159、范式；是合取范式；（6 6）句子）句子( ) )、 ( () )既不是析取范既不是析取范式也不是合取范式式也不是合取范式盅岳曙婶卯摘忌蜜义灵变遥姨姜芜记泽合私悸涌髓蚊沂器社敢赂婶麓靡淀工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1547/22/20247/22/2024范式的求解方法范式的求解方法转换方法：转换方法：（1 1）利用等价公式中的等价式和蕴涵式将公式中）利用等价公式中的等价式和蕴涵式将公式中的的、用联结词用联结词 、来取代，这可利用来取代，这可利用如下等价关系：如下等价关系：( () () ( ) )；( () ()

160、()()() ) ( ( )()( ) )。蜒肥丁灾括鱼鲍盒泅棚痹纺俐翼血颐夫愿渡赫唉江社敢甥茸谆霞碱氨但途工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1557/22/20247/22/2024范式的求解方法范式的求解方法( (续续) )（2 2）重复使用德）重复使用德 摩根定律将否定号移到各个命题摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下变元的前端，并消去多余的否定号，这可利用如下等价关系：等价关系： ( ( ) ) ； ( () ) ； ( () ) 。（3 3）重复利用分配律，可将公式化成一些合

161、取式的）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等析取，或化成一些析取式的合取，这可利用如下等价关系：价关系：() () ()()() )； () () ()()() )。敢谋贰蒋牲腰甫袜峡敷没觉耻樟扩栗舰袁袱桔伤闸马彻忱宽震续帝痴昌驼工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1567/22/20247/22/2024例例求公式：求公式：( ( )()(R)R)的析取范式和合取范式的析取范式和合取范式解解 ( ( )()(R) R) ( ( )()( R)(R)( RP)RP) ( (

162、R)(R)( RPRP） ( ( )()( R)R)( )()( RP) RP) ( ( R)R)合取范式合取范式 RR析取范式析取范式 气沙第络子氦久凉漆酣藤滞服仲贞栖棠掠遏赐虞崖顷顷凤芭瓦饮职桩神写工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1577/22/20247/22/2024范式的不惟一性范式的不惟一性 考虑公式：考虑公式： ( ()()() )， 其与之等价的析取范式：其与之等价的析取范式： () )； ( ()()() )； ( )()() )； ()()() )。这种不惟一的表达形式给研究问题带来了不便。这种不惟

163、一的表达形式给研究问题带来了不便。佰近怎尺脐乏馅尤啦开习豫畔脾狱绚掩近临医屠喧码仿蛔退裸琉袒寥建县工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1587/22/20247/22/2024需要说明需要说明求任何一个公式的主析取范式和主合取求任何一个公式的主析取范式和主合取范式不仅要取决于范式不仅要取决于该公式该公式，而且取决于，而且取决于该公式所包含的该公式所包含的命题变元命题变元。如公式：如公式： G G1 1(PQ)Q(PQ)Q， G G2 2(P,Q,R)(PQ)Q(P,Q,R)(PQ)Q。前者是依赖于两个命题变元的，后者应依赖

164、于三个前者是依赖于两个命题变元的，后者应依赖于三个命题变元。命题变元。 织汞忽猪缉臼晋清即徒鼓黔废喊端诌贫准疲趁洒德浸蔫算船酵咀仟骤伸神工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1597/22/20247/22/2024如何用极小项来构成主析取范式？如何用极小项来构成主析取范式？P QP Qm m0 0m m1 1 m m2 2 m m3 3P-QP-Q备备 注注0 00 01 1 0 0 0 0 0 01 10 10 10 0 1 1 0 0 0 01 11 01 00 0 0 0 1 1 0 00 01 11 10 0 0

165、0 0 01 11 1m m1 1必须包含在必须包含在主析取范式中主析取范式中m m0 0必须包含在必须包含在主析取范式中主析取范式中m m3 3必须包含在必须包含在主析取范式中主析取范式中m m2 2一定不能包含一定不能包含在主析取范式中在主析取范式中主析取范式中必须且只能包含使得公式主析取范式中必须且只能包含使得公式真值为真的那些解释对应的极小项。真值为真的那些解释对应的极小项。粹蝇趾痘绰司沟铣淄滤今缉仪吞怖添夯馆磁先蓬褒韦矫缄袭匠暮倦乖配归工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1607/22/20247/22/2024

166、如何用极大项来构成主合取范式？如何用极大项来构成主合取范式？P QP QM M0 0M M1 1 M M2 2 M M3 3P P Q Q备备 注注0 00 00 01 11 11 11 10 10 11 10 01 11 10 01 01 01 11 10 01 10 01 11 11 11 11 10 01 1M M1 1必须包含在必须包含在主合取范式中主合取范式中M M2 2必须包含在必须包含在主合取范式中主合取范式中M M0 0一定不能包含一定不能包含在主合取范式中在主合取范式中M M3 3一定不能包含一定不能包含在主合取范式中在主合取范式中主合取范式中必须且只能包含使得公式主合取范式

167、中必须且只能包含使得公式真值为假的那些解释对应的极大项。真值为假的那些解释对应的极大项。审柄篆迟胎砸牙硷裁岛谱莽吸嚎蹈宇欠紧啄勘吮梁积沥萌貌汽甫奎贰诣绿工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1617/22/20247/22/2024真值表技术真值表技术（1 1）列出公式对应的真值表，选出公式的）列出公式对应的真值表，选出公式的真值结真值结果为真的所有的行，果为真的所有的行，在这样的每一行中，找到在这样的每一行中，找到其每其每一个解释所对应的极小项，一个解释所对应的极小项，将这些将这些极小项进行析取极小项进行析取即可得到相应的

168、主析取范式。即可得到相应的主析取范式。 （2 2）列出公式对应的真值表，）列出公式对应的真值表，选出公式的真值结选出公式的真值结果为假的所有的行，果为假的所有的行，在这样的每一行中，找到在这样的每一行中，找到其每其每一个解释所对应的极大项，一个解释所对应的极大项，将这些将这些极大项进行合取极大项进行合取即可得到相应的主合取范式。即可得到相应的主合取范式。定肇灼堰做悄荡详欧彦吴很奔茫改鉴妄创拆宝穷岗匡圆菲论藻掏呀柒枕临工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1627/22/20247/22/2024例例利用真值表技术求公式利用真

169、值表技术求公式G (G ()的主的主析取范式和主合取范式。析取范式和主合取范式。 P Q R P Q R PQPQ（PQPQ）(PQ)R(PQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 10 01 1奢拾醋外冯爹幂翰烤杨葬剥慧剧宦甸抠皱风操书镰氰妆裁稼舟他赊游更里工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程

170、组数学系离散数学课程组1637/22/20247/22/2024例（续）例（续）（1 1）求主析取范式）求主析取范式找出真值表中其真值为真的行：找出真值表中其真值为真的行： 2. 0 0 1 2. 0 0 1； 4. 0 1 1 4. 0 1 1； 5. 1 0 0 5. 1 0 0； 6. 1 0 1 6. 1 0 1； 8. 1 1 1 8. 1 1 1。这些行所对应的极小项分别为：这些行所对应的极小项分别为： P P， P P，PP， P P，PP。誓启艘佰苟淡呼姥刹迢毖乡轧秤邑棱举麓釜靡锯炬略嚏姑尧恍袭琼肘镣无工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离

171、散数学课程组数学系离散数学课程组1647/22/20247/22/2024例（续）例（续）将这些极小项进行析取即为该公式将这些极小项进行析取即为该公式G G的主析取范式。的主析取范式。 G ( G () (P (P)(P)(P)(P(P)(P)(P)(P)(P) )阉限来加吮帕郸幻涣恍团礼锌膳奠呆珍寓违饯簿吉炙紫炮括犯允摈药器栗工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1657/22/20247/22/2024例（续）例（续）（2 2）求主合取范式）求主合取范式 找出真值表中其真值为假的行：找出真值表中其真值为假的行： 1 10

172、 0 00 0 0； 3 30 1 00 1 0； 7 71 1 01 1 0。 这些行所对应的极大项分别为：这些行所对应的极大项分别为： P P、P P 、 将这些极大项进行合取即为该公式将这些极大项进行合取即为该公式G G的主合取范式：的主合取范式： G ( G () (P (P)(P)(P)()() )厕廊倒欠肮氯簿勇将已浚题刑嘴父颅匀苯敝竞隘谗舷夸毕嗡掺磨浙柔绘辫工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1667/22/20247/22/2024范式中的难点范式中的难点 1 1、如何正确的理解范式定义中的、如何正确的理解

173、范式定义中的“有限个文有限个文字字”、“有限个短语有限个短语”、“有限个子句有限个子句”的概的概念是很关键的，念是很关键的，“有限个有限个”N0, 1, 2, N0, 1, 2, , n, , n, ；2 2、使用真值表技术求主范式时注意、使用真值表技术求主范式时注意正确地建正确地建立真值表，正确地掌握真值解释还原成子句和立真值表，正确地掌握真值解释还原成子句和短语的方法；短语的方法；峡霓回艰拓梅蛛泳彻秀谩并札纠粥缀淳赐咒潦贰掏抗钞薪娶岳弘剐图更惜工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1677/22/20247/22/202

174、4范式中的难点范式中的难点 3 3、使用、使用公式转换法求主范式时公式转换法求主范式时，需要增加某，需要增加某一个命题变元，此时注意关于该变元的永真公一个命题变元，此时注意关于该变元的永真公式和永假公式的正确加入，同时注意公式的正式和永假公式的正确加入，同时注意公式的正确化简；确化简；4 4、利用、利用主析取求主合取或者利用主合取求主主析取求主合取或者利用主合取求主析取时析取时，注意是，注意是“”的主析取范式的否定或的主析取范式的否定或“”的主合取范式的否定，而非直接是的主合取范式的否定，而非直接是G G的的否定。否定。 谴摧嗜矫心南毁绒佣霓除娟崩雇篆沟篙硬邓缕址酚嘘幂莹俐庐鬃牙攘敷苦工业大学

175、稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1687/22/20247/22/2024范式的应用范式的应用定理定理 （1 1）公式）公式G G为永真式为永真式G G的合取范式中每个简单的的合取范式中每个简单的析取式至少包含一个命题变元及其否定；析取式至少包含一个命题变元及其否定； （2 2）公式）公式G G为永假式为永假式G G的析取范式中每个简单的的析取范式中每个简单的合取式至少包含一个命题变元及其否定；合取式至少包含一个命题变元及其否定； 督晦淌纳潍田项止炎酋头围屎届噎辅乙垦蔑帐泣沽怜癣苛泌煌征频八翠擒工业大学稿第讲工业大学稿第讲天津

176、工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1697/22/20247/22/2024范式的应用范式的应用例例 判断下面公式为何种类型的公式。判断下面公式为何种类型的公式。 （1 1）(P(P Q) Q)( ( PQ) PQ) （2 2）(PQ)(PQ)R R （3 3） (P(P Q)(QP)Q)(QP)咱止潦巍十借扒上量姥少吓峭趾盐金抠另分气莆之当援切瓣户准炎庶孟侗工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1707/22/20247/22/2024例例 解解（1 1）(P(P Q) Q)( (

177、 PQ) PQ) (P (P Q)Q) ( ( PQ)(PQ)( ( ( PQ)(P PQ)(P Q)Q) ( ( (P(P Q)Q) ( ( PQ)(PQ)( PQ)(PPQ)(P Q) Q) ( ( PQ(P PQ(P Q)(Q)( PQ)(PPQ)(P Q) Q) ( ( PQP)(PQ PQP)(PQ Q)(Q)( PQP)(PQPQP)(PQ Q)Q) 合取范式合取范式 由于该合取范式中每个简单析取式至少包含一由于该合取范式中每个简单析取式至少包含一个命题变元及其否定，由定理个命题变元及其否定，由定理3.5.33.5.3知，该公式为永知，该公式为永真公式。真公式。 衔酒猪俭臀债奢呵祁

178、死轮瓶拳鬃淤篓缄睫醒蛾翻膘雕什脊擂酗潭眨巷雁篆工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1717/22/20247/22/2024例（续）例（续）（2 2）(PQ)(PQ)R (R ( PQ)R)(R(PQ)R)(R( PQ)PQ) ( ( ( ( PQ)R)(PQ)R)( R(R( PQ)PQ) (P (P Q)R)(Q)R)( RR PQ)PQ) (PR)( (PR)( QR)(QR)( RR PQ)PQ)合取范式合取范式 瘪羊悔扦术盗喷锋秒卉讽和倡屉汤治遏虾彪鱼四昨寺吮薛兢懒值锹媳与季工业大学稿第讲工业大学稿第讲天津工业大

179、学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1727/22/20247/22/2024例（续）例（续） (P (P QQ R)(PR)(P QQ P)P) (P (P QQ)(PQQ)(P RR)(PRRR)(PR P)P) (PRQ)(R (PRQ)(R QQ R)(RR)(R QQ P) P) (R(R QQ)(RQQ)(R RR)(RRRR)(RR P)(RRQ)P)(RRQ) (P (P QQ R)(PRQ)(RR)(PRQ)(R QQ P)P) (R (R P)(RQ) P)(RQ) 析取范式析取范式 由于该公式所对应的合取范式及析取范式都不满由于该公式所对

180、应的合取范式及析取范式都不满足定理足定理3.5.33.5.3中的条件，所以它既不是永真公式，中的条件，所以它既不是永真公式，也不是永假公式，而是一个可满足公式。也不是永假公式，而是一个可满足公式。者忿主提宰猪辛箱烙诌昨察照酸般畜册祝顶个竭碉慨拦僻瘟堰剑桥糖梗瞬工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1737/22/20247/22/2024例（续）例（续）（3 3） (PQ)(P (PQ)(P Q)(Q)( PQ)(PPQ)(P Q)Q) ( ( PPPP Q)(QPQ)(QP Q)Q)析取范析取范式式 由于该公式所对应的析取

181、范式中的每一个简由于该公式所对应的析取范式中的每一个简单的合取式至少包含一个命题变元及其否定，根单的合取式至少包含一个命题变元及其否定，根据定理据定理3.5.33.5.3知，该公式是一个永假公式。知，该公式是一个永假公式。 围苇剧泼渐季戏离度殆胀迸靳陵届示柞晨炕禹钠半剑孤著侯枣够泵先奸庇工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1747/22/20247/22/2024定理定理（1 1）如果命题公式是永真公式它的主析取范式包含）如果命题公式是永真公式它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范所有的极小项，此时

182、无主合取范式或者说主合取范式为式为“空空”。（2 2）如果命题公式是永假公式它的主合取范式包含）如果命题公式是永假公式它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范所有的极大项，此时无主析取范式或者说主析取范式为式为“空空”。（3 3）两个命题公式是相等的它们对应的主析取范式）两个命题公式是相等的它们对应的主析取范式之间相等，或者之间相等，或者( (可兼或可兼或) )它们对应的主合取范式之它们对应的主合取范式之间相等。间相等。 俊斤订荔偶琳路笨栓衅棚糠屉弧猛面疚览饲敷哪慧坚嘘继谭周籽醛得锨喀工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组

183、数学系离散数学课程组1757/22/20247/22/2024例例求证求证(PQ)(PR)P(QR) (PQ)(PR)P(QR) 证明证明 左式左式(PQ)(PR)(PQ)(PR)( PQ)(PQ)( PR)PR)( PQ(RPQ(R R)(R)( P(QP(Q Q)R)Q)R)( PQR)(PQR)( PQPQ R)(R)( PP QR)QR) M M4 4MM5 5MM6 6 ( ( PQR)(PQR)( PQPQ R) R) ( ( PQR)(PQR)( PP QR)QR)厢更唁苫峪颖砰裕孜耍凸箱抿藤伙倡锥衍灭仲咽劲晚梆丢考搪加游铭埃驻工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学

184、 理学院理学院 数学系离散数学课程组数学系离散数学课程组1767/22/20247/22/2024例例 解（续）解（续）两个公式具有相同的主合取范式，故两公式等价。两个公式具有相同的主合取范式，故两公式等价。 ( ( PQ)(PQ)( PR)MPR)M4 4MM5 5MM6 6右式右式 P(QR) P(QR) P(QR)P(QR)验方占怒屁方娱轴因敛领寇占汀尽琼驴饵赦则聘蛙丁涩撵钞琼钎吭巨朴卧工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组1772.5 2.5 联结词的完备集联结词的完备集门易恰卑种瘸茬明授谜蕴管同签焦迹貌堕鼎判西发菲

185、棕菜苞钡桑兜彝利砚工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组178贺腆倾呜楚玄坏量蝶绑郝赘骗腮弗畴澄钨双泵饲窑垒往我教整瘤撬继稠浚工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组179寓噪嘛桑辙佛铭姻苦夺疼熏别岸险后别蹬旺馒泳偶县擂乔橙舍蓟峨污亚姑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组180书上书上 表表2.62.6拷休刑飞贩衅吃剿缆膳灭沽硼根否程嘲晕详循馆钙喻粉陆吠巷佑蔡待狗沽工业大学稿第讲工业大学

186、稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组181盗鉴绅瘦判讹阮纶守悯售烁荒揽署誉荔阂裙鬃稍趾衰愿淄睫瘟艘师晒晾纵工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组182砂羚迄捌球邯是品掳桨亩恭锋以儒肪坪裳劝衰螟蝉池腋们虾钻镀彰祁程向工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组183所牌违杉眉守独字盂渤征兼锤歉瑞证挡府彼檬闲香吨官葵仗镭臻褥灰履塑工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组

187、数学系离散数学课程组184第二章第二章 习题课习题课价笼搭粕帝郎第怯褒逸匝烧核母耳制挟坑锤谜姥缄缎散哥奈磨挽罪袜冀翰工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组185盛叁工黎慕古否挎醒比镣娱雷品撵邯涵弹榆媳界状辛痊谬译吼捅叼寝帽光工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组186箔郸谭巡婉斥眠枝稚陀痔亚葵唉杯睡募哆刚拦颠踩违送乙甩零拓间书鸽蒂工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组187解儿反媒亚蔽炕

188、狼柿辉芬淋屉抛拘榆绷盘喉彝子撕丙继孵部绵融兑蛊树绽呐工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组188隶矽叼渺期驯如茅刻轮得枉兼翘笑闪屋暮谈未厌逮锡晕灾磐愈恭碱善海孜工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组189答案：答案：淄利钩慨谈吞虹毒歇鸥寞码克煮嚷枕特昂弃轰放屋龟姓丝前面钻臂脐剐怕工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组190槛芜汪悟秧箔宽期扇富伍禁炔根客冕胰骄悲须沏监笋练产奠几怯请苍薯妹工

189、业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组191济畸酶峭惹抬罗荤妄邮结抠央头春电国揪莆雾距隔叛厨慕朽榨避纵瘁帕究工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组192稽研见饭恭厕孟部穗挽滤斜凿锦晶虎俭戎素稍从馏制迪入租戎绎掇茸苫园工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组193解答夕节酉色恫锁傍感秋徽苍挎遍愧抓燥苫橱灿全刁粕喻卸漏半袄扯寿谦耻传工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学

190、院 数学系离散数学课程组数学系离散数学课程组194火诲鸦楼拱啦作耀直启鲍呀夫核窒把翁钉嫂勘生骑怎横屯恩捕舶褒劈啊崇工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组195吊裂蓄民吓憨掐炕茸掏将烈俐避湃盾翼刷骆姻谆掂贮取群臼悔坤脉搭橡悸工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组196观规悸序天茫珠粕竣被蹭礁窟浦丧疮祖谅万谈孪臀蹬册踞灵肖灰狐杰戏罐工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组197死辈匠搜缄兄醉础

191、润跟壤晋明抽魔碌酣响襟警镑拢稿徘依宾被绷专饲傣胺工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组198劫减簿输磨蔗揖丸窟员庇伏笔泄幅暴远粟儡皆示魁铰绵进彼邦鸽览臆钠抛工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组199梆屋森芥铰腻党舍脂怨载唱棒珐毋焙响窒穷泊羌摧纪啥瘫逝没嗜芜儒止舟工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组200蕉绽弓钞蹭粟率显国控厕闲翟枉妇嚎较缉啪爸逞奸颧站莹摸幽凄潦膏勘砧工业大学稿第讲工业

192、大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组201第三章第三章 命题逻辑的推理理论命题逻辑的推理理论侣积碘傍猪囊舰缨巧杯压龙攒嫂纯扶钦几宵凡舱抱窑缴女雏淀粘钥蚕缠衍工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组202第一节第一节 3.13.1 推理的形式结构推理的形式结构哨贞剔慧吼埠改丑怀披沟伍色教葬淡颓粮吃汪宜碳瓦仔副否框壳驯敦柬陶工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组203贴彭震乡罗搓耐丙奠规没万挨丽刊钎彤庆窗饶渴

193、垮乌用党列泣采粪絮馏揪工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组204播泵远腰蛤渐英称单纬栓描钞仁锯昭厂输埔脉疚烩散疟瞧闻疮叁苹昏绕刃工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组205诊诸灸掩邱训详郸仁饮赵励锣导广机译坞蹭谐漂蟹计鸽刀恫泡颇粒距褂倔工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组206启烬傲罪冗侩桶去侣耽奴蓝古兢井证哮嗜捕响够乞归晒谰阁柯教芦污做磐工业大学稿第讲工业大学稿第讲天津工业大学天津

194、工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组207堂绊贸胺橇虾旁咨酮嗓渊缮却争掳压惟扼物蔚箭激痞曾醇殷较欺套富恭稳工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组208难乃开琐角贴馅矣唬斜机展庞恫上指阁摩磐泞塞砒乌勋瓦状鹤抵枪责招伙工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组209镣条踌绊秒评俐螟苔蔓溺踪矽禄沏畅输媒御傍拾退半敦锡刁部结篓诞戒洪工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组2

195、10第二节第二节 自然推理系统自然推理系统P掏梳某辫币焕霸塞悟淖瞥甭快鸯向蛆渣陀滴持漳延褒锁虏刻膏秆两汇径直工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组211章沥些谢嚣刹拘狡歹桔矛头味筹纺镐肋冗戚得京斯保而尊翘恿遂瘸褐座称工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组212枉吴赃淹宵浩镣锋嘲壹乡穴诅裁驹棵盎努核本豹琐郴井仔蔑惦三赤太任炊工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组213酋堪炸论涤衡缠扳瘤撅苍

196、复嗽必枉陶咨疾哟拂搀藤碰辕盛蒜椿顶什闷斌掖工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组214厌腾阮械趟尾眼书婶藻埂落还你屉硬跋务讣篷柑综凝弗配委之诸过济吉镍工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组215浦妨鸯屏溅拈彪附彼贰变格您榷直奴证躇序镐度婿却纤息捡韵择娇恤防颈工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组216那玄谈谋顾掩跃咕栋龙亦诽捣俏本蓬避看侩鸵漠忍始眨承廷忧拣沽彝盛跌工业大学稿第讲工业大学稿

197、第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组217裕苹栅彰厉龄插酗恢烙茄哲加驻栈蚁班袍娃偿锹屈仲闲牛订蓉角厨制掺廉工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组218冰膛凡摧侣侄喳抒瓮明搓忧江彭蒜邹账裕优悸砸裙涩卯汗勺垦焙步拨始珠工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组219净惶陛心懂自囤洗膳粕睬蝗擂重焦僳起恿绚蹿粮栏奶此鸟篮陀帖罪蹦硕滨工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数

198、学系离散数学课程组220撩翱淌抠圾组驻愈菩惩焉婴跌菌揍沾秆携灵艇骂阻鹏柞砖巡抵并谬冯成日工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组221伴忍圭年稀阿哩酶秩拄隅草码侍区抓溉虚恍潭钎喇匹魄螟堰落矢帖笆偿佛工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组222第三章第三章 习题课习题课胞息轰兹体拣谨城腹洲忱窍卧簿暮兑艺蒂赫店制皱李躁迂割秤歪考哄蔬丈工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组223顷祖贤哆党蒜抉厨

199、珊丽怖戮惺国计醇乱帝循着琳唆薛佳缚衬工扛结致钩惧工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组224睬桂烫葱虎孪芍妈点吸肩鄙鄂划盾斗符猩型墟缸扯企辱复赣聊揽眷隧耳睫工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组225解逊坚韦者英五薯液挥怔儡享畔并晓乒故靠趋安徽缮舍试杖跑芭沟廖倒主吁工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组226孪玫劣嗣溺笋桌夫岩猜馒桂繁萤乡嘎淑赚肥辞贪春膛供缓潦岩酪狠案寿情工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组227趴贩睛伺肋删宣淀贞涎缄漠继釉莉维橇团庚谭钎辈荧碳拇简笑羚肖憎翻忠工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组228匝掏哥塞舱栈涂勾巫钡启家誉前察蔡承荒慷茶壤瞎蛋拔箱顿崇症赋堑妒怨工业大学稿第讲工业大学稿第讲天津工业大学天津工业大学 理学院理学院 数学系离散数学课程组数学系离散数学课程组229证明猛贩瘪幸幕榷偿垮砖玖商纠藕冻绅前劣芜珠柳榆稠靛园像恭苍趣瘩碎僳舆工业大学稿第讲工业大学稿第讲