离散数学第一章 命题逻辑

1、第一章第一章 命题逻辑命题逻辑离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社引言离散数学是计算机专业的一门重要基础课。它所研究的对象是离散数量关系和离散结构数学结构模型。 离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中。同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。 学习方法n 精确严格地掌握好概念和术语，正确理解它们的内涵和外延

2、；n 独立完成作业，自觉归纳基本解题方法；n 阅读和复习时，随时备好纸笔，以便进行详细的推导和计算；n 学习和理解术语，给术语赋予特殊的含义，加深理解。n 多做习题，加深理解。什么是数理逻辑？数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律。因此，数理逻辑又称为符号逻辑。什么是数理逻辑？数理逻辑的创始人-莱布尼茨n 莱布尼茨(Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14n 德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、

3、语言学、生物学以及外交、神学等诸多方面.n 出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了，给他留下了丰富的藏书。什么是数理逻辑？数理逻辑的创始人-莱布尼茨n 15岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的几何原本的课程后，莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位 。n 19岁设计出世界第一台乘法器，被认为是现代机器数学的先驱

4、者。n Leibniz(16461716年) 之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。n 1693年，发现了机械能的能量守恒定律。n 与牛顿并称为微积分的创立者。n 系统阐述了二进制记数法，并把它和中国的八卦联系起来。命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的推理理论1.1 命题和联结词现实语言判定推理翻译应用：p 计算机电路设计 p 计算机程序构造 p 程序正确性证明1.1 命题和联结词定义1.1 命题是或者为真，或者为假而不是两者同时成立的陈述句。n 作为命题的陈述句所表达的判断结果称作命题的

5、真值，真值只能取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。注意：任何命题的真值都是唯一的。n 如果一个命题的真值是真，则用1或T(Ture)来表示；如果一个命题的真值是假，则用0或F（False）来表示。n 命题用大写的英文字母，如P，Q，R来表示。n 判断给定句子是否为命题分为两步：首先判断该句子是否为陈述句，其次判断它是否有唯一的一个真值。命题的概念1.1 命题和联结词例1.1 判断下面句子是否是命题。（1）2013年是闰年。（2）22=5。（3）小明晚上去看电影。（4）这朵花真漂亮啊！（5）请不要在此处吸烟！（6）你下午会出去吗？（7）2既是素数又是偶数。（8）

6、本句话是错的。命题的概念（1）、（2）、（3）和（7）都是命题1.1 命题和联结词联结词是逻辑联结词或者命题联结词的简称，它是自然语言中连词的逻辑抽象。有了联结词，就可以通过它和原子命题构成复合命题。常用的逻辑联结词主要包括以下6种。n（1）联结词“非”，记为“P ”，表示“否定”的意思。n（2）联结词“合取”，记为“”，表示“且”的意思。n（3）联结词“析取”，记为“”，表示“或”的意思。n（4）联结词“蕴涵”，记为“”，表示“如果，则”的意思。n（5）联结词“等价”，记为“”，表示“当且仅当”的意思。n（6）联结词“抑或”，记为“”，表示“要么，要么”的意思。联结词1.1 命题和联结词n

7、设P是一个命题，则联结词和命题P构成P，P为命题P的否定式复合命题，读作“非P”。联结词是自然语言中的“非”、“不”和“没有”等的逻辑抽象。n 其真值是这样定义的，若P的真值是T，那么P的真值是F；若P的真值是F，则P的真值是T。命题P与其否定P的如表1.1所示。逻辑联结词否定“”PPFTTFPP0110表1.1逻辑联结词“”的定义1.1 命题和联结词n例1.2 给出下列命题的否定。（1）令P表示：大连是北方香港。 于是P表示：大连不是北方香港。 注意：逻辑联结词否定是个一元运算符。（2）令Q表示：所有的素数都是奇数。 于是Q表示：并非所有的素数都是奇数。 注意：翻译成“所有的素数都不是奇数”

8、是错误的。因为否定是对整个命题进行的。逻辑联结词否定“”1.1 命题和联结词n 设P是一个命题，Q是一个命题，由联结词把P和Q连接成PQ，称PQ为P和Q的合取式复合命题，PQ读作“P与Q”或者“P合取Q”。联结词是“并且”的逻辑抽象。n 它的真值是这样定义的：当且仅当P和Q的真值都为T时，PQ的真值才为T，否则PQ的真值为F。逻辑联结词“”的定义如表1.2所示。逻辑联结词合取“”PQPQFFFFTFTFFTTTPQPQ000010100111表1.2逻辑联结词“”的定义1.1 命题和联结词n 例1.3 令P表示：外面正在下雪。 令Q表示：3小于5。 于是PQ表示 ：外面正在下雪并且3小于5。n

9、 从自然语言看，上述命题是不合理的、没有意义的，因为P和Q毫不相关。但是，在数理逻辑中是被允许的，也是正确的。P和Q再合取PQ仍可成为一个新的命题。只要P和Q的真值给定，PQ的真值即可确定。n 逻辑联结词“”是个二元运算符，且具有对称性，即PQ和QP具有相同真值。逻辑联结词合取“”1.1 命题和联结词n 设P是一个命题，Q是一个命题，由联结词把P、Q连接成PQ，称PQ为P、Q的析取式复合命题，读作“P或Q”，或“P析取Q”。n 其真值是这样的定义的：当且仅当P和Q的真值均为F时，PQ的真值为F，其余情况均为T。逻辑联结词“”的定义如表1.3所示。逻辑联结词析取“”PQPQFFFFTTTFTTT

10、TPQPQ000011101111表1.3逻辑联结词“”的定义1.1 命题和联结词n 联结词是自然语言中“或”、“或者”的逻辑抽象。而在自然语言中，“或”是多义的。从析取的定义不难看出，逻辑联结词“”和自然汉语中的“或”的意义并不完全相同。因为汉语中的“或”可表示“排斥或”，亦可表示“可兼或”，而逻辑联结词“析取”指的仅仅是“可兼或”，并不表示其他意义的“或”。n 例1.4 令P表示：小明现在正在睡觉。 令Q表示：小明现在正在打球。于是命题，小明现在正在睡觉或者正在打球不能用PQ来表示。因为这里自然语言陈述的或是排斥或，这种意义的或我们用另一个逻辑联结词“异或”“”来表示，后面我们将给出它的定

11、义。逻辑联结词析取“”1.1 命题和联结词n 例1.5 将句子“他昨晚做了20或者30道作业题”表示为复合命题。在此例中，该句子不能被表示成复合命题，因为这里的“或”表示的是近似或者猜测的意思。n 例1.6 令P表示：张亮是跳高运动员。 令Q表示：张亮是跳远运动员。于是命题，张亮可能是跳高或跳远运动员就可以用PQ来表示，因为这里的或是可兼或。逻辑联结词析取也是个二元运算符。逻辑联结词析取“”1.1 命题和联结词n 设P是一个命题，Q是一个命题，由联结词把P、Q连接成PQ，称PQ为P、Q的条件式复合命题，把P和Q分别称为PQ的前件和后件，或者前提和结论。PQ读作“如果P则Q”或“如果P那么Q”。

12、其中P被称为前件，Q被称为为后件。很多时候联结词也被称为蕴涵。n PQ的真值是这样定义的，当且仅当PQ的前件P的真值为T，后件Q的真值为F时，PQ的真值为F，否则，PQ的真值为T。单条件逻辑联结词“”的定义如表1.4所示。逻辑联结词单条件“”PQPQFFTFTTTFFTTTPQPQ001011100111表1.4逻辑联结词“”的定义1.1 命题和联结词n例1.7：（1）令P表示：天不下雨 令Q表示：植物枯萎 于是PQ表示：如果天不下雨，则植物枯萎。（2）令R表示：我有时间。 令S表示：我一定去学画画。 于是，RS表示：如果我有时间，那我一定去学画画。（3）令U表示：大海的颜色是蓝色的。 令V表

13、示：雪的颜色是白色的。 于是，UV表示：如果大海的颜色是蓝色的，那么雪的颜色是白色的。逻辑联结词单条件“”1.1 命题和联结词n 设P是一个命题，Q是一个命题，于是联结词把P、Q连接成PQ，称PQ为P和Q的双条件式复合命题，读作“P当且仅当Q”或“P等值于Q”。n PQ的真值是这样定义的，当且仅当P和Q有相同的真值时，PQ的真值为T，否则，PQ的真值为F。PQ的运算表如表1.5所示。逻辑联结词双条件“” PQPQFFTFTFTFFTTTPQPQ001010100111表1.5逻辑联结词“”的定义1.1 命题和联结词n例1.8 使用联结词翻译一下命题：（1）三角形是等边的，当且仅当它的3个内角相

14、等。（2）电灯不亮，当且仅当灯泡发生故障或开关发生故障。（3）2 + 2 = 4，当且仅当今天天晴。逻辑联结词双条件“”解：令P：三角形是等边的。 Q：三角形3个内角相等。于是（1）可表示为：PQ令R：电灯不亮。 S：灯泡发生故障。 T：开关发生故障。于是（2）可表示成：R(ST)。令A：2 + 2 = 4。 B：今天天晴。于是（3）可表示为：AB1.1 命题和联结词n 设P是一个命题，Q是一个命题，于是“P异或Q”是一个新的命题，记作“PQ”，读作“P异或Q”。其真值是这样定义的，当且仅当P和Q有不同的真值时，PQ的真值为T，否则PQ的真值为F。n PQ的运算表如表1.6所示。逻辑联结词异或

15、“”PQPQFFFFTTTFTTTFPQPQ000011101110表1.6逻辑联结词“”的定义命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的推理理论1.2 合式公式与真值表n 定义1.2 合式公式：（1）真值T和F是合式公式。（2）原子命题公式是一个合式公式。（3）如果A是合式的公式，那么A是合式的公式。（4）如果A和B均是合式的公式，那么(AB)，(AB),(AB)和(AB)都是合式的公式。（5）当且仅当有限次地应用（1）至（4）条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式的公式。 以上定义方法称为递归定义法。其中（1）称为递归定义的基础

16、，（2）、（3）和（4）称为递归定义的归纳，（5）称为递归定义的界限。合式公式1.2 合式公式与真值表n 按照上面的定义，下面的字符串都是合式的公式。（1）(PQ)（2）(PQ)（3）(P(PQ)（4）(PQ)(QR)(S T)n 下面的字符串则不是合式的公式。（1）(PQ)(Q)（2）(PQ)（3）(PQ)Q)合式公式1.2 合式公式与真值表n今后，我们把合式的公式简称为命题公式。一般一个命题公式的真值是不确定的，只有用确定的命题去取代命题公式中的命题变元，或对其中的命题变元进行真值指派时，命题公式才成为具有确定真值的命题。n给定两个命题公式，若对其中变元的所有可能的真值指派两个命题公式具有

17、相同的真值，则称它们是相互等价的。可以利用真值表技术来判定两个命题公式的等价性。合式公式1.2 合式公式与真值表n定义1.3 设A为一命题公式，对其中出现的命题变元做所有可能的每一组真值指派S，连同公式A相应S(A)的取值汇列成表，称为A的真值表。一个真值表由两部分构成。（1）表的左半部分列出公式的每一种解释。（2）表的右半部分给出相应每种解释公式得到的真值。为构造的真值表方便和一致，有如下约定。（1）命题变元按字典序排列。（2）对公式的每种解释，以二进制数从小到大或者从大到小顺序排列。（3）若公式复杂，可先列出各子公式的真值（若有括号从里层向外展开），最后列出所给公式的真值。真值表1.2 合

18、式公式与真值表n 例1.10：（1）给出命题公式(PQ)P)的真值表。（2）使用真值表技术证明命题公式PQ与PQPQ是相互等价的。真值表解：构造（1）的真值表如下PQPQ(PQ)P(PQ)P)00001011011011011110对于（2）构造真值表如下PQPQPQPQ0011010010001111命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的推理理论1.3 永真式和等价式n 定义1.4 永真式、永假式与可满足式。（1）不依赖于命题变元的真值指派，而总是取值为T（即1）的命题公式，称为永真式或称作重言式。（2）不依赖于命题变元的真值指派，而总是取值

