离散数学命题逻辑.ppt

离散数学命题逻辑离散数学命题逻辑现在学习的是第1页，共121页Ch.0 Introduction数学是研究数量的科学 亚里士多得数学的研究对象是客观世界的和逻辑可能的数量关系和结构关系 丁石孙Discrete v.s Continuous0-1:About Math.2现在学习的是第2页，共121页0-2:About Discrete Math.v计算机本身的结构和它处理的对象都是离散型 的，所以计算机科学与技术本质上是一门离散数学技术。v“数字电路”、“编译原理”、“数据结构”、“操作系统”、“数据库系统”、“系统结构”、“容错判断”、“算法的分析与设计”、“逻辑程序设计”、“软件工程”、“人工智能”、“多媒体技术”、“计算机网络”、“信息管理”、“信号处理”、“模式识别”、“数据加密”、“机器定理证明”、“形式语言与自动机”等v 离散数学研究离散（变）量的结构及其相互关系，是计算机科学的理论基础。3现在学习的是第3页，共121页v高等数学：从初等的思维方式带到基于工业革命高等数学：从初等的思维方式带到基于工业革命的学科表达语言的富于创造性的思维方式的学科表达语言的富于创造性的思维方式v离散数学：带入信息革命的学科的表达语言中去离散数学：带入信息革命的学科的表达语言中去发展和创造具有时代特点的先进的思维方式。发展和创造具有时代特点的先进的思维方式。0-2:About Discrete Math.4现在学习的是第4页，共121页0-2:About Discrete Math.The kind of problems solved using Discrete math.include:v How many ways are there to choose a valid password on a computer system?vIs there a link between two computers in a network?v What is the shortest path between two cities using a transportation system?v How can a circuit that adds two integers be designed?v How can a list of integers be sorted so that the integers are in increasing order?How many steps are required to do such a sorting?How can it be proved that a sorting algorithm correctly sorts a list?And so on.5现在学习的是第5页，共121页学科特点学科特点(1)知识点集中，概念和定理多：离散数学是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。(2)方法性强：课程对抽象思维能力要求较高，通过学习能大大提高学习者的逻辑推理能力、抽象思维能力和形式思维能力。课程证明题多，方法灵活，在平时的学习中，要勤于思考，善于总结，多于练习。6现在学习的是第6页，共121页教材与教学参考书v教材：耿素云、屈婉玲、张立昂，离散数学（第四版），清华大学出版社,2008.v教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第三版），清华大学出版社，2008.7现在学习的是第7页，共121页参考书目参考书目v离散数学离散数学，左孝凌著，上海科技文献出版社，左孝凌著，上海科技文献出版社；vDiscrete Mathematics and Its Discrete Mathematics and Its ApplicationsApplications(英文英文Fifth Edition),Fifth Edition),Kenneth H.RosenKenneth H.Rosen著，机械工业出版社；著，机械工业出版社；8现在学习的是第8页，共121页考核方法考核方法v1平时成绩：占总成绩的平时成绩：占总成绩的50%出勤，作业，听课情况，测验出勤，作业，听课情况，测验v2期末考试：占总成绩的期末考试：占总成绩的50%。9现在学习的是第9页，共121页主要内容v数理逻辑数理逻辑v集合论集合论v代数结构代数结构v图论图论v组合分析初步组合分析初步v形式语言和自动机初步形式语言和自动机初步10现在学习的是第10页，共121页数数 理理 逻逻 辑辑 逻辑学是研究推理的科学利用计算的方法来代替人们思维中的逻辑推理过程 莱布尼兹数理逻辑用数学方法研究推理的一门数学学科11现在学习的是第11页，共121页数理逻辑数理逻辑v数理逻辑又称符号逻辑、理论逻辑。它既是数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。数学的一个分支，也是逻辑学的一个分支。v是用数学方法研究逻辑或形式逻辑的学科。是用数学方法研究逻辑或形式逻辑的学科。v其研究对象是对证明和计算这两个直观概念其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。进行符号化以后的形式系统。-一套符号体系 +一组规则12现在学习的是第12页，共121页数理逻辑部分v第1章 命题逻辑 研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。v第2章 一阶逻辑数理逻辑13现在学习的是第13页，共121页第第一一章章 命题逻辑命题逻辑离散数学现在学习的是第14页，共121页第一章 命题逻辑 1.1 1.1 命题符号化及联结词命题符号化及联结词1.2 1.2 命题公式及分类命题公式及分类1.3 1.3 等值演算等值演算1.4 1.4 联结词全功能集联结词全功能集1.5 1.5 对偶与范式对偶与范式1.6 1.6 推理理论推理理论15现在学习的是第15页，共121页1 命题符号化及联结词 一、命题与真值一、命题与真值二、命题分类：原子命题，复合命题二、命题分类：原子命题，复合命题三、命题常项与命题变项及其符号化三、命题常项与命题变项及其符号化四、联结词四、联结词 16现在学习的是第16页，共121页一、命题与真值 命题命题:具有唯一确定真假意义的陈述句具有唯一确定真假意义的陈述句命题的真值命题的真值:判断的结果判断的结果真值的取值真值的取值:真或假真或假真命题真命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假的命题注意注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中判断结果不惟一确定的也不是命题陈述句中判断结果不惟一确定的也不是命题 17现在学习的是第17页，共121页 .真命题假命题疑问句感叹句祈使句不是命题（1）2是素数.（2）雪是黑色的.（3）2+3=5.（4）明年十月一日是晴天.（5）3能被2整除.（6）这朵花多好看呀!（7）明天下午有会吗?（8）请关上门!（9）x+y5.（10）地球外的星球上也有人.真命题假命题18现在学习的是第18页，共121页二、命题分类：简单命题与复合命题二、命题分类：简单命题与复合命题v 简单命题（原子命题）：简单命题（原子命题）：命题不能分成更简单的句子的命题命题不能分成更简单的句子的命题，又称为命题常项（命题常元）。又称为命题常项（命题常元）。2是素数.雪是黑色的.2+3=5.明年十月一日是晴天.3能被2整除.19现在学习的是第19页，共121页二、命题分类：简单命题与复合命题二、命题分类：简单命题与复合命题v复合命题：复合命题：由简单命题用联结词联结而成的命题由简单命题用联结词联结而成的命题。3不是偶数;2是素数和偶数;林芳学过英语或日语;如果角A和角B是对顶角，则角A等于角B20现在学习的是第20页，共121页三、命题常项与命题变项及其符号化三、命题常项与命题变项及其符号化1.1.命题变项（命题变元、命题函数）：真值可以变化命题变项（命题变元、命题函数）：真值可以变化的陈述句。的陈述句。如：x+y5.命题变项不是命题命题变项不是命题。2.2.命题常项（命题常元）：真值唯一确定的陈述句。命题常项（命题常元）：真值唯一确定的陈述句。如：2是偶数.命题常项是命题。命题常项是命题。21现在学习的是第21页，共121页3.简单命题、命题变项的符号化简单命题、命题变项的符号化v简单命题符号化：简单命题符号化：p:2是素数;-命题常项 q:雪是白的;-命题常项v命题变项命题变项符号化：符号化：p:x+y5;-命题变项（不是命题）v命题的真值表示命题的真值表示：1(T)表示真;0(F)表示假.22现在学习的是第22页，共121页四、联结词与复合命题 1.1.否定式与否定式与否定联结词否定联结词“”定义定义1 1 设设p p为命题，复合命题为命题，复合命题 “非非p p”（或（或 “p p的的否定否定”）称）称 为为p p的的否定式否定式，记作，记作 p p.符号符号 称称作作否定联结词否定联结词 p p 为真当且仅当为真当且仅当p p为假为假.例例 p p：3 3是偶数。是偶数。p p：3 3不是偶数不是偶数23现在学习的是第23页，共121页四、联结词与复合命题(续)2.2.合取式与合取联结词合取式与合取联结词“”“”定义定义2 2 设设p p,q q为二命题为二命题,复合命题复合命题“p p并且并且q q”(或或“p p与与q q”)称为称为p p与与q q的的合取式合取式，记作，记作p pq q.称称作作合取联结词合取联结词p pq q为真当且仅当为真当且仅当p p与与q q同时为真同时为真合取联结词合取联结词是是逻辑逻辑“与与”的意思。的意思。24现在学习的是第24页，共121页 例例 将下列命题符号化将下列命题符号化.（1 1）李平既聪明又用功）李平既聪明又用功（2 2）李平虽然聪明）李平虽然聪明,但不用功但不用功（3 3）李平不但聪明，而且用功）李平不但聪明，而且用功（4 4）李平不是不聪明，而是不用功）李平不是不聪明，而是不用功（5 5）李文和李武是兄弟）李文和李武是兄弟解：解：令令 p p：李平用功，：李平用功，q q：李平聪明，则：李平聪明，则（1 1）p p q q （2 2）p p q q（3 3）p p q q （4 4）（(p p)q q）（5 5）r:r:李文和李武是兄弟李文和李武是兄弟v分清简单命题与复合命题分清简单命题与复合命题不能见到不能见到“和和”、“与与”就用就用“”v 描述合取式的灵活性与多样性描述合取式的灵活性与多样性 25现在学习的是第25页，共121页四、联结词与复合命题(续)定义定义3 3 设设 p,qp,q为命题，复合命题为命题，复合命题“p p或或q q”称作称作p p与与q q 的的析取式析取式，记作，记作p pq q.称作称作析取联结词析取联结词 p pq q为假当且仅当为假当且仅当p p与与q q同时为假同时为假.3.析取式与析取联结词“”26现在学习的是第26页，共121页四、联结词与复合命题(续)例 将下列命题符号化 (1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.27现在学习的是第27页，共121页解解 令令 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数,则则 (1),(2),(3)均为均为相容或相容或.分别符号化为分别符号化为:pr,pq,rs,它们的真值分别为它们的真值分别为 1,1,0.而而 (4)为为排斥或排斥或.(4)令令 t:小元元拿一个苹果，小元元拿一个苹果，u:小元元拿一个梨小元元拿一个梨，则则 (4)符号化为符号化为 (t u)(tu).28现在学习的是第28页，共121页四、联结词与复合命题(续)定义4 设 p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，pq为假当且仅当 p 为真 q 为假.4.蕴涵式与蕴涵联结词“”29现在学习的是第29页，共121页pq 的逻辑关系：的逻辑关系：q 为为 p 的必要条件的必要条件“如果如果 p，则，则 q”的不同表述法很多：的不同表述法很多：若若 p，就，就 q 只要只要 p，就，就 q 只有只有 q,才才 p 除非除非 q，才才 p 除非除非 q，否则非，否则非 p四、联结词与复合命题(续)30现在学习的是第30页，共121页v自然语言中自然语言中p与与q具有联系，而数理逻辑中具有联系，而数理逻辑中p与与q可以没有联系。可以没有联系。v例例 如果336，则雪是黑的。如果3+36，则雪是黑的。31现在学习的是第31页，共121页例 设 p:天冷，q:小王穿羽绒服，将下列命题符号化 (1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(7)如果天不冷，则小王不穿羽绒服.注意：pq 与 qp 等值（真值相同）pqpqpqqp qpqp32现在学习的是第32页，共121页四、联结词与复合命题(续)定义5 设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.pq为真当且仅当p与q同时为真或同时为假.说明说明:(1)(1)p pq q 的逻辑关系的逻辑关系:p p与与q q互为充分必要条件互为充分必要条件 5.等价式与等价联结词“”33现在学习的是第33页，共121页例 将下列复合命题符号化并求其真值 （1）2+2=42+2=4当且仅当当且仅当3 3是奇数是奇数:p:pq q 1 1 （2 2）2+242+24当且仅当当且仅当3 3是奇数是奇数:p:p q q 0 0 （3 3）2+2=42+2=4当且仅当当且仅当3 3不是奇数不是奇数:p:p q q 0 0 （4 4）2+242+24当且仅当当且仅当3 3不是奇数不是奇数:p:p q q 1 134现在学习的是第34页，共121页习题习题v小王是游泳冠军或百米赛跑冠军小王是游泳冠军或百米赛跑冠军:v小王现在在宿舍或在图书馆小王现在在宿舍或在图书馆:(p q)(p q)或或 p qv选小王或小李中的一人当班长选小王或小李中的一人当班长:(p q)(p q)v如果我上街，我就去书店看看，除非我很累如果我上街，我就去书店看看，除非我很累:r(r(p q)v王一乐是计算机系的学生，他生于王一乐是计算机系的学生，他生于1968年或年或1969年，他是三好学生年，他是三好学生:p(q r)r)ssp q35现在学习的是第35页，共121页联结词运算规则联结词运算规则v我们所学的我们所学的5 5种基本联结词种基本联结词也称为也称为逻辑逻辑运算符运算符，其，其运算顺序运算顺序为：为：，v如果出现的基本联结词相同，又无括号时，则按从左到右的运算顺序；v如果遇有括号时，不管出现的基本联结词如何，都先进行括号中的运算。36现在学习的是第36页，共121页真值表真值表 p p T F F T p q pq T T T T F F F T F F F F p q p q T T T T F T F T T F F F p q p q T T T T F F F T T F F T p q p q T T T T F F F T F F F T37现在学习的是第37页，共121页第一章 命题逻辑 1.1 1.1 命题符号化及联结词命题符号化及联结词1.2 1.2 命题公式及分类命题公式及分类1.3 1.3 等值演算等值演算1.4 1.4 联结词全功能集联结词全功能集1.5 1.5 对偶与范式对偶与范式1.6 1.6 推理理论推理理论38现在学习的是第38页，共121页2 命题公式及分类一、命题（合式）公式一、命题（合式）公式二、公式的赋值二、公式的赋值三、真值表三、真值表四、命题的分类：重言式四、命题的分类：重言式 矛盾式矛盾式 可满足式可满足式39现在学习的是第39页，共121页一、命题（命题（合式）公式 递归定义递归定义：（1）单个命题常项或变项p,q,r,.,pi,qi,ri,.,0,1是合式公式；（2）如果是合式公式，则是合式公式；（3）如果,B是合式公式，则(A B),(A B),(A B),(A B)是合式公式；（4）只有有限次地应用(1)-(3)组成的符号串才是合式公式.命题（合式）公式：由命题常项、命题变项、联结词、括号等组成的符号串.1.定义40现在学习的是第40页，共121页(p q)r(p q)r(p q)rp r p q rp q r 41现在学习的是第41页，共121页一、命题（命题（合式）公式（续）2.层次 v 若公式若公式A A是单个的命题变项是单个的命题变项,则称则称A A为为0 0层公式层公式.(2)(2)称称A A是是n+1(n0)n+1(n0)层公式是指层公式是指A A符合下列情况之一：符合下列情况之一：A=B，B是n层公式；A=B C，其中B，C分别为i层公式和j层公式A=B C，其中B，C分别为i层公式和j层公式A=B C，其中B，C分别为i层公式和j层公式A=B C，其中B，C分别为i层公式和j层公式其中n=max(i,j);42现在学习的是第42页，共121页合式公式的层次(续)例如 公式 p p pq (pq)r (pq)r)(rs)0层1层2层3层4层43现在学习的是第43页，共121页二、公式的赋值 定义定义 给公式给公式A A中的命题变项中的命题变项 p p1 1,p p2 2,p pn n指指定一组真值称为对定一组真值称为对A A的一个的一个赋值赋值或或解释解释成真赋值成真赋值:使公式为真的赋值使公式为真的赋值成假赋值成假赋值:使公式为假的赋值使公式为假的赋值 A=(pq)r 1 1 0：A=0 成假赋值 1 1 1，0 1 1，0 1 0：A=1 成真赋值44现在学习的是第44页，共121页三、真值表 真值表:公式A在所有赋值下的取值情况列成的表 例例 给出公式的真值表给出公式的真值表 A A=(=(q qp p)q qp p 的真值表的真值表 p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 111145现在学习的是第45页，共121页例 B=(pq)q 的真值表 p q ppq(pq)(pq)q0 00 11 01 1 1100110100100000实例46现在学习的是第46页，共121页例 C=(pq)r 的真值表 p q r pq r (pq)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 1110101047现在学习的是第47页，共121页四、公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1)若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式(也称也称永真式永真式)(2)若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式(也称也称永假式永假式)(3)若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式 A=(qp)qp，B=(pq)q，C=(pq)r48现在学习的是第48页，共121页第一章 命题逻辑 1.1 1.1 命题符号化及联结词命题符号化及联结词1.2 1.2 命题公式及分类命题公式及分类1.3 1.3 等值演算等值演算1.4 1.4 联结词全功能集联结词全功能集1.5 1.5 对偶与范式对偶与范式1.6 1.6 推理理论推理理论49现在学习的是第49页，共121页3 等值演算 一、等值式一、等值式二、基本等值式二、基本等值式三、等值演算与置换规则三、等值演算与置换规则四、应用举例四、应用举例50现在学习的是第50页，共121页一、等值式 定义 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式(pVq)与 pV q(pVq)与 pq注:不是逻辑联结词，表示对任意的赋值，A与B的值相同。是等价联结词，它与不能混为一谈。51现在学习的是第51页，共121页真值表法（真值表法（1）p qpqpVq(pVq)pV q0 0110110 1101011 0011011 100100(pVq)与 pV q 不等值52现在学习的是第52页，共121页真值表法（真值表法（2）p qpppVq(pVq)pq0 0110110 1101001 0011001 100100(pVq)与pq 等值53现在学习的是第53页，共121页二、基本等值式序号等值式定律1A A双重否定2A AVA等幂律3A AA4AVB BVA交换律5ABBA6(AVB)VC AV(BVC)结合律7(AB)C A(BC)8AV(BC)(AVB)(AVC)分配律9A(BVC)(AB)V(AC)54现在学习的是第54页，共121页基本等值式（基本等值式（2）序号等值式定律10(AVB)AB德.摩根律11(AB)AV B12AV(AB)A吸收律13A(AVB)A14A V1 1零律15A0 016AV 0 A同一律17A1 A18AV A 1排中律19AA 0矛盾律55现在学习的是第55页，共121页基本等值式（基本等值式（3）序号等值式定律20AB AVB蕴涵等值式(真值表)21A B(AB)(BA)等价等值式22AB B A假言易位(逆否命题)23A B A B等价否定等值式24(AB)(AB)A归缪论56现在学习的是第56页，共121页三、等值演算与置换规则 等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB,则则(A)(B)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2)基本的等值式基本的等值式 (3)置换规则置换规则 57现在学习的是第57页，共121页四、应用举例四、应用举例验证等值式验证等值式v验证下列等值式验证下列等值式:p(q r)(p q)r（P10例例1.9(1)p(qr)vp(qr)（蕴涵等值式)v p(qr)（蕴涵等值式)v(pq)r（结合律）v(pq)r （德摩根律）v(pq)r（蕴涵等值式)(pq)r (pq)r (pq)r p(qr)p(qr)p(qr)58现在学习的是第58页，共121页验证等值式（续）验证等值式（续）v验证下列等式验证下列等式:p(p q)(p q)（P10例例1.9(2)pp1（同一律）p(q q)（排中律）(pq)(p q)（分配律）59现在学习的是第59页，共121页四、应用举例判断公式类型 例3 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.60现在学习的是第60页，共121页例3(续)(2)(pq)(qp)解 (pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.61现在学习的是第61页，共121页例3(续)(3)(pq)(pq)r)解 (pq)(pq)r)(p(qq)r （分配律）p1r （排中律）pr （同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些62现在学习的是第62页，共121页第一章 命题逻辑 1.1 1.1 命题符号化及联结词命题符号化及联结词1.2 1.2 命题公式及分类命题公式及分类1.3 1.3 等值演算等值演算1.4 1.4 联结词全功能集联结词全功能集1.5 1.5 对偶与范式对偶与范式1.6 1.6 推理理论推理理论63现在学习的是第63页，共121页1.4 联结词全功能集 一、联结词的扩展 异或联结词 与非联结词 或非联结词二、真值函数三、联结词全功能集64现在学习的是第64页，共121页一、复合联结词 排斥或:p q(pq)(pq)与非式:pq(pq)或非式:pq(pq)65现在学习的是第65页，共121页二、真值函数 问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？定义 称定义域为000,001,111，值域为0,1的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:0,1n0,1 表示F是n元真值函数.共有 个n元真值函数.n2266现在学习的是第66页，共121页2元真值函数对应的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFp q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF67现在学习的是第67页，共121页三、联结词的全功能集 定义 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集,中，pqpq,所以，为冗余的联结词;类似地，也是冗余的 在,中，pq(pq)，所以，是冗余的联结词.68现在学习的是第68页，共121页全功能集，极小功能集全功能集，极小功能集v 若任一真值函数都可以用含某一联结词集中的联结词的命题公若任一真值函数都可以用含某一联结词集中的联结词的命题公式表示，则称该联结词集为式表示，则称该联结词集为全功能集全功能集。若一联结词的全功能集。若一联结词的全功能集中不含冗余的联结词，则称它为中不含冗余的联结词，则称它为极小全功能集极小全功能集。,V,，,V,，,V，V，,，为为全功能集全功能集。,V，,，为极小全功能集。69现在学习的是第69页，共121页v用用表示下列命题公式：表示下列命题公式：极小功能集例题极小功能集例题1.pqpq(pq)(pp)(q q)(p p)(q q)2.pq(pq)(pq)(pq)(pq)v pqpq(pp)q Aq(Aq)(Aq)(pp)q)(pp)q)(pp)A70现在学习的是第70页，共121页第一章 命题逻辑 1.1 1.1 命题符号化及联结词命题符号化及联结词1.2 1.2 命题公式及分类命题公式及分类1.3 1.3 等值演算等值演算1.4 1.4 联结词全功能集联结词全功能集1.5 1.5 对偶与范式对偶与范式1.6 1.6 推理理论推理理论71现在学习的是第71页，共121页5 对偶与范式 一、对偶式与对偶原理 二、析取范式与合取范式 三、主析取范式与主合取范式1.极小项和极大项2.求法3.用途 72现在学习的是第72页，共121页一、对偶式和对偶原理定义定义 在仅含有联结词在仅含有联结词,的命题公式的命题公式A A中，将中，将换成换成,换成换成，若，若A A中含有中含有0 0或或1 1，就将，就将0 0换成换成1 1，1 1换成换成0 0，所得命题公式称为，所得命题公式称为A A的的对偶式对偶式，记为，记为A A*.pq 与 pVq是对偶式；(pq)与(pVq)是对偶式。73现在学习的是第73页，共121页一、对偶式和对偶原理(续)定理定理 设设A和和A*互为对偶式，互为对偶式，p1,p2,pn是出现在是出现在A和和A*中的全部命题变项，将中的全部命题变项，将A和和A*写成写成n元函数形式，元函数形式，则则(1)A(p1,p2,pn)A*(p1,p2,pn)(2)A(p1,p2,pn)A*(p1,p2,pn)例如:A(p,q,r)=p(qVr)A(p,q,r)=(p(qVr)pV(qr)A*(p,q,r)=pV(qr)A*(p,q,r)=pV(qr)A*(p,q,r)=(pV(qr)p(qV r)A(p,q,r)=p(qV r)74现在学习的是第74页，共121页对偶原理对偶原理设设A,B为两命题公式为两命题公式,若若AB,则则A*B*,其中其中A*,B*分别为分别为A,B的对偶式的对偶式.例如:(pq)V(pV(pVq)pVq(pq)V(pV(pVq)(pq)v(pvq)(pv(pvq)(qv(pvq)1(pvq)pVq 对偶式(pvq)(p(pq)pq (pvq)(p(pq)(pvq)(pq)(p(pq)v(q(pq)0v(p q)pq75现在学习的是第75页，共121页二、析取范式与合取范式 简单析取式简单析取式:有限个命题变项及其否定构成的析取式有限个命题变项及其否定构成的析取式如 p,q,pq,pqr,简单合取式:有限个命题变项及其否定构成的合取式如 p,q,pq,pqr,析取范式:由有限个简单合取式组成的析取式A1A2Ar,其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,Ar是简单析取式76现在学习的是第76页，共121页二、析取范式与合取范式(续)范式:析取范式与合取范式的总称 公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式 pqr,pqr 既是析取范式，又是合取范式 77现在学习的是第77页，共121页命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)否定联结词的内移或消去 (3)使用分配律 对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一78现在学习的是第78页，共121页求公式的范式举例 例 求下列公式的析取范式与合取范式(1)A=(pq)r解 (pq)r (pq)r （消去）pqr （结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）79现在学习的是第79页，共121页求公式的范式举例(续)解 (pq)r (pq)r （消去第一个）(pq)r （消去第二个）(pq)r （否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r (pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）(2)B=(pq)r80现在学习的是第80页，共121页三、三、主析取范式与主合取范式主析取范式与主合取范式 极小项与极大项极小项与极大项 定义定义 在含有在含有n n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中，中，若每个命题变项及其否定在其中出现且仅出现一次，而且第若每个命题变项及其否定在其中出现且仅出现一次，而且第i（1 i n）个文字出现在左起第个文字出现在左起第i i位上，称这样位上，称这样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项（极大项）极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 mi 极小项，i 成真赋值.Mi 极大项，i成假赋值 mi与Mi的关系:mi Mi,Mi mi 81现在学习的是第81页，共121页极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项 公式 成真赋值名称 公式 成假赋值名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项 极大项 82现在学习的是第82页，共121页 由p,q,r三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真赋值名称 公式 成假赋值名称 p q rp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 83现在学习的是第83页，共121页2.主析取范式与主合取范式 主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3 是主析取范式 (pqr)(pqr)M1M5 是主合取范式 A的主析取范式:与A等值的主析取范式 A的主合取范式:与A等值的主合取范式.84现在学习的是第84页，共121页主析取范式与主合取范式(续)定理定理 任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式,并且是惟一的并且是惟一的.用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)(2)对命题中不含某个变项的采用对命题中不含某个变项的采用 BB1(Bp)(Bp)BB0(Bp)(Bp)(3)(3)极小项（极大项）用名称极小项（极大项）用名称m mi i（M Mi i）表示，并）表示，并按角标从小到大顺序排序按角标从小到大顺序排序.85现在学习的是第85页，共121页求公式的主范式例 求公式 A=(pq)r的主析取范式与主合 取范式.(1)求主析取范式 (pq)r (pq)r,（析取范式）(pq)(pq)(rr)(pqr)(pqr)m6m7,86现在学习的是第86页，共121页求公式的主范式(续)r (pp)(qq)r (pqr)(pqr)(pqr)(pqr)m1m3m5m7 ,代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）87现在学习的是第87页，共121页主析取范式与主合取范式的关系主析取范式与主合取范式的关系v存在存在 mi Mi关系（单个）关系（单个）.所以 Am0 m1 m5 m7 (0,1,5,7)M0 M1 M5 M7 (M0 M1 M5 M7)(M2 M3 M4 M6)(2,3,4,6)88现在学习的是第88页，共121页求公式的主范式(续)(2)求A的主合取范式 (pq)r (pr)(qr),（合取范式）pr p(qq)r (pqr)(pqr)M0M2,89现在学习的是第89页，共121页求公式的主范式(续)qr (pp)qr (pqr)(pqr)M0M4 ,代入并排序，得 (pq)r M0M2M4 （主合取范式）90现在学习的是第90页，共121页3.主范式的用途与真值表相同(1)(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值 例如 (pq)r m1m3m5 m6m7，其成真赋值为001,011,101,110,111，其余的赋值 000,010,100为成假赋值.类似地，由主合取范式也可立即求出成 假赋值和成真赋值.91现在学习的是第91页，共121页主范式的用途(续)(2)判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1.A为矛盾式 A的主析取范式为0 A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项 92现在学习的是第92页，共121页主范式的用途(续)例 用主析取范式判断下述两个公式是否等值：p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4m5 m7 (pq)r=m0m1m2m3 m4m5 m7 (pq)r=m1m3 m4m5 m7故中的两公式等值，而的不等值.(3)判断两个公式是否等值说明：由公式A的主析取范式确定它的主