第一数理逻辑

第一数理逻辑第一页，共一百五十七页，2022年，8月28日引言1.计算机专业的学生为什么要学习离散数学？2.离散数学包含的内容?3.怎样学习离散数学？第二页，共一百五十七页，2022年，8月28日1

什么是离散数学？

离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。

第三页，共一百五十七页，2022年，8月28日2离散数学与计算机科学计算机学科的一个重要特点——离散性硬件软件（系统软件、应用软件）模型算法（程序运行逻辑）数据表示、存储程序编写、执行离散数学第四页，共一百五十七页，2022年，8月28日2离散数学与计算机科学

离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学”！计算机科学知识掌握的过程：“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”！

——需要如下三个方面的能力：构造模型、算法设计、程序设计的能力。思维训练：构造性思维第五页，共一百五十七页，2022年，8月28日3

关于课程学习课程特点知识点集中，概念和定理多方法性强

——阅读，思考，练习，阅读，总结，……学习内容

数理逻辑、集合论、抽象代数、图论第六页，共一百五十七页，2022年，8月28日4.计算科学与数学的关系

至于计算机技术专业的学生为何要学习数学这个问题的答案：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。第七页，共一百五十七页，2022年，8月28日4计算学科与离散数学的关系

在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。

构造模型的能力；算法设计的能力；程序设计的能力。第八页，共一百五十七页，2022年，8月28日6.离散数学在国外的状况

纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….）都有第一流的离散数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。第九页，共一百五十七页，2022年，8月28日6.离散数学在国外的状况

美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T联合创办的，设在Rutgers大学），该中心已是离散数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（MathematicalSciencesResearchInstitute，由陈省身先生创立）在1997年选择了离散数学作为研究专题，组织了为期一年的研究活动。第十页，共一百五十七页，2022年，8月28日6.离散数学在国外的状况

值得一提的是亚洲的发达国家也十分重视离散数学的研究。日本有离散数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的离散数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展离散数学。新加坡，韩国，马来西亚也在积极推动离散数学的研究和人才培养。。世界各地对离散数学的如此钟爱显然是有原因的，那就是没有离散数学就没有计算机科学，没有计算机软件。第十一页，共一百五十七页，2022年，8月28日5.离散数学在国外的状况

20世纪公认的伟大数学家盖尔芳德预言离散数学和几何学将是21世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响应。除上述以外，欧洲也在积极发展离散数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的离散数学研究中心。近几年，南美国家也在积极推动离散数学的研究。澳大利亚，新西兰也组建了很强的离散数学研究机构。第十二页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

例1:在日常生活中我们常常遇到离散数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。第十三页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

例2:一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的"中国邮递员问题"，由中国离散数学家管梅谷教授提出，著名离散数学家J.Edmonds和他的合作者给出了一个解答。第十四页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

例3:一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。第十五页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

例4:一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？第十六页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

例5网络计划技术在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。第十七页，共一百五十七页，2022年，8月28日6.关于离散数学的一些应用

总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。

胡锦涛同志在1998年接见“五四”青年奖章时发表的讲话中指出，离散数学不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的离散数学研究能够为国家的经济建设服务。第十八页，共一百五十七页，2022年，8月28日2023/2/16数理逻辑（MathematicalLogic）

——是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。第一篇数理逻辑第十九页，共一百五十七页，2022年，8月28日2023/2/16主要研究内容：推理

——着重于推理过程是否正确

——着重于语句之间的关系主要研究方法：数学的方法

——就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（SymbolicLogic）。

第一篇数理逻辑第二十页，共一百五十七页，2022年，8月28日2023/2/16什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？

程序＝算法＋数据

算法＝逻辑＋控制第二十一页，共一百五十七页，2022年，8月28日2023/2/16第一章命题逻辑

命题逻辑也称命题演算，或语句逻辑。

研究内容：（1）研究以命题为基本单位构成的前提和结论之间的可推导关系?

（2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？第二十二页，共一百五十七页，2022年，8月28日2023/2/16第一章命题逻辑

命题逻辑的特征：

在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。第二十三页，共一百五十七页，2022年，8月28日2023/2/161.1.1命题定义具有确切真值的陈述句称为命题,该命题只取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“Ｔ”(或“１”)和“Ｆ”(或“０”)表示。1.1命题与命题联结词第二十四页，共一百五十七页，2022年，8月28日2023/2/16（1）太阳是圆的；（2）成都是一个旅游城市；（3）北京是中国的首都；（5）1＋1＝10；（6）ｘ+y>０；（7）我喜欢踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中国是世界上人口最多的国家；（11）我正在说谎；例TTT/F非命题T/FFT/FT悖论T第二十五页，共一百五十七页，2022年，8月28日悖论

首先要知道悖论是一个逻辑学的名词。其定义的表述为：由一个被承认是真的命题为前提，设为B，进行正确的逻辑推理后，得出一个与前提互为矛盾命题的结论非B；反之，以非B为前提，亦可推得B。那么命题B就是一个悖论。当然非B也是一个悖论。第二十六页，共一百五十七页，2022年，8月28日2023/2/16例（续）（12）把门关上；（13）滚出去！（14）你要出去吗？（15）今天天气真好啊！非命题非命题非命题非命题注意：一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。

