第二章 命题逻辑.ppt

1、第二章 命题逻辑,数理逻辑,数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，数理逻辑一般又称为符号逻辑。 数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。 古典数理逻辑：命题逻辑和谓词逻辑是计算机科学很重要的数学基础。 现代数理逻辑：逻辑演算、证明论、公理集合论、递归论和模型论 。,数理逻辑的创始人-莱布尼茨 (Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14,德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研

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

3、的先驱者。Leibniz(16461716年) 之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。 1693年，发现了机械能的能量守恒定律。 与牛顿并称为微积分的创立者。 系统阐述了二进制记数法，并把它和中国的八卦联系起来。,第二章 命题逻辑,2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 2.5 命题逻辑在二值逻辑器件 和语句逻辑中的应用,2.1 命题以及逻辑联结词,1 命题,所谓命题是指一句有真假意义的话。 例如：上海是中国最大的城市今天是星期二所有素数都是奇数1+1=2 命题用大写英文字母P，Q，

4、P1，P2，表示。,下列句子中不是命题的有( ),A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起，你就可以长生不老。 E. 别的星球上有生物。 F. 几点了？ G. 1960年长春春城电影院放映了国产故事片“白毛女”。 H. 1+101=110 I. 全体起立！ J. 这个教室好大呀!,如果一个命题是真的，就说它的真值是1； 如果一个命题是假的，就说它的真值是0。 也用“1”代表一个抽象的真命题，用“0”代表一个抽象的假命题。,2 逻辑联结词 定义2.1.1,设P是一个命题，命题 “P是不对的”称为P的否定，记以P，读作非P。 真值规定：P是真的当且仅

5、当P是假的。 例. P：吉大是中国最大的大学。 P：吉大不是中国最大的大学。 Q:张三是好人 Q ：张三不是好人,定义2.1.2,设P，Q是两个命题，命题 “P或者Q”称为P，Q的析取，记以PQ，读作P或Q。 真值规定： PQ是真的当且仅当P，Q中至少有一个是真的。 例. P：今天下雨，Q：今天刮风， PQ：今天下雨或者刮风。,定义2.1.3,设P，Q是两个命题，命题 “P并且Q”称为P，Q的合取，记以PQ，读作P且Q。 真值规定： PQ是真的当且仅当P和Q都是真的。 例. P：22=5，Q：雪是黑的， PQ：22=5并且雪是黑的。,注意：,自然语言中的“或者”一词有两种用法：1) “张三或者

6、李四考了90分”, 表示两者可以同时成立。这是“可兼或”。 按照联结词“”的定义，当P，Q都为真时，PQ也为真，因此，“”所表示的“或”是“可兼或”。,2) “我明天到北京出差或者到广州去度假”，表示的是二者只能居其一，不会同时成立。这是“不可兼或”。 “不可兼或” 不可以用来表示. 表示为：(PQ) ( PQ) 异或,判断： （1）今天晚上我在家中看戏或去剧场看戏。 （2）他可能是100米或400米冠军。 （3）我第一节课上数学课或上英语课。 （4）李梅是三好学生或优秀团员。 （5）张三生于1987年或1988年。 （6）老王或小李有一个去上海出差。 （7）李明是软件学院的学生，他住在312

7、室或313室。,定义2.1.4,设P，Q是两个命题，命题 “如果P，则Q”称为P蕴涵Q，记以PQ。 真值规定： PQ是假的当且仅当P是真的而Q是假的。 例. P：f(x)是可微的，Q：f(x)是连续的， PQ： 若f(x)是可微的，则f(x)是连续的。,由定义知，如果P是假命题，则不管Q是什么命题，命题 “如果P，则Q”在命题逻辑中都被认为是真命题。 与自然语言不一样的地方 例. P： 22=5，Q： 雪是黑的， 于是，命题 “如果22=5，则雪是黑的”是真命题。,定义2.1.5,设P，Q是两个命题，命题 “P当且仅当Q”称为P等价Q，记以PQ。 真值规定： PQ是真的当且仅当P，Q或者都是真

