Download presentation
Presentation is loading. Please wait.
1
第二章 命题逻辑
2
数理逻辑 数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，数理逻辑一般又称为符号逻辑。 数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。 古典数理逻辑：命题逻辑和谓词逻辑—是计算机科学很重要的数学基础。 现代数理逻辑：逻辑演算、证明论、公理集合论、递归论和模型论 。
3
数理逻辑的创始人--莱布尼茨 (Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14
德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、神学等诸多方面. 出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了，给他留下了丰富的藏书。
4
15岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的《几何原本》的课程后，莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位 。 26岁设计出世界第一台乘法器，被认为是现代机器数学的先驱者。 Leibniz(1646～1716年) 之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。 1693年，发现了机械能的能量守恒定律。 与牛顿并称为微积分的创立者。 系统阐述了二进制记数法，并把它和中国的八卦联系起来。
5
第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式
第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 2.5 命题逻辑在二值逻辑器件 和语句逻辑中的应用
6
2.1 命题以及逻辑联结词
7
1 命题 所谓命题是指一句有真假意义的话。 例如：上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2
命题用大写英文字母P，Q，…，P1，P2，…，表示。 “我在说谎”,这是既不能为真，又不能为假的句子，称为“悖论”。
8
下列句子中不是命题的有( ) A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起，你就可以长生不老。
下列句子中不是命题的有( ) A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起，你就可以长生不老。 E. 别的星球上有生物。 F. 几点了？ G. 1960年长春春城电影院放映了国产故事片“白毛女”。 H =110 I. 全体起立！ J. 这个教室好大呀!
9
如果一个命题是真的，就说它的真值是1； 如果一个命题是假的，就说它的真值是0。
也用“1”代表一个抽象的真命题，用“0”代表一个抽象的假命题。
10
2 逻辑联结词 定义2.1.1 设P是一个命题，命题 “P是不对的”称为P的否定，记以P，读作非P。
2 逻辑联结词 定义2.1.1 设P是一个命题，命题 “P是不对的”称为P的否定，记以P，读作非P。 真值规定：P是真的当且仅当P是假的。 例. P：吉大是中国最大的大学。 P：吉大不是中国最大的大学。 Q:张三是好人 Q ：张三不是好人
11
定义2.1.2 设P，Q是两个命题，命题 “P或者Q”称为P，Q的析取，记以PQ，读作P或Q。
12
定义2.1.3 设P，Q是两个命题，命题 “P并且Q”称为P，Q的合取，记以PQ，读作P且Q。
13
注意： 自然语言中的“或者”一词有两种用法： 1) “张三或者李四考了90分”, 表示两者可以同时成立。这是“可兼或”。
按照联结词“”的定义，当P，Q都为真时，PQ也为真，因此，“”所表示的“或”是“可兼或”。
14
2) “我明天到北京出差或者到广州去度假”，表示的是二者只能居其一，不会同时成立。这是“不可兼或”。
“不可兼或” 不可以用来表示. 表示为：(PQ) ( PQ) –异或
15
判断： （1）今天晚上我在家中看戏或去剧场看戏。 （2）他可能是100米或400米冠军。 （3）我第一节课上数学课或上英语课。 （4）李梅是三好学生或优秀团员。 （5）张三生于1987年或1988年。 （6）老王或小李有一个去上海出差。 （7）李明是软件学院的学生，他住在312室或 313室。
16
定义2.1.4 设P，Q是两个命题，命题 “如果P，则Q”称为P蕴涵Q，记以PQ。 真值规定： PQ是假的当且仅当P是真的而Q是假的。
例. P：f(x)是可微的， Q：f(x)是连续的， PQ： 若f(x)是可微的，则f(x)是连续的。
17
由定义知，如果P是假命题，则不管Q是什么命题，命题 “如果P，则Q”在命题逻辑中都被认为是真命题。 —与自然语言不一样的地方
18
定义2.1.5 设P，Q是两个命题，命题 “P当且仅当Q”称为P等价Q，记以PQ。
例如， P ： a2+b2=a2， Q： b=0， PQ： a2+b2=a2当且仅当b=0 。
19
例2.1.1 如果你走路时看书，那么你会成为近视眼。 令P：你走路；Q：你看书； R：你会成为近视眼。
20
例2.1.2 除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。 令P：他书面通知我； Q：他口头通知我； R：我参加明天的会议。
21
例2.1.3 设P，Q，R的意义如下： P：苹果是甜的；Q：苹果是红的； R：我买苹果。 试用日常语言复述下述复合命题： (1) (PQ)R (2) (PQ)R 解：(1)如果苹果甜且红，那么我买; (2)我没买苹果，因为苹果不甜也不红. 非P应该是什么？
22
2.2 命题公式
23
1 公式 我们用大写的英文字母P，Q，R，…等代表一个抽象的命题，或称为命题符号。 定义2.2.1 命题符号称为原子。
定义 命题符号称为原子。 例如，Q，S，…等都是原子。
24
命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式； (2) 0、1是公式；
定义2.2.2 命题公式 命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式； (2) 0、1是公式； (3) 若G，H是公式，则(G)，(GH)， (GH)，(GH)，(GH)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3) 得到的符号串。
25
规定： 公式(G)的括号可以省略，写成G。 整个公式的最外层括号可以省略。 五种逻辑联结词的优先级按如下次序递增： ，，，，
五种逻辑联结词的优先级按如下次序递增： ，，，， 例如，我们写符号串 PQRQSR 就意味着是如下公式： ((P(QR))(Q((S)R)))
26
2 解释 定义 设G是命题公式，A1, …, An是出现在G中的所有原子。 指定A1, …, An的一组真值，则这组真值称为G的一个解释。 设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。
27
例 G=PQ，设解释I，I’如下： I： I’： 则TI (G)=1，TI’ (G)=0 注意：该例子中写成G=1或G=0是错误的！
P Q
28
定义2.2.4 公式G在其所有可能的解释下所取真值的表，称为G的真值表。 显然，有n个不同原子的公式，共有2n个解释。
29
例：G=(PQ)R，其真值表如下： P Q R G 1
30
练习：请画出 P ， PQ， PQ， PQ，PQ的真值表。
31
若公式G中出现的所有原子为A1，…，An，有时我们用{m1，…，mn}表示G的一个解释I，其中
例.公式G=(PQ)R的真值表中第二个解释就可以记为{P，Q，R}
32
定义2.2.5 公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；
33
从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。
考虑G1= (P→Q) →P， G2=(P →Q) P， G3=P P。 从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。 P Q G1 G2 G3 1
34
练习：用真值表判断公式 （P→Q）→（（Q →R）→（P→R））的类型
35
G是恒真的 iff G是恒假的。 G是可满足的 iff 至少有一个解释I，使G在I下为真。 若G是恒真的，则G是可满足的； 反之不对。 如果公式G在解释I下是真的，则称I满足G； 如果G在解释I下是假的，则称I弄假G。
36
练习：求满足公式（ P →Q ）→P Q的解释和弄假它的解释。
37
在逻辑研究和计算机推理以及决策判断中，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以恒真公式在数理逻辑研究中占有特殊且重要的地位。
38
3 判定问题 能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。
因为一个命题公式的原子数目有限(n)，从而解释的数目是有限的(2n)，所以命题逻辑的判定问题是可解的(可判定的，可计算的). 结论:命题公式的恒真，恒假性是可判定的.
39
作业: 习题2.1-3， 习题2.2-1、3、4 下周二（２００７年４月１０日）交
40
§2.3 命题公式的等价关系 和蕴涵关系
41
1 公式的等价 定义2.3.1 称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。
公式G，H等价 iff 公式GH恒真。 公式间的等价关系有自反性、对称性、传递性。
42
基本等价式 1) (GH)=(GH)(HG)； 2) (GH)=(GH)； 3) GG=G，GG=G； (等幂律)
4) GH=HG，GH=HG； (交换律) 5) G(HS)=(GH)S， G(HS)=(GH)S； (结合律) 证明方法？
43
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 ） 上述等价式可用真值表验证。
44
证明命题公式恒真或恒假的两个方法 方法一. 真值表方法。 即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。
45
方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。
例.（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
46
应用基本等价式的例子 例. （ P →Q ）→ P Q = ( P Q) (P Q) = (P Q) (P Q)
= P ( Q Q) =P 1=P
47
例. 证明： (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) =右
48
练习： 证明： P →（Q →R）= P Q →R 问： （P →Q）→R与P Q →R是否等价？
49
例.世界冰球赛正在激烈进行，看台上三位观众
正在热烈地议论着这次比赛的名次。 甲：中国第一，匈牙利第三 乙：奥地利第一，中国第三 丙：匈牙利第一，中国第二 比赛结束后，发现这三位观众每人恰好都猜对了 一半。假设无并列名次。 问：中国、奥地利、匈牙利各队的名次。 解： 设P1:中国第一； P2:中国第二； P3:中国第三 Q1:奥地利第一 R1:匈牙利第一； R3:匈牙利第三
50
由于甲、乙、丙个猜对一半，故有： （P1 R3） ( P1 R3)=1 (1)
（Q1 P3） ( Q1 P3)= (2) （R1 P2） ( R1 P2)= (3) 无并列名次： P1Q1=0， P1R1=0，Q1R1=0，P3R3=0 （*） 每个国家只能得一个名次： P1P2=0，P1P3=0，P2P3=0，R1R3= （**）
51
(1)(2)左边合取，利用（*）（**）化简得： P1 R3 Q1 P3 (4)
(4)(3)左边合取，利用（*）（**）化简得： P1 R3 Q1 P3 R1 P2 而右边合取得1。 由此得出结论： 奥地利第一，中国第二，匈牙利第三
52
2 完备集 定义2.3.2 完备集 设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。 可以证明，{，}，{，}都是完备集。
53
证明 {，} 是完备集 证明： PQ = ( P Q) PQ = PQ= (PQ)
PQ = (PQ) (QP) = ( P Q) ( Q P) = ((P Q)) ((QP))
54
定义2.3.3 与非式 设P，Q是两个命题，命题 “P与Q的否定”称为P与Q的与非式，记作PQ。 “”称作与非联结词。
真值规定:PQ为真 iff P,Q不同时为真。 由定义可知： PQ=(PQ)。
55
定义2.3.4 或非式 设P，Q是两个命题，命题 “P或Q的否定”称为P与Q的或非式，记作PQ， 称作或非联结词。
定义 或非式 设P，Q是两个命题，命题 “P或Q的否定”称为P与Q的或非式，记作PQ， 称作或非联结词。 真值规定：PQ为真 iff P，Q同时为假。 由定义可知： PQ=(PQ)
56
{}是完备集 P = (P P) =PP PQ = ( P Q) = (P) (Q)
=(PP)(QQ) PQ= （PQ）= (PQ) = ((PQ) (PQ))=(PQ)(PQ) 读者可以自己证明{}也是完备集。
57
3 公式的蕴涵 逻辑的一个重要功能是研究推理。固然， 依靠等价关系可以进行推理。但是，进行 推理时，不必一定要依靠等价关系，只需
蕴涵关系就可以了。 例.若三角形等腰，则两底角相等， 这个三角形等腰， 所以，这个三角形两底角相等。 例.若行列式两行成比例，则行列式值为0， 这个行列式两行成比例， 所以，这个行列式值为0。
58
上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为： 若P则Q，P，所以Q。
59
设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。
定义 蕴涵 设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。
60
注意： 符号“”和“=” 一样，它们都不是逻辑联结词，因此，G=H，GH也都不是公式。
定义 蕴涵 注意： 符号“”和“=” 一样，它们都不是逻辑联结词，因此，G=H，GH也都不是公式。 是一种部分序关系。 公式G蕴涵公式H iff 公式GH是恒真的。 例. (PQ)P，(PQ)Q
61
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。
62
是一种部分序关系 证明：要证明公式间的蕴涵关系是部分序关系，需要证明其具有自反性、反对称性和传递性。
自反性：任取公式G，有G G 恒真，因此， G G。 反对称性：若G H，H G，则 G H，H G恒真，从而, (G H) (H G)恒真，即，G H恒真，故G=H。
63
是一种部分序关系 传递性：若GG1，G1H，则对G, G1, H的任意解释I，若I满足G，则由GG1知，I满足G1，再由G1H知，I满足H。因此，GH。
64
定义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。 设G’ = G1 … Gn ，则公式H是G1, …, Gn的逻辑结果 当且仅当公式G’ 蕴涵 H 当且仅当公式 G’ H 是恒真的 当且仅当公式((G1 … Gn)H)是恒真的。 一个前提扩展到了多个前提。
65
定理2.3.1 如果H1, …, Hm，P共同蕴涵公式Q，则H1, …, Hm共同蕴涵公式PQ。
例. 因为公式PQ，QR，P共同蕴涵R，所以PQ，QR共同蕴涵PR。
66
定理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。
67
4 演绎 定义 设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列： G1, G2, …, Gk 其中，Gi （1≤i ≤ k）或者属于S，或者是某些 Gj (j<i)的逻辑结果。 并且 Gk就是G。 称公式G为“此演绎的” 逻辑结果，或称从S演绎出G。 有时也记为SG。
68
例 设S={PQ，QR，PM，M} 则下面的公式序列: M，PM，P，PQ，Q，QR，R 就是从S推出R的一个演绎。
69
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)。
70
定理2.3.2 设S是公式集合，G是一个公式。于是，从S演绎出G的充要条件是G是S的逻辑结果。
证明：必要性，设从S演绎出G，令 G1，…，Gk（即是G） 是这个演绎。 对任意 Gi (i=1，…，k)，往证Gi 是S的逻辑结果。 对i用归纳法: (1) 当i=1时，因G1S，显然, G1 … G1 是恒真公式，故S G1 ，即 G1 是S的逻辑结果。
71
(2) 设i<n时，命题成立。 (3) 当i=n时， 若 GnS，则S Gn，归纳法完成. 若Gn是某些Gj (j<n)的逻辑结果，不妨设 (Gj1 …Gjh )Gn (1) 其中j1，…，jh都小于n。 由归纳假设知，SGjm ，m=1，…，h。由引理知：S( Gj1 …Gjh ) (2) 根据(1)，(2)式及蕴涵关系的传递性，得 S Gn 即Gn是S的逻辑结果，归纳完成。
72
充分性，若G是S的逻辑结果，由演绎的定义知，G是如下演绎： H1 ，…，Hm ，G 的逻辑结果，其中 H1 ，…，Hm 是S中所有公式.
注:如果S中一部分公式就可以演绎出G, 则再添加上S中剩余的公式, 也是可以演绎出G的。
73
演绎定理 定理2.3.3 设S是前提公式集合，G，H是两个公式。 如果从S∪{G}可演绎出H，则从S可演绎出GH。
证明：因为从S∪{G}可演绎出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。
74
基本蕴涵式 PQP PQQ PPQ QPQ P(PQ) Q(PQ) (PQ)P
75
基本蕴涵式 (PQ)Q P，QPQ P，PQQ P，PQQ Q，PQP PQ，QRPR
PQ，PR，QRR
76
7 小结：公式间蕴涵的证明方法 给出两个公式G，H，证明G蕴涵H。 真值表法； 证G H是恒真公式； 利用一些基本等价式及蕴涵式进行推导；
7 小结：公式间蕴涵的证明方法 给出两个公式G，H，证明G蕴涵H。 真值表法； 证G H是恒真公式； 利用一些基本等价式及蕴涵式进行推导； 任取解释I，若I满足G，往证I满足H； 反证法，设结论假，往证前提假 (即证明H G)。
77
真值表法 将公式G和公式H同列在一张真值表中，扫描公式G所对应的列，验证该列真值为1的每一项，它所在行上相应公式H所对应列上的每一项必为1（真），则公式G蕴涵H。
78
证G H是恒真公式 1 例. 设A、B和C为命题公式，且AB。请分别阐述（肯定或否定）下列关系式的正确性。
（1）(AC) (BC)；--正确 （2）(AC) ( BC)。--不正确 A B C AB AC BC ACBC AC BC (AC)(BC) 1
79
例 设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
80
利用一些基本等价式及蕴涵式进行推导 例 设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。
81
例. 设A= P Q，B=(RQ) ((PR) Q)，
任取解释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。
82
反证法，设结论假，往证前提假 (即证明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) Q蕴涵 P Q。
83
7 公式蕴涵的证明方法 若给出前提集合S={G1 ，…，Gk }，公式G，证明SG有如下两种方法： 1. G1 … Gk G 2. 形式演绎法
84
8 形式演绎法 根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则：
8 形式演绎法 根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则： 规则1. 可随便使用前提。 (根据演绎定义) 规则2. 可随便使用前面演绎出的某些公 式的逻辑结果。 (根据演绎的定义) 规则3. 如果需要演绎出的公式是PQ的 形式，则可将P做为附加前提使 用，而力图去演绎出Q。 (根据定理2.3.3)。
85
例2.3.1 证明{(PQ)，(PR)，(QS)}SR PQ 规则1 PQ 规则2，根据1 QS 规则1
PS 规则2，根据2，3 SP 规则2，根据4 PR 规则1 SR 规则2，根据5，6 SR 规则2，根据7
86
例2.3.2 证明{P(QS)，RP，Q}RS RP 规则1 R 规则3 P 规则2，根据1，2 P(QS) 规则1
87
例2.3.3 若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。 问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止? 令 P： 厂方拒绝增加工资； Q： 罢工停止； R： 工厂经理辞职； S： 罢工超过一年。
88
于是， G1：(P(RS))Q G2：P G3：S H： Q 要证明： H是{G1，G2，G3}的逻辑结果。 1. S 规则1 2. SR 规则2，根据1
89
3. (RS) 规则2，根据2 4. P 规则1 5. P(RS) 规则2，根据3，4 6. (P(RS))Q 规则1 7. Q 规则2，根据5，6 亦即，罢工不会停止。
90
例.一个公安人员审查一件盗窃案，已知的事实如下：
(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并不富裕
91
再将各前提写出： 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
92
作业 习题2.3 –1、7、8、9 2007年4月17日交
93
§2.4 范式
94
范式的引入 在命题逻辑中，对于含有有限个原子的命题公式来说，用真值表的方法，总可以在有限的步骤内确定它的真值，因此判定问题总是可解的。
但是我们知道，这种方法并不理想，因为公式每增加一个原子，真值表的行数就增加一倍。为了给出另一种方法，我们将介绍命题公式的一种标准形式，即范式，两个命题公式是否等价及一个公式恒真、恒假、可满足的判定，都将由公式的范式来解决。
95
1 析取范式和合取范式 定义2.4.1 原子或原子的否定称为文字。 例. P，P是文字。
1 析取范式和合取范式 定义 原子或原子的否定称为文字。 例. P，P是文字。 定义 有限个文字的析取式称为一个子句； 有限个文字的合取式称为一个短语。 特别，一个文字既可称为是一个子句，也可称为是一个短语。 例. P，PQ，PQ是子句，P，PQ，PQ是短语。 在命题逻辑中，对于含有有限个原子的命题公式来说，用真值表的方法，总可以在有限的步骤内确定它的真值，因此判定问题总是可解的。但是我们知道，这种方法并不理想，因为公式每增加一个原子，真值表的行数就增加一倍。为了给出另一种方法，我们将介绍命题公式的一种标准形式，即范式，两个命题公式是否等价及一个公式是否恒假(或恒真)的判定，都将由公式的范式来解决。
96
定义2.4.3 析取范式、合取范式 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。
有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。 例如，P，PQ，PQ，(PQ)(PQ)是析取范式。 P，PQ，PQ，(PQ)(PR)是合取范式。
97
定理2.4.1 对于任意命题公式，都存在等价于它的析取范式和合取范式。 证明：对于公式G，通过如下算法即可得出等价于G的范式：
步2. 使用(H)=H和摩根律，将G中所有的否定 号都放在原子之前。 步3. 反复使用分配律，即可得到等价于G的范 式。
98
例： G = (P(QR))S =P(QR)S =P(QR)S ……………. (析取范式)
=P(QR)(S(QQ)) =P(QR)(SQ)(SQ) (析取范式) =(PS)(QR) =(PSQ)(PSR) …… (合取范式)
99
2 主析取范式 定义 设P1,…,Pn是n个不同原子，一个短语如果恰好包含所有这n个原子或其否定，且其排列顺序与P1,…,Pn的顺序一致，则称此短语为关于P1,…,Pn的一个极小项。 例.对原子P，Q，R而言，PQR，PQR，PQR都是极小项，但是，P，PQ不是极小项，而PQ对原子P，Q而言是极小项。 显然，共有2n个不同的极小项。
100
极小项与解释的1-1对应关系 对于n个原子P1,…,Pn而言，其不同的解释共有2n个，对于P1,…,Pn的任一个极小项m，2n个解释中，有且只有一个解释使m取1值。 证明：任取一个极小项，按照如下方法构造其解释：对原子Pi (1≤i≤n)，如果Pi出现在该极小项中，Pi指定为1；如果Pi的否定出现在该极小项中，Pi指定为0。则构造出来的解释使该极小项取1值, 而且只能构造出来一个这样的解释。
101
极小项与解释的1-1对应关系 例如，对P，Q，R而言，PQR是极小项，解释{P，Q，R}使该极小项取1值，其他解释都使该极小项取0值。
102
解释与n位二进制数的1-1对应关系 如果将真值1，0看做是数，则每一个解释对应一个n位二进制数。
假设使极小项m取1值的解释对应的二进制数为i，今后将m记为mi。
103
例: 对P，Q，R而言，PQR是极小项，解释(0，1，0)使该极小项取1值，解释(0，1，0)对应的二进制数是2，于是PQR记为m2。 对P，Q，R而言，8个极小项与其对应的解释如下：
104
极小项 解释 记法 PQR 000 m0 PQR 001 m1 PQR 010 m2 PQR 011 m3 PQR 100 m4 PQR 101 m5 PQR 110 m6 PQR 111 m7
105
一般地，对P1,…,Pn而言，2n个极小项为
106
定义2.4.5主析取范式 设命题公式G中所有不同原子为P1,…,Pn，如果G的某个析取范式G’中的每一个短语，都是关于P1,…,Pn的一个极小项，则称G’为G的 主析取范式。 恒假公式的主析取范式用0表示。
107
3 主析取范式（存在性） 定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。
3 主析取范式（存在性） 定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。 证明：设命题公式G中所有不同原子为P1，…，Pn，则等价于它的主析取范式的求法如下： (a) 将公式G化为析取范式G’。(由定理2.4.1知，存在析取范式G’，使得G=G’) (b) 删去析取范式中所有恒假的短语。 (c) 用等幂律将短语中重复出现的同一文字化简为一次出现，如，PP=P。
108
(d) 对于所有不是关于P1，…，Pn的极小项 的短语使用同一律，补进短语中未出现的 所有命题原子，并使用分配律展开，即，
如果Gi’不是关于P1,…,Pn的极小项，则Gi’ 中必然缺少原子P j1,…,Pjk，则 在定理2.4.2的证明中，实际上已经给出了求公式的主析取范式的方法。 于是将G’中非极小项Gi’化成了一些极小项之析取。对G’中其他非极小项也做如上处理，最后得等价于G的主析取范式G*。
109
例 求G=(RP)(Q(PR)) 的主析取范式 解： G =(RP)(Q(PR))
=(R P)(Q P)(Q R) =(P R)(P Q)(Q R) =((PR)(QQ))((PQ)(RR)) ((QR)(PP)) =(PQR)(PQR)(PQR) (PQR)
110
G的主析取范式为(PQR) (PQR) (PQR) (PQR)
求G=(PQ)(PR)(QR)的主析取范式 P Q R G 1 寻找与公式G等价的主析取范式，也可以通过真值表来做。 如果真值表中没有一行真值为1，则G’=0 G的主析取范式为(PQR) (PQR) (PQR) (PQR)
111
真值表法写主析取范式的正确性 定理. 在真值表中，使得公式为真的解释所对应的极小项的析取 即为此公式的主析取范式。
即为此公式的主析取范式。 证明：给定公式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等价的主析取范式。
112
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不等价。
113
5 主析取范式（唯一性） 定理2.4.4 对于任意公式G，存在唯一一个与G等价的主析取范式。 （唯一性）
114
6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。
6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 证明：充分性，若有一个原子P及其否定P同时出现在短语中，则此短语有形式： PP… 显然，不管是什么解释I，PP在I下取0值，于是此短语在I下取0值，故此短语恒假。
115
必要性. 若短语恒假，而任意原子及其否定均不同时在短语中出现。那么，取这样的解释I：指定带有否定号的原子取0值，不带否定号的原子取1值，显然，此短语在这个解释I下取1值，与此短语恒假矛盾。
116
定理2.4.5 命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。
证明： 设G的析取范式如下： G=G1…Gn 其中Gi是短语，i=1，…，n。 显然，公式G恒假的充要条件是每个Gi恒假。 再根据引理，此定理结论显然成立。
117
例2.4.1 判断公式G=(PQ)(QR)(RP)是否恒假? 解： G=(PQ)(QR)(RP)
=((PQ)(QQ)(PR)(QR))(RP) =(PQR)(QQR)(PRR)(Q RR)(PQP)(QQP)(PRP) (QRP) 故公式G不是恒假的。
118
例2.4.2 判断公式G=(PQ)PQ是否恒假? 解：G=(PQ)PQ =(PQ)PQ
=(PPQ)(QPQ) 故公式G是恒假的。
119
7 判定公式是否恒真的其它方法 把公式化成主析取范式， 公式恒假时，主析取范式没有极小项； 公式恒真时，主析取范式有全部极小项。
120
2. 一种判定算法 对任给要判定的命题公式G，设其中有原子P1,P2,…,Pn，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2,…, Pn，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。
121
例2.4.3 (PQR)(PQ)(PR) (QR)QR RR 1 P取1值 P取0值 Q取1值 Q取0值 R取1值
122
补充:主合取范式 模仿主析取范式的概念，引进主合取范式的概念。
定义：设P1，…，Pn是n个不同原子，一个子句如果恰好包含所有这n个原子或其否定，且其排列顺序与P1，…，Pn的顺序一致，则称此子句为关于P1，…，Pn的一个极大项。 定义：设命题公式G中所有不同原子为P1，…，Pn，如果G的某个合取范式G’中的每一个子句，都是关于P1，…，Pn的一个极大项，则称G’为G的主合取范式。
123
极小项与极大项性质 P Q R 极小项 极大项 1 m0= P QR M0=PQR m1= P QR
m0= P QR M0=PQR 1 m1= P QR M1=PQR m2= P QR M2=PQR m3= P QR M3=PQR m4= P Q R M4=PQR m5= P Q R M5=PQ R m6= P Q R M6=P Q R m7= P Q R M7=PQR
124
极小项与极大项性质 对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）所有极小项的析取式恒真。
125
极大项有如下性质： （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
126
主合取范式与主析取范式之间的关系 例. 若PQR为一公式G的主合取范式，则 G =G = M0 =(M1M2…M7)
127
从一公式A的主合取范式（PQ）求其主析取范式的步骤为：
（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)
128
例.若（PQ）（PQ）（PQ）为一公式H的主析取范式，
H=H =((PQ）（PQ）（PQ)) =（（m0 m1 m3） = (m2) =M2 = PQ 为H的主合取范式。
129
由主析取范式求主合取范式： （1）求出A的主析取范式中没有包含的所有极小项。m2 （2）求出与（1）中极小项下标相同的极大项。 M2 （3）将（2）求出的所有极大项合取起来，即得A的主合取范式。
130
定理. 对任意命题公式，存在唯一一个与其等价的主合取范式。
证明: (存在性) 设命题公式G中所有不同原子为P1，…，Pn，则等价于它的主合取范式的求法如下： (a) 将公式G化为合取范式G’。(由定理2.4.1知，存在合取范式G’，使得G=G’) (b) 删去合取范式中所有恒真的子句。 (c) 用等幂律将子句中重复出现的同一文字化简为一次出现，如，P P=P。
131
(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’’。
132
(唯一性)也就是证明对任意两个关于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不等价。
133
用真值表法求主合取范式的正确性 定理. 在真值表中，使得公式为假的解释所对应的极大项 的合取即为此公式的主合取范式。
定理. 在真值表中，使得公式为假的解释所对应的极大项 的合取即为此公式的主合取范式。 证明： 给定公式G，设用这种方法写出主合取范式为G’，往证G= G’。 任意取G, G’ 的一个解释I。 如果I满足G，则唯一的一个在I下为假的那个极大项不在G’中出现，而I使所有其他的极大项取1，这样，G’在I下的真值是1； 如果I弄假G，则唯一的一个在I下为假的那个极大项出现在G’中，从而G’在下取0值。 这样，G与G’是等价的。
134
求主合取范式和主析取范式的方法 方法一. 真值表法。主析取范式恰好是使得公式为真的解释所对应的极小项的析取组成，主合取范式恰好是使得公式为假的解释所对应的极大项的合取组成。 方法二. 公式推导法。
135
例 求公式G= P→(Q→R)的主析取范式与主合取范式。
1
136
解：（1）使用真值表法。 根据真值表中使得公式为真的解释，所对应的极 小项的析取即为其主析取范式： G=(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) = m0 m1 m2 m3 m4 m5 m7 根据真值表中使得公式为假的解释，所对应的极 大项的合取即为其主合取范式： G= P Q R= M6
137
（2）公式推导法 G= P→(Q→R) = P Q R =（P（QQ）（RR）） （ Q（PP）（RR）） （R（PP）（QQ）） = (PQR) (PQR)(PQR) ( PQR) (PQR) (PQR) = m0 m1 m2 m3 m4 m5 m7 = M6
138
定理. 命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。
证明：设公式G的合取范式为：G’=G1G2…Gn 若公式G恒真，则G’恒真，即子句Gi,i=1,2,…n恒真 为其充要条件。下面只需证明：子句是恒真的当且仅当 至少有一个原子及其否定(也称互补对)同时在此子句中 出现。 若有一个原子P及其否定P同时出现在子句中，则此子句有形式： PP… 显然，不管是什么解释I，PP在I下取１值，于是此子句在I下取１值，故恒真。 假设子句恒真，但每个原子和其否定都不同时出现在其中。则可以给定一个解释I，使带否定号的原子为1，不带否定号的原子为0，那么此子句在解释I下的取值为0。这与子句恒真矛盾。
139
主合取范式与主析取范式的应用 利用主合取范式与主析取范式可求解判定问题
主析取范式：公式恒假时，主析取范式没有极小项（G’=0）；公式恒真时，主析取范式包含所有极小项。 主合取范式：公式恒假时，主合取范式包含所有极大项；公式恒真时，主合取范式没有极大项(G’=1)。
140
由于任意公式的主范式是唯一的，所以可以分别求出两 个给定的公式的主范式，若二者主范式相同，则给定的
证明等价式成立 由于任意公式的主范式是唯一的，所以可以分别求出两 个给定的公式的主范式，若二者主范式相同，则给定的 两公式是等价的，否则，给定的两公式不等价。 例 判断P→(Q→R)与（P Q）→ R是否等价。 证明： 利用求主合取范式的方法来判断。 由前知，P→(Q→R)的主合取范式为：M6。 下面求（P Q）→ R的主合取范式。 （P Q）→ R = （P Q） R =（ PQ）R =（ PR）（QR） =（ P（QQ）R）（（PP）QR） =（ PQR） （ PQR） （PQR） = M2 M4 M6 二者的主合取范式不相同，因此，这两个公式不等价。
141
作业 习题2.4--5
Similar presentations
