离散数学电子教材1

第1章 命题逻辑
逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻 辑是研究反映客观世界
辩证发展过程的人类思维的形态的。形式逻辑是研究思维的形式结构和规律的科学 ，它撇开
具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。所谓的数学方法也就是
用一套有 严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。
数理逻辑的基础部分是 命题逻辑和谓词逻辑。本章主要讲述命题逻辑，谓词逻辑将在第
2章进行讨论。
命题及其表示
1.1.1命题的基本概念
数理逻辑研究的中心问题是推理（Inference)，而推理 就必然包含前提和结论，前提和
结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要 素。在数理逻辑中，
将能够判断真假的陈述句称为命题。因此命题就成为推理的基本单位。在命题逻辑中 ，对命
题的组成部分不再进一步细分。
定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的
真值，常用 T(True)（或1）表示真，F(False)（或0）表示假。真值为真的命题称为真命题，
真值 为假的命题称为假命题。
从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈 述句，二
是能否判定真假，二者缺一不可。
例 判断下列句子是否为命题
（1） 北京是中国的首都。
（2） 请勿吸烟！
（3） 雪是黑的。
（4） 明天开会吗？
（5） x+y=5。
（6） 我正在说谎。
（7） 9+5≤12。
（8） 1+101=110。
（9） 今天天气多好啊！
（10） 别的星球上有生物。
解 在上述的十个句子中，（2）、（9）为祈使句，（4 ）为疑问句，（5）、（6）虽然是陈述
句，但（5）没有确定的真值，其真假随x、y取值的不同而有 改变，（6）是悖论(Paradox)
（即由真能推出假，由假也能推出真），因而（2）、（4）、 （5）、（6）、（9）均不是命题。（1）、
（3）、（7）、（8）、（10）都是命题，其中（1 0）虽然现在无法判断真假，但随着科技的进步
是可以判定真假的。
需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1 的
（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，
否 则为假命题。还有的命题的真假不能马上给出，如例 的（10），但它确实有真假意义。
1.1.2 命题分类

根据命题的结构形式，命题分为原子命题和复合命题。
定义1.1.2 不能被分解为更简单的陈述语句的命题称为原子命题(Simple Proposition )。

由两个或两个以上原子命题组合而成的命题称为复合命题(Compound Proposition )。
例如，例1.1.1中的命题全部为原子命题，而命题“小王和小李都 去公园。”是复合命题，
是由“小王去公园。”与“小李去公园。”两个原子命题组成的。
1.1.3命题标识符
定义1.1.3 表示原子命题的符号称为命题标识符(Identifier)。
通常用大写字母A
，
B
，
C
，…，
P
，
Q
，…
等表示命题，如P：今天下雨。
命题标识符依据表示命题的情况，分为命题常元和命题变元。一个表示 确定命题的标识
符称为命题常元（或命题常项）(Propositional constant)； 没有指定具体内容的命题标识符称
为命题变元（或命题变项）(Propositional Vari able)。命题变元的真值情况不确定，因而命题
变元不是命题。只有给命题变元P一具体的命题取代 时，P有了确定的真值，P才成为命题。


习题
1． 判断下列语句是否为命题，若是，指出其真值。
（1） 外面下雨吗？
（2） 7能被2 整除。
（3） 2x+3<4。
（4） 请关上门。
（5） 小红在教室里。
2． 指出下列命题是原子命题还是复合命题。
（1） 小李一边看书，一边听音乐。
（2） 北京不是中国的首都。
（3） 大雁北回，春天来了。
（4） 不是东风压倒西风，就是西风压倒东风。
（5） 张三与李四在吵架。


逻辑联结词
本节主要介绍5种常用的逻辑联结词
(Logical Connectives )
，分别是“非”（否定联结
词）、“与”（合取联结词）、“或” （析取联结词）、“若…则…”（条件联结词）、“…当且仅当…”
（双条件联结词），通过这些联结词 可以把多个原子命题复合成一个复合命题。
下面分别给出各自的符号形式及真值情况。

1.2.1 否定联结词

定义1.2.1 设P为一命题，P的否定
(Negation)
是一个新的命题，记为
?P
（读作非P）。
规定若P为 T，则
?P
为F；若P为F，则
?P
为T。
?P
的取值情况依赖于P的取值情况，真值情况见表1-1。
表1-1
P
1
0
?P

0
1
在自然语言中 ，常用“非”、“不”、“没有”、“无”、“并非”等来表示否定。
例 P：上海是中国的城市。
?P
：上海不是中国的城市。

P是真命题，
?P
是假命题。
Q：所有的海洋动物都是哺乳 动物。
?Q
：不是所有的海洋动物都是哺乳动物。Q为假
命题，
?Q
为真命题。
1.2.2合取联结词

定义1.2.2 设P、Q为两个命题，P 和Q的合取(Conjunction)是一个复合命题，记为
P
?
Q（读作P与Q） ，称为P与Q的合取式。规定P与Q同时为T时，P
?
Q为T，其余
情况下，P
?
Q均为F。
联结词“
?
”的定义见表1-2。
表1-2 联结词“
?
”的定义
P
0
0
1
1
Q
0
1
0
1
P
?
Q
0
0
0
1
显然P
?
?P
的真值永远是假，称为矛盾式。
在自然语言中，常用 “既…又…”、“不但…而且…”、“虽然…但是…”、“一边…一边…”
等表示合取。
例 （1）今天下雨又刮风。
设P：今天下雨。Q：今天刮风。则（1）可表示为P
?
Q
（2）猫吃鱼且太阳从西方升起。
设P：猫吃鱼。Q：太阳从西方升起。则（2）可表示为P
?
Q
（3）张三虽然聪明但不用功。
P：张三聪明。Q：张三用功。则（3）可表示为P
?
?
Q
需要注 意的是，在自然语言中，命题（2）是没有实际意义的，因为P与Q两个命题是
互不相干的，但在数理逻 辑中是允许的，数理逻辑中只关注复合命题的真值情况，并不关心
原子命题之间是否存在着内在联系。
1.2.3 析取联结词
定义1.2.3 设P、Q为两个命题，P和Q的析取(Disj unction)是一个复合命题，记为P
?
Q
（读作P或Q），称为P与Q的析取式 。规定当且仅当P与Q同时为F时，P
?
Q为F，否
则P
?
Q均为T 。
析取联结词“
?
”的定义见表1-3。
表1-3 联结词“
?
”的定义
P
0
0
1
1
Q
0
1
0
1
P
?
Q
0
1
1
1
显然
P??P
的真值永远为真，称为永真式。
析取联结词“
?”与汉语中的“或”二者表达的意义不完全相同，汉语中的“或”可
表达“排斥或”，也可以表达“ 可兼或”，而从析取联结词的定义可看出，“
?
”允许P、Q

同时为真 ，因而析取联结词“
?
”是可兼或。对于“排斥或”将在中论述。
例 （1）小王爱打球或跑步。
（2）他身高1.8m或1.85m。
（1）为可兼或，（2）为排斥或。
设P：小王爱打球。Q：小王爱跑步。则（1）可表示为P
?
Q
设P：他身 高米。Q：他身高米。则（2）可表示为（P
?
?
Q）
?
（
?
P
?
Q）
1.2.4条件联结词
定义1.2.4 设P、Q为 两个命题，P和Q的条件(Conditional)命题是一个复合命题，记
为P
?
Q（读作若P则Q），其中P称为条件的前件，Q称为条件的后件。规定当且仅当前
件P为T， 后件Q为F时，P
?
Q为F，否则P
?
Q均为T。
条件联结词“
?
”的定义见表1-4。
表1-4 联结词“
?
”的定义
P
0
0
1
1
Q
0
1
0
1
P
?
Q
1
1
0
1
在自然语言中，常会出现的语句如“只要P就Q
”、
“因为P所以Q”、“ P仅当Q”、“只
有Q才P”、“除非Q才P”等都可以表示为“P
?
Q”的形式。
例（1）如果雪是黑色的，则太阳从西方升起。
（2）仅当天气好，我才去公园。
对于（1），设P：雪是黑色的。Q：太阳从西方升起。则（1）可表示为P
?
Q
（2）设R：天气好。S：我去公园。则（2）可表示为S
?
R

1.2.5 双条件联结词

定义1.2.5 设P、Q为两个命题，其复合命题P
?
Q称为双条件(Biconditional)命题，
P
?
Q读作 P当且仅当Q。规定当且仅当P与 Q真值相同时，P
?
Q为T，否则P
?
Q
均为F。
双条件联结词“
?
”的定义如表1-5所示。
表1-5
P
0
0
1
1
Q
0
1
0
1
P
?
Q
1
0
0
1
例1.2.5（1）雪是黑色的当且仅当2+2>4。
（2）燕子北回，春天来了。
（1）设P：雪是黑色的。Q：2+2>4。则（1）可表示为P
?
Q，其真值为T。
（2）设R：燕子北回。S：春天来了。则（2）可表示为R
?
S，其真值为T。
与前面的联结词一样，条件联结词和双条件联结词连接的两个命题之间可以没有任何
的因果联系 ，只要能确定复合命题的真值即可。

习题
1．指出下列命题的真值：
（1） 若2+2>4，则太阳从西方升起。
（2） 若a
?
?
，则a
?
A。
（3） 胎生动物当且仅当是哺乳动物。
（4） 指南针永指北方，除非它旁边有磁铁。
（5） 除非ABCD 是平行四边形,否则它的对边不都平行。
2．令P：天气好。Q：我去公园。请将下列命题符号化。
（1） 如果天气好，我就去公园。
（2） 只要天气好，我就去公园。
（3） 只有天气好，我才去公园。
（4） 我去公园，仅当天气好。
（5） 或者天气好，或者我去公园。
（6） 天气好，我去公园。


命题公式与翻译

1.3.1命题公式
上一节介绍了5种常用的逻辑联结词，利用 这些逻辑联结词可将具体的命题表示成符
号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经 过各种相互组合以得到其符
号化的形式，那么怎样的组合形式才是正确的、符合逻辑的表示形式呢？
定义1.3.1（1）单个的命题变元是命题公式。
（2）如果
A
是命题公式，那么
?A
也是命题公式。
（3 ）如果
A
、
B
是命题公式，那么(
A
∧
B
),（
A
∨
B
), (
A
→
B
)和
(
A
?
B
)也是命题公式。
（4）当且仅当能够 有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词
和括号的符号串是命题公式（又称 为合式公式，或简称为公式）。
上述定义是以递归的形式给出的，其中（1）称为基础，（2）、（3 ）称为归纳，（4）
称为界限。
由定义知,命题公式是没有真假的，仅当一个命题公式中的命 题变元被赋以确定的命题
时，才得到一个命题。例如在公式
P?Q
中，把命题“雪是白 色的。”赋给
P
，把命题“2+2>4。”
赋给
Q
，则公式
P?Q
被解释为假命题；但若
P
的赋值不变，而把命题“2+2=4。”赋给
Q
，
则公式
P?Q
被解释为真命题。
定义中的符号
A,
B
不同于具体公式里的
P
、
Q
、
R
等符号，它可以用来表示任意的
命题公式。
例
?(P?Q)
，
(P?(Q?R))
，
((P?Q)?(Q?R))
等都是命题公式，而