8、的，或者都是假的。 例如， P ： a2+b2=a2， Q： b=0， PQ： a2+b2=a2当且仅当b=0 。,例2.1.1,如果你走路时看书，那么你会成为近视眼。 令P：你走路；Q：你看书； R：你会成为近视眼。 于是，上述语句可表示为（PQ）R。,例2.1.2,除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。 令P：他书面通知我； Q：他口头通知我； R：我参加明天的会议。 于是，上述语句可表示为(PQ)R。,例2.1.3,设P，Q，R的意义如下： P：苹果是甜的；Q：苹果是红的； R：我买苹果。 试用日常语言复述下述复合命题： (1) (PQ)R (2) (PQ)R 解：

9、(1)如果苹果甜且红，那么我买;(2)我没买苹果，因为苹果不甜也不红.,2.2 命题公式,1 公式,我们用大写的英文字母P，Q，R，等代表一个抽象的命题，或称为命题符号。 定义2.2.1 命题符号称为原子。 例如，Q，S，等都是原子。,定义2.2.2 命题公式,命题逻辑中的公式，是如下定义的一个符号串：(1) 原子是公式；(2) 0、1是公式； (3) 若G，H是公式，则(G)，(GH)， (GH)，(GH)，(GH)是公式；(4) 所有公式都是有限次使用(1)，(2)，(3) 得到的符号串。,规定：,公式(G)的括号可以省略，写成G。 整个公式的最外层括号可以省略。 五种逻辑联结词的优先级按

10、如下次序递增： ， 例如，我们写符号串 PQRQSR 就意味着是如下公式： (P(QR)(Q(S)R),2 解释,定义2.2.3 设G是命题公式，A1, , An是出现在G中的所有原子。 指定A1, , An的一组真值，则这组真值称为G的一个解释。 设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。,例,G=PQ，设解释I，I如下： I： I： 则TI (G)=1，TI (G)=0 注意：该例子中写成G=1或G=0是错误的！,定义2.2.4,公式G在其所有可能的解释下所取真值的表，称为G的真值表。 显然，有n个不同原子的公式，共有2n个解释。,例：G=(PQ)R，其真值表

11、如下：,练习：请画出 P ， PQ， PQ， PQ，PQ的真值表。,若公式G中出现的所有原子为A1，An，有时我们用m1，mn表示G的一个解释I，其中 例.公式G=(PQ)R的真值表中第二个解释就可以记为P，Q，R,定义2.2.5,公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的； 公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的； 公式G称为可满足的，如果它不是恒假的。,考虑G1= (PQ) P，G2=(P Q) P，G3=P P。,从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。,练习：用真值表判断公式 （

12、PQ）（Q R）（PR）的类型,G是恒真的 iff G是恒假的。 G是可满足的 iff 至少有一个解释I，使G在I下为真。 若G是恒真的，则G是可满足的； 反之不对。 如果公式G在解释I下是真的，则称I满足G； 如果G在解释I下是假的，则称I弄假G。,练习：求满足公式（ P Q ）P Q的解释和弄假它的解释。,在逻辑研究和计算机推理以及决策判断中，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以恒真公式在数理逻辑研究中占有特殊且重要的地位。,3 判定问题,能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。 因为一个命题公式的原子数目有限(n)，从而解释的数目是有限的(2n)

13、，所以命题逻辑的判定问题是可解的(可判定的，可计算的). 结论:命题公式的恒真，恒假性是可判定的.,作业: 习题2.1-3，习题2.2-1、3、4下周二（年月日）交,2.3 命题公式的等价关系 和蕴涵关系,1 公式的等价,定义2.3.1 称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。 公式G，H等价 iff 公式GH恒真。 公式间的等价关系有自反性、对称性、传递性。,基本等价式,1) (GH)=(GH)(HG)； 2) (GH)=(GH)； 3) GG=G，GG=G； (等幂律) 4) GH=HG，GH=HG； (交换律) 5) G(HS)=(GH)S， G(HS)

14、=(GH)S； (结合律),6) G(GH)=G，G(GH)=G； (吸收律) 7) G(HS)=(GH)(GS)， G(HS)=(GH)(GS)； (分配律) 8) G0=G，G1=G； (同一律) 9) G0=0，G1=1； (零一律) 10) (GH)=GH， (GH)=GH。 (De Morgan律) （互补律： G G=1；G G=0双重否定律： G=G ） 上述等价式可用真值表验证。,证明命题公式恒真或恒假的两个方法,方法一. 真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0