19、为F（即0）的命题公式，称为永假式或矛盾式。（3）至少存在一组真值指派使命题公式取值为T的命题公式，称为可满足的。永真式1.3 永真式和等价式n 定义1.5 设A和B是两个命题公式，如果A、B在其任意解释下，其真值都是相同的，即AB是重言式，则称A和B是等价的，或逻辑相等，记作AB，读作A恒等于B，或A等价于B。n 注意符号“”与符号“”的意义是有区别的。符号“”是逻辑联结词，是个运算符；而符号“”是关系符，AB表示A和B有逻辑等价关系。等价式1.3 永真式和等价式n 常用的逻辑恒等式如表1.7所示。n 表中符号P、Q、R代表任意命题，符号T代表真命题，符号F代表假命题。表中所有公式是进行等价

20、变换和逻辑推理的重要依据。等价式1.3 永真式和等价式n 在一个重言式中，某个命题变元出现的每一处均代以同一个公式后，所得到的新的公式仍是重言式，这条规则称之为代入规则。这条规则之所以正确，是因为永真式对任何解释，其值都是真，与所给的某个变元指派的真值是真还是假无关，因此，用一个命题公式代入到原子命题变元R出现的每一处后，所得命题公式的真值还是真。例如：PPF令以RQ代P得，（RQ）(RQ) F仍是重言式。代入规则1.3 永真式和等价式n 设有恒等式AB若在公式C中出现A的地方替换以B（不一定是每一处都进行）而得到公式D,则CD，这条规则称之为替换规则。如果A是公式C中完整的部分，且A是合式的