P?(?Q)
，
(P?Q
，
(P?Q)?R)
等都不是命 题公式。
为了减少命题公式中使用括号的数量，规定：（1）逻辑联结词的优先级别由高到低依
次为
?
、∧、∨、→、
?
。（2）具有相同级别的联结词，按出现的先后次 序进行计算，括
号可以省略。（3）命题公式的最外层括号可以省去。
例
(P? Q)?R
也可以写成
P?Q?R
，
(P?Q)?R
也可写成
P?Q?R
，
((P?Q)?R)
也可写成
(P?Q)?R
，而P?(Q?R)
中的括号不能省去。
定义1.3.2 设
P
是命题公式
Q
的一部分，且
P
也是命题公式，则称
P
为
Q的子公式。
例如
P?Q
及
R
都是公式
P?Q?R的子公式；
?P
、
?P?Q
及
P?R
都是公式
(?P?Q)?(P?R)
的子公式。
1.3.2 命题的符号化
有了命题公 式的概念之后，就可以把自然语言中的一些命题翻译成命题逻辑中的符号化
形式。把一个文字描述的命题 相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形
式称为命题的符号化或翻译。
命 题符号化的一般步骤：（1）明确给定命题的含义；（2）找出命题中的各原子命题，分
别符号化。（3 ）使用合适的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化
形式。
把命题符 号化，是不管具体内容而突出思维形式的一种方法。注意在命题符号化时，要
正确地分析和理解自然语言 命题，不能仅凭文字的字面意思进行翻译。
例 张三或李四都可以做这件事。
设
P
：张三可以做这件事。
Q
：李四可以做这件事。
则命题符号化为：
P?Q
，而不是
P?Q
。
例 （1）只有你走，我才留下。
这个命题的意义也可以理解为：如果我留下了，那么你一定走了。 设
P
：你走。
Q
：我留下。则命题符号化为：
Q?P
。
与原命题类似的命题如：仅当你走我才留下。我留下仅当你走。当我留下你得走。
注意：在一 般的命题表述中，“仅当”是必要条件，译成条件命题时其后的命题是后件，
而“当”是充分条件，译成 条件命题时其后的命题是前件。
（2）仅当天不下雨且我有时间，我才上街。
设
P
：天下雨。
Q
：我有时间。
R
：我上街。命题符号化为：
R ?(?P?Q)
。
（3）你将失败，除非你努力。
这个命题的意义可以理解为：如果你不努力，那么你将失败。
设
P
：你努力 。
Q
：你失败。则命题符号化为：
?P?Q
。
含有“除非”的命题，“非…”是充分条件，译成条件命题时，“非…”是条件的前件。

（4）
A
中没有元素，
A
就是空集。
设< br>P
：
A
中有元素。
Q
：
A
是空集。则命题符 号化为：
?P?Q

（5）张三与李四是表兄弟。
此命题是一个原子命题， “…与…是表兄弟。”表示两个对象之间的关系。“张三是表兄
弟。”及“李四是表兄弟。”都不是命题 。所以上述命题只能符号化为
P
的形式。其中
P
：
张三与李四是表兄 弟。
例1.3.5 将下列命题符号化。
（1） 如果明天早上下雨或下雪，则我不去学校。
（2） 如果明天早上不下雨且不下雪，则我去学校。
（3） 如果明天早上不是雨夹雪，则我去学校。
（4） 当且仅当明天早上不下雨且不下雪时，我才去学校。
设
P
：明天早上下雨。
Q
：明天早上下雪。
R
：我去学校。
（1） 符号化为：
(P?Q)??R

（2） 符号化为：
(?P??Q)?R

（3） 符号化为：
?(P?Q)?R

（4） 符号化为：
?P??Q?R

例1.3.6 将下列命题符号化。
（1） 如果小王和小张都不去，则小李去。
（2） 如果小王和小张不都去，则小李去。
设
P
：小王去。
Q
：小张去。
R
：小李去。
（1） 符号化为：
(?P??Q)?R

（2） 符号化为：
?(P?Q)?R
或
(?P??Q)?R

例1.3.7 将下列命题符号化。
（1）说离散数学无用且枯燥无味是不对的。
（2）若天不下雨，我就上街；否则在家。
对于（1），设
P
：离散数学是 有用的。
Q
：离散数学是枯燥无味的。则命题符号化为：
?(?P?Q)
。
对于（2），设
P
：天下雨。
Q
：我上街。
R
：我 在家。则命题符号化为：
(?P?Q)?(P?R)
。
通过上述的例题可以看出， 要正确地将自然语言中的联结词翻译成恰当的逻辑联结词，
必须要正确地理解各原子命题之间的关系。

习题
1．判断下列各式子是否是命题公式
（1）
P?(Q?R)

（2）
(P?(Q?R))

（3）
(P?Q)?(?Q?R))

（4）
PQ?T

（5）
((R?(Q?R)?(P?Q))

（6）
（P?QR)?S

2．将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）
（1）我去新华书店
(P)
，仅当我有时间
(Q)
。
（2）我们不能既划船
(P)
又跑步
(Q)
。
（3）只要努力学习
(P)
，成绩就会好的
(Q)
。
（4）或者你没有给我写信
(P)
，或者它在路上丢了
(Q)
。 < br>（5）如果上午不下雨
(P)
，我就去看电影
(Q)
，否则我就在家里 读书
(R)
或看报纸
(S)
。
（6）我今天进城
(P)
，除非下雨
(Q)
。
（7）如果 太阳没出来
(P)
，则或者下雨
(Q)
或者阴天
(R)
而且 温度下降
(S)
。
（8）指南针永指南北
(P)
，除非它旁边有磁铁
(Q)
。
（9）说逻辑枯燥无味
(P)
和毫无价值
(Q)
是不对的。
（10）人不犯我
(P)
，我不犯人
(Q)
；人若犯我，我必犯人。

真值表与等价公式

1.4.1真值表
定义1.4.1 设
P
1
，
P
2
，…，
P
n
是出现在 命题公式
A
中的全部命题变元，给
P
1
，
P
2，…，
P
n
各指定一个真值，称为对公式
A
的一个赋值（或解释 或真值指派）。

若指定的一组值使公式
A
的真值为1，则这组值称为 公式
A
的成真赋值。
若指定的一组值使公式
A
的真值为0，则这组 值称为公式
A
的成假赋值。
例如，对公式
(P?Q)?R
，赋值0 11（即令
P?0,Q?1,R?1)
，则可得到公式的真
值为1；若赋值000，则 公式真值为0。因此，011为公式的一个成真赋值；000为公式的一
个成假赋值。除了上述的两种赋 值外，公式的赋值还有000，001，…等。一般的结论是在
含有n个命题变元的命题公式中，共有< br>2
n
种赋值。
定义1.4.2 将命题公式
A
在所有赋值下 的取值情况列成表，称为公式
A
的真值表(Truth
Table)。
构造真值表的基本步骤：
（1）找出公式中所有的命题变元
P
1
，
P
2
，…，
P
n
，按二进制从小到大的顺序列出
2
n
种赋值。
（2）当公式较为复杂时，按照运算的顺序列出各个子公式的真值。
（3）计算整个命题公式的真值。
例 写出下列公式的真值表，并求其成真赋值和成假赋值。
（1）
?P?Q

（2）
?(P?Q)?Q

（3）
?(P?Q)?(?P??Q)

解 （1）的真值表见表1-6。
表1-6
?P?Q
的真值表
P

Q

?P

?P?Q

0
0
1
1
0
1
0
1
1
1
0
0
1
1
0
1
成真赋值为00，01，11，成假赋值为10。
（2）的真值表见表1-7。

表1-7
?(P?Q)?Q
的真值表
P

Q

P?Q

?(P?Q)

?(P?Q)?Q

0
0
1
1

0
1
0
1
1
1
0
1
0
0
1
0
0
0
0
0

无成真赋值，成假赋值为00，01，10，11。
（3）的真值表见表1-8。
表1-8
?(P?Q)?(?P??Q)
的真值表
P

Q

P?Q

?(P?Q)

?P??Q

?(P?Q)?(?P??Q)

0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
1
1
0
1
1
1
1
成真赋值为00，01，10，11，无成假赋值。

1.4.2 等价公式

定义1.4.3 给定两个命题公式
A,B
，设
P
1，
P
2
，…，
P
n
是出现在命题公式
A,B< br>中的
全部命题变元，若给
P
1
，
P
2
，…，
P
n
任一组赋值，公式
A
和
B
的真值都对应相同， 则称
公式
A
与
B
等价或逻辑相等(Equivalence)，记作
A
?
B
。
需要注意的是，“
?
”不是逻辑联结词 ，因而“
A
?
B
”不是命题公式，只是表示两
个命题公式之间的一种 等价关系，即若
A
?
B
，
A
和
B
没有本质 上的区别，最多只是
A
和
B
具有不同的形式而已。
“
?< br>”具有如下的性质：（1）自反性：
A
?
A
。（2）对称性：若
A
?
B
，则
B
?
A
。
（3）传递性：若
A
?
B
，
B
?
C
，则
A
?
C
。
给定n个命题变元，根据公式的形成规则，可以形成许多个形式各异的公式， 但是有很
多形式不同的公式具有相同的真值表。因此引入公式等价的概念，其目的就是将复杂的公式简化。
下面介绍两种证明公式等价的方法。
1．真值表法
由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。
例1.4.2 证明
P?Q?(P?Q)?(Q?P)

证明 命题公式
P?Q
与
(P?Q)?(Q?P)
的真值表见表1-9。
由表1-9可知，在任意赋值下
P?Q
与
(P?Q)?(Q?P)
两者的真值 均对应相同。
因此
P?Q?(P?Q)?(Q?P)

表1-9
P?Q
与
(P?Q)?(Q?P)
的真值表
P

Q

P?Q

Q?P

(P?Q)?(Q?P)

P?Q

0
0
0
1
1
1
1
0
1
0
1
0

1
1
0
1
0
1
1
1
0
1
0
1
例1.4.3 判断公式
P?Q
与
?P??Q
二者是否等价。
证明 公式
P?Q
与
?P??Q
的真值表见表1-10。
表1-10
P?Q
与
?P??Q
的真值表
P

Q

P?Q

?P??Q

0
0
1
1
0
1
0
1
1
1
0
1
1
0
1
1
可见真值表中的最后两列值不完全相同，因此公式
P?Q
与
?P??Q
不等价。
从理论上来讲，利用真值表法可以判 断任何两个命题公式是否等价，但是真值表法并
不是一个非常好的方法，因为当公式中命题变元较多时， 其计算量较大，例如当公式中有四
个变元时，需要列出
2
=16种赋值情况，计算较为 繁杂。因此，通常采用其他的证明方法。
这种证明方法是先用真值表法验证出一些等价公式，再用这些等 价公式来推导出新的等价公
式，以此作为判断两个公式是否等价的基础。下面给出12组常用的等价公式 ，它们是进一
步推理的基础。牢记并熟练运用这些公式是学好数理逻辑的关键之一。
（1）双重否定律：
?
?A
?
A

