1
第一章 命题逻辑
§ 1.命题
§ 2.命题联结词
§ 3.命题变元与命题公式
§ 4.等价式
§ 5.永真蕴含式
§ 6.命题联结词总结
§ 7.范 式 和 判 定
§ 8.推论规则和证明方法
2
§ 1命题
,定义,,具有唯一真值的陈述句叫命题 。
讨论定义：
（１）命题可以是真的，或者是假的，但不能同时为真又为假。
（２）命题分类：
ⅰ )原子命题 （基本命题、本原命题）：一个命题，不能分解成为更简单的命题。
例：我是一位学生。
3
§ 1命题
ⅱ )分子命题 （复合命题）,若干个原子命题使用适当的联结词 所组成的新命题例：我是一位学生和他是一位工人
(3)命题所用符号：常用大写２６个英文字母表示命题。
用Ａ、Ｂ、Ｃ．．．．Ｚ表示。
(4)命题中所有的“真”用“Ｔ”表示，
命题中所有的“假”用“Ｆ”表示。
4
§ 1命题例,判断下列语句是否为命题。
＊ 陈述句一般为命题
（ 1）十是整数。 （Ｔ）
（ 2）上海是一个村庄。（Ｆ）
（ 3）今天下雨。
（ 4）加拿大是一个国家。（Ｔ）
（ 5）２是偶数而３是奇数。
（ 6）她不是护士。
（ 7）１＋１０１＝１１０
（ 8）今天是星期天。
5
§ 1命题命令句，感叹句，疑问句均不是命题。
（ 1）把门关上！
（ 2）你到哪里去？
语句既为真，同时又包含假的不是命题，这样的句子称为,悖论,。
（ 3）他正在说谎。
（在命题逻辑中不讨论这类问题）
6
§ 2命题联结词在命题演算中也有类似的日常生活中的联结词称做：,命题联结词” 下面先介绍五个常用的命题联结词。
１,否定词,（否定运算、非运算）
（１）符号?,读作“非”，“否定”
设命题为Ｐ，则在Ｐ的前面加否定词?,变成?
Ｐ,?Ｐ读做“Ｐ的否定”或“非Ｐ”
7
§ 2命题联结词
（２）定义：严格由真值表定义
（３）举例：
Ｐ：北京是一座城市。
Ｐ：北京不是一座城市。
Ｑ：每一种生物均是动物。 F
Ｑ：有一些生物不是动物。 T
这里?Ｑ不能讲成“每一种生物都不是动物”为假命题了。
对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。
P?P
T F
F T
8
§ 2命题联结词
２．合取词 （“合取”、“积”、“与”运算）
符号,Λ”
设Ｐ，Ｑ为两个命题，则Ｐ ΛＱ称Ｐ与Ｑ的合取，
读作：“Ｐ与Ｑ”、“Ｐ与Ｑ的合取”、
“Ｐ并且Ｑ”等。
定义（由真值表给出）：
9
§ 2命题联结词
P Q PΛ Q QΛP
F F F F
F T F F
T F F F
T T T T
Ｐ ΛＱ真值表如下,
10
§ 2命题联结词当且仅当Ｐ和Ｑ的真值均为“Ｔ”，则（Ｐ ΛＱ）
的真值为“Ｔ”。否则，其真值为“Ｆ”。
注意,Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ
和Ｑ的位置可以交换而不会影响Ｐ ΛＱ的结果。
11
§ 2命题联结词举例：
(a) P：王华的成绩很好
Q：王华的品德很好。
则Ｐ ΛＱ：王华的成绩很好并且品德很好。
(b) P：我们去种树
Q：房间里有一台电视机则Ｐ ΛＱ：我们去种树与房间里有一台电视机。
12
§ 2命题联结词
(c) P：今天下大雨 Q,3+3=6
则Ｐ ΛＱ：今天下大雨和 3+3=6
由例 (b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。
13
§ 2命题联结词
(d) 下列语句不是合取联结词组成的命题。
P,王大和王二是亲兄弟。
Q,他打开箱子然后（而后）拿出一件衣服来。
14
§ 2命题联结词
３．析取词 （或运算）
（１）符号,∨,
设Ｐ、Ｑ为二个命题，则（Ｐ ∨ Ｑ）称作Ｐ与Ｑ
的“析取”，读作：“Ｐ或Ｑ”。
（２）定义（由真值表给出）：
15
§ 2命题联结词当且仅当Ｐ、Ｑ均为“Ｆ”时，（Ｐ ∨ Ｑ）为
“Ｆ”。否则，其真值为“Ｔ”．
P Q P∨ Q
F F F
F T T
T F T
T T T
Ｐ ∨ Ｑ真值表如右：
16
§ 2命题联结词区分“可兼或”与“不可兼或（异或，排斥或）”
析取词为可兼或即,P和 Q均为,T”时（ P∨ Q）
为,T”
例如：
灯泡有故障或开关有故障。
今晚写字或看书。
今天下雨或打雷。
以上例句均为可兼或。
17
§ 2命题联结词
“不可兼或”中当 P和 Q均为,T”时，则 P异或 Q
为,F”。
（异或用,▽,表示） P Q P▽ Q
F F F
F T T
T F T
T T F
18
§ 2命题联结词例：
他通过电视看杂技 或 到剧场看杂技。
他乘火车去北京 或 乘飞机去北京。
以上两句均为不“可兼或”。
19
§ 2命题联结词
４．单条件联结词,（“蕴含”联结词、蕴含词）
（１）符号,→”，读作：“如果 … 则 …”,
“蕴含”
Ｐ、Ｑ为二个命题，（Ｐ →Ｑ）为新的命题，读作：“如果Ｐ则Ｑ”，“Ｐ蕴含Ｑ”，“Ｐ仅当Ｑ”，“Ｑ当且Ｐ”，“Ｐ是Ｑ的充分条件”。
（２）定义
20
§ 2命题联结词
（由真值表定义）：
P Q P→Q
F F T
F T T
T F F
T T T
21
§ 2命题联结词当Ｐ为“Ｔ”，Ｑ为“Ｆ”时，则
（Ｐ →Ｑ）为“Ｆ”，否则（Ｐ →Ｑ）均为
“Ｔ”。
Ｐ：称为前件、条件、前提、假设
Ｑ：称为后件、结论。
（３）举例：
P：我拿起一本书
Q：我一口气读完了这本书
22
§ 2命题联结词
P→Q：如果我拿起一本书，则我一口气读完了这本书。
(b) P：月亮出来了
Q,3× 3=9
P→Q：如果月亮出来了，则
3× 3=9。
通常称,(a)为形式条件命题。
——前提和结果有某种形式和内容上的联系。
23
§ 2命题联结词
(b)为实质条件命题。 ——前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。
所以,是形式条件命题一定是实质条件命题,反之不一定。,→”是实质条件命题。
例：
Ｐ：我买到了鱼；Ｑ,我吃鱼。
24
§ 2命题联结词
Ｐ →Ｑ：如果我买到了鱼，则我吃鱼。
但“如果我没买到鱼，则我吃鱼”，这在日常生活中是不可能的，但在单条件命题的定义中是允许的。
25
§ 2命题联结词可以证明：
Ｐ →Ｑ Q →? P
原命题 逆反命题
Ｑ →ＰＰ →?Ｑ
逆命题 反命题
26
§ 2命题联结词列出真值表,由真值表得：
原命题?逆反命题；逆命题?反命题。
P Q P→Q? Q→?P Ｑ →P?Ｐ →?Ｑ
F F T T T T
F T T T F F
T F F F T T
T T T T T T
27
§ 2命题联结词
５．双条件联结词 （“等价”词、“同”联结词、
“等同”词）
（１）符号,?”
设Ｐ、Ｑ为二个命题，则Ｐ?Ｑ读作：“Ｐ当且仅当Ｑ”，“Ｐ等价Ｑ”,“Ｐ是Ｑ的充分必要条件”。
（２）定义（见真值表）：
28
§ 2命题联结词真值表,
每当Ｐ和Ｑ的真值相同时，
则（Ｐ?Ｑ）的真值为
“Ｔ”，否则（Ｐ?Ｑ）
的真值为“Ｆ”。
P Q P?Q
F F T
F T F
T F F
T T T
29
§ 2命题联结词
（３）举例：
（ a）设
Ｐ：△ ABC是等腰三角形
Ｑ：△ ABC有两只角相等
Ｐ?Ｑ：△ ABC是等腰三角形当且仅当△ ABC中有两只角相等。
30
§ 2命题联结词
（ b）下面均为等价联结词：
春天来了当且仅当燕子飞回来了。
平面上二直线平行，当且仅当这二直线不相交。
２＋２＝４当且仅当雪是白色的。
31
§ 2命题联结词
（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、
Ｑ交换位置不会改变真值表中的值。
（５）Ｐ当且仅当Ｑ Ｐ?Ｑ
Ｐ仅当Ｑ Ｐ →Ｑ
Ｐ当且Ｑ Ｑ →Ｐ
32
§ 2命题联结词
６．命题联结词在使用中的优先级
（１）先括号内，后括号外
（２）运算时联结词的优先次序为,? Λ ∨
→?
（由高到低）
33
§ 2命题联结词
（３）联结词按从左到右的次序进行运算例
Ｐ ∨ （Ｑ ∨ Ｒ）可省去括号因为“Ｖ”运算是可结合的。
（?Ｐ ∨ Ｑ） ∨ Ｒ可省去括号 因为符合上述规定而 Ｐ →（Ｑ →Ｒ） 中的括号不能省去，因为,→”
不满足结合律。
34
§ 2命题联结词
（４）最外层的括号一律均可省去
（Ｐ →Ｑ ∨ Ｒ）可写成Ｐ →Ｑ ∨ Ｒ
７．命题联结词小结：
（１）五个联结词的含义与日常生活中的联结词的含义大致相同。
（２）,或,可分为可兼或（ ∨ ）和异或（ ▽ ）
（不可兼或）
35
§ 2命题联结词
(3) 除,?”为一元运算外，其余四个均为二元运算。
(4),→,分为形式条件和实质条件命题,当前件为“Ｆ”时，不论后件怎样，则单条件命题的真值均为“Ｔ” 。
(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。
36
§ 2命题联结词以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，
首先要把推理所涉及到的各命题符号化。
步骤如下：
①找出各简单命题，分别符号化。
②找出各联结词，把简单命题逐个联结起来。
37
§ 2命题联结词例,将下列命题符号化：
（ 1）李明是计算机系的学生，他住在 312室或
313室。
（ 2）张三和李四是朋友。
（ 3）虽然交通堵塞，但是老王还是准时到达了车站。
（ 4）只有一个角是直角的三角形才是直角三角形。
（ 5）老王或小李中有一个去上海出差。
38
§ 2命题联结词解：
（ 1）首先用字母表示简单命题。
P：李明是计算机系的学生。
Q：李明住在 312室。
R：李明住在 313室。
该命题符号化为,P?（ Q▽ R）
（ 2）张三和李四是朋友。是一个简单句该命题符号化为,P
39
§ 2命题联结词
（ 3）首先用字母表示简单命题。
P：交通堵塞。
Q：老王准时到达了车站。
该命题符号化为,P?Q
（ 4）首先用字母表示简单命题。
P：三角形的一个角是直角。
Q：三角形是直角三角形。
该命题符号化为,?PQ
40
§ 2命题联结词
（ 5）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为,P ▽ Q
也可符号化为：
（ PQ）?（?P?Q）或者
（ P? Q） （ P?Q）
41
§ ３命题公式约定：
（１）我们只注意命题的真假值，而不再去注意命题的汉语意义。
（２）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。
１．命题公式命题常元：表示确定的命题｛ T,F｝。
命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母Ａ … Ｚ表示。
42
§ ３命题公式命题公式,由命题变元、常元、联结词、括号，
以规定的格式联结起来的字符串。
,定义,,命题公式可按下述法则来生成：
１）孤立的命题变元是一个命题公式。
２）若Ａ是命题公式,?Ａ也为命题公式。
３）若Ａ、Ｂ是命题公式，则（Ａ ΛＢ）、（Ａ
∨ Ｂ）、（Ａ →Ｂ）、（Ａ?Ｂ）均为命题公式。
43
§ ３命题公式
４）当且仅当有限次使用
（１）（２）（３）所生成的公式才是命题公式。
例如,(?(P ∨Q)),(P→(Q →R)),((PΛQ)?R),P都是命题公式。而 (P→),(P∨?)都不是命题公式
２．命题公式的真值表,
命题变元用特定的命题来取代，这一过程称为对该命题变元进行 指派。
命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。
写成ｙ＝ｆ (x)
44
§ ３命题公式例如：公式 P?(Q?R) 定义三元函数
Y(P,Q,R)＝ P?(Q?R)
,定义,,命题公式 A在其所有可能的赋值下取得的值列成的表称为 A的真值表。
构造真值表的步骤如下：
1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。
2)按照从低到高的顺序写出命题公式的各层次。
3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。
45
§ ３命题公式
P Q P ∨ Q （Ｐ ∨ Ｑ） ΛＰ?（（Ｐ ∨ Ｑ） ΛＰ）
F F F F T
F T T F T
T F T T F
T T T T F
例１．构造命题公式?（（Ｐ ∨ Ｑ） ΛＰ）
的真值表：
46
§ ３命题公式例２．写出命题公式
Ｐ ∨ （Ｑ ΛＲ）的真值表
P Q R Ｐ ∨ （Ｑ ΛＲ )
F F F F F
F F T F F
F T F F F
F T T T T
T F F T F
T F T T F
T T F T F
T T T T T
47
§ ３命题公式由上二例可见，２个命题变元有４组真值指派；
３个命题变元有 23＝ ８组真值指派，
ｎ个则有个 2n个真值指派。
３．命题公式的永真式、永假式和可满足式例：举最简单例子：
48
§ ３命题公式
P?P P∨?P P∧?P
F T T F
T F T F
,定义,,设公式Ａ中有 n个不同的原子变元 p1,… pn,(n
为正整数 )。该变元组的任意一组确定的值（ u1,… un）
称为Ａ关于 p1,… pn的一个 完全指派,其中 ui或为Ｔ，
或为Ｆ。如果对于Ａ中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式Ａ的关于该变元组的 部分指派 。
,定义,,凡使公式Ａ取真的指派称为Ａ的 成真指派 。
49
§ ３命题公式
,定义,,如果一个命题公式的所有完全指派均为成真指派，则该公式称为 永真式 。如果一个命题公式的所有完全指派均为成假指派，则该公式称为 永假式 。既不是永真式，又不是永假式，则称此命题公式是 可满足式。
讨论：
（１）永真式的否定为永假式（?Ｔ＝Ｆ）；永假式的否定为永真式（?Ｆ＝Ｔ）。
（２）二个永真式的析取、合取、蕴含、等价均为永真式。
50
§ 4等价式
１．等价式
,定义,,如果对两个公式Ａ，Ｂ不论作何种指派，它们真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ（Ｂ）等价于Ｂ（Ａ）。
并记作：Ａ?Ｂ
51
§ 4等价式例：Ｐ ∨?Ｐ?Ｑ ∨?Ｑ
P Q P∨?P Q ∨?Q
F F T T
F T T T
T F T T
T T T T
52
§ 4等价式例：判断公式 A,(PQ)?(P?Q)
与 B,(PR)?(P?R)是否等价。
解：
列该公式的真值表：
53
§ 4等价式
P Q R?Q PQ P?Q?R PR P?R A B
T T T F T T F T T T T
T T F F T T T T T T T
T F T T T T F T T T T
T F F T T T T T T T T
F T T F F T F F T F F
F T F F F T T T F F F
F F T T T F F F T F F
F F F T T F T T F F F
54
§ 4等价式
,定理,,
命题公式Ａ?Ｂ的充要条件是Ａ?Ｂ为永真式。
说明：
,?”为等价关系符，Ａ?Ｂ表示Ａ和Ｂ有等价关系。
Ａ?Ｂ不为命题公式
,?”为等价联结词（运算符），Ａ、Ｂ为命题公式，
则（Ａ?Ｂ）也为一命题公式。
55
§ 4等价式证明：
（１）充分性：Ａ?Ｂ为永真式，即Ａ、Ｂ有相同的真值，所以Ａ?Ｂ。
（２）必要性：Ａ?Ｂ，即Ａ、Ｂ有相同的真值表，所以Ａ?Ｂ为永真式。
例：证明Ｐ?Ｐ；
Ｐ →ＱＰ ∨ Ｑ
56
§ 4等价式
P QP? P P→QP∨ Q
F F F T F T T T
F T F T F T T T
T F T T T F T F
T T T T T T T T
由定理可知,Ａ?Ａ
若Ａ?Ｂ，则Ｂ?Ａ
若Ａ?Ｂ，Ｂ?C,则Ａ?Ｃ
57
§ 4等价式下面列出１５组等价公式
（ 1） 双重否定律Ｐ?Ｐ
（ 2） 同等律 Ｐ ∨ Ｐ?Ｐ；Ｐ ΛＰ?Ｐ
（ 3） 交换律 Ｐ ∨ Ｑ?Ｑ ∨ Ｐ；
Ｐ ΛＱ?Ｑ ΛＰ；Ｐ?Ｑ?Ｑ?Ｐ
（ 4） 结合律
（Ｐ ∨ Ｑ） ∨ Ｒ?Ｐ ∨ （Ｑ ∨ Ｒ）；
（Ｐ ΛＱ） ΛＲ?Ｐ Λ（Ｑ ΛＲ）；
（Ｐ?Ｑ）?Ｒ?Ｐ?（Ｑ?Ｒ）
58
§ 4等价式
（ 5） 分配律
Ｐ Λ（Ｑ ∨ Ｒ）?（Ｐ ΛＱ） ∨ （Ｐ ΛＲ）；
Ｐ ∨ （Ｑ ΛＲ）?（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）
（ 6） 摩根律?（Ｐ ∨ Ｑ）Ｐ Λ?Ｑ；
（Ｐ ΛＱ）Ｐ ∨?Ｑ
（ 7） 吸收律 Ｐ ∨ （Ｐ ΛＱ）?Ｐ；
Ｐ Λ（Ｐ ∨ Ｑ）?Ｐ
59
§ 4等价式
（ 8） 蕴含律 Ｐ →ＱＰ ∨ Ｑ
（ 9） 等价律
Ｐ?Ｑ?（Ｐ →Ｑ） Λ（Ｑ →Ｐ）
（ 10） 零 律 Ｐ ∨ Ｔ?Ｔ；Ｐ ΛＦ?Ｆ
（ 11） 同一律 Ｐ ∨ Ｆ?Ｐ；Ｐ ΛＴ?Ｐ
（ 12） 互补律 Ｐ ∨?Ｐ?Ｔ；Ｐ Λ?Ｐ?Ｆ
（ 13） 输出律
Ｐ ΛＱ →Ｒ?Ｐ →（Ｑ →Ｒ）
60
§ 4等价式
（ 14） 归缪律
（Ｐ →Ｑ） Λ（Ｐ →?Ｑ）Ｐ
（ 15） 逆反律 Ｐ →ＱＱ →?Ｐ
说明：
（１）证明上述１５组等价公式的方法可用真值表法，把?改为?所得的命题公式为永真式，则?
成立。
61
§ 4等价式
（ 2） Λ,∨,?均满足结合律，
则在单一用 Λ,∨,?联结词组成的命题公式中，
括号可以省去 。
（ 3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。
例如,?(P?Q)?(?PQ)，
((P?Q)?(R?S))?(?(P? Q)(R? S)，
((P?Q)R)?(?(P?Q)R)
62
§ 4等价式
２．置换规则
,定义,,给定一命题公式Ｂ，其中 P1、
P2．．,Pn 是Ｂ中的原子命题变元，
若（ 1）用某些命题公式代换Ｂ中的一些原子命题变元 Pi
（ 2）用命题公式 Ａ i代换 Pi，则必须用 Ａ i代换
Ｂ中的所有 Pi
由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例
63
§ 4等价式讨论定义：
（１）用命题公式只能代换原子命题变元，而不能去代换分子命题公式 。
（２）要用命题公式同时代换同一个原子命题变元 。
（３）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。
64
§ 4等价式例,Ｐ ∨?Ｐ为一永真式，若用任何命题公式代换Ｐ，则仍为永真式
Ｐ →Ｑ为一个可满足的命题公式，若用Ｐ代换Ｑ，
则得（Ｐ →Ｐ）为永真式，但（Ｐ →Ｑ）并不是永真式。
（４）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式
65
§ 4等价式例１．
设Ｂ：Ｐ →（?QΛＰ）若用（Ｒ?Ｓ）代换Ｂ中的Ｐ，
得Ａ：（Ｒ?Ｓ） →（?QΛ（Ｒ?Ｓ））是Ｂ的代换实例，
而Ａ’：（Ｒ?Ｓ） →（?QΛＰ）不是 B的代换实例。
例２．Ｐ →?Ｑ的代换实例有：（Ｒ Λ?Ｓ） →?Ｍ，（Ｒ
Λ?Ｓ） →Ｐ，Ｑ →?（Ｐ →?Ｑ）等所以，一个命题公式的代换实例有无限个。
66
§ 4等价式下面讨论取代过程（置换规则）：
,定义,,给定一命题公式Ａ，Ａ’是Ａ的任何部分，
若Ａ’也是一命题公式，则称Ａ’是Ａ的 子命题公式 。
例,Ａ：（Ｐ ∨ Ｑ） →（Ｑ ∨ （Ｒ Λ?Ｓ））
Ａ的子命题公式有：Ｐ、Ｑ、Ｒ,?Ｓ、（Ｐ ∨ Ｑ）、
（Ｒ Λ?Ｓ）、（Ｑ ∨ （Ｒ Λ?Ｓ））、
（Ｐ ∨ Ｑ） →（Ｑ ∨ （Ｒ Λ?Ｓ））等。
67
§ 4等价式
,定理,,给定一命题公式Ａ，Ａ’是Ａ的子公式。
设 B’是一命题公式，若Ａ’? B’，并用 B’取代Ａ
中的Ａ’，从而生成一新的命题公式 B，则Ａ?B。
从定理可见：一个命题公式 A，经多次取代，所得到的新公式与原公式等价。
例：证明：Ｐ →（Ｑ →Ｒ）?Ｐ →（?Ｑ ∨ Ｒ）
Ｐ ∨?Ｑ ∨?Ｒ
68
§ 4等价式
（Ｐ ΛＱ） ∨ Ｒ
（Ｐ ΛＱ） →Ｒ
例：证明：
（（Ｐ ∨ Ｑ） Λ?（?Ｐ Λ（?Ｑ ∨?Ｒ））） ∨ （?Ｐ
Λ?Ｑ） ∨ （?Ｐ Λ?Ｒ）为一永真式
69
§ 4等价式证明,原式,（（Ｐ ∨ Ｑ） Λ?（?Ｐ Λ（?Ｑ ∨?Ｒ））） ∨ （?Ｐ Λ?
Ｑ） ∨ （?Ｐ Λ?Ｒ）
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ （Ｑ ΛＲ））） ∨?（Ｐ ∨
Ｑ） ∨?（Ｐ ∨ Ｒ）
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）） ∨?
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ））
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）） ∨?（（Ｐ ∨ Ｑ） Λ
（Ｐ ∨ Ｒ））?Ｔ
∵ 它是Ｐ Λ?Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式！
70
§ 4等价式
３．对偶原理（对偶定律）
,定义,,给定二个命题公式Ａ和 A*,若用 Λ代换 ∨,用 ∨
代换 Λ，用Ｔ代换Ｆ，用Ｆ代换Ｔ，其中一个命题公式由另一个命题公式得来，则称Ａ和 A*是互为对偶的，而联结词 Λ和 ∨ 也是互为对偶的例：写出下列命题公式的对偶式：
Ｐ ∨ （Ｑ ΛＲ） Ｐ Λ（Ｑ ∨ Ｒ）
Ｐ ∨ Ｆ?Ｐ 对偶式 A* Ｐ ΛＴ?Ｐ
Ｐ ∨ Ｔ?Ｔ Ｐ ΛＦ?Ｆ
71
§ 4等价式讨论定义：
（１）若命题公式中有联结词?,?，则必须把化成由联结词 Λ,∨,?组成的等价的命题公式，
然后求它的对偶式；
例,求 (P?Q)?(P?R)的对偶式
72
§ 4等价式
（２）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。
例：（Ｐ ΛＱ） ∨ Ｒ对偶式写成
（Ｐ ∨ Ｑ） ΛＲ，而不能写成Ｐ ∨ Ｑ ΛＲ
73
§ 4等价式
,定理,,（摩根推广定理）
设Ａ和 A*为对偶式 P1,P2．．,Pn 是出现在Ａ和 A*中的所有原子命题变元，，于是有：
Ａ（ P1,P2．．,Pn）
A* （?P1,?P2．．,?Pn） ——（ 1）
Ａ（?P1,?P2．．,?Pn）
A*（ P1,P2．．,Pn） ——（２）
74
§ 4等价式证明,由摩根定理
（Ｐ ∨ Ｑ）Ｐ Λ?Ｑ —（１）
（Ｐ ΛＱ）Ｐ ∨?Ｑ —（２）
∴ 不难看出,一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。
例,设Ａ（Ｐ，Ｑ，Ｒ）Ｐ Λ?（Ｑ ∨ Ｒ），
验证上述定理：
75
§ 4等价式证明：
(１ )Ａ（Ｐ，Ｑ，Ｒ）Ｐ Λ?Ｑ Λ?Ｒ
∴?Ａ（Ｐ，Ｑ，Ｒ）?Ｐ ∨ Ｑ ∨ Ｒ
A*（Ｐ，Ｑ，Ｒ）Ｐ ∨?Ｑ ∨?Ｒ
A*（?Ｐ,?Ｑ,?Ｒ）?Ｐ ∨ Ｑ ∨ Ｒ
（２）Ａ（?Ｐ,?Ｑ,?Ｒ）?Ｐ ΛＱ ΛＲ
A*（Ｐ，Ｑ，Ｒ）（?Ｐ ∨ Ｑ ∨?Ｒ）
Ｐ ΛＱ ΛＲ
有Ａ（?Ｐ,?Ｑ,?Ｒ）A*（Ｐ，Ｑ，Ｒ）
76
§ 4等价式
,定理,,若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若Ａ?Ｂ，则 A*?B*成立。
证明,已知：Ａ、Ｂ为任一命题公式，且Ａ?
Ｂ，要证明 A*?B*
设,P1,P2．．,Pn 是出现在Ａ和Ｂ中的原子命题变元，
77
§ 4等价式由Ａ?Ｂ，
即Ａ（ P1,P2．．,Pn）?
Ｂ（ P1,P2．．,Pn）
∴?Ａ（ P1,P2．．,Pn）?
Ｂ（ P1,P2．．,Pn）
由 摩根推广定理
∴ Ａ *（?P1,?P2．．,?Pn）?
Ｂ *（?P1,?P2．．,?Pn）
78
§ 4等价式
∴ Ａ *（?P1,?P2．．,?Pn）?
Ｂ *（?P1,?P2．．,?Pn）为永真式
＊ 前面讲过永真式的代换实例仍为永真式，所以用?Pi代换 A*和 B*中的 Pi （ 1≤i≤n)
则得,Ａ *（P1,P2．．,Pn）?
Ｂ *（P1,P2．．,Pn）
即为：Ａ *（ P1,P2．．,Pn）?
Ｂ *（ P1,P2．．,Pn）
79
§ 4等价式例：证明：
（１）?（Ｐ ΛＱ） →（?Ｐ ∨ （?Ｐ ∨ Ｑ））
（?Ｐ ∨ Ｑ）
（２）（Ｐ ∨ Ｑ） Λ （?Ｐ Λ（?Ｐ ΛＱ））
（?Ｐ ΛＱ）
证明：（１）左边?
（Ｐ ΛＱ） ∨ （?Ｐ ∨ （?Ｐ ∨ Ｑ））
（Ｐ ΛＱ） ∨ （?Ｐ ∨ Ｑ）
（Ｐ ∨?Ｐ ∨ Ｑ） Λ （Ｑ ∨?Ｐ ∨ Ｑ）
（?Ｐ ∨ Ｑ）
80
§ 4等价式
（２）左边? （Ｐ ∨ Ｑ） Λ （?Ｐ ΛＱ）
（Ｐ Λ?Ｐ ΛＱ） ∨ （Ｑ Λ?Ｐ ΛＱ）
（?Ｐ ΛＱ）
结论：（１）和（２）是互为对偶的。
81
§ 5永真蕴含式
,定义,,命题公式Ａ
称为永真蕴含命题公式Ｂ，当且仅当Ａ →Ｂ是一个永真式，
记作：Ａ?Ｂ
说明：“Ａ?Ｂ”读作“Ａ永真蕴含Ｂ”，“Ａ蕴含Ｂ”，
“Ａ能推得Ｂ”
,?,是关系符，Ａ? Ｂ不为命题公式。
例：证明：Ｐ?Ｐ ∨ Ｑ； Ｐ ΛＱ? P
（１）列出真值表证明：Ｐ →（Ｐ ∨ Ｑ）和（Ｐ ΛＱ） →Ｐ为永真式
82
§ 5永真蕴含式
（２）可用等价公式证：
Ｐ →（Ｐ ∨ Ｑ）Ｐ ∨ （Ｐ ∨ Ｑ）? T
（Ｐ ΛＱ） →Ｐ（Ｐ ΛＱ） ∨ Ｐ
Ｐ ∨?Ｑ ∨ Ｐ? T
P Q Ｐ →（Ｐ ∨ Ｑ） （Ｐ ΛＱ） →Ｐ
F F F T F F T F
F T F T T F T F
T F T T T F T T
T T T T T T T T
83
§ 5永真蕴含式
,定理,,设Ａ、Ｂ是二个命题公式
Ａ?Ｂ的充分必要条件是 Ａ?Ｂ且Ｂ? Ａ。
证明,若Ａ?Ｂ，则Ａ?Ｂ为一永真式由定律：
（Ａ?Ｂ）?（Ａ →Ｂ） Λ（Ｂ →Ａ）
∴ （Ａ →Ｂ）且（Ｂ →Ａ）也为一永真式即,Ａ? Ｂ且Ｂ?Ａ成立反之
Ａ? Ｂ且Ｂ? Ａ 则Ａ?Ｂ也成立此定理把,?”和,?,之间建立了相应的关系。
84
§ 5永真蕴含式下面给出常用的永真蕴含式
I1 Ｐ?Ｐ ∨ Ｑ （Ｑ?Ｐ ∨ Ｑ）
I2 Ｐ ΛＱ? Ｐ （Ｐ ΛＱ? Ｑ）
I3 Ｐ Λ（Ｐ →Ｑ）?Ｑ
I4 （Ｐ →Ｑ） Λ?ＱＰ
I5?Ｐ Λ（Ｐ ∨ Ｑ）? Ｑ
I6 （Ｐ →Ｑ） Λ（Ｑ →Ｒ）? （Ｐ →Ｒ）
I7 （Ｐ →Ｑ） Λ（Ｒ →Ｓ）? （Ｐ ΛＲ →Ｑ ΛＳ）
I8 （Ｐ?Ｑ） Λ（Ｑ?Ｒ）? （Ｐ?Ｒ）
I9?P?Ｐ →Ｑ
85
§ 5永真蕴含式
I10 Ｑ? Ｐ →Ｑ
I11?（Ｐ →Ｑ）? Ｐ
I12?（Ｐ →Ｑ）Ｑ
I13 （Ｐ ∨ Ｑ） Λ（Ｐ →Ｒ） Λ（Ｑ →Ｒ）? Ｒ
证明上述永真蕴含式的方法有三种：
（１）把,?,关系符改为,→”联结词，证明它为永真式。
(a)真值表法
(b)命题演算法
86
§ 5永真蕴含式
（２）＊找出使单条件命题前件为“Ｔ”的所有真值指派，试看能否导致后件均为“Ｔ”，若为
“Ｔ”，则永真蕴含关系成立。
P Q P→Q
F F T
F T T
T F F
T T T
87
§ 5永真蕴含式例：Ｐ Λ（Ｐ →Ｑ）? Ｑ
前件为“Ｔ”的所有指派为Ｐ、（Ｐ →Ｑ）均为
“Ｔ”，
Ｐ →Ｑ为“Ｔ”,∵ Ｐ为“Ｔ”,∴ Ｑ也应为
“Ｔ”，
∴ Ｐ Λ（Ｐ →Ｑ）? Ｑ成立
（３）＊找出使单条件命题的后件均为“Ｆ”的所有真值指派，试看前件的所有真值是否为“Ｆ”，
若是，则蕴含成立。
88
§ 5永真蕴含式例,?Ｑ Λ（Ｐ →Ｑ）Ｐ
后件为“Ｆ”的所有条件是：Ｐ为“Ｔ”，
代入前件得
（ ⅰ ）若Ｑ为Ｔ，则?Ｑ Λ（Ｐ →Ｑ）为“Ｆ”；
（ ⅱ ）若Ｑ为Ｆ，则?Ｑ Λ（Ｐ →Ｑ）为“Ｆ”；
∴?Ｑ Λ（Ｐ →Ｑ）Ｐ成立若后件简单则可选用 (3)；若前件简单则可选用 (2)。
二种方法是互为独立的，只需使用一种证明就行。
89
§ 5永真蕴含式讨论一下永真式可得出三个结论：
（１）若一个命题公式等价于一个永真式，则该公式一定为永真式。
（２）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。
（３）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。
90
§ 5永真蕴含式
,定理,,给定命题公式Ａ、Ｂ、Ｃ，
若Ａ?Ｂ，且Ｂ?Ｃ，则Ａ?Ｃ。
证明,∵ Ａ?Ｂ，且Ｂ?Ｃ，
∴ （Ａ →Ｂ） Λ（Ｂ →Ｃ）为永真式，
由 I6：（Ａ →Ｂ） Λ（Ｂ →Ｃ）?
（Ａ →Ｃ），
∴ （Ａ →Ｃ）也为永真式；即，Ａ?Ｃ成立
91
§ 5永真蕴含式
,推论,,
若Ａ?B1,B1? B2．．．．．,Bm?Ｂ，则Ａ?Ｂ。
,定理,,给定一个命题公式Ａ、Ｂ、Ｃ，若Ａ?Ｂ,Ａ?
Ｃ，则Ａ?（Ｂ ΛＣ）
证明,∵ Ａ?Ｂ Λ Ａ?Ｃ，
∴ （Ａ →Ｂ） Λ（Ａ →Ｃ）为永真式，
由条件，若Ａ一定为“Ｔ”，则Ｂ、Ｃ均为“Ｔ”，
∴ Ａ →（Ｂ ΛＣ）也为“Ｔ”，
结论：Ａ?（Ｂ ΛＣ）为“Ｔ”。
92
§ 5永真蕴含式上述也可用等价公式证明它：
（Ａ →Ｂ） Λ（Ａ →Ｃ）
（?Ａ ∨ Ｂ） Λ（?Ａ ∨ Ｃ）
Ａ ∨ （Ｂ ΛＣ）
Ａ →（Ｂ ΛＣ）也为永真式
∴ Ａ?（Ｂ ΛＣ）成立
,定义,,设 H1,H2….Hm,Ｑ 均为命题公式，若
（ H1 ΛH2Λ…Hm ）?Ｑ，则称：
H1,H2….Hm,共同蕴含Ｑ，并记作：
H1,H2….Hm?Ｑ。
93
§ 5永真蕴含式
,定理,,若 （ H1 ΛH2Λ…Hm ）,P?Ｑ，
则（ H1 ΛH2Λ…Hm ）?（Ｐ →Ｑ）。
证明,（ H1 ΛH2Λ…ΛHm ΛP） →Ｑ
（ H1 ΛH2Λ…ΛHm ΛP） ∨ Q
（?H1 ∨?H2 ∨ … ∨?Hm ） ∨ （?P ∨ Q ）
（ H1 ΛH2Λ…ΛHm ） ∨ （ P→ Q ）
H1 Λ H2 Λ…,Λ Hm→（Ｐ →Ｑ）也为永真式
∴ （ H1 Λ,H2 Λ…,Λ Hm ）?（Ｐ →Ｑ）
成立
94
§ 6命题联结词总结
１．其他命题联结词：
（１）不可兼或（异或，异）
(a)符号：,?”（ ⊕ ），Ｐ?Ｑ，读作“Ｐ异或Ｑ”
(b)定义：（由真值表）
(c)异或的性质：
Ｐ?Ｑ
（?Ｐ ΛＱ） ∨ （?Ｑ ΛＰ）
（Ｐ ∨ Ｑ） Λ（?Ｐ ∨?Ｑ）
Ｐ?Ｑ（Ｐ?Ｑ）
Ｐ?Ｑ?Ｑ?Ｐ （可交换的）
（Ｐ?Ｑ）?Ｒ?
Ｐ?（Ｑ?Ｒ）（可结合的）
P Q P? Q
F F F
F T T
T F T
T T F
95
§ 6命题联结词总结
Ｐ Λ（Ｑ?Ｒ）?（Ｐ ΛＱ）?（Ｐ ΛＲ）
（ Λ对? 可分配的）
Ｐ? Ｐ?Ｆ
ＰＰ?Ｔ
Ｆ? Ｐ?Ｐ
Ｔ? ＰＰ
若Ｐ? Ｑ?Ｒ，则有：Ｐ? Ｒ?Ｑ?Ｒ? Ｐ
Ｒ? Ｑ?Ｐ?Ｑ? Ｒ
Ｑ?Ｐ?Ｒ，Ｐ? Ｑ? Ｒ?Ｆ
96
§ 6命题联结词总结
（２）“与非”联结词：
(a)符号,↑”，（Ｐ ↑Ｑ）读作：“Ｐ与Ｑ的否定”或“Ｐ与非Ｑ”
(b)定义：（由真值表）
（Ｐ ↑Ｑ）（Ｐ ∧ Ｑ） P Q P ↑Q
F F T
F T T
T F T
T T F
97
§ 6命题联结词总结
(c)性质：
（Ｐ ↑Ｑ）?（Ｑ ↑Ｐ）
（Ｐ ↑Ｐ）Ｐ
（Ｐ ↑Ｑ） ↑（Ｐ ↑Ｑ）?（Ｐ ∧ Ｑ）
（Ｐ ↑Ｐ） ↑（Ｑ ↑Ｑ）?（Ｐ ∨ Ｑ）
Ｐ ↑（Ｑ ↑Ｒ）Ｐ ∨ （Ｑ ∧ Ｒ） 不可结合的
（Ｐ ↑Ｑ） ↑Ｒ?（Ｐ ∧ Ｑ） ∨?Ｒ 不可结合的
Ｐ ↑ＴＰ，Ｐ ↑Ｆ?Ｔ
98
§ 6命题联结词总结
（３）“或非”联结词：
(a)符号：,↓”
（Ｐ ↓Ｑ）读作：“Ｐ或Ｑ的否定”或,Ｐ或非Ｑ”
(b)定义（由真值表给出）：
（Ｐ ↓Ｑ）（Ｐ ∨ Ｑ）
P Q Ｐ ↓Ｑ
F F T
F T F
T F F
T T F
99
§ 6命题联结词总结
(c)性质：
Ｐ ↓Ｑ?Ｑ ↓Ｐ（可交换的）
Ｐ ↓ＰＰ
（Ｐ ↓Ｑ） ↓（Ｐ ↓Ｑ）?Ｐ ∨ Ｑ
（Ｐ ↓Ｐ） ↓（Ｑ ↓Ｑ）?Ｐ ∧ Ｑ
Ｐ ↓（Ｑ ↓Ｒ）Ｐ ∧ （Ｑ ∨ Ｒ） 不可结合的
（Ｐ ↓Ｑ） ↓Ｒ?（Ｐ ∨ Ｑ） ∧?Ｒ 不可结合的
Ｐ ↓ＦＰ； Ｐ ↓Ｔ?Ｆ
(d)由（２）和（３）中的性质可见,↑和 ↓是互为对偶的。
100
§ 6命题联结词总结
（ 4）,蕴含否定”联结词：
(a)符号：
(b)定义
（由真值表给出）：
P Q(P?Q)
“?”c
P Q P Q
T T F
T F T
F T F
F F F
c
c
101
§ 6命题联结词总结
（１）不同真值表的命题公式：
按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：
(a)若命题变元只有一个Ｐ，则用联结词组成的命题公式由四种不同的真值表，即为：
P 0 1 2 3
F F F T T
T F T F T
102
§ 6命题联结词总结所有依赖于Ｐ的命题公式均等价于这四个中的一个
(b)若有二个命题变元Ｐ、Ｑ，则命题公式的不同真值表有,222=24=16种。
推广到一般：若有ｎ个变元的命题公式，则可构成不同的真值表为 22n（个）。
103
§ 6命题联结词总结
（２）二元运算中的全部联结词总结：
,∧,∨,→,?是五个基本联结词。
到此为止，一个符号系统已定义完毕，它们是：
命题变元,Ａ、Ｂ … Ｘ、Ｙ、Ｚ
值,Ｆ、Ｔ
运算符,
,∧,∨,→,?、,↑,↓,?
括号,（）
关系符,?,?
。
C
104
§ 6命题联结词总结
３．全功能联结词集合：
,定义,,一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，
则称此联结词集合为全功能联结词集合。
,定义,,设有一联结词集合Ａ，
若（１）用Ａ中的联结词的等价式能表达任何的一个命题公式；
105
§ 6命题联结词总结
（２）删除Ａ中的任一联结词，从而形成一个新的联结词集合Ａ’，至少有一个命题公式Ｂ不能用
Ａ’中的联结词的等价式来表示，则称 A为 最小的全功能联结词集合 。
我们可以证明,{?,∨ }； {?,∧ }； {?,→}； {↑}；
{↓}均为全功能联结词集合，且均是 最小的全功能联结词集合 。
例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：
106
§ 6命题联结词总结
（Ｐ →Ｑ）Ｐ ∨ Ｑ {?,∨ }
（?Ｐ ∨ Ｑ）
（Ｐ ∧?Ｑ） {?,∧ }
（Ｐ →Ｑ） {?,→}
(Ｐ Ｑ ) {?,}
（?Ｐ ∨ Ｑ）
（（Ｐ ↓Ｐ） ↓Ｑ） ↓（（Ｐ ↓Ｐ） ↓Ｑ）
{↓}
（?Ｐ ∨ Ｑ）（Ｐ ∧?Ｑ）
Ｐ ↑（Ｑ ↑Ｑ） {↑}
→ c→ c
107
§ 7范式和判定如何判定命题公式为永真式、永假式和可满足的呢或二个命题公式等价，归纳有三种方法：
（ 1）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。
（ 2）命题演算方法,化简命题公式至最简式，看是否存在和 （Ｐ ∨?Ｐ）、（Ｐ ∧?Ｐ）等价，
若不则为可满足的。
（ 3）范式方法：本节就介绍此法。
108
§ 7范式和判定什么叫范式把命题公式化归为一种标准的形式，称此标准形式为范式。
什么叫判定以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。
讨论范式和主范式的目的就是为了进行判定。
109
§ 7范式和判定
１．析取范式和合取范式：
设命题变元为：Ｐ、Ｑ、Ｒ，则：（Ｐ ∨ Ｑ ∨ Ｒ）
的析取式称为“和”；（Ｐ ∧ Ｑ ∧ Ｒ）的合取式称为“积”。
,定义,,命题公式的变元和变元的否定之积称为 基本积,而变元和变元的否定之和称为 基本和 。
110
§ 7范式和判定例：设Ｐ、Ｑ为二个命题变元，则：Ｐ ∨ Ｐ，Ｑ ∨
Ｑ,?Ｐ ∨ Ｑ,?Ｑ ∨?Ｐ，Ｐ ∨ Ｑ，Ｐ ∨?Ｑ称为基本和；Ｐ ∧ Ｐ，Ｑ ∧ Ｑ,?Ｐ ∧ Ｑ,?Ｑ ∧?
Ｐ，Ｐ ∧ Ｑ，Ｐ ∧?Ｑ称为基本积。
若“基本和”或“基本积”中的子公式”，称为此基本积（和）的 因子 。
例,?Ｑ ∧ Ｐ ∧?Ｐ的因子有,?Ｑ、Ｐ、
Ｐ,?Ｑ ∧ Ｐ、Ｐ ∧?Ｐ ……
111
§ 7范式和判定
,定理,,一个基本积必定是永假式，
它的充分必要条件是，它至少包含一对因子，
其中一个是另一个的否定。
证明：
（ ⅰ ）充分条件,Ｐ,?Ｐ为基本积中一对因子
该基本积一定为永假式。
∵ （（Ｐ ∧?Ｐ） ∧ （ … ））?
（Ｆ ∧ （ … ））?Ｆ
（ ⅱ ）必要条件：基本积为永假式?基本积中包含Ｐ,?Ｐ这对因子。
112
§ 7范式和判定反证法：假设基本积中不包含Ｐ,?Ｐ这样的因子，
且为永假式。若给基本积中的命题变元指派
“Ｔ”，而命题变元的否定指派为“Ｆ”，
∵ 在基本积中不包含Ｐ,?Ｐ这对因子，
∴ 基本积得到的真值为“Ｔ”，这和假设相矛盾；
∴ 基本积中必然包含Ｐ,?Ｐ这对因子才能使基本积为“Ｆ”。
113
§ 7范式和判定
,定理,,一个“基本和”必定为永真式，
其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。
,定义,,与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的 析取范式 。并记为,P?P1 ∨ P2 ∨ … ∨ Pn（ n∈I +）。
其中 P1,P2．．,Pn均为基本积。
方法可按下列三步（或四步）进行：
114
§ 7范式 和判定
（１）利用等价公式：化去,→”、,?”联结词，把命题公式变为与其等价的用 {?,∧,∨ }表达的公式。
例,Ｐ →ＱＰ ∨ Ｑ，
Ｐ?Ｑ?（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧?Ｑ）
（?Ｐ ∨ Ｑ） ∧ （Ｐ ∨?Ｑ）
（２）将,?”深入到原子命题变元之前，并使变元之前最多只有一个,?”词。
例,?（?Ｐ ∨?Ｑ）Ｐ ∧Ｑ
Ｐ ∧ Ｑ
115
§ 7范式和判定
（３）利用,∧,对,∨,的分配，将公式化成为析取范式。
（４）除去永假项得最简析取范式。
例：求?（Ｐ ∨ Ｑ）?（Ｐ ∧ Ｑ）的析取范式：
解：原式
(?（Ｐ ∨ Ｑ） ∨ （Ｐ ∧ Ｑ） ) ∧
(?（Ｐ ∧ Ｑ） ∨?（Ｐ ∨ Ｑ） )
116
§ 7范式和判定
(?（Ｐ ∨ Ｑ） ∧ （Ｐ ∧ Ｑ） ) ∨
(（Ｐ ∨ Ｑ） ∧?（Ｐ ∧ Ｑ） )
-----（ 1） 化去?词
（?Ｐ ∧?Ｑ ∧ Ｐ ∧ Ｑ） ∨ （（Ｐ ∨ Ｑ） ∧ （?Ｐ ∨?
Ｑ））
-----（ 2） 将,?”深入到变元前面，并最多保留一个
（?Ｐ ∧?Ｑ ∧ Ｐ ∧ Ｑ） ∨ （（Ｐ ∧?Ｐ） ∨ （Ｐ ∧?
Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｑ ∧?Ｑ））
-----（ 3）,∧,对或,∨,的分配，化成为析取范式
（Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
-----（ 4）最简析取范式
117
§ 7范式 和判定讨论定义：
（１）从上例看出，一个命题公式的析取范式不是唯一的，
但同一命题公式的析取范式一定是等价的。
（２）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。
即,P?P1∨P 2∨?∨P n
（ P1,P2．．,Pn均为基本积）
则,当 P1?P2 Pn?F时,
Ｐ一定为永假式。
(可用来判定是否为永假式 )
118
§ 7范式和判定例,（析取范式）ＰＰ
（Ｐ ∧?Ｐ） ∨ （?Ｐ ∧ Ｐ）
Ｆ 永假式
,定义,,与给定命题公式等价的一个公式，
如果它是由基本和之积所组成，则称它是给定命题公式的 合取范式 。
并表示成,Q? Q1∧ Q2∧ … ∧ Qn,(n∈I +),其中
Q!,Q2,…Q n均为基本和。
119
§ 7范式和判定求一个命题公式的合取范式的方法和求析取范式的方法类同：
第（１）、（２）步相同；
第（３）利用,∨,对,∧,的分配就行；
第（４）去掉永真的析取项。
120
§ 7范式和判定例：求Ｑ ∨?（Ｐ →Ｑ） ∨?（Ｐ ∨ Ｑ）的合取范式原式? Ｑ ∨?（?Ｐ ∨ Ｑ） ∨?（Ｐ ∨ Ｑ）
——化去,→,词
Ｑ ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧?Ｑ）
——“?”深入到变元前，并最多保留一个
（（Ｑ ∨ Ｐ） ∧ （Ｑ ∨?Ｑ）） ∨ （?Ｐ ∧?Ｑ）
——“∨,对,∧,的分配
（Ｑ ∨ Ｐ ∨?Ｐ） ∧ （Ｑ ∨?Ｑ ∨?Ｐ） ∧ （Ｑ ∨ Ｐ ∨
Ｑ） ∧ （Ｑ ∨?Ｑ ∨?Ｑ）
Ｔ（最简合取范式）
121
§ 7范式和判定讨论定义：
（１）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。
（２）若一个命题公式的合取范式中的各基本和的真值为“Ｔ”，则该命题公式一定是永真式。
(可用来判定是否为永真式 )
例：（Ｐ?Ｐ）?（?Ｐ ∨ Ｐ） ∧ （Ｐ ∨?Ｐ）?Ｔ
122
§ 7范式和判定
２．主析取范式。
,定义,,在ｎ个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为 极小项 。
例：对二个命题变元讲，极小项有 22=4个，即,
Ｐ ∧ Ｑ,?Ｐ ∧ Ｑ、Ｐ ∧?Ｑ,?Ｐ ∧?Ｑ
对一个命题变元讲，极小项有 21=2个，即：
Ｐ,?Ｐ
123
§ 7范式和判定对三个命题变元讲，极小项有 23=8个，
即,Ｐ ∧ Ｑ ∧ Ｒ、Ｐ ∧ Ｑ ∧?Ｒ、Ｐ ∧?Ｑ ∧ Ｒ、
Ｐ ∧?Ｑ ∧?Ｒ,?Ｐ ∧ Ｑ ∧ Ｒ,?Ｐ ∧ Ｑ ∧?Ｒ、
Ｐ ∧?Ｑ ∧ Ｒ,?Ｐ ∧?Ｑ ∧?Ｒ
推广到一般：ｎ个命题变元构成的不同极小项有 2n个
（ n∈I +）。使得每个极小项为真的赋值仅有一个。
124
§ 7范式和判定
,定义,,对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的 主析取范式。
,定理,,在真值表中，一个公式的真值为Ｔ的指派所对应的极小项的析取，即为此公式的主析取范式。
125
§ 7范式和判定例：求出Ｐ →Ｑ、Ｐ ∨?Ｑ、
（Ｐ ∧ Ｑ）、Ｐ ∧?Ｑ的主析取范式
Ｐ Ｑ Ｐ ∨?Ｑ?（Ｐ ∧ Ｑ） Ｐ ∧?Ｑ Ｐ →Ｑ
F F T T F T
F T F T F T
T F T T T F
T T T F F T
126
§ 7范式和判定则可直接写出各命题公式的主析取范式：
Ｐ →Ｑ?（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ）
Ｐ ∨?Ｑ?（?Ｐ ∧?Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ）?
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
Ｐ ∧?Ｑ?（Ｐ ∧?Ｑ）
讨论此定理：
（ 1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“Ｔ”的行，对应写出极小项的析取式，且一定是唯一的。
127
§ 7范式和判定
（ 2）若命题公式是含有 n个变元的永真式，则它的主析取范式一定含有 2n个极小项。
（ 3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。
（ 4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“Ｔ”的个数。
128
§ 7范式和判定下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：
（１）将命题公式化归为与其等价的析取范式；
（２）除去永假项，合并基本积中相同项（例：Ｐ
∧ Ｐ ∧ Ｑ?Ｐ ∧ Ｑ），变为最简析取范式。
（３）利用添变元的方法，将所有基本积变为极小项。
129
§ 7范式和判定例：二个变元Ｐ、Ｑ，利用,∧,对或,∨,的分配添项
Ｐ?Ｐ ∧ （Ｑ ∨?Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
Ｑ?Ｑ ∧ （Ｐ ∨?Ｐ）
（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
（４）合并相同的极小项变为一项。
例：求（Ｐ ∧ （Ｐ →Ｑ）） ∨ Ｑ的主析取范式解：原式?（Ｐ ∧?Ｐ） ∨ （Ｐ ∧ Ｑ） ∨ Ｑ
----（ 1）化为析取范式
130
§ 7范式和判定
（Ｐ ∧ Ｑ） ∨ Ｑ
----（ 2）消去永假项，变为最简析取范式
（Ｐ ∧ Ｑ） ∨ （Ｑ ∧ （Ｐ ∨?Ｐ））
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
----（ 3）添项
（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
----（ 4）合并相同最小项
131
§ 7范式和判定例：证明Ｐ ∨ （?Ｐ ∧ Ｑ）?Ｐ ∨ Ｑ
证明方法是写出二个命题公式的主析范式，看其是否相同：
（Ｑ ∨?Ｑ） ∧ Ｐ ∨ （?Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
而Ｐ ∨ Ｑ
（Ｐ ∧ （Ｑ ∨?Ｑ）） ∨ （Ｑ ∧ （Ｐ ∨?Ｐ））
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
主析范式相同,∴ 有Ｐ ∨ （?Ｐ ∧ Ｑ）?Ｐ ∨ Ｑ
132
§ 7范式和判定
３．主合取范式
,定义,,在ｎ个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项。
例：有二个变元Ｐ,Ｑ的极大项有 22=4个，（Ｐ
∨ Ｑ）、（Ｐ ∨?Ｑ）、（?Ｐ ∨ Ｑ）、（?Ｐ
∨?Ｑ）
有ｎ个变元，则有 2n个极大项 （ n∈I +）。
133
§ 7范式和判定
,定理,,在真值表中，一个公式的真值为 F的指派所对应的极大项的合取，即为此公式的主合取范式。
在真值表中真值为“Ｆ”的个数等于主合取范式中极大项的个数。
例：求出（Ｐ →Ｑ）、（Ｐ ∨ Ｑ）,?（Ｐ ∧ Ｑ）、
（Ｐ ∧ Ｑ）的主合取范式
134
§ 7范式和判定
Ｐ Ｑ Ｐ ∨ Ｑ?（Ｐ ∧ Ｑ） Ｐ ∧ Ｑ Ｐ →Ｑ
F F F T F T
F T T T F T
T F T T F F
T T T F T T
直接写出其主合取范式：
（Ｐ →Ｑ）?（?Ｐ ∨ Ｑ）（极大项）
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ）
135
§ 7范式和判定
（Ｐ ∨ Ｑ）? （Ｐ ∨ Ｑ）
（?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ）?（?Ｐ ∨?Ｑ）
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
（ Ｐ ∧ Ｑ ）?
（ Ｐ ∨ Ｑ ） ∧ （ Ｐ ∨?Ｑ ） ∧ （?Ｐ ∨ Ｑ ）
136
§ 7范式和判定讨论
（ １ ） 与命题公式等价的主合范式中极大项的个数等于其真值表中真值为,Ｆ,的个数 。 由真值表找极大项的方法为：将表中值为,Ｆ,的对应真值指派中,把变元写成否定,把变元的否定写成变元 。
（ ２ ） 只要命题公式不是永真式,则一定可以写出对应与其等价的唯一的主合取范式 。
137
§ 7范式和判定
（ ３ ） 若命题公式为含有ｎ个变元的永假式,则主合取范式包含了 2n个极大项的合取式 。
（ ４ ） 可用主合取范式判定二个命题公式是否等价 。
（ ５ ） 已知一个命题公式的主析取范式,则一定可以直接写出与其等价的主合取范式来 。 反之也行 。
例：Ｐ ∨?Ｑ
（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
…… 主析范式
（?Ｐ ∧ Ｑ ）?Ｐ ∨?Ｑ …… 主合取范式
138
§ 7范式和判定
（ ６ ） 对应于有ｎ个变元的命题公式,则一定有：
主析范式极小项数＋主合范式极大项数＝ 2n
下面介绍不用真值表求一命题公式主合取范式的方法：
（ 1） 化为与命题公式等价的合取范式；
（ 2） 除去真值为,T”的析取项和除去析取项中相同变元且只保留一个,变为最简合取式；
（ 3）添项，使析取项均变为极大项；
139
§ 7范式和判定例如：Ｐ,Ｑ为二个变元,
即：Ｐ?Ｐ ∨ （ Ｑ ∧?Ｑ ）
（ Ｐ ∨ Ｑ ） ∧ （ Ｐ ∨?Ｑ ）
（ 4） 合并相同的极大项,保留一项 。
例：求Ｐ ∧ （ Ｐ →Ｑ ） ∨ Ｑ的主合取范式解：原式?Ｐ ∧ （?Ｐ ∨ Ｑ ） ∨ Ｑ
（ Ｐ ∧ Ｑ ） ∨ Ｑ
（ Ｐ ∨ Ｑ ） ∧ Ｑ
（ Ｐ ∨ Ｑ ） ∧ （?Ｐ ∨ Ｑ ）
140
§ 7范式和判定
４,主范式排序 （ 列 ） 的唯一性
（ １ ） 极小项极其编码为了确保主范式的唯一性,二个安排：
（ a） 各命题变元的位置安排一固定次序；
（ b） 对极小项,极大项安排一个次序 。
对于有ｎ个变元的命题公式，则最多可有 2n个极小项，
用 m0 ∧ m1… ∧ m2n-1来表示。
下面列出三个变元,且Ｐ,Ｑ,Ｒ的位置已排定,则
141
m(i)十 十进制数 二进制数 极小项表示
m(0)十 0 000?P ∧? Q ∧? R
m(1)十 1 001?P ∧? Q ∧ R
m(2)十 2 010?P ∧ Q ∧? R
m(3)十 3 011 P ∧? Q?∧ R
m(4)十 4 100 P ∧? Q ∧? R
m(5)十 5 101 P ∧? Q ∧ R
m(6)十 6 110 P ∧ Q ∧? R
m(7)十 7 111 P ∧ Q ∧ R
§ 7范式和判定
142
§ 7范式和判定例：设一命题公式有五个变元,P0,P1,P2,P3,P4（次序已定），则必可写出 25=32个极小项，
下列出 m(11)十 和 m(18)十 的极小项表示：
即,m(11)十 ＝ m(01011)二
＝ （? P0 ∧ P1 ∧? P2 ∧ P3 ∧ P4 ）
m(18)十 ＝ m(10010)二
＝ （ P0 ∧? P1 ∧? P2 ∧ P3 ∧? P4 ）
143
§ 7范式和判定通过上例归纳出一求极小项 m(i)十 的方法：
(a)把 (i)十 变换成等价的 (J0,J1…Jn-1)二
(b)由二进制写出其对应的极小项：
例：求 （ Ｐ ∧ Ｑ ） ∨ （?Ｐ ∧ Ｒ ） 的编码表达式：
（ 设Ｐ,Ｑ,Ｒ次序已定 ）
解：原式?（?Ｐ ∧?Ｑ ∧ Ｒ ） ∨ （?Ｐ ∧ Ｑ ∧
Ｒ ） ∨ （ Ｐ ∧ Ｑ ∧ Ｒ ） ∨ （ Ｐ ∧ Ｑ ∧?Ｒ ）
144
§ 7范式和判定
m(001) 二 ∨ m(010)二 ∨ m(100)二 ∨ m(101)二
m(1)十 ∨ m(3)十 ∨ m(7)十 ∨ m(6)
十
m1,m3,m7,m61,3,6,7
（ ２ ） 极大项及其编码用 M0,M1,… M2n-1表示ｎ个变元的命题公式的极大项 。
求极大项的方法：
145
§ 7范式和判定
(a)把 (i)十 变换成等价的 (J0,J1…Jn-1)二
(b)由二进制数写出其对应的极大项：
例：求（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｒ）的极大项编码表示（设Ｐ、Ｑ、Ｒ次序已定）
146
§ 7范式和判定解：原式?
（Ｐ ∨ Ｑ ∨ Ｒ） ∧ （Ｐ ∨?Ｑ ∨ Ｒ） ∧ （?Ｐ ∨
Ｑ ∨ Ｒ） ∧ （?Ｐ ∨ Ｑ ∨?Ｒ）
M(000) 二 ∧ M(010)二 ∧ M(100)二 ∧ (110)二
M (0)十 ∧ M (2)十 ∧ M (4)十 ∧ M (5)十
M0,M2,M4,M5
0,2,4,5
147
§ 7范式和判定极大项和极小项编码约定刚好相反,
从上例中,（ Ｐ ∧ Ｑ ） ∨ （?Ｐ ∧ Ｒ ）
1,3,6,70,2,4,5
例：写出 （ Ｐ ∨?Ｑ ） 的主析和主合编码表示
148
§ 7范式和判定
P Q P ∨?Q
F F T
F T F
T F T
T T T
P ∨?Q10,2,3
主析范式为,（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
主合范式为,P ∨?Q
且 P ∨?Q?（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
149
§ 7范式和判定
５,主范式的个数在介绍联结词总结时讲到：
一个原子命题变元有四个不同的真值表（ 221个）；
二个原子命题变元有 16个不同的真值表 （ 222个 ） ；
以此类推,若有ｎ个变元的命题公式,则可构成 22n
个不同的真值表 。
∴ 得到结论：
对于含有ｎ个变元的命题公式,必定可写出 22n个主范式,若排除永真式或永假式,则实际可写出
（ 22n －１ ） 个主析 （ 或主合 ） 范式 。
150
§ 8推理理论按公认的推论规则，从前提集合中推导出一个结论来，
这样的推导过程称为 演绎,或者叫 形式证明 。
在任何论证中,若认定前提是真的,且从前提集合推导出结论的论证是遵守了逻辑规则的,则我们称此结论是 合法的 。
根据逻辑规则推导出来的任何结论称为 有效结论 。
推论规则 就是指确定论证的有效性的判据,常是用命题形式表示这些规则,而不涉及实际命题和它的真值 。
151
§ 8 推理理论本节介绍的证明方法,归纳分成三类：
（一）真值表技术；
（二）推论规则；
（三）间接证明法。
真值表技术的主要依据是,→” 的真值表定义 。
若Ｐ?Ｑ当且仅当
（ Ｐ →Ｑ ） 为永真式 。 P Q Ｐ →Ｑ
F F T
F T T
T F F
T T T
152
§ 8推理理论真值表技术：
,定义,,给定二个命题公式Ａ和Ｂ,当且仅当Ａ →
Ｂ是一个永真式,才可以说Ｂ是从Ａ推导出来的,
或称Ｂ是前提Ａ的有效结论 。
,定义,,设 H1,H2,…Hm,Ｃ都是命题公式,当且仅当 H1 ∧ H2 ∧ … ∧ Hm?Ｃ,才可以说Ｃ是前提集合 ｛ H1,H2,…Hm ｝ 的有效结论 。
153
§ 8推理理论从给定真值表常用的判断方法有二种：
（ １ ） 检查真值表中 H1,H2,…Hm全部为,Ｔ,的所有行,
看结论Ｃ是否也均为,Ｔ,,若Ｃ均为,Ｔ,,则结论有效 。 否则结论无效 。
（２）看结论Ｃ为,Ｆ,的所有行，检查每行前提 H1，
H2,…Hm中是否至少有一个为Ｆ，若有,Ｆ,,则结论有效；若有均为,Ｔ,的行，则结论无效。
例：试证明下列结论是否有效：
画出真值表：
154
§ 8推理理论由真值表可见：
（１）Ｐ，Ｐ →Ｑ?Ｑ 有效
（２）Ｐ →Ｑ,?Ｐ?Ｑ 无效
（３）Ｐ →Ｑ,? （Ｐ ∧ Ｑ）Ｐ 有效
（４）?Ｐ，Ｐ?Ｑ （Ｐ ∧ Ｑ） 有效
P Q Ｐ →Ｑ?Ｐ?Q?（Ｐ ∧ Ｑ） Ｐ?Ｑ
F F T T T T T
F T T T F T F
T F F F T T F
T T T F F F T
155
§ 8推理理论
（５）Ｐ →Ｑ，Ｑ?Ｐ 无效例,H1：如果大连是一个大城市,则大寨是一个乡村； Ｐ →Ｑ
H2：大寨是一个乡村； Ｑ
Ｃ：大连是一个大城市； Ｐ
则：Ｐ →Ｑ,Ｑ?Ｐ
或者称：Ｐ不能从前提集合中推导出来 。
156
§ 8推理理论
２,推理 （ 论 ） 规则：
从这节开始,我们只讨论命题论证的有效性,而不去讨论命题的真假值；
∴ 在推论规则中不需要有真值表,也不需要对命题进行真值指派 。
推理规则的依据是常用的永真蕴含式和等价公式 。
I1 Ｐ?Ｐ ∨ Ｑ； Ｑ?Ｐ ∨ Ｑ
I2 Ｐ?Ｑ?Ｐ； Ｐ?Ｑ?Ｑ
I3 Ｐ,Ｐ →Ｑ?Ｑ
157
§ 8推理理论
I4 （ Ｐ →Ｑ ）,?ＱＰ
I5?Ｐ,（ Ｐ ∨ Ｑ ）?Ｑ
I6 （ Ｐ →Ｑ ）,（ Ｑ →Ｒ ）? （ Ｐ →Ｒ ）
I7 （ Ｐ →Ｑ ）? （（ Ｑ →Ｒ ） →（ Ｐ →Ｒ ））
I8 （ Ｐ →Ｑ ）,（ Ｒ →Ｓ ）? （ Ｐ ∧ Ｒ →Ｑ ∧ Ｓ ）
I9 （ Ｐ?Ｑ ）,（ Ｑ?Ｒ ）? （ Ｐ?Ｒ ）
I10?Ｐ?Ｐ →Ｑ
158
§ 8推理理论下面介绍二个规则：
P规则：在推导的任何步骤上都可以引入前提
（ 条件 ）
T规则：在推导过程中,如果前面有一个或多个公式永真蕴含 S,则可以把 S引入推导过程之中 。
例 1：证明,P?Q,Q? R,P?R
推理过程：
159
§ 8推理理论步骤 推理过程 规则 根据
(1) P?Q P
(2) P P
(3) Q T I(1)(2)
(4) Q? R P
(5) R T I(3)(4)
也可以这样推理：
(1) P?Q P
(2) Q?R P
(3) P?R T I(1)(2)
160
§ 8推理理论
(4) P P
(5) R T I(3)(4)
例 2 证明：
(P∨ Q),(P?R),(Q?S)?S∨ R
(1) (P∨ Q) P
(2)? P?Q T(1) E16
(3) Q?S P
(4)? P?S T(2)(3) I6
(5)? S?P T(4) E18
161
§ 8推理理论
(6) P?R P
(7)? S?R T(6) I6
(8) S∨ R T(7) E16
下面引进条件证明规则 CP：
如果能从 Q和给定的前提集合 P中推导出 R来，
则就能从前提集合中推导出（ Q? R）来。
即,(P∧ Q?R)则,P? (Q?R)
162
§ 8推理理论例 1,P?(Q?S),?R∨ P,Q? R?S
证,(1) R 附加前提
(2)?R∨ P P
(3) R?P T(2) E
(4) P T(1)(3) I
(5) P?(Q?S) P
(6) Q?S T(4)(5) I
163
§ 8推理理论
(7) Q P
(8) S T(6)(7) I
(9) R?S CP
例 2,P?Q? P?(P ∧ Q)
(1) P 附加前提
(2) P?Q P
(3) Q T(1)(2) I
(4) P ∧ Q T(1)(3)
(5) P?(P ∧ Q) CP
164
§ 8推理理论
3．间接证明法,（反证法、归谬法）
,定义,给出命题公式 H1,H2… Hm，
H1?H2?…? Hm具有真值为,T”，则命题公式集合 {H1,H2… Hm}称为是一致的。否则称
{H1,H2… Hm}是非一致的。
165
§ 8推理理论
,定理,设 {H1,H2… Hm}是一致的，同时设 C是一个命题公式，如果前提集合 {H1,H2… Hm,?C}
是非一致的，则一定有 H1,H2… Hm?C成立。
证明：由条件 H1?H2?…? HmC?F
∴ H1?H2?…? HmC必定为永假式。而 H1?H2
…? Hm是一致的，即为永真式，从而只有?C
为永假式，则 C 一定为永真式，
故 H1?H2?…? Hm?C成立。
166
§ 8推理理论例：证明?PQ(P?Q)
证,(1)?(?(P?Q)) 假设前提
(2) P?Q T(1)
(3) P T(2)
(4)?PQ P
(5)?P T(4)
(6) PP T(3)(5)
(7) F
167
§ 8推理理论例 2:证明,RQ,R∨ S,SQ,P?QP
(1)?(?P) 假设前提
(2) P T(1)
(3) P?Q P
(4) Q T(2)(3)
(5) SQ P
(6) QS T(5)
(7)?S T(4)(6)
(8) R∨ S P
(9) R T(7)(8)
168
§ 8推理理论
(10) RQ P
(11)?Q T(9)(10)
(12)Q ∧?Q T(4)(11)
讨论：
由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用 CP规则代替它。
169
§ 8推理理论间接证明法：特殊条件下的 CP规则
∵ H1?H2?…? HmC?F
由 CP规则：
H1?H2?…? HmC?F
C∨ F
C
∴ H1,H2… Hm?C成立
170
§ 8推理理论例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。
（ 1）会计张某或邻居王某谋害了厂长。
（ 2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。
（ 3）如果邻居王某的证词不正确，则在半夜时房里灯光未灭。
（ 4）如果邻居王某的证词是正确的，则谋害发生在半夜。
（ 5）在半夜房子里的灯光灭了，且会计张某曾贪污过。
171
§ 8推理理论解：设 P：会计张某谋害了厂长
Q：邻居王某谋害了厂长
N：谋害发生在半夜
O：邻居王某的证词是正确的
R：半夜时房子的灯光灭了
A：会计张某曾贪污过列出条件公式：
172
§ 8推理理论
(1) P∨ Q (4) Q?N
(2) PN (5) R?A
(3)?OR
推导过程为：
(1) R?A P (6) N T
(2) R T (7) PN P
(3)?OR P (8)?P T
(4) O T (9) P∨ Q P
(5) O? R P (10) Q T
结论：邻居王某谋害了厂长；
173
第一章小结学习第一章要注意以下几点：
（ 1）弄清命题与陈述句的关系。
（ 2）弄清由 6种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式” P?Q“的逻辑关系及其真值。
（ 3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。
（ 4）会准确地求出给定公式的主析取范式和主合取范式。
掌握主析取范式与真值表、成真赋值、主合取范式的关系。
（ 5）会用多种方法判断公式的类型及判断两个公式是否等价。
174
第一章小结
（ 6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。
（ 7）掌握推理和判断推理是否正确的方法。
175
例题选讲例 1.符号化下列命题：
（ 1）辱骂和恐吓决不是战斗；
（ 2）除非天气好，否则我是不会去公园的；
（ 3）如果晚上做完作业且没有其它的事，他就会去看电视或听音乐。
解,（ 1）设 P：辱骂不是战斗。
Q：恐吓不是战斗。
P?Q
（ 2）设 P：今天天气好。
Q：我去公园。 Q?P
176
例题选讲
（ 3）设 P：他晚上做完了作业。
Q：他晚上没有其它事情。
R：他看电视。
S：他听音乐。
（ P?Q）?（ R?S）
例 2.证明 P? （ Q? R）?（ P? Q）? （ P? R）
给出本题的各种证明：
（ 1）列真值表：设 M? P? （ Q? R）
K? （ P? Q）? （ P? R）
S?P? （ Q? R）? （ P? Q）? （ P? R）
177
例题选讲
P Q R Q?R M P?Q P?R K S
T T T T T T T T T
T T F F F T F F T
T F T T T F T T T
T F F T T F F T T
F T T T T T T T T
F T F F T T T T T
F F T T T T T T T
F F F T T T T T T
178
例题选讲
a)直接证法,P? （ Q? R）的真值为 T，其对应指派下
（ P? Q）? （ P? R）的真值均为 T。
b)反证法：（ P? Q）? （ P? R）的真值为 F，其对应指派下 P? （ Q? R）的真值为 F。
c)条件永真式：
（ P? （ Q? R））?（ （ P? Q）? （ P? R））
的真值都为 T，及为永真式。
（ 2）逻辑推证
a)直接证法：设 P? （ Q? R）为 T，则
① P为 T,Q? R为 T，有三种情况：
P为 T,Q为 T,R为 T，则（ P? Q）? （ P? R）为 T。
179
例题选讲
P为 T,Q为 F,R为 T，则（ P? Q）? （ P? R）为 T。
P为 T,Q为 F,R为 F，则（ P? Q）? （ P? R）为 T。
② P为 F,Q? R为 F，则：
P为 F,Q为 T,R为 F，所以 P? Q为 T,P? R为 T，得
（ P? Q）? （ P? R）为 T。
③ P为 F,Q? R为 T，则：
P为 F,Q为 T,R为 T，则（ P? Q）? （ P? R）为 T。
P为 F,Q为 F,R为 F，则（ P? Q）? （ P? R）为 T。
P为 F,Q为 F,R为 T，则（ P? Q）? （ P? R）为 T。
综上各点：当 P? （ Q? R）为 T时，必有（ P? Q）?
（ P? R）为 T。
180
例题选讲
b)间接证法：
设 （ P? Q）? （ P? R）为 F，则必有 P? Q为 T,P? R为 F，故得 P为 T,Q为 T,R为 F。
所以 P? （ Q? R）为 F。
（ 3）等价变换
S? (P? (Q? R))?((P? Q)? (P? R))
(?P?(?Q?R))?((?P? Q)?(?P? R))
(?PQ?R)? (?(?P? Q)? (?P? R))
(P?QR)?((PQ)?(?P? R))
(P?QR)?((?P? R? P)?(?QP? R))
(P?QR)?(?PQ? R)
(P?QR)(P?QR)?T
181
例题选讲例 3.证明 ｛?,?｝不是最小联结词组。
证明：设变元 P,Q，用联结词?,?作用于 P,Q得到：
P,Q,?P,?Q,P?Q,P?P,Q?Q,Q?P。但
(P?Q)?(Q?P),(P?P)? (Q?Q)，故实际有：
P,Q,?P,?Q,P?Q,P?P(T) (A)
用?作用于 (A)类,得到扩大的公式类 (包括原公式类 ):
P,Q,?P,?Q,P?Q,?(P?Q),T,F (B)
用?作用于 (A)类得到：
P?Q,PP(F),PQ(P?Q)，
P? (P?Q)? Q,P? (P?P)?P,
QP(P?Q),QQ(F),Q? (P?Q)? P,
Q?T?Q，
182
例题选讲
PQ? (P?Q),?P? (P?Q)Q，
P?TP,?Q? (P?Q)P，
Q?TQ,(P?Q)? (P?P)? P?Q。
因此 (A)类使用?运算后，仍在 (B)类中。
同样，对 (B)类使用?,?运算后，结果仍在 (B)中。
由上证明：用?,?两个联结词，反复作用在两个变元的公式中，结果只能产生 (B)类中的公式，总共仅八个不同公式，而两个变元所形成的公式共有 222=16个彼此不等价的公式，因此 ｛?,?｝不是功能完备的，更不可能是最小联结词组。
183
例题选讲例 4,求 (A?B?C)?(?A?(?BC))的主析取范式与主合取范式。
解,(1)列表法：
设 S? (A?B?C)?(?A?(?BC))，
R? A?B?C，
MA?(?BC)，
根据真值表中 S真值为 T的指派，所对应的小项析取即为 S的主析取范式,S真值为 F的指派，所对应的大项合取即为主合取范式。
S的真值表如下：
184
例题选讲
A B C B?C R?A?BC M S
T T T T T F F T T
T T F F F F F T F
T F T F F F F T F
T F F F F F T F F
F T T T T T F F F
F T F F T T F F F
F F T F T T F F F
F F F F T T T T T
185
例题选讲
S? (A?B? C)?(?ABC) －－ 主析取范式
S?(?AB? C)?(?A? BC)?(?A? B? C)
(ABC)?(AB? C)?(A? BC)
－－主合取范式
(2)公式推导法：
S? (A?B?C)?(?A?(?BC))
(?A? (B?C))?(?A?(?BC))?((?BC)A)
(?A? (B?C))?(A?(?BC))?((B?C)A)
((?ABC)? (A?B?C))?(B?CA)
(?ABC)? (A?B?C)?m000?m1110,7
186
例题选讲当求出主析取范式的编码表达式后可直接利用编码关系，解出主合取范式。即：
S? (A?B?C)?(?A?(?BC))
(?ABC)? (A?B?C)?m000?m1110,7
1,2,3,4,5,6?M001?M010?M011?M100?M100?M101?M110
(?AB? C)?(?A? BC)?(?A? B? C)
(ABC)?(AB? C)?(A? BC)
187
例题选讲例 5.用推理规则论证下述问题：
或者是天晴，或者是下雨。如果是天晴，我去看电影。
如果我去看电影，我就不看书。所以，如果我在看书，则天在下雨。
解：设 S：今天天晴。 R：今天下雨。
E：我去看电影。 B：我去看书。
本题符号化为：
S?R,S?E,EB?B?R
因为 S?R(S?R)
故本题为?(S?R),S?E,EB?B?R
188
例题选讲
① 直接证法：
(1)?(S?R) P
(2) S R T(1),E
(3) (SR)?(?R?S) T(2),E
(4)?R?S T(3),I
(5)S?E P
(6)?R?E T(4)(5),I
(7)EB P
(8)?RB T(6)(7),I
(9)B?R T(8),E
189
例题选讲
② 间接证法：
a) (1)?(S?R) P
(2) S R T(1)
(3) (SR)?(?R?S) T(2)
(4)?R?S T(3)
(5)?(B?R) P(附加前提 )
(6)BR T(5)
(7)B T(6)
(8)?R T(6)
(9)S T(4)(8)
190
例题选讲
(10) S?E P
(11)E T(4)(10)
(12)EB P
(13)?B T(11)(12)
(14)BB 矛盾 (7)(13)
b)
(1)B P(附加前提 )
(2)EB P
(3)?E T(1)(2)
(4) S?E P
191
例题选讲
(5)?S T(3)(4)
(6)?(S?R) P
(7) S R T(6)
(8) (SR)?(?R?S) T(7)
(9)?R?S T(8)
(10)?S?R T(9)
(11)R T(5)(10)
(12) B?R CP
第一章 命题逻辑
§ 1.命题
§ 2.命题联结词
§ 3.命题变元与命题公式
§ 4.等价式
§ 5.永真蕴含式
§ 6.命题联结词总结
§ 7.范 式 和 判 定
§ 8.推论规则和证明方法
2
§ 1命题
,定义,,具有唯一真值的陈述句叫命题 。
讨论定义：
（１）命题可以是真的，或者是假的，但不能同时为真又为假。
（２）命题分类：
ⅰ )原子命题 （基本命题、本原命题）：一个命题，不能分解成为更简单的命题。
例：我是一位学生。
3
§ 1命题
ⅱ )分子命题 （复合命题）,若干个原子命题使用适当的联结词 所组成的新命题例：我是一位学生和他是一位工人
(3)命题所用符号：常用大写２６个英文字母表示命题。
用Ａ、Ｂ、Ｃ．．．．Ｚ表示。
(4)命题中所有的“真”用“Ｔ”表示，
命题中所有的“假”用“Ｆ”表示。
4
§ 1命题例,判断下列语句是否为命题。
＊ 陈述句一般为命题
（ 1）十是整数。 （Ｔ）
（ 2）上海是一个村庄。（Ｆ）
（ 3）今天下雨。
（ 4）加拿大是一个国家。（Ｔ）
（ 5）２是偶数而３是奇数。
（ 6）她不是护士。
（ 7）１＋１０１＝１１０
（ 8）今天是星期天。
5
§ 1命题命令句，感叹句，疑问句均不是命题。
（ 1）把门关上！
（ 2）你到哪里去？
语句既为真，同时又包含假的不是命题，这样的句子称为,悖论,。
（ 3）他正在说谎。
（在命题逻辑中不讨论这类问题）
6
§ 2命题联结词在命题演算中也有类似的日常生活中的联结词称做：,命题联结词” 下面先介绍五个常用的命题联结词。
１,否定词,（否定运算、非运算）
（１）符号?,读作“非”，“否定”
设命题为Ｐ，则在Ｐ的前面加否定词?,变成?
Ｐ,?Ｐ读做“Ｐ的否定”或“非Ｐ”
7
§ 2命题联结词
（２）定义：严格由真值表定义
（３）举例：
Ｐ：北京是一座城市。
Ｐ：北京不是一座城市。
Ｑ：每一种生物均是动物。 F
Ｑ：有一些生物不是动物。 T
这里?Ｑ不能讲成“每一种生物都不是动物”为假命题了。
对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。
P?P
T F
F T
8
§ 2命题联结词
２．合取词 （“合取”、“积”、“与”运算）
符号,Λ”
设Ｐ，Ｑ为两个命题，则Ｐ ΛＱ称Ｐ与Ｑ的合取，
读作：“Ｐ与Ｑ”、“Ｐ与Ｑ的合取”、
“Ｐ并且Ｑ”等。
定义（由真值表给出）：
9
§ 2命题联结词
P Q PΛ Q QΛP
F F F F
F T F F
T F F F
T T T T
Ｐ ΛＱ真值表如下,
10
§ 2命题联结词当且仅当Ｐ和Ｑ的真值均为“Ｔ”，则（Ｐ ΛＱ）
的真值为“Ｔ”。否则，其真值为“Ｆ”。
注意,Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ
和Ｑ的位置可以交换而不会影响Ｐ ΛＱ的结果。
11
§ 2命题联结词举例：
(a) P：王华的成绩很好
Q：王华的品德很好。
则Ｐ ΛＱ：王华的成绩很好并且品德很好。
(b) P：我们去种树
Q：房间里有一台电视机则Ｐ ΛＱ：我们去种树与房间里有一台电视机。
12
§ 2命题联结词
(c) P：今天下大雨 Q,3+3=6
则Ｐ ΛＱ：今天下大雨和 3+3=6
由例 (b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。
13
§ 2命题联结词
(d) 下列语句不是合取联结词组成的命题。
P,王大和王二是亲兄弟。
Q,他打开箱子然后（而后）拿出一件衣服来。
14
§ 2命题联结词
３．析取词 （或运算）
（１）符号,∨,
设Ｐ、Ｑ为二个命题，则（Ｐ ∨ Ｑ）称作Ｐ与Ｑ
的“析取”，读作：“Ｐ或Ｑ”。
（２）定义（由真值表给出）：
15
§ 2命题联结词当且仅当Ｐ、Ｑ均为“Ｆ”时，（Ｐ ∨ Ｑ）为
“Ｆ”。否则，其真值为“Ｔ”．
P Q P∨ Q
F F F
F T T
T F T
T T T
Ｐ ∨ Ｑ真值表如右：
16
§ 2命题联结词区分“可兼或”与“不可兼或（异或，排斥或）”
析取词为可兼或即,P和 Q均为,T”时（ P∨ Q）
为,T”
例如：
灯泡有故障或开关有故障。
今晚写字或看书。
今天下雨或打雷。
以上例句均为可兼或。
17
§ 2命题联结词
“不可兼或”中当 P和 Q均为,T”时，则 P异或 Q
为,F”。
（异或用,▽,表示） P Q P▽ Q
F F F
F T T
T F T
T T F
18
§ 2命题联结词例：
他通过电视看杂技 或 到剧场看杂技。
他乘火车去北京 或 乘飞机去北京。
以上两句均为不“可兼或”。
19
§ 2命题联结词
４．单条件联结词,（“蕴含”联结词、蕴含词）
（１）符号,→”，读作：“如果 … 则 …”,
“蕴含”
Ｐ、Ｑ为二个命题，（Ｐ →Ｑ）为新的命题，读作：“如果Ｐ则Ｑ”，“Ｐ蕴含Ｑ”，“Ｐ仅当Ｑ”，“Ｑ当且Ｐ”，“Ｐ是Ｑ的充分条件”。
（２）定义
20
§ 2命题联结词
（由真值表定义）：
P Q P→Q
F F T
F T T
T F F
T T T
21
§ 2命题联结词当Ｐ为“Ｔ”，Ｑ为“Ｆ”时，则
（Ｐ →Ｑ）为“Ｆ”，否则（Ｐ →Ｑ）均为
“Ｔ”。
Ｐ：称为前件、条件、前提、假设
Ｑ：称为后件、结论。
（３）举例：
P：我拿起一本书
Q：我一口气读完了这本书
22
§ 2命题联结词
P→Q：如果我拿起一本书，则我一口气读完了这本书。
(b) P：月亮出来了
Q,3× 3=9
P→Q：如果月亮出来了，则
3× 3=9。
通常称,(a)为形式条件命题。
——前提和结果有某种形式和内容上的联系。
23
§ 2命题联结词
(b)为实质条件命题。 ——前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。
所以,是形式条件命题一定是实质条件命题,反之不一定。,→”是实质条件命题。
例：
Ｐ：我买到了鱼；Ｑ,我吃鱼。
24
§ 2命题联结词
Ｐ →Ｑ：如果我买到了鱼，则我吃鱼。
但“如果我没买到鱼，则我吃鱼”，这在日常生活中是不可能的，但在单条件命题的定义中是允许的。
25
§ 2命题联结词可以证明：
Ｐ →Ｑ Q →? P
原命题 逆反命题
Ｑ →ＰＰ →?Ｑ
逆命题 反命题
26
§ 2命题联结词列出真值表,由真值表得：
原命题?逆反命题；逆命题?反命题。
P Q P→Q? Q→?P Ｑ →P?Ｐ →?Ｑ
F F T T T T
F T T T F F
T F F F T T
T T T T T T
27
§ 2命题联结词
５．双条件联结词 （“等价”词、“同”联结词、
“等同”词）
（１）符号,?”
设Ｐ、Ｑ为二个命题，则Ｐ?Ｑ读作：“Ｐ当且仅当Ｑ”，“Ｐ等价Ｑ”,“Ｐ是Ｑ的充分必要条件”。
（２）定义（见真值表）：
28
§ 2命题联结词真值表,
每当Ｐ和Ｑ的真值相同时，
则（Ｐ?Ｑ）的真值为
“Ｔ”，否则（Ｐ?Ｑ）
的真值为“Ｆ”。
P Q P?Q
F F T
F T F
T F F
T T T
29
§ 2命题联结词
（３）举例：
（ a）设
Ｐ：△ ABC是等腰三角形
Ｑ：△ ABC有两只角相等
Ｐ?Ｑ：△ ABC是等腰三角形当且仅当△ ABC中有两只角相等。
30
§ 2命题联结词
（ b）下面均为等价联结词：
春天来了当且仅当燕子飞回来了。
平面上二直线平行，当且仅当这二直线不相交。
２＋２＝４当且仅当雪是白色的。
31
§ 2命题联结词
（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、
Ｑ交换位置不会改变真值表中的值。
（５）Ｐ当且仅当Ｑ Ｐ?Ｑ
Ｐ仅当Ｑ Ｐ →Ｑ
Ｐ当且Ｑ Ｑ →Ｐ
32
§ 2命题联结词
６．命题联结词在使用中的优先级
（１）先括号内，后括号外
（２）运算时联结词的优先次序为,? Λ ∨
→?
（由高到低）
33
§ 2命题联结词
（３）联结词按从左到右的次序进行运算例
Ｐ ∨ （Ｑ ∨ Ｒ）可省去括号因为“Ｖ”运算是可结合的。
（?Ｐ ∨ Ｑ） ∨ Ｒ可省去括号 因为符合上述规定而 Ｐ →（Ｑ →Ｒ） 中的括号不能省去，因为,→”
不满足结合律。
34
§ 2命题联结词
（４）最外层的括号一律均可省去
（Ｐ →Ｑ ∨ Ｒ）可写成Ｐ →Ｑ ∨ Ｒ
７．命题联结词小结：
（１）五个联结词的含义与日常生活中的联结词的含义大致相同。
（２）,或,可分为可兼或（ ∨ ）和异或（ ▽ ）
（不可兼或）
35
§ 2命题联结词
(3) 除,?”为一元运算外，其余四个均为二元运算。
(4),→,分为形式条件和实质条件命题,当前件为“Ｆ”时，不论后件怎样，则单条件命题的真值均为“Ｔ” 。
(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。
36
§ 2命题联结词以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，
首先要把推理所涉及到的各命题符号化。
步骤如下：
①找出各简单命题，分别符号化。
②找出各联结词，把简单命题逐个联结起来。
37
§ 2命题联结词例,将下列命题符号化：
（ 1）李明是计算机系的学生，他住在 312室或
313室。
（ 2）张三和李四是朋友。
（ 3）虽然交通堵塞，但是老王还是准时到达了车站。
（ 4）只有一个角是直角的三角形才是直角三角形。
（ 5）老王或小李中有一个去上海出差。
38
§ 2命题联结词解：
（ 1）首先用字母表示简单命题。
P：李明是计算机系的学生。
Q：李明住在 312室。
R：李明住在 313室。
该命题符号化为,P?（ Q▽ R）
（ 2）张三和李四是朋友。是一个简单句该命题符号化为,P
39
§ 2命题联结词
（ 3）首先用字母表示简单命题。
P：交通堵塞。
Q：老王准时到达了车站。
该命题符号化为,P?Q
（ 4）首先用字母表示简单命题。
P：三角形的一个角是直角。
Q：三角形是直角三角形。
该命题符号化为,?PQ
40
§ 2命题联结词
（ 5）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为,P ▽ Q
也可符号化为：
（ PQ）?（?P?Q）或者
（ P? Q） （ P?Q）
41
§ ３命题公式约定：
（１）我们只注意命题的真假值，而不再去注意命题的汉语意义。
（２）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。
１．命题公式命题常元：表示确定的命题｛ T,F｝。
命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母Ａ … Ｚ表示。
42
§ ３命题公式命题公式,由命题变元、常元、联结词、括号，
以规定的格式联结起来的字符串。
,定义,,命题公式可按下述法则来生成：
１）孤立的命题变元是一个命题公式。
２）若Ａ是命题公式,?Ａ也为命题公式。
３）若Ａ、Ｂ是命题公式，则（Ａ ΛＢ）、（Ａ
∨ Ｂ）、（Ａ →Ｂ）、（Ａ?Ｂ）均为命题公式。
43
§ ３命题公式
４）当且仅当有限次使用
（１）（２）（３）所生成的公式才是命题公式。
例如,(?(P ∨Q)),(P→(Q →R)),((PΛQ)?R),P都是命题公式。而 (P→),(P∨?)都不是命题公式
２．命题公式的真值表,
命题变元用特定的命题来取代，这一过程称为对该命题变元进行 指派。
命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。
写成ｙ＝ｆ (x)
44
§ ３命题公式例如：公式 P?(Q?R) 定义三元函数
Y(P,Q,R)＝ P?(Q?R)
,定义,,命题公式 A在其所有可能的赋值下取得的值列成的表称为 A的真值表。
构造真值表的步骤如下：
1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。
2)按照从低到高的顺序写出命题公式的各层次。
3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。
45
§ ３命题公式
P Q P ∨ Q （Ｐ ∨ Ｑ） ΛＰ?（（Ｐ ∨ Ｑ） ΛＰ）
F F F F T
F T T F T
T F T T F
T T T T F
例１．构造命题公式?（（Ｐ ∨ Ｑ） ΛＰ）
的真值表：
46
§ ３命题公式例２．写出命题公式
Ｐ ∨ （Ｑ ΛＲ）的真值表
P Q R Ｐ ∨ （Ｑ ΛＲ )
F F F F F
F F T F F
F T F F F
F T T T T
T F F T F
T F T T F
T T F T F
T T T T T
47
§ ３命题公式由上二例可见，２个命题变元有４组真值指派；
３个命题变元有 23＝ ８组真值指派，
ｎ个则有个 2n个真值指派。
３．命题公式的永真式、永假式和可满足式例：举最简单例子：
48
§ ３命题公式
P?P P∨?P P∧?P
F T T F
T F T F
,定义,,设公式Ａ中有 n个不同的原子变元 p1,… pn,(n
为正整数 )。该变元组的任意一组确定的值（ u1,… un）
称为Ａ关于 p1,… pn的一个 完全指派,其中 ui或为Ｔ，
或为Ｆ。如果对于Ａ中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式Ａ的关于该变元组的 部分指派 。
,定义,,凡使公式Ａ取真的指派称为Ａ的 成真指派 。
49
§ ３命题公式
,定义,,如果一个命题公式的所有完全指派均为成真指派，则该公式称为 永真式 。如果一个命题公式的所有完全指派均为成假指派，则该公式称为 永假式 。既不是永真式，又不是永假式，则称此命题公式是 可满足式。
讨论：
（１）永真式的否定为永假式（?Ｔ＝Ｆ）；永假式的否定为永真式（?Ｆ＝Ｔ）。
（２）二个永真式的析取、合取、蕴含、等价均为永真式。
50
§ 4等价式
１．等价式
,定义,,如果对两个公式Ａ，Ｂ不论作何种指派，它们真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ（Ｂ）等价于Ｂ（Ａ）。
并记作：Ａ?Ｂ
51
§ 4等价式例：Ｐ ∨?Ｐ?Ｑ ∨?Ｑ
P Q P∨?P Q ∨?Q
F F T T
F T T T
T F T T
T T T T
52
§ 4等价式例：判断公式 A,(PQ)?(P?Q)
与 B,(PR)?(P?R)是否等价。
解：
列该公式的真值表：
53
§ 4等价式
P Q R?Q PQ P?Q?R PR P?R A B
T T T F T T F T T T T
T T F F T T T T T T T
T F T T T T F T T T T
T F F T T T T T T T T
F T T F F T F F T F F
F T F F F T T T F F F
F F T T T F F F T F F
F F F T T F T T F F F
54
§ 4等价式
,定理,,
命题公式Ａ?Ｂ的充要条件是Ａ?Ｂ为永真式。
说明：
,?”为等价关系符，Ａ?Ｂ表示Ａ和Ｂ有等价关系。
Ａ?Ｂ不为命题公式
,?”为等价联结词（运算符），Ａ、Ｂ为命题公式，
则（Ａ?Ｂ）也为一命题公式。
55
§ 4等价式证明：
（１）充分性：Ａ?Ｂ为永真式，即Ａ、Ｂ有相同的真值，所以Ａ?Ｂ。
（２）必要性：Ａ?Ｂ，即Ａ、Ｂ有相同的真值表，所以Ａ?Ｂ为永真式。
例：证明Ｐ?Ｐ；
Ｐ →ＱＰ ∨ Ｑ
56
§ 4等价式
P QP? P P→QP∨ Q
F F F T F T T T
F T F T F T T T
T F T T T F T F
T T T T T T T T
由定理可知,Ａ?Ａ
若Ａ?Ｂ，则Ｂ?Ａ
若Ａ?Ｂ，Ｂ?C,则Ａ?Ｃ
57
§ 4等价式下面列出１５组等价公式
（ 1） 双重否定律Ｐ?Ｐ
（ 2） 同等律 Ｐ ∨ Ｐ?Ｐ；Ｐ ΛＰ?Ｐ
（ 3） 交换律 Ｐ ∨ Ｑ?Ｑ ∨ Ｐ；
Ｐ ΛＱ?Ｑ ΛＰ；Ｐ?Ｑ?Ｑ?Ｐ
（ 4） 结合律
（Ｐ ∨ Ｑ） ∨ Ｒ?Ｐ ∨ （Ｑ ∨ Ｒ）；
（Ｐ ΛＱ） ΛＲ?Ｐ Λ（Ｑ ΛＲ）；
（Ｐ?Ｑ）?Ｒ?Ｐ?（Ｑ?Ｒ）
58
§ 4等价式
（ 5） 分配律
Ｐ Λ（Ｑ ∨ Ｒ）?（Ｐ ΛＱ） ∨ （Ｐ ΛＲ）；
Ｐ ∨ （Ｑ ΛＲ）?（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）
（ 6） 摩根律?（Ｐ ∨ Ｑ）Ｐ Λ?Ｑ；
（Ｐ ΛＱ）Ｐ ∨?Ｑ
（ 7） 吸收律 Ｐ ∨ （Ｐ ΛＱ）?Ｐ；
Ｐ Λ（Ｐ ∨ Ｑ）?Ｐ
59
§ 4等价式
（ 8） 蕴含律 Ｐ →ＱＰ ∨ Ｑ
（ 9） 等价律
Ｐ?Ｑ?（Ｐ →Ｑ） Λ（Ｑ →Ｐ）
（ 10） 零 律 Ｐ ∨ Ｔ?Ｔ；Ｐ ΛＦ?Ｆ
（ 11） 同一律 Ｐ ∨ Ｆ?Ｐ；Ｐ ΛＴ?Ｐ
（ 12） 互补律 Ｐ ∨?Ｐ?Ｔ；Ｐ Λ?Ｐ?Ｆ
（ 13） 输出律
Ｐ ΛＱ →Ｒ?Ｐ →（Ｑ →Ｒ）
60
§ 4等价式
（ 14） 归缪律
（Ｐ →Ｑ） Λ（Ｐ →?Ｑ）Ｐ
（ 15） 逆反律 Ｐ →ＱＱ →?Ｐ
说明：
（１）证明上述１５组等价公式的方法可用真值表法，把?改为?所得的命题公式为永真式，则?
成立。
61
§ 4等价式
（ 2） Λ,∨,?均满足结合律，
则在单一用 Λ,∨,?联结词组成的命题公式中，
括号可以省去 。
（ 3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。
例如,?(P?Q)?(?PQ)，
((P?Q)?(R?S))?(?(P? Q)(R? S)，
((P?Q)R)?(?(P?Q)R)
62
§ 4等价式
２．置换规则
,定义,,给定一命题公式Ｂ，其中 P1、
P2．．,Pn 是Ｂ中的原子命题变元，
若（ 1）用某些命题公式代换Ｂ中的一些原子命题变元 Pi
（ 2）用命题公式 Ａ i代换 Pi，则必须用 Ａ i代换
Ｂ中的所有 Pi
由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例
63
§ 4等价式讨论定义：
（１）用命题公式只能代换原子命题变元，而不能去代换分子命题公式 。
（２）要用命题公式同时代换同一个原子命题变元 。
（３）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。
64
§ 4等价式例,Ｐ ∨?Ｐ为一永真式，若用任何命题公式代换Ｐ，则仍为永真式
Ｐ →Ｑ为一个可满足的命题公式，若用Ｐ代换Ｑ，
则得（Ｐ →Ｐ）为永真式，但（Ｐ →Ｑ）并不是永真式。
（４）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式
65
§ 4等价式例１．
设Ｂ：Ｐ →（?QΛＰ）若用（Ｒ?Ｓ）代换Ｂ中的Ｐ，
得Ａ：（Ｒ?Ｓ） →（?QΛ（Ｒ?Ｓ））是Ｂ的代换实例，
而Ａ’：（Ｒ?Ｓ） →（?QΛＰ）不是 B的代换实例。
例２．Ｐ →?Ｑ的代换实例有：（Ｒ Λ?Ｓ） →?Ｍ，（Ｒ
Λ?Ｓ） →Ｐ，Ｑ →?（Ｐ →?Ｑ）等所以，一个命题公式的代换实例有无限个。
66
§ 4等价式下面讨论取代过程（置换规则）：
,定义,,给定一命题公式Ａ，Ａ’是Ａ的任何部分，
若Ａ’也是一命题公式，则称Ａ’是Ａ的 子命题公式 。
例,Ａ：（Ｐ ∨ Ｑ） →（Ｑ ∨ （Ｒ Λ?Ｓ））
Ａ的子命题公式有：Ｐ、Ｑ、Ｒ,?Ｓ、（Ｐ ∨ Ｑ）、
（Ｒ Λ?Ｓ）、（Ｑ ∨ （Ｒ Λ?Ｓ））、
（Ｐ ∨ Ｑ） →（Ｑ ∨ （Ｒ Λ?Ｓ））等。
67
§ 4等价式
,定理,,给定一命题公式Ａ，Ａ’是Ａ的子公式。
设 B’是一命题公式，若Ａ’? B’，并用 B’取代Ａ
中的Ａ’，从而生成一新的命题公式 B，则Ａ?B。
从定理可见：一个命题公式 A，经多次取代，所得到的新公式与原公式等价。
例：证明：Ｐ →（Ｑ →Ｒ）?Ｐ →（?Ｑ ∨ Ｒ）
Ｐ ∨?Ｑ ∨?Ｒ
68
§ 4等价式
（Ｐ ΛＱ） ∨ Ｒ
（Ｐ ΛＱ） →Ｒ
例：证明：
（（Ｐ ∨ Ｑ） Λ?（?Ｐ Λ（?Ｑ ∨?Ｒ））） ∨ （?Ｐ
Λ?Ｑ） ∨ （?Ｐ Λ?Ｒ）为一永真式
69
§ 4等价式证明,原式,（（Ｐ ∨ Ｑ） Λ?（?Ｐ Λ（?Ｑ ∨?Ｒ））） ∨ （?Ｐ Λ?
Ｑ） ∨ （?Ｐ Λ?Ｒ）
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ （Ｑ ΛＲ））） ∨?（Ｐ ∨
Ｑ） ∨?（Ｐ ∨ Ｒ）
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）） ∨?
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ））
（（Ｐ ∨ Ｑ） Λ（Ｐ ∨ Ｒ）） ∨?（（Ｐ ∨ Ｑ） Λ
（Ｐ ∨ Ｒ））?Ｔ
∵ 它是Ｐ Λ?Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式！
70
§ 4等价式
３．对偶原理（对偶定律）
,定义,,给定二个命题公式Ａ和 A*,若用 Λ代换 ∨,用 ∨
代换 Λ，用Ｔ代换Ｆ，用Ｆ代换Ｔ，其中一个命题公式由另一个命题公式得来，则称Ａ和 A*是互为对偶的，而联结词 Λ和 ∨ 也是互为对偶的例：写出下列命题公式的对偶式：
Ｐ ∨ （Ｑ ΛＲ） Ｐ Λ（Ｑ ∨ Ｒ）
Ｐ ∨ Ｆ?Ｐ 对偶式 A* Ｐ ΛＴ?Ｐ
Ｐ ∨ Ｔ?Ｔ Ｐ ΛＦ?Ｆ
71
§ 4等价式讨论定义：
（１）若命题公式中有联结词?,?，则必须把化成由联结词 Λ,∨,?组成的等价的命题公式，
然后求它的对偶式；
例,求 (P?Q)?(P?R)的对偶式
72
§ 4等价式
（２）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。
例：（Ｐ ΛＱ） ∨ Ｒ对偶式写成
（Ｐ ∨ Ｑ） ΛＲ，而不能写成Ｐ ∨ Ｑ ΛＲ
73
§ 4等价式
,定理,,（摩根推广定理）
设Ａ和 A*为对偶式 P1,P2．．,Pn 是出现在Ａ和 A*中的所有原子命题变元，，于是有：
Ａ（ P1,P2．．,Pn）
A* （?P1,?P2．．,?Pn） ——（ 1）
Ａ（?P1,?P2．．,?Pn）
A*（ P1,P2．．,Pn） ——（２）
74
§ 4等价式证明,由摩根定理
（Ｐ ∨ Ｑ）Ｐ Λ?Ｑ —（１）
（Ｐ ΛＱ）Ｐ ∨?Ｑ —（２）
∴ 不难看出,一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。
例,设Ａ（Ｐ，Ｑ，Ｒ）Ｐ Λ?（Ｑ ∨ Ｒ），
验证上述定理：
75
§ 4等价式证明：
(１ )Ａ（Ｐ，Ｑ，Ｒ）Ｐ Λ?Ｑ Λ?Ｒ
∴?Ａ（Ｐ，Ｑ，Ｒ）?Ｐ ∨ Ｑ ∨ Ｒ
A*（Ｐ，Ｑ，Ｒ）Ｐ ∨?Ｑ ∨?Ｒ
A*（?Ｐ,?Ｑ,?Ｒ）?Ｐ ∨ Ｑ ∨ Ｒ
（２）Ａ（?Ｐ,?Ｑ,?Ｒ）?Ｐ ΛＱ ΛＲ
A*（Ｐ，Ｑ，Ｒ）（?Ｐ ∨ Ｑ ∨?Ｒ）
Ｐ ΛＱ ΛＲ
有Ａ（?Ｐ,?Ｑ,?Ｒ）A*（Ｐ，Ｑ，Ｒ）
76
§ 4等价式
,定理,,若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若Ａ?Ｂ，则 A*?B*成立。
证明,已知：Ａ、Ｂ为任一命题公式，且Ａ?
Ｂ，要证明 A*?B*
设,P1,P2．．,Pn 是出现在Ａ和Ｂ中的原子命题变元，
77
§ 4等价式由Ａ?Ｂ，
即Ａ（ P1,P2．．,Pn）?
Ｂ（ P1,P2．．,Pn）
∴?Ａ（ P1,P2．．,Pn）?
Ｂ（ P1,P2．．,Pn）
由 摩根推广定理
∴ Ａ *（?P1,?P2．．,?Pn）?
Ｂ *（?P1,?P2．．,?Pn）
78
§ 4等价式
∴ Ａ *（?P1,?P2．．,?Pn）?
Ｂ *（?P1,?P2．．,?Pn）为永真式
＊ 前面讲过永真式的代换实例仍为永真式，所以用?Pi代换 A*和 B*中的 Pi （ 1≤i≤n)
则得,Ａ *（P1,P2．．,Pn）?
Ｂ *（P1,P2．．,Pn）
即为：Ａ *（ P1,P2．．,Pn）?
Ｂ *（ P1,P2．．,Pn）
79
§ 4等价式例：证明：
（１）?（Ｐ ΛＱ） →（?Ｐ ∨ （?Ｐ ∨ Ｑ））
（?Ｐ ∨ Ｑ）
（２）（Ｐ ∨ Ｑ） Λ （?Ｐ Λ（?Ｐ ΛＱ））
（?Ｐ ΛＱ）
证明：（１）左边?
（Ｐ ΛＱ） ∨ （?Ｐ ∨ （?Ｐ ∨ Ｑ））
（Ｐ ΛＱ） ∨ （?Ｐ ∨ Ｑ）
（Ｐ ∨?Ｐ ∨ Ｑ） Λ （Ｑ ∨?Ｐ ∨ Ｑ）
（?Ｐ ∨ Ｑ）
80
§ 4等价式
（２）左边? （Ｐ ∨ Ｑ） Λ （?Ｐ ΛＱ）
（Ｐ Λ?Ｐ ΛＱ） ∨ （Ｑ Λ?Ｐ ΛＱ）
（?Ｐ ΛＱ）
结论：（１）和（２）是互为对偶的。
81
§ 5永真蕴含式
,定义,,命题公式Ａ
称为永真蕴含命题公式Ｂ，当且仅当Ａ →Ｂ是一个永真式，
记作：Ａ?Ｂ
说明：“Ａ?Ｂ”读作“Ａ永真蕴含Ｂ”，“Ａ蕴含Ｂ”，
“Ａ能推得Ｂ”
,?,是关系符，Ａ? Ｂ不为命题公式。
例：证明：Ｐ?Ｐ ∨ Ｑ； Ｐ ΛＱ? P
（１）列出真值表证明：Ｐ →（Ｐ ∨ Ｑ）和（Ｐ ΛＱ） →Ｐ为永真式
82
§ 5永真蕴含式
（２）可用等价公式证：
Ｐ →（Ｐ ∨ Ｑ）Ｐ ∨ （Ｐ ∨ Ｑ）? T
（Ｐ ΛＱ） →Ｐ（Ｐ ΛＱ） ∨ Ｐ
Ｐ ∨?Ｑ ∨ Ｐ? T
P Q Ｐ →（Ｐ ∨ Ｑ） （Ｐ ΛＱ） →Ｐ
F F F T F F T F
F T F T T F T F
T F T T T F T T
T T T T T T T T
83
§ 5永真蕴含式
,定理,,设Ａ、Ｂ是二个命题公式
Ａ?Ｂ的充分必要条件是 Ａ?Ｂ且Ｂ? Ａ。
证明,若Ａ?Ｂ，则Ａ?Ｂ为一永真式由定律：
（Ａ?Ｂ）?（Ａ →Ｂ） Λ（Ｂ →Ａ）
∴ （Ａ →Ｂ）且（Ｂ →Ａ）也为一永真式即,Ａ? Ｂ且Ｂ?Ａ成立反之
Ａ? Ｂ且Ｂ? Ａ 则Ａ?Ｂ也成立此定理把,?”和,?,之间建立了相应的关系。
84
§ 5永真蕴含式下面给出常用的永真蕴含式
I1 Ｐ?Ｐ ∨ Ｑ （Ｑ?Ｐ ∨ Ｑ）
I2 Ｐ ΛＱ? Ｐ （Ｐ ΛＱ? Ｑ）
I3 Ｐ Λ（Ｐ →Ｑ）?Ｑ
I4 （Ｐ →Ｑ） Λ?ＱＰ
I5?Ｐ Λ（Ｐ ∨ Ｑ）? Ｑ
I6 （Ｐ →Ｑ） Λ（Ｑ →Ｒ）? （Ｐ →Ｒ）
I7 （Ｐ →Ｑ） Λ（Ｒ →Ｓ）? （Ｐ ΛＲ →Ｑ ΛＳ）
I8 （Ｐ?Ｑ） Λ（Ｑ?Ｒ）? （Ｐ?Ｒ）
I9?P?Ｐ →Ｑ
85
§ 5永真蕴含式
I10 Ｑ? Ｐ →Ｑ
I11?（Ｐ →Ｑ）? Ｐ
I12?（Ｐ →Ｑ）Ｑ
I13 （Ｐ ∨ Ｑ） Λ（Ｐ →Ｒ） Λ（Ｑ →Ｒ）? Ｒ
证明上述永真蕴含式的方法有三种：
（１）把,?,关系符改为,→”联结词，证明它为永真式。
(a)真值表法
(b)命题演算法
86
§ 5永真蕴含式
（２）＊找出使单条件命题前件为“Ｔ”的所有真值指派，试看能否导致后件均为“Ｔ”，若为
“Ｔ”，则永真蕴含关系成立。
P Q P→Q
F F T
F T T
T F F
T T T
87
§ 5永真蕴含式例：Ｐ Λ（Ｐ →Ｑ）? Ｑ
前件为“Ｔ”的所有指派为Ｐ、（Ｐ →Ｑ）均为
“Ｔ”，
Ｐ →Ｑ为“Ｔ”,∵ Ｐ为“Ｔ”,∴ Ｑ也应为
“Ｔ”，
∴ Ｐ Λ（Ｐ →Ｑ）? Ｑ成立
（３）＊找出使单条件命题的后件均为“Ｆ”的所有真值指派，试看前件的所有真值是否为“Ｆ”，
若是，则蕴含成立。
88
§ 5永真蕴含式例,?Ｑ Λ（Ｐ →Ｑ）Ｐ
后件为“Ｆ”的所有条件是：Ｐ为“Ｔ”，
代入前件得
（ ⅰ ）若Ｑ为Ｔ，则?Ｑ Λ（Ｐ →Ｑ）为“Ｆ”；
（ ⅱ ）若Ｑ为Ｆ，则?Ｑ Λ（Ｐ →Ｑ）为“Ｆ”；
∴?Ｑ Λ（Ｐ →Ｑ）Ｐ成立若后件简单则可选用 (3)；若前件简单则可选用 (2)。
二种方法是互为独立的，只需使用一种证明就行。
89
§ 5永真蕴含式讨论一下永真式可得出三个结论：
（１）若一个命题公式等价于一个永真式，则该公式一定为永真式。
（２）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。
（３）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。
90
§ 5永真蕴含式
,定理,,给定命题公式Ａ、Ｂ、Ｃ，
若Ａ?Ｂ，且Ｂ?Ｃ，则Ａ?Ｃ。
证明,∵ Ａ?Ｂ，且Ｂ?Ｃ，
∴ （Ａ →Ｂ） Λ（Ｂ →Ｃ）为永真式，
由 I6：（Ａ →Ｂ） Λ（Ｂ →Ｃ）?
（Ａ →Ｃ），
∴ （Ａ →Ｃ）也为永真式；即，Ａ?Ｃ成立
91
§ 5永真蕴含式
,推论,,
若Ａ?B1,B1? B2．．．．．,Bm?Ｂ，则Ａ?Ｂ。
,定理,,给定一个命题公式Ａ、Ｂ、Ｃ，若Ａ?Ｂ,Ａ?
Ｃ，则Ａ?（Ｂ ΛＣ）
证明,∵ Ａ?Ｂ Λ Ａ?Ｃ，
∴ （Ａ →Ｂ） Λ（Ａ →Ｃ）为永真式，
由条件，若Ａ一定为“Ｔ”，则Ｂ、Ｃ均为“Ｔ”，
∴ Ａ →（Ｂ ΛＣ）也为“Ｔ”，
结论：Ａ?（Ｂ ΛＣ）为“Ｔ”。
92
§ 5永真蕴含式上述也可用等价公式证明它：
（Ａ →Ｂ） Λ（Ａ →Ｃ）
（?Ａ ∨ Ｂ） Λ（?Ａ ∨ Ｃ）
Ａ ∨ （Ｂ ΛＣ）
Ａ →（Ｂ ΛＣ）也为永真式
∴ Ａ?（Ｂ ΛＣ）成立
,定义,,设 H1,H2….Hm,Ｑ 均为命题公式，若
（ H1 ΛH2Λ…Hm ）?Ｑ，则称：
H1,H2….Hm,共同蕴含Ｑ，并记作：
H1,H2….Hm?Ｑ。
93
§ 5永真蕴含式
,定理,,若 （ H1 ΛH2Λ…Hm ）,P?Ｑ，
则（ H1 ΛH2Λ…Hm ）?（Ｐ →Ｑ）。
证明,（ H1 ΛH2Λ…ΛHm ΛP） →Ｑ
（ H1 ΛH2Λ…ΛHm ΛP） ∨ Q
（?H1 ∨?H2 ∨ … ∨?Hm ） ∨ （?P ∨ Q ）
（ H1 ΛH2Λ…ΛHm ） ∨ （ P→ Q ）
H1 Λ H2 Λ…,Λ Hm→（Ｐ →Ｑ）也为永真式
∴ （ H1 Λ,H2 Λ…,Λ Hm ）?（Ｐ →Ｑ）
成立
94
§ 6命题联结词总结
１．其他命题联结词：
（１）不可兼或（异或，异）
(a)符号：,?”（ ⊕ ），Ｐ?Ｑ，读作“Ｐ异或Ｑ”
(b)定义：（由真值表）
(c)异或的性质：
Ｐ?Ｑ
（?Ｐ ΛＱ） ∨ （?Ｑ ΛＰ）
（Ｐ ∨ Ｑ） Λ（?Ｐ ∨?Ｑ）
Ｐ?Ｑ（Ｐ?Ｑ）
Ｐ?Ｑ?Ｑ?Ｐ （可交换的）
（Ｐ?Ｑ）?Ｒ?
Ｐ?（Ｑ?Ｒ）（可结合的）
P Q P? Q
F F F
F T T
T F T
T T F
95
§ 6命题联结词总结
Ｐ Λ（Ｑ?Ｒ）?（Ｐ ΛＱ）?（Ｐ ΛＲ）
（ Λ对? 可分配的）
Ｐ? Ｐ?Ｆ
ＰＰ?Ｔ
Ｆ? Ｐ?Ｐ
Ｔ? ＰＰ
若Ｐ? Ｑ?Ｒ，则有：Ｐ? Ｒ?Ｑ?Ｒ? Ｐ
Ｒ? Ｑ?Ｐ?Ｑ? Ｒ
Ｑ?Ｐ?Ｒ，Ｐ? Ｑ? Ｒ?Ｆ
96
§ 6命题联结词总结
（２）“与非”联结词：
(a)符号,↑”，（Ｐ ↑Ｑ）读作：“Ｐ与Ｑ的否定”或“Ｐ与非Ｑ”
(b)定义：（由真值表）
（Ｐ ↑Ｑ）（Ｐ ∧ Ｑ） P Q P ↑Q
F F T
F T T
T F T
T T F
97
§ 6命题联结词总结
(c)性质：
（Ｐ ↑Ｑ）?（Ｑ ↑Ｐ）
（Ｐ ↑Ｐ）Ｐ
（Ｐ ↑Ｑ） ↑（Ｐ ↑Ｑ）?（Ｐ ∧ Ｑ）
（Ｐ ↑Ｐ） ↑（Ｑ ↑Ｑ）?（Ｐ ∨ Ｑ）
Ｐ ↑（Ｑ ↑Ｒ）Ｐ ∨ （Ｑ ∧ Ｒ） 不可结合的
（Ｐ ↑Ｑ） ↑Ｒ?（Ｐ ∧ Ｑ） ∨?Ｒ 不可结合的
Ｐ ↑ＴＰ，Ｐ ↑Ｆ?Ｔ
98
§ 6命题联结词总结
（３）“或非”联结词：
(a)符号：,↓”
（Ｐ ↓Ｑ）读作：“Ｐ或Ｑ的否定”或,Ｐ或非Ｑ”
(b)定义（由真值表给出）：
（Ｐ ↓Ｑ）（Ｐ ∨ Ｑ）
P Q Ｐ ↓Ｑ
F F T
F T F
T F F
T T F
99
§ 6命题联结词总结
(c)性质：
Ｐ ↓Ｑ?Ｑ ↓Ｐ（可交换的）
Ｐ ↓ＰＰ
（Ｐ ↓Ｑ） ↓（Ｐ ↓Ｑ）?Ｐ ∨ Ｑ
（Ｐ ↓Ｐ） ↓（Ｑ ↓Ｑ）?Ｐ ∧ Ｑ
Ｐ ↓（Ｑ ↓Ｒ）Ｐ ∧ （Ｑ ∨ Ｒ） 不可结合的
（Ｐ ↓Ｑ） ↓Ｒ?（Ｐ ∨ Ｑ） ∧?Ｒ 不可结合的
Ｐ ↓ＦＰ； Ｐ ↓Ｔ?Ｆ
(d)由（２）和（３）中的性质可见,↑和 ↓是互为对偶的。
100
§ 6命题联结词总结
（ 4）,蕴含否定”联结词：
(a)符号：
(b)定义
（由真值表给出）：
P Q(P?Q)
“?”c
P Q P Q
T T F
T F T
F T F
F F F
c
c
101
§ 6命题联结词总结
（１）不同真值表的命题公式：
按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：
(a)若命题变元只有一个Ｐ，则用联结词组成的命题公式由四种不同的真值表，即为：
P 0 1 2 3
F F F T T
T F T F T
102
§ 6命题联结词总结所有依赖于Ｐ的命题公式均等价于这四个中的一个
(b)若有二个命题变元Ｐ、Ｑ，则命题公式的不同真值表有,222=24=16种。
推广到一般：若有ｎ个变元的命题公式，则可构成不同的真值表为 22n（个）。
103
§ 6命题联结词总结
（２）二元运算中的全部联结词总结：
,∧,∨,→,?是五个基本联结词。
到此为止，一个符号系统已定义完毕，它们是：
命题变元,Ａ、Ｂ … Ｘ、Ｙ、Ｚ
值,Ｆ、Ｔ
运算符,
,∧,∨,→,?、,↑,↓,?
括号,（）
关系符,?,?
。
C
104
§ 6命题联结词总结
３．全功能联结词集合：
,定义,,一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，
则称此联结词集合为全功能联结词集合。
,定义,,设有一联结词集合Ａ，
若（１）用Ａ中的联结词的等价式能表达任何的一个命题公式；
105
§ 6命题联结词总结
（２）删除Ａ中的任一联结词，从而形成一个新的联结词集合Ａ’，至少有一个命题公式Ｂ不能用
Ａ’中的联结词的等价式来表示，则称 A为 最小的全功能联结词集合 。
我们可以证明,{?,∨ }； {?,∧ }； {?,→}； {↑}；
{↓}均为全功能联结词集合，且均是 最小的全功能联结词集合 。
例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：
106
§ 6命题联结词总结
（Ｐ →Ｑ）Ｐ ∨ Ｑ {?,∨ }
（?Ｐ ∨ Ｑ）
（Ｐ ∧?Ｑ） {?,∧ }
（Ｐ →Ｑ） {?,→}
(Ｐ Ｑ ) {?,}
（?Ｐ ∨ Ｑ）
（（Ｐ ↓Ｐ） ↓Ｑ） ↓（（Ｐ ↓Ｐ） ↓Ｑ）
{↓}
（?Ｐ ∨ Ｑ）（Ｐ ∧?Ｑ）
Ｐ ↑（Ｑ ↑Ｑ） {↑}
→ c→ c
107
§ 7范式和判定如何判定命题公式为永真式、永假式和可满足的呢或二个命题公式等价，归纳有三种方法：
（ 1）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。
（ 2）命题演算方法,化简命题公式至最简式，看是否存在和 （Ｐ ∨?Ｐ）、（Ｐ ∧?Ｐ）等价，
若不则为可满足的。
（ 3）范式方法：本节就介绍此法。
108
§ 7范式和判定什么叫范式把命题公式化归为一种标准的形式，称此标准形式为范式。
什么叫判定以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。
讨论范式和主范式的目的就是为了进行判定。
109
§ 7范式和判定
１．析取范式和合取范式：
设命题变元为：Ｐ、Ｑ、Ｒ，则：（Ｐ ∨ Ｑ ∨ Ｒ）
的析取式称为“和”；（Ｐ ∧ Ｑ ∧ Ｒ）的合取式称为“积”。
,定义,,命题公式的变元和变元的否定之积称为 基本积,而变元和变元的否定之和称为 基本和 。
110
§ 7范式和判定例：设Ｐ、Ｑ为二个命题变元，则：Ｐ ∨ Ｐ，Ｑ ∨
Ｑ,?Ｐ ∨ Ｑ,?Ｑ ∨?Ｐ，Ｐ ∨ Ｑ，Ｐ ∨?Ｑ称为基本和；Ｐ ∧ Ｐ，Ｑ ∧ Ｑ,?Ｐ ∧ Ｑ,?Ｑ ∧?
Ｐ，Ｐ ∧ Ｑ，Ｐ ∧?Ｑ称为基本积。
若“基本和”或“基本积”中的子公式”，称为此基本积（和）的 因子 。
例,?Ｑ ∧ Ｐ ∧?Ｐ的因子有,?Ｑ、Ｐ、
Ｐ,?Ｑ ∧ Ｐ、Ｐ ∧?Ｐ ……
111
§ 7范式和判定
,定理,,一个基本积必定是永假式，
它的充分必要条件是，它至少包含一对因子，
其中一个是另一个的否定。
证明：
（ ⅰ ）充分条件,Ｐ,?Ｐ为基本积中一对因子
该基本积一定为永假式。
∵ （（Ｐ ∧?Ｐ） ∧ （ … ））?
（Ｆ ∧ （ … ））?Ｆ
（ ⅱ ）必要条件：基本积为永假式?基本积中包含Ｐ,?Ｐ这对因子。
112
§ 7范式和判定反证法：假设基本积中不包含Ｐ,?Ｐ这样的因子，
且为永假式。若给基本积中的命题变元指派
“Ｔ”，而命题变元的否定指派为“Ｆ”，
∵ 在基本积中不包含Ｐ,?Ｐ这对因子，
∴ 基本积得到的真值为“Ｔ”，这和假设相矛盾；
∴ 基本积中必然包含Ｐ,?Ｐ这对因子才能使基本积为“Ｆ”。
113
§ 7范式和判定
,定理,,一个“基本和”必定为永真式，
其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。
,定义,,与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的 析取范式 。并记为,P?P1 ∨ P2 ∨ … ∨ Pn（ n∈I +）。
其中 P1,P2．．,Pn均为基本积。
方法可按下列三步（或四步）进行：
114
§ 7范式 和判定
（１）利用等价公式：化去,→”、,?”联结词，把命题公式变为与其等价的用 {?,∧,∨ }表达的公式。
例,Ｐ →ＱＰ ∨ Ｑ，
Ｐ?Ｑ?（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧?Ｑ）
（?Ｐ ∨ Ｑ） ∧ （Ｐ ∨?Ｑ）
（２）将,?”深入到原子命题变元之前，并使变元之前最多只有一个,?”词。
例,?（?Ｐ ∨?Ｑ）Ｐ ∧Ｑ
Ｐ ∧ Ｑ
115
§ 7范式和判定
（３）利用,∧,对,∨,的分配，将公式化成为析取范式。
（４）除去永假项得最简析取范式。
例：求?（Ｐ ∨ Ｑ）?（Ｐ ∧ Ｑ）的析取范式：
解：原式
(?（Ｐ ∨ Ｑ） ∨ （Ｐ ∧ Ｑ） ) ∧
(?（Ｐ ∧ Ｑ） ∨?（Ｐ ∨ Ｑ） )
116
§ 7范式和判定
(?（Ｐ ∨ Ｑ） ∧ （Ｐ ∧ Ｑ） ) ∨
(（Ｐ ∨ Ｑ） ∧?（Ｐ ∧ Ｑ） )
-----（ 1） 化去?词
（?Ｐ ∧?Ｑ ∧ Ｐ ∧ Ｑ） ∨ （（Ｐ ∨ Ｑ） ∧ （?Ｐ ∨?
Ｑ））
-----（ 2） 将,?”深入到变元前面，并最多保留一个
（?Ｐ ∧?Ｑ ∧ Ｐ ∧ Ｑ） ∨ （（Ｐ ∧?Ｐ） ∨ （Ｐ ∧?
Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｑ ∧?Ｑ））
-----（ 3）,∧,对或,∨,的分配，化成为析取范式
（Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
-----（ 4）最简析取范式
117
§ 7范式 和判定讨论定义：
（１）从上例看出，一个命题公式的析取范式不是唯一的，
但同一命题公式的析取范式一定是等价的。
（２）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。
即,P?P1∨P 2∨?∨P n
（ P1,P2．．,Pn均为基本积）
则,当 P1?P2 Pn?F时,
Ｐ一定为永假式。
(可用来判定是否为永假式 )
118
§ 7范式和判定例,（析取范式）ＰＰ
（Ｐ ∧?Ｐ） ∨ （?Ｐ ∧ Ｐ）
Ｆ 永假式
,定义,,与给定命题公式等价的一个公式，
如果它是由基本和之积所组成，则称它是给定命题公式的 合取范式 。
并表示成,Q? Q1∧ Q2∧ … ∧ Qn,(n∈I +),其中
Q!,Q2,…Q n均为基本和。
119
§ 7范式和判定求一个命题公式的合取范式的方法和求析取范式的方法类同：
第（１）、（２）步相同；
第（３）利用,∨,对,∧,的分配就行；
第（４）去掉永真的析取项。
120
§ 7范式和判定例：求Ｑ ∨?（Ｐ →Ｑ） ∨?（Ｐ ∨ Ｑ）的合取范式原式? Ｑ ∨?（?Ｐ ∨ Ｑ） ∨?（Ｐ ∨ Ｑ）
——化去,→,词
Ｑ ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧?Ｑ）
——“?”深入到变元前，并最多保留一个
（（Ｑ ∨ Ｐ） ∧ （Ｑ ∨?Ｑ）） ∨ （?Ｐ ∧?Ｑ）
——“∨,对,∧,的分配
（Ｑ ∨ Ｐ ∨?Ｐ） ∧ （Ｑ ∨?Ｑ ∨?Ｐ） ∧ （Ｑ ∨ Ｐ ∨
Ｑ） ∧ （Ｑ ∨?Ｑ ∨?Ｑ）
Ｔ（最简合取范式）
121
§ 7范式和判定讨论定义：
（１）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。
（２）若一个命题公式的合取范式中的各基本和的真值为“Ｔ”，则该命题公式一定是永真式。
(可用来判定是否为永真式 )
例：（Ｐ?Ｐ）?（?Ｐ ∨ Ｐ） ∧ （Ｐ ∨?Ｐ）?Ｔ
122
§ 7范式和判定
２．主析取范式。
,定义,,在ｎ个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为 极小项 。
例：对二个命题变元讲，极小项有 22=4个，即,
Ｐ ∧ Ｑ,?Ｐ ∧ Ｑ、Ｐ ∧?Ｑ,?Ｐ ∧?Ｑ
对一个命题变元讲，极小项有 21=2个，即：
Ｐ,?Ｐ
123
§ 7范式和判定对三个命题变元讲，极小项有 23=8个，
即,Ｐ ∧ Ｑ ∧ Ｒ、Ｐ ∧ Ｑ ∧?Ｒ、Ｐ ∧?Ｑ ∧ Ｒ、
Ｐ ∧?Ｑ ∧?Ｒ,?Ｐ ∧ Ｑ ∧ Ｒ,?Ｐ ∧ Ｑ ∧?Ｒ、
Ｐ ∧?Ｑ ∧ Ｒ,?Ｐ ∧?Ｑ ∧?Ｒ
推广到一般：ｎ个命题变元构成的不同极小项有 2n个
（ n∈I +）。使得每个极小项为真的赋值仅有一个。
124
§ 7范式和判定
,定义,,对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的 主析取范式。
,定理,,在真值表中，一个公式的真值为Ｔ的指派所对应的极小项的析取，即为此公式的主析取范式。
125
§ 7范式和判定例：求出Ｐ →Ｑ、Ｐ ∨?Ｑ、
（Ｐ ∧ Ｑ）、Ｐ ∧?Ｑ的主析取范式
Ｐ Ｑ Ｐ ∨?Ｑ?（Ｐ ∧ Ｑ） Ｐ ∧?Ｑ Ｐ →Ｑ
F F T T F T
F T F T F T
T F T T T F
T T T F F T
126
§ 7范式和判定则可直接写出各命题公式的主析取范式：
Ｐ →Ｑ?（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ）
Ｐ ∨?Ｑ?（?Ｐ ∧?Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ）?
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
Ｐ ∧?Ｑ?（Ｐ ∧?Ｑ）
讨论此定理：
（ 1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“Ｔ”的行，对应写出极小项的析取式，且一定是唯一的。
127
§ 7范式和判定
（ 2）若命题公式是含有 n个变元的永真式，则它的主析取范式一定含有 2n个极小项。
（ 3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。
（ 4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“Ｔ”的个数。
128
§ 7范式和判定下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：
（１）将命题公式化归为与其等价的析取范式；
（２）除去永假项，合并基本积中相同项（例：Ｐ
∧ Ｐ ∧ Ｑ?Ｐ ∧ Ｑ），变为最简析取范式。
（３）利用添变元的方法，将所有基本积变为极小项。
129
§ 7范式和判定例：二个变元Ｐ、Ｑ，利用,∧,对或,∨,的分配添项
Ｐ?Ｐ ∧ （Ｑ ∨?Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
Ｑ?Ｑ ∧ （Ｐ ∨?Ｐ）
（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
（４）合并相同的极小项变为一项。
例：求（Ｐ ∧ （Ｐ →Ｑ）） ∨ Ｑ的主析取范式解：原式?（Ｐ ∧?Ｐ） ∨ （Ｐ ∧ Ｑ） ∨ Ｑ
----（ 1）化为析取范式
130
§ 7范式和判定
（Ｐ ∧ Ｑ） ∨ Ｑ
----（ 2）消去永假项，变为最简析取范式
（Ｐ ∧ Ｑ） ∨ （Ｑ ∧ （Ｐ ∨?Ｐ））
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
----（ 3）添项
（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
----（ 4）合并相同最小项
131
§ 7范式和判定例：证明Ｐ ∨ （?Ｐ ∧ Ｑ）?Ｐ ∨ Ｑ
证明方法是写出二个命题公式的主析范式，看其是否相同：
（Ｑ ∨?Ｑ） ∧ Ｐ ∨ （?Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
而Ｐ ∨ Ｑ
（Ｐ ∧ （Ｑ ∨?Ｑ）） ∨ （Ｑ ∧ （Ｐ ∨?Ｐ））
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ）
主析范式相同,∴ 有Ｐ ∨ （?Ｐ ∧ Ｑ）?Ｐ ∨ Ｑ
132
§ 7范式和判定
３．主合取范式
,定义,,在ｎ个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项。
例：有二个变元Ｐ,Ｑ的极大项有 22=4个，（Ｐ
∨ Ｑ）、（Ｐ ∨?Ｑ）、（?Ｐ ∨ Ｑ）、（?Ｐ
∨?Ｑ）
有ｎ个变元，则有 2n个极大项 （ n∈I +）。
133
§ 7范式和判定
,定理,,在真值表中，一个公式的真值为 F的指派所对应的极大项的合取，即为此公式的主合取范式。
在真值表中真值为“Ｆ”的个数等于主合取范式中极大项的个数。
例：求出（Ｐ →Ｑ）、（Ｐ ∨ Ｑ）,?（Ｐ ∧ Ｑ）、
（Ｐ ∧ Ｑ）的主合取范式
134
§ 7范式和判定
Ｐ Ｑ Ｐ ∨ Ｑ?（Ｐ ∧ Ｑ） Ｐ ∧ Ｑ Ｐ →Ｑ
F F F T F T
F T T T F T
T F T T F F
T T T F T T
直接写出其主合取范式：
（Ｐ →Ｑ）?（?Ｐ ∨ Ｑ）（极大项）
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧ Ｑ）
135
§ 7范式和判定
（Ｐ ∨ Ｑ）? （Ｐ ∨ Ｑ）
（?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ） ∨ （Ｐ ∧ Ｑ）
（Ｐ ∧ Ｑ）?（?Ｐ ∨?Ｑ）
（?Ｐ ∧?Ｑ） ∨ （?Ｐ ∧ Ｑ） ∨ （Ｐ ∧?Ｑ）
（ Ｐ ∧ Ｑ ）?
（ Ｐ ∨ Ｑ ） ∧ （ Ｐ ∨?Ｑ ） ∧ （?Ｐ ∨ Ｑ ）
136
§ 7范式和判定讨论
（ １ ） 与命题公式等价的主合范式中极大项的个数等于其真值表中真值为,Ｆ,的个数 。 由真值表找极大项的方法为：将表中值为,Ｆ,的对应真值指派中,把变元写成否定,把变元的否定写成变元 。
（ ２ ） 只要命题公式不是永真式,则一定可以写出对应与其等价的唯一的主合取范式 。
137
§ 7范式和判定
（ ３ ） 若命题公式为含有ｎ个变元的永假式,则主合取范式包含了 2n个极大项的合取式 。
（ ４ ） 可用主合取范式判定二个命题公式是否等价 。
（ ５ ） 已知一个命题公式的主析取范式,则一定可以直接写出与其等价的主合取范式来 。 反之也行 。
例：Ｐ ∨?Ｑ
（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
…… 主析范式
（?Ｐ ∧ Ｑ ）?Ｐ ∨?Ｑ …… 主合取范式
138
§ 7范式和判定
（ ６ ） 对应于有ｎ个变元的命题公式,则一定有：
主析范式极小项数＋主合范式极大项数＝ 2n
下面介绍不用真值表求一命题公式主合取范式的方法：
（ 1） 化为与命题公式等价的合取范式；
（ 2） 除去真值为,T”的析取项和除去析取项中相同变元且只保留一个,变为最简合取式；
（ 3）添项，使析取项均变为极大项；
139
§ 7范式和判定例如：Ｐ,Ｑ为二个变元,
即：Ｐ?Ｐ ∨ （ Ｑ ∧?Ｑ ）
（ Ｐ ∨ Ｑ ） ∧ （ Ｐ ∨?Ｑ ）
（ 4） 合并相同的极大项,保留一项 。
例：求Ｐ ∧ （ Ｐ →Ｑ ） ∨ Ｑ的主合取范式解：原式?Ｐ ∧ （?Ｐ ∨ Ｑ ） ∨ Ｑ
（ Ｐ ∧ Ｑ ） ∨ Ｑ
（ Ｐ ∨ Ｑ ） ∧ Ｑ
（ Ｐ ∨ Ｑ ） ∧ （?Ｐ ∨ Ｑ ）
140
§ 7范式和判定
４,主范式排序 （ 列 ） 的唯一性
（ １ ） 极小项极其编码为了确保主范式的唯一性,二个安排：
（ a） 各命题变元的位置安排一固定次序；
（ b） 对极小项,极大项安排一个次序 。
对于有ｎ个变元的命题公式，则最多可有 2n个极小项，
用 m0 ∧ m1… ∧ m2n-1来表示。
下面列出三个变元,且Ｐ,Ｑ,Ｒ的位置已排定,则
141
m(i)十 十进制数 二进制数 极小项表示
m(0)十 0 000?P ∧? Q ∧? R
m(1)十 1 001?P ∧? Q ∧ R
m(2)十 2 010?P ∧ Q ∧? R
m(3)十 3 011 P ∧? Q?∧ R
m(4)十 4 100 P ∧? Q ∧? R
m(5)十 5 101 P ∧? Q ∧ R
m(6)十 6 110 P ∧ Q ∧? R
m(7)十 7 111 P ∧ Q ∧ R
§ 7范式和判定
142
§ 7范式和判定例：设一命题公式有五个变元,P0,P1,P2,P3,P4（次序已定），则必可写出 25=32个极小项，
下列出 m(11)十 和 m(18)十 的极小项表示：
即,m(11)十 ＝ m(01011)二
＝ （? P0 ∧ P1 ∧? P2 ∧ P3 ∧ P4 ）
m(18)十 ＝ m(10010)二
＝ （ P0 ∧? P1 ∧? P2 ∧ P3 ∧? P4 ）
143
§ 7范式和判定通过上例归纳出一求极小项 m(i)十 的方法：
(a)把 (i)十 变换成等价的 (J0,J1…Jn-1)二
(b)由二进制写出其对应的极小项：
例：求 （ Ｐ ∧ Ｑ ） ∨ （?Ｐ ∧ Ｒ ） 的编码表达式：
（ 设Ｐ,Ｑ,Ｒ次序已定 ）
解：原式?（?Ｐ ∧?Ｑ ∧ Ｒ ） ∨ （?Ｐ ∧ Ｑ ∧
Ｒ ） ∨ （ Ｐ ∧ Ｑ ∧ Ｒ ） ∨ （ Ｐ ∧ Ｑ ∧?Ｒ ）
144
§ 7范式和判定
m(001) 二 ∨ m(010)二 ∨ m(100)二 ∨ m(101)二
m(1)十 ∨ m(3)十 ∨ m(7)十 ∨ m(6)
十
m1,m3,m7,m61,3,6,7
（ ２ ） 极大项及其编码用 M0,M1,… M2n-1表示ｎ个变元的命题公式的极大项 。
求极大项的方法：
145
§ 7范式和判定
(a)把 (i)十 变换成等价的 (J0,J1…Jn-1)二
(b)由二进制数写出其对应的极大项：
例：求（Ｐ ∧ Ｑ） ∨ （?Ｐ ∧ Ｒ）的极大项编码表示（设Ｐ、Ｑ、Ｒ次序已定）
146
§ 7范式和判定解：原式?
（Ｐ ∨ Ｑ ∨ Ｒ） ∧ （Ｐ ∨?Ｑ ∨ Ｒ） ∧ （?Ｐ ∨
Ｑ ∨ Ｒ） ∧ （?Ｐ ∨ Ｑ ∨?Ｒ）
M(000) 二 ∧ M(010)二 ∧ M(100)二 ∧ (110)二
M (0)十 ∧ M (2)十 ∧ M (4)十 ∧ M (5)十
M0,M2,M4,M5
0,2,4,5
147
§ 7范式和判定极大项和极小项编码约定刚好相反,
从上例中,（ Ｐ ∧ Ｑ ） ∨ （?Ｐ ∧ Ｒ ）
1,3,6,70,2,4,5
例：写出 （ Ｐ ∨?Ｑ ） 的主析和主合编码表示
148
§ 7范式和判定
P Q P ∨?Q
F F T
F T F
T F T
T T T
P ∨?Q10,2,3
主析范式为,（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
主合范式为,P ∨?Q
且 P ∨?Q?（?Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧?Ｑ ） ∨ （ Ｐ ∧ Ｑ ）
149
§ 7范式和判定
５,主范式的个数在介绍联结词总结时讲到：
一个原子命题变元有四个不同的真值表（ 221个）；
二个原子命题变元有 16个不同的真值表 （ 222个 ） ；
以此类推,若有ｎ个变元的命题公式,则可构成 22n
个不同的真值表 。
∴ 得到结论：
对于含有ｎ个变元的命题公式,必定可写出 22n个主范式,若排除永真式或永假式,则实际可写出
（ 22n －１ ） 个主析 （ 或主合 ） 范式 。
150
§ 8推理理论按公认的推论规则，从前提集合中推导出一个结论来，
这样的推导过程称为 演绎,或者叫 形式证明 。
在任何论证中,若认定前提是真的,且从前提集合推导出结论的论证是遵守了逻辑规则的,则我们称此结论是 合法的 。
根据逻辑规则推导出来的任何结论称为 有效结论 。
推论规则 就是指确定论证的有效性的判据,常是用命题形式表示这些规则,而不涉及实际命题和它的真值 。
151
§ 8 推理理论本节介绍的证明方法,归纳分成三类：
（一）真值表技术；
（二）推论规则；
（三）间接证明法。
真值表技术的主要依据是,→” 的真值表定义 。
若Ｐ?Ｑ当且仅当
（ Ｐ →Ｑ ） 为永真式 。 P Q Ｐ →Ｑ
F F T
F T T
T F F
T T T
152
§ 8推理理论真值表技术：
,定义,,给定二个命题公式Ａ和Ｂ,当且仅当Ａ →
Ｂ是一个永真式,才可以说Ｂ是从Ａ推导出来的,
或称Ｂ是前提Ａ的有效结论 。
,定义,,设 H1,H2,…Hm,Ｃ都是命题公式,当且仅当 H1 ∧ H2 ∧ … ∧ Hm?Ｃ,才可以说Ｃ是前提集合 ｛ H1,H2,…Hm ｝ 的有效结论 。
153
§ 8推理理论从给定真值表常用的判断方法有二种：
（ １ ） 检查真值表中 H1,H2,…Hm全部为,Ｔ,的所有行,
看结论Ｃ是否也均为,Ｔ,,若Ｃ均为,Ｔ,,则结论有效 。 否则结论无效 。
（２）看结论Ｃ为,Ｆ,的所有行，检查每行前提 H1，
H2,…Hm中是否至少有一个为Ｆ，若有,Ｆ,,则结论有效；若有均为,Ｔ,的行，则结论无效。
例：试证明下列结论是否有效：
画出真值表：
154
§ 8推理理论由真值表可见：
（１）Ｐ，Ｐ →Ｑ?Ｑ 有效
（２）Ｐ →Ｑ,?Ｐ?Ｑ 无效
（３）Ｐ →Ｑ,? （Ｐ ∧ Ｑ）Ｐ 有效
（４）?Ｐ，Ｐ?Ｑ （Ｐ ∧ Ｑ） 有效
P Q Ｐ →Ｑ?Ｐ?Q?（Ｐ ∧ Ｑ） Ｐ?Ｑ
F F T T T T T
F T T T F T F
T F F F T T F
T T T F F F T
155
§ 8推理理论
（５）Ｐ →Ｑ，Ｑ?Ｐ 无效例,H1：如果大连是一个大城市,则大寨是一个乡村； Ｐ →Ｑ
H2：大寨是一个乡村； Ｑ
Ｃ：大连是一个大城市； Ｐ
则：Ｐ →Ｑ,Ｑ?Ｐ
或者称：Ｐ不能从前提集合中推导出来 。
156
§ 8推理理论
２,推理 （ 论 ） 规则：
从这节开始,我们只讨论命题论证的有效性,而不去讨论命题的真假值；
∴ 在推论规则中不需要有真值表,也不需要对命题进行真值指派 。
推理规则的依据是常用的永真蕴含式和等价公式 。
I1 Ｐ?Ｐ ∨ Ｑ； Ｑ?Ｐ ∨ Ｑ
I2 Ｐ?Ｑ?Ｐ； Ｐ?Ｑ?Ｑ
I3 Ｐ,Ｐ →Ｑ?Ｑ
157
§ 8推理理论
I4 （ Ｐ →Ｑ ）,?ＱＰ
I5?Ｐ,（ Ｐ ∨ Ｑ ）?Ｑ
I6 （ Ｐ →Ｑ ）,（ Ｑ →Ｒ ）? （ Ｐ →Ｒ ）
I7 （ Ｐ →Ｑ ）? （（ Ｑ →Ｒ ） →（ Ｐ →Ｒ ））
I8 （ Ｐ →Ｑ ）,（ Ｒ →Ｓ ）? （ Ｐ ∧ Ｒ →Ｑ ∧ Ｓ ）
I9 （ Ｐ?Ｑ ）,（ Ｑ?Ｒ ）? （ Ｐ?Ｒ ）
I10?Ｐ?Ｐ →Ｑ
158
§ 8推理理论下面介绍二个规则：
P规则：在推导的任何步骤上都可以引入前提
（ 条件 ）
T规则：在推导过程中,如果前面有一个或多个公式永真蕴含 S,则可以把 S引入推导过程之中 。
例 1：证明,P?Q,Q? R,P?R
推理过程：
159
§ 8推理理论步骤 推理过程 规则 根据
(1) P?Q P
(2) P P
(3) Q T I(1)(2)
(4) Q? R P
(5) R T I(3)(4)
也可以这样推理：
(1) P?Q P
(2) Q?R P
(3) P?R T I(1)(2)
160
§ 8推理理论
(4) P P
(5) R T I(3)(4)
例 2 证明：
(P∨ Q),(P?R),(Q?S)?S∨ R
(1) (P∨ Q) P
(2)? P?Q T(1) E16
(3) Q?S P
(4)? P?S T(2)(3) I6
(5)? S?P T(4) E18
161
§ 8推理理论
(6) P?R P
(7)? S?R T(6) I6
(8) S∨ R T(7) E16
下面引进条件证明规则 CP：
如果能从 Q和给定的前提集合 P中推导出 R来，
则就能从前提集合中推导出（ Q? R）来。
即,(P∧ Q?R)则,P? (Q?R)
162
§ 8推理理论例 1,P?(Q?S),?R∨ P,Q? R?S
证,(1) R 附加前提
(2)?R∨ P P
(3) R?P T(2) E
(4) P T(1)(3) I
(5) P?(Q?S) P
(6) Q?S T(4)(5) I
163
§ 8推理理论
(7) Q P
(8) S T(6)(7) I
(9) R?S CP
例 2,P?Q? P?(P ∧ Q)
(1) P 附加前提
(2) P?Q P
(3) Q T(1)(2) I
(4) P ∧ Q T(1)(3)
(5) P?(P ∧ Q) CP
164
§ 8推理理论
3．间接证明法,（反证法、归谬法）
,定义,给出命题公式 H1,H2… Hm，
H1?H2?…? Hm具有真值为,T”，则命题公式集合 {H1,H2… Hm}称为是一致的。否则称
{H1,H2… Hm}是非一致的。
165
§ 8推理理论
,定理,设 {H1,H2… Hm}是一致的，同时设 C是一个命题公式，如果前提集合 {H1,H2… Hm,?C}
是非一致的，则一定有 H1,H2… Hm?C成立。
证明：由条件 H1?H2?…? HmC?F
∴ H1?H2?…? HmC必定为永假式。而 H1?H2
…? Hm是一致的，即为永真式，从而只有?C
为永假式，则 C 一定为永真式，
故 H1?H2?…? Hm?C成立。
166
§ 8推理理论例：证明?PQ(P?Q)
证,(1)?(?(P?Q)) 假设前提
(2) P?Q T(1)
(3) P T(2)
(4)?PQ P
(5)?P T(4)
(6) PP T(3)(5)
(7) F
167
§ 8推理理论例 2:证明,RQ,R∨ S,SQ,P?QP
(1)?(?P) 假设前提
(2) P T(1)
(3) P?Q P
(4) Q T(2)(3)
(5) SQ P
(6) QS T(5)
(7)?S T(4)(6)
(8) R∨ S P
(9) R T(7)(8)
168
§ 8推理理论
(10) RQ P
(11)?Q T(9)(10)
(12)Q ∧?Q T(4)(11)
讨论：
由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用 CP规则代替它。
169
§ 8推理理论间接证明法：特殊条件下的 CP规则
∵ H1?H2?…? HmC?F
由 CP规则：
H1?H2?…? HmC?F
C∨ F
C
∴ H1,H2… Hm?C成立
170
§ 8推理理论例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。
（ 1）会计张某或邻居王某谋害了厂长。
（ 2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。
（ 3）如果邻居王某的证词不正确，则在半夜时房里灯光未灭。
（ 4）如果邻居王某的证词是正确的，则谋害发生在半夜。
（ 5）在半夜房子里的灯光灭了，且会计张某曾贪污过。
171
§ 8推理理论解：设 P：会计张某谋害了厂长
Q：邻居王某谋害了厂长
N：谋害发生在半夜
O：邻居王某的证词是正确的
R：半夜时房子的灯光灭了
A：会计张某曾贪污过列出条件公式：
172
§ 8推理理论
(1) P∨ Q (4) Q?N
(2) PN (5) R?A
(3)?OR
推导过程为：
(1) R?A P (6) N T
(2) R T (7) PN P
(3)?OR P (8)?P T
(4) O T (9) P∨ Q P
(5) O? R P (10) Q T
结论：邻居王某谋害了厂长；
173
第一章小结学习第一章要注意以下几点：
（ 1）弄清命题与陈述句的关系。
（ 2）弄清由 6种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式” P?Q“的逻辑关系及其真值。
（ 3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。
（ 4）会准确地求出给定公式的主析取范式和主合取范式。
掌握主析取范式与真值表、成真赋值、主合取范式的关系。
（ 5）会用多种方法判断公式的类型及判断两个公式是否等价。
174
第一章小结
（ 6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。
（ 7）掌握推理和判断推理是否正确的方法。
175
例题选讲例 1.符号化下列命题：
（ 1）辱骂和恐吓决不是战斗；
（ 2）除非天气好，否则我是不会去公园的；
（ 3）如果晚上做完作业且没有其它的事，他就会去看电视或听音乐。
解,（ 1）设 P：辱骂不是战斗。
Q：恐吓不是战斗。
P?Q
（ 2）设 P：今天天气好。
Q：我去公园。 Q?P
176
例题选讲
（ 3）设 P：他晚上做完了作业。
Q：他晚上没有其它事情。
R：他看电视。
S：他听音乐。
（ P?Q）?（ R?S）
例 2.证明 P? （ Q? R）?（ P? Q）? （ P? R）
给出本题的各种证明：
（ 1）列真值表：设 M? P? （ Q? R）
K? （ P? Q）? （ P? R）
S?P? （ Q? R）? （ P? Q）? （ P? R）
177
例题选讲
P Q R Q?R M P?Q P?R K S
T T T T T T T T T
T T F F F T F F T
T F T T T F T T T
T F F T T F F T T
F T T T T T T T T
F T F F T T T T T
F F T T T T T T T
F F F T T T T T T
178
例题选讲
a)直接证法,P? （ Q? R）的真值为 T，其对应指派下
（ P? Q）? （ P? R）的真值均为 T。
b)反证法：（ P? Q）? （ P? R）的真值为 F，其对应指派下 P? （ Q? R）的真值为 F。
c)条件永真式：
（ P? （ Q? R））?（ （ P? Q）? （ P? R））
的真值都为 T，及为永真式。
（ 2）逻辑推证
a)直接证法：设 P? （ Q? R）为 T，则
① P为 T,Q? R为 T，有三种情况：
P为 T,Q为 T,R为 T，则（ P? Q）? （ P? R）为 T。
179
例题选讲
P为 T,Q为 F,R为 T，则（ P? Q）? （ P? R）为 T。
P为 T,Q为 F,R为 F，则（ P? Q）? （ P? R）为 T。
② P为 F,Q? R为 F，则：
P为 F,Q为 T,R为 F，所以 P? Q为 T,P? R为 T，得
（ P? Q）? （ P? R）为 T。
③ P为 F,Q? R为 T，则：
P为 F,Q为 T,R为 T，则（ P? Q）? （ P? R）为 T。
P为 F,Q为 F,R为 F，则（ P? Q）? （ P? R）为 T。
P为 F,Q为 F,R为 T，则（ P? Q）? （ P? R）为 T。
综上各点：当 P? （ Q? R）为 T时，必有（ P? Q）?
（ P? R）为 T。
180
例题选讲
b)间接证法：
设 （ P? Q）? （ P? R）为 F，则必有 P? Q为 T,P? R为 F，故得 P为 T,Q为 T,R为 F。
所以 P? （ Q? R）为 F。
（ 3）等价变换
S? (P? (Q? R))?((P? Q)? (P? R))
(?P?(?Q?R))?((?P? Q)?(?P? R))
(?PQ?R)? (?(?P? Q)? (?P? R))
(P?QR)?((PQ)?(?P? R))
(P?QR)?((?P? R? P)?(?QP? R))
(P?QR)?(?PQ? R)
(P?QR)(P?QR)?T
181
例题选讲例 3.证明 ｛?,?｝不是最小联结词组。
证明：设变元 P,Q，用联结词?,?作用于 P,Q得到：
P,Q,?P,?Q,P?Q,P?P,Q?Q,Q?P。但
(P?Q)?(Q?P),(P?P)? (Q?Q)，故实际有：
P,Q,?P,?Q,P?Q,P?P(T) (A)
用?作用于 (A)类,得到扩大的公式类 (包括原公式类 ):
P,Q,?P,?Q,P?Q,?(P?Q),T,F (B)
用?作用于 (A)类得到：
P?Q,PP(F),PQ(P?Q)，
P? (P?Q)? Q,P? (P?P)?P,
QP(P?Q),QQ(F),Q? (P?Q)? P,
Q?T?Q，
182
例题选讲
PQ? (P?Q),?P? (P?Q)Q，
P?TP,?Q? (P?Q)P，
Q?TQ,(P?Q)? (P?P)? P?Q。
因此 (A)类使用?运算后，仍在 (B)类中。
同样，对 (B)类使用?,?运算后，结果仍在 (B)中。
由上证明：用?,?两个联结词，反复作用在两个变元的公式中，结果只能产生 (B)类中的公式，总共仅八个不同公式，而两个变元所形成的公式共有 222=16个彼此不等价的公式，因此 ｛?,?｝不是功能完备的，更不可能是最小联结词组。
183
例题选讲例 4,求 (A?B?C)?(?A?(?BC))的主析取范式与主合取范式。
解,(1)列表法：
设 S? (A?B?C)?(?A?(?BC))，
R? A?B?C，
MA?(?BC)，
根据真值表中 S真值为 T的指派，所对应的小项析取即为 S的主析取范式,S真值为 F的指派，所对应的大项合取即为主合取范式。
S的真值表如下：
184
例题选讲
A B C B?C R?A?BC M S
T T T T T F F T T
T T F F F F F T F
T F T F F F F T F
T F F F F F T F F
F T T T T T F F F
F T F F T T F F F
F F T F T T F F F
F F F F T T T T T
185
例题选讲
S? (A?B? C)?(?ABC) －－ 主析取范式
S?(?AB? C)?(?A? BC)?(?A? B? C)
(ABC)?(AB? C)?(A? BC)
－－主合取范式
(2)公式推导法：
S? (A?B?C)?(?A?(?BC))
(?A? (B?C))?(?A?(?BC))?((?BC)A)
(?A? (B?C))?(A?(?BC))?((B?C)A)
((?ABC)? (A?B?C))?(B?CA)
(?ABC)? (A?B?C)?m000?m1110,7
186
例题选讲当求出主析取范式的编码表达式后可直接利用编码关系，解出主合取范式。即：
S? (A?B?C)?(?A?(?BC))
(?ABC)? (A?B?C)?m000?m1110,7
1,2,3,4,5,6?M001?M010?M011?M100?M100?M101?M110
(?AB? C)?(?A? BC)?(?A? B? C)
(ABC)?(AB? C)?(A? BC)
187
例题选讲例 5.用推理规则论证下述问题：
或者是天晴，或者是下雨。如果是天晴，我去看电影。
如果我去看电影，我就不看书。所以，如果我在看书，则天在下雨。
解：设 S：今天天晴。 R：今天下雨。
E：我去看电影。 B：我去看书。
本题符号化为：
S?R,S?E,EB?B?R
因为 S?R(S?R)
故本题为?(S?R),S?E,EB?B?R
188
例题选讲
① 直接证法：
(1)?(S?R) P
(2) S R T(1),E
(3) (SR)?(?R?S) T(2),E
(4)?R?S T(3),I
(5)S?E P
(6)?R?E T(4)(5),I
(7)EB P
(8)?RB T(6)(7),I
(9)B?R T(8),E
189
例题选讲
② 间接证法：
a) (1)?(S?R) P
(2) S R T(1)
(3) (SR)?(?R?S) T(2)
(4)?R?S T(3)
(5)?(B?R) P(附加前提 )
(6)BR T(5)
(7)B T(6)
(8)?R T(6)
(9)S T(4)(8)
190
例题选讲
(10) S?E P
(11)E T(4)(10)
(12)EB P
(13)?B T(11)(12)
(14)BB 矛盾 (7)(13)
b)
(1)B P(附加前提 )
(2)EB P
(3)?E T(1)(2)
(4) S?E P
191
例题选讲
(5)?S T(3)(4)
(6)?(S?R) P
(7) S R T(6)
(8) (SR)?(?R?S) T(7)
(9)?R?S T(8)
(10)?S?R T(9)
(11)R T(5)(10)
(12) B?R CP