15、，这说明该公式在它的所有解释下都为假，因此是恒假的。,方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例.（PQ）（Q R）（PR） = ( P Q) ( Q R) ( P R) = (P Q) (Q R) ( P R) = (P Q) (Q P R) (R P R) = (P Q) ( (Q P R) 1) = (P Q) (Q P R) =(P Q P R) (Q Q P R) =1 1=1,应用基本等价式的例子,例. （ P Q ） P Q = ( P Q) (P Q) = (P Q) (P Q) = P (

16、Q Q) =P 1=P,例. 证明： (P Q) (P R) (Q R)=(PQ)(P R) 证明： 左= (P Q) (P R) (PP)(QR)） = (P Q) (P R) (PQR) (PQR) =(PQ)(PQR)(PR)(PRQ) =(PQ)(P R) =右,练习： 证明： P （Q R）= P Q R 问： （P Q）R与P Q R是否等价？,例.世界冰球赛正在激烈进行，看台上三位观众 正在热烈地议论着这次比赛的名次。 甲：中国第一，匈牙利第三 乙：奥地利第一，中国第三 丙：匈牙利第一，中国第二 比赛结束后，发现这三位观众每人恰好都猜对了 一半。假设无并列名次。 问：中国、奥地利

17、、匈牙利各队的名次。 解： 设P1:中国第一； P2:中国第二； P3:中国第三Q1:奥地利第一R1:匈牙利第一； R3:匈牙利第三,由于甲、乙、丙个猜对一半，故有： （P1 R3） ( P1 R3)=1 (1) （Q1 P3） ( Q1 P3)=1 (2) （R1 P2） ( R1 P2)=1 (3) 无并列名次： P1Q1=0， P1R1=0，Q1R1=0，P3R3=0 （*） 每个国家只能得一个名次： P1P2=0，P1P3=0，P2P3=0，R1R3=0 （*）,(1)(2)左边合取，利用（*）（*）化简得： P1 R3 Q1 P3 (4) (4)(3)左边合取，利用（*）（*）化简得

18、： P1 R3 Q1 P3 R1 P2 而右边合取得1。 由此得出结论： 奥地利第一，中国第二，匈牙利第三,2 完备集 定义2.3.2 完备集,设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。 可以证明，都是完备集。,证明 ， 是完备集,证明： PQ = ( P Q) PQ = PQ= (PQ) PQ = (PQ) (QP) = ( P Q) ( Q P) = (P Q) (QP),定义2.3.3 与非式,设P，Q是两个命题，命题 “P与Q的否定”称为P与Q的与非式，记作PQ。 “”称作与非联结词。 真值规定:PQ为真 iff P,Q

19、不同时为真。 由定义可知： PQ=(PQ)。,定义2.3.4 或非式,设P，Q是两个命题，命题 “P或Q的否定”称为P与Q的或非式，记作PQ， 称作或非联结词。 真值规定：PQ为真 iff P，Q同时为假。 由定义可知： PQ=(PQ),是完备集,P = (P P) =PPPQ = ( P Q)= (P) (Q) =(PP)(QQ) PQ= （PQ）= (PQ)= (PQ) (PQ)=(PQ)(PQ) 读者可以自己证明也是完备集。,3 公式的蕴涵,逻辑的一个重要功能是研究推理。固然，依靠等价关系可以进行推理。但是，进行推理时，不必一定要依靠等价关系，只需蕴涵关系就可以了。 例.若三角形等腰，则

20、两底角相等， 这个三角形等腰， 所以，这个三角形两底角相等。例.若行列式两行成比例，则行列式值为0， 这个行列式两行成比例， 所以，这个行列式值为0。,上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为： 若P则Q，P，所以Q。 推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴涵关系。,定义2.3.5 蕴涵,设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。,定义2.3.5 蕴涵,注意： 符号“”和“=” 一样，它们都不是逻辑联结词，因此

21、，G=H，GH也都不是公式。是一种部分序关系。 公式G蕴涵公式H iff 公式GH是恒真的。 例. (PQ)P，(PQ)Q,GH当且仅当GH是恒真的,证明：必要性，任取G, H的解释I， 若I满足G（ TI(G)=1），则由GH知， TI(H)=1 ，因此TI(GH)=1； 若I弄假G(TI(G)=0)，则TI(GH)=1 。 从而，对G, H的任意解释I，都有GH为 真， 故GH是恒真的. 充分性，任取G, H的解释I，若TI(G)=1，由 GH恒真，知， TI(H)=1。从而有GH。,是一种部分序关系,证明：要证明公式间的蕴涵关系是部分序关系，需要证明其具有自反性、反对称性和传递性。 自反