（2）结合律：
(A?B)?C?A?(B?C)
，
(A?B)?C?A?(B?C)
，4
(A?B)?C?A?(B?C)

（3）交换律：
A?B?B?A< br>，
A?B?B?A
，
A?B?B?A

（4）分配律：
A?(B?C)?(A?B)?(A?C)
，
A?(B?C)?(A?B)?(A?C)
（5）幂等律：
A?A?A
，
A?A?A

（6）吸收律：
A?(A?B)?A
，
A?(A?B)?A

（7）德.摩根律：
?(A?B)??A??B
，
?(A?B)??A??B

（8）同一律：
A?F?A,A?T?A

（9）零律：
A?T?T,A?F?F

（10）否定律：
A??A?T,A??A?F

（11）条件等价式：
A?B??A?B??B??A

（12）双条件等价式：
A?B?(A?B)?(B?A)??A??B

上述12组公式均可以通过构造真值表法来证明。
2．等值演算法
定理1.4.1 （代入规则）在一个永真式
A
中，任何一个原子命题变元
R
出现的每一处用< br>另一个公式代入，所得的公式
B
仍为永真式。
证明：因为永真式对于任何指派 ，其真值都是1，与每个命题变元指派的真假无关，所
以，用一个命题公式代入到原子命题变元
R
出现的每一处，所得到的命题公式的真值仍为1。
例如，
R??R
是永真 式，将原子命题变元
R
用
P?Q
代入后得到的式子
(P?Q)??( P?Q)
仍为永真式。
定理1.4.2（置换规则） 设
X
是命题公式A
的一个子公式，若
X?Y
，如果将公式
A
中的
X用
Y
来置换，则所得到的公式
B
与公式
A
等价，即A?B
。
证明：因为
X?Y
，所以在相应变元的任一种指派情况下，< br>X
与
Y
的真值相同，故
以
Y
取代
X
后，公式
B
与公式
A
在相应的指派情况下真值也必相同，因此
A?B
。
例如
P?Q??P?Q
，利用
R?S
置换
P< br>，则
(R?S)?Q??(R?S)?Q
。
从定理可以看出，代入规则是对原 子命题变元而言，而置换规则可对命题公式进行；
代入必须处处代入，替换可以部分或全部替换；代入规 则可以用来扩大永真式的个数，替换
规则可以增加等价式的个数。
有了上述的12组等价公式 及代入规则和置换规则后，就可以推演出更多的等价式。由
已知等价式推出另外一些等价式的过程称为等 值演算(Equivalent Calculation)。
例 证明下列公式等价。
（1）
(P?Q)?R
?
P?(Q?R)

（2）
(P??Q)?(?P?Q)?(P?Q)??(P?Q)

证明 （1）
(P?Q)?R
?
?(P?Q)?R


?
?P??Q?R


??P?(?Q?R)


??P?(Q?R)


?P?(Q?R)

（2）
(P??Q)?(?P?Q)?((P??Q)? ?P)?((P??Q)?Q)


?(P??P)?(?Q??P)?(P?Q)?(?Q?Q)


?1?(?Q??P)?(P?Q)?1

?(P?Q)?(?P??Q)


?(P?Q)??(P?Q)

例1.4.5 某件事情是甲、乙、丙、丁4人中某一 个人干的。询问4人后回答如下：（1）
甲说是丙干的；（2）乙说我没干；（3）丙说甲讲的不符合事 实；（4）丁说是甲干的。若其中
3人说的是真话，一人说假话，问是谁干的？
解 设A
：这件事是甲干的。
B
：这件事是乙干的。
C
：这件事是丙干 的。
D
：这
件事是丁干的。
4个人所说的命题分别用
P
、
Q
、
R
、
S
表示，则（1）、（2）、（3）、（4）分别 符号化
为：
P
??A??B?C??D
；
Q
??B
；
R
??C
；
S?A??B??C??D

则3人说真话，一人说假话的命题
K
符号化为：
K
?(?P?Q? R?S)?(P??Q?R?S)?(P?Q??R?S)?(P?Q?R??S)

其中
?P?Q?R?S?(A?B??C?D)??B??C?A??D

?(A??B??C?D)?(B??B??C?A??D)

?(?C??B??C?A??D)?(D??B??C?A??D)

?A??B??C??D

同理
P??Q?R?S?P?Q??R?S?P?Q?R??S
?0

所以，当
K
为真时，
A??B??C??D
为真，即这件事是甲干的。 < br>本题也可以从题干直接找出相互矛盾的两个命题作为解题的突破口。甲、丙两人所说
的话是相互矛 盾的，必有一人说真话，一人说假话，而4个人中只有一人说假话，因此乙、
丁两人必说真话，由此可断 定这件事是甲干的。
例1.4.6 在某次球赛中，3位球迷甲、乙、丙对某球队的比赛结果进行猜 测。甲说：
该球队不会得第一名，是第二名。乙说：该球队不会得第二名，是第一名。丙说：该球队不< br>会得第二名，也不会是第三名。比赛结束后，结果证实甲、乙、丙3人中有一人猜的全对，
有一人 猜对一半，有一人猜的全错。试分析该球队究竟是第几名。
解 设
P
：该球队获得 第一名。
Q
：该球队获得第二名。
R
：该球队获得第三名。则
P、
Q
、
R
中必然有一个真命题，两个假命题。
设甲、乙、丙3 人所说的命题分别用
A
1
，
A
2
，
A
3< br>表示。则有
A
1
??P?Q
，
A
2
?P?? Q
，
A
3
??Q??R
。
设甲、乙、丙的判断全对分别用
B
1
、
C
1
、
D
1
表示，甲、乙 、丙的判断对一半分别用
B
2
、
C
2
、
D
2
表示，甲、乙、丙的判断全错分别用
B
3
、
C
3
、
D
3
表示。则有：

B
1
??P?Q
。
B
2
?(?P ??Q)?(P?Q)??P??Q
（由于该球队不可能既是第一名又是第二
名，所以
P?Q?0
）。
B
3
?P??Q
。
C
1
?P??Q
。
C
2
?(P?Q)?(?P??Q)??P??Q
。
C
3
??P?Q
。
D
1
??Q??R
。
D
2
?(?Q?R)?(Q??R)
。
D
3
?Q?R
?0
。
甲、乙、丙3人中有一人全对，有 一人猜对一半，有一人全错的命题
K
符号化为
K?(B
1
?C
2
?D
3
)?(B
1
?C
3
?D
2)?(B
2
?C
1
?D
3
)
?
(B< br>2
?C
3
?D
1
)
?

(B
3
?C
1
?D
2
)
?
(B
3?C
2
?D
1
)

其中，
B
1
?C
2
?D
3
?(?P?Q)?(?P??Q)?0?0
。 同理，
B
2
?C
1
?D
3
?0
，B
2
?C
3
?D
1
?0
，
B
3
?C
1
?D
2
?(P??Q)?((?Q?R)?(Q??R) )


?(P??Q?R)?(P??Q?Q??R)

，
?P??Q?R?0< br>（由于该球队不可能既是第一名，又是第三名）
B
3
?C
2
? D
1
?0
。
因此，若
K
为真，只有
B
1
?C
3
?D
2
??P?Q??R
为真。因而
Q为真命题，
P,R
为假命题。即该球队获得第二名。甲的判断全对，乙的判断全错，丙的判 断对一半。
例1.4.7
A
、
B
、
C
、
D
4人进行百米竞赛，观 众甲、乙、丙对比赛的结果进行预
测。甲：
C
第一，
B
第二；乙：< br>C
第二，
D
第三；丙：
A
第二，
D
第四。比 赛结束后发现
甲、乙、丙每个人的预测结果都各对一半。试问实际名次如何（假如无并列者）？
解 设
A
i
表示
A
第
i
名，
B
i
表示
B
第
i
名，
C
i
表示C
第
i
名，
D
i
表示
D
第
i
名，

i?1,2,3,4
。
则由题意有

(C
1
??B
2
)?(?C
1
?B
2)?T
（1）

(C
2
??D
3
)?(?C
2
?D
3
)?T
（2）

(A
2
??D
4
)?(?A
2
?D
4
)?T
（3）
因为真命题的合取仍为真命题，所以
（1）
?
（2）
?(C1
??B
2
?C
2
??D
3
)?(C
1
??B
2
??C
2
?D
3
)?(?C
1
?B
2
?C
2
??D
3
)?


(?C
1
?B
2
??C
2
?D
3
)

?
(
C
1
??B
2
??C
2
?D
3
)?(?C
1
?B
2
??C
2
?D
3
)
（4）
（3）
?
（4）
?
(A
2
??D
4?C
1
??B
2
??C
2
?D
3
)? (?A
2
?D
4
?C
1
??B
2
??C< br>2
?D
3
)?


(A
2
? ?D
4
??C
1
?B
2
??C
2
?D3
)?(?A
2
?D
4
??C
1
?B
2
??C
2
?D
3
)

?
A
2< br>??D
4
?C
1
??B
2
??C
2
?D
3
?T

因此，
A
第二，
B
第四，< br>C
第一，
D
第三。

习题
1．写出下列公式的真值表。
（1）
P?(Q?R)

（2）
P?(Q?R)

（3）
(?P?Q)?(P??Q)

（4）
(P?Q)?(?P??Q)

2．证明下列等价公式。
（1）
P?(Q?R)?Q?(P?R)

（2）
(P?Q)??(P?Q)??(P?Q)

（3）
A?(B?C)?(A??B)?C

（4）
(P?Q)?(P?R)?P?(Q?R)

3．甲、 乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说：不是我。乙说：是
丁。丙说：是乙。丁说 ：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是
谁？
4．3个球迷估计 比赛结果，球迷甲说：大连实德第一，北京国安第二。球迷乙说：上海申
花第二，长春亚泰第四。球迷丙 说：大连实德第二，长春亚泰第四。结果3人估计的都不全
对，但都对了一半，问4支球队的名次（假设 无并列次序）。
5．如果
A?C?B?C
，是否有
A?B
？如果< br>A?C?B?C
，是否有
A?B
？如
果
?A??B
， 是否有
A?B
？
6．化简下列公式：
（1）
((P?Q)?(?Q??P))?R

（2）
P?(?P?(Q??Q))
（3）
(P?(Q?S))?(?P?(Q?S))


命题公式的分类与蕴含式

1.5.1 命题公式的分类