第二十七页，共一百五十七页，2022年，8月28日2023/2/16命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。结论：第二十八页，共一百五十七页，2022年，8月28日简单命题符号化

用小写英文字母p,q,r,…,pi,qi,ri(i1)或大写英文字母P，Q，R等表示简单命题用“1”表示真，用“0”表示假例如，令

p：是有理数，则p的真值为0，

q：2+5=7，则q的真值为1

命题的符号化第二十九页，共一百五十七页，2022年，8月28日2023/2/16

一般来说，命题可分两种类型：原子命题(简单命题)：不能再分解为更为简单命题的命题。复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果...则...”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类第三十页，共一百五十七页，2022年，8月28日2023/2/161.2.1命题联结词设命题P,Q表示任意两个命题,则最常见的命题联结词有：联接词记号复合命题读法记法真值结果

3.析取

P或者QP与Q的析取PQP∨Q=1P=1或Q=12.合取

∧P并且QP与Q的合取P∧QP∧Q=1P=1且Q=11.否定

┐非PP的否定┐P┐P=1P=04.条件→若P,则QP条件QP→QP→Q=0P=1,Q=0↔5.等价

P当且仅当QP等价于QP↔QPQ=1P=1,Q=1或P=0,Q=0第三十一页，共一百五十七页，2022年，8月28日命题联结词及真值表否定词“¬”（或“”）否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。1.2.2命题联结词的真值表P

¬P0110第三十二页，共一百五十七页，2022年，8月28日合取词“∧”合取词（Conjunction）是二元联结词。相当于自然语言中的“与”、“并且”“而且”、“也”等，真值表如右图。PQP∧Q0000101001111.2.2命题联结词的真值表第三十三页，共一百五十七页，2022年，8月28日析取词“∨”析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么…要么…”等，真值表如右图。PQP∨Q0000111011111.2.2命题联结词的真值表第三十四页，共一百五十七页，2022年，8月28日例：P：今晚我写字，Q：今晚我看书。P∨Q：今晚我写字或看书。或字常见的含义有两种：一种是“可兼或”，如上例：它不排除今晚既看书又写字这种情况；一种是“排斥或”，如：“人固有一死，或重于泰山，或轻于鸿毛”中的或就表示非此即彼，不可兼得。运算∨：表示可兼或注：排斥或用∨表示。1.2.2命题联结词的真值表第三十五页，共一百五十七页，2022年，8月28日蕴含词“”蕴含词（Implication）是二元联结词。相当于自然语言中的“若…则…”、“如果…就…”、“只有…才…”，真值表如右图。PQPQ0010111001111.2.2命题联结词的真值表第三十六页，共一百五十七页，2022年，8月28日等价词“

”等价词（Equivalence）是二元联结词。相当于自然语言中的“等价”“当且仅当”“充要条件”等，真值表如右图。

PQPQ0010101001111.2.2命题联结词的真值表第三十七页，共一百五十七页，2022年，8月28日2023/2/16例题：PQ┐PP∧QP∨QP→QP↔Q0010011011011010001001101111例如：命题P：2是素数；Q：北京是中国的首都第三十八页，共一百五十七页，2022年，8月28日2023/2/16说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；第三十九页，共一百五十七页，2022年，8月28日2023/2/16说明3、联结词与自然语言之间的对应并非一一对应；联结词自然语言∧既…又…、不仅…而且…、虽然…但是…、并且、和、与，等等；→如P则Q、只要P就Q、P仅当Q、只有Q才P、除非Q否则P，等等↔等价、当且仅当、充分必要、等等；相容（可兼）的或第四十页，共一百五十七页，2022年，8月28日2023/2/16符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。

(6)张辉与王丽是同学。例第四十一页，共一百五十七页，2022年，8月28日2023/2/16例1.2.3解（1）设Ｐ：四川是人口最多的省份。则命题（1）可表示为┐Ｐ。（2）设Ｐ：王超是一个思想品德好的学生；Ｑ：王超是一个学习成绩好的学生；

R：王超是一个体育成绩好的学生。则命题（2）可表示为Ｐ∧Ｑ∧R。（3）设Ｐ：教室的灯不亮可能是灯管坏了Ｑ：教室的灯不亮可能是停电了则命题（3）可表示为Ｐ∨Ｑ。第四十二页，共一百五十七页，2022年，8月28日2023/2/16（4）设Ｐ：周末天气晴朗；Ｑ：学院将组织我们到石像湖春游。则命题（4）可表示为Ｐ→Ｑ。（5）设Ｐ：两个三角形全等；Ｑ：三角形的三条边全部相等。则命题（5）可表示为ＰＱ。

(6)P:张辉与王丽是同学例1.2.3解(续)第四十三页，共一百五十七页，2022年，8月28日2023/2/16