22、性：任取公式G，有G G 恒真，因此， G G。 反对称性：若G H，H G，则G H，H G恒真，从而, (G H) (H G)恒真，即，G H恒真，故G=H。,是一种部分序关系,传递性：若GG1，G1H，则对G, G1, H的任意解释I，若I满足G，则由GG1知，I满足G1，再由G1H知，I满足H。因此，GH。,定义2.3.6,设G1, , Gn，H是公式。 称H是G1, ,Gn的逻辑结果(或称G1, , Gn共同蕴涵H)，当且仅当 (G1 Gn) H。 显然，公式H是G1, , Gn的逻辑结果 iff公式(G1 Gn)H)是恒真的。 例如，P，PQ共同蕴涵Q。,定理2.3.1,如果H1,

23、 , Hm，P共同蕴涵公式Q，则H1, , Hm共同蕴涵公式PQ。例. 因为公式PQ，QR，P共同蕴涵R，所以PQ，QR共同蕴涵PR。,定理2.3.1,证明：因为(H1 HmP)Q，所以公式(H1 HmP)Q是恒真的。 利用下面的基本等价公式： P1(P2P3)=(P1P2)P3 于是，(H1 HmP)Q=(H1 Hm)(PQ)。 故(H1 Hm)(PQ)是恒真的。 所以H1，Hm共同蕴涵PQ。,4 演绎,定义2.3.7 设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列： G1, G2, , Gk 其中，Gi （1i k）或者属于S，或者是某些 Gj (ji)

24、的逻辑结果。 并且 Gk就是G。 称公式G为“此演绎的” 逻辑结果，或称从S演绎出G。 有时也记为SG。,例,设S=PQ，QR，PM，M 则下面的公式序列: M，PM，P，PQ，Q，QR，R 就是从S推出R的一个演绎。,5 演绎方法的可靠性与完备性,引理 设G，H1，H2是公式。 如果GH1，GH2，则G(H1 H2) 。 证明：任取G，H1，H2的一个解释I。 若I满足G，由假设知，H1, H2都是G的逻辑结果，从而I满足 H1，而且I满足H2，故I满足 H1 H2。由I的任意性，知，G (H1 H2)。,定理2.3.2,设S是公式集合，G是一个公式。于是，从S演绎出G的充要条件是G是S的逻

25、辑结果。 证明：必要性，设从S演绎出G，令 G1，Gk（即是G） 是这个演绎。 对任意 Gi (i=1，k)，往证Gi 是S的逻辑结果。 对i用归纳法: (1) 当i=1时，因G1S，显然, G1 G1 是恒真公式，故S G1 ，即 G1 是S的逻辑结果。,(2) 设in时，命题成立。 (3) 当i=n时， 若 GnS，则S Gn，归纳法完成. 若Gn是某些Gj (jn)的逻辑结果，不妨设 (Gj1 Gjh )Gn (1) 其中j1，jh都小于n。 由归纳假设知，SGjm ，m=1，h。由引理知：S( Gj1 Gjh ) (2) 根据(1)，(2)式及蕴涵关系的传递性，得 S Gn 即Gn是S

26、的逻辑结果，归纳完成。,充分性，若G是S的逻辑结果，由演绎的定义知，G是如下演绎：H1 ，Hm ，G 的逻辑结果，其中 H1 ，Hm 是S中所有公式.,演绎定理,定理2.3.3 设S是前提公式集合，G，H是两个公式。 如果从SG可演绎出H，则从S可演绎出GH。 证明：因为从SG可演绎出H，由定理2.3.2知，H是S G的逻辑结果。 亦即 (G1 Gk G)H 其中 G1 ，Gk 是S中所有公式。 由定理2.3.1知： (G1 Gk )(GH) 即GH是S的逻辑结果，再由定理2.3.2知，从S可演绎出GH。,基本蕴涵式,PQP PQQ PPQ QPQ P(PQ) Q(PQ) (PQ)P,基本蕴涵

