第 2章 命题逻辑等值演算离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 等值式与基本的等值式
– 等值演算与置换规则
– 析取范式与合取范式、主析取范式与主合取范式
– 联结词完备集 (不讲 )
本章与后续各章的关系
– 是第一章的抽象与延伸
– 是后续各章的现行准备
2.1 等值式
两公式什么时候代表了同一个命题呢？
抽象地看，它们的真假取值完全相同时即代表了相同的命题。
设公式 A,B共同含有 n个命题变项，可能对 A或
B有哑元，若 A与 B有相同的真值表，则说明在
2n个赋值的每个赋值下,A与 B的真值都相同
。于是等价式 A?B应为重言式。
等值的定义及说明定义 2.1 设 A,B是两个命题公式，若 A,B构成的等价式 A?B为重言式,则称 A与 B是 等值 的，记作
A?B。
说明
定义中,A,B,?都是 元语言符号 。
A或 B中可能有哑元出现。
p→q? (┐ p∨q)∨( ┐ r∧r)
r为左边公式中的哑元。
用真值表可以验证两个公式是否等值。
例题例 2.1 判断下面两个公式是否等值
┐( p∨q) 与 ┐ p∧┐q
解答说明?在用真值表法判断 A?B是否为重言式时，真值表的最后一列可以省略
。
等值例题例题 2.2 判断下列各组公式是否等值
(1)p→(q→r) 与 (p∧q)→r
(2)(p→q)→r 与 (p∧q)→r
解答等值不等值基本等值式
1.双重否定律 A? ┐┐A
2.幂等律 A? A∨A,A? A∧A
3.交换律 A∨B? B∨A,A∧B? B∧A
4.结合律 (A∨B)∨C? A∨(B∨C)
(A∧B)∧C? A∧(B∧C)
5.分配律 A∨(B∧C)? (A∨B)∧(A∨C)
（ ∨ 对 ∧ 的分配律）
A∧(B∨C)? (A∧B)∨(A∧C)
（ ∧ 对 ∨ 的分配律）
6.德 ·摩根律 ┐( A∨B)? ┐A∧┐B
┐(A∧B)? ┐A∨┐B
7.吸收律 A∨(A∧B)? A,A∧(A∨B)? A
基本等值式
8.零律 A∨1? 1,A∧0? 0
9.同一律 A∨0? A,A∧1? A
10.排中律 A∨┐A? 1
11.矛盾律 A∧┐A? 0
12.蕴涵等值式 A→B? ┐A∨B
13.等价等值式 A?B? (A→B)∧(B→A)
14.假言易位 A→B? ┐B→┐A
15.等价否定等值式 A?B? ┐A?┐B
16.归谬论 (A→B)∧(A→┐B)? ┐A
对偶原理一个逻辑等值式，如果只含有 ┐,∨,∧,0,1
那么同时把 ∨ 和 ∧ 互换把 0和 1互换得到的还是等值式。
等值演算与置换规则
各等值式都是用元语言符号书写的，其中 A,B,C可以代表任意的公式，称这样的等值式为 等值式模式 。
每个等值式模式都给出了无穷多个同类型的具体的等值式。
例如，在蕴涵等值式 A→B?┐A∨B 中，
取 A=p,B=q时，得等值式 p→q?┐p∨q
取 A=p∨q∨r,B=p∧q 时，得等值式
(p∨q∨r)→(p∧q)? ┐(p∨q∨r)∨(p∧q)
这些具体的等值式都被称为原来的等值式模式的 代入实例 。
由已知的等值式推演出另外一些等值式的过程为 等值演算 。
置换规则 设 Φ(A) 是含公式 A的命题公式,Φ(B) 是用公式 B
置换了 Φ(A) 中所有的 A后得到的命题公式，若 B?A,则
Φ(B)?Φ(A) 。
关于等值演算的说明
等值演算的基础
– 等值关系的性质：
自反性,A?A。
对称性：若 A?B,则 B?A。
传递性：若 A?B且 B?C,则 A?C。
– 基本的等值式
– 置换规则
等值演算的应用
– 证明两个公式等值
– 判断公式类型
– 解判定问题等值演算的应用举例证明两个公式等值
(p→q)→r? (p∨r)∧(┐q∨r)
(p→q )→r? (┐p∨q) →r （ 蕴含等值式,置换规则 ）
┐(┐ p∨q) ∨r （ 蕴含等值式,置换规则 ）
(p∧┐q) ∨r （ 德摩根律,置换规则 ）
(p∨r)∧(┐q∨r) （ 分配律,置换规则 ）
说明
也可以从右边开始演算
因为每一步都用置换规则，故可不写出
熟练后，基本等值式也可以不写出
通常不用等值演算直接证明两个公式不等值解答例题例 2.3 用等值演算法验证等值式
(p∨q)→r? (p→r)∧(q→r)
(p→ r)∧(q → r)
(┐p ∨r )∧(┐q ∨r ) (蕴含等值式 )
(┐p∧┐q )∨r (分配律 )
┐(p∨q)∨r (德摩根律 )
(p∨q)→r (蕴含等值式 )
解答例题例 2.4 证明,(p→q)→r 与 p→(q→r) 不等值方法一,真值表法。
方法二,观察法。 易知,010是 (p→q)→r 的成假赋值，而 010
是 p→(q→r) 的成真赋值，所以原不等值式成立。
方法三,通过等值演算化成容易观察真值的情况，再进行判断。
A=(p→ q)→r? (┐p∨q) → r （蕴涵等值式）
┐(┐p∨q) ∨r （蕴涵等值式）
(p∧┐q)∨r （德摩根律）
B=p→ (q→ r)? ┐p∨ (┐q∨r ) （蕴涵等值式）
┐p∨┐q∨r （结合律）
000,010是 A的成假赋值，而它们是 B的成真赋值。
解答例题例题 2.5 用等值演算判断下列公式的类型：
（ 1） (p→q)∧p→q
（ 2） (p→(p∨q))∧r
（ 3） p∧(((p∨q)∧┐p)→q)
例 2.5 解答
(1) (p→ q)∧p→q
(┐p∨q)∧p → q （ 蕴涵等值式 ）
┐((┐ p∨q)∧p) ∨q （ 蕴涵等值式 ）
(┐(┐ p∨q) ∨┐p)∨q （ 德摩根律 ）
((p∧┐q) ∨┐p )∨q （ 德摩根律 ）
((p∨┐p )∧(┐q∨┐p))∨q （ 分配律 ）
(1∧ (┐ q∨┐p))∨ q （ 排中律 ）
(┐ q∨q )∨┐p （ 同一律 ）
1∨ ┐ p （ 排中律 ）
1 （ 零律 ）
例 2.5 解答
(2) ┐(p → (p∨q))∧r
┐ (┐p∨p∨q)∧r
(p∧┐p ∧┐q)∧r
0∧ r
0
(3) p∧(((p∨q)∧┐p) → q)
p∧(┐((p∨q) ∧┐p )∨q)
p∧(┐( (p∧┐p) ∨(q∧┐p))∨q)
p∧( ┐ (0∨ (q∧┐p))∨q)
p∧( ┐q∨ p∨ q)
p∧ 1? p
例 2.6 应用题在某次研讨会的中间休息时间,3名与会者根据王教授的口音对他是哪个省市的人进行了判断：
甲说王教授不是苏州人,是上海人 。
乙说王教授不是上海人,是苏州人 。
丙说王教授既不是上海人,也不是杭州人 。
听完以上 3人的判断后,王教授笑着说,他们 3人中有一人说的全对,有一人说对了一半,另一人说的全不对 。 试用逻辑演算法分析王教授到底是哪里人？
例 2.6 解答设命题 p,王教授是苏州人。
q,王教授是上海人。
r,王教授是杭州人。
p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。
设 甲的判断为 A1=┐p∧q
乙的判断为 A2=p∧┐q
丙的判断为 A3=┐q∧┐r
例 2.6 解答甲的判断全对 B1=A1=┐p∧q
甲的判断对一半 B2=(┐p∧┐q)∨(p∧q)
甲的判断全错 B3=p∧┐q
乙的判断全对 C1=A2=p∧┐q
乙的判断对一半 C2=(p∧q)∨(┐p∧┐q)
乙的判断全错 C3=┐p∧q
丙的判断全对 D1=A3=┐q∧┐r
丙的判断对一半 D2=(q∧┐r)∨(┐q∧r)
丙的判断全错 D3=q∧r
例 2.6 解答由王教授所说
E = (B1∧C 2∧D 3)∨(B 1∧C 3∧D 2)∨(B 2∧C 1∧D 3)
∨(B 2∧C 3∧D 1)∨(B 2∨C 1∧D 2)∨(B 3∧C 2∧D 1)
为真命题。
经过等值演算后,可得
E? (┐p∧q∧┐r)∨(p∧┐q∧r)
由题设，王教授不能既是上海人，又是杭州人，因而 p,r中必有一个假命题，即 p∧┐q∧r?0，于是
E? ┐p∧q∧┐r
为真命题，因而必有 p,r为假命题,q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。
例 2.6的进一步思考王教授只可能是其中一个城市的人或者三个城市都不是。
所以，丙至少说对了一半。
因此，可得甲或乙必有一人全错了。
又因为，若甲全错了，则有 p∧┐q,因此乙全对。
同理，乙全错则甲全对。
所以丙必是一对一错。
根据上述推理，可对公式 E进行简化，方便等值演算。
(如何简化，请同学们课后思考 )
2.2 析取范式和合取范式定义 2.2
命题变项及其否定统称作 文字（ letters） 。
仅由有限个文字构成的析取式称作 简单析取式 。
仅由有限个文字构成的合取式称作 简单合取式 。
简单析取式举例：
p,┐q p∨┐p,┐p∨q ┐ p∨┐q∨r,p∨┐q∨r
简单合取式举例：
┐ p,q ┐ p∧p,p∧┐q p∧q∧┐r,┐p∧p∧q
说明?一个文字既是简单析取式，又是简单合取式。
2.2 析取范式和合取范式
为讨论方便，有时用 A1,A2,…,As表示 s个简单析取式或 s个简单合取式。
设 Ai是含 n个文字的简单析取式，若 Ai中既含某个命题变项
pj,又含它的否定式 ┐ pj,即 pj∨ ┐ pj，则 Ai为重言式。
反之，若 Ai为重言式，则它必同时含某个命题变项和它的否定式，否则，若将 Ai中的不带否定符号的命题变项都取 0值
，带否定号的命题变项都取 1值，此赋值为 Ai的成假赋值，
这与 Ai是重言式相矛盾。
类似的讨论可知，若 Ai是含 n个命题变项的简单合取式，且
Ai为矛盾式，则 Ai中必同时含某个命题变项及它的否定式，
反之亦然。
2.2 析取范式和合取范式定理 2.1
(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。
(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。
定义 2.3
(1)由有限个简单合取式构成的析取式称为 析取范式
（ disjunctive normal form） 。
(2)由有限个简单析取式构成的合取式称为 合取范式
（ conjunctive normal form） 。
(3)析取范式与合取范式统称为 范式 。
2.2 析取范式和合取范式
设 Ai(i=1,2,…,s)为简单合取式，则 A=A1∨A 2∨ … ∨A s为析取范式。例如,A1=p∧┐q,A2=┐q∧┐r,A3=p,则由
A1,A2,A3构造的析取范式为
A=A1∨A 2∨A 3=(p∧┐q)∨(┐q∧┐r)∨p
设 Ai(i=1,2,…,s)为简单析取式，则 A=A1∧A 2∧ … ∧A s为合取范式。例如，取 A1=p∨q∨r,A2=┐p∨┐q,A3=r,则由
A1,A2,A3组成的合取范式为
A=A1∧A 2∧A 3=(p∨q∨r)∧(┐p∨┐q)∧r
说明
形如 ┐ p∧q∧r 的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。
形如 p∨┐q∨r 的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式。
析取范式和合取范式的性质定理 2.2
(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。
(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
说明
研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。
范式存在的讨论
在范式中不会出现联结词 → 与?,否则可使用等值式消除
A→B? ┐A∨B
A?B? (┐A∨B)∧(A∨┐B)
在范式中不会出现形如 ┐┐ A,┐(A∧B),┐(A∨B) 的公式：
┐┐ A? A
┐( A∧B)? ┐A∨┐B ┐( A∨B)?┐A∧┐B
在析取范式中不会出现形如 A∧(B∨C) 的公式：
A∧(B∨C)? (A∧B)∨(A∧C)
在合取范式中不出现形 A∨(B∧C) 的公式：
A∨(B∧C)? (A∨B)∧(A∨C)
定理 2.3
任一命题公式都存在着与之等值的析取范式与合取范式。
求给定公式范式的步骤
(1)消去联结词 →,?(若存在 )。
A→B? ┐A∨B
A?B? (┐A∨B)∧(A∨┐B)
(2)否定号的消去 (利用双重否定律 )或内移 (利用德摩根律 )。
┐┐ A? A
┐( A∧B)? ┐A∨┐B
┐( A∨B)?┐A∧┐B
(3)利用分配律：利用 ∧ 对 ∨ 的分配律求析取范式，
∨ 对 ∧ 的分配律求合取范式。
A∧(B∨C)? (A∧B)∨(A∧C)
A∨(B∧C)? (A∨B)∧(A∨C)
例题例题 2.7 求下面公式的析取范式与合取范式：
(p→q)? r
(1) 求合取范式
(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∨r)∧(┐q∨r)∧(┐p∨q∨┐r) （ ∨ 对 ∧ 分配律 ）
解答例题
(2) 求析取范式
(p→q)? r
((p∧┐q) ∨ 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)
说明
由此例可知,命题公式的析取范式不唯一。
同样,合取范式也是不唯一的。
范式的规范化形式
定义 2.4 在含有 n个命题变项的简单合取式（简单析取式）
中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第 i个命题变项或它的否定式出现在从左算起的第 i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为 极小项
（ 极大项 ）。
n个命题变项共可产生 2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数 i,就将所对应极小项记作 mi 。
类似地,n个命题变项共可产生 2n个极大项，每个极大项只有一个成假赋值，将其对应的十进制数 i做极大项的角标，
记作 Mi。
表 2.3 p,q形成的极小项与极大项表 2.4 p,q,r形成的极小项与极大项范式的规范化形式定理 2.4 设 mi与 Mi是命题变项 p1,p2,…,pn形成的极小项和极大项，则
┐ mi? Mi,┐M i? mi
定义 2.5 设由 n个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）
为主析取范式 （ 主合取范式 ）。
定理 2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。
定理 2.5的证明
(只证主析取范式的存在和唯一性 )
(1)证明存在性。
设 A是任一含 n个命题变项的公式。
由定理 2.3可知，存在与 A等值的析取范式 A′,即 A?A′,若 A′
的某个简单合取式 Ai中既不含命题变项 pj,也不含它的否定式
┐ pj,则将 Ai展成如下形式：
Ai? Ai∧1? Ai∧(p j∨┐p j)? (Ai∧p j)∨(A j∧┐p j)
继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式。
若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应,消去,,如用 p代替 p∧p,mi代替 mi∨m i,0代替矛盾式等
。最后就将 A化成与之等值的主析取范式 A''。
定理 2.5
(2)证明唯一性。
假设某一命题公式 A存在两个与之等值的主析取范式 B和 C，
即 A?B且 A?C,则 B?C。
由于 B和 C是不同的主析取范式，不妨设极小项 mi只出现在 B
中而不出现在 C中。
于是，角标 i的二进制表示为 B的成真赋值，而为 C的成假赋值。这与 B?C矛盾，因而 B与 C必相同。
求公式 A的主析取范式的方法与步骤方法一、等值演算法
(1)化归为析取范式。
(2)除去析取范式中所有永假的析取项。
(3)将析取式中重复出现的合取项和相同的变元合并。
(4)对合取项补入没有出现的命题变元，即添加如 (p∨┐p) 式
，然后应用分配律展开公式。
方法二、真值表法
(1)写出 A的真值表。
(2)找出 A的成真赋值。
(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。
求公式 A的主合取范式的方法与步骤方法一、等值演算法
(1)化归为合取范式。
(2)除去合取范式中所有永真的合取项。
(3)将合取式中重复出现的析取项和相同的变元合并。
(4)对析取项补入没有出现的命题变元，即添加如 (p∧┐p)
式，然后应用分配律展开公式。
方法二、真值表法
(1)写出 A的真值表。
(2)找出 A的成假赋值。
(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。
例题例 2.9 求命题公式 p→q 的主析取范式和主合取范式。
(1)求主合取范式
p→q? ┐p∨q? M2
(2)求析取范式
p→q? ┐p∨q
（ ┐p∧ （ ┐q∨q ）） ∨ （ (┐p∨p )∧q ）
(┐ p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)
(┐p∧┐q)∨(┐p∧q)∨(p∧q)
m0∨m 1∨m 3
解答 p q p → q
0 0 1
0 1 1
1 0 0
1 1 1
例 2.8 求例 2.7中公式的主析取范式和主合取范式。
(1)求主析取范式
(p→q)?r? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)
p∧┐q∧┐r? m4
┐p∧r? ┐ p∧ （ ┐q∨q ） ∧r
(┐ p∧┐q∧r)∨(┐p∧q∧r)
m1∨m 3
q∧r? (┐p∨p)∧q∧r
(┐ p∧q∧r)∨(p∧q∧r)
m3∨m 7
(p→q)?r? m1∨m 3∨m 4∨m 7
例 2.8 求例 2.7中公式的主析取范式和主合取范式。
(2)求主合取范式
(p→q)?r? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)
┐p∨q∨┐r? M5
p∨r? p∨(q∧┐q)∨r
(p∨q∨r)∧(p∨┐q∨r)
M0∧M 2
┐q∨r? (p∧┐p)∨┐q∨r
(p∨┐q∨r)∧(┐p∨┐q∨r)
M2∧M 6
(p→q)?r? M0∧M 2∧M 5∧M 6
主析取范式的用途
求公式的成真赋值与成假赋值
判断公式的类型
判断两个命题公式是否等值
应用主析取范式分析和解决实际问题求公式的成真赋值与成假赋值
若公式 A中含 n个命题变项,A的主析取范式含 s(0≤s≤2 n)
个极小项，则 A有 s个成真赋值，它们是所含极小项角标的二进制表示，其余 2n-s个赋值都是成假赋值。
在例 2.8中,(p→q)?r? m1∨m 3∨m 4∨m 7,各极小项均含三个文字，因而各极小项的角标均为长为 3的二进制数，它们分别是 001,011,100,111，这四个赋值为该公式的成真赋值,其余的为成假赋值。
在例 2.9中,p→q? m0∨m 1∨m 3,这三个极小项均含两个文字，它们的角标的二进制表示 00,01,11为该公式的成真赋值,10是它的成假赋值。
判断公式的类型设公式 A中含 n个命题变项，容易看出：
A为重言式当且仅当 A的主析取范式含全部 2n个极小项。
A为矛盾式当且仅当 A的主析取范式不含任何极小项。此时，记 A的主析取范式为 0。
A为可满足式当且仅当 A的主析取范式至少含一个极小项。
判断公式的类型例 2.10 用公式的主析取范式判断公式的类型：
(1) ┐( p→q)∧q
(2) p→(p∨q)
(3) (p∨q)→r
解答
(1)┐( p→q)∧q? ┐ （ ┐p∨q ） ∧q
(p∧┐q)∧q? 0
(2)p→(p∨q)? m0∨m 1∨m 2∨m 3
(3)(p∨q)→r? m0∨m 1∨m 3∨m 5∨m 7
矛盾式重言式可满足式判断两个命题公式是否等值
设公式 A,B共含有 n个命题变项，按 n个命题变项求出 A与 B的主析取范式 A‘与 B’。 若 A‘＝ B’,则 A?B； 否则,A与 B不等值。
例 2.11 判断下面两组公式是否等值：
(1) p与 (p∧q)∨(p∧┐q)
(2)(p→q)→r 与 (ｐ ∧ q)→r
(1) p? p∧(┐q∨q)? (p∧┐q)∨(p∧q)? m2∨m 3
(p∧q)∨(p∧┐q)? m2∨m 3
两公式等值。
(2) (p→q)→r? m1∨m 3∨m 4∨m 5∨m 7
(ｐ ∧ q)→r? m0∨m 1∨m 2∨m 3∨m 4∨m 5∨m 7
两公式不等值。
解答应用主析取范式分析和解决实际问题例 2.12 某科研所要从 3名科研骨干 A,B,C中挑选 1～ 2名出国进修。由于工作原因，选派时要满足以下条件：
(1)若 A去，则 C同去。
(2)若 B去，则 C不能去。
(3)若 C不去，则 A或 B可以去。
问应如何选派他们去？
分析：
(1) 将简单命题符号化
(2) 写出各复合命题
(3) 写出由 (2)中复合命题组成的合取式（前提）
(4) 将 (3)中公式化成析取式（最好是主析取范式）
(5) 这样每个小项就是一种可能产生的结果。
去掉不符合题意的小项，即得结论。
应用主析取范式分析和解决实际问题设 p:派 A去,q:派 B去,r:派 C去由已知条件可得公式
(p→r)∧(q→┐r)∧(┐r→(p∨q))
经过演算可得
(p→r)∧(q→┐r)∧(┐r→(p∨q))? m1∨m 2∨m 5
由于 m1=┐p∧┐q∧r,m 2=┐p∧q∧┐r,m 5=p∧┐q∧r
可知，选派方案有 3种：
(a)C去，而 A,B都不去。
(b)B去，而 A,C都不去。
(c)A,C去，而 B不去。
解答由公式的主析取范式求主合取范式设公式 A含 n个命题变项。
A的主析取范式含 s(0<s<2n)个极小项，即
sjimmmA njiii s,,2,1,120,21
没有出现的极小项设为
snjjj
mmm
221
,,,?
它们的角标的二进制表示为 ┐A 的成真赋值，因而 ┐A 的主析取范式为
snjjj
mmmA
221
)(
221 snjjj
mmmAA
)
221 snjjj
mmm
)
221 snjjj
MMM
例题例 2.13 由公式的主析取范式，求主合取范式：
(1) A? m1∨m 2 (A中含两个命题变项 p,q)
(2) B? m1∨m 2∨m 3 (B中含两个命题变项 p,q,r)
解答
(1) A? M0∧M 3
(2) B? M0∧M 4∧M 5∧M 6∧M 7
重言式与矛盾式的主合取范式设 n为公式中命题变项个数
矛盾式无成真赋值，因而矛盾式的主合取范式含 2n个极大项。
重言式无成假赋值，因而主合取范式不含任何极大项。
将重言式的主合取范式记为 1。
可满足式的主合取范式中极大项的个数一定小于 2n。
真值表与范式的关系
A?B当且仅当 A与 B有相同的真值表，又当且仅当 A与 B
有相同的主析取范式（主合取范式）。
真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。
n个命题变项共可产生 2n个极小项（极大项）
可以产生的 主析取范式（主合取范式）数目为：
nn
nnn CCC
22
2
1
2
0
2 2
本章主要内容
等值式与等值演算。
基本的等值式，其中含：双重否定律、幂等律、
交换律、结合律、分配律、德 ·摩根律、吸收律、
零律、同一律、排中律、矛盾律、蕴含等值式、
等价等值式、假言易位、等价否定等值式、归谬论。
与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。
本章学习要求
深刻理解等值式的概念。
牢记 24个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算。
了解简单析取式、简单合取式、析取范式、合取范式的概念
。
深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。
熟练掌握求公式的主析取范式的方法。
熟练掌握由公式的主析取范式求公式的主合取范式的方法。
会用公式的主析取范式（主合取范式）求公式的成真赋值、
成假赋值。
本章典型习题
用等值演算法证明重言式和矛盾式
用等值演算法证明等值式
求公式的主析取范式和主合取范式
用主范式判断两个公式是否等值
求解实际问题例题求公式 (p∧q)∨(┐p∧r) 的主析取范式和主合取范式。
解答 p q r (p∧q)∨(┐p∧r)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
主析取范式为 (┐ p∧ ┐ q∧r)∨( ┐ p∧q∧r)∨(p∧q∧ ┐ r)∨ (p∧q∧r)
主合取范式为 (p∨q∨r)∧(p∨ ┐ q∨r)∧( ┐ p∨q∨r)∧ (┐ p∨q∨ ┐ r)
例题甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，下列四个判断都是正确的：
(1)甲和乙只有一人参加比赛。
(2)丙参加，丁必参加。
(3)乙或丁至多参加一人。
(4)丁不参加，甲也不会参加。
请推断出哪两个人参加围棋比赛。
设 a,甲参加了比赛。 b,乙参加了比赛。
c,丙参加了比赛。 d,丁参加了比赛。
(1) (a∧ ┐ b)∨( ┐ a∧b) (2) c→d
(3) ┐ (b∧d) (4) ┐ d→ ┐ a
解答
((a∧ ┐ b)∨( ┐ a∧b) )∧( c→d )∧( ┐ (b∧d) )∧( ┐ d→ ┐ a)
(a∧ ┐ b∧ ┐ c∧d )∨( a∧ ┐ b∧d )∨( ┐ a∧b∧ ┐ c∧ ┐ d)
根据题意条件，有且仅有两人参赛，
故﹁ a∧b∧ ﹁ c∧ ﹁ d为 0,所以
(a∧ ﹁ b∧ ﹁ c∧d )∨( a∧ ﹁ b∧d )为 1，
即甲和丁参加了比赛。
(a∨b)∧(c∨d)? (a∧c)∨(b∧c)∨(a∧d)∨(b∧d) 说明本章作业习题二
4,7,8,9,10,23,29,30
本章的主要内容
– 等值式与基本的等值式
– 等值演算与置换规则
– 析取范式与合取范式、主析取范式与主合取范式
– 联结词完备集 (不讲 )
本章与后续各章的关系
– 是第一章的抽象与延伸
– 是后续各章的现行准备
2.1 等值式
两公式什么时候代表了同一个命题呢？
抽象地看，它们的真假取值完全相同时即代表了相同的命题。
设公式 A,B共同含有 n个命题变项，可能对 A或
B有哑元，若 A与 B有相同的真值表，则说明在
2n个赋值的每个赋值下,A与 B的真值都相同
。于是等价式 A?B应为重言式。
等值的定义及说明定义 2.1 设 A,B是两个命题公式，若 A,B构成的等价式 A?B为重言式,则称 A与 B是 等值 的，记作
A?B。
说明
定义中,A,B,?都是 元语言符号 。
A或 B中可能有哑元出现。
p→q? (┐ p∨q)∨( ┐ r∧r)
r为左边公式中的哑元。
用真值表可以验证两个公式是否等值。
例题例 2.1 判断下面两个公式是否等值
┐( p∨q) 与 ┐ p∧┐q
解答说明?在用真值表法判断 A?B是否为重言式时，真值表的最后一列可以省略
。
等值例题例题 2.2 判断下列各组公式是否等值
(1)p→(q→r) 与 (p∧q)→r
(2)(p→q)→r 与 (p∧q)→r
解答等值不等值基本等值式
1.双重否定律 A? ┐┐A
2.幂等律 A? A∨A,A? A∧A
3.交换律 A∨B? B∨A,A∧B? B∧A
4.结合律 (A∨B)∨C? A∨(B∨C)
(A∧B)∧C? A∧(B∧C)
5.分配律 A∨(B∧C)? (A∨B)∧(A∨C)
（ ∨ 对 ∧ 的分配律）
A∧(B∨C)? (A∧B)∨(A∧C)
（ ∧ 对 ∨ 的分配律）
6.德 ·摩根律 ┐( A∨B)? ┐A∧┐B
┐(A∧B)? ┐A∨┐B
7.吸收律 A∨(A∧B)? A,A∧(A∨B)? A
基本等值式
8.零律 A∨1? 1,A∧0? 0
9.同一律 A∨0? A,A∧1? A
10.排中律 A∨┐A? 1
11.矛盾律 A∧┐A? 0
12.蕴涵等值式 A→B? ┐A∨B
13.等价等值式 A?B? (A→B)∧(B→A)
14.假言易位 A→B? ┐B→┐A
15.等价否定等值式 A?B? ┐A?┐B
16.归谬论 (A→B)∧(A→┐B)? ┐A
对偶原理一个逻辑等值式，如果只含有 ┐,∨,∧,0,1
那么同时把 ∨ 和 ∧ 互换把 0和 1互换得到的还是等值式。
等值演算与置换规则
各等值式都是用元语言符号书写的，其中 A,B,C可以代表任意的公式，称这样的等值式为 等值式模式 。
每个等值式模式都给出了无穷多个同类型的具体的等值式。
例如，在蕴涵等值式 A→B?┐A∨B 中，
取 A=p,B=q时，得等值式 p→q?┐p∨q
取 A=p∨q∨r,B=p∧q 时，得等值式
(p∨q∨r)→(p∧q)? ┐(p∨q∨r)∨(p∧q)
这些具体的等值式都被称为原来的等值式模式的 代入实例 。
由已知的等值式推演出另外一些等值式的过程为 等值演算 。
置换规则 设 Φ(A) 是含公式 A的命题公式,Φ(B) 是用公式 B
置换了 Φ(A) 中所有的 A后得到的命题公式，若 B?A,则
Φ(B)?Φ(A) 。
关于等值演算的说明
等值演算的基础
– 等值关系的性质：
自反性,A?A。
对称性：若 A?B,则 B?A。
传递性：若 A?B且 B?C,则 A?C。
– 基本的等值式
– 置换规则
等值演算的应用
– 证明两个公式等值
– 判断公式类型
– 解判定问题等值演算的应用举例证明两个公式等值
(p→q)→r? (p∨r)∧(┐q∨r)
(p→q )→r? (┐p∨q) →r （ 蕴含等值式,置换规则 ）
┐(┐ p∨q) ∨r （ 蕴含等值式,置换规则 ）
(p∧┐q) ∨r （ 德摩根律,置换规则 ）
(p∨r)∧(┐q∨r) （ 分配律,置换规则 ）
说明
也可以从右边开始演算
因为每一步都用置换规则，故可不写出
熟练后，基本等值式也可以不写出
通常不用等值演算直接证明两个公式不等值解答例题例 2.3 用等值演算法验证等值式
(p∨q)→r? (p→r)∧(q→r)
(p→ r)∧(q → r)
(┐p ∨r )∧(┐q ∨r ) (蕴含等值式 )
(┐p∧┐q )∨r (分配律 )
┐(p∨q)∨r (德摩根律 )
(p∨q)→r (蕴含等值式 )
解答例题例 2.4 证明,(p→q)→r 与 p→(q→r) 不等值方法一,真值表法。
方法二,观察法。 易知,010是 (p→q)→r 的成假赋值，而 010
是 p→(q→r) 的成真赋值，所以原不等值式成立。
方法三,通过等值演算化成容易观察真值的情况，再进行判断。
A=(p→ q)→r? (┐p∨q) → r （蕴涵等值式）
┐(┐p∨q) ∨r （蕴涵等值式）
(p∧┐q)∨r （德摩根律）
B=p→ (q→ r)? ┐p∨ (┐q∨r ) （蕴涵等值式）
┐p∨┐q∨r （结合律）
000,010是 A的成假赋值，而它们是 B的成真赋值。
解答例题例题 2.5 用等值演算判断下列公式的类型：
（ 1） (p→q)∧p→q
（ 2） (p→(p∨q))∧r
（ 3） p∧(((p∨q)∧┐p)→q)
例 2.5 解答
(1) (p→ q)∧p→q
(┐p∨q)∧p → q （ 蕴涵等值式 ）
┐((┐ p∨q)∧p) ∨q （ 蕴涵等值式 ）
(┐(┐ p∨q) ∨┐p)∨q （ 德摩根律 ）
((p∧┐q) ∨┐p )∨q （ 德摩根律 ）
((p∨┐p )∧(┐q∨┐p))∨q （ 分配律 ）
(1∧ (┐ q∨┐p))∨ q （ 排中律 ）
(┐ q∨q )∨┐p （ 同一律 ）
1∨ ┐ p （ 排中律 ）
1 （ 零律 ）
例 2.5 解答
(2) ┐(p → (p∨q))∧r
┐ (┐p∨p∨q)∧r
(p∧┐p ∧┐q)∧r
0∧ r
0
(3) p∧(((p∨q)∧┐p) → q)
p∧(┐((p∨q) ∧┐p )∨q)
p∧(┐( (p∧┐p) ∨(q∧┐p))∨q)
p∧( ┐ (0∨ (q∧┐p))∨q)
p∧( ┐q∨ p∨ q)
p∧ 1? p
例 2.6 应用题在某次研讨会的中间休息时间,3名与会者根据王教授的口音对他是哪个省市的人进行了判断：
甲说王教授不是苏州人,是上海人 。
乙说王教授不是上海人,是苏州人 。
丙说王教授既不是上海人,也不是杭州人 。
听完以上 3人的判断后,王教授笑着说,他们 3人中有一人说的全对,有一人说对了一半,另一人说的全不对 。 试用逻辑演算法分析王教授到底是哪里人？
例 2.6 解答设命题 p,王教授是苏州人。
q,王教授是上海人。
r,王教授是杭州人。
p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。
设 甲的判断为 A1=┐p∧q
乙的判断为 A2=p∧┐q
丙的判断为 A3=┐q∧┐r
例 2.6 解答甲的判断全对 B1=A1=┐p∧q
甲的判断对一半 B2=(┐p∧┐q)∨(p∧q)
甲的判断全错 B3=p∧┐q
乙的判断全对 C1=A2=p∧┐q
乙的判断对一半 C2=(p∧q)∨(┐p∧┐q)
乙的判断全错 C3=┐p∧q
丙的判断全对 D1=A3=┐q∧┐r
丙的判断对一半 D2=(q∧┐r)∨(┐q∧r)
丙的判断全错 D3=q∧r
例 2.6 解答由王教授所说
E = (B1∧C 2∧D 3)∨(B 1∧C 3∧D 2)∨(B 2∧C 1∧D 3)
∨(B 2∧C 3∧D 1)∨(B 2∨C 1∧D 2)∨(B 3∧C 2∧D 1)
为真命题。
经过等值演算后,可得
E? (┐p∧q∧┐r)∨(p∧┐q∧r)
由题设，王教授不能既是上海人，又是杭州人，因而 p,r中必有一个假命题，即 p∧┐q∧r?0，于是
E? ┐p∧q∧┐r
为真命题，因而必有 p,r为假命题,q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。
例 2.6的进一步思考王教授只可能是其中一个城市的人或者三个城市都不是。
所以，丙至少说对了一半。
因此，可得甲或乙必有一人全错了。
又因为，若甲全错了，则有 p∧┐q,因此乙全对。
同理，乙全错则甲全对。
所以丙必是一对一错。
根据上述推理，可对公式 E进行简化，方便等值演算。
(如何简化，请同学们课后思考 )
2.2 析取范式和合取范式定义 2.2
命题变项及其否定统称作 文字（ letters） 。
仅由有限个文字构成的析取式称作 简单析取式 。
仅由有限个文字构成的合取式称作 简单合取式 。
简单析取式举例：
p,┐q p∨┐p,┐p∨q ┐ p∨┐q∨r,p∨┐q∨r
简单合取式举例：
┐ p,q ┐ p∧p,p∧┐q p∧q∧┐r,┐p∧p∧q
说明?一个文字既是简单析取式，又是简单合取式。
2.2 析取范式和合取范式
为讨论方便，有时用 A1,A2,…,As表示 s个简单析取式或 s个简单合取式。
设 Ai是含 n个文字的简单析取式，若 Ai中既含某个命题变项
pj,又含它的否定式 ┐ pj,即 pj∨ ┐ pj，则 Ai为重言式。
反之，若 Ai为重言式，则它必同时含某个命题变项和它的否定式，否则，若将 Ai中的不带否定符号的命题变项都取 0值
，带否定号的命题变项都取 1值，此赋值为 Ai的成假赋值，
这与 Ai是重言式相矛盾。
类似的讨论可知，若 Ai是含 n个命题变项的简单合取式，且
Ai为矛盾式，则 Ai中必同时含某个命题变项及它的否定式，
反之亦然。
2.2 析取范式和合取范式定理 2.1
(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。
(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。
定义 2.3
(1)由有限个简单合取式构成的析取式称为 析取范式
（ disjunctive normal form） 。
(2)由有限个简单析取式构成的合取式称为 合取范式
（ conjunctive normal form） 。
(3)析取范式与合取范式统称为 范式 。
2.2 析取范式和合取范式
设 Ai(i=1,2,…,s)为简单合取式，则 A=A1∨A 2∨ … ∨A s为析取范式。例如,A1=p∧┐q,A2=┐q∧┐r,A3=p,则由
A1,A2,A3构造的析取范式为
A=A1∨A 2∨A 3=(p∧┐q)∨(┐q∧┐r)∨p
设 Ai(i=1,2,…,s)为简单析取式，则 A=A1∧A 2∧ … ∧A s为合取范式。例如，取 A1=p∨q∨r,A2=┐p∨┐q,A3=r,则由
A1,A2,A3组成的合取范式为
A=A1∧A 2∧A 3=(p∨q∨r)∧(┐p∨┐q)∧r
说明
形如 ┐ p∧q∧r 的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。
形如 p∨┐q∨r 的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式。
析取范式和合取范式的性质定理 2.2
(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。
(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
说明
研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。
范式存在的讨论
在范式中不会出现联结词 → 与?,否则可使用等值式消除
A→B? ┐A∨B
A?B? (┐A∨B)∧(A∨┐B)
在范式中不会出现形如 ┐┐ A,┐(A∧B),┐(A∨B) 的公式：
┐┐ A? A
┐( A∧B)? ┐A∨┐B ┐( A∨B)?┐A∧┐B
在析取范式中不会出现形如 A∧(B∨C) 的公式：
A∧(B∨C)? (A∧B)∨(A∧C)
在合取范式中不出现形 A∨(B∧C) 的公式：
A∨(B∧C)? (A∨B)∧(A∨C)
定理 2.3
任一命题公式都存在着与之等值的析取范式与合取范式。
求给定公式范式的步骤
(1)消去联结词 →,?(若存在 )。
A→B? ┐A∨B
A?B? (┐A∨B)∧(A∨┐B)
(2)否定号的消去 (利用双重否定律 )或内移 (利用德摩根律 )。
┐┐ A? A
┐( A∧B)? ┐A∨┐B
┐( A∨B)?┐A∧┐B
(3)利用分配律：利用 ∧ 对 ∨ 的分配律求析取范式，
∨ 对 ∧ 的分配律求合取范式。
A∧(B∨C)? (A∧B)∨(A∧C)
A∨(B∧C)? (A∨B)∧(A∨C)
例题例题 2.7 求下面公式的析取范式与合取范式：
(p→q)? r
(1) 求合取范式
(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∨r)∧(┐q∨r)∧(┐p∨q∨┐r) （ ∨ 对 ∧ 分配律 ）
解答例题
(2) 求析取范式
(p→q)? r
((p∧┐q) ∨ 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)
说明
由此例可知,命题公式的析取范式不唯一。
同样,合取范式也是不唯一的。
范式的规范化形式
定义 2.4 在含有 n个命题变项的简单合取式（简单析取式）
中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第 i个命题变项或它的否定式出现在从左算起的第 i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为 极小项
（ 极大项 ）。
n个命题变项共可产生 2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数 i,就将所对应极小项记作 mi 。
类似地,n个命题变项共可产生 2n个极大项，每个极大项只有一个成假赋值，将其对应的十进制数 i做极大项的角标，
记作 Mi。
表 2.3 p,q形成的极小项与极大项表 2.4 p,q,r形成的极小项与极大项范式的规范化形式定理 2.4 设 mi与 Mi是命题变项 p1,p2,…,pn形成的极小项和极大项，则
┐ mi? Mi,┐M i? mi
定义 2.5 设由 n个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）
为主析取范式 （ 主合取范式 ）。
定理 2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。
定理 2.5的证明
(只证主析取范式的存在和唯一性 )
(1)证明存在性。
设 A是任一含 n个命题变项的公式。
由定理 2.3可知，存在与 A等值的析取范式 A′,即 A?A′,若 A′
的某个简单合取式 Ai中既不含命题变项 pj,也不含它的否定式
┐ pj,则将 Ai展成如下形式：
Ai? Ai∧1? Ai∧(p j∨┐p j)? (Ai∧p j)∨(A j∧┐p j)
继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式。
若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应,消去,,如用 p代替 p∧p,mi代替 mi∨m i,0代替矛盾式等
。最后就将 A化成与之等值的主析取范式 A''。
定理 2.5
(2)证明唯一性。
假设某一命题公式 A存在两个与之等值的主析取范式 B和 C，
即 A?B且 A?C,则 B?C。
由于 B和 C是不同的主析取范式，不妨设极小项 mi只出现在 B
中而不出现在 C中。
于是，角标 i的二进制表示为 B的成真赋值，而为 C的成假赋值。这与 B?C矛盾，因而 B与 C必相同。
求公式 A的主析取范式的方法与步骤方法一、等值演算法
(1)化归为析取范式。
(2)除去析取范式中所有永假的析取项。
(3)将析取式中重复出现的合取项和相同的变元合并。
(4)对合取项补入没有出现的命题变元，即添加如 (p∨┐p) 式
，然后应用分配律展开公式。
方法二、真值表法
(1)写出 A的真值表。
(2)找出 A的成真赋值。
(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。
求公式 A的主合取范式的方法与步骤方法一、等值演算法
(1)化归为合取范式。
(2)除去合取范式中所有永真的合取项。
(3)将合取式中重复出现的析取项和相同的变元合并。
(4)对析取项补入没有出现的命题变元，即添加如 (p∧┐p)
式，然后应用分配律展开公式。
方法二、真值表法
(1)写出 A的真值表。
(2)找出 A的成假赋值。
(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。
例题例 2.9 求命题公式 p→q 的主析取范式和主合取范式。
(1)求主合取范式
p→q? ┐p∨q? M2
(2)求析取范式
p→q? ┐p∨q
（ ┐p∧ （ ┐q∨q ）） ∨ （ (┐p∨p )∧q ）
(┐ p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)
(┐p∧┐q)∨(┐p∧q)∨(p∧q)
m0∨m 1∨m 3
解答 p q p → q
0 0 1
0 1 1
1 0 0
1 1 1
例 2.8 求例 2.7中公式的主析取范式和主合取范式。
(1)求主析取范式
(p→q)?r? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)
p∧┐q∧┐r? m4
┐p∧r? ┐ p∧ （ ┐q∨q ） ∧r
(┐ p∧┐q∧r)∨(┐p∧q∧r)
m1∨m 3
q∧r? (┐p∨p)∧q∧r
(┐ p∧q∧r)∨(p∧q∧r)
m3∨m 7
(p→q)?r? m1∨m 3∨m 4∨m 7
例 2.8 求例 2.7中公式的主析取范式和主合取范式。
(2)求主合取范式
(p→q)?r? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)
┐p∨q∨┐r? M5
p∨r? p∨(q∧┐q)∨r
(p∨q∨r)∧(p∨┐q∨r)
M0∧M 2
┐q∨r? (p∧┐p)∨┐q∨r
(p∨┐q∨r)∧(┐p∨┐q∨r)
M2∧M 6
(p→q)?r? M0∧M 2∧M 5∧M 6
主析取范式的用途
求公式的成真赋值与成假赋值
判断公式的类型
判断两个命题公式是否等值
应用主析取范式分析和解决实际问题求公式的成真赋值与成假赋值
若公式 A中含 n个命题变项,A的主析取范式含 s(0≤s≤2 n)
个极小项，则 A有 s个成真赋值，它们是所含极小项角标的二进制表示，其余 2n-s个赋值都是成假赋值。
在例 2.8中,(p→q)?r? m1∨m 3∨m 4∨m 7,各极小项均含三个文字，因而各极小项的角标均为长为 3的二进制数，它们分别是 001,011,100,111，这四个赋值为该公式的成真赋值,其余的为成假赋值。
在例 2.9中,p→q? m0∨m 1∨m 3,这三个极小项均含两个文字，它们的角标的二进制表示 00,01,11为该公式的成真赋值,10是它的成假赋值。
判断公式的类型设公式 A中含 n个命题变项，容易看出：
A为重言式当且仅当 A的主析取范式含全部 2n个极小项。
A为矛盾式当且仅当 A的主析取范式不含任何极小项。此时，记 A的主析取范式为 0。
A为可满足式当且仅当 A的主析取范式至少含一个极小项。
判断公式的类型例 2.10 用公式的主析取范式判断公式的类型：
(1) ┐( p→q)∧q
(2) p→(p∨q)
(3) (p∨q)→r
解答
(1)┐( p→q)∧q? ┐ （ ┐p∨q ） ∧q
(p∧┐q)∧q? 0
(2)p→(p∨q)? m0∨m 1∨m 2∨m 3
(3)(p∨q)→r? m0∨m 1∨m 3∨m 5∨m 7
矛盾式重言式可满足式判断两个命题公式是否等值
设公式 A,B共含有 n个命题变项，按 n个命题变项求出 A与 B的主析取范式 A‘与 B’。 若 A‘＝ B’,则 A?B； 否则,A与 B不等值。
例 2.11 判断下面两组公式是否等值：
(1) p与 (p∧q)∨(p∧┐q)
(2)(p→q)→r 与 (ｐ ∧ q)→r
(1) p? p∧(┐q∨q)? (p∧┐q)∨(p∧q)? m2∨m 3
(p∧q)∨(p∧┐q)? m2∨m 3
两公式等值。
(2) (p→q)→r? m1∨m 3∨m 4∨m 5∨m 7
(ｐ ∧ q)→r? m0∨m 1∨m 2∨m 3∨m 4∨m 5∨m 7
两公式不等值。
解答应用主析取范式分析和解决实际问题例 2.12 某科研所要从 3名科研骨干 A,B,C中挑选 1～ 2名出国进修。由于工作原因，选派时要满足以下条件：
(1)若 A去，则 C同去。
(2)若 B去，则 C不能去。
(3)若 C不去，则 A或 B可以去。
问应如何选派他们去？
分析：
(1) 将简单命题符号化
(2) 写出各复合命题
(3) 写出由 (2)中复合命题组成的合取式（前提）
(4) 将 (3)中公式化成析取式（最好是主析取范式）
(5) 这样每个小项就是一种可能产生的结果。
去掉不符合题意的小项，即得结论。
应用主析取范式分析和解决实际问题设 p:派 A去,q:派 B去,r:派 C去由已知条件可得公式
(p→r)∧(q→┐r)∧(┐r→(p∨q))
经过演算可得
(p→r)∧(q→┐r)∧(┐r→(p∨q))? m1∨m 2∨m 5
由于 m1=┐p∧┐q∧r,m 2=┐p∧q∧┐r,m 5=p∧┐q∧r
可知，选派方案有 3种：
(a)C去，而 A,B都不去。
(b)B去，而 A,C都不去。
(c)A,C去，而 B不去。
解答由公式的主析取范式求主合取范式设公式 A含 n个命题变项。
A的主析取范式含 s(0<s<2n)个极小项，即
sjimmmA njiii s,,2,1,120,21
没有出现的极小项设为
snjjj
mmm
221
,,,?
它们的角标的二进制表示为 ┐A 的成真赋值，因而 ┐A 的主析取范式为
snjjj
mmmA
221
)(
221 snjjj
mmmAA
)
221 snjjj
mmm
)
221 snjjj
MMM
例题例 2.13 由公式的主析取范式，求主合取范式：
(1) A? m1∨m 2 (A中含两个命题变项 p,q)
(2) B? m1∨m 2∨m 3 (B中含两个命题变项 p,q,r)
解答
(1) A? M0∧M 3
(2) B? M0∧M 4∧M 5∧M 6∧M 7
重言式与矛盾式的主合取范式设 n为公式中命题变项个数
矛盾式无成真赋值，因而矛盾式的主合取范式含 2n个极大项。
重言式无成假赋值，因而主合取范式不含任何极大项。
将重言式的主合取范式记为 1。
可满足式的主合取范式中极大项的个数一定小于 2n。
真值表与范式的关系
A?B当且仅当 A与 B有相同的真值表，又当且仅当 A与 B
有相同的主析取范式（主合取范式）。
真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。
n个命题变项共可产生 2n个极小项（极大项）
可以产生的 主析取范式（主合取范式）数目为：
nn
nnn CCC
22
2
1
2
0
2 2
本章主要内容
等值式与等值演算。
基本的等值式，其中含：双重否定律、幂等律、
交换律、结合律、分配律、德 ·摩根律、吸收律、
零律、同一律、排中律、矛盾律、蕴含等值式、
等价等值式、假言易位、等价否定等值式、归谬论。
与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。
本章学习要求
深刻理解等值式的概念。
牢记 24个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算。
了解简单析取式、简单合取式、析取范式、合取范式的概念
。
深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。
熟练掌握求公式的主析取范式的方法。
熟练掌握由公式的主析取范式求公式的主合取范式的方法。
会用公式的主析取范式（主合取范式）求公式的成真赋值、
成假赋值。
本章典型习题
用等值演算法证明重言式和矛盾式
用等值演算法证明等值式
求公式的主析取范式和主合取范式
用主范式判断两个公式是否等值
求解实际问题例题求公式 (p∧q)∨(┐p∧r) 的主析取范式和主合取范式。
解答 p q r (p∧q)∨(┐p∧r)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
主析取范式为 (┐ p∧ ┐ q∧r)∨( ┐ p∧q∧r)∨(p∧q∧ ┐ r)∨ (p∧q∧r)
主合取范式为 (p∨q∨r)∧(p∨ ┐ q∨r)∧( ┐ p∨q∨r)∧ (┐ p∨q∨ ┐ r)
例题甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，下列四个判断都是正确的：
(1)甲和乙只有一人参加比赛。
(2)丙参加，丁必参加。
(3)乙或丁至多参加一人。
(4)丁不参加，甲也不会参加。
请推断出哪两个人参加围棋比赛。
设 a,甲参加了比赛。 b,乙参加了比赛。
c,丙参加了比赛。 d,丁参加了比赛。
(1) (a∧ ┐ b)∨( ┐ a∧b) (2) c→d
(3) ┐ (b∧d) (4) ┐ d→ ┐ a
解答
((a∧ ┐ b)∨( ┐ a∧b) )∧( c→d )∧( ┐ (b∧d) )∧( ┐ d→ ┐ a)
(a∧ ┐ b∧ ┐ c∧d )∨( a∧ ┐ b∧d )∨( ┐ a∧b∧ ┐ c∧ ┐ d)
根据题意条件，有且仅有两人参赛，
故﹁ a∧b∧ ﹁ c∧ ﹁ d为 0,所以
(a∧ ﹁ b∧ ﹁ c∧d )∨( a∧ ﹁ b∧d )为 1，
即甲和丁参加了比赛。
(a∨b)∧(c∨d)? (a∧c)∨(b∧c)∨(a∧d)∨(b∧d) 说明本章作业习题二
4,7,8,9,10,23,29,30