为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：否定→合取→析取→条件→等价同级的联结词，按其出现的先后次序(从左到右)若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。约定第四十四页，共一百五十七页，2022年，8月28日2023/2/16设命题

P：明天上午七点下雨；

Q：明天上午七点下雪；

R：我将去学校。符号化下述语句：如果明天上午七点不是雨夹雪，则我将去学校如果明天上午七点不下雨并且不下雪，则我将去学校如果明天上午七点下雨或下雪，则我将不去学校明天上午我将雨雪无阻一定去学校可符号化为：

(P∧Q∧R)∨(┐P∧Q∧R)∨

(P∧┐Q∧R)∨(┐P∧┐Q∧R)。

或((P∧Q)∨(┐P∧Q)∨(P∧┐Q)

∨(┐P∧┐Q))∧R。例题4可符号化为：┐(P∧Q)→R。可符号化为:(┐P∧┐Q)→R。可符号化为:(P∨Q)→┐R。第四十五页，共一百五十七页，2022年，8月28日2023/2/161.3命题公式与真值表定义

一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合{T，F}(或{0，1})注意(1)复合命题为命题变元的“函数”,其函数值仍为"真"或“假”值。(2)真值函数或命题公式，没有确切真值。真值函数第四十六页，共一百五十七页，2022年，8月28日2023/2/16命题公式定义1.3.2(命题公式)命题变元本身是一个公式；如G是公式，则(┐G)也是公式；如G，H是公式，则(G∧H)、(G∨H)、(G→H)、(GH)也是公式；仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、…等表示。第四十七页，共一百五十七页，2022年，8月28日2023/2/16符号串：P∧(Q∨R)→(Q∧(┐S∨R))； ┐P∧Q；P→(┐(P∧Q))； ((P→Q)∧(R→Q))(P→R)。等都是命题公式。例1.3.1例符号串：

(P→Q)∧┐Q)；(┐P∨Q∨(R；

P∨Q∨。等都不是合法的命题公式。第四十八页，共一百五十七页，2022年，8月28日2023/2/161.3.2公式的解释与真值表定义1.3.3设P1、P2、…、Pn是出现在公式G中的所有命题变元，指定P1、P2、…、Pn一组真值，则这组真值称为G的一个解释或指派,常记为Ｉ。

一般来说，若有ｎ个命题变元，则应有2n个不同的解释。

如果公式G在解释Ｉ下是真的，则称Ｉ满足G；如果G在解释Ｉ下是假的，则称Ｉ不满足G。定义

将公式G在其所有可能解释下的真值情况列成表，称为G的真值表。第四十九页，共一百五十七页，2022年，8月28日构造真值表的步骤:(1)找出公式中所含的全部命题变元p1,p2,…,pn(若无下角标则按字母顺序排列),列出2n个全部赋值,从000开始,按二进制加法,每次加1,直至111为止。(2)按从低到高的顺序写出公式的各个层次。(3)对每个赋值依次计算各层次的真值,直到最后计算出公式的真值为止。1.3.2公式的解释与真值表第五十页，共一百五十七页，2022年，8月28日2023/2/16例求下面公式的真值表：Ｇ＝(P→((PQ)∧R))∨Q

其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命题变元。PQRPPQ((PQ)∧RP→((PQ)∧R)G000100110011001101011011011111111000100010101111110000011110

0001第五十一页，共一百五十七页，2022年，8月28日2023/2/16例（续）PQR(P→((PQ)∧R))∨Q00010011010101111000101111011111进一步化简为：第五十二页，共一百五十七页，2022年，8月28日2023/2/16例PQ(Ｐ→Ｑ)→Ｐ(Ｐ→Ｑ)∧Ｐ(Ｐ∧Ｑ)(Ｐ→Q)00100011001010011110求下面这组公式的真值表： Ｇ1＝(Ｐ→Ｑ)→Ｐ；Ｇ2＝(Ｐ→Ｑ)∧Ｐ；Ｇ3＝(Ｐ∧Ｑ)(Ｐ→Q)。第五十三页，共一百五十七页，2022年，8月28日2023/2/16从这三个真值表可以看到一个非常有趣的事实：公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值结论第五十四页，共一百五十七页，2022年，8月28日2023/2/16定义公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足的，如果它不是永假的。第五十五页，共一百五十七页，2022年，8月28日2023/2/16从上述定义可知三种特殊公式之间的关系：永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式可满足式的否定不一定为不可满足式(即为矛盾式)结论第五十六页，共一百五十七页，2022年，8月28日2023/2/16例写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1=(Ｐ→Ｑ)(Ｐ∨Ｑ)；（2）G2=(ＰQ)((Ｐ→Q)∨(Q→Ｐ))；（3）G3=(P→Q)∨Q。第五十七页，共一百五十七页，2022年，8月28日2023/2/16例1.3.4解PQ(Ｐ→Ｑ)(Ｐ∨Ｑ)(Ｐ

Q)(Ｐ→Q)∨(Q→Ｐ)(P→Q)∨Q00101011011010111100永真公式永假公式可满足公式三个公式的真值表如下：第五十八页，共一百五十七页，2022年，8月28日2023/2/16若将其看成两个公式，分别令：

Ｇ＝Ｐ→Ｑ，Ｈ＝┐Ｐ∨Ｑ。则ＧＨ是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说Ｇ和Ｈ相等，记为Ｇ＝Ｈ。为此可定义：1.4等价公式定义

设G、H是公式，如果在任意解释Ｉ下，G与H的真值相同，则称公式G、H是等价的，记作G＝H。第五十九页，共一百五十七页，2022年，8月28日2023/2/16公式G、H等价的充分必要条件是公式GH是永真公式证明:“”假定G，H等价，则G，H在其任意解释Ｉ下或同为真或同为假，于是由“”的意义知，GH在其任何的解释Ｉ下，其真值为“真”，即GH为永真公式。“”假定公式GH是永真公式，Ｉ是它的任意解释，在Ｉ下，GH为真，因此，G、H或同为真，或同为假，由于Ｉ的任意性，故有G＝H。定理第六十页，共一百五十七页，2022年，8月28日2023/2/16

首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“＝”则是描述了两个公式G与H之间的一种逻辑等价关系，G＝H表示“命题公式G等价于命题公式H”，G＝H的结果不是命题公式。

其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即G＝H那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。

“＝”与“”的区别第六十一页，共一百五十七页，2022年，8月28日2023/2/16“=”的性质由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性G=G；（2）对称性若G=H，则H=G；（3）传递性若G=H，H=S，则G=S。这三条性质体现了“=”的实质含义。第六十二页，共一百五十七页，2022年，8月28日2023/2/161.4.2命题公式的基本等价关系例

证明公式G1＝(ＰＱ)与公式G2＝(P→Q)∧(Q→P)之间是逻辑等价的。解：根据定理，只需判定公式G3＝(ＰＱ)((P→Q)∧(Q→P))为永真公式。PQG3＝(ＰＱ)((Ｐ→Q)∧(Q→Ｐ))0011111010110010010011111111第六十三页，共一百五十七页，2022年，8月28日2023/2/16设G，H，S是任何的公式，则：基本等价公式1)Ｅ1：G∨G＝G (幂等律)Ｅ2：G∧G＝G2)Ｅ3：G∨H＝H∨G(交换律)Ｅ4：G∧H＝H∧G3)Ｅ5：G∨(H∨S)＝(G∨H)∨S (结合律)Ｅ6:G∧(H∧S)＝(G∧H)∧S4)