27、式,(PQ)Q P，QPQ P，PQQ P，PQQ Q，PQP PQ，QRPR PQ，PR，QRR,给出两个公式G，H，证明G蕴涵H。 真值表法； 证G H是恒真公式； 利用一些基本等价式及蕴涵式进行推导； 任取解释I，若I满足G，往证I满足H； 反证法，设结论假，往证前提假(即证明H G)。,7 小结：公式间蕴涵的证明方法,真值表法将公式G和公式H同列在一张真值表中，扫描公式G所对应的列，验证该列真值为1的每一项，它所在行上相应公式H所对应列上的每一项必为1（真），则公式G蕴涵H。,证G H是恒真公式 例. 设A、B和C为命题公式，且AB。请分别阐述（肯定或否定）下列关系式的正确性。 （1）

28、(AC) (BC)；-正确 （2）(AC) ( BC)。-不正确,例 设A=(R P) Q，B= P Q，证明A蕴涵B。 证明：证明AB恒真。(R P) Q) ( P Q) = ( ( RP) Q) (PQ) =(RP) Q) (PQ) =(R Q) ( P Q) ( P Q) =1,利用一些基本等价式及蕴涵式进行推导 例 设A=(R P) Q，B= P Q，证明A蕴涵B。 证明：由基本等价式可得： A=(R P) Q= ( RP) Q= (R P) Q=( RQ) ( PQ)=( RQ) ( P Q) 由基本蕴涵式2. PQQ可知， ( RQ) ( P Q) (P Q)，即A蕴涵B。,任取解

29、释I，若I满足G，往证I满足H 例. 设A= P Q，B=(RQ) (PR) Q)，证明A蕴涵B。 证明： 任取解释I，若I满足A，则有如下两种情况： （1）在解释I下，P为假，这时，TI(B)= (RQ) （R Q）=1， 因此，I亦满足B。 （2）在解释I下，Q为真，这时，TI(B)= 1 1=1，即，I亦满足B。 综上，I满足B，因此，A蕴涵B。,反证法，设结论假，往证前提假(即证明H G)。 例 设A=(R P) Q，B= P Q，证明A蕴涵B。 证明：假设存在解释I使P Q为假，则只有一种情形：P在I下为真，且Q在I下为假，这时R P在I下为真，故I弄假(R P) Q。因此，(RP)

30、 Q蕴涵 P Q。,若给出前提集合S=G1 ，Gk ，公式G，证明SG有如下两种方法： 1. G1 Gk G 2. 形式演绎法,7 公式蕴涵的证明方法,根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则： 规则1. 可随便使用前提。 (根据演绎定义) 规则2. 可随便使用前面演绎出的某些公式的逻辑结果。 (根据演绎的定义) 规则3. 如果需要演绎出的公式是PQ的形式，则可将P做为附加前提使用，而力图去演绎出Q。 (根据定理2.3.3)。,8 形式演绎法,例2.3.1,证明(PQ)，(PR)，(QS)SR PQ 规则1 PQ 规则2，根据1QS 规则1PS 规则2，

