《第二章命题逻辑的等值和推理演算课件.ppt》由会员分享，可在线阅读，更多相关《第二章命题逻辑的等值和推理演算课件.ppt（100页珍藏版）》请在三一办公上搜索。
1、第二章 命题逻辑的等值和推理演算,推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的推理过程是从前提出发，根据所规定的规则来推导出结论的过程 重言式是重要的逻辑规律，正确的推理形式、等值式都是重言式,1,谢谢观赏,2019-8-23,本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式的描述，不仅直观且容易理解，也便于实际问题的逻辑描述和推理。严格的形式化的讨论见第三章所建立的公理系统。,2,谢谢观赏,2019-8-23,等值演算(考察逻辑关系符(=),等值定理、公式联结词的完备集(由个别联结词表示所有联结词的问题)对偶式(命题公式的对偶性)范式(命题
2、公式的统一标准) 由真值表写命题公式(由T写、由F写),3,谢谢观赏,2019-8-23,推理演算(考察逻辑关系符),推理形式(正确推理形式的表示)基本推理公式(各种三段论及五种证明方法)推理演算(证明推理公式的第六种方法，使用推理规则)归结推理法(证明推理公式的第七种方法，常用反证法),4,谢谢观赏,2019-8-23,2.1 等值定理,若把初等数学里的、等运算符看作是数与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下：x2y2 = (xy)(xy)(xy)2 = x22xyy2 sin2xcos2x = 1在命题逻辑里也同样可建立一些重要的等值式,5,谢谢观赏,2
3、019-8-23,2.1.1 等值的定义,给定两个命题公式A和B, 而P1Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或AB显然，可以根据真值表来判明任何两个公式是否是等值的,6,谢谢观赏,2019-8-23,例1: 证明(PP)Q = Q,证明: 画出(PP)Q与Q的真值表可看出等式是成立的。,7,谢谢观赏,2019-8-23,例2: 证明PP = QQ,证明: 画出PP, QQ的真值表, 可看出它们是等值的, 而且它们都是重言式。,8,谢谢观赏,2019-8-23,从例1
4、、2还可说明, 两个公式等值并不一定要求它们一定含有相同的命题变项若仅在等式一端的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。例1中公式(PP)Q与Q的真值都同P无关例2中PP, QQ都是重言式, 它们的真值也都与P、Q无关。,说明,9,谢谢观赏,2019-8-23,2.1.2 等值定理,定理 对公式A和B, A=B的充分必要条件是AB是重言式。A、B不一定都是简单命题, 可能是由简单命题P1, , Pn构成的. 对A, B的一个解释, 指的是对P1, , Pn的一组具体的真值设定.若AB为重言式, 则在任一解释下A和B都只能有相同的真值, 这就是定理的意思。,10,谢谢观赏,2
5、019-8-23,证明,若A B是重言式, 即在任一解释下, A B的真值都为T依A B的定义只有在A、B有相同的值时, 才有A B = T。于是在任一解释下, A和B都有相同的真值, 从而有A=B。反过来，若有A = B, 即在任一解释下A和B都有相同的真值, 依A B的定义, A B只有为真, 从而A B是重言式。注：根据该等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可,11,谢谢观赏,2019-8-23,“”作为逻辑关系符是一种等价关系,不要将“”视作联结词，在合式公式定义里没有“”出现A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性
6、 A = A2. 对称性 若A = B, 则B = A3. 传递性 若A = B, B = C, 则A = C 这三条性质体现了“”的实质含义。,12,谢谢观赏,2019-8-23,2.2 等值公式,2.2.1 基本的等值公式(命题定律, P和Q是任意的命题公式)1. 双重否定律P = P2. 结合律(PQ)R = P(QR)(PQ)R = P(QR)(P Q) R = P (Q R)注: 所有这些公式，都可使用真值表加以验证,13,谢谢观赏,2019-8-23,3. 交换律PQ = QPPQ = QPP Q = Q P4. 分配律P(QR) = (PQ)(PR)P(QR) = (PQ)(PR
7、)P(QR) = (PQ)(PR)5. 等幂律(恒等律)PP = PPP = PPP = TPP = T,14,谢谢观赏,2019-8-23,6. 吸收律P(PQ) = PP(PQ) = P7. 摩根律(PQ) = PQ(PQ) = PQ对蕴涵词、双条件词作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ),15,谢谢观赏,2019-8-23,8. 同一律PF = PPT = PTP = PTP = P还有PF = PFP = P,16,谢谢观赏,2019-8-23,9. 零律PT = TPF = F还有PT = TFP = T10. 补余律PP = TPP = F还有P
8、P = PPP = PPP = F,17,谢谢观赏,2019-8-23,Venn图(理解等式),将P、Q理解为某总体论域上的子集合，并规定：PQ为两集合的公共部分(交集合)PQ为两集合的全部(并集合)P为总体论域(如矩形域)中P的余集,18,谢谢观赏,2019-8-23,Venn图(理解等式),从Venn 图，因PQ较P来得“小”, PQ较P来得“大”，从而有P(PQ) = PP(PQ) = P,19,谢谢观赏,2019-8-23,理解等式: Venn图，自然语言,(PQ) = PQVenn图(理解集合间、命题逻辑中、部分信息量间的一些关系)对这些等式使用自然用语加以说明，将有助于理解如P表示
9、张三是学生, Q表示李四是工人, 那么(PQ)就表示并非“张三是学生或者李四是工人”。这相当于说，“张三不是学生而且李四也不是工人”，即可由PQ表示, 从而有(PQ) = PQ,20,谢谢观赏,2019-8-23,2.2.2 常用的等值公式,由于人们对、更为熟悉，常将含有和的公式化成仅含有、的公式。这也是证明和理解含有，的公式的一般方法公式11-18是等值演算中经常使用的, 也该掌握它们, 特别是能直观地解释它们的成立,21,谢谢观赏,2019-8-23,11. PQ = P Q,通常对PQ进行运算时, 不如用PQ来得方便。而且以PQ表示PQ帮助我们理解如果P则Q的逻辑含义问题是这种表示也有缺
10、点，丢失了P、Q间的因果关系,22,谢谢观赏,2019-8-23,12. PQ = QP,逆否定理，假言易位如将PQ视为正定理, 那么QP就是相应的逆否定理, 它们必然同时为真, 同时为假, 所以是等值的,23,谢谢观赏,2019-8-23,13. P(QR) = (PQ)R,前提合并P是(QR)的前提, Q是R的前提, 于是可将两个前提的合取PQ作为总的前提。 即如果P则如果Q则R, 等价于如果P与Q则R,24,谢谢观赏,2019-8-23,14. PQ = (PQ)(PQ),从取真来描述双条件这可解释为PQ为真, 有两种可能的情形, 即(PQ)为真或(PQ)为真。而PQ为真, 必是在P =
11、 Q = T的情况下出现; PQ为真, 必是在P = Q = F的情况下出现。从而可说, PQ为真, 是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式,25,谢谢观赏,2019-8-23,15. PQ = (PQ)(PQ),从取假来描述双条件这可解释为PQ为假, 有两种可能的情形, 即(PQ)为假或(PQ)为假, 而PQ为假, 必是在P = F, Q = T的情况下出现; PQ为假, 必是在P = T, Q = F的情况下出现。从而可说PQ为假, 是在P真Q假或P假Q真时成立。这就是从取假来描述这等式,26,谢谢观赏,2019-8-23,16. PQ = (PQ)(QP),从蕴含词
12、来描述双条件这表明PQ成立, 等价于正定理PQ和逆定理QP都成立,27,谢谢观赏,2019-8-23,17. P(QR) = Q(PR),前提交换前提条件P、Q可交换次序,28,谢谢观赏,2019-8-23,18. (PR)(QR)=(PQ)R,左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立, 这就是等式右端,29,谢谢观赏,2019-8-23,补充,等价否定等值式PQ = PQ归谬论(PQ)(PQ) = P,30,谢谢观赏,2019-8-23,2.2.3 置换规则,置换定义对公式A的子公式, 用与之等值的公式来代换便称置换置换规则公式A的子公式置换后A化为公式B, 必有A
13、= B当A是重言式时, 置换后的公式B必也是重言式置换与代入是有区别的。置换只要求A的某一子公式作代换, 不必对所有同一的子公式都作代换,31,谢谢观赏,2019-8-23,代入规则回顾,A是一个公式，对A使用代入规则得公式B，若A是重言式，则B也是重言式为保证重言式经代入规则仍得到保持，要求公式中被代换的只能是命题变元(原子命题), 而不能是复合命题对公式中某命题变元施以代入，必须对该公式中出现的所有同一命题变元代换以同一公式,32,谢谢观赏,2019-8-23,2.2.4 等值演算举例,例1: 证明(P(QR)(QR)(PR) = R证明: 左端= (P(QR) (QP)R)(分配律)=
14、(PQ)R)(QP)R)(结合律)= (PQ)R)(QP)R)(摩根律)= (PQ)(QP)R(分配律)= (PQ)(PQ)R(交换律)= TR(置 换)= R(同一律),33,谢谢观赏,2019-8-23,例2: 试证 (PQ)(P(QR) (PQ)(PR) = T证明:左端=(PQ)(P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律)=(PQ)(PR)(PQ)(PR)(等幂律)=T,举例,34,谢谢观赏,2019-8-23,问题提出：由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？,2.3 命题公式与真值表关系,35,谢谢观赏,2019-8-
15、23,2.3.1 从T来列写,记忆方法：各项间用，每项内用每项内书写方法：例真值表中P=T且Q=F等价于PQ=T简化方法：有时A的表达通过A来描述,36,谢谢观赏,2019-8-23,2.3.2 从F来列写,记忆方法：各项间用 ，每项内用每项内书写方法：例真值表中P=T且Q=F等价于PQ=F简化方法：有时A的表达通过A来描述,37,谢谢观赏,2019-8-23,举例,从A的真值T直接: A = (P Q) (P Q) (P Q)间接: A = A = (P Q) = P Q从B的真值FB = (P Q) (P Q)当C可取任意值C与P, Q = T, T无关, 可适当选取C的真值, 使其表达式
16、简单,38,谢谢观赏,2019-8-23,作业(1),(P37) 1(1, 3), 2,39,谢谢观赏,2019-8-23,2.4 联结词的完备集,问题的提出对n 个命题变项P1Pn来说, 共可定义出多少个联结词? 在那么多联结词中有多少是相互独立的?3个新联结词：,思考：考虑异或联结词与双条件联结词的关系(可利用真值表),40,谢谢观赏,2019-8-23,2.4.1 命题联结词的个数,第一个问题。可定义多少个联结词？由命题变项和命题联结词可以构成无限多个合式公式把所有的合式公式分类：将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项，或者说对于该类合式公式，就可定义一个
17、联结词与之对应例：等价类。自然数集合N被3除余数相同的自然数构成3个集合N0 , N1 , N2,41,谢谢观赏,2019-8-23,一元联结词是联结一个命题变项(如P)的P有真假2种值，因此P(自变量)上可定义4种一元联结词fi 或说真值函项fi(P), i = 1, 2, 3, 4,一元联结词的个数,42,谢谢观赏,2019-8-23,由真值表写出真值函项的命题公式：f0(P) = F(永假式)f1(P) = P(P自身)f2(P) = P(否定词)f3(P) = T(永真式)新的公式只有f2(P), 与之对应的联结词是否定词,一元联结词,43,谢谢观赏,2019-8-23,二元联结词联结
18、两个命题变项(如P、Q)两个变项共有4种取值情形,于是P、Q上可建立起16种不同的真值函项,相应的可定义出16个不同的二元联结词g0, g1, , g15 图2.4.2给出了这些联结词gi或说真值函项gi(P,Q)的真值表定义,二元联结词的个数,44,谢谢观赏,2019-8-23,45,谢谢观赏,2019-8-23,根据真值表写出各真值函项的命题表达式:g0(P,Q) = F(永假式)g1(P,Q) = PQ (合取式)g2(P,Q) = PQ g3(P,Q) = (PQ)(PQ) = P(QQ) = Pg4(P,Q) = PQ g5(P,Q) = (PQ)(PQ) = (PP)Q = Qg6
19、(P,Q) = P Q (异或式)g7(P,Q) = PQ (析取式)g8(P,Q) = PQ = P Q(或非式) g9(P,Q) = P Q (双条件式)g10(P,Q) = (PQ)(PQ) = (PP)Q = Qg11(P,Q) = PQ = QP(蕴涵式)g12(P,Q) = (P Q)(PQ) = P(QQ) = Pg13(P,Q) = PQ = PQ(蕴涵式)g14(P,Q) = PQ = P Q (与非式)g15(P,Q) = T (永真式),46,谢谢观赏,2019-8-23,n元联结词对n个命题变元P1 , , Pn , 每个Pi有两种取值, 从而对P1Pn来说共有2n种取
20、值情形于是相应的真值函项就有22n个, 或说可定义22n个n元联结词,n元联结词的个数,47,谢谢观赏,2019-8-23,2.4.2 联结词的完备集,第二个问题。联结词是否都是独立的，或者说能否相互表示?联结词的完备集定义: 设C是联结词的集合，如果对任一命题公式(能直接使用T和F)都有由C中的联结词表示出来的公式(不能直接使用T和F)与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。,48,谢谢观赏,2019-8-23,1. 全体联结词的无限集合是完备的2. , , 是完备的联结词集合 证明：从2.3节介绍的由真值表列写逻辑公式的过程可知, 任一公式都可由, , 表示出来, 从而
21、, , 是完备的3. , 是联结词的完备集(独立的完备集)证明：PQ = (PQ)，因此可由, 表示4. , 是联结词的完备集(独立的完备集)证明：PQ = (PQ)，因此可由, 表示,完备集,49,谢谢观赏,2019-8-23,5. , 是完备集(独立的完备集)因为：PQ = PQ6. 是完备集(独立的完备集)7. 是完备集(独立的完备集)8. , , , , 是完备的 因为它包含了2中的集合,完备集,50,谢谢观赏,2019-8-23, 不是完备的因为F不能仅由该集合的联结词表达出, 不是完备的, 的任何子集都是不完备的 , 的任何子集也是不完备的(如果一个联结词的集合是不完备的，那么它的
22、任何子集都是不完备的),不是完备的,不完备集,51,谢谢观赏,2019-8-23,最小的联结词的完备集基底,基底：完备的联结词集合的联结词是独立的，也就是说这些联结词不能相互表示任取四个一元或二元联结词，它们必组不成基底,52,谢谢观赏,2019-8-23,基底,只含一个联结词的: NK;NA含两个联结词的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC含三个联结词的:F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE其中：A- K- E- C- N- ,53,谢谢观赏,2019-8-23,2.5 对偶式,
23、研究目的简化等值公式的讨论希望一个公式成立，能够导出与其“相像”的公式成立逻辑关系上看，是一种逻辑规律对偶式定义：将A中出现的、T、F分别以、F、T代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式注：这里假定A中仅出现 、三个联结词若A = B，必有A*=B*?,54,谢谢观赏,2019-8-23,新符号“-”: (代入规则、内否式)若A=A(P1, , Pn)，令A= A(P1, , Pn)关于等值的三个定理定理2.5.1 (A*) = (A)*, (A) = (A) 定理2.5.2 (A*)* = A, (A)=A定理2.5.3 A = A* (摩根律的另一种形式)更
24、多：(A B)* = A* B*，(A B)- = A- B- (A B)* = A* B*，(A B)- = A- B-,对偶式相关定理,55,谢谢观赏,2019-8-23,56,性质举例,A= (P (Q R) TA*= (P (Q R) FA-= (P) (Q R) TA*- = (P) (Q R) FA-* = (P) (Q R) F,谢谢观赏,2019-8-23,定理2.5.3 A = A*,证明: 可用数学归纳法, 施归纳于A中出现的 联结词个数n来证明基始: 设n=0, A中无联结词, 便有 A=P, 从而 A = P但 A* = P n=0时定理成立。,57,谢谢观赏,2019
25、-8-23,归纳： 设n k时定理成立，来证n = k+1时定理也成立 n = k + 1 1, A中至少有一个联结词，可分为三种情形A = A1, A = A1A2, A = A1A2 其中A1, A2中联结词个数k。依归纳法假设，A1 = A1*, A2 = A2*,定理2.5.3 A = A*,58,谢谢观赏,2019-8-23,当 A = A1时 A = (A1) A = A1 = (A1*)归纳法假设 = (A1)*定理2.5.1, 2.5.2 = A* A = A1,定理2.5.3 A = A*,59,谢谢观赏,2019-8-23,当A = A1A2时， A = (A1A2) =
26、A1A2摩根律 = A1*A2*归纳法假设 = (A1*A2*)A定义 = (A1A2)* A*定义 = A*另一种情况同理，从而定理得证。,定理2.5.3 (摩根律) A = A*,60,谢谢观赏,2019-8-23,定理2.5.6 (1) A与A同永真, 同可满足 (2) A与A*同永真, 同可满足注：“A和B”同永真表示：A永真当且仅当B永真证明：设A是由命题变项P1,Pn构成的命题公式。(1) 如果A永真，根据代入规则，则A-永真。 如果A-永真，则(A-)-永真，又根据定理2.5.2有 A=(A-)-, 所以A永真(2) 根据定理2.5.3，A = A*，所以根据(1)可得(2)成立
27、,对偶式相关定理,61,谢谢观赏,2019-8-23,定理 2.5.4 若A = B，必有A*=B*证明: 因为A = B等价于AB 永真等价于AB永真。依定理2.5.3, A = A*, B = B* 于是A* B*永真，则(A*- B*-)-永真(根据代入规则，A永真，A-永真)亦即 A* B* 永真故 A* = B*,对偶式相关定理,62,谢谢观赏,2019-8-23,定理2.5.5 若AB永真, 必有B*A*永真或者，AB和B*A*同永真证明:(1) 如果AB永真，则BA永真(逆否命题)根据定理2.5.3，A= A*-, B= B*-所以B*-A*-永真，则(B*-A*-)-永真(代入
28、规则)，即B*A*永真(2) 如果B*A*永真，根据(1)有: (A*)*(B*)*永真根据定理2.5.2，A=(A*)*, B=(B*)*所以AB永真 ,对偶式相关定理,63,谢谢观赏,2019-8-23,作业(2),(P37) 3，4(2),64,谢谢观赏,2019-8-23,2.6 范式,n 个命题变项所能组成的具有不同真值的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个等值的公式，能否都可以化为某一个统一的标准形式？希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值借助于标准形容易判断任一公式是否
29、为重言式或矛盾式,65,谢谢观赏,2019-8-23,2.6.1 范式,若干术语简单命题P及其否定式P统称为文字一些文字的合取称为合取式一些文字的析取称为析取式(也称子句)P与P称为互补对析取范式，形如：A1A2 An其中Ai(i=1, , n)为合取式合取范式，形如： A1A2 An其中Ai(i=1, , n)为析取式,66,谢谢观赏,2019-8-23,67,范式举例,p, qp1p2 , q1q2,谢谢观赏,2019-8-23,范式定理,范式定理：任一命题公式都存在与之等值的析取范式、合取范式求范式三步曲：1) 消去和2) 否定深入到命题变项3) 使用分配律的等值变换,68,谢谢观赏,2
30、019-8-23,举例,求(PQ)(PQ)的析取范式(PQ)(PQ)=(PQ)(PQ)(PQ)(PQ)=(PQPQ)(PQ)(PQ)=(PQPQ)(PP)(PQ)(QP)(QQ) (析取范式)= (PQ)(QP) (析取范式，简化)注：范式的不唯一性,69,谢谢观赏,2019-8-23,举例,求(PQ)(PQ)的合取范式(PQ)(PQ)=(PQ)(QP) (析取范式，简化)=(PQ)(PP)(QQ)(QP)(合取范式)=(PQ)(QP) (合取范式，简化)注：已知一种范式，可以使用分配律求另一种范式,70,谢谢观赏,2019-8-23,判断重言式合取范式中所有析取式都有互补对 判断矛盾式析取范
31、式中所有合取式都有互补对 判断两公式是否等值范式不唯一，引入唯一的主范式，便于判别公式相等,范式功能,71,谢谢观赏,2019-8-23,2.6.2 主范式,主析取范式极小项定义与编码Q1Qn是由n个命题变项P1, , Pn组成的公式, 其中Qi=Pi或者Pi, 我们称其为极小项, 一般用mj表示例：P1, P2的极小项有四个P1 P2 (m0), P1 P2 (m1), P1 P2 (m2), P1P2 (m3)主析取范式定义 仅由极小项构成的析取范式主析取范式唯一性定理任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含这n个命题变项的主析取范式,极小项必须含有Q1, , Qn全部n个
32、文字,72,谢谢观赏,2019-8-23,由真值表写主析取范式：从T写P Q=(PQ)(PQ)=m0m3= 0,3由析取范式写主析取范式：填满命题变项法, 永真式P = P(QQ) = (PQ)(PQ) Q = Q(PP) = (QP)(QP)PQ = PQ = (PQ)(PQ) (QP)(QP) = (PQ)(PQ)(PQ) = m0m1m3 = 0,1,3,主析取范式,73,谢谢观赏,2019-8-23,所有可能极小项的个数：2n每个极小项只在一个解释下为真对于每个解释只有一个极小项为真 极小项互不相等，且mi mj=F (i j)任一含有n个变项的公式，都可由k个(k2n)极小项的析取来
33、表示；或者说所有的极小项可建立一个“坐标系”恰由2n个极小项的析取构成的公式，必为重言式 A与A的主析取范式关系A由k个极小项的析取组成，那么其余的2n-k个极小项的析取必是A例如P1, P2, P3构成的A= 0,2,4, A= 1,3,5,6,7,极小项性质,74,谢谢观赏,2019-8-23,主合取范式,极大项定义与编码Q1 Qn是由n个命题变项P1, , Pn组成的公式, 其中Qi=Pi或者Pi(i = 1, , n), 我们称其为极大项, 一般用Mj表示(0j2n-1)例：P1, P2的极大项有四个P1P2 (M0), P1P2 (M1), P1P2 (M2), P1P2 (M3)主
34、合取范式定义仅由极大项构成的合取范式主合取范式唯一性定理任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含这n个命题变项的主合取范式由真值表写主合取范式(从F写)由合取范式写主合取范式(填满命题变项法, 矛盾式),极大项必须含有Q1, , Qn全部n个文字,75,谢谢观赏,2019-8-23,极大项性质,所有可能极大项的个数：2n每个极大项只在一个解释下为假对于每个解释只有一个极大项为假 极大项互不相等，且Mi Mj=T (i j)任一含有n个变项的公式，都可由k个(k2n)极大项的合取来表示；或者说所有的极大项可建立一个“坐标系”恰由2n个极大项的合取构成的公式，必为矛盾式A与A的主合
35、取范式关系A由k个极大项的合取组成，那么其余的2n-k个极大项的合取必是A例如P1, P2, P3构成的A= 0,2,5, A= 1,3,4,6,7,76,谢谢观赏,2019-8-23,主析取范式与主合取范式的转换,设A是由命题变项P1, P2, P3构成的公式已知主析取范式A = 0,1,4,5,7 = (0,1,7-0,1,4,5,7)补 = 2,3,6补 = 5,4,1已知主合取范式A = 1,4,5 = (0,1,7-1,4,5补) = (0,1,7-6,3,2) = 0,1,4,5,7,77,谢谢观赏,2019-8-23,主析取范式与主合取范式的转换,注意从真值表列写公式的主析取范式
36、和主合取范式时，除了分别从T和F列写外，在填写合取式和析取式时是取变项还是其否定是有区别的，这就是主合取范式、主析取范式转换过程要求补的原因数字补不同于补集。这里的数字求补是对2n-1=23-1=7而言的，如2的补是5，因为2+5=7,78,谢谢观赏,2019-8-23,主范式的用途与真值表相同,(1) 求公式的成真赋值和成假赋值例如：(PQ)R m1m3m5 m6m7，其成真指派为001, 011, 101, 110, 111，其余的指派 000, 010, 100为成假指派. 类似地，由主合取范式也可立即求出成假指派和成真指派,79,谢谢观赏,2019-8-23,主范式的用途(续),(2)
37、 判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为TA为矛盾式 A的主析取范式为F A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项,80,谢谢观赏,2019-8-23,主范式的用途(续),判断两个公式是否等值例 用主析取范式判断下述两个公式是否等值： P(QR) 与 (PQ)R P(QR) 与 (PQ)R解 P(QR) = m0m1m2m3m4m5m7 (PQ)R = m0m1m2m3m4m5m7 (PQ)R = m1m3 m4m5 m7显见，中的两公式等值，
38、而的不等值.,81,谢谢观赏,2019-8-23,作业(3),(P37) 5(1，5，8),82,谢谢观赏,2019-8-23,2.7 推理形式,自然语言推理前提1：如果我今天病了，那么我没来上课前提2：今天我病了结论：所以今天我没来上课推理形式引入符号, 形式化并用条件式表示出来例：(PQ)P)Q正确的推理形式前提真，结论必真的推理形式(PQ)Q)P 正确的推理形式(PQ)P)Q 不正确的推理形式,83,谢谢观赏,2019-8-23,重言蕴涵,重言蕴涵对于公式A, B, 如果当A取值为真时，B必取值为真，则称A重言(永真)蕴涵B，或称B是A的逻辑推论。记为： A B(是真值关系，并非逻辑联结
39、词)重言蕴涵与正确推理形式如果A B，则AB是正确的推理形式如果AB是正确的推理形式，可以用A B来表示用真值表法判断A B查看真值表，如果所有使A为真的解释，亦能使B为真，则A B,84,谢谢观赏,2019-8-23,如果A B, A为重言式, 则B也是重言式 如果A B, B A同时成立, 必有A = B如果A = B, 必有A B和B A 如果A B, B C, 则A C 如果A B, A C, 则A BC 如果A C, B C, 则AB C,重言蕴涵的结果,85,谢谢观赏,2019-8-23,2.8 基本的推理公式,1. (PQ) P化简律2. (PQ) P 3. (PQ) Q4. P
40、 (PQ)附加律 5. P PQ6. Q PQ7. (PQ)P Q 析取三段论8. (PQ)P Q 假言推理、分离规则,86,谢谢观赏,2019-8-23,9. (PQ)Q P 拒取式10. (PQ)(QR) (PR) 假言三段论、三段论11. (PQ)(QR) (PR)等价三段论12. (PR)(QR)(PQ) R 构造性二难(特殊形式)13. (PQ)(RS)(PR) (QS)构造性二难14. (PQ)(RS)(Q S) (PR) 破坏性二难15. (QR) (PQ)(PR)16. (QR) (PQ)(PR)注：真值表证明，或者语义上直接说明,基本的推理公式,87,谢谢观赏,2019-8-
41、23,2.8.2 证明推理公式的方法(五种),A B成立的充分必要条件是AB(或AB) 为重言式证明：如果A B, 那么在任一解释下, A真B必真, 而不会出现A真B假的情况, 于是AB为重言式。如果AB为重言式, 则在任一解释下, 若A为真, B只能为真不可能为假, 从而有A B证明AB为重言式的方法真值表、等值演算、范式,88,谢谢观赏,2019-8-23,例1 用等值演算法证明(PQ)PQ为重言式 (PQ)PQ (PQ)P)Q(PQ)P)Q QPQ T,举例,89,谢谢观赏,2019-8-23,例2 用主析取范式法证明(PQ)QP不是重言式 (PQ)QP (PQ)Q)P(PQ)Q)P (
42、吸收律)QP(QP)(QP)(PQ)(PQ) (PQ)(PQ)(PQ) m0m2m3缺少m1即(PQ), 所以(PQ)QP不是重言式，或者说推理形式(PQ)QP不正确,举例,90,谢谢观赏,2019-8-23,2. AB成立的充分必要条件是AB为重言式, 即AB是矛盾式3. (逆否定理) AB成立的充分必要条件B A4. 解释法例: (PQ)(QR) (PR)若(PQ)(QR)T, 则同时有PQT, QR=T若P=T, 则Q=T, 进而R=T. 故PRT若P=F, 则Q可取任意值: (1) Q=T, 则R=T; (2) Q=F, 则R取何值无论如何, PR=T5. 真值表法, 即通过真值表检验
43、A为真时B一定为真注： 证明AB时不考虑A为假的情况,证明推理公式的方法,91,谢谢观赏,2019-8-23,上述方法的特点,都是从真值的角度进行论证和解释看不出由前提A到结论B的推演过程难于扩展到谓词逻辑的推演过程,92,谢谢观赏,2019-8-23,2.9 推理演算(证明推理公式AB的新方法),基本思想：从前提A1, , An出发(即A= A1A2 An)运用推理规则和基本推理公式，逐步推演出结论B，即证明AB推理规则前提引入规则推理过程中可以随时引入前提A1, , An结论引用规则推理过程中得到的中间结论可作为后续推理的前提代入规则(参考P8)推理过程中对重言式的命题变项可使用该规则,9
44、3,谢谢观赏,2019-8-23,推理规则,置换规则(参考P18)推理过程中命题公式中任何部分公式都可由与之等值的公式置换分离规则(假言推理)已知命题公式AB和A, 则有命题公式B(B被分离出来)条件证明规则(附加前提)A1 A2B与A1A2 B是等价的。即结论方的条件A2移到了前提方, 作为条件使用。,94,谢谢观赏,2019-8-23,例1 证明R是PQ, QR, P的逻辑推论 特点: 前提引入规则、分离规则例2 证明RS可以由前提CD, (CD)E, E(AB ), (AB)RS推演出来特点: 基本推理公式(三段论)例3 证明(PQ)(PR)(QS) SR特点: 置换规则例4 证明(P(
45、QS)(RP)Q RS特点: 条件证明规则(附加前提引入)例5 证明 (PQ)(RS)(QP)R)R (PQ)特点: 反证法、条件证明、结论引入,举例,95,谢谢观赏,2019-8-23,2.10 归结推理法(证明推理公式AB的新方法),特点定理机器证明方法只有一条归结推理规则易于机器实现可推广到谓词逻辑推理基本思想证明AB等价于证明AB是矛盾式用反证法, 即假设AB在某种解释下为真, 最后导出矛盾, 得以证明,96,谢谢观赏,2019-8-23,归结证明过程,从AB出发建立子句集S将AB化为合取范式, 每个析取式均作为一个子句, 构成这些子句的集合, 记为S对S作归结即用归结推理规则消互补对
46、, 将得到的新的归结式放入S中，重复此过程直至归结出矛盾, 结束即出现P与P,97,谢谢观赏,2019-8-23,归结推理规则,归结式定义设R1=PQ1, R2=PQ2为两个子句有互补对P和P则新子句R(R1, R2)= Q1Q2称为R1, R2的归结式推理规则 R1R2 R(R1, R2)设在任一解释下, R1R2=T, 则R1=T且R2=T若P=T, 则P=F, Q2=T, R(R1, R2)= Q1Q2=T若P=F, 则P=T, Q1=T, R(R1, R2)= Q1Q2=T若Q1=T或者Q2=T, 都有R(R1, R2)= Q1Q2=T,98,谢谢观赏,2019-8-23,举例,证明(PQ)(QR) (PR)1. 将(PQ)(QR) (PR)化成合取范式(PQ)(QR) P R2. 建立子句集S=PQ, QR, P, R3. 归结过程(1)PQ(2)QR (3)P(4)R(5)PR (1)(2)归结，新子句(6)R(3)(5)归结(7)(4)(6)归结,99,谢谢观赏,2019-8-23,作业(4),(P37) 7(10,11), 9(1), 12(1),100,谢谢观赏,2019-8-23,