Ｅ7：G∨(G∧H)＝G(吸收律)Ｅ8：G∧(G∨H)＝G第六十四页，共一百五十七页，2022年，8月28日2023/2/165)

Ｅ9：G∨(H∧S)＝(G∨H)∧(G∨S) (分配律）Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S)6)Ｅ11：G∨０＝G (同一律)

Ｅ12：G∧１＝G7)Ｅ13：G∨１＝１ (零律）Ｅ14：G∧０＝０8)Ｅ15：G∨┐G＝1 (排中律)9)Ｅ16：G∧┐G＝0 (矛盾律)基本等价公式（续）第六十五页，共一百五十七页，2022年，8月28日2023/2/16基本等价公式（续）10)Ｅ17：┐(┐G)＝G (双重否定律)11)Ｅ18：┐(G∨H)＝┐G∧┐H(DeMoRGan定律)

Ｅ19：┐(G∧H)＝┐G∨┐H。12)Ｅ20:(GH)＝(G→H)∧(H→G) (等价)13)Ｅ21：(G→H)＝(┐G∨H) (蕴涵)14)E22：G→Ｈ＝Ｈ→G。

(假言易位)15)

E23：GＨ＝GＨ。

(等价否定等式)16)

E24：(G→Ｈ)∧(G→Ｈ)＝G

(归谬论)第六十六页，共一百五十七页，2022年，8月28日2023/2/16设G(P1,P2,…,Pn)是一个命题公式，其中：P1、P2、…、Pn是命题变元，G1(P1,P2,…,Pn)、G2(P1,P2,…,Pn)、...、Gn(P1,P2,…,Pn)为任意的命题公式，分别用G1、G2…、Gn取代G中的P1、P2、…、Pn后得到新的命题公式：

G(G1,G2,…,Gn)＝G′(P1,P2,…,Pn)若G是永真公式（或永假公式），则G′也是一个永真公式（或永假公式）。定理1.4.2(代入定理)第六十七页，共一百五十七页，2022年，8月28日2023/2/16例设Ｇ(Ｐ,Ｑ)＝(Ｐ∧(Ｐ→Ｑ))→Ｑ，证明公式G是一个永真公式。另有两个任意公式： Ｈ(Ｐ,Ｑ)＝(Ｐ∨Ｑ)； Ｓ(Ｐ,Ｑ)＝(ＰＱ)。进一步验证代入定理的正确性。解建立公式G的真值表如右所示。可见为永真公式。PQ(Ｐ∧(Ｐ→Ｑ))→Ｑ001011101111第六十八页，共一百五十七页，2022年，8月28日2023/2/16例（续）