31、根据2，3SP 规则2，根据4PR 规则1SR 规则2，根据5，6SR 规则2，根据7,例2.3.2,证明P(QS)，RP，QRSRP 规则1R 规则3P 规则2，根据1，2P(QS) 规则1QS 规则2，根据3，4Q 规则1S 规则2，根据5，6RS 规则3，根据2，7,例2.3.3,若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。 问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止? 令 P： 厂方拒绝增加工资；Q： 罢工停止；R： 工厂经理辞职；S： 罢工超过一年。,于是， G1：(P(RS)QG2：PG3：SH： Q 要证明： H是G1，G2，G3的逻辑结

32、果。 1. S 规则1 2. SR 规则2，根据1,3. (RS) 规则2，根据2 4. P 规则1 5. P(RS) 规则2，根据3，4 6. (P(RS)Q 规则1 7. Q 规则2，根据5，6亦即，罢工不会停止。,例.一个公安人员审查一件盗窃案，已知的事实如下： (1)A或B盗窃了x (2)若A盗窃了x，则作案时间不能发生在午夜前 (3)若B证词正确，则在午夜时屋里灯光未灭 (4)若B证词不正确，则作案时间发生在午夜前 (5)午夜时屋里灯光灭了 (6)A并不富裕 试用演绎法找出盗窃犯。 解:先将已知事实中的各简单命题符号化，设： P：A盗窃了x Q：B盗窃了x R：作案时间发生在午夜前

33、S：B证词正确 T：在午夜时屋里灯光未灭 U：A并不富裕,再将各前提写出： G1：PQ G2：P R G3：ST G4：SR G5：T G6：U 演绎过程为： （1） ST 规则 （2） T 规则 （3） S 规则2，根据（1），（2） （4） SR 规则 （5） R 规则2，根据（3），（4） （6） P R 规则 （7） P 规则2，根据（5），（6） （8） PQ 规则 （9） Q 规则2，根据（7），（8） 因此，是B盗窃了x,作业,习题2.3 1、7、8、9 2007年4月17日交,2.4 范式,范式的引入,在命题逻辑中，对于含有有限个原子的命题公式来说，用真值表的方法，总可以在有限

34、的步骤内确定它的真值，因此判定问题总是可解的。 但是我们知道，这种方法并不理想，因为公式每增加一个原子，真值表的行数就增加一倍。为了给出另一种方法，我们将介绍命题公式的一种标准形式，即范式，两个命题公式是否等价及一个公式恒真、恒假、可满足的判定，都将由公式的范式来解决。,定义2.4.1 原子或原子的否定称为文字。 例. P，P是文字。 定义2.4.2 有限个文字的析取式称为一个子句； 有限个文字的合取式称为一个短语。 特别，一个文字既可称为是一个子句，也可称为是一个短语。 例. P，PQ，PQ是子句，P，PQ，PQ是短语。,1 析取范式和合取范式,定义2.4.3 析取范式、合取范式,有限个短语

35、的析取式称为析取范式； 有限个子句的合取式称为合取范式。 特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。 例如，P，PQ，PQ，(PQ)(PQ)是析取范式。 P，PQ，PQ，(PQ)(PR)是合取范式。,定理2.4.1,对于任意命题公式，都存在等价于它的析取范式和合取范式。 证明：对于公式G，通过如下算法即可得出等价于G的范式： 步1. 使用基本等价式，将G中的逻辑联结词， 删除。 步2. 使用(H)=H和摩根律，将G中所有的否定号都放在原子之前。步3. 反复使用分配律，即可得到等价于G的范 式。,例：,G = (P(Q

36、R)S=(P(QR)S=P(QR)S=P(QR)S . (析取范式)=P(QR)(S(QQ)=P(QR)(SQ)(SQ) (析取范式)=(PS)(QR)=(PSQ)(PSR) (合取范式),定义2.4.4 设P1,Pn是n个不同原子，一个短语如果恰好包含所有这n个原子或其否定，且其排列顺序与P1,Pn的顺序一致，则称此短语为关于P1,Pn的一个极小项。 例.对原子P，Q，R而言，PQR，PQR，PQR都是极小项，但是，P，PQ不是极小项，而PQ对原子P，Q而言是极小项。 显然，共有2n个不同的极小项。,2 主析取范式,对于n个原子P1,Pn而言，其不同的解释共有2n个，对于P1,Pn的任一个极

37、小项m，2n个解释中，有且只有一个解释使m取1值。 证明：任取一个极小项，按照如下方法构造其解释：对原子Pi (1in)，如果Pi出现在该极小项中，Pi指定为1；如果Pi的否定出现在该极小项中，Pi指定为0。则构造出来的解释使该极小项取1值, 而且只能构造出来一个这样的解释。,极小项与解释的1-1对应关系,例如，对P，Q，R而言，PQR是极小项，解释P，Q，R使该极小项取1值，其他解释都使该极小项取0值。,极小项与解释的1-1对应关系,解释与n位二进制数的1-1对应关系,如果将真值1，0看做是数，则每一个解释对应一个n位二进制数。 假设使极小项m取1值的解释对应的二进制数为i，今后将m记为mi

38、。,例:,对P，Q，R而言，PQR是极小项，解释(0，1，0)使该极小项取1值，解释(0，1，0)对应的二进制数是2，于是PQR记为m2。 对P，Q，R而言，8个极小项与其对应的解释如下：,一般地，对P1,Pn而言，2n个极小项为,定义2.4.5主析取范式,设命题公式G中所有不同原子为P1,Pn，如果G的某个析取范式G中的每一个短语，都是关于P1,Pn的一个极小项，则称G为G的 主析取范式。恒假公式的主析取范式用0表示。,定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。 证明：设命题公式G中所有不同原子为P1，Pn，则等价于它的主析取范式的求法如下： (a) 将公式G化为析取范式G

39、。(由定理2.4.1知，存在析取范式G，使得G=G) (b) 删去析取范式中所有恒假的短语。 (c) 用等幂律将短语中重复出现的同一文字化简为一次出现，如，PP=P。,3 主析取范式（存在性）,于是将G中非极小项Gi化成了一些极小项之析取。对G中其他非极小项也做如上处理，最后得等价于G的主析取范式G*。,(d) 对于所有不是关于P1，Pn的极小项 的短语使用同一律，补进短语中未出现的 所有命题原子，并使用分配律展开，即， 如果Gi不是关于P1,Pn的极小项，则Gi 中必然缺少原子P j1,Pjk，则,例,求G=(RP)(Q(PR) 的主析取范式 解： G =(RP)(Q(PR)=(R P)(Q

40、 P)(Q R)=(P R)(P Q)(Q R)=(PR)(QQ)(PQ)(RR)(QR)(PP)=(PQR)(PQR)(PQR)(PQR),求G=(PQ)(PR)(QR)的主析取范式,G的主析取范式为(PQR) (PQR) (PQR) (PQR),定理. 在真值表中，使得公式为真的解释所对应的极小项的析取即为此公式的主析取范式。 证明：给定公式G，设用这种方法写出主析取范式为G，往证G= G。 对G的任意解释I， （1）若解释I使G取1值，则在I下取1值的极小项写在G中，故G在I下也取1值。 （2）若I使G取0值，而在I下取1值的极小项不在G中且I弄假其它所有极小项，故G在I下也取0值。 所

41、以G是与G等价的主析取范式。,真值表法写主析取范式的正确性,定理2.4.3 设公式G，H是关于原子P1,Pn的两个主析取范式。 如果G，H不完全相同，则G，H不等价。 证明：因为G，H不完全相同，所以或者G中有一个极小项不在H中； 或者反之。不妨设极小项mi 在G中而不在H中。 于是根据极小项的性质，二进制数i所对应的关于P1,Pn的解释Ii使mi取1值，从而使公式G取1值。 Ii使所有不是mi的极小项取0值，从而使公式H取0值。 故G，H不等价。,4 用范式判断公式的等价性,定理2.4.4 对于任意公式G，存在唯一一个与G等价的主析取范式。 （唯一性）,5 主析取范式（唯一性）,引理 短语是

42、恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 证明：充分性，若有一个原子P及其否定P同时出现在短语中，则此短语有形式： PP 显然，不管是什么解释I，PP在I下取0值，于是此短语在I下取0值，故此短语恒假。,6 用范式判定公式的恒真恒假性,必要性. 若短语恒假，而任意原子及其否定均不同时在短语中出现。那么，取这样的解释I：指定带有否定号的原子取0值，不带否定号的原子取1值，显然，此短语在这个解释I下取1值，与此短语恒假矛盾。,定理2.4.5,命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。 证明： 设G的析取范式如下： G=G1G

43、n 其中Gi是短语，i=1，n。 显然，公式G恒假的充要条件是每个Gi恒假。 再根据引理，此定理结论显然成立。,例2.4.1,判断公式G=(PQ)(QR)(RP)是否恒假? 解： G=(PQ)(QR)(RP) =(PQ)(QR)(RP) =(PQ)(QQ)(PR)(QR)(RP) =(PQR)(QQR)(PRR)(Q RR)(PQP)(QQP)(PRP) (QRP) 故公式G不是恒假的。,例2.4.2,判断公式G=(PQ)PQ是否恒假? 解：G=(PQ)PQ=(PQ)PQ=(PPQ)(QPQ) 故公式G是恒假的。,把公式化成主析取范式， 公式恒假时，主析取范式没有极小项； 公式恒真时，主析取范

44、式有全部极小项。,7 判定公式是否恒真的其它方法,2. 一种判定算法 对任给要判定的命题公式G，设其中有原子P1,P2,Pn，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2, Pn，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。,例2.4.3,补充:主合取范式,模仿主析取范式的概念，引进主合取范式的概念。 定义：设P1，Pn是n个不同原子，一个子句如果恰好包含所有这n个原子或其否定，且其排列顺序与P1，Pn的顺序一致，则称此子句为关于P1，Pn的一个极大项。 定义：设命题公式G中所有不同原子为P1，Pn，如果G的某个合取范式G中的每一个子句，都是关于P1，Pn的一个极大项，则称G为G的主合取范式。,