命题逻辑的等值和推理演算.ppt
《命题逻辑的等值和推理演算.ppt》由会员分享,可在线阅读,更多相关《命题逻辑的等值和推理演算.ppt(100页珍藏版)》请在三一文库上搜索。
1、第二章 命题逻辑的等值和推理演算,推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的 推理过程是从前提出发,根据所规定的规则来推导出结论的过程 重言式是重要的逻辑规律,正确的推理形式、等值式都是重言式,本章对命题等值和推理演算进行讨论,是以语义的观点进行的非形式的描述,不仅直观且容易理解,也便于实际问题的逻辑描述和推理。 严格的形式化的讨论见第三章所建立的公理系统。,等值演算(考察逻辑关系符(=),等值定理、公式 联结词的完备集(由个别联结词表示所有联结词的问题) 对偶式(命题公式的对偶性) 范式(命题公式的统一标准) 由真值表写命题公式(由T写、由F写),推
2、理演算(考察逻辑关系符),推理形式(正确推理形式的表示) 基本推理公式(各种三段论及五种证明方法) 推理演算(证明推理公式的第六种方法,使用推理规则) 归结推理法(证明推理公式的第七种方法,常用反证法),2.1 等值定理,若把初等数学里的、等运算符看作是数与数之间的联结词,那么由这些联结词所表达的代数式之间,可建立许多等值式如下: x2y2 = (xy)(xy) (xy)2 = x22xyy2 sin2xcos2x = 1 在命题逻辑里也同样可建立一些重要的等值式,2.1.1 等值的定义,给定两个命题公式A和B, 而P1Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对
3、其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或AB 显然,可以根据真值表来判明任何两个公式是否是等值的,例1: 证明(PP)Q = Q,证明: 画出(PP)Q与Q的真值表可看出等式是成立的。,例2: 证明PP = QQ,证明: 画出PP, QQ的真值表, 可看出它们是等值的, 而且它们都是重言式。,从例1、2还可说明, 两个公式等值并不一定要求它们一定含有相同的命题变项 若仅在等式一端的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。 例1中公式(PP)Q与Q的真值都同P无关 例2中PP, QQ都是重言式, 它们的真值也都与P、Q无关。,
4、说明,2.1.2 等值定理,定理 对公式A和B, A=B的充分必要条件是AB是重言式。 A、B不一定都是简单命题, 可能是由简单命题P1, , Pn构成的. 对A, B的一个解释, 指的是对P1, , Pn的一组具体的真值设定. 若AB为重言式, 则在任一解释下A和B都只能有相同的真值, 这就是定理的意思。,证明,若A B是重言式, 即在任一解释下, A B的真值都为T 依A B的定义只有在A、B有相同的值时, 才有A B = T。于是在任一解释下, A和B都有相同的真值, 从而有A=B。 反过来,若有A = B, 即在任一解释下A和B都有相同的真值, 依A B的定义, A B只有为真, 从而
5、A B是重言式。 注:根据该等值定理,证明两个公式等值,只要证明由这两个公式构成的双条件式是重言式即可,“”作为逻辑关系符是一种等价关系,不要将“”视作联结词,在合式公式定义里没有“”出现 A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性 A = A 2. 对称性 若A = B, 则B = A 3. 传递性 若A = B, B = C, 则A = C 这三条性质体现了“”的实质含义。,2.2 等值公式,2.2.1 基本的等值公式(命题定律, P和Q是任意的命题公式) 1. 双重否定律 P = P 2. 结合律 (PQ)R = P(QR) (PQ)R = P(QR) (
6、P Q) R = P (Q R) 注: 所有这些公式,都可使用真值表加以验证,3. 交换律 PQ = QP PQ = QP P Q = Q P 4. 分配律 P(QR) = (PQ)(PR) P(QR) = (PQ)(PR) P(QR) = (PQ)(PR) 5. 等幂律(恒等律) PP = P PP = P PP = T PP = T,6. 吸收律 P(PQ) = P P(PQ) = P 7. 摩根律 (PQ) = PQ (PQ) = PQ 对蕴涵词、双条件词作否定有 (PQ) = PQ (PQ) = PQ = PQ = (PQ)(PQ),8. 同一律 PF = P PT = P TP =
7、P TP = P 还有 PF = P FP = P,9. 零律 PT = T PF = F 还有 PT = T FP = T 10. 补余律 PP = T PP = F 还有 PP = P PP = P PP = F,Venn图(理解等式),将P、Q理解为某总体论域上的子集合,并规定: PQ为两集合的公共部分(交集合) PQ为两集合的全部(并集合) P为总体论域(如矩形域)中P的余集,Venn图(理解等式),从Venn 图,因PQ较P来得“小”, PQ较P来得“大”,从而有 P(PQ) = P P(PQ) = P,理解等式: Venn图,自然语言,(PQ) = PQ Venn图(理解集合间、命
8、题逻辑中、部分信息量间的一些关系) 对这些等式使用自然用语加以说明,将有助于理解 如P表示张三是学生, Q表示李四是工人, 那么(PQ)就表示并非“张三是学生或者李四是工人”。这相当于说,“张三不是学生而且李四也不是工人”,即可由PQ表示, 从而有(PQ) = PQ,2.2.2 常用的等值公式,由于人们对、更为熟悉,常将含有和的公式化成仅含有、的公式。这也是证明和理解含有,的公式的一般方法 公式11-18是等值演算中经常使用的, 也该掌握它们, 特别是能直观地解释它们的成立,11. PQ = P Q,通常对PQ进行运算时, 不如用PQ来得方便。而且以PQ表示PQ帮助我们理解如果P则Q的逻辑含义
9、 问题是这种表示也有缺点,丢失了P、Q间的因果关系,12. PQ = QP,逆否定理,假言易位 如将PQ视为正定理, 那么QP就是相应的逆否定理, 它们必然同时为真, 同时为假, 所以是等值的,13. P(QR) = (PQ)R,前提合并 P是(QR)的前提, Q是R的前提, 于是可将两个前提的合取PQ作为总的前提。 即如果P则如果Q则R, 等价于如果P与Q则R,14. PQ = (PQ)(PQ),从取真来描述双条件 这可解释为PQ为真, 有两种可能的情形, 即(PQ)为真或(PQ)为真。而PQ为真, 必是在P = Q = T的情况下出现; PQ为真, 必是在P = Q = F的情况下出现。从
10、而可说, PQ为真, 是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式,15. PQ = (PQ)(PQ),从取假来描述双条件 这可解释为PQ为假, 有两种可能的情形, 即(PQ)为假或(PQ)为假, 而PQ为假, 必是在P = F, Q = T的情况下出现; PQ为假, 必是在P = T, Q = F的情况下出现。从而可说PQ为假, 是在P真Q假或P假Q真时成立。这就是从取假来描述这等式,16. PQ = (PQ)(QP),从蕴含词来描述双条件 这表明PQ成立, 等价于正定理PQ和逆定理QP都成立,17. P(QR) = Q(PR),前提交换 前提条件P、Q可交换次序,18. (
11、PR)(QR)=(PQ)R,左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立, 这就是等式右端,补充,等价否定等值式 PQ = PQ 归谬论 (PQ)(PQ) = P,2.2.3 置换规则,置换定义 对公式A的子公式, 用与之等值的公式来代换便称置换 置换规则 公式A的子公式置换后A化为公式B, 必有A = B 当A是重言式时, 置换后的公式B必也是重言式 置换与代入是有区别的。置换只要求A的某一子公式作代换, 不必对所有同一的子公式都作代换,代入规则回顾,A是一个公式,对A使用代入规则得公式B,若A是重言式,则B也是重言式 为保证重言式经代入规则仍得到保持,要求 公式中被代换
12、的只能是命题变元(原子命题), 而不能是复合命题 对公式中某命题变元施以代入,必须对该公式中出现的所有同一命题变元代换以同一公式,2.2.4 等值演算举例,例1: 证明(P(QR)(QR)(PR) = R 证明: 左端= (P(QR) (QP)R) (分配律) = (PQ)R)(QP)R) (结合律) = (PQ)R)(QP)R) (摩根律) = (PQ)(QP)R (分配律) = (PQ)(PQ)R (交换律) = TR (置 换) = R (同一律),例2: 试证 (PQ)(P(QR) (PQ)(PR) = T 证明: 左端=(PQ)(P(QR)(PQ)(PR) (摩根律) =(PQ)(P
13、Q)(PR)(PQ)(PR) (分配律) =(PQ)(PR)(PQ)(PR) (等幂律) =T,举例,问题提出: 由命题公式写真值表是容易的,那么如何由真值表写命题公式呢?,2.3 命题公式与真值表关系,2.3.1 从T来列写,记忆方法:各项间用,每项内用 每项内书写方法:例 真值表中P=T且Q=F等价于PQ=T 简化方法:有时A的表达通过A来描述,2.3.2 从F来列写,记忆方法:各项间用 ,每项内用 每项内书写方法:例 真值表中P=T且Q=F等价于PQ=F 简化方法:有时A的表达通过A来描述,举例,从A的真值T 直接: A = (P Q) (P Q) (P Q) 间接: A = A = (
14、P Q) = P Q 从B的真值F B = (P Q) (P Q) 当C可取任意值 C与P, Q = T, T无关, 可适当选取C的真值, 使其表达式简单,作业(1),(P37) 1(1, 3), 2,2.4 联结词的完备集,问题的提出 对n 个命题变项P1Pn来说, 共可定义出多少个联结词? 在那么多联结词中有多少是相互独立的? 3个新联结词:,思考:考虑异或联结词与双条件联结词的关系(可利用真值表),2.4.1 命题联结词的个数,第一个问题。可定义多少个联结词? 由命题变项和命题联结词可以构成无限多个合式公式 把所有的合式公式分类:将等值的公式视为同一类,从中选一个作代表称之为真值函项。对
15、一个真值函项,或者说对于该类合式公式,就可定义一个联结词与之对应 例:等价类。自然数集合N被3除余数相同的自然数构成3个集合N0 , N1 , N2,一元联结词是联结一个命题变项(如P)的 P有真假2种值,因此P(自变量)上可定义4种一元联结词fi 或说真值函项fi(P), i = 1, 2, 3, 4,一元联结词的个数,由真值表写出真值函项的命题公式: f0(P) = F (永假式) f1(P) = P (P自身) f2(P) = P(否定词) f3(P) = T (永真式) 新的公式只有f2(P), 与之对应的联结词是否定词,一元联结词,二元联结词联结两个命题变项(如P、Q) 两个变项共有
16、4种取值情形,于是P、Q上可建立起16种不同的真值函项,相应的可定义出16个不同的二元联结词g0, g1, , g15 图2.4.2给出了这些联结词gi或说真值函项gi(P,Q)的真值表定义,二元联结词的个数,根据真值表写出各真值函项的命题表达式: g0(P,Q) = F (永假式) g1(P,Q) = PQ (合取式) g2(P,Q) = PQ g3(P,Q) = (PQ)(PQ) = P(QQ) = P g4(P,Q) = PQ g5(P,Q) = (PQ)(PQ) = (PP)Q = Q g6(P,Q) = P Q (异或式) g7(P,Q) = PQ (析取式) g8(P,Q) = P
17、Q = P Q (或非式) g9(P,Q) = P Q (双条件式) g10(P,Q) = (PQ)(PQ) = (PP)Q = Q g11(P,Q) = PQ = QP (蕴涵式) g12(P,Q) = (P Q)(PQ) = P(QQ) = P g13(P,Q) = PQ = PQ (蕴涵式) g14(P,Q) = PQ = P Q (与非式) g15(P,Q) = T (永真式),n元联结词 对n个命题变元P1 , , Pn , 每个Pi有两种取值, 从而对P1Pn来说共有2n种取值情形 于是相应的真值函项就有22n个, 或说可定义22n个n元联结词,n元联结词的个数,2.4.2 联结词
18、的完备集,第二个问题。联结词是否都是独立的,或者说能否相互表示? 联结词的完备集定义: 设C是联结词的集合,如果对任一命题公式(能直接使用T和F)都有由C中的联结词表示出来的公式(不能直接使用T和F)与之等值,就说C是完备的联结词集合,或说C是联结词的完备集。,1. 全体联结词的无限集合是完备的 2. , , 是完备的联结词集合 证明:从2.3节介绍的由真值表列写逻辑公式的过程可知, 任一公式都可由, , 表示出来, 从而, , 是完备的 3. , 是联结词的完备集(独立的完备集) 证明:PQ = (PQ),因此可由, 表示 4. , 是联结词的完备集(独立的完备集) 证明:PQ = (PQ)
19、,因此可由, 表示,完备集,5. , 是完备集(独立的完备集) 因为:PQ = PQ 6. 是完备集(独立的完备集) 7. 是完备集(独立的完备集) 8. , , , , 是完备的 因为它包含了2中的集合,完备集, 不是完备的 因为F不能仅由该集合的联结词表达出 , 不是完备的 , 的任何子集都是不完备的 , 的任何子集也是不完备的 (如果一个联结词的集合是不完备的,那么它的任何子集都是不完备的) ,不是完备的,不完备集,最小的联结词的完备集基底,基底:完备的联结词集合的联结词是独立的,也就是说这些联结词不能相互表示 任取四个一元或二元联结词,它们必组不成基底,基底,只含一个联结词的: NK;
20、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- ,2.5 对偶式,研究目的 简化等值公式的讨论 希望一个公式成立,能够导出与其“相像”的公式成立 逻辑关系上看,是一种逻辑规律 对偶式定义:将A中出现的、T、F分别以、F、T代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式 注:这里假定A中仅出现 、三个联结词 若A = B,必有A*=B*?,新符号“-”: (
21、代入规则、内否式) 若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* (摩根律的另一种形式) 更多:(A B)* = A* B*,(A B)- = A- B- (A B)* = A* B*,(A B)- = A- B-,对偶式相关定理,56,性质举例,A= (P (Q R) T A*= (P (Q R) F A-= (P) (Q R) T A*- = (P) (Q R) F A-* = (P) (Q R) F,定理2.5.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 命题逻辑 等值 推理 演算
链接地址:https://www.31doc.com/p-4146201.html