21、公式，则称A是C的子公式。规则中“公式C中出现A”意即“A是C的子公式”。这条规则之所以正确，是因为在公式C和D中替换部分以外均相同，所以C和D的真值也相同，故CD。替换规则1.3 永真式和等价式 设应用代入规则和替换规则及已有的重言式可以证明新的重言式。例如对公式E12：（PQ） PQ，我们以AB代E12中的P，而以AB代E12中的Q就得出公式(AB)(AB) (AB) (AB)对公式E20：PTP，我们利用公式PPT，对其中的T作替换（对命题常元不能做代换）得公式P(PP) P因此，我们可以说表1.7和表1.9中的字符P、Q和R不仅代表命题变元，而且可以代表命题公式；T和F不仅代表真命题和

22、假命题，而且可以代表重言式和永假式。用这样的观点看待表中的公式，应用就显得更方便。1.3 永真式和等价式n例1.12（1）试证P(QR) Q(PR) R(QP)证：P(QR) P(QR)两次替换 Q(PR) 结合、交换、结合 Q(PR) 两次替换类似可证P(QR) R(QP)。（2）试证（PQ）(QR) PQR证：(PQ)(QR) (PQ) (QR)E27和替换规则 (PQ)(QR) E12和替换规则 (PQ)Q)RE4 (PQ)(QQ)R PQR例1.12的（1）和替换规则命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的推理理论1.4 对偶式与蕴含式n

