第二章 命题逻辑

数理逻辑 数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，数理逻辑一般又称为符号逻辑。 数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。 古典数理逻辑：命题逻辑和谓词逻辑—是计算机科学很重要的数学基础。 现代数理逻辑：逻辑演算、证明论、公理集合论、递归论和模型论 。

数理逻辑的创始人--莱布尼茨 (Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14 德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、神学等诸多方面. 出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了，给他留下了丰富的藏书。

15岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的《几何原本》的课程后，莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位 。 26岁设计出世界第一台乘法器，被认为是现代机器数学的先驱者。 Leibniz(1646～1716年) 之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。 1693年，发现了机械能的能量守恒定律。 与牛顿并称为微积分的创立者。 系统阐述了二进制记数法，并把它和中国的八卦联系起来。

第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 2.5 命题逻辑在二值逻辑器件 和语句逻辑中的应用

2.1 命题以及逻辑联结词

1 命题 所谓命题是指一句有真假意义的话。 例如：上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2 命题用大写英文字母P，Q，…，P1，P2，…，表示。 “我在说谎”,这是既不能为真，又不能为假的句子，称为“悖论”。

下列句子中不是命题的有( ) A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起，你就可以长生不老。 下列句子中不是命题的有( ) 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。 2 逻辑联结词 定义2.1.1 设P是一个命题，命题 “P是不对的”称为P的否定，记以P，读作非P。 真值规定：P是真的当且仅当P是假的。 例. P：吉大是中国最大的大学。 P：吉大不是中国最大的大学。 Q:张三是好人  Q ：张三不是好人

定义2.1.2 设P，Q是两个命题，命题 “P或者Q”称为P，Q的析取，记以PQ，读作P或Q。

定义2.1.3 设P，Q是两个命题，命题 “P并且Q”称为P，Q的合取，记以PQ，读作P且Q。

注意： 自然语言中的“或者”一词有两种用法： 1) “张三或者李四考了90分”, 表示两者可以同时成立。这是“可兼或”。 按照联结词“”的定义，当P，Q都为真时，PQ也为真，因此，“”所表示的“或”是“可兼或”。

2) “我明天到北京出差或者到广州去度假”，表示的是二者只能居其一，不会同时成立。这是“不可兼或”。 “不可兼或” 不可以用来表示. 表示为：(PQ)  ( PQ) –异或

判断： （1）今天晚上我在家中看戏或去剧场看戏。 （2）他可能是100米或400米冠军。 （3）我第一节课上数学课或上英语课。 （4）李梅是三好学生或优秀团员。 （5）张三生于1987年或1988年。 （6）老王或小李有一个去上海出差。 （7）李明是软件学院的学生，他住在312室或 313室。

定义2.1.4 设P，Q是两个命题，命题 “如果P，则Q”称为P蕴涵Q，记以PQ。 真值规定： PQ是假的当且仅当P是真的而Q是假的。 例. P：f(x)是可微的， Q：f(x)是连续的， PQ： 若f(x)是可微的，则f(x)是连续的。

由定义知，如果P是假命题，则不管Q是什么命题，命题 “如果P，则Q”在命题逻辑中都被认为是真命题。 —与自然语言不一样的地方

定义2.1.5 设P，Q是两个命题，命题 “P当且仅当Q”称为P等价Q，记以PQ。 例如， P ： a2+b2=a2， Q： b=0， PQ： a2+b2=a2当且仅当b=0 。

例2.1.1 如果你走路时看书，那么你会成为近视眼。 令P：你走路；Q：你看书； R：你会成为近视眼。

例2.1.2 除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。 令P：他书面通知我； Q：他口头通知我； R：我参加明天的会议。

例2.1.3 设P，Q，R的意义如下： P：苹果是甜的；Q：苹果是红的； R：我买苹果。 试用日常语言复述下述复合命题： (1) (PQ)R (2) (PQ)R 解：(1)如果苹果甜且红，那么我买; (2)我没买苹果，因为苹果不甜也不红. 非P应该是什么？

2.2 命题公式

1 公式 我们用大写的英文字母P，Q，R，…等代表一个抽象的命题，或称为命题符号。 定义2.2.1 命题符号称为原子。 定义2.2.1 命题符号称为原子。 例如，Q，S，…等都是原子。