从前述的真 值表中可以看到，有的命题公式无论对命题欧变元作何种赋值，其对应的
真值恒为
T
或 恒为
F
，如例1.4.1的（2）、（3）；而有的公式对应的真值则是有
T
有
F
，如
例的（1）。
根据命题公式在不同赋值下的真值情况，可以对命题公式进行分类。
定义1.5.1 设
A
为一命题公式，对公式
A
所有可能的赋值：
（1）若
A
的真值永为
T
，则称公式
A
为重言式(Tautology)或永 真式。
（2）若
A
的真值永为
F
，则称公式
A
为 矛盾式(Contradictory)或永假式。
（3）若至少存在一种赋值使得
A
的真值为
T
，则称公式
A
为可满足式(Satisfiable)。 由定义可知，根据命题公式的真值情况，公式可分为两大类，即矛盾式和可满足式。
重言式一定是可 满足式，但反之不成立。
用真值表法可以判定公式的类型：若真值表的最后一列全为1，则公式为重言 式；若最
后一列全为0，则公式为矛盾式；若最后一列至少有一个1，则公式为可满足式。在的例1.4 .1
中，（1）为可满足式，（2）为矛盾式，（3）为重言式。用真值表法判断公式的类型方法简单，
但当变元较多时，计算量大，在后面的章节中还要介绍其他的方法。

1.5.2 重言式与矛盾式的性质

定理1.5.1 任何两个重言式的析取或合取，仍是一个重言式。
证明：设
A
、
B
为两个重言式，则无论对
A
与B
的分量作何种指派，总有
A?T
，
B?T
，故
A?B ?T
，
A?B?T
。
定理1.5.2 一个重言式，对同一分量用任何合式公式置换，所得公式仍为一重言式。
证明：因为重言式的真值与分 量的指派无关，所以对同一分量用任何合式公式置换后，
重言式的真值仍永为真。
例如，P??P
为一重言式，用
Q?R
置换
P
，所得新公式
( Q?R)??(Q?R)
仍为
重言式。

对于矛盾式，也有类似于定理1.5.1和定理的结果。
定理1.5.3 设
A
、
B
为两个命题公式，
A?B
当且仅当
A?B< br>为重言式。
证明：若
A?B
，则在
A
、
B
所含命题变元的任何指派下，
A
与
B
的真值都相同，
即
A? B
恒为真。
若
A?B
为重言式，由重言式的定义知，在对
A
、
B
所含命题变元的任何指派下，
A
与
B
都有相同的真值 ，即
A?B
。
例1.5.1 证明
(P?Q)?((P?Q)?(Q?P))
为重言式。
证明 由例1.4.2 知
P?Q?(P?Q)?(Q?P)
，故依据定理有
(P?Q)?((P?Q)?(Q ?P))
为重言式。
1.5.3 蕴含式
下面讨论
A?B
的重言式。
定义1.5.2 设
A
、B
为两个命题公式，若
A?B
为重言式，则称“
A
蕴含
( Implication)
B
”，记作
A?B
。
注意“
?
”与“
?
”一样，都不是逻辑联结词，因而
A?B
也不是公式。
A?B
是
用来表示由条件
A
能够推导出结论
B
，或 称为
B
可以由
A
逻辑推出。
蕴含关系具有如下的性质：
（1）自反性：对任意的公式
P
，有
P?P
。
（2）反对 称性：对任意的公式
P
、
Q
，若
P?Q
且
Q?P< br>，则有
P?Q
。
（3）传递性：对任意的公式
P
、
Q
、
R
，若
P?Q
、
Q?R
，则有
P?R
。
由于
A?B
不具有对称性，即
A?B
与
B?A
不等价，因此，对于
A?B
而言，
B?A
称为它的逆换式，
?A??B
称为它的反换式，
?B??A
称为它的逆反式。在上
述的4个公式 中，
A?B
?
?B??A
，
B?A
?
?A??B< br>。
定理1.5.4
A?B
的充分必要条件是
A?B
且
B?A
。
证明 ：若
A?B
，则
A?B
为重言式，而
A?B
?(A?B)? (B?A)
，故
A?B且B?A
均为重言式，即
A?B
且
B ?A
。
反之，若
A?B
且
B?A
，则
A?B且B ?A
均为重言式，于是
(A?B)?(B?A)
为重言式，即
A?B
为重言式，故
A?B
。
由定义1.5.2知，要证明
A?B
，只需 证明
A?B
为重言式即可。因此，前面介绍的
真值表法和等值演算法均可应用。
下面综合介绍证明
A?B
的各种方法。
1．真值表法
例1.5.2 证明
A?B?A

证明 只需证明
A?B?A
为重言式。真值表见表1-11。
A?B?A
的真值表
A

B

A?B

A?B?A

表1-11
0
0
0
1
0
0
1
1

1
1
2．等值演算法
例1.5.3 证明
0
1
0
1
1
1
P?(P?Q)?Q

证明 只需证明
P?(P?Q)?Q
为重言式。
P?(P?Q)?Q??(P?(?P?Q))?Q


??P??(?P?Q)?Q


?(?P?Q)??(?P?Q)


?1

即
P?(P?Q)?Q

3．分析法
分析法包括以下两种形式：
（1）假定前件
A
为真，推出后件
B< br>为真，则
A?B
。
（2）假定后件
B
为假，推出前件
A
为假，则
A?B
。
理由是：（1）若
A
为真，则B
可能为真也可能为假，但由假设推出
B
为真，所以否定
了
A< br>为真、
B
为假的可能，只能是
A
为真、
B
也为真。所 以
A?B
为重言式，即
A?B
。
对于（2），若后件
B< br>为假，则前件
A
可能为真也可能为假。若
A
为真，则
A?B< br>B
为假，
为假；若
A
为假，
B
为假，则
A? B
为真。而由假设推知
A
为假，因此否定了
A
为真，
B为假的可能。所以
A?B
为重言式，即
A?B
。
例1.5.4 证明（1）
?Q?(P?Q)?P

（2）
P?(P?Q)?Q

证明 （1）假设前件
?Q?(P?Q)
为真，则
?Q
为真，P?Q
为真；由此有
Q
为假，
P
为真。因此
?Q?(P ?Q)?P
。
（2）假设后件
Q
为假，
若
P
为 真，则
P?Q
为假，有
P?(P?Q)
为假。
若
P
为假，则
P?Q
为真，有
P?(P?Q)
为假。
综上，若后件< br>Q
为假，无论
P
为真还是假，前件
P?(P?Q)
均为假。因 此
P?(P?Q)?Q
。
需要指出的是，在例1.5.4的（2）中，因为不知道< br>P
的真值情况，所以要分情况讨论。

例 分析下列论证的有效性。
条件：香烟有利于健康；
如果香烟有利于健康，那么医生就会把香烟作为药品开给病人。
结论：医生把香烟作为药品开给病人。
解 设
P
：香烟有利于健康。
Q
：医生把香烟作为药品开给病人。
上述推理符号化为：
P?(P?Q)?Q
。
其证明同例1.5.4的（2）。因此上述论证是有效的。
下面给出的蕴含式其正确性均可用上述的推理方法进行证明。
（1）
P?Q?P

（2）
P?Q?Q

（3）
P?P?Q

（4）
?P?P?Q

（5）
Q?P?Q

（6）
?(P?Q)?P

（7）
?(P?Q)??Q

（8）
P?(P?Q)?Q

（9）
?Q?(P?Q)??P

（10）
?P?(P?Q)?Q

（11）
(P?Q)?(Q?R)?P?R

（12）
(P?Q)?(P?R)?(Q?R)?R

（13）
(P?Q)?(R?S)?(P?R)?(Q?S)

（14）
(P?Q)?(Q?R)?P?R



习题
1．判断下列命题公式的类型。
（1）
(P?Q)?(P?Q)
。

（2）
(P?Q?R)?(P??R?Q)
。
（3）
?P?(P?Q)
。
（4）
(?P?Q)??(P?Q)
。
2．证明下列各蕴含式。
（1）
(P?Q)?P?(P?Q)

（2）
(P?Q)?Q?P?Q

（3）
P?(Q?R)?(P?Q)?(P?R)

（4）
((P??P)?Q)?((P??P)?R)?Q?R

3．判断下列命题的真假。
（1）重言式的否定是矛盾式。
（2）矛盾式的否定是重言式。
（3）不是重言式就是矛盾式。
（4）不是矛盾式就是重言式。
（5）重言式必是可满足式。
（6）不是矛盾式就是可满足式。
（7）可满足式未必是重言式。
（8）不是可满足式就是矛盾式。
4．设P表示命题“8是偶数”，Q表示命题“糖果是甜的”。试以句子写出：
（1）
P?Q
。
（2）
P?Q
的逆换式。
（3）
P?Q
的反换式。
（4）
P?Q
的逆反式。
5．叙述下列各个命题的逆换式和逆反式，并以符号写出。
（1）如果下雨，我不去。
（2）仅当你走我将留下。
（3）如果我不能获得更多帮助，我不能完成这个任务。
6．检验下列论证的有效性。
如果我学习，那么我数学不会不及格。
如果我不热衷于玩扑克，那么我将学习。
但我数学不及格。
因此，我热衷于玩扑克。
7．用符号写出下列各式并且验证论证的有效性。
如果6是偶数，则7被2除不尽。

或5 不是素数，或7被2除尽。
但5是素数。
所以6是奇数。
8．证明
P?Q
，Q逻辑蕴含P。

其它逻辑联结词和最小功能完备联结词组

1.6.1 其它逻辑联结词

前面介绍了5种常用的逻辑联结词
?
，
?，
?
，
?
和
?
，但是这5种联结词还不能
很广 泛地直接用来表达命题间的联系，为此，下面再介绍4种联结词。
1．不可兼析取(排斥或异或)(exclusive or)（
?
）
定义1.6.1 设
P
、
Q
为两个命题公式，复合命题
P? Q
称为
P
异或
Q
。规定
P?Q
的真
值为< br>T
，当且仅当
P
与
Q
的真值不相同，否则
P?Q的真值为
F
。
联结词“
?
”的定义见表1-12。
表1-12 联结词“
?
”的定义
P

Q

P?Q

0
0
1
1
0
1
0
1
0
1
1
0
从真值表中易见，
P?Q
?(P??Q)?(?P?Q)
。
利用真值表法，易证“
?
”具有如下性质：
（1）
P?Q?Q?P

（2）（
P?Q
）
?
R
?P?(Q?R)

（3）
P?(Q?R)?(P?Q)?(P?R)

（4）
P?Q
??(P?Q)

（5）
P?P?F
；
F?P?P
；
T?P??P

（6）若
P?Q
?R
，则
P?R?Q
，Q?R?P
，且
P?Q?R
为一矛盾式。
2．与非联结词(Nand)(
?
)
定义1.6.2 设
P< br>、
Q
为两个命题公式，复合命题
P?Q
称为
P
和Q
的“与非式”。当
且仅当
P
与
Q
的真值都为
T
时，
P?Q
的真值为
F
，否则
P?Q
的真值为< br>T
。
联结词“
?
”的定义见表1-13。
表1-13 联结词“
?
”的定义
P

Q

P?Q

0
0
1
1
0
1
0
1
1
1
1
0
从真值表中易见，
P?Q
??(P?Q)
。
联结词“
?
”具有如下性质：
（1）
P?P??(P?P)??P

（2）
(P?Q)?(P?Q)??(P?Q)?P?Q

（3）
(P?P)?(Q?Q)??P??Q??(?P??Q)?P?Q