将Ｈ，Ｓ代入到Ｇ中分别取代G中的命题变元P、Q，所得到的公式Ｇ＇为：Ｇ＇(P,Q)=G(H,S)=(H∧(H→S))→S=((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)→(ＰＱ)))→(ＰＱ)

建立新公式Ｇ＇(P,Q)的真值表。PQ((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)→(ＰＱ)))→(ＰＱ)00111111110010000010101011011001011101101111第六十九页，共一百五十七页，2022年，8月28日2023/2/16定理1.4.3(替换定理)设G1是G的子公式(即G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1＝H1，则G＝H。

利用24个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。第七十页，共一百五十七页，2022年，8月28日2023/2/16例利用基本的等价关系，完成如下工作：（1）判断公式的类型：证明((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)是一个永真公式。（2）证明公式之间的等价关系：证明Ｐ→(Ｑ→Ｒ)=(Ｐ∧Ｑ)→Ｒ（3）化简公式：证明(P∧(Ｑ∧R))∨((Ｑ∧R)∨(P∧R))=R第七十一页，共一百五十七页，2022年，8月28日2023/2/16例1.4.3证明（1）((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)=((Ｐ∨Ｑ)∧(Ｐ∨(Ｑ∧Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨(

(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=T

即:((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)为永真公式；

第七十二页，共一百五十七页，2022年，8月28日2023/2/16例将下面程序语言进行化简。IfAthenifBthenXelseYelseifBthenXelseY

TFFTFTStartAXYEndBB

解：执行X的条件为：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)执行Y的条件为：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)第七十三页，共一百五十七页，2022年，8月28日2023/2/16例1.4.4(续）

执行X的条件可化简为：(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝Ｂ∧(Ａ∨Ａ)＝Ｂ执行Y的条件可化简为：(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝Ｂ∧(Ａ∨Ａ)＝ＢTXYEndStartAF程序可简化为：IfBthenXelseY第七十四页，共一百五十七页，2022年，8月28日例题1.4.5:

某件事是甲、乙、丙、丁四人中某一人干的，询问四人后回答如下：1）甲说是丙干的；2）乙说我没干3）丙说甲说的不符合事实4）丁说是甲干的,若其中三人说的对，一人说的不对，问谁干的？第七十五页，共一百五十七页，2022年，8月28日解答：解：若A、B、C、D分别表示命题是甲、乙、丙、丁干的，设4个人所说的命题1）、2）、3）、4）分别用P1，P2，P3，P4表示，则有：P1=A∧B∧C∧

DP2=BP3=CP4=A∧B∧C∧

D据题意，三人说的对，一人说的不对的命题P表示为：P<=>（P1∧P2∧

P3

∧

P4

）∨（P1∧P2∧

P3

∧

P4

）∨（

P1∧P2∧

P3

∧

P4

）∨（P1∧P2∧

P3

∧P4

）

<=>(A∧B∧C∧

D)∨F∨F∨F<=>A∧B∧C∧

D

因为P为真时,A∧B∧C∧

D为真,所以这件事是甲干的。第七十六页，共一百五十七页，2022年，8月28日1.4重言式与蕴含式定理：任何两个重言式的合取或析取，仍然是一个重言式。证明：设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故Ａ∧Ｂ=T，Ａ∨Ｂ=T第七十七页，共一百五十七页，2022年，8月28日定理：一个重言式，对同一分量用任何公式置换，其结果仍为重言式。证明：由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值永为T。例：证明((P∨S)∧R)∨((P∨S)∧R)为重言式。证明：因为P∨P=T，如以((P∨S)∧R)转换P即得,((P∨S)∧R)∨((P∨S)∧R)=T1.4重言式与蕴含式第七十八页，共一百五十七页，2022年，8月28日定理：设A，B为两个命题公式，A<=>B当且仅当AB为一重言式。证明：若A<=>B，则A,B有相同真值,AB永为真，AB为一个重言式。若AB为一重言式,则AB永为真，故A，B真值相同,则A<=>B。1.4重言式与蕴含式第七十九页，共一百五十七页，2022年，8月28日定义：若PQ是一个永真式，则称“P蕴含Q”，记为P⇒Q对PQ来说：QP称作它的逆换式,PQ

称作它的反换式，QP称作它的逆反式，有如下关系；

PQ<=>QPQP<=>PQ

蕴含式第八十页，共一百五十七页，2022年，8月28日两种证明AB的方法：1.用真值表法或推导法证明AB=T(用定义)例:试证:P∧(PQ)Q

证明:P∧(PQ)Q=P∧(P∨Q)Q=(P∧P)∨(P∧Q)Q=(P∧Q)Q=(P∧Q)∨Q=P∨Q∨Q=T1.4.2蕴含式第八十一页，共一百五十七页，2022年，8月28日2.用分析方证明AB,有两种分析法(1)假设前件A为真时,推出后件B也为真,则AB(2)假设后件B为假时,推出前件A也为假,则AB例:P∧(PQ)Q用(1)分析:即P∧(PQ)为真推出Q为真。当P∧(PQ)为真时,则P为真且PQ为真,故Q为真,得证。用(2)分析:即Q为假时,P∧(PQ)为假因为P∧(PQ)=P∧Q,当Q为假时,P∧Q为假,则P∧(PQ)为假,得证。1.4.2蕴含式第八十二页，共一百五十七页，2022年，8月28日基本蕴涵式：（1）PQP（2）PQQ（3）PPQQPQ（4）P(PQ)（5）Q(PQ)（6）(PQ)P（7）(PQ)Q（8）P(PQ)Q（9）Q(PQ)P（10）P(PQ)Q第八十三页，共一百五十七页，2022年，8月28日（11）(PQ)(QR)PR（12）(PQ)(PR)(QR)R（13）(PQ)(RS)（PR）（QS）（14）（P⇆Q）（Q⇆R）（P⇆R）基本蕴涵式：第八十四页，共一百五十七页，2022年，8月28日定理：设P、Q为任意两命题公式，P=Q的充分必要条件是PQ且QP。证明：若P=Q，则P⇆Q为重言式，因为P⇆Q=(P→Q)∧(Q→P)，故P→Q为T且Q→P为T，即PQ且QP成立。反之，若PQ且QP，则P→Q为T且Q→P为T，因此P⇆Q为T，P⇆Q是重言式，即P=Q1.4.2蕴含式第八十五页，共一百五十七页，2022年，8月28日(1)设A,B,C为合式公式,若AB,且A为重言式,则B必是重言式.证明:因为A→B永为T,当A为T时,B必为T.(2)若AB,BC,则AC即蕴含关系是传递的.证明:由AB,BC,可知A→B,B→C为重言式,所以(A→B)(B→C)为重言式.由基本蕴含式(11)可知:(A→B)(B→C)A→C由性质(1)知:A→C为重言式,即AC1.4.3蕴含式的常用性质第八十六页，共一百五十七页，2022年，8月28日(3)若AB且AC,那么A(BC)

证明:由假设可知A→B,A→C为重言式,设A为T,则B,C为T,故BC为T,因此,A→(BC)为T.若A为F,则不论BC为何值,A→(BC)都为T,所以A→(BC)为重言式,所以A(BC)1.4.3蕴含式的常用性质第八十七页，共一百五十七页，2022年，8月28日(4)若AB且CB,则ACB证明:因为A→B,C→B为T,故(AB)(CB)为T,即(AC)B为T即AC→B为T,所以ACB蕴含式的常用性质第八十八页，共一百五十七页，2022年，8月28日2023/2/161.5公式的标准型——范式1.5.1析取范式和合取范式定义

（1）命题变元或命题变元的否定称为文字（2）有限个文字的析取称为析取式(也称为子句）（3）有限个文字的合取称为合取式(也称为短语）（4）P与

P称为互补对。第八十九页，共一百五十七页，2022年，8月28日2023/2/16例子（1）Ｐ、Ｐ是文字；（2）Ｐ∨Ｑ∨Ｒ是子句；（3）Ｐ∧Ｑ∧Ｒ是短语。┐P是一个子句，这种说法正确么？一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。因此，Ｐ，Ｐ不但是文字，也是子句、短语

第九十页，共一百五十七页，2022年，8月28日2023/2/16定义（1）有限个短语的析取式称为析取范式（2）有限个子句的合取式称为合取范式一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）。第九十一页，共一百五十七页，2022年，8月28日2023/2/16例子（1）Ｐ、Ｐ是析取范式、合取范式；（2）Ｐ∨Ｑ∨Ｒ是子句、析取范式、合取范式，

(Ｐ∨Ｑ∨Ｒ)仅是子句、合取范式；（3）Ｐ∧Ｑ∧Ｒ是短语、析取范式、合取范式，

(Ｐ∧Ｑ∧Ｒ)仅是短语、析取范式；（4）(Ｐ∧Ｑ)∨(Ｐ∧Ｑ)是析取范式；（5）(Ｐ∨Ｑ)∧(Ｐ∨Ｑ)是合取范式；（6）句子Ｐ∨(Ｑ∨Ｒ)、(Ｑ∨Ｒ)既不是析取范式也不是合取范式第九十二页，共一百五十七页，2022年，8月28日2023/2/16总结（1）单个的文字是子句、短语、析取范式，合取范式（2）单个的子句是析取范式；（3）单个的短语是合取范式；（4）若单个的子句（短语）无最外层括号，则是合取范式（析取范式）；（5）析取范式、合取范式仅含联结词集{，∧，∨}（6）“”联结词仅出现在命题变元前。第九十三页，共一百五十七页，2022年，8月28日2023/2/16范式的求解方法定理

对于任意命题公式，都存在与其等价的析取范式和合取范式。转换方法：（1）利用等价公式中的等价式和蕴涵式将公式中的→、用联结词、∧、∨来取代，这可利用如下等价关系：(Ｇ→Ｈ)=(Ｇ∨Ｈ)；(ＧＨ)=(Ｇ→Ｈ)∧(Ｈ→Ｇ)=(Ｇ∨Ｈ)∧(Ｈ∨Ｇ)。第九十四页，共一百五十七页，2022年，8月28日2023/2/16范式的求解方法(续)（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：(Ｇ)=Ｇ；

(Ｇ∨Ｈ)=Ｇ∧Ｈ；

(Ｇ∧Ｈ)=Ｇ∨Ｈ。（3）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：Ｇ∨(Ｈ∧Ｓ)=(Ｇ∨Ｈ)∧(Ｇ∨Ｓ)；Ｇ∧(Ｈ∨Ｓ)=(Ｇ∧Ｈ)∨(Ｇ∧Ｓ)。第九十五页，共一百五十七页，2022年，8月28日2023/2/16例求公式：(Ｐ→Ｑ)∨(ＰR)的析取范式和合取范式解

(Ｐ→Ｑ)∨(ＰR)=(Ｐ∨Ｑ)∨((Ｐ∨R)∧(R∨P))=(Ｐ∨Ｑ∨Ｐ∨R)∧(Ｐ∨Ｑ∨

R∨P）=(Ｐ∨Ｑ)∨(Ｐ∨R)) ∧((Ｐ∨Ｑ)∨(R∨P))

=(Ｐ∨Ｑ∨R)——合取范式=Ｐ∨Ｑ∨R——析取范式

第九十六页，共一百五十七页，2022年，8月28日2023/2/16范式的不惟一性

考虑公式：

(Ｐ∨Ｑ)∧(Ｐ∨Ｒ)，其与之等价的析取范式：

Ｐ∨(Ｑ∧Ｒ)；

(Ｐ∧Ｐ)∨(Ｑ∧Ｒ)；Ｐ∨(Ｑ∧Ｑ)∨(Ｑ∧Ｒ)；Ｐ∨(Ｐ∧Ｒ)∨(Ｑ∧Ｒ)。这种不惟一的表达形式给研究问题带来了不便。第九十七页，共一百五十七页，2022年，8月28日2023/2/161.5.2主析取范式和主合取范式1极小项和极大项定义

在含有n个命题变元P1、P2、P3、…、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、…、Pn的一个极小项或极大项。对于n个命题变元，可构成2n个极小项和2n个极大项第九十八页，共一百五十七页，2022年，8月28日2023/2/16例子（1）一个命题变元P，对应的极小项有两项：P、

P；对应的极大项有两项：P、

P。（2）两个命题变元P、Q，对应的极小项有四项：

P∧Q、

P∧Q、P∧Q、

P∧Q；对应的极大项有四项：

P∨Q、

P∨Q、P∨Q、

P∨Q。第九十九页，共一百五十七页，2022年，8月28日2023/2/16例子（续）（3）三个命题变元P、Q、R，对应的极小项有八项：

Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ＲＰ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ＲＰ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ；对应的极大项有八项：

Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨ＲＰ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨ＲＰ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ。第一百页，共一百五十七页，2022年，8月28日2023/2/16两个命题变元的所对应极小项真值表PQ┐P∧┐Q┐P∧QP∧┐QP∧Q001000010100100010110001注意：（1）没有等价的两个极小项；（2）使该极小项的真值为真的指派是唯一的；（3）使极小项为真的那组指派为对应极小项的编码；（4）命题变元与1对应，命题变元的否定与0对应。Ｐ∧Ｑ→{0、0}为真→

{00}→m00(m0)Ｐ∧Ｑ→{01}为真→{01}

→m01(m1)Ｐ∧Ｑ→{10}为真→{10}

→m10(m2)Ｐ∧Ｑ→{11}为真→{11}

→m11(m3)第一百零一页，共一百五十七页，2022年，8月28日2023/2/16两个命题变元的所对应极大项真值表PQ┐P∨┐Q┐P∨QP∨┐QP∨Q001110011101101011110111注意：（1）没有等价的两个极大项；（2）使该极大项的真值为假的指派是唯一的；（3）使极大项为假的那组指派为对应极大项的编码；（4）命题变元与0对应，命题变元的否定与1对应。Ｐ∨Ｑ→{0、0}为假→

{00}→M00(M0)Ｐ∨Ｑ→{01}为假→{01}

→M01(M1)Ｐ∨Ｑ→{10}为假→{10}

→M10(M2)Ｐ∨Ｑ→{11}为假→{11}

→M11(M3)第一百零二页，共一百五十七页，2022年，8月28日2023/2/16三个命题变元的极小项和极大项PQR极小项极大项000m0=┐P∧┐Q∧┐RM0=P∨Q∨R001m1=┐P∧┐Q∧RM1=P∨Q∨┐R010m2=┐P∧Q∧┐RM2=P∨┐Q∨R011m3=┐P∧Q∧RM3=P∨┐Q∨┐R100m4=P∧┐Q∧┐RM4=┐P∨Q∨R101m5=P∧┐Q∧RM5=┐P∨Q∨┐R110m6=P∧Q∧┐RM6=┐P∨┐Q∨R111m7=P∧Q∧RM7=┐P∨┐Q∨┐R第一百零三页，共一百五十七页，2022年，8月28日mi∧mj=F2023/2/16极小项和极大项的性质任意两个极小项的合取必为假；任意两个极大项的析取必为真；极大项的否定是极小项；极小项的否定是极大项；所有极小项的析取为永真公式；所有极大项的合取是永假公式。

Mi=┐miMi∨Mj=T

┐Mi=

mi第一百零四页，共一百五十七页，2022年，8月28日2023/2/162主析取范式和主合取范式定义

（1）在给定的析取范式中，每一个短语都是极小项，则称该范式为主析取范式（2）在给定的合取范式中，每一个子句都是极大项，则称该范式为主合取范式（3）如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”。第一百零五页，共一百五十七页，2022年，8月28日2023/2/16定理任何一个公式都有与之等价的主析取范式和主合取范式。证明（1）利用定理先求出该公式所对应的析取范式和合取范式；（2）在析取范式的短语和合取范式的子句中重复出现的命题变元，将其化成只出现一次；（3）去掉析取范式中的所有永假式（P∧┐P

），去掉合取范式中所有永真式（P∨┐P

）第一百零六页，共一百五十七页，2022年，8月28日2023/2/16定理1.5.2证明（续）（4）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式：(Ｐ∨┐Ｐ)∧Q=Q将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式：(Ｐ∧┐Ｐ)∨Q=Q将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项；第一百零七页，共一百五十七页，2022年，8月28日2023/2/16证明（续）（5）利用等幂律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。第一百零八页，共一百五十七页，2022年，8月28日2023/2/16例利用等价公式转换法求公式(P→Q)→(Q∧R)的主析取范式和主合取范式。解（1）求主析取范式

(P→Q)→(Q∧R)=(P∨Q)∨(Q∧R)=(P∧Q)∨(Q∧R)——析取范式=(P∧Q∧(R∨R))∨((P∨P)∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)——主析取范式第一百零九页，共一百五十七页，2022年，8月28日2023/2/16例（续）（2）求主合取范式

(P→Q)→(Q∧R)=(P∧Q)∨(Q∧R)=(P∨Q)∧(P∨R)∧(Q∨Q)∧(Q∨R)=(P∨Q)∧(P∨R)∧(Q∨R)——合取范式

第一百一十页，共一百五十七页，2022年，8月28日2023/2/16例（续）=(P∨Q∨(R∧R))∧(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧((P∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)——主合取范式

第一百一十一页，共一百五十七页，2022年，8月28日2023/2/16需要说明求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。如公式：

G1=(P→Q)∧Q，

G2(P,Q,R)=(P→Q)∧Q。前者是依赖于两个命题变元的，后者应依赖于三个命题变元。第一百一十二页，共一百五十七页，2022年，8月28日定理1-5.4在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。定理1-5.5在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。主析取范式与主合取范式第一百一十三页，共一百五十七页，2022年，8月28日2023/2/16如何用极小项来构成主析取范式？PQm0m1m2m3P->Q备注0010001010100110001001100011m1必须包含在主析取范式中m0必须包含在主析取范式中m3必须包含在主析取范式中m2一定不能包含在主析取范式中主析取范式中必须且只能包含使得公式真值为真的那些解释对应的极小项。第一百一十四页，共一百五十七页，2022年，8月28日2023/2/16如何用极大项来构成主合取范式？PQM0M1M2M3PQ备注0001111011011010110101111101M1必须包含在主合取范式中M2必须包含在主合取范式中M0一定不能包含在主合取范式中M3一定不能包含在主合取范式中主合取范式中必须且只能包含使得公式真值为假的那些解释对应的极大项。第一百一十五页，共一百五十七页，2022年，8月28日2023/2/16真值表技术（1）列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到相应的主析取范式。（2）列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。第一百一十六页，共一百五十七页，2022年，8月28日2023/2/16例利用真值表技术求公式G=┐(Ｐ→Ｑ)∨Ｒ的主析取范式和主合取范式。PQRP→Q┐（P→Q）┐(P→Q)∨R000100001101010100011101100011101011110100111101第一百一十七页，共一百五十七页，2022年，8月28日2023/2/16例（续）（1）求主析取范式找出真值表中其真值为真的行：

2.001；4.011；

5.100；6.101；

8.111。这些行所对应的极小项分别为：┐P∧┐Ｑ∧Ｒ，┐P∧Ｑ∧Ｒ，P∧┐Ｑ∧┐Ｒ，

P∧┐Ｑ∧Ｒ，P∧Ｑ∧Ｒ。第一百一十八页，共一百五十七页，2022年，8月28日2023/2/16例（续）将这些极小项进行析取即为该公式G的主析取范式。

G=┐(Ｐ→Ｑ)∨Ｒ=(┐P∧┐Ｑ∧Ｒ)∨(┐P∧Ｑ∧