23、 定义1.6 设有公式A，其中仅含逻辑联结词，和逻辑常值T和F。在A中将，T，F分别换以，F，T得公式A*，则称A*为A的对偶式。同理，A也可称为A*的对偶式，即对偶式是相互的。n定理1.1 设A和A*互为对偶式，P1，P2，Pn是出现于A和A*中的所有命题变元，于是：A（P1，P2，Pn）A*( P1，P2，Pn) A（P1，P2，Pn）A*( P1，P2，Pn)对偶式1.4 对偶式与蕴含式n 定理1.2 若AB，且A、B为命题变元P1，P2，Pn及联结词，构成的公式，则A*B*。证明：AB意味着：A(P1，P2，Pn）B(P1，P2，Pn）为永真式，于是A(P1，P2，Pn）B(P1，P2

24、，Pn）为永真式，由定理1.1得，A*(P1，P2，Pn）B*(P1，P2，Pn）为永真式。因为上式是永真式，使用带入规则所得仍为永真式，今以Pi代P（i=1,2,n），得A*(P1，P2，Pn）B*(P1，P2，Pn）为永真式，所以A*B* 。本定理称为对偶原理。对偶式1.4 对偶式与蕴含式n 定理1.3 如果A B且A，B为命题变元P1，P2，Pn及联结词，构成的公式，则B* A*证明：A B意味着A(P1，P2，Pn）B(P1，P2，Pn）为永真式。由逆反律得，B(P1，P2，Pn）A(P1，P2，Pn）为永真式。由定理1.1得，B*(P1，P2，Pn）A*(P1，P2，Pn）为永真式。

25、因为上式是永真式，使用带入规则仍为永真式，今以Pi代 Pi (i=1，2， )得B* A* 。对偶式1.4 对偶式与蕴含式n 如果单条件联结式AB是一个永真式，则它被称为永真蕴涵式，记为“AB”,读作“A永真蕴涵B”。其中A称为B的有效前提，B称为A的逻辑结果，可以说由A推出B，也可以说B是由A推出的。从AB的定义不难看出，要证明A永真蕴涵B，只要证明AB是一个永真式即可。而从AB的定义不难知道要说明AB是永真式，只要说明下面两点之一即可。假定前件A是真，若能推出后件B必为真，则AB永真，于是AB。假定后件B是假，若能推出前件A必为假，则AB永真，于是AB。也可以用真值表法来证明永真蕴涵式。即

26、证明对于命题公式中命题变元的所有真值指派来说，若其中使逻辑前提取值为真的那些真值指派，也必然使逻辑结果取值为真，则说AB。蕴含式1.4 对偶式与蕴含式n常用的永真蕴涵式如表1.9所示。蕴含式I1PQ P 化简式I2PQ QI3P PQ 附加式I4Q PQI5P PQI6Q PQI7 (PQ) PI8(PQ) QI9P,PQ Q析取三段论I10P,PQ Q假言推论I11Q, PQ P拒取式I12PQ，QR PR假言三段论I13PR，PR,QR R二难推论I14PQRPRQI15PQ RPRQI16P,Q PQ命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的

27、推理理论1.5 范式和判定问题n定义1.7 命题公式中的一些变元和一些变元的否定之积，称为基本积；一些变元和变元的否定之和，称为基本和。n定理1.4 一个基本积是永假式，当且仅当它含有P，P形式的两个因子。证明：（充分性）PP是永假式，而QF两个因子时，此基本是永假式，所以含有P和P形式的两个因子的基本积是永假式。（必要性）用反证法。设基本积永假但不含P和P形式的因子，于是给这个基本积中的命题变元指派真值T，给带有否定的命题变元指派真值F，得基本积的真值是T，与假设矛盾。证毕。析取范式1.5 范式和判定问题n定理1.5 一个基本和是永真式，当且仅当它含有P，P形式的两个因子。n定义1.8 一个

28、由基本积的和组成的公式，如果与给定的公式A等价，则称它是A的析取范式，记为：AA1A2An ，n1，其中Ai(i1，2，n)是基本积。对于任何命题公式，都可求得与其等价的析取范式，这是因为命题公式中出现的和可用、和表达，括号可通过德摩根定律和对的分配律消去。但是一个命题公式的析取范式不是唯一的。如果析取范式中每个基本积都是永假式，则该范式必定是永假式。析取范式1.5 范式和判定问题n例1.16（1）求(P(QR) S的析取范式。解：(P(QR) S (P(QR) S (P(QR) S P(QR) S 析取范式（2）求(PQ) (PQ)的析取范式。解：(PQ) (PQ)(PQ)(PQ)(PQ)(

29、PQ) (PQPQ)(PQ)(PQ)F(PQ)(PQ) (PQ)(PQ) (PQ)P)(PQ)Q)PPPQPQQQFPQPQF(PQ)(PQ)。 析取范式1.5 范式和判定问题n定义1.9 一个由基本和的积组成的公式，如果与给定的命题公式A等价，则称它是A的合取范式，记为：AA1A2An ，n1，其中A1，A2，An，是基本和。对任何命题公式都可求得与其等价的合取范式，道理同析取范式。同样，一个命题公式的合取范式也不唯一。如果一个命题公式的合取范式的每个基本和都是永真式，则该式也必定是永真式。合取范式1.5 范式和判定问题n例1.17（1）试证QPQPQ是永真式。解：QPQPQQ(PP)Q Q

30、TQ QQ T（2）求(PQ) (PQ)的合取范式。解：令A(PQ) (PQ)，则 A(PQ) (PQ) (PQ)(PQ)(PQ)(PQ) (PQPQ)(PQ)(PQ) (PQ)(PQ)由于AA(PQPQ)所以A (PQ)(PQ)合取范式1.5 范式和判定问题n定义1.10 在含n个变元的基本积中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本积为极小项。n个变元可构成2n个不同的极小项。例如3个变元P、Q，R可构成8个极小项。我们把命题变元看成1，命题变元的否定看成0，于是每个极小项对应于一个二进制数，也对应一个十进制数。对应情况如下。极小项PQR0000PQR00

31、1lPQR0102PQR0113PQR1004PQR1015PQR1106PQR1117PQR m0PQRm 1PQRm 2PQRm 3PQRm 4PQR m 5PQRm 6PQRm 7把极小项对应的十进制数当作足标，并用mi(i=0，1，2，2n-1)表示这一项一般，n个变元的极小项是：P1P2Pnm0P1P2Pn-1Pnm1P1P2Pn-1Pnm2P1P2Pn 21nm1.5 范式和判定问题n定义1.11 一个由极小项的和组成的公式，如果与命题公式A等价，则称它是公式A的主析取范式。对任何命题公式(永假式除外)都可求得与其等价的主析取范式，而且主析取范式的形式唯一。它给范式判定问题带来很大

32、益处。例如：APQR (PQ)(RR)(PP)R PQRPQRPRPR PQRPQRPR(QQ)(PR)(QQ) PQRPQRPQRPQRPQRPQR PQRPQRPQRPQRPQR m7m6m5m3m1 (1，3，5，6，7)其中，符号“”是借用数学中求和的符号，这里代表析取。主析取范式 1.5 范式和判定问题n定义1.12 在含n个变元的基本和中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本和为极大项。n个变元可以构成2n个不同的极大项。例如三个变元P，Q，R可构成八个极大项。在极大项中，我们把命题变元看成0,而把命题变元的否定看成1，于是每一个极大项对应于一个

33、二进制数，也对应一个十进制数。对应情况如下极大项PQR-0000PQR-0011PQR-0102PQR -0113PQR-1004PQR -1015PQR -1106PQR -1117PQRM0PQR M1PQR M2PQR M3PQRM4PQR M5PQR M6PQR M7把极大项对应的十进制数当作足标，并用mi(i=0，1，2，2n-1)表示这一项一般，n个变元的极大项是：P1 P2 PnM0P1 P2 Pn-1 Pn M1P1 P2 Pn-1 PnM2P1 P2 Pn 21nM1.5 范式和判定问题n定义1.13 一个由极大项的积组成的公式，如果与命题公式A等价，则称它是A的主合取范式。

34、对任何命题公式(永真式除外)都可求得与其等价的主合取范式，且主合取范式的形式唯一。例如：A PQR (PR)(QR) (PR)(QQ)(QR)(PP) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) M0M2M4 (0，2，4)其中，符号“”是借用数学中求积的符号，这里代表合取。从A的主合取范式，我们立刻可以判断出A是可满足的。主合取范式 命题和联结词主要内容合式公式与真值表永真式和等价式对偶式与蕴涵式范式和判定问题命题演算的推理理论1.6 命题演算的推理理论逻辑学的主要任务是提供一套推论规则，按照公认的推论规则，从前提集合中推导出一个结论来，这样的推导过程称为演绎或

35、形式证明。在任何论证中，倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推论规则，则认为此结论是真的，并且认为这个论证过程是合法的。也就是说，对于任何论证来说，人们所注意的是论证的合法性。数理逻辑则把注意力集中于推论规则的研究，依据这些推论规则推导出的任何结论，称为有效结论，而这种论证规则被称为有效论证。数理逻辑所关心的是论证的有效性而不是合法性，也就是说数理逻辑所注重的是推论过程中推论规则使用的有效，而并不关心前提的实际真值。推论理论对计算机科学中的程序验证、定理的机械证明和人工智能都十分重要。 1.6 命题演算的推理理论n定义1.14 设H1 ，H2 , Hm +, C是一些命题公式

36、。当且仅当H1H2Hm C，则说C是前提集合H1，H2，Hm的有效结论。显然，给定一个前提集合和一个结论，用构成真值表的方法，在有限步内能够确定该结论是否是该前提集合的有效结论。这种方法被称为真值表技术。 1.6 命题演算的推理理论n规则P：引入一个前提称为使用一次P规则。n规则T：在推导中，如果前面有一个或多个公式永真蕴涵公式S，则可以把公式S引进推导过程中。换句话说，引进前面推导过程中的推论结果称为使用T规则。 n规则CP：如果能从R和前提集合中推导出S来，则就能够从前提集合中推导出RS。实际上恒等式E28就可以推出规则CP。(PQR) (PQ) R PQR P(QR) P(QR) P(QR)设P表示前提的合取，Q是任意公式，则上述恒等式可表述成：在前提集合中若包含有附加前提Q，并且从PQ中可以推导出R来，则可从前提P中推导出QR来。 1.6 命题演算的推理理论n例1.19 试证明P是(PQ)，QR，R的有效结论。解：1 (1) (PQ) P规则1 (2) PQ T 规则 (1)和E111 (3) PQ T规则(2)和E274 (4) QR P规则4 (5) QR T规则 (4)和E271,4 (6) PR T,