3．或非联结词(Nor)（
?
）
定义1.6.3 设
P
、
Q
为两个命题公式，复合命题
P?Q
称为
P
和
Q
的“或非式”。当
且仅当
P
与
Q
的真值都为
F时，
P?Q
的真值为
T
，否则
P?Q
的真值为
F
。
联结词“
?
”的定义见表1-14。
表1-14 联结词“
?
”的定义
P

Q

P?Q

0
0
1
1
0
1
0
1
1
0
0
0

从真值表中易见，
P?Q
??(P?Q)
。
联结词“
?
”具有如下性质：
（1）
P?P??(P?P)??P

（2）
(P?Q)?(P?Q)??(P?Q)??(?(P?Q))?P?Q

（3）
(P?P)?(Q?Q)??P??Q??(?P??Q)?P?Q

4．条件否定联结词(Non-conditional)（
???
）
c
??Q
称为
P
和
Q
的定义1.6.4 设
P
、
Q
为两个命题公式，复合命题
P?
“条件否定”。
? ?Q
的真值为
T
，否则
P???Q
的真当且仅当
P
的真值为
T
，
Q
的真值为
F
时，
P?
值为
F
。
cc
c
??
”的定义见表1-15。 联结词“
?
??
”的定义 表1-15 联结词“
?
c
??Q

P

Q

P?
c
c
0
0
1
1
c
0
1
0
1
0
0
1
0
??Q
??(P?Q)
。 从真值表中易见，
P?
1.6.2 最小功能完备联结词组
到目前为止，共定义了9个联结词，但这些联结词在表达命题时并不是缺一不可 ，因
为包含某些联结词的公式可以用含有另外一些联结词的公式来进行表示。如
P?Q?(P?Q)?(Q?P)

P?Q??P?Q

P?Q??(?P??Q)

P?Q??(?P??Q)

这说明“
?
”可以转化为“
?
”，而“
?
”可转化为由“
?
”与“
?
”表示，而“
?
”
与“
?
”又可 以相互转化。
对于另外的4个联结词，由于
P?Q??(P?Q)
，
P?Q
??(P?Q)
，

c
P?Q
??(P?Q)
，
P???Q
??(P?Q)
，这说明任意的一个命题公式最终都可以
转化为 仅包含
?
?
，
?
?
或
?
?
，?
?
的命题公式来等价地表示。
定义1.6.5 设
G
是一个 联结词的集合，若任意一个命题公式都可用
G
中联结词构成的
公式来表示，则称
G
为功能完备联结词组。如果在
G
中去掉任何一个联结词后都不再具有
这种 性质，则称
G
为最小功能完备联结词组，简称为最小联结词组。
可以证明
?
?
，
?
，
?
?
，
?
?
，
?
?
，
?
?
，
?
?
，
?
?
，
?
?
等都是功能完备联结词组，
而
?
?
，
?
?
，
?
?
，
?
?
及
?
?
，
?
?
均为最小功能完备联结词组。由联结词“?
”
及“
?
”的性质知，联结词“
?
”、“
?
”和“
?
”可分别用“
?
” 或“
?
”表示，所以
?
及
?
也是最小功能完备联结词组。
通常为了命题表示的简洁清楚，常用包含
?
?
，
?
，
?
?
的联结词组来表示命题。

??
??
习题
1．将下列命题公式转化为仅含联结词
?
的命题公式。
（1）
?P

（2）
P?Q

（3）
P?Q

2．将下列命题公式用只含
?
和
?
的等价式表达，并要求尽可能简单。
（1）
(P?Q)??P

（2）
(P?(Q??R))??P?Q

（3）
?P??Q?(?R?P)

3．证明
{?},{?},{?}
不是最小功能完备连接词组。
4．证明
{?,?}
是最小功能完备连接词组。

对偶与范式

1.7.1对偶式与对偶原理

1．对偶式
定义1.7.1 在只含有逻辑联结词
?
，
?
，
?
的命题公式
A
中，若把
?
与
?
互换，
T
与
F
互换得到一个新的命题公式
A
*
，则称
A
*是
A
的对偶式(Dualistic Formula)，或称
A
*
与
A
互
为对偶式。
显然
(A)?A
。
例 写出下列公式的对偶式。
（1）
(P?Q)?R

（2）
(P?Q)?T

（3）
?(P?Q)?(P??(Q??S))

解 上述公式的对偶式为
（1）
(P?Q)?R

（2）
(P?Q)?F

（3）
?(P?Q)?(P??(Q??S))

例1.7.2 求
P?Q
，
P?Q
的对偶式。
解 因为
P?Q
??(P?Q)
，
所以
P?Q
的对偶式为
?(P?Q)?P?Q
。
同理，
P?Q
的对偶式为
P?Q
。
2．对偶原理(Duality Principle)
一个仅含有逻辑联结词?
，
?
，
?
的命题公式和它的对偶式之间具有如下等值关系：
定理1.7.1 设公式
A
为仅含有逻辑联结词
?
，
?，
?
及命题变元
P
1
，
P
2
，…，< br>P
n
的命
题公式，
A
是
A
的对偶式，则有：
*
（1）
?A(P
1
,P
2
,...,P
n
)?A(?P
1
,?P
2
,...,?P
n
)< br>
*
（2）
A(?P
1
,?P
2
,..., ?P
n
)??A(P
1
,P
2
,...,P
n)

**
*
证明：由德.摩根定律
P?Q??(?P??Q)
，
P?Q??(?P??Q)

*
故
?A(P
1
,P
2
,...,P
n
)?A(? P
1
,?P
2
,...,?P
n
)

*
同理
A(?P
1
,?P
2
,...,?Pn
)??A(P
1
,P
2
,...,P
n
)< br>
例1.7.3 设
A(P,Q,R)??P?(?Q?R)
，证明
A(?P,?Q,?R)??A(P,Q,R)

证明 因为
A(P,Q, R)??P?(?Q?R)
，所以
*
**
A
*
(?P,?Q ,?R)?P?(Q??R)
，
而
?A(P,Q,R)??(?P?(?Q?R))?P?(Q??R)

所以
A(?P,?Q,?R)??A(P,Q,R)

定理1.7.2（对偶原理）若公式
A
?B
，则
A?B
。
证明：设
P
1
，
P
2
，…，
P
n
是出现在命题公式
A
，
B
中所有的命题变元，因为
A
?B
，
即
A(P
1
,P
2
,...,P
n
)?B(P
1
,P
2
,...,P
n
)
，
所以
?A(P
1
,P
2
,...,P
n
)??B(P
1
,P
2
,...,P
n
)
。 < br>**
由定理1.7.1得，
A(?P
1
,?P
2
,. ..,?P
n
)?B(?P
1
,?P
2
,...,?Pn
)

**
即
A(?P
1
,?P
2< br>,...,?P
n
)?B(?P
1
,?P
2
,... ,?P
n
)
为重言式
**
故
A(P
1
, P
2
,...,P
n
)?B(P
1
,P
2
,...,P
n
)
也为重言式
*
**
即
A?B

对偶定律表明，利用公式的对偶式可以扩 大等价式的数量，也可以简化证明。例如
**
P?(Q?R)?(P?Q)?(P?R)
与
P?(Q?R)?(P?Q)?(P?R)
这两个等价公式
的两端互为对偶式，因 而只需证明一个等价公式成立即可。

1.7.2命题公式的范式

从前 面的讨论可知,存在大量互不相同的命题公式，实际上互为等价，因此，有必要引
入命题公式的标准形式 ，使得相互等价的命题公式具有相同的标准形式。这无疑对判别两个
命题公式是否等价以及判定命题公式 的类型是一种好方法，同时对命题公式的简化和推证也
是十分有益的。
1．简单析取式与简单合取式
定义1.7.2 单个的命题变元及其否定形式称为文字。如
P
，
?Q
等。
定义1.7.3 仅由有限个文字组成的析取式称为简单析取式。仅由有限个文字组成的合取
式称为简单合取式。

例如
?P?Q
，
P??Q?R
，
?P
，< br>Q
等都是简单析取式；
P?Q
，
?P?Q?R
，
?P
，
Q
等都是简单合取式。
一个文字既是简单析取式，又是简单合取式。
定理1.7.3 简单析取式是重言式当且仅当它同时含有某个命题变元及其否定形式。
证明 ：设公式
A
为简单析取式，含有命题变元
P
1
,P
2
,...,P
n
。
若
A
同时含有
P
i
及
?P
i
，显然
A
为重言式。
若
A
为重 言式但不同时含有某个命题变元及其否定形式，不妨设
A?P
1
?P
2
?...?P
i
??P
i?1
?...??P
n
，若P
1
,P
2
,...,P
i
真值均为0，而
P
i?1
,...,P
n
真值均
为1，则
A
的真值为 0，这与
A
为重言式矛盾。
对于简单合取式也有类似的性质。
定理1.7.4 简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定形式。
证明同定理1.7.3。
2．析取范式与合取范式
定义1.7.4 由有限个简单合取式组成的析取式称为析取范式（Disjunctive Normal
Form）。由有限个简单析取式组成的合取式称为合取范式（Conjunctive Normal Form）。析取
范式与合取范式统称为范式。
例如，
(P?Q)?(P??Q?R )
，
P?Q
等是析取范式。
(P?Q)?(P??Q?R)
，
P?Q
等是合取范式。
对于单独的一个命题变元
P
或其否定
?P
既可以看成是析取范式，又可看成是合取范
式。当然既可以看成是简单析取式，又可以看成是简 单合取式。至于
P?Q
，若把它看作为
简单合取式的析取，则它是析取范式；若把它看 成是文字的析取，则它是合取范式。同理，
P??Q
，
P?Q
等既是析取范式 ，又是合取范式。
定理1.7.5（范式存在定理）任何一个命题公式都存在着与之等价的析取范式和合取范
式。
从析取范式和合取范式的定义可知，范式中不存在除了
?
，
?
，?
以外的其余逻辑联
结词。
下面给出求公式范式的步骤：
（1）消去 除
?
，
?
，
?
以外公式中出现的所有逻辑联结词。
（2）将否定联结词消去或内移到各命题变元之前。
如，
??A?B?A?B??A?B
；
?(A?B)??A??B
；
?(A?B)??A??B
。

（3）利用分配律、结合律将公式转化为合取范式或析取范式。
如，
P?(Q?R)?(P?Q)?(P?R)
；
P?(Q?R)?(P?Q)?(P?R)
。
例1.7.4 求
(P?Q)?R
的析取范式和合取范式。
解
(P?Q)?R