命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式； (2) 0、1是公式； 定义2.2.2 命题公式 命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式； (2) 0、1是公式； (3) 若G，H是公式，则(G)，(GH)， (GH)，(GH)，(GH)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3) 得到的符号串。

规定： 公式(G)的括号可以省略，写成G。 整个公式的最外层括号可以省略。 五种逻辑联结词的优先级按如下次序递增： ，，，， 五种逻辑联结词的优先级按如下次序递增： ，，，， 例如，我们写符号串 PQRQSR 就意味着是如下公式： ((P(QR))(Q((S)R)))

2 解释 定义2.2.3 设G是命题公式，A1, …, An是出现在G中的所有原子。 指定A1, …, An的一组真值，则这组真值称为G的一个解释。 设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。

例 G=PQ，设解释I，I’如下： I： I’： 则TI (G)=1，TI’ (G)=0 注意：该例子中写成G=1或G=0是错误的！ 1 1 P Q 1 0

定义2.2.4 公式G在其所有可能的解释下所取真值的表，称为G的真值表。 显然，有n个不同原子的公式，共有2n个解释。

例：G=(PQ)R，其真值表如下： P Q R G 1

练习：请画出 P ， PQ， PQ， PQ，PQ的真值表。

若公式G中出现的所有原子为A1，…，An，有时我们用{m1，…，mn}表示G的一个解释I，其中 例.公式G=(PQ)R的真值表中第二个解释就可以记为{P，Q，R}

定义2.2.5 公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；

从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。 考虑G1= (P→Q) →P， G2=(P →Q) P， G3=P   P。 从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。 P Q G1 G2 G3 1

练习：用真值表判断公式 （P→Q）→（（Q →R）→（P→R））的类型

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)，所以命题逻辑的判定问题是可解的(可判定的，可计算的). 结论:命题公式的恒真，恒假性是可判定的.

作业: 习题2.1-3， 习题2.2-1、3、4 下周二（２００７年４月１０日）交

§2.3 命题公式的等价关系 和蕴涵关系

1 公式的等价 定义2.3.1 称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。 公式G，H等价 iff 公式GH恒真。 公式间的等价关系有自反性、对称性、传递性。

基本等价式 1) (GH)=(GH)(HG)； 2) (GH)=(GH)； 3) GG=G，GG=G； (等幂律) 4) GH=HG，GH=HG； (交换律) 5) G(HS)=(GH)S， G(HS)=(GH)S； (结合律) 证明方法？

6) G(GH)=G，G(GH)=G； (吸收律) 7) G(HS)=(GH)(GS)， G(HS)=(GH)(GS)； (分配律) 8) G0=G，G1=G； (同一律) 9) G0=0，G1=1； (零一律) 10) (GH)=GH， (GH)=GH。 (De Morgan律) （互补律： G G=1；G G=0 双重否定律：  G=G ） 上述等价式可用真值表验证。

