第01章 命题逻辑.ppt

逻辑学：是研究推理的一门学科。数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。数理逻辑的内容丰富逻辑演算、证明论、公理化集合论、递归函数论、模型论基础:命题逻辑、谓词逻辑,第一章命题逻辑,命题逻辑,也称命题演算,它与谓词逻辑构成数理逻辑的基础,而命题逻辑又是谓词逻辑的基础数理逻辑是用数学方法(通过引入表意符号)研究推理的学科。因此,数理逻辑又名为符号逻辑。(一套符号体系+一组推理规则)命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。,第一章命题逻辑,1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集*1.5对偶与范式1.6推理理论1.7例题分析,1.1命题符号化及联结词,一、什么是命题定义：命题是能判断真假的陈述句。该定义有2层含义:(1)命题是一个陈述句;(2)命题具有真假值。命题仅有两种可能的真值:真、假,且二者只居其一。真用1或T表示,假用0或F表示。二值逻辑,命题是具有唯一真值的陈述句,判断给定句子是否为命题,应该分两步：首先判定它是否为陈述句,其次判断它的真值是否唯一。例1.1判断下例句子是否为命题。(1)2是素数。(2)雪是黑色的。(3)1+101=110(4)十是整数。(5)向右看齐！(6)今天是十五号。(7)这朵花多美啊！(8)我们这里四季如春。(9)x+y5(10)你是谁？(11)明年十月一日是晴天。(12)地球外的星球上也有人。,定义：由简单陈述句(一套主谓结构)构成的命题称为简单命题或原子命题。由若干个简单命题用联结词联结而成的命题是复合命题。如果一陈述句再也不能分解成更为简单的陈述句,由它构成的命题称为简单命题。简单命题是命题逻辑的基本单位。,二、简单命题与复合命题,三、命题符号化,(1)简单命题用英文字母P,Q,R或带下标的Pi,Qi,Ri,表示。P:2是素数。Q:雪是黑的。将表示命题的符号命题标识符放在该命题前面,称为命题符号化。(2)命题的真值也符号化:用T或1表示“真”;用F或0表示“假”。(3)命题中的联结词也符号化:、。,四、命题常量与命题变元,简单命题可用命题标识符表示。表示命题的符号有双重作用:(1)如果命题标识符表示确定的命题(真值确定)命题常元;(2)如果命题标识符只表示任意命题的位置标志,即可表示任意命题(真值不确定)命题变元。注:命题变元不是命题,只有用一个特定命题取代时,才能确定其真值,才变为命题即对命题变元进行真值指派后变为命题。,五、联结词,例1.2复合命题示例1.上海不是小城镇。2.他既在学习又在工作。3.林芳学过英语或日语。4.如果他病了,那么他就需要休息。5.三角形是等腰三角形,当且仅当三角形的两个底角相等。,(一)否定()定义1.1设P为任一命题,复合命题“非P”(或P的否定)称为P否定式。记作P。为否定联结词。P为真,当且仅当P为假;P是假,当且仅当P为真。否定联结词的定义可由表1-1表示之。,由于“否定”修改了命题,它是对单个命题进行操作,称它为一元联结词。,(二)合取()定义1.2设P、Q为两个命题,复合命题“P并且Q”(或P与Q)称作P与Q的合取式,记作:PQ。称为合取联结词。PQ为真当且仅当P和Q同为真,否则PQ为假。合取联结词的定义由表1-2表示之。,“合取”是一个二元运算。,例1.3：将下列命题符号化。(1)李平既聪明又用功。(2)李平虽然聪明,但不用功。(3)李平不但聪明,而且用功。(4)李平不是不聪明,而是不用功。(5)张辉和王丽都是三好学生。(6)张辉和王丽是同学。解：命题符号化:P:李平聪明。Q:李平用功。R:张辉是三好学生。S:王丽是三好学生。T:张辉和王丽是同学。选用合适的联结词将命题符号化：(1)PQ(2)PQ(3)PQ(4)(P)Q(5)RS(6)T,(三)析取()定义1.3设P和Q为两个命题,复合命题“P或Q”称作P与Q的析取式,记作:PQ,为析取联结词。PQ的为假当且仅当P与Q同为假,否则PQ为真。析取联结词的定义由表1-3表示之。,“析取”是一个二元运算。,例：将下列命题符号化。1.王燕学过英语或日语。(可兼或)P:王燕学过英语。Q:王燕学过日语。则:PQ2.他昨天做了20题或30题。“或”只表示了习题的近似数目,是原子命题。不能用“”表示。P:他昨天做了20题或30题。3.我在教室看书或在图书馆看书。排斥或/异或“”表示。P:我在教室看书。Q:我在图书馆看书。则:PQPQ=(PQ)(PQ)=(PQ)(PQ),(四)蕴涵()定义1.4设P和Q为两个命题,复合命题“如果P,则Q”称作P和Q的蕴涵式,记作:PQ,称为蕴涵联结词。当P的真值为真,而Q的真值为假时,命题PQ的真值为假;否则,PQ的真值为真。蕴涵联结词的定义由表1-4表示之。,注:在条件命题PQ中,命题P称为PQ的前件或前提,命题Q称为PQ的后件或结论。条件命题PQ有多种方式陈述：(1)“如果P,则Q”;(2)“P是Q的充分条件”;(3)“Q是P的必要条件”;(4)“P仅当Q”;(5)“只有Q才P”;。,例：将下列命题符号化。1.如果我拿到奖学金,我就请客。P:我拿到奖学金。Q:我请客。PQ2.如果他努力学习,就会门门功课优秀。P:他努力学习。Q:他门门功课优秀。PQ3.只要不下雨,我就骑自行车上班。P:天下雨。Q:我骑自行车上班。PQ4.只有不下雨,我才骑自行车上班。P:天下雨。Q:我骑自行车上班。QP,注意：在使用联结词时,要特别注意以下几点:1.在自然语言里,特别在数学中,Q是P的必要条件有多种不同的叙述方式。如:“只要P,就Q”,“因为P,所以Q”,“P仅当Q”,“只有Q才P”,“除非Q才P”,“除非Q,否则非P”。各种叙述方式表面看来有所不同,但都表达的是Q是P的必要条件,故联结词均符号化为,均符号化为PQ。2.在自然语言中,“如果P,则Q”中的前件P与后件Q往往具有某种内在联系。而在数理逻辑中,P与Q可以无任何内在联系。3.在数学或其它自然科学中,“如果P,则Q”往往表达的是前件P为真,后件Q也为真的推理关系。但在数理逻辑中,作为一种规定,当P为假时,无论Q是真是假,PQ均为真。即:“只有P为真Q为假”使得复合命题PQ为假。,(五)双条件()定义1.5令P、Q是两个命题,复合命题“P当且仅当Q”称作P与Q的等价式,记作PQ。称为等价联结词。当P和Q的真值相同时,PQ的真值为真;否则PQ的真值为假。等价联结词的定义由表1-5表示之。,以上定义了五种最基本、最常用、也是最重要的联结词:、,将它们组成一个集合,称为一个联结词集。其中为一元联结词,其余的都是二元联结词。使用这些联结词有什么好处呢？,可以将复杂命题表示成简单的符号公式。,把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式,称为命题的符号化。符号化应该注意下列事项:确定给定句子是否为命题。句子中连词是否为命题联结词。要正确地表示原子命题和选择适当命题联结词。,命题的符号化,命题符号化是很重要的,一定要掌握好。在命题推理中常常最先遇到的就是符号化这个问题,解决不好,等于说推理的首要前提没有了。,在本节结束时,应强调指出的是:复合命题的真值只取决于各原子命题的真值,而与它们的内容、含义无关,与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的,请认真领会。,1.2命题公式及分类,一、命题公式(合式公式)通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构,因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式,以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。,定义1.6命题演算的合式公式(Well-formedformula_WFF)是由下列规则所产生的符号串:(1)单个命题常量、变元是一个WFF;(2)如果A是WFF,则(A)是WFF;(3)如果A、B是WFF,则(AB)、(AB)、(AB)和(AB)都是WFF;(4)只有有限次地使用规则(1)(3)得到的符号串才是合式公式WFF。,一、命题公式(合式公式),当合式公式比较复杂时,常常使用很多圆括号。为了减少圆括号的使用量,可作以下约定:规定联结词的优先级由高到低的次序为:、相同的联结词按从左至右次序计算时,圆括号可省略。最外层的圆括号可以省略。合式公式也简称公式。,二、命题公式的层次,定义1.7(1)若A是单个命题(常项或变项),则称A是0层公式;(2)称A是n+1(n0)层公式是指A符合下列情况之一:A=B,B是n层公式;A=BC,其中B、C分别为i层和j层公式,n=max(i,j)A=BC,其中B、C的层次同;A=BC,其中B、C的层次同;A=BC,其中B、C的层次同。,三、命题公式的解释(赋值),定义1.8设A为命题公式,P1,P2,Pn为出现在A中的所有命题变元。给Pi(i=1,2,n)指定一组真值,称为对公式A的一个真值指派(也称解释或赋值),记作I。(1)若指定的一组真值使公式A为真,则称这组真值为A的成真赋值；(2)若指定的一组真值使公式A为假,则称这组真值为A的成假赋值。,例：设命题公式A=PQR：在解释I1=(0,0,0)下,A为真,则I1为A的成真赋值;在解释I2=(1,1,0)下,A为假,则I2为A的成假赋值。一个命题公式中含有n个命题变元,则共有2n组不同的赋值。,四、真值表,定义:在命题公式中,把所有命题变元在所有可能的解释(赋值)下取得的真值汇列成的表格称为真值表。构造真值表的步骤如下:(1)找出公式中所含的全部命题变元(如有n个),列出2n个赋值;(2)按从低到高的顺序写出各层次的子公式;(3)对应各个赋值,计算出各层次的真值,直到最后计算出命题公式的真值。,例:下列公式的真值表,并求成真赋值和成假赋值。(1)(PQ)R(2)(PP)(QQ)(3)(PQ)QR,定义1.9设A为命题公式,则若A在它的各种赋值下取值均为真,则称A为永真式或重言式。若A在它的各种赋值下取值均为假,则称A为永假式或矛盾式。若A至少存在一组赋值是成真赋值,则称A为可满足式。,五、命题公式的分类,判定给定公式是否为永真式、永假式或可满足式的问题,称为命题公式的判定问题。真值表可用来判断公式的类型：1.若真值表最后一列全为1,则公式为永真式。2.若真值表最后一列全为0,则公式为永假式。3.若真值表最后一列中至少有一个1,则公式为可满足式。,注:由定义可知,永真式一定是可满足式,但反之不真。重点将研究重言式,它最有用,因为它有以下特点:重言式的否定是矛盾式,矛盾式的否定是重言式,这样只研究其一就可以了。两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是,由简单的重言式可构造出复杂的重言式。由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,一、等价公式定义1.10设A、B是两个命题公式,若AB是永真式(即A、B在任意指派下,真值均相同),则称A和B是等价的,记作AB。显然,若公式A和B的真值表是相同的,则A和B等价。因此,验证两公式是否等价,只需做出它们的真值表即可。,1.3等值演算,注意：和的区别与联系。区别：是逻辑联结词,属于目标语言中的符号,它出现在命题公式中;不是逻辑联结词,用于表示两个命题公式的一种关系,不属于这两个公式的任何一个公式中的符号。联系：可用下面定理表明之。,定理：设A和B是两个命题公式,AB当且仅当AB是永真式。证明：(充分性)若AB是永真式,则其原子命题不论在何种解释下,AB均为真;按照AB的真值表,只有当A、B具有相同的真值时,才有ABT于是,无论什么情况都有AB。(必要性)如果AB,即A、B在任意解释下都具有相同的真值,故必有AB恒为T,即AB是永真式。#,等价式具有下列性质：自反性:即对任意公式A,有AA。对称性:即对任意公式A和B,若AB,则BA。传递性:即对任意公式A、B和C,若AB、BC,则AC。,在判定公式之间是否等价,有一些简单而又经常使用的等价式,称为基本等价式或称命题定律。牢固记住并能熟练运用,是学好数理逻辑的关键之一。24个重要的等值式：(1)双重否定律：AA(2)等幂律：AAA,AAA(3)结合律：(AB)CA(BC),(AB)CA(BC),二、基本等价式命题定律,(4)交换律：ABBA,ABBAABBA(5)分配律：A(BC)(AB)(AC)A(BC)(AB)(AC)(6)吸收律：A(AB)A,A(AB)A(7)德摩根律：(AB)AB(AB)AB(8)同一律：A1A,A0A。(9)零律：A00,A11。,(10)补余律：AA0(矛盾律)AA1(排中律)(11)蕴含等值式：ABAB,(12)假言易位：ABBA。(13)等价等值式：AB(AB)(BA)(AB)(AB)(14)等价否定律：ABAB(15)归谬论：(AB)(AB)A。,以上15组等值式包含了24个重要等值式。由于A、B、C可代表任意的公式,因而每个公式都是一个模式(称之为等值式模式)。每个等值式模式都给出了无穷多个同类型的具体的等值式。,三、代入规则和置换规则,例如,在蕴含等值式(ABAB)中,当取A=PQR,B=PQ时,得等值式为：(PQR)(PQ)(PQR)(PQ)所得的等值式称为原来的等值式模式的代换实例。每个具体的代换实例的正确性都可用真值表证明之。定理:在一个永真式A中,任何一个原子命题变元R出现的每一处,用另一个公式代入,所得公式B仍是永真式。(代入规则),定义如果X是合式公式A的一部分,且X本身也是一个合式公式,则称X为公式A的子公式。定理1.1设A1是合式公式A的子公式,若A1B1,并且将A中的A1用B1替换得到公式B,则AB。称该定理为置换规则。例:在公式(PQ)R中,可用蕴含等值式依次置换,得:(PQ)R(PQ)R(PQ)R(PQ)R(PR)(QR),注：代入和置换有两点区别：代入是对原子命题变元而言的,而置换可对命题公式实行。代入必须是处处代入,置换则可部分替换,亦可全部替换。,我们已经给出了:1.重言式(永真式)的代换实例为重言式(永真式)。2.重言式(永真式)的否定为矛盾式(永假式)。3.两重言式(永真式)的合取式、析取式、条件式和双条件式等都仍是重言式(永真式)。于是,由简单的重言式可构造出复杂的重言式。,虽然用真值表法可以判断任何两个命题公式是否等值,但当命题变元较多时,工作量是很大的。前面我们已经介绍了15组24个重要的等值式和代入规则、置换规则,利用它们就可以通过等值演算来判断两个命题公式是否等价。,四、等值演算,例:用等值演算判断下列公式的类型：(1)(PQ)PQ(2)(P(PQ)R(3)P(PQ)P)Q),(1)(PQ)PQ(PQ)PQ(蕴含等值式)(PQ)P)Q(蕴含等值式)(PQ)P)Q(德摩根律)(PQ)P)Q(德摩根律、双重否定律)(PP)(QP)Q(分配律)(1(QP)Q(排中律)(QQ)P(交换律、结合律)1P(零律)1最后结果说明(1)中公式是重言式,(2)(P(PQ)R(PPQ)R(蕴含等值式)(PPQ)R(德摩根律)0R(矛盾律、零律)0(零律)最后结果说明(2)中公式是矛盾式。,(3)P(PQ)P)Q)P(PQ)P)Q)(蕴含等值式)P(PP)(QP)Q)(分配律)P(0(QP)Q)(矛盾律、零律)P(QPQ)(德摩根律)P1(排中律)P(同一律)最后结果说明(3)中公式是可满足式。,例:验证下列等值式：(1)P(QR)(PQ)R(2)P(PQ)(PQ),等值演算还能帮助人们解决工作和生活中的判断问题。例:在某次研讨会的中间休息时间,3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说:王教授不是苏州人,是上海人。乙说:王教授不是上海人,是苏州人。丙说:王教授既不是上海人,也不是杭州人。听完以上3人的判断后,王教授笑着说,他们3人中有一人说的全对,有一人说对了一半,另一人说的全不对。试用命题演算法分析王教授到底是哪里人？,解:设命题：P:王教授是苏州人。Q:王教授是上海人。R:王教授是杭州人。P,Q,R中必有一个真命题,两个假命题,要通过命题演算将真命题找出来。,设：甲的判断为:A1=PQ乙的判断为:A2=PQ丙的判断为:A3=QR则有：甲的判断全对为:B1=A1=PQ甲的判断对一半为:B2=(PQ)(PQ)甲的判断全错为:B3=PQ乙的判断全对为:C1=A2=PQ乙的判断对一半为:C2=(PQ)(PQ)乙的判断全错为:C3=PQ丙的判断全对为:D1=A3=QR丙的判断对一半为:D2=(QR)(QR)丙甲的判断全错为:D3=QR,由王教授所说“甲、乙、丙3人中有一人说的全对,有一人说对了一半,另一人说的全不对”,得出公式E：E=(B1C2D3)(B1C3D2)(B2C1D3)(B2C3D1)(B2C1D2)(B3C2D1)为真命题。其中：B1C2D3=(PQ)(PQ)(PQ)(QR)(PQQR)(PQPR)0B1C3D2=(PQ)(PQ)(QR)(QR)(PQR)(PQQR)PQRB2C1D3=(PQ)(PQ)(PQ)(QR)(PQPQQR)(PQQR)0,类似地可得：B2C3D10B3C1D2PQRB3C2D10于是,由同一律可知E(PQR)(PQR)但因为王教授不能既是上海人,又是杭州人,因而P,R必有一个假命题,即PQR0,于是EPQR为真命题,因而必有P,R为假命题,Q为真命题,即王教授是上海人。甲说的全对,丙说对了一半,而乙全说错了。,1.5对偶与范式,要求：掌握对偶与范式,会求命题公式的主析取范式、主合取范式。重点与难点：求命题公式的主析(合)取范式。,1.5对偶与范式,一、对偶在前面介绍的命题定律中,多数公式是成对出现的,这些成对出现的定律就是对偶性质的反映,即对偶式。利用对偶式的命题定律,可以扩大等价式的个数,也可减少证明的次数。,定义1.17在仅含联结词、和的命题公式A中,若把和互换,0和1互换而得到一个命题公式A*,则称A*为A的对偶式。显然,A也是A*的对偶式。即A与A*互为对偶式。且有:(A*)*=A,一、对偶,定理1.2(对偶定理)设A和A*互为对偶式,P1,P2,Pn是出现A和A*中的原子命题变元,则A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)表明,公式A的否定等价于其命题变元否定的对偶式A*;表明,公式A的命题变元否定等价于对偶式A*之否定。,定理1.3(对偶原理)设A和B为两个命题公式,若AB,则A*B*。若A为永真式,则A*必为永假式有了等价式、代入规则、置换规则和对偶定理,便可以得到更多的永真式,证明更多的等价式,使化简命题公式更为方便。,1、简单合取式与简单析取式定义1.18在一公式中,仅由命题变元及或否定构成的析取式,称该公式为简单析取式,仅由命题变元或其否定构成的合取式,称该公式为简单合取式。,二、范式,例如:公式P,Q,PQ和PQP等都是简单合取式,而P,Q和P为相应的简单合取式的合取项；公式P,Q,PQ,PQP等都是简单析取式,而P,Q和P为相应简单析取式的析取项。注意：一个命题变元或其否定既可以是简单合取式,也可是简单析取式,如例中P,Q等。,由定义不难看出：(1)简单析取式为永真式,当且仅当它同时含有某个命题变元及其否定;(2)一个简单合取式为永假式的充要条件是:简单合取式同时含有某个命题变元及其否定。,、析取范式与合取范式,定义1.19(1)一个命题公式A称为析取范式,当且仅当A可表为简单合取式的析取,即：AA1A2A3An其中：Ai为简单合取式(1in)。(2)一个命题公式A称为合取范式,当且仅当A可表为简单析取式的合取,即：AA1A2A3An其中：Ai为简单析取式(1in)。,3、范式的性质,(1)一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式。(2)一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式。给定任何命题公式,都能求出与之等值的析取范式与合取范式。,定理1.4(范式存在定理)任一命题公式都存在着与之等价的析取范式和合取范式。证明:首先,我们观察到在范式中不能出现联结词与。由蕴涵等值式与等价等值式可知ABABAB(AB)(AB)因而在等价的条件下,可消去任何公式中的联结词和。,其次,在范式中不能出现如下形式的公式：A,(AB),(AB)可利用双重否定律和德摩根律,即得AA(AB)AB(AB)AB,再次,在析取范式中不出现如下形式的公式：A(BC)在合取范式中不出现如下形式的公式：A(BC)利用对(或对)分配律,可得A(BC)(AB)(AC)A(BC)(AB)(AC)由此三步,即可将任一公式化成与之等价的析取范式或合取范式。,根据范式存在定理,求范式可使用如下步骤：使用命题定律,消去联结词、；使用双重否定律和德摩根律,将公式中出现的联结词都内移到命题变元之前；利用结合律、分配律等将公式化成析取范式或合取范式。(利用对的分配律求析取范式,对的分配律求合取范式。),例：求公式(PQ)R的析取范式与合取范式：解：(1)求合取范式(PQ)R(PQ)R(消去)(PQ)R)(R(PQ)(消去)(PQ)R)(RPQ)(消去)(PQ)R)(PQR)(否定内移)(PR)(QR)(PQR)(对分配律),(2)求析取范式求析取范式与求合取范式的前两步是相同的,只是在利用分配律时有所不同。(PQ)R(PQ)R)(PQR)(PQP)(PQQ)(PQR)(RP)(RQ)(RR)(PQR)(PR)(QR)与命题公式等值的析(合)取范式不唯一。,范式基本解决了公式的判定问题。但由于范式的不唯一,对识别公式间是否等价带来一定困难,而公式的主范式解决了这个问题。下面将分别讨论主范式:主析取范式和主合取范式。,三、主范式,1.极大项和极小项,定义1.22在含有n个命题变元的简单合取式(简单析取式)中,若每个命题变元与它的否定式不同时出现,而二者之一必出现一次且仅出现一次,则称该简单合取式(简单析取式)为极小项(极大项)。由于每个命题变元在极小项(极大项)中以原形或否定式形式出现且仅出现一次,因而n个命题变元共可产生2n个不同的极小项(极大项)。,其中,每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数i,就将所对应极小项记作mi。类似地,每个极大项只有一个成假赋值,将其对应的十进制数i做极大项的角标,记作Mi。,两个命题变元P、Q构成的极小项、极大项：,三个命题变元P、Q、R构成的极小项、极大项：,(1)任意两个不同的小项的合取式是永假的：mimj(ij)。(2)所有极小项之析取式为永真：mi。(3)每个极小项只有一个解释为真,且其真值1位于主对角线上。,极小项有如下性质：,极小项与极大项的关系：,定理：设mi与Mi是命题变项P1,P2,Pn形成的极小项和极大项,则：miMi,Mimi。,2.主析(合)取范式,定义1.23设命题公式A中含n个命题变元,如果A的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项),则称该析取范式(合取范式)为主析取范式(主合取范式)。,任何命题公式都存在着与之等价的主析取范式和主合取范式,并且是唯一的。证:这里只证主析取范式的存在和唯一性。(1)证明存在性。设A是任一含n个命题变元的公式。由范式存在定理可知,存在与A等价的析取范式A,即AA,若A的某个简单合取式Ai中既不含命题变元Pj,也不含它的否定式Pj,则将Ai展成如下形式：AiAi1Ai(PjPj)(AiPj)(AiPj)继续这一过程,直到所有的简单合取式都含任意命题变项或它的否定式。(极小项),定理:(主范式的唯一性),若在演算过程中重复出现的命题变元、极小项和矛盾式时,都应“消去”:比如用P代替PP,mi代替mimi,0代替矛盾式等。最后,就将A化成与之等值的主析取范式A”。(2)证明唯一性。假设某一命题公式A存在两个与之等价的主析取范式B和C,即AB且AC,则BC。由于B和C是不同的主析取范式,不妨设极小项mi只出现在B中而不出现在C中。于是,角标i的二进制表示为B的成真赋值,而为C的成假赋值。这与BC矛盾,因而B与C必相同。主合取范式的存在唯一性可类似证明。,例:求公式(PQ)R的主析取范式与主合取范式;解:(1)求主析取范式在前面的例子中已求出该公式的析取范式,即(PQ)R(PQR)(PR)(QR)其中:(PR)、(QR)都不是极小项。(PR)P(QQ)R(PQR)(PQR)m1m3QR(PP)QR(PQR)(PQR)m3m7(PQR)m4(PQ)Rm1m3m4m7,(2)求主合取范式在前面的例子中已求出该公式的合取范式,即(PQ)R(PR)(QR)(PQR)其中：(PR)、(QR)都不是极大项。(PR)P(QQ)R(PQR)(PQR)M0M2(QR)(PP)QR(PQR)(PQR)M2M6(PQR)M5(PQ)RM0M2M5M6,由于主范式是由极小项或极大项构成,从极小项和极大项的定义,可知两者有下列关系：miMiMimi因此,主析取范式和主合取范式有着“互补”关系,即是由给定公式的主析取范式可以求出其主合取范式。,3.主范式之间的关系,设命题公式A中含有n个命题变元,且A的主析取范式中含有k个极小项,则A的主析取范式中必含有2n-k个极小项,不妨设为,即A。于是AA(),由此可知,从A的主析取范式求其主合取范式的步骤为：(a)求出A的主析取范式中没有包含的极小项。(b)求出与(a)中极小项的下标相同的极大项。(c)做(b)中极大项之合取,即为A的主合取范式。例：(PQ)Q(PQ)Q(PQ)Qm1m3(1,3)则(PQ)QM0M2(0,2),利用主范式可以求解判定问题或者证明等价式成立。(1)求公式的成真赋值与成假赋值(2)判断公式的类型根据主范式的定义和定理,也可以判定含n个命题变元的公式,其关键是先求出给定公式的主范式;其次按下列条件判定之：(a)若A,或A可化为与其等价的、含2n个极小项的主析取范式,则A为永真式。,4.主范式的用途,(b)若A,或A可化为与其等价的、含2n个极大项的主合取范式,则A为永假式。(c)若A不与或等价,且又不含2n个极小项或者极大项,则A为可满足的。例:利用公式的主范式判断公式的类型;(PQ)QP(PQ)(PQ)R,(3)判断两个命题公式是否等价由于任一公式的主范式是唯一的,所以将给定的公式求出其主范式,若主范式相同,则给定两公式是等价的。例:判断下面两组公式是否等价;P与(PQ)(PQ)(PQ)R与(PQ)R,(4)应用主范式分析和解决实际问题例:某科研所要从3名科研骨干A,B,C中挑选12名出国进修。由于工作原因,选派时要满足以下条件：(1)若A去,则C同去。(2)若B去,则C不能去。(3)若C不去,则A或B可以去。问应如何选派他们去？解：设P:派A去。Q:派B去。R:派C去。则有:(PR)(QR)(R(PQ)m1m2m5由于m1=PQR,m2=PQR,m5=PQR可知,选派方案有3种：(a)C去,而A,B都不去。(b)B去,而A,C都不去。(c)A,C去,而B不去。,1.6推理理论,要求:能够熟练地进行命题逻辑的推理重点:有效结论的概念,有效结论的推演难点:利用推理规则,已知的等价式、蕴含式推演得到有效结论。,在数学和其它自然科学中,经常要考虑从某些前提A1,A2,An能够推导出什么结论。例如：从分子学说,原子学说,能够得到什么结论,从光的波动学说,能得到什么结论。我们一般地要对“假设”的内容作深入分析,并推究其间的关系,从而得到结论。但也有一些推理,只需分析假设中的真值和联结词,便可获得结论。,1.6推理理论,在数理逻辑中,集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理,这些规则有关的理论称为推理理论。在实际应用的推理中,我们常常把本门学科的一些定律、定理和条件,作为假设前提,尽管这些前提在数理逻辑中实非永真,但在推理过程中,却总是假设这些命题为T,并使用一些公认的规则,得到另外的命题,形成结论,这种过程就是论证。注意区分：有效结论和结论的真实性,1.6推理理论,一、有效推理数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构,为此,首先应该明确什么样的推理是有效的或正确的。,定义1.24设H1,H2,Hn,C都是命题公式,若对于H1,H2,Hn和C中出现的命题变元的任意一组赋值,或者H1H2Hn为假,或者当H1H2Hn为真时,C也为真,则称由前提H1,H2,Hn推出C的推理是有效的或正确的,并称C是有效结论。,关于定义1.24还需要做以下几点说明：1.由前提H1,H2,Hn推出结论C是否正确与诸前提的排列次序无关。2.设H1,H2,Hn,C中共出现n个命题变元,对于任何一组赋值,前提和结论的取值情况有以下四种：(1)H1H2Hn为0,C为0。(2)H1H2Hn为0,C为1。(3)H1H2Hn为1,C为0。(4)H1H2Hn为1,C为1。只要不出现(3)中的情况,推理就是正确的。3.推理正确,并不能保证结论C一定为真,这与数学中的推理是不同的。,定理命题公式H1,H2,Hn推出C的推理是正确,当且仅当(H1H2Hn)C为重言式。证：(1)必要性。若H1,H2,Hn推出C的推理是正确,则对于H1,H2,Hn,C中所含命题变元的任意一组赋值,不会出现H1H2Hn为真,而C为假的情况,因而在任何赋值下,蕴涵式(H1H2Hn)C均为真,故它为重言式。,二、有效推理的等价定理,(2)充分性。若蕴涵式(H1H2Hn)C为重言式,则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件为假的情况,即在任何赋值下,或者H1H2Hn为假,或者H1H2Hn和C同时为真,这正符合定义1.24中推理正确的定义。,由此定理知,推理形式为：前提：H1,H2,Hn结论：C是有效的当且仅当(H1H2Hn)C为重言式。(H1H2Hn)C称为上述推理的形式结构。从而推理的有效性等价于它的形式结构为永真式。于是,推理正确H1H2HnC(重言蕴涵式),例：判断下面推理是否正确：(1)若a能被4整除,则a能被2整除；a能被4整除。所以a能被2整除。(2)若a能被4整除,则a能被2整除；a能被2整除。所以a能被4整除。(3)下午马芳或去看电影或去游泳；她没有看电影。所以,她去游泳了。(4)若下午气温超过30,则王小燕必去游泳；若她去游泳,她就不去看电影了。所以王小燕没有去看电影,下午气温必超过了30。,推理也称论证,它是指由已知命题得到新的命题的思维过程,其中已知命题称为推理的前提或假设,推得的新命题称为推理的结论。在数理逻辑中,前提H是一个或者n个命题公式H1,H2,Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,HnC,其中符号表示推出。可见,推理形式是命题公式的一个有限序列,它的最后一个公式是结论,余下的为前提或假设。,三、推理规则,在数理逻辑中,从前提推导出结论,要依据事先提供的公认的推理规则,它们是：(1)规则(前提引入规则)：在推理过程的任何步骤上都可以引入前提。(2)规则(结论引入规则)：在推理过程中,前面已导出的有效结论都可作为后续推导的前提引入。(3)置换规则：在推理过程的任何步骤上,命题公式中的子公式都可用与之等价的公式置换。,此外,在从前提推出的结论为条件式时,还需要下面规则：(4)CP规则(附加前提引入规则)：若推出有效结论为条件式RC时,只需将其前件R加入到前提中作为附加前提且再去推出后件C即可。CP规则的正确性可由下面定理得到保证：定理若H1,H2,Hn,RC,则H1,H2,HnRC。,四、推理定律,在推理过程中,除使用推理规则外,还需要使用许多条推理定律。这些定律可由以前讲过的命题定律、永真蕴涵式及运用定理而得到。(1)PQP,PQQ化简(2)PPQ,QPQ附加(3)PPQ,QPQ附加(4)(PQ)P,(PQ)Q化简(5)P,QPQ合取引入(6)P(PQ)Q假言推理(7)(PQ)QP拒取式,(8)P(PQ)Q析取三段论(9)(PQ)(QR)PR假言三段论(10)(PQ)(QR)PR等价三段论(11)(PQ)(RS)(PR)QS构造性二难(12)PQ(PR)(QR)PQ(PR)(QR)由于推理定律是确定有效结论的不可缺少的重要根据,因此要牢记并熟练运用它们。,判断有效结论的常用方法有真值表法,演绎法和间接证法。下面分别讨论之。1.真值表法根据给定前提H1,H2,Hn和结论C,构造条件式(H1H2Hn)C的真值表,若它为永真式,则结论C是有效的。,五、判断有效结论的常用方法,列出待证推理形式中前提和结论的真值表,原则上可以解决推理的有效性问题。但当出现在公式中的命题变元数目很大时,真值表法又显得不太实用,而使用演绎法却能比较好地解决这个问题。,2.演绎法,定义:从前提H推出结论C的一个演绎是构造命题公式的一个有限序列：A1,A2,An其中,A1是前提H中的某个前提Hi；Ai(i2)或者是H中某个前提Hi,或者