?(?P?Q)?R??(?P?Q)?R?(P??Q)?R
（析取范式）
?(P?R)?(?Q?R)
（合取范式）
例1.7.5 求
?(P?Q)?(P?Q)
的析取范式。
解
?(P?Q)?(P?Q )?(?(P?Q)?(P?Q))?(??(P?Q)?(?(P?Q))

?(?P??Q?P?Q)?((P?Q)?(?P??Q))

?(?P??Q?P?Q)?(P??P)?(P??Q)?(Q??P)?(Q??Q)

?(P??Q)?(?P?Q)

上面所求的最后两个等价的公式都是原公式的析取范式，所以命题公式的析取范式不
唯一。
例1.7.6 求
?(P?Q)?(P?Q)
的合取范式。
解
?(P?Q)?(P?Q)?(??(P?Q)?(P?Q))?(?(P?Q)??(P?Q))

?((P?Q)?(P?Q))?((?P??Q)?(?P??Q))

?(P?Q?P)?(P?Q?Q)?(?P??P??Q)?(?Q??P??Q)

?(P?Q)?(?P??Q)

上面所求的最后两个等价的公式都是原公式的合取范式，所以命题公式的合取范式不
唯一。
3．范式的应用
利用范式判断命题公式类型的问题称为判定问题。
定理1.7.6 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取
范式是重言式当且仅当它的每 个简单析取式都是重言式。
例1.7.7 判断下列公式的类型。
（1）
?(P?Q)?Q

（2）
P?(Q?R)??(P?R)

解 （1）
?(P?Q)?Q??(?P?Q)?Q?P??Q?Q

由定理1.7.6可知，
?(P?Q)?Q
为矛盾式。
（2）
P?(Q?R)??(P?R)?P??Q?R?(?P??R)


?(P??Q?R??P)?(P??Q?R??R)

由定理1.7.6可知，
P?(Q?R)??(P?R)
为重言式。

1.7.3命题公式的主析取范式和主合取范式

由于一个命题公式的范式不唯一， 这就使得范式的应用受到了一定的限制，为了使任意
命题公式化为唯一的标准形式，下面引入主范式的概 念。
1．主析取范式
定义1.7.5 在含有n个命题变元的简单合取式中，若每个命题变 元及其否定不同时出
现，而二者之一必出现且仅出现一次，则称该简单合取式为小项。
例如， 两个命题变元
P
和
Q
生成的4个小项为：
P?Q
，
P??Q
，
?P?Q
，
?P??Q
。三个命题变元
P
，
Q
和
R
生成的8个小项为：
P?Q?R
，
P? Q??R
，
P??Q?R
，
P??Q??R
，
?P?Q?R
，
?P?Q??R
，
?P??Q?R
，
?P??Q??R< br>。
一般说来，n个命题变元共有
2
个小项。
小项的二进制编码为 ：命题变元按字母顺序排列，命题变元与1对应，命题变元的否
定与0对应，则得到小项的二进制编码， 记为m
i
,其下标
i
是由二进制编码转化的十进制数。
n个命题变元 形成的
2
个小项，分别记为：
n
n
m
0
，
m
1
，…，
m
2
n
?1
。
表1-16列出了两个命题变元
P
和
Q
生成的4个小项的真值表。
表1-16 两个命题变元
P
和
Q
生成的4个小项的真值表
m
（二进制）
m
00

m
01

m
10

m
11

P

0
0
Q

?P??Q

?P?Q

P??Q

P?Q

0
1
1
0
0
1
0
0
0
0

1
1
0
1

0
0
0
0
1
0
0
1
m
（十进制）
m
0

m
1

m
2

m
3

从这个真值表中可以看到，没有两个小项是等价的，且每个小项都只对 应着
P
和
Q
的
一组真值指派使得该小项的真值为1。
这个结论可以推广到3个及3个以上变元的情况。
由真值表可得到小项具有如下性质：
（1）各小项的真值表都不相同。
（2）每个小项当其真值指派与对应的二进制编码相同时， 其真值为真，在其余
2
n
?1
种指派情况下，其真值均为假。
（3 ）任意两个小项的合取式是矛盾式。例如
m
00
?
m
10
=
(?P??Q)?(P??Q)??P??Q?P??Q?0

（4）全体小项的析取式为永真式。
定义1.7.6 由若干个不同的小项组成的析取式称为主析取范式(The Principal
Disjunctive Normal Form )。与公式
A
等价的主析取范式称为
A
的主析取范式。
定理1.7.7 任意含
n
个命题变元的非永假式命题公式都存在着与之等价的主析取 范式，
并且其主析取范式是唯一的。
证明：设
A
'
是公式
A
的析取范式，即
A?A
。若
A
'
的某个简单合取式
A
i
中不含有
命题变元
P
及其否定
?P
，将A
i
展成形式
'
A
i
?
A
i
?T
?
A
i
?(P??P)?(A
i
?P)?(A
i
??P)
，继续这个过程，直到所有的
简单合取式成为小项。然后消去重复的项及矛 盾式后，得到公式
A
的主析取范式。
下证唯一性。
若公式
A有两个与之等价的主析取范式
B
和
C
，则
B?C
。由于
B
和
C
是
A
的不同
的主析取范式，不妨设小项m
i
只出现在
B
中而不在
C
中，于是
i
的二进制表示为
B
的成真
赋值、
C
的成假赋值，这与
B? C
矛盾。因而公式
A
的主析取范式是唯一的。
一个命题公式的主析取范式可 通过两种方法求得，一是由公式的真值表得出，即真值表
法；另一是由基本等价公式推出，即等值演算法 。
（1）真值表法
定理1.7.8 在真值表中，命题公式
A
的真值为真 的赋值所对应的小项的析取即为命题
公式
A
的主析取范式。
证明：设命题 公式
A
的真值为真的赋值所对应的小项为
m
1
，
m
2
，…，
m
k
。令
B
=
m
1
?m
2
?
…
?m
k
。下证
A?B
，即证
A
与
B
在相应指派下具有相同的真值。
首先，对
A
为真 的某一指派，其对应的小项为
m
i
，则因为
m
i
为
T
，而
m
1
，
m
2
，…，

m
i?1
，
m
i?1
，…，
m
k
均为F
，所以
B
=
m
1
?m
2
?
…
?m
k
为真。
其次，对
A
为假的某一指派，则其赋值所 对应的小项一定不是
m
1
，
m
2
，…，
m
k
中的
某一项，即
m
1
，
m
2
，…，m
k
均为假，所以
B
=
m
1
?m
2< br>?
…
?m
k
为假。
综上，
A?B
。
利用真值表法求主析取范式的基本步骤为：
（1）列出公式的真值表。
（2）将真值表中的最后一列中的1的赋值所对应的小项写出。
（3）将这些小项进行析取。
例1.7.8 利用真值表法求
?(P?Q)
的主析取范式。
解
?(P?Q)
的真值表见表1-17。
表1-17
?(P?Q)
的真值表
P

Q

?(P?Q)

0
0
1
1
0
1
0
1
1
1
1
0
从表1-17中可以看 出，该公式在其真值表的00行、01行、10行处取真值1，所以
?(P?Q)
?
m
0
?m
1
?m
2
?
(?P??Q)?(?P?Q) ?(P??Q)
。
例1.7.9用真值表法求
(P?Q)?R
的主析取范式。
解
(P?Q)?R
的真值表见表1-18。
表1-18
(P?Q)?R
的真值表
P

Q

R

P?Q

(P?Q)?R

0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
从表1-18中可以看出，该公式在 其真值表的001行、011行、101行、110行和111行
处取真值1，所以

(P?Q)?R
?
m
1
?m
3
?m
5
?m
6
?m
7
?(?P??Q?R)?(?P?Q?R)?(P??Q?R) ?(P?Q??R)?(P?Q?R)
。
例1.7.10 设公式
A
的真值表见表1-19，求公式
A
的主析取范式。
解 由真值表可看出公式
A
有3组成真赋值，分别出现在000行，100行和111行，
所以公式
A
的主析取范式为
A
?(?P??Q??R)?(P??Q??R)?(P?Q?R)
。
表1-19 公式
A
的真值表
P

Q

R

A

0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
0
1
（2）等值演算法
除了用真值表法来求一个命题公式 的主析取范式外，还可以利用公式的等值演算方法
来推导。具体的求解步骤如下：
1）求公式
A
的析取范式
A
；
'
2）除去
A
中所有永假的析取项；
3） 若
A
的某个简单合取式
B
中不含有某个命题变元
P
，也不含
?P
，则将
B
展成形
式
B?B?1?B?(P??P)?(B?P)?(B??P )
。
（4）将重复出现的命题变元、矛盾式及重复出现的小项都消去。
（5）将小项按顺序排列。
例1.7.11 求
(P?Q)?Q
的主析取范式。
解
(P?Q)?Q?(?P?Q)?Q?(?P?Q)?Q


?(?P?Q)?((P??P)?Q)


?(?P?Q)?((P?Q)?(?P?Q))


?(?P?Q)?(P?Q)

'
'

例1.7.12 求
(P?Q)?R
的主析取范式。
解
(P?Q)?R?(?P?Q)?R


?((?P?Q)?R)?(R?(?P?Q))

?(?(?P?Q)?R)?(?R??P?Q)

?((P??Q)?R)?(?P?Q??R)

?((P??Q)?(?P?Q??R))?(R?(?P?Q??R))

?(P? ?Q??P)?(P??Q?Q)?(P??Q??R)?(R??P)?(R?Q)?(R??R)
? (P??Q??R)?(?P?R)?(Q?R)

?(P??Q??R)?(?P?(Q??Q)?R)?((P??P)?Q?R)

?(P??Q??R)?(?P?Q?R)?(?P??Q?R)?(P?Q?R)?(?P?Q?R)
?(?P??Q?R)?(?P?Q?R)?(P??Q??R)?(P?Q?R)

2．主合取范式
定义1.7.7 在含有n个命题变元的简单析取式中，若每个命题变元及其 否定形式不同时
出现，但二者之一必出现且仅出现一次，则称该简单析取式为大项。
例如，两 个命题变元
P
和
Q
生成的4个大项为：
P?Q
，
P ??Q
，
?P?Q
，
?P??Q
。3个命题变元
P
、
Q
和
R
生成的8个大项为：
P?Q?R
，
P?Q ??R
，
P??Q?R
，
P??Q??R
，
?P?Q?R< br>，
?P?Q??R
，
?P??Q?R
，
?P??Q??R。
一般说来，n个命题变元共有
2
个大项。
大项的二进制编码为： 命题变元按字母顺序排列，命题变元与0对应，命题变元的否
定与1对应，则得到大项的二进制编码，记 为
M
i
,其下标i是由二进制编码转化的十进制数。
n个命题变元形成的2
个大项，分别记为：
n
n
M
0
，
M
1
，…，
M
2
n
?1
。
表1-20列出了两个命题变元
P
和
Q
生成的4个大项的真值表。

表1-20 两个命题变元
P
和
Q
生成的4个大项的真值表


M
（二进制）
M
00

M
01

M
10

M
11

P

Q

P?Q

P??Q

?P?Q

?P??Q

0 0
0 1
1 0
1 1




0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0


M
（十进制）
M
0

M
1

M
2

M
3

从 这个真值表中可以看到，没有两个大项是等价的，且每个大项都只对应着
P
和
Q
的
一组真值指派使得该大项的真值为0。
这个结论可以推广到3个及3个以上变元的情况。
由真值表可得到大项具有如下性质：
1）各大项的真值表都不相同。
2）每个大项 当其真值指派与对应的二进制编码相同时，其真值为假，在其余
2
n
?1
种< br>指派情况下，其真值均为真。
3）任意两个不同大项的析取式是永真式。例如
M
00
?
M
10
=
(P?Q)?(?P?Q)?P??P?Q?1< br>
4）全体大项的合取式必为永假式。
定义1.7.8 由若干个不同的大项组成的合取式称为主合取范式(The Principal
Conjunctive Normal Form)。与公式
A
等价的主合取范式称为
A
的主合取范式。
定理1.7.9 任意含
n
个命题变元的非永真式命题公式都存在着与之等价的主合取 范式，
并且其主合取范式是唯一的。
与主析取范式的求解方法相类似，主合取范式同样可通过真值表法或等值演算法求得。
（1）真值表法
定理1.7.10 在真值表中，命题公式
A
的真值为假 的赋值所对应的大项的合取即为命
题公式
A
的主合取范式。
证明方法与定理1.7.8的证明相类似。
利用真值表法求主合取范式的基本步骤为：
（1）列出公式的真值表。
（2）将真值表中的最后一列中的0的赋值所对应的大项写出。
（3）将这些大项进行合取。
例1.7.13 求
(P?Q)?Q
的主合取范式。
解
(P?Q)?Q
的真值表见表1-21。
表1-21
(P?Q)?Q
的真值表

P

Q

P?Q

(P?Q)?Q

0
0
1
1
0
1
0
1
1
1
0
1
0
1
0
1
从上表可看出，公式
(P? Q)?Q
在00行，10行处取真值0，所以
(P?Q)?Q
?(P?Q)?(?P? Q)?M
0
?M
2
。
（2）等值演算法
具体的求解步骤如下：
1）求公式
A
的合取范式
A
；
'
2）除去
A
中所有永真的合取项；
3） 若
A
的某个简单析取式
B
中不含有某个命题变元
P
，也不含
?P
，则将
B
展成形
式
B?B?0?B?(P??P)?(B?P)?(B??P )
。
4）将重复出现的命题变元、永真式及重复出现的大项都消去。
5）将大项按顺序排列。
例1.7.14 求
(P?Q)?(?P?R)
的主合取范式。
解
(P?Q)?(?P?R)

'
'
?((P?Q)??P)?((P?Q)?R)

?(P??P)?(Q??P)?(P?R)?(Q?R)

?(?P?Q)?(P?R)?(Q?R)

?((?P?Q)?(R??R))?(P?(Q??Q)?R)?((P??P)?Q?R)

?(?P?Q?R)?(?P?Q??R)?(P?Q?R)?(P??Q?R)?(P?Q?R)?( ?P?Q?R)
?(?P?Q?R)?(?P?Q??R)?(P?Q?R)?(P??Q?R)

?
M
0
?M
2
?M
4
?M
5

3．主析取范式和主合取范式关系
设
Z
为命题公式
A< br>的主析取范式中所有小项的足标集合，
R
为命题公式
A
的主合取范式中所有大项的足标集合，则有

R?{0,1,2,L,2
n
?1}?Z

或
Z?{0,1,2,L,2
n
?1}?R
。
故已知命题公式
A
的主析取范式，可求得其主合取范式；反之亦然。
事实上 ，注意到小项
m
i
与大项
M
i
满足
?
m< br>i
?
M
i
，
?
M
i
?
m< br>i
。（例：
m
5
:P??Q?R
，
M
5
:?P?Q??R
）。
在含有
n
个命题变元 的命题公式
A
中，如果
A
的主析取范式中含有
k
个小项m
j
1
,m
j
2
，
,L
,m
j
k
，则
?A
的主析取范式中必含
2
n
?k
个小项
m
i
1
,m
i
2
,
L
, m
i
n
，且
2?k
{0,1,2,L,2
n
?1 }?{j
1
,j
2
,L,j
k
}?{i
1
,i
2
,L,i
2
n
?k
}

所以 ?A?m
i
1
?m
i
2
?
L
?mi
n
2?k
A??(m
i
1
?m
i
2
?
L
?m
i
n
)
2?k
??m
i
1
??m
i
2
?
L
??m
i
n
?M
i
1
?M
i
2
?
L
?M< br>i
n
n
2?k

2?k
则
A
的主合 取范式中含有
2?k
个大项，且
A
的主合取范式为
M
i1
?M
i
2
?L?M
i
n
。因
2?k
此，根据公式的主析（合）取范式可以写出相应的主合（析）取范式。
如例1.7.14 中 的主合取范式为
M
0
?M
2
?M
4
?M
5
已求出，则主析取范式为
m
1
?m
3
?m
6
?m
7
，然后写出相应的小项即可。
例1.7.15 求
?(P?Q)??(?P?R)
的主析取范式与主合取范式。
解
?(P?Q)??(?P?R)

?(?(P?Q)??(?P?R))?(?(?P?R)??(P?Q))

?((P?Q)??(?P?R))?((?P?R)??(P?Q))

?((P?Q)?(?P??R))?((P?R)?(?P??Q))

?(P??R)?(?P?Q)?(Q??R)

?(P?Q??R)?(P??Q??R)?(?P?Q?R)?

(?P?Q??R )?(P?Q??R)?(?P?Q??R)

?M
1
?M
3< br>?M
4
?M
5

?m
0
?m
2
?m
6
?m
7

?(?P??Q??R)?(?P?Q??R)?(P?Q??R)?(P?Q?R)

4．主范式的应用
（1）命题公式等价性的判定
由于每个命题公式都存在着与之等 价的唯一的主析取范式和主合取范式，因此，如果两
个命题公式等价，则相应的主范式也对应相同。
例1.7.16 判断
(P?Q)?(P?R)
与
P?(Q?R)
是否等价。
解 因为
(P?Q)?(P?R)
?
(?P?Q)?(?P?R)

?(?P?Q?(R??R))?(?P?(Q??Q)?R)

?(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)

?M
4
?M
5
?M
6

P?(Q?R)??P?(Q?R)

?(?P?Q)?(?P?R)

?M
4
?M
5
?M
6

所以
(P?Q)?(P?R)
?
P?(Q?R)
。
( 2) 命题公式类型的判定
定理1.7.11 设
A
是含
n
个命题变元的命题公式，则
1）
A
为 永真式当且仅当
A
的主析取范式中含有全部
2
个小项。
2）
A
为矛盾式当且仅当
A
的主合取范式中含有全部
2
个大项。
3）若
A
的主析取范式中至少含有一个小项，则
A
是可满足式。
例1.7.17 判断下列命题公式的类型。
1)
((P?Q)?P)?Q