证明命题公式恒真或恒假的两个方法 方法一. 真值表方法。 即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例.（P→Q）→（（Q →R）→（P→R）） = ( 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  ( Q  Q) =P 1=P

例. 证明： (P Q)  (P R) (Q R)=(PQ)(P R) 证明： 左= (P Q)  (P R) ((PP)(QR)） = (P Q)  (P R) (PQR) (PQR) =((PQ)(PQR))((PR)(PRQ) =(PQ)(P R) =右

练习： 证明： P →（Q →R）= P Q →R 问： （P →Q）→R与P Q →R是否等价？

例.世界冰球赛正在激烈进行，看台上三位观众 正在热烈地议论着这次比赛的名次。 甲：中国第一，匈牙利第三 乙：奥地利第一，中国第三 丙：匈牙利第一，中国第二 比赛结束后，发现这三位观众每人恰好都猜对了 一半。假设无并列名次。 问：中国、奥地利、匈牙利各队的名次。 解： 设P1:中国第一； P2:中国第二； P3:中国第三 Q1:奥地利第一 R1:匈牙利第一； R3:匈牙利第三

由于甲、乙、丙个猜对一半，故有： （P1  R3） ( P1  R3)=1 (1) （Q1  P3） ( Q1  P3)=1 (2) （R1  P2） ( R1  P2)=1 (3) 无并列名次： P1Q1=0， P1R1=0，Q1R1=0，P3R3=0 （*） 每个国家只能得一个名次： P1P2=0，P1P3=0，P2P3=0，R1R3=0 （**）

(1)(2)左边合取，利用（*）（**）化简得：  P1  R3  Q1   P3 (4) (4)(3)左边合取，利用（*）（**）化简得：  P1  R3  Q1   P3   R1  P2 而右边合取得1。 由此得出结论： 奥地利第一，中国第二，匈牙利第三

2 完备集 定义2.3.2 完备集 设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。 可以证明，{，}，{，}都是完备集。

证明 {，} 是完备集 证明： PQ = ( P  Q) PQ = PQ= (PQ) PQ = (PQ) (QP) = ( P  Q) ( Q  P) = ((P  Q)) ((QP))

定义2.3.3 与非式 设P，Q是两个命题，命题 “P与Q的否定”称为P与Q的与非式，记作PQ。 “”称作与非联结词。 真值规定:PQ为真 iff P,Q不同时为真。 由定义可知： PQ=(PQ)。

定义2.3.4 或非式 设P，Q是两个命题，命题 “P或Q的否定”称为P与Q的或非式，记作PQ， 称作或非联结词。 定义2.3.4 或非式 设P，Q是两个命题，命题 “P或Q的否定”称为P与Q的或非式，记作PQ， 称作或非联结词。 真值规定：PQ为真 iff P，Q同时为假。 由定义可知： PQ=(PQ)

{}是完备集 P = (P  P) =PP PQ = ( P  Q) = (P)  (Q) =(PP)(QQ) PQ=  （PQ）=  (PQ) = ((PQ)  (PQ))=(PQ)(PQ) 读者可以自己证明{}也是完备集。

3 公式的蕴涵 逻辑的一个重要功能是研究推理。固然， 依靠等价关系可以进行推理。但是，进行 推理时，不必一定要依靠等价关系，只需 蕴涵关系就可以了。 例.若三角形等腰，则两底角相等， 这个三角形等腰， 所以，这个三角形两底角相等。 例.若行列式两行成比例，则行列式值为0， 这个行列式两行成比例， 所以，这个行列式值为0。

上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为： 若P则Q，P，所以Q。

设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。 定义2.3.5 蕴涵 设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。

注意： 符号“”和“=” 一样，它们都不是逻辑联结词，因此，G=H，GH也都不是公式。 定义2.3.5 蕴涵 注意： 符号“”和“=” 一样，它们都不是逻辑联结词，因此，G=H，GH也都不是公式。 是一种部分序关系。 公式G蕴涵公式H iff 公式GH是恒真的。 例. (PQ)P，(PQ)Q

GH当且仅当GH是恒真的 证明：必要性，任取G, H的解释I， 若I满足G（ TI(G)=1），则由GH知， TI(H)=1 ，因此TI(GH)=1； 若I弄假G(TI(G)=0)，则TI(GH)=1 。 从而，对G, H的任意解释I，都有GH为 真， 故GH是恒真的. 充分性，任取G, H的解释I，若TI(G)=1，由 GH恒真，知， TI(H)=1。从而有GH。

是一种部分序关系 证明：要证明公式间的蕴涵关系是部分序关系，需要证明其具有自反性、反对称性和传递性。 自反性：任取公式G，有G  G 恒真，因此， G G。 反对称性：若G  H，H  G，则 G  H，H  G恒真，从而, (G  H) (H  G)恒真，即，G  H恒真，故G=H。

是一种部分序关系 传递性：若GG1，G1H，则对G, G1, H的任意解释I，若I满足G，则由GG1知，I满足G1，再由G1H知，I满足H。因此，GH。

定义2.3.6 设G1, …, Gn，H是公式。 称H是G1, …,Gn的逻辑结果(或称G1, …, Gn共同蕴涵H)，当且仅当 (G1 … Gn)  H。 显然，公式H是G1, …, Gn的逻辑结果 iff 公式((G1 … Gn)H)是恒真的。 例如，P，PQ共同蕴涵Q。 设G’ = G1 … Gn ，则公式H是G1, …, Gn的逻辑结果 当且仅当公式G’ 蕴涵 H 当且仅当公式 G’ H 是恒真的 当且仅当公式((G1 … Gn)H)是恒真的。 一个前提扩展到了多个前提。

定理2.3.1 如果H1, …, Hm，P共同蕴涵公式Q，则H1, …, Hm共同蕴涵公式PQ。 例. 因为公式PQ，QR，P共同蕴涵R，所以PQ，QR共同蕴涵PR。

定理2.3.1 证明：因为(H1 …HmP)Q，所以公式(H1 …HmP)Q是恒真的。 利用下面的基本等价公式： P1(P2P3)=(P1P2)P3 于是，(H1 …HmP)Q=(H1 …Hm)(PQ)。 故(H1 …Hm)(PQ)是恒真的。 所以H1，…，Hm共同蕴涵PQ。

4 演绎 定义2.3.7 设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列： G1, G2, …, Gk 其中，Gi （1≤i ≤ k）或者属于S，或者是某些 Gj (j<i)的逻辑结果。 并且 Gk就是G。 称公式G为“此演绎的” 逻辑结果，或称从S演绎出G。 有时也记为SG。

例 设S={PQ，QR，PM，M} 则下面的公式序列: M，PM，P，PQ，Q，QR，R 就是从S推出R的一个演绎。

5 演绎方法的可靠性与完备性 引理 设G，H1，H2是公式。 如果 GH1，GH2，则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的逻辑结果。 证明：必要性，设从S演绎出G，令 G1，…，Gk（即是G） 是这个演绎。 对任意 Gi (i=1，…，k)，往证Gi 是S的逻辑结果。 对i用归纳法: (1) 当i=1时，因G1S，显然, G1 … G1 是恒真公式，故S G1 ，即 G1 是S的逻辑结果。

(2) 设i<n时，命题成立。 (3) 当i=n时， 若 GnS，则S Gn，归纳法完成. 若Gn是某些Gj (j<n)的逻辑结果，不妨设 (Gj1 …Gjh )Gn (1) 其中j1，…，jh都小于n。 由归纳假设知，SGjm ，m=1，…，h。由引理知：S( Gj1 …Gjh ) (2) 根据(1)，(2)式及蕴涵关系的传递性，得 S Gn 即Gn是S的逻辑结果，归纳完成。

充分性，若G是S的逻辑结果，由演绎的定义知，G是如下演绎： H1 ，…，Hm ，G 的逻辑结果，其中 H1 ，…，Hm 是S中所有公式. 注:如果S中一部分公式就可以演绎出G, 则再添加上S中剩余的公式, 也是可以演绎出G的。

演绎定理 定理2.3.3 设S是前提公式集合，G，H是两个公式。 如果从S∪{G}可演绎出H，则从S可演绎出GH。 证明：因为从S∪{G}可演绎出H，由定理2.3.2知，H是S ∪{G}的逻辑结果。 亦即 (G1  … Gk G)H 其中 G1 ，…，Gk 是S中所有公式。 由定理2.3.1知： (G1  … Gk )(GH) 即GH是S的逻辑结果，再由定理2.3.2知，从S可演绎出GH。

基本蕴涵式 PQP PQQ PPQ QPQ P(PQ) Q(PQ) (PQ)P

基本蕴涵式 (PQ)Q P，QPQ P，PQQ P，PQQ Q，PQP PQ，QRPR PQ，PR，QRR

7 小结：公式间蕴涵的证明方法 给出两个公式G，H，证明G蕴涵H。 真值表法； 证G H是恒真公式； 利用一些基本等价式及蕴涵式进行推导； 7 小结：公式间蕴涵的证明方法 给出两个公式G，H，证明G蕴涵H。 真值表法； 证G H是恒真公式； 利用一些基本等价式及蕴涵式进行推导； 任取解释I，若I满足G，往证I满足H； 反证法，设结论假，往证前提假 (即证明H  G)。

真值表法 将公式G和公式H同列在一张真值表中，扫描公式G所对应的列，验证该列真值为1的每一项，它所在行上相应公式H所对应列上的每一项必为1（真），则公式G蕴涵H。

证G H是恒真公式 1 例. 设A、B和C为命题公式，且AB。请分别阐述（肯定或否定）下列关系式的正确性。 （1）(AC)  (BC)；--正确 （2）(AC) ( BC)。--不正确 A B C AB AC BC ACBC AC BC (AC)(BC) 1

例 设A=(R P)  Q，B= P Q， 证明A蕴涵B。 证明：证明AB恒真。 ((R P)  Q) ( P Q) =  ( ( RP) Q) (PQ) =((RP)  Q) (PQ) =(R Q) ( P  Q) ( P  Q) =1

利用一些基本等价式及蕴涵式进行推导 例 设A=(R P)  Q，B= P Q， 证明A蕴涵B。 证明：由基本等价式可得： A=(R P)  Q = ( RP) Q = (R P) Q =( RQ) ( PQ) =( RQ) ( P Q) 由基本蕴涵式2. PQQ可知， ( RQ) ( P Q) (P Q)，即A蕴涵B。

例. 设A= P Q，B=(RQ) ((PR) Q)， 任取解释I，若I满足G，往证I满足H 例. 设A= P Q，B=(RQ) ((PR) Q)， 证明A蕴涵B。 证明： 任取解释I，若I满足A，则有如下两种情况： （1）在解释I下，P为假，这时， TI(B)= (RQ) （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。因此，(RP) Q蕴涵 P Q。

7 公式蕴涵的证明方法 若给出前提集合S={G1 ，…，Gk }，公式G，证明SG有如下两种方法： 1. G1  … Gk G 2. 形式演绎法

8 形式演绎法 根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则： 8 形式演绎法 根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则： 规则1. 可随便使用前提。 (根据演绎定义) 规则2. 可随便使用前面演绎出的某些公 式的逻辑结果。 (根据演绎的定义) 规则3. 如果需要演绎出的公式是PQ的 形式，则可将P做为附加前提使 用，而力图去演绎出Q。 (根据定理2.3.3)。

例2.3.1 证明{(PQ)，(PR)，(QS)}SR PQ 规则1 PQ 规则2，根据1 QS 规则1 PS 规则2，根据2，3 SP 规则2，根据4 PR 规则1 SR 规则2，根据5，6 SR 规则2，根据7

例2.3.2 证明{P(QS)，RP，Q}RS RP 规则1 R 规则3 P 规则2，根据1，2 P(QS) 规则1

例2.3.3 若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。 问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止? 令 P： 厂方拒绝增加工资； Q： 罢工停止； R： 工厂经理辞职； S： 罢工超过一年。

于是， G1：(P(RS))Q G2：P G3：S H： Q 要证明： H是{G1，G2，G3}的逻辑结果。 1. S 规则1 2. SR 规则2，根据1

3. (RS) 规则2，根据2 4. P 规则1 5. P(RS) 规则2，根据3，4 6. (P(RS))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：作案时间发生在午夜前 S：B证词正确 T：在午夜时屋里灯光未灭 U：A并不富裕

再将各前提写出： G1：P∨Q G2：P → R G3：S→T G4：S→R G5：T G6：U 演绎过程为： （1） S→T　　　规则１ （2） T 规则１ （3） S 规则2，根据（1），（2） （4） S→R 规则１ （5） R 规则2，根据（3），（4） （6） P → R 规则１ （7） P 规则2，根据（5），（6） （8） P∨Q 规则１ （9） Q 规则2，根据（7），（8） 因此，是B盗窃了x

作业 习题2.3 –1、7、8、9 2007年4月17日交

§2.4 范式

范式的引入 在命题逻辑中，对于含有有限个原子的命题公式来说，用真值表的方法，总可以在有限的步骤内确定它的真值，因此判定问题总是可解的。 但是我们知道，这种方法并不理想，因为公式每增加一个原子，真值表的行数就增加一倍。为了给出另一种方法，我们将介绍命题公式的一种标准形式，即范式，两个命题公式是否等价及一个公式恒真、恒假、可满足的判定，都将由公式的范式来解决。

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

定义2.4.3 析取范式、合取范式 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。 例如，P，PQ，PQ，(PQ)(PQ)是析取范式。 P，PQ，PQ，(PQ)(PR)是合取范式。

定理2.4.1 对于任意命题公式，都存在等价于它的析取范式和合取范式。 证明：对于公式G，通过如下算法即可得出等价于G的范式： 步2. 使用(H)=H和摩根律，将G中所有的否定 号都放在原子之前。 步3. 反复使用分配律，即可得到等价于G的范 式。

例： G = (P(QR))S =P(QR)S =P(QR)S ……………. (析取范式) =P(QR)(S(QQ)) =P(QR)(SQ)(SQ) (析取范式) =(PS)(QR) =(PSQ)(PSR) …… (合取范式)

2 主析取范式 定义2.4.4 设P1,…,Pn是n个不同原子，一个短语如果恰好包含所有这n个原子或其否定，且其排列顺序与P1,…,Pn的顺序一致，则称此短语为关于P1,…,Pn的一个极小项。 例.对原子P，Q，R而言，PQR，PQR，PQR都是极小项，但是，P，PQ不是极小项，而PQ对原子P，Q而言是极小项。 显然，共有2n个不同的极小项。

极小项与解释的1-1对应关系 对于n个原子P1,…,Pn而言，其不同的解释共有2n个，对于P1,…,Pn的任一个极小项m，2n个解释中，有且只有一个解释使m取1值。 证明：任取一个极小项，按照如下方法构造其解释：对原子Pi (1≤i≤n)，如果Pi出现在该极小项中，Pi指定为1；如果Pi的否定出现在该极小项中，Pi指定为0。则构造出来的解释使该极小项取1值, 而且只能构造出来一个这样的解释。

极小项与解释的1-1对应关系 例如，对P，Q，R而言，PQR是极小项，解释{P，Q，R}使该极小项取1值，其他解释都使该极小项取0值。

解释与n位二进制数的1-1对应关系 如果将真值1，0看做是数，则每一个解释对应一个n位二进制数。 假设使极小项m取1值的解释对应的二进制数为i，今后将m记为mi。

例: 对P，Q，R而言，PQR是极小项，解释(0，1，0)使该极小项取1值，解释(0，1，0)对应的二进制数是2，于是PQR记为m2。 对P，Q，R而言，8个极小项与其对应的解释如下：

极小项 解释 记法 PQR 000 m0 PQR 001 m1 PQR 010 m2 PQR 011 m3 PQR 100 m4 PQR 101 m5 PQR 110 m6 PQR 111 m7

一般地，对P1,…,Pn而言，2n个极小项为

定义2.4.5主析取范式 设命题公式G中所有不同原子为P1,…,Pn，如果G的某个析取范式G’中的每一个短语，都是关于P1,…,Pn的一个极小项，则称G’为G的 主析取范式。 恒假公式的主析取范式用0表示。

3 主析取范式（存在性） 定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。 3 主析取范式（存在性） 定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。 证明：设命题公式G中所有不同原子为P1，…，Pn，则等价于它的主析取范式的求法如下： (a) 将公式G化为析取范式G’。(由定理2.4.1知，存在析取范式G’，使得G=G’) (b) 删去析取范式中所有恒假的短语。 (c) 用等幂律将短语中重复出现的同一文字化简为一次出现，如，PP=P。

(d) 对于所有不是关于P1，…，Pn的极小项 的短语使用同一律，补进短语中未出现的 所有命题原子，并使用分配律展开，即， 如果Gi’不是关于P1,…,Pn的极小项，则Gi’ 中必然缺少原子P j1,…,Pjk，则 在定理2.4.2的证明中，实际上已经给出了求公式的主析取范式的方法。 于是将G’中非极小项Gi’化成了一些极小项之析取。对G’中其他非极小项也做如上处理，最后得等价于G的主析取范式G*。

例 求G=(RP)(Q(PR)) 的主析取范式 解： G =(RP)(Q(PR)) =(R  P)(Q  P)(Q  R) =(P  R)(P  Q)(Q  R) =((PR)(QQ))((PQ)(RR)) ((QR)(PP)) =(PQR)(PQR)(PQR) (PQR)

G的主析取范式为(PQR) (PQR) (PQR) (PQR) 求G=(PQ)(PR)(QR)的主析取范式 P Q R G 1 寻找与公式G等价的主析取范式，也可以通过真值表来做。 如果真值表中没有一行真值为1，则G’=0 G的主析取范式为(PQR) (PQR) (PQR) (PQR)

真值表法写主析取范式的正确性 定理. 在真值表中，使得公式为真的解释所对应的极小项的析取 即为此公式的主析取范式。 　　　即为此公式的主析取范式。 证明：给定公式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值。 所以G’是与G等价的主析取范式。

4 用范式判断公式的等价性 定理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不等价。

5 主析取范式（唯一性） 定理2.4.4 对于任意公式G，存在唯一一个与G等价的主析取范式。 （唯一性）

6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 证明：充分性，若有一个原子P及其否定P同时出现在短语中，则此短语有形式： PP… 显然，不管是什么解释I，PP在I下取0值，于是此短语在I下取0值，故此短语恒假。

必要性. 若短语恒假，而任意原子及其否定均不同时在短语中出现。那么，取这样的解释I：指定带有否定号的原子取0值，不带否定号的原子取1值，显然，此短语在这个解释I下取1值，与此短语恒假矛盾。

定理2.4.5 命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。 证明： 设G的析取范式如下： G=G1…Gn 其中Gi是短语，i=1，…，n。 显然，公式G恒假的充要条件是每个Gi恒假。 再根据引理，此定理结论显然成立。

例2.4.1 判断公式G=(PQ)(QR)(RP)是否恒假? 解： G=(PQ)(QR)(RP) =((PQ)(QQ)(PR)(QR))(RP) =(PQR)(QQR)(PRR)(Q RR)(PQP)(QQP)(PRP) (QRP) 故公式G不是恒假的。

例2.4.2 判断公式G=(PQ)PQ是否恒假? 解：G=(PQ)PQ =(PQ)PQ =(PPQ)(QPQ) 故公式G是恒假的。

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 (PQR)(PQ)(PR) (QR)QR RR 1 P取1值 P取0值 Q取1值 Q取0值 R取1值

补充:主合取范式 模仿主析取范式的概念，引进主合取范式的概念。 定义：设P1，…，Pn是n个不同原子，一个子句如果恰好包含所有这n个原子或其否定，且其排列顺序与P1，…，Pn的顺序一致，则称此子句为关于P1，…，Pn的一个极大项。 定义：设命题公式G中所有不同原子为P1，…，Pn，如果G的某个合取范式G’中的每一个子句，都是关于P1，…，Pn的一个极大项，则称G’为G的主合取范式。

极小项与极大项性质 P Q R 极小项 极大项 1 m0= P QR M0=PQR m1= P QR m0= P QR M0=PQR 1 m1= P QR M1=PQR m2= P QR M2=PQR m3= P QR M3=PQR m4= P  Q  R M4=PQR m5= P  Q R M5=PQ R m6= P Q  R M6=P Q R m7= P Q R M7=PQR

极小项与极大项性质 对n个命题原子P1，…，Pn 极小项有如下性质： （1）n个命题原子P1，…，Pn有2n个不同的解释，每个解释对应P1，…，Pn的一个极小项。 （2）对P1，…，Pn的任意一个极小项m，有且只有一个解释使m取1值，若使极小项取1的解释对应的二进制数为i，则m记为mi。 （3）任意两个不同的极小项的合取式恒假： mi mj=0，i≠j。 （4）所有极小项的析取式恒真。

极大项有如下性质： （1）n个命题原子P1，…，Pn有2n个不同的解释，每个解释对应P1，…，Pn的一个极大项。 （2）对P1，…，Pn的任意一个极大项M，有且只有一个解释使M取0值，若使极大项取0的解释对应的二进制数为i，则M记为Mi。 （3）任意两个不同的极大项的析取式恒真： Mi  Mj=1，i≠j。 （4）所有极大项的合取式恒假。 极小项和极大项的关系：mi= Mi ，Mi=mi

主合取范式与主析取范式之间的关系 例. 若PQR为一公式G的主合取范式，则 G =G = M0 =(M1M2…M7)

从一公式A的主合取范式（PQ）求其主析取范式的步骤为： （1）求出A的主合取范式中没有包含的所有极大项。 P  Q， P  Q， P  Q （2）求出与（1）中极大项下标相同的极小项。 P  Q， P  Q， P  Q （3）将（2）求出的所有极小项析取起来，即得A的主析取范式。 (P  Q)  ( P  Q)  (P  Q)

例.若（PQ）（PQ）（PQ）为一公式H的主析取范式， H=H =((PQ）（PQ）（PQ)) =（（m0 m1 m3） =  (m2) =M2 = PQ 为H的主合取范式。

由主析取范式求主合取范式： （1）求出A的主析取范式中没有包含的所有极小项。m2 （2）求出与（1）中极小项下标相同的极大项。 M2 （3）将（2）求出的所有极大项合取起来，即得A的主合取范式。

定理. 对任意命题公式，存在唯一一个与其等价的主合取范式。 证明: (存在性) 设命题公式G中所有不同原子为P1，…，Pn，则等价于它的主合取范式的求法如下： (a) 将公式G化为合取范式G’。(由定理2.4.1知，存在合取范式G’，使得G=G’) (b) 删去合取范式中所有恒真的子句。 (c) 用等幂律将子句中重复出现的同一文字化简为一次出现，如，P  P=P。

(d)对于G’中的每一个子句G’i进行检查，如果G’i不是关于P1，…，Pn的极大项，则G’i必然缺少原子Pj1,…Pjk。则可以通过如下方式扩展G’i G’i= G’i (Pj1 Pj1) …( Pjk Pjk) =Mi1…Mi2k 于是将G’中的非极大项G’i化成了一些极大 项的合取。 对其它非极大项也做同样处理，得到等价 于G的主合取范式G’’。

(唯一性)也就是证明对任意两个关于P1，…，Pn的主合取范式，如果公式不完全相同，则G与H不等价。 设公式G、H是关于P1，…，Pn的任意两个主合取范式。若G和H不完全相同，则必然存在一个极大项Mi在G中而不在H中（或相反），则取一解释I使Mi取0值，即，使公式G取0值。由定义可知I使非Mi的极大项都为1，从而有I使H取1值。所以G与H不等价。

用真值表法求主合取范式的正确性 定理. 在真值表中，使得公式为假的解释所对应的极大项 的合取即为此公式的主合取范式。 定理. 在真值表中，使得公式为假的解释所对应的极大项　 　　 的合取即为此公式的主合取范式。 证明： 给定公式G，设用这种方法写出主合取范式为G’，往证G= G’。 任意取G, G’ 的一个解释I。 如果I满足G，则唯一的一个在I下为假的那个极大项不在G’中出现，而I使所有其他的极大项取1，这样，G’在I下的真值是1； 如果I弄假G，则唯一的一个在I下为假的那个极大项出现在G’中，从而G’在下取0值。 这样，G与G’是等价的。

求主合取范式和主析取范式的方法 方法一. 真值表法。主析取范式恰好是使得公式为真的解释所对应的极小项的析取组成，主合取范式恰好是使得公式为假的解释所对应的极大项的合取组成。 方法二. 公式推导法。

例 求公式G= P→(Q→R)的主析取范式与主合取范式。 1

解：（1）使用真值表法。 根据真值表中使得公式为真的解释，所对应的极 小项的析取即为其主析取范式： G=(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) = m0 m1 m2  m3 m4 m5 m7 根据真值表中使得公式为假的解释，所对应的极 大项的合取即为其主合取范式： G=  P  Q  R= M6

（2）公式推导法 G= P→(Q→R) = P  Q  R =（P（QQ）（RR）） （ Q（PP）（RR）） （R（PP）（QQ）） = (PQR) (PQR)(PQR)  ( PQR)  (PQR)  (PQR) = m0 m1 m2  m3 m4 m5 m7 = M6

定理. 命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 证明：设公式G的合取范式为：G’=G1G2…Gn 若公式G恒真，则G’恒真，即子句Gi,i=1,2,…n恒真 为其充要条件。下面只需证明：子句是恒真的当且仅当 至少有一个原子及其否定(也称互补对)同时在此子句中 出现。 若有一个原子P及其否定P同时出现在子句中，则此子句有形式： PP… 　显然，不管是什么解释I，PP在I下取１值，于是此子句在I下取１值，故恒真。 假设子句恒真，但每个原子和其否定都不同时出现在其中。则可以给定一个解释I，使带否定号的原子为1，不带否定号的原子为0，那么此子句在解释I下的取值为0。这与子句恒真矛盾。

主合取范式与主析取范式的应用 利用主合取范式与主析取范式可求解判定问题 主析取范式：公式恒假时，主析取范式没有极小项（G’=0）；公式恒真时，主析取范式包含所有极小项。 主合取范式：公式恒假时，主合取范式包含所有极大项；公式恒真时，主合取范式没有极大项(G’=1)。

由于任意公式的主范式是唯一的，所以可以分别求出两 个给定的公式的主范式，若二者主范式相同，则给定的 证明等价式成立 由于任意公式的主范式是唯一的，所以可以分别求出两 个给定的公式的主范式，若二者主范式相同，则给定的 两公式是等价的，否则，给定的两公式不等价。 例 判断P→(Q→R)与（P Q）→ R是否等价。 证明： 利用求主合取范式的方法来判断。 由前知，P→(Q→R)的主合取范式为：M6。 下面求（P Q）→ R的主合取范式。 　（P Q）→ R = （P Q） R =（ PQ）R =（ PR）（QR） =（ P（QQ）R）（（PP）QR） =（ PQR） （ PQR） （PQR） = M2  M4  M6 二者的主合取范式不相同，因此，这两个公式不等价。

作业 习题2.4--5