华工离散数学命题逻辑课件.ppt

离散数学及其应用,华南理工大学计算机科学与工程学院,1,离散数学,研究离散对象及其相互间关系的一门数学学科。它是以研究离散量的结构和相互间的关系为主要目标，描述了计算机科学离散性的特点.从数学的角度出发：连续数学和离散数学，都是刻画和分析现实世界的重要工具。基础数学的延伸算法与数据结构的理论基础概率统计、算法设计与分析的理论基础其他专业课程的描述和建模工具,2,为什么要学习离散数学？,离散数学是现代数学的一个重要分支，是计算机专业的一门重要的专业基础课程。是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是遗传算法、数据挖掘、模式识别、密码学、网络通信理论等课程的重要基础。该课程所提供的训练十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于严谨、完整、规范的科学态度的培养。,3,2020年6月1日9时53分,ChenQiong,SouthChinaUniv.ofTech.,3,计算机科学与离散数学的关系,计算机科学的任务是用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。离散数学就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言和逻辑语言等）从最简单的对象（集合）出发表示通用模型。,4,计算机科学与离散数学的关系,离散数学的思维方法能够为计算机科学所用计算机科学知识的掌握需要三方面的能力-构造模型、算法设计、程序设计的能力思维训练：构造性思维,5,离散数学课程教学目标,知识获取能力：建立良好的知识结构，为学习其他课程打下基础基本应用能力：掌握离散数学的语言，能对实际问题给出清晰的描述（建模）工程实践能力：掌握离散数学的分析方法，针对实际问题设计解决方案并加以实施研究能力：培养思维严谨性，提升抽象思考和严格推理能力培养创新意识：了解现代数学思想和学科进展，,6,2020年6月1日9时53分,ChenQiong,SouthChinaUniv.ofTech.,6,6,离散数学的应用,在计算机科学方面的应用是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是遗传算法、数据挖掘、模式识别、密码学、网络通信理论、等课程的重要基础。在通信方面的应用代数系统在开关线路的计数，数字通信的纠错码方面的应用在现实生活中的应用TSP在企业管理、交通规划、战争指挥、金融分析，生物、医药等领域都有重要的应用。,7,2020年6月1日9时53分,ChenQiong,SouthChinaUniv.ofTech.,7,7,离散数学的一些应用,关系数据库四色定理网络规划信息安全计算复杂性问题：该问题可计算吗？该问题能/不能计算？计算机复杂性如何？操作系统中，如何调度进程使得系统效率最优？程序结构度量：判断程序结构是否相似提高信息传输效率的通信编码的设计通信网络频率分配设计集成电路线路的布局，达到最优效率数字通信的可靠性：如何设计高效的检错码和纠错码？,8,离散数学的一些应用,中国邮递员问题学生考试日程表的安排人携带狼、羊和草渡河的问题物流运输的最优路径的计算达到最高效率的工作流程的安排生产调度和人员安排酒店的清洁工的工序安排库房和运输管理航班调度，交通规划考生录取,9,学习内容,数理逻辑集合，函数和关系图论数理逻辑是研究推理的学科，在人工智能、程序理论和数据库理论等的研究中有重要的应用。集合论和图论为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进行抽象描述的一些重要方法。,10,结束,下一页,关于课程学习,课程特点知识点集中、概念定理多方法性强-阅读、思考、练习、阅读、总结.课程考核过程考核、在线测试、期末考试,11,参考资料,教材：陈琼等编著：离散数学及其应用，机械工业出版社KennethH.Rosen,DiscreteMathematicsandApplications,机械工业出版社耿素云、屈婉玲著：离散数学，高教出版社傅彦、顾小丰著：离散数学及其应用，电子工业出版社BKolman,RobertC.Busby,SharonRoss,DiscreteMathematicsStructures,高等教育出版社,12,第一部分数理逻辑,数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性等。数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算、集合论、模型论、递归论和证明论。数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。,13,第1章命题逻辑,1.1命题与联结词1.2命题公式及其分类1.3命题演算的关系式1.4范式1.5命题演算的推理,14,1.1命题与联接词,1.1.1命题的概念定义命题的真值联结词,15,命题及其真值,命题:是用陈述句表示的一个或者为真或者为假，但不能同时既为真又为假的判断语句。命题的真值:判断的结果,真（T或1）或假（F或0)真命题:真值为真的命题假命题:真值为假的命题,16,例题,判断下列句子中那些是命题？若是命题的，判断其真值。北京是中国的首都。2+3=6。3-x=5。请关上门。几点了？除地球外的星球有生物。多漂亮的花啊！我只给所有不给自己理发的人理发。,17,Y真,Y假,N真值不确定,N疑问句,N感叹句,N祈使句,N悖论,Y真值确定,但未知,命题的表示,引入英文字母表示任意的命题表示命题的符号称为命题变量，通常用p、q、r.、P、Q、R.表示命题变量。命题变量没有真值，只有表示一个确定的命题后，才有真值。如用p表示命题：“2+3=6”，这时p的真值为假（F），也可以用p表示命题：“2+3=5”,这时p的真值为真（T）。,18,简单命题与复合命题,简单命题(原子命题):不能分解为更简单的陈述语句的命题简单命题：“北京是中国的首都”。复合命题:由两个或几个简单句和连词组合而成的命题复合命题：“如果明天天气好,我们就去爬山。”命题的符号化：用英文字母或英文字母和联结词的组合表示命题，称为命题的符号化。联结词-连词,19,联结词,（一）否定定义1.1.4设p是一个命题，p表示一个新命题“非p”。命题p称为p的否定。当且仅当p的真值为假时，p的真值为真。p的真值表：例如：p：今天是晴天。则p：今天不是晴天。“非”，“不”，“没有”，“无”，“并非”等都可用来表示。,20,联结词,（二）合取定义1.1.5设p、q表示任意两个命题,pq可表示复合命题“p并且q”。当且仅当p和q的真值同时为真时，pq的真值为真。pq的真值表：例如：p:今天是晴天；q:今天去公园。pq:今天是晴天并且今天去公园。“和”，“与”，“也”，“并且”，“既.又.”，“不仅.而且.”，“虽然.但是.”等都可用来表示。,21,联结词,（三）析取定义1.1.6设p、q表示任意两个命题,pq可表示复合命题“p或q”。当且仅当p和q的真值同时为假时，pq的真值为假。pq的真值表：例如：p:今天去看电影；q:今天去公园。pq:今天去看电影或今天去公园。“或”，“可能.可能.”，“或者.或者.”等可用表示。,22,联结词,自然语言中的“或”具有二义性：兼容性或和不兼容性或。兼容性或电灯不亮是灯泡或线路有问题所致.不兼容性或（排斥或）派小王或小李中的一人去开会表示兼容性或例如：p:电灯不亮是灯泡有问题所致；q:电灯不亮是线路有问题所致。pq:电灯不亮是灯泡或线路有问题所致。p：派小王去开会，q：派小李去开会，(pq)(pq):派小王或小李中的一人去开会,23,联结词,（四）蕴涵定义1.1.7设p、q表示任意两个命题,pq可表示复合命题“如果p，则q”。当且仅当p的真值为真，q的真值为假时，pq的真值为假。pq的真值表：例如：p:今天天气晴朗；q:我们去海滩。pq:如果今天天气晴朗，我们就去海滩。,24,联结词,蕴涵式：pqp为蕴涵前件，q为蕴涵后件p是q的充分条件，q是p的必要条件表示：“如果p，则q”，“如果p，那么q”，“当p则q”，“p仅当q”等。假设：p：天气晴朗；q：我们去海滩。如果天气晴朗，我们去海滩。pq仅当天气晴朗，我们去海滩。qp,25,联结词,（五）等价定义1.1.8设p、q表示任意两个命题,pq可表示复合命题“p当且仅当q”。当且仅当p和q的真值同时为真或同时为假时，pq的真值为真。pq的真值表：例如：p:两个三角形是全等的。q：两个三角形的三条对应边相等。pq表示“两个三角形是全等的当且仅当它们的三条对应边相等”。,26,联结词,等值式pq表示p与q互为充分必要条件的逻辑关系表示形如“p当且仅当q”，“如果p，那么q，反之亦然”等的命题。,27,例题,将下列命题符号化：虽然天气很冷，老王还是来了。小王和小李是好朋友。小王和小李是好学生。小王或小李中的一人是游泳冠军。只有你学过微积分或是数学系的学生，才可以选修这门课。如果明天早晨6点不下雨，我就去跑步。今天下雨与3+3=6。登陆服务器必须输入一个有效的口令。2+3=5的充要条件是加拿大位于亚洲。,28,解：虽然天气很冷，老王还是来了。设p：天气很冷。q：老王来了。则符号化为：pq。小王和小李是好朋友。这句虽然有连词“和”，但是个简单句，可用p表示：小王和小李是好朋友。小王和小李是好学生。设p：“小王是好学生”q：“小李是好学生”，则符号化为：pq。,29,解：小王或小李中的一人是游泳冠军。设p：“小王是游泳冠军”，q：“小李是游泳冠军”(pq)(pq)只有你学过微积分或是数学系的学生，才可以选修这门课。设p：你学过微积分；q：你是数学系的学生；r：你可以选修这门课。r(pq)如果明天早晨6点不下雨，我就去跑步。设p：明天早晨6点下雨。q：我去跑步符号化为：pq,或者：qp。,30,解：今天下雨与3+3=6。设p：今天下雨。q：3+3=6。符号化为：pq。登陆服务器必须输入一个有效的口令。设p：登陆服务器,q:输入一个有效的口令,符号化为：pq。2+3=5的充要条件是加拿大位于亚洲。设p：2+3=5,q:加拿大位于亚洲,符号化为pq。,31,联结词,（），优先级高低,32,括号有时被省略，如pq是p和q的合取，这里是省略了p的括号，即(p)q,例题,将下列命题符号化，并指出它们的真值：1+1=2和2+3=61+1=2或猴子是飞禽若2+3=6，则猴子是飞禽。若猴子不是飞禽，则1+1=2和2+3=6。若2+3=6或猴子是飞禽，则1+1=2。2+3=6当且仅当猴子不是飞禽。,33,解设p：1+1=2，q：2+3=6，r:猴子是飞禽1+1=2和2+3=6,pq，真值为0，1+1=2或猴子是飞禽,pq，真值为1，若2+3=6，则猴子是飞禽,qr，真值为1若猴子不是飞禽，则1+1=2和2+3=6。rpq，真值为0，,34,例题(续）,例题（续）,若2+3=6或猴子是飞禽，则1+1=2qrp，真值为1，2+3=6当且仅当猴子不是飞禽。qr，真值为0,35,其它联结词,定义1.1.9设p和q是任意两个命题,pq可表示复合命题“p和q的与非”,称为与非联结词。命题pq称为p和q的与非式。当且仅当p和q的真值同时为真时，pq的真值为假.pq的真值表,36,其它联结词,定义1.1.10设p、q是任意两个命题,pq可表示复合命题“p和q的或非”,称为或非联结词。命题pq称为p和q的或非式。当且仅当p和q的真值同时为假时，pq的真值为真.pq的真值表,37,其它联结词,定义1.1.11设p和q是任意两个命题,pq可表示复合命题“p、q之中恰有一个成立”,称为异或（不兼容性或）联结词。命题pq称为p和q的异或式。当且仅当p和q的真值恰有一个为真时，pq的真值为真。pq的真值表,38,联结词的真值,39,逻辑关系的数字门电路实现,用数字电路中的“非门”实现，联结词用“与门”实现，联结词用“或门”实现,40,非门与门或门逻辑门电路符号,命题公式的门电路实现,命题公式G(pq)p,41,逻辑电路,联结词的应用,布尔检索中，联结词AND用于匹配同时包含两个检索项的记录，联结词OR用于匹配至少包含一个检索项的记录，而联结词NOT用于排除某个特定的检索项。如：把自然语言表示的命题翻译成由命题变量和逻辑联结词组成的表达式，进行判断和推理,42,例题,三个客人坐在餐馆，服务生问：“每个人都要咖啡吗？”，第一位客人回答：“我不知道。”接着第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每个人都要咖啡。”一会儿，服务生回来，将咖啡递给需要的客人。请问服务生是如何判断哪位客人需要咖啡的？解：根据三位客人的回答，服务生给第一位客人和第二为客人送来咖啡。,43,例题,设p、q、r分别表示第一、二、三位客人要咖啡如果每个人都要咖啡，则pqr为真。如果第一位客人不要咖啡，则p为假，根据第一个客人的回答“我不知道。”，服务生可以判断p为真；根据第二个人的回答“我不知道。”可以判断q为真；第三位客人的回答：“不是每个人都要咖啡。”说明r为假因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。,44,1.2命题公式及其分类,命题常元:代表特定简单命题命题变元:代表任意命题，取值1(真)或0(假)的变量定义1.2.1命题公式（公式）的定义如下：每一个命题常元或命题变元都是命题公式。如果A是命题公式，则(A)是命题公式。如果A和B都是命题公式，则(AB)，(AB)，(AB)，(AB)都是命题公式。一个由命题常元或命题变元、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。,45,命题公式,一个含有命题变元的命题公式的真值是不确定的.只有当公式中的所有命题变元被指定代表特定的命题时，命题公式才成为命题，其真值才唯一确定。例如，命题公式pq若指定p为“2是素数”，q为“3是奇数”则pq为真命题若指定p为“2是素数”，q为“3是偶数”则pq为假命题,46,公式的赋值,定义1.2.2若命题公式A含有的全部命题变元为p1,p2,pn，给p1,p2,pn指定一组真值，称为对A的一个解释或赋值。使A的真值为真的赋值称为成真赋值，使A的真值为假的赋值称为成假赋值。说明通常赋值与命题变元之间按下标或字母顺序对应,即当A的全部命题变元为p1,p2,pn时,给A赋值12n，是指p1=1,p2=2,pn=n;当A的全部命题变元为p,q,r,时,给A赋值123是指p=1,q=2,r=3,。,47,命题公式的真值表,例给出公式的真值表p(qr)(pq)(pq)(pq)q,48,真值表:命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2n个赋值,例题(续),(1)p(qr),49,例题(续),（2）(pq)(pq),50,例题(续),(3)(pq)q,51,N个命题变元的不同的真值表有,命题公式的分类,定义1.2.3设A为一个命题公式(1)若A在它的各种赋值下取值均为真，则称A为重言式或永真式。(2)若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式。(3)若至少存在一种赋值使A的真值为真，则称A为可满足式。例如(1)p(qr)为非重言式的可满足式（2）(pq)(pq)为重言式(3)(pq)q为矛盾式,52,命题公式的分类,这三类公式之间有下面的关系：公式A永真，则A永假，反之亦然。公式A是可满足的，当且仅当A不是永真式。公式A不是可满足的，则一定是永假式。公式A不是永假式，则一定是可满足的。判断命题公式类型的方法：构造真值表,53,1.3命题演算的关系式,等价关系式定义1.3.1设A和B是两个命题(或命题公式)，若AB是永真式，命题A和B称为逻辑等价的，可记为AB。说明：AB是永真式，表示命题公式A和B在所有的赋值下都有相同的真值，也就是说命题公式A和B有相同的真值表。可以用真值表判定两个命题是否等价。,54,例题,证明：pq和pq等价。证列出真值表,55,所以有:pqpq,例题,证明p(qr)和(pq)(pr)逻辑等价证列出真值表,56,所以有：p(qr)和(pq)(pr)等价,等价关系式,双重否定律pp同一律p0p,p1p零元律p11,p00等幂律ppp,ppp交换律pqqp,pqqp结合律(pq)rp(qr)(pq)rp(qr)德摩根律(pq)pq(pq)pq吸收律p(pq)p,p(pq)p,57,基本等值式(续),分配律p(qr)(pq)(pr)p(qr)(pq)(pr)排中律pp1矛盾律pp0蕴涵等值式pqpq等价等值式pq(pq)(qp)假言易位pqqp等价否定等值式pqpq归谬论(pq)(pq)p,58,等价运算,置换规则若公式G中的一部分A(包含G中几个连续的符号)是公式，称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其它一些等价关系式，这一过程称为命题的等价运算。利用命题的等价运算，可以判断两个命题是否等价判断命题公式的类型命题公式的化简等。,59,例题,例1.3.3证明pqqp解pqpq蕴涵等价式(q)p交换律和双重否定式qp蕴涵等价式条件命题：pq否命题：pq逆命题：qp逆否命题：qp条件命题和它的逆否命题等价,60,例题,例1.3.4利用命题的等价运算判断下列公式的类型。（1）p(pq)解p(pq)p(pq)蕴涵等价式p(pq)摩根律(pp)q结合律Fq矛盾式F零元律该式是永假式,61,例题,（2）p(pq)解p(pq)p(pq)蕴涵等价式(pp)(pq)分配律F(pq)零元律pq同一律该式是可满足式,62,例题,(3)(pq)(qp)解(pq)(qp)(pq)(qp)摩根律(pq)(pq)交换律T排中律该式是永真式,63,例题,化简公式(pq)(pq)解(pq)(pq)p(qq)分配律pT排中律p同一律,64,例题,对于图1.3.1所示的逻辑电路，可否用更简单的电路实现该逻辑关系？,65,解：F(pq)(pq)(pq)(pq)qpq,全功能联结词集,定义1.3.2设G是一个联结词的集合，若任意一个命题公式都可用G中的联结词构成的公式来表示，则称G为全功能联结词集。如在G中去掉任何一个联结词，就不再具有这种特性，就称其为最小全功能联结词集。、，、，、，、，和都是全功能联结词集，而、，、，、，和都是最小全功能联结词集。,66,AB(AB)(BA),ABAB,AB(AB)(AB),AB(AB),AB(A)BAB,例题,证明：,是最小全功能联结词集证：p(pp)pppq(pq)(pq)(pq)(pq)得证是联结词完备集.对于可类似证明.只用一个或就可以实现联结词，、表示的逻辑关系。在数字电子技术中，只用与非门或者或非门组成的电路就可以实现任何逻辑运算。,67,与非门或非门,例题,用只有一种与非门的逻辑电路实现F(pq)(pq)(pq)。解：F(pq)(pq)(pq)pq(pq)(pp)q,68,对偶式,定义1.3.3在仅含有联结词，的公式A中，将其中的换成，换成，T(或1)换成F(或0)，F(或0)换成T(或1)，其它符号不变得到的公式称为A的对偶式，记为A*。pq和pq，pq和pq，p(qr)和p(qr)，pq和pq都互为对偶式,69,对偶式,设A(p1，p2，pn)和A*(p1，p2，pn)互为对偶式，其中p1，p2，pn是出现在A和A*中的全部的命题变元，则A(p1，p2，pn)A*(p1，p2，pn)A(p1，p2，pn)A*(p1，p2，pn)定理1.3.1设A和B为两个命题公式，A和A*，B和B*互为对偶式，若AB，则A*B*。证明因为A(p1，p2，pn)A*(p1，p2，pn)，B(p1，p2，pn)B*(p1，p2，pn)，若A(p1，p2，pn)B(p1，p2，pn)，则A*(p1，p2，pn)B*(p1，p2，pn)，即A*(p1，p2，pn)B*(p1，p2，pn)，则A*(p1，p2，pn)B*(p1，p2，pn)。,70,例题,求公式Ap(p(qq)的对偶式。解公式A的对偶式A*为：A*p(p(qq)重言式A的对偶式A*是矛盾式,71,1.4范式,1.4.1析取范式与合取范式1.4.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途,72,析取范式与合取范式,定义1.4.1一个命题公式具有形式A1A2.An(n1)，其中A1，A2，.，An都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。如：p(pqr)(pq)q是析取范式。定义1.4.2一个命题公式具有A1A2.An(n1)，其中A1，A2，.，An都是由命题变元或其否定所组成的析取式，则称该命题公式为合取范式。如：(pqr)(pq)q是合取范式。,73,范式存在定理,定理1.4.1任何一个命题公式都存在着与之等值的析取范式与合取范式.证设G为任意一个公式，将公式化成只含、3个联结词的形式。将否定联结词内移或消去。利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。通过上面3个步骤可以求出与G等价的析取范式和合取范式，任意一个命题公式都存在着与之等价的析取范式和合取范式。以上亦是求析取范式和合取范式的步骤。,74,例题,求命题公式(p(pq)q的析取范式和合取范式。解(p(pq)q(p(pq)q(pp)(pq)q析取范式(pq)q析取范式q析取范式(pq)q合取范式(pq)(pq)合取范式q合取范式注意:公式的析取范式与合取范式不惟一.,75,主析取范式与主合取范式,定义1.4.3含有n个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为极小项。定义1.4.4含有n个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为极大项。说明:(1)由n个命题变元产生的不同的极大项和极小项的个数均为2n个。(2)每个极小项在它的2n个赋值中只有一个成真赋值(3)每个极大项在它的2n个赋值中只有一个成假赋值,76,主析取范式与主合取范式(续),77,3个命题变元的极小项,一般地，n个命题变元形成的极小项可表示为：,主析取范式与主合取范式(续),3个命题变元的极大项,78,一般地，n个命题变元形成的极大项可表示为：,主析取范式与主合取范式,定义1.4.5如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为主析取范式。定理1.4.2任何命题公式的主析取范式都是存在的，并且是唯一的。证明给定命题公式A，1.求A的析取范式A；2.若A的某合取式B不是极小项，则补入没有出现的变元。例如，若pi不在B中，则将B展成如下形式：BB1B(pipi)(Bpi)(Bpi)3.消去重复出现的命题变项、矛盾式及重复出现的极小项。按上述步骤求得的就是A的主析取范式。唯一性证明（略）,79,例题,求命题公式(p(qr)(pqr)的主析取范式。解(p(qr)(pqr)(p(qr)(pqr)(p(qr)(pqr)(pq)(pr)(pqr)析取范式(pq)(rr)(pr)(qq)(pqr)(pqr)(pqr)(prq)(prq)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m2m7(0，1，2，7),80,主析取范式,例题,试由pqr的真值表求它的主析取范式。pqr的真值表解：成真赋值为001，011，101，110，111pqr(1，3，5，6，7)(pqr)(pqr)(prq)(prq)(pqr)一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值,81,主析取范式与主合取范式,定义1.4.6如果含n个命题变元的命题公式的合取范式的每个析取式全是极大项，则称该析取范式为主合取范式。定理1.4.3任何命题公式的主合取范式都是存在的，并且是唯一的。证明给定命题公式A，1.求A的合取范式A；2.若A的某析取式B不是极大项，则补入没有出现的变元。例如，若pi不在B中则将B展成如下形式：BB1B(pipi)(Bpi)(Bpi)3.消去重复出现的命题变项、重言式及重复出现的极大项。按上述步骤求得的就是A的主合取范式。唯一性证明（略）,82,例题,求命题公式(p(qr)(pqr)的主合取范式。解(p(qr)(pqr)(p(qr)(pqr)(pq)(pr)(qrp)合取范式(pq)(rr)(pr)(qq)(pqr)(pqr)(pqr)(pqr)(pqr)主合取范式M3M4M5M6(3，4，5，6)m0m1m2m7(0，1，2，7),83,主析取范式的用途,(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如(pq)rm0m2m4m5m6成真赋值:000,010,100,101,110;成假赋值:001,011,111,84,主析取范式的用途(续),(2)判断公式的类型设A含n个命题变项，则A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项,85,例题,判断公式G(pq)(qp)是否重言式？解G(pq)(qp)(pq)(qp)(pq)qpm10(m01m11)(m00m01)m2m1m3m0m1(0，1，2，3)公式G(pq)(qp)是重言式,86,例题,一种简单的三人表决器，表决者每人座位旁有一个按钮，表决时，若表示同意则按按钮，若不同意不按按钮；表决结果超过半数时，喇叭发出声音。设计满足上述条件的表决器。解三个表决者的按钮分别为p，q，r，喇叭为A。A(pqr)(pqr)(pqr)(pqr)(pq)(pr)(qr)(p(qr)(qr),87,例题,某单位选派A、B、C三位业务骨干去进修，由于工作需要，选派要满足如下条件：若A去，则C同去。若B去，则C不能去。若C不去，则A或B可以去。问可以有哪些选派方案？,88,例题（续）,解设p:派A去，q:派B去，r:派C去。,89,有3个成真赋值，所以有3种选派方案：A和B不去，C去；A和C不去，B去；A和C去，B不去。,该公式的成真赋值就是可行的选派方案。写出该公式的主析取范式：,由已知条件可得：,1.5命题演算的推理,1.5.1推理理论1.5.2推理证明方法,90,推理理论,定义1.5.1设A和B是两个命题公式，当且仅当命题AB是重言式时(即ABT时)，称从A可推出B，或A蕴涵B，或B是前提A的结论，可以表示成AB。一般地，推理的前提可以有多个，若(A1A2An)B是重言式，则称由前提A1，A2，An可推出结论B，可表示为(A1A2An)B。,91,例题,判断下列推理是否正确：p(pq)q(pq)qp解写出p(pq)q和(pq)qp的真值表。p(pq)q正确(pq)qp不正确,92,例题,证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草。”是正确的推理。证明设：p：牛吃草；q：马会飞。前提符号化为：pq，q，结论符号化为：p。而(pq)qp(pq)q)p(pq)qp(pq)(pq)T所以，p是pq和q的有效结论，这个推理是正确的。注意：推理时，只要推理过程的每一步骤都遵循正确的推理规则，推出的结论都称为有效结论，推理都是有效的。,93,推理定律,94,定理（CP规则）,若H1，H2，.，Hm和P推出Q，则H1，H2，.，Hm推出PQ。证明从定理的假设有：H1H2.HmPQ根据定义1.5.1，即有：H1H2.HmPQT令H1H2.HmH，则HPQ(HP)QHPQH(PQ)T所以HPQ，即：H1H2.HmPQ,95,推理证明方法,真值表法等价演算法演绎法附加前提证明法间接推演法(归谬法)归结证明法,96,1、真值表法,通过写出真值表判断AB的类型，若AB是重言式，则由前提A可以推出结论B。例证明前提pq和pr，可以推出结论qr。证明根据定义1.5.1，只需证明(pq)(pr)qr是重言式。列出真值表：,97,98,由真值表可知，(pq)(pr)qr是重言式，所以前提pq和pr，可以推出结论qr。,2、等价演算法,利用命题的等值演算判断AB的类型，若AB是重言式，则由前提A可以推出结论B。证明q是p和pq的结论。证明p(pq)q(p(pq)qp(pq)qpqqT,99,3、演绎法,演绎法是从前提（假设）出发，依据公认