2)
(P?Q)?Q

解
((P?Q)?P)?Q?((?P?Q)?P)?Q


??((?P?Q)?P)?Q

n
n

?(P??Q)??P?Q


?(P??Q)?(?P?(Q??Q))?((P??P)?Q)


?(P??Q)?(?P?Q)?(?P??Q)?(P?Q)?(?P?Q)


?m
0
?m
1
?m
2
?m
3

因此，命题公式1)为永真式。
(P?Q)?Q?(?P?Q)?Q?(?P?Q)?Q


?(?P?Q)?((?P?P)?Q)


?(?P?Q)?(?P?Q)?(P?Q)


?(?P?Q)?(P?Q)


?m
1
?m
3

因此，命题公式2)为可满足式。
（3） 解决实际问题
例1.7.18 张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。请问3
人中到底谁在说谎？
解 设
P
：张三说真话（即没有说谎）。
Q
：李四说真话。
R
：王五说真话。则张三说
李四在说谎可符号化为：
P??Q
。类似地，其 余两句话可符号化为：
Q??R
，
R?(?P??Q)
。
上述已知条件可表示为
G?
(P??Q)?(Q??R)?(R?(?P??Q))

公式
G
的真值表见表1-22。
表1-22 公式
G
的真值表
P

Q

R

G

0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
0
0
0
0
0

则公式
G
的主析取范式为
?P?Q??R
，即张三在说谎，李四说真话，王五说谎话。
例1.7.19 某单位要从 4位职工甲、乙、丙、丁中挑选两位职工去外地旅游，由于工作
需要，选派时要考虑下列要求：
（1）甲、乙两人中去且仅去1人。
（2）乙和丁不能都去。
（3）若丙去，则丁必须去。
（4）若丁不去，则甲也不去。
问该单位派谁去符合要求？
解 设
P
：派甲去旅游。
Q
：派乙去旅游。
R
：派丙去旅游。
S
：派丁去旅游。
则由已知条件可得命题公式：
G?((P??Q)?(?P?Q))?(?Q??S)?(R?S)?(?S??P)

公式
G
化成主析取范式为
G
?(P??Q?R?S)?(P??Q??R?S)?(?P?Q??R??S)

故选派方案有：
（1）派甲、丙、丁去旅游。
（2）派甲、丁去旅游。
（3）派乙去旅游。
由于单位要派两位职工去旅游，因此只有方案（2）满足要求，即派甲、丁去旅游。

习题
1．写出下列公式的对偶式。
（1）
(P?Q)?T

（2）
(P??Q)?(P?(Q??R))

（3）
(P?F)??R

（4）
((P?Q)?R)??P

2．（1）设
A(P,Q,R) ?(P?Q)??R
，则
A(?P,?Q,?R)?
。
（2）
A(P,Q)?P?Q
，则
?A(?P,?Q)?
。
3．求下列公式的析取范式与合取范式：
（1）
P?(P?Q)
。
（2）
(P?Q)?R
。
（3）
((P?Q)?R)?P
。
*
*

（4）
?(P?Q)?(P?Q)
。
4．写出下列含有3个命题变元的大项或小项（脚标是十进制）。
（1）
M
4
（2）
m
4
（3）
?M
7
（4）
?m
7

5． 在对
P
、
Q
、
R
的真值指派110下，小项
m010
取值为 ，大项
M
001
取值
为 。
6．求下列命题公式的主析取范式和主合取范式：
（1）
((P?Q)?R)?P
。
（2）
?(P?Q)?(P?Q)
。
（3）
(?P?Q)?R

7．判断下列命题公式的类型：
（1）
P?(P?(Q?P))
。
（2）
(Q?P)?(?P?Q)
。
（3）
(?P??Q)?(P??Q)
。
（4）
(P?(Q?R))?(?P?(?Q??R))
。
8．某科研所有 三名青年高级工程师A、B和C。所里要选派他们中的1~2人出国进修，由
于所里工作的需要，选派时 必须满足以下条件：
①若A去，则C也去。
②若B去，则C不能去。
③若C不去，则A或B去。
问所里应如何选派他们？
9．试判断下列各组命题是否等价：
(1)
(P?Q)?(P?R)
与
P?(Q?R)
。
(2)
P?(Q?R)
与
P?(Q?R)
。

推理理论
推理是由一个或几个命题推出另一个命题的思维形式。从结构上说，推理由前提、结
论和规则3 个部分组成。前提与结论有蕴含关系的推理，或者结论是从前提中必然推出的推
理称为必然性推理，如演 绎推理；前提和结论没有蕴含关系的推理，或者前提与结论之间并
没有必然联系而仅仅是一种或然性联系 的推理称为或然性推理，如简单枚举归纳推理。推理：
“金能导电，银能导电，铜能导电。金、银、铜都 是金属。所以金属都能导电。”这种从偶
然现象概括出一般规律的推理就是一种简单枚举归纳推理。命题 逻辑中的推理是演绎推理。

