第1章 数理逻辑-命题逻辑.ppt

第一章数理逻辑MathematicsLogic,数理逻辑,逻辑学研究人的思维形式和规律的科学根据研究的对象和方法形式逻辑辩证逻辑数理逻辑用数学方法研究推理的规律和形式的科学推理：由一个或几个判断推出一个新判断的思维形式数学方法建立一套表意符号体系，对具体事物进行抽象的形式研究方法又称符号逻辑两种演算命题逻辑谓词逻辑,形式语言与自然语言,数理逻辑需建立一套表意符号体系形式语言符号体系自然语言二义性Doubleclickthemouse,thenitllrun.小王现在不方便接电话，他方便去了建立形式语言符号体系的目的消除二义性,主要内容,1.1命题1.2重言式1.3范式1.4联结词的扩充与归约1.5推理规则和证明方法1.6谓词和量词1.7谓词演算的永真公式1.8谓词演算的推理规则,1.11.5命题逻辑PropositionLogic,1.1命题（Proposition）,1.1.1命题断言一个陈述语句命题命题是一个非真即假(不可兼)的断言如果命题是真命题的真值（TruthValues）为真真命题大写字母“T”(1)表示如果命题是假命题的真值是假假命题大写字母“F”(0)表示,例1:,今天下雪3+3=62是偶数而3是奇数1+101=110明年的今天会下雨较大的偶数都可表为两个质数之和,例2:,x+y4真好啊!x=3你去哪里?0*x=0我正在说谎,原子命题(Primitiveproposition)由简单陈述句表示的判断命题逻辑规定：原子命题是不可再分的命题的表示常用大写英文字母（或带下标）表示P表示“雪是白的”Q表示“北京是中国的首都”命题变元（命题词）P表示任一命题时，P就称为命题变元（命题词）命题词不是命题命题指具体的陈述句，是有确定的真值命题变元的真值不定，只当将某个具体命题代入命题变元时，命题变元化为命题，方可确定其真值,复合命题(Compoundproposition)一个或几个简单命题用联结词联结所构成的命题例：“张三学英语和李四学日语”两个特殊的命题词命题常量T：永远表示真命题F：永远表示假命题T和F的两种含义命题常量命题的真值,数理逻辑不关心内容具体的陈述句的真值究竟为什么或在什么环境下是真还是假数理逻辑只关心形式命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系,1.1.2命题联结词,命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复合命题例：P:明天下雪,Q:明天下雨“明天不下雪”“非P”“明天下雪并且明天下雨”“P并且Q”“明天下雪或者明天下雨”“P或Q”,真值表（TruthTable),与自然语言中的“不”，“否”，“非”，“没有”，“未必”等类似,1.否定词（，negation）,设P表示命题,那么“P不真”是另一命题,表示为P,叫做P的否定,读做“非P”。如果P是假,则P是真,反之亦然。,例4,(a)P:4是质数。P:4不是质数。(b)Q:这些都是男同学。Q:这些不都是男同学。,例5P:王华的成绩很好Q:王华的品德很好PQ:王华的成绩很好并且品德很好。,2.合取词(Conjunction),如果P和Q是命题,那么“P并且Q”也是一命题,记为PQ,称为P和Q的合取,读做“P与Q”或“P并且Q”。,3.析取词(disjunction),如果P和Q是命题,则“P或Q”也是一命题,记作PQ,称为P和Q的析取,读做“P或Q”。,可兼或,排斥或,X,（RS）（RS）,（RS）（RS）,例6,(a)今晚我写字或看书P:今晚我写字,Q:今晚我看书。PQ(b)选小王或小李当班长R:选小王当班长，S:选小李当班长RS？,与自然语言中的“如果则”，“如果那么”，“只要就”等类似,4.条件词(蕴涵，蕴含，implication),如果P和Q是命题,那么“P蕴含Q”也是命题,记为PQ,称为蕴含式,读做“如果P,那么Q”或“P则Q”。运算对象P叫做前提,假设或前件,而Q叫做结论或后件。,例7,(a)P:天不下雨,Q:草木枯黄。PQ:如果天不下雨,那么草木枯黄。(b)R:G是正方形,S:G的四边相等。RS:如果G是正方形,那么G的四边相等。(c)W:桔子是紫色的,V:大地是不平的。WV:如果桔子是紫色的,那么大地是不平的。,因果关系,引入的目的是希望用来描述命题间的推理，表示因果关系使用PQ能描述推理如果今天是星期二，那么明天是星期天如果今天是星期一，那么明天是星期天如果n3那么n29(n=4,n=2,n=-4)与“如果那么”有一致的一面,同时也有与常识不一致的地方数理逻辑不关心具体命题，只关心推理的形式人为的规定，对P为F时PQ的值另作规定也是可以的,蕴含式PQ可以用多种方式陈述:;“若P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”;“P仅当Q”等。给定命题PQ,我们把QP,PQ,QP分别叫做命题PQ的逆命题,反命题和逆反命题.,例,令：P：天气好。Q：我去公园。1.如果天气好，我就去公园。2.只要天气好，我就去公园。3.天气好，我就去公园。4.仅当天气好，我才去公园。5.只有天气好，我才去公园。6.我去公园，仅当天气好。,PQPQPQQPQPQP,5.双条件词（等值，Biconditional）,如果P和Q是命题,那么“P等值于Q”也是命题,记为PQ,称为双条件式（等值式）,读做“P当且仅当Q”或“P等值于Q”。PQ也读做“P是Q的充要条件”。,联结词的注意事项,要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义特别要注意“或”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。特别要注意“”的用法，它既表示“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件联结词的优先级顺序，,练习：填空,已知PQ为T，则P为()，Q为()已知PQ为F，则P为()，Q为()已知P为F，则PQ为()已知P为T，则PQ为()已知PQ为T，且P为F，则Q为()已知PQ为F，则P为()，Q为()已知P为F，则PQ为()已知Q为T，则PQ为()已知PQ为F，则P为()，Q为(),1.1.3命题变元和命题公式,命题变元与命题常元命题常元命题有具体含义(真值)的例：“3是素数。”；T；F命题变元用大写的英字母如P、Q等表示任何命题真值指派解释将一个命题常元赋予命题变元的过程或者是直接赋给命题变元真值“T”或“F”的过程注意：命题变元本身不是命题，只有给它一个解释，才变成命题。,命题演算的合式公式(命题公式，wff，wellformedformulas),定义：单个命题变元是个合式公式。若A是合式公式，则A是合式公式。若A和B是合式公式，则(AB)，(AB)，(AB)和(AB)都是合式公式。当且仅当有限次地应用，所得到的含有命题变元、联结词和圆括号的符号串是合式公式。此外，称逐次使用规则，的过程中所得到的命题公式为最后构成的命题公式的子公式。递归定义(1)基本项，是递归的基础(2)(3)递归项，是递推规则(4)极小化，保证所构造集合的唯一性,例9,(a)(P(PQ)解(i)P是命题公式根据条款(1)(ii)Q是命题公式根据条款(1)(iii)(PQ)是命题公式根据(i)(ii)和条款(2)(iv)(P(PQ)是命题公式根据(i)(iii)和条款(2),例,下面的式子是否为合式公式：PQ，PR，PQR修改(PQ)，(PR)，(PQ)R),圆括号的省略规则最外层的圆括号可以省去符合联结词优先级顺序的,括号可省去相同的联结词,按从左至右次序计算时,括号可省去(PQ)R)(RP)Q)(PQ)R)(RP)Q)(PQR)(RPQ)(PQR)RPQ,命题符号化,用形式语言所表示的命题公式符号串来表示给定的命题例他既有理论知识又有实践经验P：他有理论知识Q：他有实践经验PQ如果明天不是雨夹雪则我去学校P：明天下雨Q：明天下雪R：我去学校(PQ)R如果明天不下雨并且不下雪则我去学校PQR,如果明天下雨或下雪则我不去学校PQR明天,我将雨雪无阻一定去学校PQRPQRPQRPQR当且仅当明天不下雪并且不下雨时我才去学校PQRPQR仅当明天不下雪并且不下雨时我才去学校RPQ说小学生编不了程序,或说小学生用不了个人计算机,那是不对的P：小学生会编程序Q：小学生会用个人计算机(PQ)PQ,练习,将下列命题符号化张三与李四是表兄弟张三或李四都能做这件事今晚我在家里看电视或去体育场看球赛今天我上班，除非今天我病了,命题函数有n个命题变元的命题公式可用函数A(P1,P2,Pn)的形式表示其中P1,P2,Pn按字典顺序排列对应的真值指派可记为I=(P1,P2,Pn)，其中Pi=0或1例A(P,Q,R)=P(RQ),真值指派(1,0,1)，(1,1,0)真值分别为F和T有n个命题变元的命题公式共有2n个不同的真值指派,1.2重言式/矛盾式/可满足式,1.2.1重言式（tautology）/矛盾式（contradiction）A(P1,P2,Pn)是含有命题变元P1,P2,Pn的命题公式，如不论对P1,P2,Pn作任何指派，都使得A(P1,P2,Pn)为真(假)，则称之为重言式(矛盾式),也称之为永真式(永假式)例：PP和PP偶然式不是永真式,也不是永假式例：P,PQ可满足式（satisfactableformula）非矛盾式PP，PQ,重言式的证明方法方法1：列真值表方法2：公式的等价变换，化简成“T”方法3：用公式的主析取范式证明(P(PQ)Q为重言式,T,T,T,T,重言式的性质,如果A是重言式，则A是矛盾式如果A是矛盾式，则A是重言式如果A，B是重言式，则(AB)、(AB)、(AB)和(AB)也都是重言式如果A，B是矛盾式，则(AB)、(AB)也都是矛盾式，(AB)和(AB)是重言式,命题公式的等价与蕴含,1.2.2恒等式（等价式，equivalent）设A:A(P1,P2,Pn),B:B(P1,P2,Pn)是两个命题公式,这里Pi(i=1,2,n)不一定在两公式中同时出现，如不论对P1,P2,Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价（恒等），记作AB，读做“A等价于B”或“A恒等于B”等价定理：AB当且仅当AB是重言式注意：“”与“”不同：逻辑联结词：描述两个命题公式之间的关系若A与B是wff，AB是wff，AB不是,常用逻辑恒等式,等价式的证明,方法1：列真值表方法2：公式的等价变换,T,T,F,F,T,T,T,T,1.2.3永真蕴含式(implication),定义给定两个命题公式A和B，如果公式AB是重言式，则称A重言(永真)蕴含B，或简单的说A蕴含B，记作AB注意：“”不是联结词表示公式间的“永真蕴含”关系也可看成“推导”关系AB可以理解成由A可推出B，即由A为真，可以推出B也为真,蕴含式的证明方法真值表利用一些基本等价式及蕴涵式进行推导逻辑推证假定前件是真,若能推出后件是真,则此蕴含式是真假定后件是假,若能推出前件是假,则此蕴含式是真,用真值表证明蕴含关系,证明：(PQ)(PR)(QR)R,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,方法1:设Q(PQ)是真则Q,PQ是真所以,Q是假,P是假。因而P是真。故Q(PQ)P,方法2:设P是假,则P是真。以下分情况讨论。(i)若Q为真,则Q是假,所以Q(PQ)是假(ii)若Q是假,则PQ是假所以Q(PQ)是假故Q(PQ)P,例1证明Q(PQ)P,永真蕴含式,1.2.4等价和蕴含的性质,等价关系的性质自反性任何命题公式A，有AA对称性若AB，则BA传递性若AB且BC，则AC,蕴含关系的性质自反性任何命题公式A，有AA反对称性若AB且BA，iffAB传递性若AB且BC，则AC若AB,AC,则ABC,思考：若AB，则AB？,No！BA,证明,若AB,BC则AC证明：AB永真;BC永真,所以(AB)(BC)永真由公式I6得AC永真,既AC若AB,AC,则ABC证明：A是真时,B和C都真,所以BC也真因此ABC永真,则ABC,1.2.5代入规则和替换规则,代入实例设A和B是两个命题公式，如果将A中的某些命题变元用命题公式进行代换便可得到B，并且此种代换满足：（1）被代换的是命题变元（2）如果要代换某个命题变元，则要将该命题变元在A中的一切出现进行代换（3）代换必须同时独立进行此时称B是A的一个代换实例（代入实例）例A(P,Q)=PQA(P,QR)=PQRA(P,Q,R,S)=(PQ)R(S(PQ)(PQ)S(R(PQ)，(PQ)R(S(PQ)PR(SP)，(PQ)R(R(PQ),1.2.5代入规则和替换规则,代入规则(RuleofSubstitution，代入定理)重言式的代入实例是重言式例(RQ)(RQ)(RQ)(RQ)(PQSQ),矛盾式的代入实例是矛盾式吗？Yes,PP,PPQ,替换规则(RuleofReplacement，置换定理)子公式定义：如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式例：AQ(P(PQ)，XPQ替换规则定理：设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB例：Q(P(PQ)QP代入与替换的区别代入是对命题变元进行取代，替换对子公式代入必须取代该命题变元的一切出现，替换不用可用任意wff去代换命题变元，只能用与子公式等价的公式去替换代入实例一般不与原公式等价，替换后的公式必与原公式等价,等价变换（等值演算）,由已知的等价式按照合理的规则逐步推演出另外一些等价式的过程反复应用代入规则和替换规则例1：E4:PQQP,AB,AB,AB,AB,E14:PQPQ(RQ)P,(RQ)P,例2,(a)证明PQQPQ证明：PQQQPQE4(QP)(QQ)E9(QP)TE20和替换规则QPE19PQE4,(b)证明(PQ)(QR)PQR证明：(PQ)(QR)(PQ)(QR)E14和替换规则(PQ)(QR)E14PQ(QR)E10、E1和替换规则(PQQ)RE6PQR例2(a)和替换规则,(c)试将语句“情况并非如此:如果他不来,那么我也不去。”化简。解：设P:他来,Q:我去(PQ)(PQ)E14和替换规则PQE10，E1和替换规则(d)找出P(PQ)R的仅含和两种联结词的等价表达式。P(PQ)RP(PQ)(QP)RP(PQ)(QP)R(PPQ)(PQP)R(PQ)TRPQR(PQR),(),1.2.6对偶原理,定义1.21：设有公式A,其中仅有联结词,。在A中将,T,F分别换以,F,T得公式A*,则A*称为A的对偶公式(A*)*?(A*)*A例3(a)A=PF，A*=？A*=PT(b)A=PQR，A*=？,A*=PQR,定理1.2-1设A和A*是对偶式。P1,P2,Pn是出现于A和A*中的所有命题变元,于是A(P1,P2,Pn)A*(P1,P2,Pn)证明：反复地使用德-摩根定律A(P,Q)PQ，A*(P,Q),PQ,A(P,Q),(PQ),A*(P,Q),PQ,A(P,Q)A*(P,Q),推论:A(P1,P2,Pn)A*(P1,P2,Pn)因为A(P1,P2,Pn)A*(P1,P2,Pn)所以A(P1,P2,Pn),A*(P1,P2,Pn),即A(P1,P2,Pn)A*(P1,P2,Pn),是重言式,则A(P1,P2,Pn)A*(P1,P2,Pn),是重言式,所以A(P1,P2,Pn)A*(P1,P2,Pn),定理1.22（对偶原理）若AB,且A,B为命题变元P1,P2,.,Pn及联结词,构成的公式,则A*B*。证明：因为A(P1,P2,Pn)B(P1,P2,Pn)故A(P1,P2,Pn)B(P1,P2,Pn)而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)若AB,且A,B为命题变元P1,P2,.,Pn及联结词,构成的公式,则A*B*成立吗？如果是，请证明；如果否，为什么？定理1.2-3若AB,且A,B为命题变元P1,P2,.,Pn及联结词,构成的公式,则B*A*,1.3范式,1.3.1析取范式和合取范式范式就是命题公式形式的规范形式范式中只含有联结词、和定义1.3-1：基本积、基本和文字（因子）原子或原子的否定称为文字例：P，PP与P称为互补对基本积文字的合取式（短语）P、P、PQ、PQR基本和文字的析取式（子句）P、P、PQ、PQR,定理1.3-1一个基本积是永假式,当且仅当它含有P,P形式的两个因子。证明：充分性：PP是永假式,而QFF,所以含有P和P形式的两个因子时,此基本积是永假式必要性：（反证法）设基本积永假但不含P和P形式的两个因子,则给这个基本积中不带否定符的命题变元指派真值T,带有否定符的命题变元指派真值F,得基本积的真值是T,与题设矛盾。证毕。,定义1.3-2析取范式一个由基本积之和组成的公式,如果与给定的命题公式A等价,则称它是A的析取范式,记为AA1A2An,n1这里A1,A2,An是基本积。任何一个命题公式都可求得它的析取范式一个命题公式的析取范式不是唯一的最简析取范式：运算符最少的析取范式定义1.3-3合取范式一个由基本和之积组成的公式,如果与给定的命题公式A等价,则称它是A的合取范式,记为AA1A2An,n1这里A1,A2,An是基本和任何一个命题公式都可求得它的合取范式一个命题公式的合取范式不是唯一的最简合取范式：运算符最少的合取范式,析取范式与合取范式的求法先用相应的公式去掉和。公式E16PQPQ公式E21PQ(PQ)(PQ)公式E20PQ(PQ)(QP)再用E16PQ(PQ)(PQ)用公式的否定公式或摩根律将后移到命题变元之前。A(P1,P2,Pn)A*(P1,P2,Pn)摩根律(PQ)PQ(PQ)PQ用分配律、幂等律等公式进行整理，使之成为所要求的形式。,例1,(a)求P(PQ)的析取范式。解P(PQ)P(PQ)PPPQ或：P(PQ)FPQPQ,最简析取范式,(b)求(PQ)(PQ)的最简析取范式。解(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)PQPQ,例2,(a)证明QPQPQ是永真式。解QPQPQQ(PP)Q(QPP)(QQ)QPPT，(QQ)T所以(QPP)(QQ)T(b)求(PQ)(PQ)的最简合取范式。解(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ),1.3.2主析取范式和主合取范式,定义1.3-4极小项在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫极小项PQ、PQ、PQ、PQn个变元可构成2n个不同的极小项命题变元看成1,命题变元的否定看成0,那么每一极小项对应一个二进制数,因而也对应一个十进制数把对应的十进制数当作足标,用mi表示这一项,m0PQR0000m1PQR0011m2PQR0102m3PQR0113m4PQR1004m5PQR1015m6PQR1106m7PQR1117一般地，对P1,Pn而言，2n个极小项为：,极小项的性质合取式每个极小项mk只在与其下标对应的真值指派下为T，其余都为FmimjF，ijmiT（0i2n-1）定义1.3-5一个由极小项之和组成的公式,如果与给定的命题公式A等价,则称它是A的主析取范式,设G=(PQ)(PR)(QR),PQR,PQR,PQR,PQR,m1m3m6m7(1，3，6，7),定理每一个不为永假的命题公式A(P1,P2,Pn)必与一个由P1,P2,Pn所产生的主析取范式等价永真公式的主析取范式包含所有2n个极小项永真公式的主合取范式是一空公式，用1表示证明：存在性：由上页主析取范式的构造过程可证唯一性：设有两个不同的主析取范式B和C都与A等价由于B和C不同，即必存在极小项mi在B中但不在C中，或在C中但不在B中，不妨设其在B中但不在C中。则在i对应的真值指派下，mi为T，即B为T，而C为F与B和C都是A的主析取范式矛盾唯一性得证,用等价变换求主析取范式先用相应的公式去掉和用公式的否定公式或摩根律将后移到命题变元之前用分配律、幂等律等公式进行整理，使之成为析取范式A1A2.An为使每个Ai都变成极小项，对缺少变元的Ai补全变元，比如缺变元R，就用联结永真式(RR)形式补R消去重复的极小项，并将极小项按下标由小到大的次序排列,例求G=(RP)(Q(PR)主析取范式,G(RP)(Q(PR)(RP)(QP)(QR)(PR)(QP)(QR)(PR)(QQ)(QP)(RR)(QR)(PP)(PQR)(PQR)(PQR)(PQR)(1，3，6，7),例3,证明PQ和P(PQ)(QP)二式逻辑等价。证PQP(QQ)Q(PP)PQPQPQP(PQ)(QP)P(PQ)(QP)P(PQP)(QQP)PPQP(QQ)PQPQPQPQ所以,二式逻辑等价。,定义1.3-6极大项在n个变元的基本和中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本和叫极大项PQ、PQ、PQ、PQn个变元可构成2n个不同的极大项命题变元看成0,命题变元的否定看成1,那么每一极大项对应一个二进制数,因而也对应一个十进制数把对应的十进制数当作足标,用Mi表示这一项,M0PQR0000M1PQR0011M2PQR0102M3PQR0113M4PQR1004M5PQR1015M6PQR1106M7PQR1117一般地，对P1,Pn而言，2n个极大项为：,极大项的性质析取式每个极大项Mk只在与其下标对应的真值指派下为F，其余都为TMiMjT，ijMiF（0i2n-1）定义1.3-7一个由极大项之积组成的公式,如果与给定的命题公式A等价,则称它是A的主合取范式,设G=(PQ)(PR)(QR),(PQR),(PQR),(PQR),(PQR),M0M2M4M5(0，2，4，5),定理每一个不为永真的命题公式A(P1,P2,Pn)必与一个由P1,P2,Pn所产生的主合取范式等价永假公式的主合取范式包含所有2n个极大项永假公式的主析取范式是一空公式，用0表示,用等价变换求主合取范式先用相应的公式去掉和用公式的否定公式或摩根律将后移到命题变元之前用分配律、幂等律等公式进行整理，使之成为合取范式A1A2.An为使每个Ai都变成极大项，对缺少变元的Ai补全变元，比如缺变元R，就用联结矛盾式(RR)形式补R消去重复的极大项，并将极大项按下标由小到大的次序排列,例:求G=(RP)(Q(PR)主合取范式,G(RP)(Q(PR)(RP)(Q(PR)(PR)(Q(PR)(PRQ)(PRPR)(PQ)(RQ)(PPR)(RPR)(PQ(RR)(RQ)(PR)(PQR)(PQR)(PQR)(PQR)(0，2，4，5),利用主范式判定公式类型,利用主析取范式判定若公式A(P1,P2，Pn)的主析取范式包含所有2n个极小项，则A是永真式若A的主析取范式是一空公式且为0，则A是永假式否则，A为偶然式利用主合取范式判定若公式A(P1,P2，Pn)的主合取范式包含所有2n个极大项，则A是永假式若A的主合取范式是一空公式且为1，则A是永真式否则，A为偶然式,例：求公式A=(Q(PQ)P的主范式并判定公式的类型,解(1)求A的主析取范式A(Q(PQ)PQ(PQ)P(Q(PP)(PQ)(P(QQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)由此可知A是可满足公式,(2)求A的主合取范式A（Q(PQ)PPQ由前分析和举例可知：仅需求出公式A的任一种主范式即可判定A的类型,主析取范式和主合取范式的关系一个命题公式的主析取范式和主合取范式紧密相关在它们的简记式中,代表极小项和极大项的足标是互补的,即两者一起构成0,1,2,2n-1诸数例A(P,Q,R)=(1,3,5,6,7)(),0,2,4,B(P,Q,R,S)=(0,1,3,5,6,7)(),(2,4,8,9,10,11,12,13,14,15),miMiMimi,练习,1.通过主范式判断公式A=(PQ)(PQ)是否为重言式或矛盾式？2.已知A(P,Q,R)的真值表如右图：求它的主析取和主合取范式。3.已知A(P,Q,R)的主析取范式中含有下面极小项m1,m3,m5,m7写出它的主合取范式及其对应的命题公式,Answers,1.解:A(PQ)(PQ)(QP)(PQ)(PQ)(QP)(PQ)(P(QP)(Q(QP)(PQ)(PQ)(PP)(QQ)(QP)(PQ)(PQ)(QP)主析取范式既非空公式，又未包含22=4个项，故F不是重言式和矛盾式，只是可满足式,2.A(P,Q,R)的主析取范式:A(P,Q,R)m0m3m4m6m7(PQR)(PQR)(PQR)(PQR)(PQR)A(P,Q,R)的主合取范式：A(P,Q,R)M1M2M5(PQR)(PQR)(PQR)3.A(P,Q,R)M0M2M4M6(PQR)(PQR)(PQR)(PQR),范式的应用,逻辑设计例1.加法器的设计，有两个n位二进制数a,b相加和为s(s=a+b)，a,b分别写成：a=anan-1ai.a2a1,+b=bnbn-1bi.b2b1s=cnsnsn-1sis2s1其中si是第i位ai、bi及ci-1(ci-1是第i-1位向第i位的进位)的和，显然si是aibi及ci-1的函数,写成si(ai,bi,ci-1),它与ai,bi,ci-1的关系如下表：,根据前边的表,列出si(ai,bi,ci-1)的主析取范式：si(ai,bi,ci-1)=(aibici-1)(aibici-1)(aibici-1)(aibici-1)(在指派001、010、100、111时si为1),在电路逻辑设计中用如下逻辑部件：非门与门或门,si(ai,bi,ci-1)=(aibici-1)(aibici-1)(aibici-1)(aibici-1),例2.安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令L1、L2、L3分别表示语言课排在第一、第二、第三节。M1、M2、M3分别表示数学课排在第一、第二、第三节。P1、P2、P3分别表示原理课排在第一、第二、第三节。,三位教师都满意的条件是：(L1L3)(M2M3)(P1P2)为真。将上式写成析取范式(用分配律)得：(L1M2)(L1M3)(L3M2)(L3M3)(P1P2)(L1M2P1)(L1M3P1)(L3M2P1)(L3M3P1)(L1M2P2)(L1M3P2)(L3M2P2)(L3M3P2)可以取(L3M2P1)、(L1M3P2)为T，得到两种排法。,1.3.3主析取范式的个数,n=1时极小项有21=2个,P,P一个命题变元能够构成的不同的主析取范式FPPPP22个,n=2极小项有22=4个,PQ,PQ,PQ,PQ两个命题变元能够构成的不同的主析取范式,222=16个,n个命题变元极小项有2n个不同的主析取范式22n个(包括F)不同的主析取范式22n个(包括T),1.4联结词的扩充与归约,1.4.1联结词的扩充问题的提出：对n个命题变元P1Pn来说,共可定义出多少个联结词?在那么多联结词中有多少是相互独立的?4个新联结词：与非:PQ(PQ)或非:PQ(PQ)排斥或(异或):PQ(PQ)PQPQ蕴含否定(条件否定):PQ(PQ),Q1：可定义多少个联结词？,命题变元和命题联结词可以构成无限多个合式公式把所有的合式公式分类：将等值的公式视为同一类，对于该类合式公式，就可定义一个联结词与之对应,一元联结词的个数一元联结词是联结一个命题变元的由一个命题变元P可构成4种不等价的命题公式相应的可定义出4个不同的一元联结词,二元联结词的个数二元联结词联结两个命题变元由两个命题变元P，Q可构成16种不等价的命题公式相应的可定义出16个不同的二元联结词n元联结词的个数对n个命题变元P1,Pn,每个Pi有2种取值,从而对P1Pn来说共有2n种取值情形相应的可定义出22n个n元联结词,二元运算,1.4.2联结词的归约,Q2：联结词是否都是独立的，或者说能否相互表示定义1.4-1一个联结词集合,用其中联结词构成的式子足以把一切命题公式等价地表达出来,则这个联结词集合称为全功能的，相应的把这个集合称为联结词功能完备集,完备集,全体联结词的无限集合是完备的,是完备的联结词集合,是联结词的完备集证明：已知,是全功能的，又PQ(PQ)，因此可由,表示，所以,是全功能的,是联结词的完备集,是完备集是完备集是完备集(独立的完备集),是完备的,不完备集,其任何子集都是不完备的,*1.4.3其它主范式前边介绍了主析取范式和主合取范式,联结词扩充后,也可由极小项和联结词构成主异或范式,由极大项和联结词构成主等值范式。例如,因为对任一指数,任两个不同的极小项mi和mj不可能同时为真,因此mimj与mimj是等价的,故由主析取范式可转写成主异或范式。类似地,任两个不同的极大项Mi和Mj不可能同时为假,因此MiMj和MiMj是等价的,故主合取范式可转写成主等值范式。主异或范式和主等值范式也是唯一的。,1.5推理规则和证明方法,例1、如果天不下雨，我就去看电影；我没有去看电影，说明_2、如果李敏出差到学校，若王军不生病，则王军一定去看望李敏。如果李敏出差到长沙，那么李敏一定来学校。王军没有生病。所以，_3、如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知_不能得亚军。,1.5.1推理规则,推理根据一个或几个已知的判断得出一个新的判断的思维过程称这些已知的判断为前提得到的新的判断为前提的有效结论定义1.51设A和B是两个命题公式，如果AB，则称B是前提A的结论或从A推出结论B。一般地设H1，H2，,Hn和C是一些命题公式,若蕴含式H1H2HnC成立，则称C是前提集合H1，H2，,Hn的结论，或称从前提H1，H2，,Hn能推出结论C。有时也记作H1，H2，,HnC称(H1H2Hn)C为由前提H1，H2，,Hn推结论C的推理的形式结构,如何判断由一个前提集合能否推出某个结论?,真值表法等价变换法“形式证明”法形式证明：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论有效的证明：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的有效的结论：通过有效的证明而得到结论，称作是有效的结论合理的证明：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。合理的结论：一个结论是否有效与它自身的真假没有关系。通过合理证明而得到的结论称作合理的结论,推理规则,规则P(引入前提规则)：在推理过程中，可以随时引入前提。规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入推理过程中。教材9-10页表1.2-1,1.2-2中的等价式和蕴涵式,例：求证PQ，QR，PR,证明序号前提或结论所用规则从哪几步得到所用公式(1)PP(2)PQP(3)QT(1)(2)I(4)QRP(5)RT(3)(4)I,例：求证(PQ)(QR)RP,I,(3)(5),T,P,(6),E,(4),T,PQ,(5),P,(PQ),(4),I,(1)(2),T,Q,(3),P,R,(2),P,QR,(1),例：用命题逻辑推理方法证明下面推理的有效性,如果我学习，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。解设P：我学习。Q：我数学及格。R：我热衷于玩朴克。PQ，RP，QR,PQ，RP，QR(1)PQP(2)QP(3)PT(1)(2)I(4)RPP(5)RT(3)(4)I(6)RT(5)E,例：求证P(QS),RP,QRS,证明(1)P(QS)P(2)P(QS)T(1)E(3)P(SQ)T(2)E(4)(PS)QT(3)E(5)QP(6)PST(4)(5)I(7)PST(6)E(8)RPP(9)RPT(8)E(10)RST(7)(9)I,练习,用形式证明方法证明：（PQ）R，RS，SPQ（1）RSP（2）SP（3）RT(1)(2)I（4）(PQ）RP（5）（PQ）RT(4)E（6）（PQ）T(3)(5)I（7）PQT(6)E,例:ABC,BD,(EP)D,BAEBE,(1)BDP(2)BDT(1)E(3)(EP)DP(4)D(EP)T(3)E(5)B(EP)T(2)(4)I(6)B(EP)T(5)E(7)BEPT(6)E(8)BEPT(7)E(9)(BE)(BP)T(8)E(10)(BE)T(9)I(11)BET(10)E,1.5.2证明方法,定理常见的形式P当且仅当Q,如果P,那么QPQ且QP,PQ证明PQ为真的方法无义证明法证明P是假,那么PQ是真平凡证明法证明Q是真,那么PQ是真直接证明法间接证明法附加前提证明法反证法（归谬法）,附加前提证明法,如果要证明的结论是蕴涵式(RS)形式，则可以把结论中蕴涵