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：三角形是直角三角形。
该命题符号化为,?P??Q
40
§ 2命题联结词
（ 5）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为,P ▽ Q
也可符号化为：
（ P??Q） ?（ ?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,(P??Q)?(P?Q)
与 B,(P??R)?(P?R)是否等价。
解：
列该公式的真值表：
53
§ 4等价式
P Q R ?Q P??Q P?Q ?R P??R 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 Q ??P ? P P→Q ? ?P∨ 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) ?(?P ??Q)，
?((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,m6??1,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,7 ??0,2,4,5
例：写出 （ Ｐ ∨ ?Ｑ ） 的主析和主合编码表示
148
§ 7范式和判定
P Q P ∨ ?Q
F F T
F T F
T F T
T T T
P ∨ ?Q??1 ??0,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 ?… ? Hm ? ?C ?F
∴ H1?H2 ?… ? Hm ? ?C必定为永假式。而 H1?H2
?… ? Hm是一致的，即为永真式，从而只有 ?C
为永假式，则 C 一定为永真式，
故 H1?H2 ?… ? Hm?C成立。
166
§ 8推理理论
例：证明 ?P ? ?Q? ?(P?Q)
证, (1) ?(?(P?Q)) 假设前提
(2) P?Q T(1)
(3) P T(2)
(4) ?P ? ?Q P
(5) ?P T(4)
(6) P? ?P T(3)(5)
(7) F
167
§ 8推理理论
例 2:证明, R??Q,R∨ S,S??Q,P?Q ? ?P
(1) ?(?P) 假设前提
(2) P T(1)
(3) P?Q P
(4) Q T(2)(3)
(5) S??Q P
(6) Q??S T(5)
(7) ?S T(4)(6)
(8) R∨ S P
(9) R T(7)(8)
168
§ 8推理理论
(10) R??Q P
(11) ?Q T(9)(10)
(12)Q ∧ ?Q T(4)(11)
讨论：
由上例可见，间接证明法在结论较为简单的条件
下，使用是比较方便的，实际上间接证明法也
可以用 CP规则代替它。
169
§ 8推理理论
间接证明法：特殊条件下的 CP规则
∵ H1?H2 ?… ? Hm ? ?C ?F
由 CP规则：
H1?H2 ?… ? Hm ? ?C ?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) P??N (5) R?A
(3) ?O? ?R
推导过程为：
(1) R?A P (6) N T
(2) R T (7) P??N P
(3) ?O? ?R 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))
?? (?P??Q ?R)? (?( ?P ? Q) ? (?P ? R))
?(P?Q ??R) ?((P ??Q) ?(?P ? R))
? (P?Q ??R) ?((?P ? R ? P) ?(?Q ??P ? R))
? (P?Q ??R) ?(?P ??Q ? R)
? (P?Q ??R) ??(P?Q ??R)?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,P??P(F),P??Q??(P?Q)，
P? (P?Q) ? Q, P? (P?P) ?P,
Q??P ??(P?Q),Q??Q(F),Q ? (P?Q) ? P,
Q?T ?Q，
182
例题选讲
?P??Q? (P?Q),?P? (P?Q) ??Q，
?P?T ??P,?Q? (P?Q) ??P，
?Q?T ??Q,(P?Q) ? (P?P) ? P?Q。
因此 (A)类使用 ?运算后，仍在 (B)类中。
同样，对 (B)类使用 ?,?运算后，结果仍在 (B)中。
由上证明：用 ?,?两个联结词，反复作用在两个变元的公
式中，结果只能产生 (B)类中的公式，总共仅八个不同公
式，而两个变元所形成的公式共有 222=16个彼此不等价的
公式，因此 ｛ ?,?｝不是功能完备的，更不可能是最小
联结词组。
183
例题选讲
例 4,求 (A?B?C) ?(?A?(?B??C))的主析取范式与主合取
范式。
解, (1)列表法：
设 S ? (A?B?C) ?(?A?(?B??C))，
R? A?B?C，
M??A?(?B??C)，
根据真值表中 S真值为 T的指派，所对应的小项析取即为 S的
主析取范式,S真值为 F的指派，所对应的大项合取即为
主合取范式。
S的真值表如下：
184
例题选讲
A B C B?C R ?A ?B??C 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)?(?A ??B ??C) －－ 主析取范式
S ?(?A ??B ? C) ?(?A ? B ??C) ?(?A ? B ? C)
?(A ??B ??C) ?(A ??B ? C) ?(A ? B ??C)
－－主合取范式
(2)公式推导法：
S ? (A?B?C) ?(?A?(?B??C))
? (?A ? (B?C)) ?(?A ?(?B??C)) ?((?B??C) ??A)
? (?A ? (B?C)) ?(A ?(?B??C)) ?((B?C) ??A)
? ((?A ??B??C) ? (A ?B?C)) ?(B?C ??A)
? (?A ??B??C) ? (A ?B?C) ?m000 ?m111 ??0,7
186
例题选讲
当求出主析取范式的编码表达式后可直接利用编码关系，解
出主合取范式。即：
S ? (A?B?C) ?(?A?(?B??C))
? (?A ??B??C) ? (A ?B?C) ?m000 ?m111 ??0,7
??1,2,3,4,5,6 ?M001 ?M010 ?M011 ?M100 ?M100 ?M101 ?M110
? (?A ??B ? C) ?(?A ? B ??C) ?(?A ? B ? C)
?(A ??B ??C) ?(A ??B ? C) ?(A ? B ??C)
187
例题选讲
例 5.用推理规则论证下述问题：
或者是天晴，或者是下雨。如果是天晴，我去看电影。
如果我去看电影，我就不看书。所以，如果我在看书，则
天在下雨。
解：设 S：今天天晴。 R：今天下雨。
E：我去看电影。 B：我去看书。
本题符号化为：
S?R,S?E,E??B?B?R
因为 S?R??(S?R)
故本题为 ?(S?R),S?E,E??B?B?R
188
例题选讲
① 直接证法：
(1) ?(S?R) P
(2) S?? R T(1),E
(3) (S??R)?(?R?S) T(2),E
(4) ?R?S T(3),I
(5)S?E P
(6) ?R?E T(4)(5),I
(7)E??B P
(8) ?R??B T(6)(7),I
(9)B?R T(8),E
189
例题选讲
② 间接证法：
a) (1) ?(S?R) P
(2) S?? R T(1)
(3) (S??R)?(?R?S) T(2)
(4) ?R?S T(3)
(5) ?(B?R) P(附加前提 )
(6)B??R 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)E??B P
(13) ?B T(11)(12)
(14)B??B 矛盾 (7)(13)
b)
(1)B P(附加前提 )
(2)E??B 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) (S??R)?(?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：三角形是直角三角形。
该命题符号化为,?P??Q
40
§ 2命题联结词
（ 5）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为,P ▽ Q
也可符号化为：
（ P??Q） ?（ ?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,(P??Q)?(P?Q)
与 B,(P??R)?(P?R)是否等价。
解：
列该公式的真值表：
53
§ 4等价式
P Q R ?Q P??Q P?Q ?R P??R 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 Q ??P ? P P→Q ? ?P∨ 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) ?(?P ??Q)，
?((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,m6??1,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,7 ??0,2,4,5
例：写出 （ Ｐ ∨ ?Ｑ ） 的主析和主合编码表示
148
§ 7范式和判定
P Q P ∨ ?Q
F F T
F T F
T F T
T T T
P ∨ ?Q??1 ??0,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 ?… ? Hm ? ?C ?F
∴ H1?H2 ?… ? Hm ? ?C必定为永假式。而 H1?H2
?… ? Hm是一致的，即为永真式，从而只有 ?C
为永假式，则 C 一定为永真式，
故 H1?H2 ?… ? Hm?C成立。
166
§ 8推理理论
例：证明 ?P ? ?Q? ?(P?Q)
证, (1) ?(?(P?Q)) 假设前提
(2) P?Q T(1)
(3) P T(2)
(4) ?P ? ?Q P
(5) ?P T(4)
(6) P? ?P T(3)(5)
(7) F
167
§ 8推理理论
例 2:证明, R??Q,R∨ S,S??Q,P?Q ? ?P
(1) ?(?P) 假设前提
(2) P T(1)
(3) P?Q P
(4) Q T(2)(3)
(5) S??Q P
(6) Q??S T(5)
(7) ?S T(4)(6)
(8) R∨ S P
(9) R T(7)(8)
168
§ 8推理理论
(10) R??Q P
(11) ?Q T(9)(10)
(12)Q ∧ ?Q T(4)(11)
讨论：
由上例可见，间接证明法在结论较为简单的条件
下，使用是比较方便的，实际上间接证明法也
可以用 CP规则代替它。
169
§ 8推理理论
间接证明法：特殊条件下的 CP规则
∵ H1?H2 ?… ? Hm ? ?C ?F
由 CP规则：
H1?H2 ?… ? Hm ? ?C ?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) P??N (5) R?A
(3) ?O? ?R
推导过程为：
(1) R?A P (6) N T
(2) R T (7) P??N P
(3) ?O? ?R 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))
?? (?P??Q ?R)? (?( ?P ? Q) ? (?P ? R))
?(P?Q ??R) ?((P ??Q) ?(?P ? R))
? (P?Q ??R) ?((?P ? R ? P) ?(?Q ??P ? R))
? (P?Q ??R) ?(?P ??Q ? R)
? (P?Q ??R) ??(P?Q ??R)?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,P??P(F),P??Q??(P?Q)，
P? (P?Q) ? Q, P? (P?P) ?P,
Q??P ??(P?Q),Q??Q(F),Q ? (P?Q) ? P,
Q?T ?Q，
182
例题选讲
?P??Q? (P?Q),?P? (P?Q) ??Q，
?P?T ??P,?Q? (P?Q) ??P，
?Q?T ??Q,(P?Q) ? (P?P) ? P?Q。
因此 (A)类使用 ?运算后，仍在 (B)类中。
同样，对 (B)类使用 ?,?运算后，结果仍在 (B)中。
由上证明：用 ?,?两个联结词，反复作用在两个变元的公
式中，结果只能产生 (B)类中的公式，总共仅八个不同公
式，而两个变元所形成的公式共有 222=16个彼此不等价的
公式，因此 ｛ ?,?｝不是功能完备的，更不可能是最小
联结词组。
183
例题选讲
例 4,求 (A?B?C) ?(?A?(?B??C))的主析取范式与主合取
范式。
解, (1)列表法：
设 S ? (A?B?C) ?(?A?(?B??C))，
R? A?B?C，
M??A?(?B??C)，
根据真值表中 S真值为 T的指派，所对应的小项析取即为 S的
主析取范式,S真值为 F的指派，所对应的大项合取即为
主合取范式。
S的真值表如下：
184
例题选讲
A B C B?C R ?A ?B??C 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)?(?A ??B ??C) －－ 主析取范式
S ?(?A ??B ? C) ?(?A ? B ??C) ?(?A ? B ? C)
?(A ??B ??C) ?(A ??B ? C) ?(A ? B ??C)
－－主合取范式
(2)公式推导法：
S ? (A?B?C) ?(?A?(?B??C))
? (?A ? (B?C)) ?(?A ?(?B??C)) ?((?B??C) ??A)
? (?A ? (B?C)) ?(A ?(?B??C)) ?((B?C) ??A)
? ((?A ??B??C) ? (A ?B?C)) ?(B?C ??A)
? (?A ??B??C) ? (A ?B?C) ?m000 ?m111 ??0,7
186
例题选讲
当求出主析取范式的编码表达式后可直接利用编码关系，解
出主合取范式。即：
S ? (A?B?C) ?(?A?(?B??C))
? (?A ??B??C) ? (A ?B?C) ?m000 ?m111 ??0,7
??1,2,3,4,5,6 ?M001 ?M010 ?M011 ?M100 ?M100 ?M101 ?M110
? (?A ??B ? C) ?(?A ? B ??C) ?(?A ? B ? C)
?(A ??B ??C) ?(A ??B ? C) ?(A ? B ??C)
187
例题选讲
例 5.用推理规则论证下述问题：
或者是天晴，或者是下雨。如果是天晴，我去看电影。
如果我去看电影，我就不看书。所以，如果我在看书，则
天在下雨。
解：设 S：今天天晴。 R：今天下雨。
E：我去看电影。 B：我去看书。
本题符号化为：
S?R,S?E,E??B?B?R
因为 S?R??(S?R)
故本题为 ?(S?R),S?E,E??B?B?R
188
例题选讲
① 直接证法：
(1) ?(S?R) P
(2) S?? R T(1),E
(3) (S??R)?(?R?S) T(2),E
(4) ?R?S T(3),I
(5)S?E P
(6) ?R?E T(4)(5),I
(7)E??B P
(8) ?R??B T(6)(7),I
(9)B?R T(8),E
189
例题选讲
② 间接证法：
a) (1) ?(S?R) P
(2) S?? R T(1)
(3) (S??R)?(?R?S) T(2)
(4) ?R?S T(3)
(5) ?(B?R) P(附加前提 )
(6)B??R 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)E??B P
(13) ?B T(11)(12)
(14)B??B 矛盾 (7)(13)
b)
(1)B P(附加前提 )
(2)E??B 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) (S??R)?(?R?S) T(7)
(9) ?R?S T(8)
(10) ?S?R T(9)
(11)R T(5)(10)
(12) B?R CP