在实际应用的推理中，常常把本门学科的一些定律、定理和 条件，作为假设前提，尽
管这些前提在数理逻辑中并非永真，但在推理过程中，却总是假设这些命题为真 ，并使用一
些公认的规则，得到另外的命题，形成结论，这种过程就是论证。
定义1.8.1 设
A
和
C
是两个命题公式，当且仅当
A?C
为一重言式，即
A?C
，称
C
是
A
的有效结论，或
C
可由
A
逻辑推出。
这个定义可以推广到有
n
个前提的情况。
设
H
1
，
H
2
，…，
H
n
，C
是命题公式，当且仅当
H
1
?
H
2
?
…
?
H
n
?
C
，称
C
是
一组前 提
H
1
，
H
2
，…，
H
n
的有效 结论。
注意，在形式逻辑中，并不关心结论
C
是否真实，而只在乎由给定的前提H
1
，
H
2
，…，
H
n
能否推出结论
C
来，只注意推理的形式是否正确。因此，有效结论并不一定是正确的，
只有正确的前 提经过正确的推理得到的逻辑结论才是正确的。
在证明有效结论时，可以用前面介绍的真值表法或证明 蕴含关系的方法来论证结论的
有效性。论证的方法千变万化，但基本上归纳起来只有3种方法，即真值表 法、直接证法和
间接证法。
真值表法在此不再讨论。
1.8.1 直接证法

直接证法就是由一组命题，利用一些公认的推理规则，根据已知的等价式或蕴含式，
推演出有效结论，即形式演绎法。
直接证法必须遵循下列推理规则：
P
规则：前提条件在推导过程中的任何时候都可以引入使用。
T
规则：在推 导过程中，所证明的结论、已知的等价或蕴含公式都可以作为后续证明
的前提，命题公式中的任何子公式 都可以用与之等价的命题公式置换。
现将常用的蕴含式和等价式列入表1-23和表1-24中。

表1-23 常用的蕴含式
I
1

P?Q?P

P?Q?Q

P?P?Q

Q?P?Q

?P?P?Q

Q?P?Q

?(P?Q)?P

I
2

I
3

I
4

I
5

I
6

I
7

I
8

I
9

I
10

?(P?Q)??Q

P,Q?P?Q

?P,P?Q?Q

P,P?Q?Q

?Q,P?Q??P

P?Q,Q?R?P?R

P?Q,P?R,Q?R?R

I
11

I
12

I
13

I
14

I
15

A?B?(A?C)?(B?C)

I
16

A?B?(A?C)?(B?C)


表1-24 常用的等价式
E
1

E
2

E
3

??P?P

P?Q?Q?P

P?Q?Q?P

(P?Q)?R?P?(Q?R)

(P?Q)?R?P?(Q?R)

P?(Q?R)?(P?Q)?(P?R)

P?(Q?R)?(P?Q)?(P?R)

?(P?Q)??P??Q

?(P?Q)??P??Q

E
4

E
5

E
6

E
7

E
8

E
9

E
10

P?P?P

P?P?P

E
11

E
12

E
13

R?(P??P)?R

R?(P??P)?R

R?(P??P)?T

R?(P??P)?F

P?Q??P?Q

?(P?Q)?P??Q

P?Q??Q??P

P?(Q?R)?(P?Q)?R

P?Q?(P?Q)?(Q?P)

P?Q?(P?Q)?(?P??Q)

?(P?Q)?P??Q

E
14

E
15

E
16

E
17

E
18

E
19

E
20

E
21

E
22

例1.8.1 证明
(P?Q)?(Q?R)?(P?S)??S?R

证明 （1）
P?S

P

（2）
?P?S

T(1)
E

（3）
?S

P

（4）
?P

T(2)(3)
I

（5）
P?Q

P

（6）
Q

T(4)(5)
I

（7）
Q?R

P

（8）
R

T(6)(7)
I

例1.8.2 证明
(W?R)?V
,
V?C?S
,
S?U
,
?C??U??W

证明 （1）
?C??U

P

（2）
?U

T(1)
I

（3）
S?U

P

（4）
?S

T(2)(3)
I

（5）
?C

T(1)
I

（6）
?C??S

T(4)(5)
I

（7）
?(C?S)

T(6)
E

（8）
(W?R)?V

P

（9）
V?C?S

P

（10）
(W?R)?(C?S)

T(8)(9)
I

（11）
?(W?R)

T(7)(10)

（12）
?W??R

T(11)
E

（13）
?W

T(12)
I

例1.8.3 符号化下述命题并证明结论的有效性。 前提：若
a
是实数，则它不是有理数就是无理数。若
a
不能表示成分数， 则它不是有
理数。
a
是实数且不能表示成分数。
结论：
a
是无理数。
证明 设
P
：
a
是实数。
Q
：
a
是有理数。
R
：
a
是无理 数。
S
：
a
能表示成分数。
则本题即证：
P?(Q?R)< br>，
?S??Q
，
P??S?R

（1）
P??S

P

（2）
P

T(1)
I

（3）
P?(Q?R)

P

（4）
Q?R

T(2)(3)
I

（5）
?S

P

（6）
?S??Q

P

（7）
?Q

T(5)(6)
I

（8）
R

T(4)(7)
I

例1.8.4 已知张三或李四的彩票中奖，如果张三中奖，你是会知道的；如果李四中奖，
王 五也中奖了；现在你不知道张三中奖。试用逻辑推理来确定谁中奖了？ 并写出推理过程。
解 设< br>P
：张三中奖。
Q
：李四中奖。
R
：王五中奖。
S< br>：你知道张三中奖。由题设

得已知条件：
P?Q
，
P? S
，
Q?R
，
?S
。则推理如下：
（1）
?S

P

（2）
P?S

P

（3）
?P?S

T(2)
E

（4）
?P

T(1)(3)
I

（5）
P?Q

P

（6）
Q

T(4)(5)
I

（7）
Q?R

P

（8）
R

T(6)(7)
I

（9）
Q?R

T(6)(8)
I

即李四和王五都中奖了。

1.8.2 间接证法
间接证法主要有两种，一种称之为
CP
规则，还有一 种是常用的反证法（也叫归谬法）。
1．附加前提证明法（
CP
规则）
由 公式的等价性知
C
1
?C
2
?
…
?C
n< br>?(A?B)?C
1
?C
2
?
…
?C
n?A?B
，
所以要证明
C
1
?C
2
?
…
?C
n
?A?B
，只需证明
C
1
?C
2
?
…
?C
n
?A?B
即可，
这种方法称为
CP
规则。
例1.8.5 证明由
P?(Q?S)
，
?R?P，
Q
能有效推出
R?S
。
证明 （1）
R

P
（附加前提）
（2）
?R?P

P

（3）
P

T(1)(2)
I

（4）
P?(Q?S)

P

（5）
Q?S

T(3)(4)
I

（6）
Q

P

（7）
S

T(5)(6)
I

（8）
R?S

CP

例1.8.6 “如果春暖花开，燕子就会飞回北方，如果燕子飞回北方，则冰 雪融化，所以

如果冰雪没有融化，则没有春暖花开”。证明这些语句构成一个正确的推理 。
解 设
P
：春暖花开。
Q
：燕子飞回北方。
R
：冰雪融化。则上述论断转化成要证明
P?Q
，
Q?R
??R??P
。
证（1）
?R

P
（附加前提）
（2）
Q?R

P

（3）
?Q

T(1)(2)
I

（4）
P?Q

P

（5）
?P

T(3)(4)
I

（6）
?R??P

CP

例1.8.7 “如 果
A
努力工作，
B
或
C
将生活愉快；如果
B
生活愉快，那么
A
将不努力
工作；如果
D
愉快，
C
将不愉快。所以如果
A
努力工作，
D
将不愉快”。问这些语句是否
构成一个正确的推理？
解 设
P
：
A
努力工作。
Q
：
B
将生活愉快 。
R
：
C
将生活愉快。
S
：
D
将愉快。
前提：
P?(Q?R)
，
Q??P
，
S??R

结论：
P??S

（1）
P

P
（附加前提）
（2）
Q??P

P

（3）
?Q

T(1)(2)
I

（4）
P?(Q?R)

P

（5）
Q?R

T(1)(4)
I

（6）
R

T(3)(5)
I

（7）
S??R

P

（8）
?S

T(6)(7)
I

（9）
P??S

CP

因此，上述推理是正确的。

2．归谬法
归谬法（反证法）是经常使用的 一种间接证明方法，是将结论的否定形式作为附加前
提与给定的前提条件一起推证来导出矛盾。它的基本 原理是：
A?B
当且仅当
A??B
为
矛盾式。

这是因为
A?B
当且仅当
A?B
为重言式，即
?A?B
永真，当且仅当
?(?A?B)?A??B
永假。
例1.8.8
R??Q
，
R?S
，
S??Q
，
P?Q
?
?P
证明 （1）
P

P
（附加前提）
（2）
P?Q

P

（3）
Q

T(1)(2)
I

（4）
S??Q

P

（5）
?S

T(3)(4)
I

（6）
R?S

P

（7）
R

T(5)(6)
I

（8）
R??Q

P

（9）
?Q

T(7)(8)
I

（10）
Q??Q
（矛盾式）
T(3)(9)
I

由（10）得出了矛盾，根据归谬法说明原推理正确。
例1.8.9
P?Q
，
P?R
，
Q?S
?
R?S

证明 （1）
?(R?S)

P
（附加前提）
（2）
?R??S

T(1)
E

（3）
?R

T(2)
I

（4）
P?R

P

（5）
?P

T(3)(4)
I

（6）
P?Q

P

（7）
Q

T(5)(6)
I

（8）
Q?S

P

（9）
S

T(7)(8)
I

（10）
?S

T(2)
I

（11）
S??S
（矛盾式）
T(9)(10)
I

由（11）得出了矛盾，根据归谬法说明原推理正确。

习题
1．证明
(?P??Q)?(?P?R)?(R??S)?S??Q
。
2．用间接证法证明
P?(?Q?R),Q??P,S??R,P??S

3．如果2是偶数，则3是奇数；或者2是偶数或者2整除3 。结果2不整除3，所以3 是
奇数。证明上述论断正确。
4．某公司若拒绝增加工资，则罢工不会停止，除非罢工超过一 年并且公司经理辞职。问：
如果公司拒绝增加工资，而罢工又刚刚开始，罢工是否会停止？
5 ．“如果下雨，春游就会改期；如果没有球赛，春游就不会改期。结果没有球赛，所以没有
下雨。”证明 上述论断正确。
6．如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我 考试
没有及格。试对上述论证构造证明。
7．证明 R?S是前提C?D，C→R，D→S的有效结论。
8．证明P∨Q , Q?R, P?S , ┐S ? R∧(Q∨P)。
9．证明 (A→B?C)?(B→┐A)?(D→┐C) ? (A→┐D)。