2009-7-29 离散数学 1
逻辑学,研究思维 (或推理 )的形式结构和规律的学科。利用数学方法研究思维 (或推理 )的形式结构和规律的学科，称作数理逻辑。
数理逻辑数理逻辑的基本内容,命题逻辑 (演算 )、
谓词逻辑 。 它们对电子元件设计和性质分析,
对逻辑程序设计语言的研制具有十分重要的意义 。
2009-7-29 离散数学 2
第一章 命题逻辑
§ 1.1 命题与联结词
§ 1.2 命题公式及其赋值
§ 1.3 等值演算
§ 1.4 联结词的完备集
§ 1.5 对偶与范式
§ 1.6 推理理论
2009-7-29 离散数学 3
一、命题的概念命题,能判断真假的陈述句。这种判断只有两种可能，一种是正确的判断，一种是错误的判断。
§ 1.1 命题符号化及联结词命题真值,判断为正确的命题称其命题真值为真 (1) ；
判断为错误的命题称其命题真值为假 (0) ；
命题是具有唯一真值的陈述句。
2009-7-29 离散数学 4
例 1 判断下列句子中哪些是命题。
(1) 4是素数。
(2) 2 + 3 = 5。
(3) 雪是黑色的。
(4) 3能被 2整除。
(5) 2050年元旦是晴天。
(6) 5x + 1 > 11。
(7) 这朵花真美丽呀！
(8) 明天下午开会吗？
(9) 我正在说假话。
(是 )
(是 )
(是 )
(是 )
(是 )
(否 )
(否 )
(否 )
(否 )
2009-7-29 离散数学 5
解题思想：判断一个句子是否为命题，首先看它是否为陈述句,其次看它的真值是否唯一。
2009-7-29 离散数学 6
二、与命题相关的几个概念
1,简单命题 (或原子命题 )：
命题为简单的陈述句，不能分解成更简单的句子。一般用小写的英文字母 p,q,r,… 表示。
2,命题常项 (或命题常元 )：
由于简单命题的真值确定，故又称之为命题常项或命题常元。
如例 1中的陈述句 (1) (2) (3) (4) (5)。
2009-7-29 离散数学 7
二、与命题相关的几个概念（续）
3,命题变项 (或命题变元 )：
真值可以变化的简单陈述句，但它不是命题,也可以用 p,q,r等 表示。
如例 1中的陈述句 (6) (5x + 1 > 11)。
4,复合命题：
由简单命题用联结词联结而成的命题。
命题逻辑主要就是研究复合命题。
5,命题的符号化：
用符号来表示命题。
2009-7-29 离散数学 8
三、联结词先看一个例子：
例 2：判断下列命题是否为复合命题，说出其联结词。
(1) 3不是偶数。
(2) 2是 偶 素数。
(3) 2或 4是素数。
(4) 如果 2是素数,3也是素数。
(5) 2是素数 当且仅当 3也是素数。
(非 )
(且 )
(或 )
(如果 …,则 … )
(当且仅当 )
2009-7-29 离散数学 9
三、联结词（续）
常见的基本联结词：
1、否定联结词,?,,读作“非”。
复合命题“非 p”称作 p 的否定式，记作,? p,。
p 为真当且仅当 p为假。
在例 2(1)中，设 p表示,3是偶数,,则?p 表示,3
不是偶数,。显然,p真值为 0,?p 真值为 1 。
2009-7-29 离散数学 10
三、联结词（续）
2、合取联结词,?,,读作“合取”。
复合命题,p并且 q,称作 p 与 q 的合取式，记,p? q,。
p? q 为真当且仅当 p与 q 同时为真。
在例 2(2)中，设 p 表示,2是素数,,q 表示,2是偶数,,则 p? q 表示,2是偶素数,。因为 p和 q 的 真值均为 1,所以 p? q 的 真值为 1。
联结词“既 … 又 …”,“不但 … 而且 …”,“虽然 …
但是 …” 等，都可符号化为? 。
2009-7-29 离散数学 11
三、联结词（续）
3、析取联结词,?,,读作“析取”。
复合命题,p或 q,称作 p与 q 的析取式，记作,p? q,。
p? q 为真当且仅当 p 与 q 中至少一个为真。
例 2(3)中，设 p 表示,2是素数,,q 表示,4是素数,,则 p? q 表示,2或 4是素数,。
注意：,或,的二义性。如命题：派小王或小李中的一人去开会，应符号化为 ( p q )? (? p? q ),
这类“或”表达的是排斥或。
2009-7-29 离散数学 12
三、联结词（续）
4、蕴涵联结词,?,,读作“蕴 涵,。
复合命题,如果 p，则 q,称作 p 与 q 的蕴 涵 式，记作
,p? q,。 其中 p 称为蕴 涵 式的前件,q 称为蕴 涵式的后件。 p? q 为假当且仅当 p 为真且 q 为假。
例 2(4)中，设 p 表示,2是素数,,q 表示,3是素数,,则 p? q 表示,如果 2是素数，则 3也是素数,。
联结词“只要 p 就 q,，,p 仅当 q,，“只有 q
才
p,等，都可符号化为 p? q 。
2009-7-29 离散数学 13
三、联结词（续）
5、等价联结词,?,,读作“等价”。
复合命题,p 当且仅当 q,称作 p 与 q 的等价式，记作,p? q,。 p? q 为真当且仅当 p 与 q 真值相同。
例 2(5)中，设 p 表示,2是素数,,q 表示,3是素数,,则 p? q 表示,2是素数 当且仅当 3是素数,,由于 p,q的真值分别为 0,1，所以 p?q的真值为 0。
2009-7-29 离散数学 14
真值表利用以上 5种联结词,可将复合命题符号化,进而正确分析出复合命题的真值 。 基本真值表如下：
p q? p p? qp? qp? qp? q
0 0
0 1
1 0
1 1
1
1
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1
0
0
1
表 1.1
2009-7-29 离散数学 15
(1) 李平不是不聪明，而是不用功 。
(2) 李文和李武是兄弟。
(3) 只有不下雨，我才骑自行车上班 。
(4) 如果下雨，我就不骑自行车上班 。
(5) 若 2 + 2＝ 4，则太阳从西方升起。
设 p:2+2=4,q:太阳从西方升起,则符号化为 p? q
例 3 将下列命题符号化设 p:李文和李武是兄弟，则符号化为 p
设 p:天下雨,q:我骑自行车上班,? p是 q的必要条件则符号化为 q p
设 p:天下雨,q:我骑自行车上班,则符号化为 p q
设 p:李平聪明,q:李平用功,则符号化为?(?p) q
解题步骤,
(1) 分析出各简单命题，并符号化；
(2) 使用合适的联结词，把简单命题逐个联结起来，组成一复合命题的符号化形式。
2009-7-29 离散数学 16
例 3 将下列命题符号化 （续）
(6) 2 + 2? 4，当且仅当 3不是奇数 。
(7) 小王现在在宿舍或在图书馆。
(8) 选小王或小李中的一人当班长。
(9) 如果我上街，我就去书店看看，除非我很累。
(10)王一乐是计算机系的学生,他生于 1968年或 1969
年,他是三好学生。
设 p:2 + 2 = 4,q:3是奇数,则符号化为?p q
设 p:小王在宿舍,q:小王在图书馆,符号化为 p? q
设 p:选小王当班长,q:选小李当班长,则符号化为 (p q)? (? p? q)
设 p:我上街,q:我去书店看看,r:我很累，则符号化为?r? (p? q)
这里的,或,本来是排斥或，排斥或一般不能直接用,?” 联结，但两个命题不能同时为真时例外，因此,命题可符号化为 p? q,
其中 p:小王在宿舍,q:小王在图书馆设 p:王一乐是计算机系的学生,q:他生于
1968年,r,他生于 1969年,s：他是三好学生，则符号化为 p? (q? r)? s
2009-7-29 离散数学 17
合式公式：
一、命题公式的概念
§ 1.2 命题公式及其赋值
(1) 单个命题常项或变项 p,q,…,0,1 是合式公式；
(2) 若 A是合式公式，则?A也是合式公式；
(3) 若 A,B是合式公式，则 (A? B),(A? B),
(A? B),(A? B)是合式公式 ;
合式公式即称为命题公式。
(4) 只有有限次地应用 (1) ～ (3)组成的符号串才是合式公式。
2009-7-29 离散数学 18
一个含有命题变项的命题公式的真值是不确定的，
只有用指定的命题常项代替后真值才唯一确定。
二、命题公式的解释或赋值设 A为一命题 公式,p1,p2,…,pn为出现在 A中的所有的命题变项。给 p1,p2,…,pn指定一组真值，
称为对 A的一个 赋值或解释 。
若指定的一组真值使命题公式 A的真值为 1，则称这组赋值为 A的 成真赋值 ；若使 A的真值为 0，则称这组赋值为 A的 成假赋值 。
将命题公式 A在所有赋值下的取值情况列成表，称为 A的 真值表 。
2009-7-29 离散数学 19
(3)对应每个赋值，计算命题公式各层次的值，直到最后计算出命题公式的值。
二、命题公式的解释或赋值（真值表）
构造真值表的步骤：
命题运算的优先级顺序,(1)先括号 (2)? (3)?,
(4)? (5)? (6)从左至右
(1)找出命题公式中所有命题变项,p1,p2,…,pn,
列出所有可能的赋值 (2n个 )。
(2)按从低到高的顺序列出命题公式的各个运算层次。
2009-7-29 离散数学 20
二、命题公式的解释或赋值（真值表）
例 4：求下列命题的真值表
(1)? (? p) q
(2) ( p? ( p? q ))? q
(3)? ( p? q )? q
2009-7-29 离散数学 21
二、命题公式的解释或赋值（真值表）
(1)? (? p) q
真值分析如下：
p q? (? p)? q? (? p) q
0 0 0 1 0
0 1 0 0 0
1 0 1 1 1
1 1 1 0 0
表 1.2
2009-7-29 离散数学 22
二、命题公式的解释或赋值（真值表）
(2)(p? ( p? q ))? q
真值分析如下：
p q p? q p? ( p? q ) (p? ( p? q ))? q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
表 1.3
2009-7-29 离散数学 23
二、命题公式的解释或赋值（真值表）
(3)? ( p? q )? q
真值分析如下：
p q p? q? ( p? q )? ( p? q )? q
0 0 1 0 0
0 1 1 0 0
1 0 0 1 0
1 1 1 0 0
表 1.4
2009-7-29 离散数学 24
三、命题公式的类型命题公式 A在各种赋值下取值恒为真，则 A为重言式。
命题公式 A在各种赋值下取值恒为假，则 A为矛盾式。
命题公式 A至少存在一组赋值是成真赋值，则 A为可满足式。
1、重言式 (或永真式 )：
2、矛盾式 (或永假式 )：
3、可满足式：
2009-7-29 离散数学 25
三、命题公式的类型（续）
3、真值表可以用来判断公式的类型：
（ 1） 若真值表最后一列全为 1，则公式为重言式；
（ 2） 若 真值表最后一列全为 0，则公式为矛盾式；
（ 3） 若 真值表最后一列至少有一个 1，则公式为可满足式。
1、可满足式至少存在一组成真赋值。
2、重言式一定是可满足式，反之不真。
从以上定义可以看出以下几点：
2009-7-29 离散数学 26
一、等值演算的概念等值关系是自反的、对称的和传递的，因而为等价关系。
等值演算,按一定方法寻找某个复合命题公式的等值式的过程。
§ 1.3 等值演算等值公式,设 A,B为两命题公式，若等价式 A? B
是重言式，称 A与 B等值。记作,A? B
用真值表可以验证公式等值。
2009-7-29 离散数学 27
例 5：判断命题是否等值
( p? q) 与? p q
表 1.5
真值分析如下：
p q? p? q p? q? ( p? q)? p q
0 0 1 1 0 1 1
0 1 1 0 1 0 1
1 0 0 1 1 0 1
1 1 0 0 1 0 0
不 等 值一、等值演算的概念（续）
2009-7-29 离散数学 28
二、常用的重要等值公式表
1,A (? A)
2,A? A? A
3,A? A? A
4,A? B? B? A
5,A? B? B? A
6,(A? B)? C? A? (B? C)
7,(A? B)? C? A? (B? C)
双重否定律结合律交换律等幂律
2009-7-29 离散数学 29
二、常用的重要等值公式表（续）
分配律零律吸收律德 ·摩根 律
8,A? (B? C )? (A? B)? (A? C)
9,A? (B? C )? (A? B)? (A? C)
10,?(A? B) A B
11,?(A? B) A B
12,A? (A? B)? A
13,A? (A? B)? A
14,A? 1? 1
15,A? 0? 0
2009-7-29 离散数学 30
二、常用的重要等值公式表（续）
同一律归谬论蕴涵等值式排中律
16,A? 0? A
17,A? 1? A
19,A A? 0
20,A? B A? B
21,A? B? (A? B)? (B? A )
22,A? B B A
23,A? B A B
24,(A? B)? (A B ) A
18,A A? 1
矛盾律等价否定等值式等价等值式假言易位
2009-7-29 离散数学 31
以上 24个等值式必须熟记，并注意其中所含的
A,B,C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。
利用 24个基本等值式，不用真值表法也可以推演出很多等值式。
二、常用的重要等值公式表（续）
2009-7-29 离散数学 32
设?(A)是含命题公式 A的命题公式,
(B)是用 B置换了?(A)中的 A之后得到的命题公式。若 A? B,则? (A) (B) 。
此外，在进行等值演算时，常常用到：
置换定理二、常用的重要等值公式表（续）
2009-7-29 离散数学 33
例 6：验证下列等值式
(1) p? (q? r)? ( p? q)? r
(2) p? ( p? q)? ( p q)
解题思想,
可以从左 或右的任一个公式开始演算；演算的每一步都要用置换定理。
三、应用
2009-7-29 离散数学 34
例 6：验证下列等值式
(1) p? (q? r)? ( p? q)? r
p? (? q? r)
( p? q)? r
蕴涵等值式蕴涵等值式结合律德 ·摩根 律蕴涵等值式解,(1)p? (q? r )
(? pq )? r
( p? q)? r
三、应用（续）
2009-7-29 离散数学 35
例 6：验证下列等值式
(2) p? ( p? q)? (p q)
( p? q)? ( pq)
同一律排中律分配律解,(2)? p? 1
三、应用（续）
p? (qq)
2009-7-29 离散数学 36
例 7：判别下列公式的类型
(1) q((? p? q )? p )
(2) ( pp )? ((qq)? r)
(3) ( p? q )p
解题思想,
真值表法和等值演算都可以用来判别公式的类型，
但等值演算更为简单快捷。
三、应用（续）
2009-7-29 离散数学 37
例 7：判别下列公式的类型
(1) q((? p? q )? p )
解,(1)? q((?p? p )? (q? p))
q(0? (q? p))
q(q? p)
q? (?qp)
(qq)p
1p
1
分配律矛盾律同一律德 ·摩根律结合律排中律零律重 言 式三、应用（续）
2009-7-29 离散数学 38
例 7：判别下列公式的类型
(2) ( pp)? ((qq)? r)
1? (0? r)
1? 0
1? 0
0? 0
0
矛盾律等幂律零律排中律蕴涵等值式矛 盾 式三、应用（续）
解,(2)? 1? ((qq)? r)
2009-7-29 离散数学 39
例 7：判别下列公式的类型
(3) ( p? q)p
解,(3)? (?p? q)p
p 吸收律蕴涵等值式真值分析如下,p q? p
0 0 1
0 1 1
1 0 0
1 1 0
可 满 足 式三、应用（续）
2009-7-29 离散数学 40
除了前面我们介绍的 5种基本联结词，这里再给出逻辑设计中常用的 3种：
§ 1.4 联结词的完备集等值关系,p q? ( pq)? (?p? q)
V
1.异或 排斥或 (V ),P,Q两个命题中有一个而且仅有一个成立。 V记作,P Q
2009-7-29 离散数学 41
2,与非,复合命题,p与 q 的否定”称作 p 与 q的与非式，记作,p? q,。
p? q为真当且仅当 p,q不同时为真。
等值关系,p? q ( p? q)
3,或非,复合命题,p或 q 的否定”称作 p 与 q的或非式，记作,p? q,。
p? q为真当且仅当 p,q同时为假。
等值关系,p? q ( p? q)
2009-7-29 离散数学 42
真值表表 1.6
p q p q p? q p? q
0 0 0 1 1
0 1 1 1 0
1 0 1 1 0
1 1 0 0 0
2009-7-29 离散数学 43
冗余联结词和独立联结词,在联结词集合中,如果一个联结词可以由集合中其它的联结词来定义，则称此联结词为冗余联结词，否则称为独立联结词。
例如,{?,?,?} 中的?或?是冗余 联结词,
全功能集,如果任一真值函数 (公式 )，都可以仅用某一联 结词集合中的联结词的命题公式表示，则称该集合为全功能集。 例如,{?,?,?},{?,?},{?,?,?,?}
不含冗余联结词的全功能集称为 极小全功能集 。
2009-7-29 离散数学 44
常见的全功能集（也是极小全功能集）,
{?,? },{?,? },{?,? },{? },{? }
2009-7-29 离散数学 45
又,?(p? q)? 0 的对偶式,?(p? q)? 1如,p? (? r)的对偶式是?p? (q? r)
一、对偶式的概念在常见的基本等值式中，多数公式是成对出现的，
它们相互构成对偶式。
对偶式,在仅含有联结词?,?,?的命题公式 A中，
将? 换成?,?换成?,0换成 1,1换成 0，
所得命题公式称为 A的对偶式。 记作,A*
显然，对偶式是相互的，即 (A*)*= A
§ 1.5 对偶与范式
2009-7-29 离散数学 46
设 A与 A*互为对偶式,P1,P2,…,Pn是出现在 A和 A*中的所有命题变元，如果用 n元函数的形式表达，则有
(1)?A (P1,P2,…,Pn )? A*(?P1,?P2,…,?Pn )
(2) A (?P1,?P2,…,?Pn)A*( P1,P2,…,Pn )
二、关于对偶式的两个定理定理
2009-7-29 离散数学 47
如：设 A (p,q,r) p? (q? r)
二、关于对偶式的两个定理（续）
则?A (p,q,r)(? p? (q? r) )? p? (?qr)
A*(p,q,r) p? (q? r)
A*(?p,?q,?r)? p? (?qr)
于是有?A (p,q,r)? A*(?p,?q,?r)
又 A (?p,?q,?r)? p? (?qr)，
A*(p,q,r)(? p? (q? r) )? p? (?qr)，
于是有 A (?p,?q,?r)A*( p,q,r)
2009-7-29 离散数学 48
设 A与 B为两命题公式，如果 A? B，
则 A*? B*。
二、关于对偶式的两个定理 （ 续）
由此可知,A*为重言式? A为矛盾式
A*为矛盾式?A为重言式
A*为可满足式? A为可满足式
,两公式等值,?,两公式的对偶式等值,
对偶定理
2009-7-29 离散数学 49
仅由有限个命题变元或其否定构成的析取式，如 p? q,? p? q。
三、范式的概念显然：简单析取式是重言式，当且仅当它同时含有一个命题变项及其否定；
简单合取式是矛盾式，当且仅当它同时含有一个命题变项及其否定。
仅由有限个命题变元或其否定构成的合取式，如? pq。
简单析取式：
简单合取式：
2009-7-29 离散数学 50
仅由有限个 简单合取式 构成的 析取式 。
如 A=A1? A2?…? An,Ai (i =1,2,…,n)为简单合取式。
三、范式的概念（续）
由对偶的定义知：析取范式的对偶式为合取范式，合取范式的对偶式为析取范式。
性质,析取范式为矛盾式，当且仅当构成它的每一个简单合取式都是矛盾式；合取范式为重言式，当且仅当构成它的每一个简单析取式都是重言式。
仅由有限个 简单析取式 构成的 合取式 。
如 A=A1? A2?…? An,Ai (i =1,2,…,n)为简单析取式。
析取范式：
合取范式：
2009-7-29 离散数学 51
任一命题公式都存在着与之等值的析取范式和合取范式。
求范式的步骤：
(2)? 的消去或内移。利用 德 ·摩根 律或双重否定律三、范式的概念（续）
范式存在定理
(1) 消去对 {?,?,?}来说冗余的联结词。 {?,?,?}
是全功能集，其他联结词都可用基本等值式消去
(3) 利用分配律。 求析取范式，可利用?对? 的分配律；求合取范式，可利用? 对? 的分配律
2009-7-29 离散数学 52
三、范式的概念（续）
基本等值式：
p? q p? q
p? q? (? p? q)? ( p q )
p q? ( pq )? (?p? q )
p? q ( p? q )
p? q ( p? q )
2009-7-29 离散数学 53
例 8：求命题公式 ( ( p? q )? r )? p 的合取范式和析取范式。
解,(1) 求析取范式
( ( p? q )? r )? p
(( p? q ) r )? p
( p r )? ( q r )? p
p? ( q r )
四、应用
(?( p? q )? r )? p
(?( p? q )? r )? p
2009-7-29 离散数学 54
例 8：求命题公式 ( ( p? q )? r )? p 的合取范式和析取范式。
四、应用（续）
解,(2) 求合取范式
( ( p? q )? r )? p
(( p? q ) r )? p
( p? q? p )? (? r? p )
( p? q)? (? r? p )
2009-7-29 离散数学 55
值得注意的是,任何命题公式的析取范式或合取范式不唯一,因而不能作为命题公式的标准型 。 为此,我们进一步引入,主析取范式,,,主合取范式,
的概念 。 它们是用极小项,极大项来定义的 。
2009-7-29 离散数学 56
含有 n个命题变元的 简单析取式,且具有形式,…
21 nPPP
含有 n个命题变元的 简单合取式,且具有形式,…
21 nPPP
注 1：其中 指 pi或?pi,1? i? n
注 2：极小项、极大项中必含有 n个联结词注 3,一定位于第 i个位置，顺序不能乱
iP
iP
五、主析取范式与主合取范式极小项：
极大项：
2009-7-29 离散数学 57
五、主析取范式与主合取范式（续）
极小项的表示 （以 3个命题变项为例）：
p q r 000 ---- 0,记作 m0
p q? r 001 ---- 1,记作 m1
p? q r 010 ---- 2,记作 m2
p? q? r 011 ---- 3,记作 m3
p q r 100 ---- 4,记作 m4
p q? r 101 ---- 5,记作 m5
p? q r 110 ---- 6,记作 m6
p? q? r 111 ---- 7,记作 m7
成真赋值
2009-7-29 离散数学 58
五、主析取范式与主合取范式（续）
极大项的表示 （以 3个命题变项为例）：
p? q? r 000 ---- 0,记作 M0
p? q r 001 ---- 1,记作 M1
p q? r 010 ---- 2,记作 M2
p q r 011 ---- 3,记作 M3
p? q? r 100 ---- 4,记作 M4
p? q r 101 ---- 5,记作 M5
p q? r 110 ---- 6,记作 M6
p q r 111 ---- 7,记作 M7
成假赋值
2009-7-29 离散数学 59
五、主析取范式与主合取范式（续）
任何命题公式的主析取范式和主合取范式一定存在，并且唯一。
定理主析取范式：
主合取范式：
命题公式 A的析取范式中的简单合取式全是极小项。
特别地约定，矛盾式的主析取范式为 0。
命题公式 A的合取范式中的简单析取式全是极大项。
特别地约定，重言式的主合取范式为 1。
2009-7-29 离散数学 60
(4) 将极小项按从小到大的顺序排列，并用 ∑表示如 m1?m4?m5?∑(1,4,5)
给定命题公式 A的 主析取范式的求解步骤,
五、主析取范式与主合取范式（续）
(1) 求 A的析取范式 A'
(2) 若 A'的某简单合取式 B中不含命题变项 pi 或?pi，
则展开 B如下：
B?B? 1?B? (pipi)?(B? pi)? (Bpi)
(3) 消去重复 出现的命题变项、极小项和矛盾式。
2009-7-29 离散数学 61
(4) 将极大项按从小到大的顺序排列，并用 ∏ 表示如 M1?M4?M5?∏(1,4,5)
给定命题公式 A的 主合取范式的求解步骤,
五、主析取范式与主合取范式（续）
(1) 求 A的合取范式 A'
(2) 若 A'的某简单析取式 B中不含命题变项 pi 或?pi，
则展开 B如下：
B?B? 0?B? (pipi)?(B? pi)? (Bpi)
(3) 消去重复 出现的命题变项、极大项和重言式。
2009-7-29 离散数学 62
例 9：求公式 (( p? r)? q)? (q? p)的主析取范式和主合取范式。
六、应用解,(1) 求主析取范式
(( p? r)? q)? (q? p)
((? p? r)? q)? (? q? p)
((? p? r)? (? q? p))? (q? (? q? p))
((? p q)? (? p? p)? (r q)? (r? p))
((q q)? (q? p))
2009-7-29 离散数学 63
六、应用（续）
(? p q)? (r q)? (r? p)? (q? 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 r))? ((r q)? (p p))
((r? p)? (q q))? ((q? p)? (r r))
m0?m1?m5?m6?m7
m1?m0?m5?m1?m7?m5?m7?m6
∑(0,1,5,6,7)
2009-7-29 离散数学 64
六、应用（续）
(2) 求主合取范式
((p? r)? q)? (q? p)
((? p? r)? q)? (? q? p)
(? p? r? q)? (? q? p)
(? p? q? r)? ((p q)? (r r))
(? p? q? r)? (p q r )? (p q? r)
M4?M3?M2
∏(2,3,4)
2009-7-29 离散数学 65
A为重言式，当且仅当 A的主析取范式含所有极小项
A为矛盾式，当且仅当 A的主析取范式不含任何极小项
A为可满足式，当 A的主析取范式中至少含一个极小项为重言式，当且仅当 的主合取范式不含任何极大项为矛盾式，当且仅当 的主合取范式含所有极大项为可满足式，当 的主合取范式中至少含一个极大项六、应用（续）
主析取范式（主合取范式）的用途：
(2) 判断两命题公式是否等值。通过判断两命题公式的主析取范式（主合取范式）是否相等
(3) 判断命题公式的类型。
(1) 求命题公式的成真和成假赋值。
2009-7-29 离散数学 66
例 10：判断下列命题公式的类型
(1)? ( p? q)? q
(2) (( p? q)? p)? q
六、应用（续）
解,(1)? ( p? q)? q
(? p? q)? q
p q? q
0
矛 盾 式
2009-7-29 离散数学 67
例 10：判断下列命题公式的类型
(1)? ( p? q)? q
(2) (( p? q)? p)? q
六、应用（续）
((? p? q)? p)? q
解,(2) (( p? q)? p)? q
( p q) p? q
( p q)? (? p? q)? (? p q)? ( p? q)
重言式
m2?m1?m0?m3?∑(0,1,2,3)
2009-7-29 离散数学 68
六、应用（续）
主析取范式和主合取范式的关系：
设命题公式 含 n个命题变项，其主析取范式中含 k个极小项 …,不含极小项 …,
则主合取范式中含极大项 …
kiii mmm,,,21 knjjj mmm?221,,,
knjjj
MMM
221
,,,
如,A中含 3个命题变项，
A? m0?m1?m6?m7?∑(0,1,6,7)
则 A? M2? M3? M4?M5?∏(2,3,4,5)
2009-7-29 离散数学 69
一、推理的概念推理,从前提推出结论的思维过程。
前提指已知的命题公式，结论是从前提出发按照一定的推理规则推出的命题公式。
逻辑结论 （有效结论）：若 ( A1? A2?…? An )? B
为重言式,则称 A1,A2,…,An推结论 B的推理正确，
B是 A1,A2,…,An的逻辑结论或有效结论。
并记之为 (A1? A2?…? An )? B
§ 1.6 推理理论
2009-7-29 离散数学 70
例 11：判断下面各推理是否正确
(1) 如果天气凉快，小王就不去游泳。天气凉快,
所以小王没去游泳。
(2) 如果我上街，我一定去新华书店。我没上街，
所以我没去新华书店。
二、应用解题思想,
(1) 将命题符号化；
(2) 写出前提、结论和推理的形式结构；
(3) 用真值表法、
等值演算或主析取范式法进行判断。
2009-7-29 离散数学 71
(1) 如果天气凉快，小王就不去游泳。天气凉快,
所以小王没去游泳。
二、应用（续）
解：设 p：天气凉快,q：小王去游泳前提,p q,p
结论,? q
推理的形式结构为
(( p q)? p) q (*)
2009-7-29 离散数学 72
下面判断 (*)式是否为重言式二、应用（续）
(( 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)
m3?m1?m0?m2
推理正确
∑(0,1,2,3)
2009-7-29 离散数学 73
(2) 如果我上街，我一定去新华书店。我没上街，
所以我没去新华书店。
二、应用（续）
解：设 p：我上街,q：我去新华书店前提,p? q,? p
结论,? q
推理的形式结构为
((p? q) p) q (**)
2009-7-29 离散数学 74
下面判断 (**)式是否为重言式二、应用（续）
((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)
m2?m3?m0
推理不正确
∑(0,2,3)
2009-7-29 离散数学 75
三、构造证明法推理规则,在推理过程中，构造证明必须在给定的规则下进行，常用的推理如下：
(1) 前提引入规则,证明的任何步骤上,都可引入前提；
证明,描述推理过程的命题公式序列。
(2) 结论引入规则：证明的任何步骤上,所证明的结论都可作为后续证明的前提；
(3) 置换规则：证明的任何步骤上,命题公式中的任何子命题公式都可以用与之等值的命题公式置换；
2009-7-29 离散数学 76
(4) 假言推理规则,A? B,A |= B
三、构造证明法（续）
(5) 附加规则,A |= A? B
(8) 假言三段论规则,A? B,B? C |= A? C
(11)合取引入规则,A,B |= A? B
(6) 化简规则,A? B |= B
(7) 拒取式规则,A? B,? B |=? A
(10)构造性二难规则,A? B,C? D,A? C |= B? D
(9) 析取三段论规则,A? B,? B |= A
2009-7-29 离散数学 77
例 12：构造下列推理的证明
(1) 前提,p? r,q? s,p? q
结论,r? s
(2) 前提,p? q,p r,s? t,? s? r,? t
结论,q
四、应用
2009-7-29 离散数学 78
(1) 前提,p? r,q? s,p? q 结论,r? s
四、应用（续）
证明,① p? r
② q? s
③ p? q
④ r? s
前提引入前提引入前提引入
①②③ 构造性二难
2009-7-29 离散数学 79
(2) 前提,p? q,p r,s? t,? s? r,? t 结论,q
四、应用（续）
证明,①? t
② s? t
③? s
④? s? r
前提引入前提引入
①② 拒取式
⑦⑧ 析取三段论
⑤ r
⑥ p r
⑦? p
⑧ p? q
⑨ q
前提引入
⑤⑥ 拒取式前提引入前提引入
③ ④ 假言推理
2009-7-29 离散数学 80
例 13,公安局受理某单位发生的一桩案件，已获取如下事实：
(1) 疑犯甲或疑犯乙，至少有一人参与作案；
(2) 如果甲作案，则作案不在上班时间；
(3) 如果乙的证词正确，则大门还未上锁；
(4) 如果乙的证词不正确，则作案发生在上班时间；
(5) 已证实大门上了锁；
试判断谁是作案人？写出推理过程。
四、应用（续）
2009-7-29 离散数学 81
解题思想,将命题符号化； 写出前提和可能结论；
使用构造证明法推演出正确结论。
四、应用（续）
解,设 p：甲作案； q：乙作案；
r：作案发生在上班时间；
s：乙证词正确；
t：大门已上锁。
2009-7-29 离散数学 82
例 13,公安局受理某单位发生的一桩案件，已获取如下事实：
(1) 疑犯甲或疑犯乙，至少有一人参与作案；
(2) 如果甲作案，则作案不在上班时间；
(3) 如果乙的证词正确，则大门还未上锁；
(4) 如果乙的证词不正确，则作案发生在上班时间；
(5) 已证实大门上了锁；
试判断谁是作案人？写出推理过程。
四、应用（续）
p? q
p r
s t
s? r
t
2009-7-29 离散数学 83
前提,p? q,p r,s t,? s? r,t
结论：待定，但只有两种可能（ p或 q）
四、应用（续）
证明,① s t
② t
③? s
④? s? r
前提引入前提引入
①② 拒取式
⑦⑧ 析取三段论
⑤ r
⑥ p r
⑦? p
⑧ p? q
⑨ q
前提引入
③ ④ 假言推理
⑤⑥ 拒取式前提引入前提引入乙作案
2009-7-29 离散数学 84
1,附加前提证明法当要证明的结论是一蕴涵式时，通过等值演算将结论中的前件变成前提，再证明该命题公式。
五、构造证明的技巧
(A1?A2?…?An)?(A?B)? (A1?A2?…?An?A)?B
2,归谬法当要证明结论 B时，将?B作为前提使用，推出矛盾的证明方法。
(A1? A2?…? An)? B (A1? A2?…? An B)
2009-7-29 离散数学 85
例 14：构造下列推理的证明
(1) 前提,p? ( q? r ),? s? p,q
结论,s? r
(2) 前提,p? (? (r? s) q),p,? s
结论,? q
六、应用
2009-7-29 离散数学 86
(1) 前提,p? ( q? r ),? s? p,q 结论,s? r
六、应用（续）
证明,①? s? p
② s
③ p
④ p? ( q? r )
前提引入附加前提引入
⑤ q? r
⑥ q
⑦ r
③ ④ 假言推理
⑤⑥ 假言推理
①② 析取三段论前提引入前提引入
2009-7-29 离散数学 87
(2) 前提,p? (? (r? s) q),p,? s 结论,? q
六、应用（续）
证明,① p? (? (r? s) q)
② p
③? (r? s) q
④? (? q)
前提引入
⑤ q
⑥ r? s
⑦ s
③⑤ 拒取式
①② 假言推理否定结论引入
⑥ 化简
⑧? s
⑦⑧ 合取⑨ s s
④ 置换前提引入前提引入
逻辑学,研究思维 (或推理 )的形式结构和规律的学科。利用数学方法研究思维 (或推理 )的形式结构和规律的学科，称作数理逻辑。
数理逻辑数理逻辑的基本内容,命题逻辑 (演算 )、
谓词逻辑 。 它们对电子元件设计和性质分析,
对逻辑程序设计语言的研制具有十分重要的意义 。
2009-7-29 离散数学 2
第一章 命题逻辑
§ 1.1 命题与联结词
§ 1.2 命题公式及其赋值
§ 1.3 等值演算
§ 1.4 联结词的完备集
§ 1.5 对偶与范式
§ 1.6 推理理论
2009-7-29 离散数学 3
一、命题的概念命题,能判断真假的陈述句。这种判断只有两种可能，一种是正确的判断，一种是错误的判断。
§ 1.1 命题符号化及联结词命题真值,判断为正确的命题称其命题真值为真 (1) ；
判断为错误的命题称其命题真值为假 (0) ；
命题是具有唯一真值的陈述句。
2009-7-29 离散数学 4
例 1 判断下列句子中哪些是命题。
(1) 4是素数。
(2) 2 + 3 = 5。
(3) 雪是黑色的。
(4) 3能被 2整除。
(5) 2050年元旦是晴天。
(6) 5x + 1 > 11。
(7) 这朵花真美丽呀！
(8) 明天下午开会吗？
(9) 我正在说假话。
(是 )
(是 )
(是 )
(是 )
(是 )
(否 )
(否 )
(否 )
(否 )
2009-7-29 离散数学 5
解题思想：判断一个句子是否为命题，首先看它是否为陈述句,其次看它的真值是否唯一。
2009-7-29 离散数学 6
二、与命题相关的几个概念
1,简单命题 (或原子命题 )：
命题为简单的陈述句，不能分解成更简单的句子。一般用小写的英文字母 p,q,r,… 表示。
2,命题常项 (或命题常元 )：
由于简单命题的真值确定，故又称之为命题常项或命题常元。
如例 1中的陈述句 (1) (2) (3) (4) (5)。
2009-7-29 离散数学 7
二、与命题相关的几个概念（续）
3,命题变项 (或命题变元 )：
真值可以变化的简单陈述句，但它不是命题,也可以用 p,q,r等 表示。
如例 1中的陈述句 (6) (5x + 1 > 11)。
4,复合命题：
由简单命题用联结词联结而成的命题。
命题逻辑主要就是研究复合命题。
5,命题的符号化：
用符号来表示命题。
2009-7-29 离散数学 8
三、联结词先看一个例子：
例 2：判断下列命题是否为复合命题，说出其联结词。
(1) 3不是偶数。
(2) 2是 偶 素数。
(3) 2或 4是素数。
(4) 如果 2是素数,3也是素数。
(5) 2是素数 当且仅当 3也是素数。
(非 )
(且 )
(或 )
(如果 …,则 … )
(当且仅当 )
2009-7-29 离散数学 9
三、联结词（续）
常见的基本联结词：
1、否定联结词,?,,读作“非”。
复合命题“非 p”称作 p 的否定式，记作,? p,。
p 为真当且仅当 p为假。
在例 2(1)中，设 p表示,3是偶数,,则?p 表示,3
不是偶数,。显然,p真值为 0,?p 真值为 1 。
2009-7-29 离散数学 10
三、联结词（续）
2、合取联结词,?,,读作“合取”。
复合命题,p并且 q,称作 p 与 q 的合取式，记,p? q,。
p? q 为真当且仅当 p与 q 同时为真。
在例 2(2)中，设 p 表示,2是素数,,q 表示,2是偶数,,则 p? q 表示,2是偶素数,。因为 p和 q 的 真值均为 1,所以 p? q 的 真值为 1。
联结词“既 … 又 …”,“不但 … 而且 …”,“虽然 …
但是 …” 等，都可符号化为? 。
2009-7-29 离散数学 11
三、联结词（续）
3、析取联结词,?,,读作“析取”。
复合命题,p或 q,称作 p与 q 的析取式，记作,p? q,。
p? q 为真当且仅当 p 与 q 中至少一个为真。
例 2(3)中，设 p 表示,2是素数,,q 表示,4是素数,,则 p? q 表示,2或 4是素数,。
注意：,或,的二义性。如命题：派小王或小李中的一人去开会，应符号化为 ( p q )? (? p? q ),
这类“或”表达的是排斥或。
2009-7-29 离散数学 12
三、联结词（续）
4、蕴涵联结词,?,,读作“蕴 涵,。
复合命题,如果 p，则 q,称作 p 与 q 的蕴 涵 式，记作
,p? q,。 其中 p 称为蕴 涵 式的前件,q 称为蕴 涵式的后件。 p? q 为假当且仅当 p 为真且 q 为假。
例 2(4)中，设 p 表示,2是素数,,q 表示,3是素数,,则 p? q 表示,如果 2是素数，则 3也是素数,。
联结词“只要 p 就 q,，,p 仅当 q,，“只有 q
才
p,等，都可符号化为 p? q 。
2009-7-29 离散数学 13
三、联结词（续）
5、等价联结词,?,,读作“等价”。
复合命题,p 当且仅当 q,称作 p 与 q 的等价式，记作,p? q,。 p? q 为真当且仅当 p 与 q 真值相同。
例 2(5)中，设 p 表示,2是素数,,q 表示,3是素数,,则 p? q 表示,2是素数 当且仅当 3是素数,,由于 p,q的真值分别为 0,1，所以 p?q的真值为 0。
2009-7-29 离散数学 14
真值表利用以上 5种联结词,可将复合命题符号化,进而正确分析出复合命题的真值 。 基本真值表如下：
p q? p p? qp? qp? qp? q
0 0
0 1
1 0
1 1
1
1
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1
0
0
1
表 1.1
2009-7-29 离散数学 15
(1) 李平不是不聪明，而是不用功 。
(2) 李文和李武是兄弟。
(3) 只有不下雨，我才骑自行车上班 。
(4) 如果下雨，我就不骑自行车上班 。
(5) 若 2 + 2＝ 4，则太阳从西方升起。
设 p:2+2=4,q:太阳从西方升起,则符号化为 p? q
例 3 将下列命题符号化设 p:李文和李武是兄弟，则符号化为 p
设 p:天下雨,q:我骑自行车上班,? p是 q的必要条件则符号化为 q p
设 p:天下雨,q:我骑自行车上班,则符号化为 p q
设 p:李平聪明,q:李平用功,则符号化为?(?p) q
解题步骤,
(1) 分析出各简单命题，并符号化；
(2) 使用合适的联结词，把简单命题逐个联结起来，组成一复合命题的符号化形式。
2009-7-29 离散数学 16
例 3 将下列命题符号化 （续）
(6) 2 + 2? 4，当且仅当 3不是奇数 。
(7) 小王现在在宿舍或在图书馆。
(8) 选小王或小李中的一人当班长。
(9) 如果我上街，我就去书店看看，除非我很累。
(10)王一乐是计算机系的学生,他生于 1968年或 1969
年,他是三好学生。
设 p:2 + 2 = 4,q:3是奇数,则符号化为?p q
设 p:小王在宿舍,q:小王在图书馆,符号化为 p? q
设 p:选小王当班长,q:选小李当班长,则符号化为 (p q)? (? p? q)
设 p:我上街,q:我去书店看看,r:我很累，则符号化为?r? (p? q)
这里的,或,本来是排斥或，排斥或一般不能直接用,?” 联结，但两个命题不能同时为真时例外，因此,命题可符号化为 p? q,
其中 p:小王在宿舍,q:小王在图书馆设 p:王一乐是计算机系的学生,q:他生于
1968年,r,他生于 1969年,s：他是三好学生，则符号化为 p? (q? r)? s
2009-7-29 离散数学 17
合式公式：
一、命题公式的概念
§ 1.2 命题公式及其赋值
(1) 单个命题常项或变项 p,q,…,0,1 是合式公式；
(2) 若 A是合式公式，则?A也是合式公式；
(3) 若 A,B是合式公式，则 (A? B),(A? B),
(A? B),(A? B)是合式公式 ;
合式公式即称为命题公式。
(4) 只有有限次地应用 (1) ～ (3)组成的符号串才是合式公式。
2009-7-29 离散数学 18
一个含有命题变项的命题公式的真值是不确定的，
只有用指定的命题常项代替后真值才唯一确定。
二、命题公式的解释或赋值设 A为一命题 公式,p1,p2,…,pn为出现在 A中的所有的命题变项。给 p1,p2,…,pn指定一组真值，
称为对 A的一个 赋值或解释 。
若指定的一组真值使命题公式 A的真值为 1，则称这组赋值为 A的 成真赋值 ；若使 A的真值为 0，则称这组赋值为 A的 成假赋值 。
将命题公式 A在所有赋值下的取值情况列成表，称为 A的 真值表 。
2009-7-29 离散数学 19
(3)对应每个赋值，计算命题公式各层次的值，直到最后计算出命题公式的值。
二、命题公式的解释或赋值（真值表）
构造真值表的步骤：
命题运算的优先级顺序,(1)先括号 (2)? (3)?,
(4)? (5)? (6)从左至右
(1)找出命题公式中所有命题变项,p1,p2,…,pn,
列出所有可能的赋值 (2n个 )。
(2)按从低到高的顺序列出命题公式的各个运算层次。
2009-7-29 离散数学 20
二、命题公式的解释或赋值（真值表）
例 4：求下列命题的真值表
(1)? (? p) q
(2) ( p? ( p? q ))? q
(3)? ( p? q )? q
2009-7-29 离散数学 21
二、命题公式的解释或赋值（真值表）
(1)? (? p) q
真值分析如下：
p q? (? p)? q? (? p) q
0 0 0 1 0
0 1 0 0 0
1 0 1 1 1
1 1 1 0 0
表 1.2
2009-7-29 离散数学 22
二、命题公式的解释或赋值（真值表）
(2)(p? ( p? q ))? q
真值分析如下：
p q p? q p? ( p? q ) (p? ( p? q ))? q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
表 1.3
2009-7-29 离散数学 23
二、命题公式的解释或赋值（真值表）
(3)? ( p? q )? q
真值分析如下：
p q p? q? ( p? q )? ( p? q )? q
0 0 1 0 0
0 1 1 0 0
1 0 0 1 0
1 1 1 0 0
表 1.4
2009-7-29 离散数学 24
三、命题公式的类型命题公式 A在各种赋值下取值恒为真，则 A为重言式。
命题公式 A在各种赋值下取值恒为假，则 A为矛盾式。
命题公式 A至少存在一组赋值是成真赋值，则 A为可满足式。
1、重言式 (或永真式 )：
2、矛盾式 (或永假式 )：
3、可满足式：
2009-7-29 离散数学 25
三、命题公式的类型（续）
3、真值表可以用来判断公式的类型：
（ 1） 若真值表最后一列全为 1，则公式为重言式；
（ 2） 若 真值表最后一列全为 0，则公式为矛盾式；
（ 3） 若 真值表最后一列至少有一个 1，则公式为可满足式。
1、可满足式至少存在一组成真赋值。
2、重言式一定是可满足式，反之不真。
从以上定义可以看出以下几点：
2009-7-29 离散数学 26
一、等值演算的概念等值关系是自反的、对称的和传递的，因而为等价关系。
等值演算,按一定方法寻找某个复合命题公式的等值式的过程。
§ 1.3 等值演算等值公式,设 A,B为两命题公式，若等价式 A? B
是重言式，称 A与 B等值。记作,A? B
用真值表可以验证公式等值。
2009-7-29 离散数学 27
例 5：判断命题是否等值
( p? q) 与? p q
表 1.5
真值分析如下：
p q? p? q p? q? ( p? q)? p q
0 0 1 1 0 1 1
0 1 1 0 1 0 1
1 0 0 1 1 0 1
1 1 0 0 1 0 0
不 等 值一、等值演算的概念（续）
2009-7-29 离散数学 28
二、常用的重要等值公式表
1,A (? A)
2,A? A? A
3,A? A? A
4,A? B? B? A
5,A? B? B? A
6,(A? B)? C? A? (B? C)
7,(A? B)? C? A? (B? C)
双重否定律结合律交换律等幂律
2009-7-29 离散数学 29
二、常用的重要等值公式表（续）
分配律零律吸收律德 ·摩根 律
8,A? (B? C )? (A? B)? (A? C)
9,A? (B? C )? (A? B)? (A? C)
10,?(A? B) A B
11,?(A? B) A B
12,A? (A? B)? A
13,A? (A? B)? A
14,A? 1? 1
15,A? 0? 0
2009-7-29 离散数学 30
二、常用的重要等值公式表（续）
同一律归谬论蕴涵等值式排中律
16,A? 0? A
17,A? 1? A
19,A A? 0
20,A? B A? B
21,A? B? (A? B)? (B? A )
22,A? B B A
23,A? B A B
24,(A? B)? (A B ) A
18,A A? 1
矛盾律等价否定等值式等价等值式假言易位
2009-7-29 离散数学 31
以上 24个等值式必须熟记，并注意其中所含的
A,B,C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。
利用 24个基本等值式，不用真值表法也可以推演出很多等值式。
二、常用的重要等值公式表（续）
2009-7-29 离散数学 32
设?(A)是含命题公式 A的命题公式,
(B)是用 B置换了?(A)中的 A之后得到的命题公式。若 A? B,则? (A) (B) 。
此外，在进行等值演算时，常常用到：
置换定理二、常用的重要等值公式表（续）
2009-7-29 离散数学 33
例 6：验证下列等值式
(1) p? (q? r)? ( p? q)? r
(2) p? ( p? q)? ( p q)
解题思想,
可以从左 或右的任一个公式开始演算；演算的每一步都要用置换定理。
三、应用
2009-7-29 离散数学 34
例 6：验证下列等值式
(1) p? (q? r)? ( p? q)? r
p? (? q? r)
( p? q)? r
蕴涵等值式蕴涵等值式结合律德 ·摩根 律蕴涵等值式解,(1)p? (q? r )
(? pq )? r
( p? q)? r
三、应用（续）
2009-7-29 离散数学 35
例 6：验证下列等值式
(2) p? ( p? q)? (p q)
( p? q)? ( pq)
同一律排中律分配律解,(2)? p? 1
三、应用（续）
p? (qq)
2009-7-29 离散数学 36
例 7：判别下列公式的类型
(1) q((? p? q )? p )
(2) ( pp )? ((qq)? r)
(3) ( p? q )p
解题思想,
真值表法和等值演算都可以用来判别公式的类型，
但等值演算更为简单快捷。
三、应用（续）
2009-7-29 离散数学 37
例 7：判别下列公式的类型
(1) q((? p? q )? p )
解,(1)? q((?p? p )? (q? p))
q(0? (q? p))
q(q? p)
q? (?qp)
(qq)p
1p
1
分配律矛盾律同一律德 ·摩根律结合律排中律零律重 言 式三、应用（续）
2009-7-29 离散数学 38
例 7：判别下列公式的类型
(2) ( pp)? ((qq)? r)
1? (0? r)
1? 0
1? 0
0? 0
0
矛盾律等幂律零律排中律蕴涵等值式矛 盾 式三、应用（续）
解,(2)? 1? ((qq)? r)
2009-7-29 离散数学 39
例 7：判别下列公式的类型
(3) ( p? q)p
解,(3)? (?p? q)p
p 吸收律蕴涵等值式真值分析如下,p q? p
0 0 1
0 1 1
1 0 0
1 1 0
可 满 足 式三、应用（续）
2009-7-29 离散数学 40
除了前面我们介绍的 5种基本联结词，这里再给出逻辑设计中常用的 3种：
§ 1.4 联结词的完备集等值关系,p q? ( pq)? (?p? q)
V
1.异或 排斥或 (V ),P,Q两个命题中有一个而且仅有一个成立。 V记作,P Q
2009-7-29 离散数学 41
2,与非,复合命题,p与 q 的否定”称作 p 与 q的与非式，记作,p? q,。
p? q为真当且仅当 p,q不同时为真。
等值关系,p? q ( p? q)
3,或非,复合命题,p或 q 的否定”称作 p 与 q的或非式，记作,p? q,。
p? q为真当且仅当 p,q同时为假。
等值关系,p? q ( p? q)
2009-7-29 离散数学 42
真值表表 1.6
p q p q p? q p? q
0 0 0 1 1
0 1 1 1 0
1 0 1 1 0
1 1 0 0 0
2009-7-29 离散数学 43
冗余联结词和独立联结词,在联结词集合中,如果一个联结词可以由集合中其它的联结词来定义，则称此联结词为冗余联结词，否则称为独立联结词。
例如,{?,?,?} 中的?或?是冗余 联结词,
全功能集,如果任一真值函数 (公式 )，都可以仅用某一联 结词集合中的联结词的命题公式表示，则称该集合为全功能集。 例如,{?,?,?},{?,?},{?,?,?,?}
不含冗余联结词的全功能集称为 极小全功能集 。
2009-7-29 离散数学 44
常见的全功能集（也是极小全功能集）,
{?,? },{?,? },{?,? },{? },{? }
2009-7-29 离散数学 45
又,?(p? q)? 0 的对偶式,?(p? q)? 1如,p? (? r)的对偶式是?p? (q? r)
一、对偶式的概念在常见的基本等值式中，多数公式是成对出现的，
它们相互构成对偶式。
对偶式,在仅含有联结词?,?,?的命题公式 A中，
将? 换成?,?换成?,0换成 1,1换成 0，
所得命题公式称为 A的对偶式。 记作,A*
显然，对偶式是相互的，即 (A*)*= A
§ 1.5 对偶与范式
2009-7-29 离散数学 46
设 A与 A*互为对偶式,P1,P2,…,Pn是出现在 A和 A*中的所有命题变元，如果用 n元函数的形式表达，则有
(1)?A (P1,P2,…,Pn )? A*(?P1,?P2,…,?Pn )
(2) A (?P1,?P2,…,?Pn)A*( P1,P2,…,Pn )
二、关于对偶式的两个定理定理
2009-7-29 离散数学 47
如：设 A (p,q,r) p? (q? r)
二、关于对偶式的两个定理（续）
则?A (p,q,r)(? p? (q? r) )? p? (?qr)
A*(p,q,r) p? (q? r)
A*(?p,?q,?r)? p? (?qr)
于是有?A (p,q,r)? A*(?p,?q,?r)
又 A (?p,?q,?r)? p? (?qr)，
A*(p,q,r)(? p? (q? r) )? p? (?qr)，
于是有 A (?p,?q,?r)A*( p,q,r)
2009-7-29 离散数学 48
设 A与 B为两命题公式，如果 A? B，
则 A*? B*。
二、关于对偶式的两个定理 （ 续）
由此可知,A*为重言式? A为矛盾式
A*为矛盾式?A为重言式
A*为可满足式? A为可满足式
,两公式等值,?,两公式的对偶式等值,
对偶定理
2009-7-29 离散数学 49
仅由有限个命题变元或其否定构成的析取式，如 p? q,? p? q。
三、范式的概念显然：简单析取式是重言式，当且仅当它同时含有一个命题变项及其否定；
简单合取式是矛盾式，当且仅当它同时含有一个命题变项及其否定。
仅由有限个命题变元或其否定构成的合取式，如? pq。
简单析取式：
简单合取式：
2009-7-29 离散数学 50
仅由有限个 简单合取式 构成的 析取式 。
如 A=A1? A2?…? An,Ai (i =1,2,…,n)为简单合取式。
三、范式的概念（续）
由对偶的定义知：析取范式的对偶式为合取范式，合取范式的对偶式为析取范式。
性质,析取范式为矛盾式，当且仅当构成它的每一个简单合取式都是矛盾式；合取范式为重言式，当且仅当构成它的每一个简单析取式都是重言式。
仅由有限个 简单析取式 构成的 合取式 。
如 A=A1? A2?…? An,Ai (i =1,2,…,n)为简单析取式。
析取范式：
合取范式：
2009-7-29 离散数学 51
任一命题公式都存在着与之等值的析取范式和合取范式。
求范式的步骤：
(2)? 的消去或内移。利用 德 ·摩根 律或双重否定律三、范式的概念（续）
范式存在定理
(1) 消去对 {?,?,?}来说冗余的联结词。 {?,?,?}
是全功能集，其他联结词都可用基本等值式消去
(3) 利用分配律。 求析取范式，可利用?对? 的分配律；求合取范式，可利用? 对? 的分配律
2009-7-29 离散数学 52
三、范式的概念（续）
基本等值式：
p? q p? q
p? q? (? p? q)? ( p q )
p q? ( pq )? (?p? q )
p? q ( p? q )
p? q ( p? q )
2009-7-29 离散数学 53
例 8：求命题公式 ( ( p? q )? r )? p 的合取范式和析取范式。
解,(1) 求析取范式
( ( p? q )? r )? p
(( p? q ) r )? p
( p r )? ( q r )? p
p? ( q r )
四、应用
(?( p? q )? r )? p
(?( p? q )? r )? p
2009-7-29 离散数学 54
例 8：求命题公式 ( ( p? q )? r )? p 的合取范式和析取范式。
四、应用（续）
解,(2) 求合取范式
( ( p? q )? r )? p
(( p? q ) r )? p
( p? q? p )? (? r? p )
( p? q)? (? r? p )
2009-7-29 离散数学 55
值得注意的是,任何命题公式的析取范式或合取范式不唯一,因而不能作为命题公式的标准型 。 为此,我们进一步引入,主析取范式,,,主合取范式,
的概念 。 它们是用极小项,极大项来定义的 。
2009-7-29 离散数学 56
含有 n个命题变元的 简单析取式,且具有形式,…
21 nPPP
含有 n个命题变元的 简单合取式,且具有形式,…
21 nPPP
注 1：其中 指 pi或?pi,1? i? n
注 2：极小项、极大项中必含有 n个联结词注 3,一定位于第 i个位置，顺序不能乱
iP
iP
五、主析取范式与主合取范式极小项：
极大项：
2009-7-29 离散数学 57
五、主析取范式与主合取范式（续）
极小项的表示 （以 3个命题变项为例）：
p q r 000 ---- 0,记作 m0
p q? r 001 ---- 1,记作 m1
p? q r 010 ---- 2,记作 m2
p? q? r 011 ---- 3,记作 m3
p q r 100 ---- 4,记作 m4
p q? r 101 ---- 5,记作 m5
p? q r 110 ---- 6,记作 m6
p? q? r 111 ---- 7,记作 m7
成真赋值
2009-7-29 离散数学 58
五、主析取范式与主合取范式（续）
极大项的表示 （以 3个命题变项为例）：
p? q? r 000 ---- 0,记作 M0
p? q r 001 ---- 1,记作 M1
p q? r 010 ---- 2,记作 M2
p q r 011 ---- 3,记作 M3
p? q? r 100 ---- 4,记作 M4
p? q r 101 ---- 5,记作 M5
p q? r 110 ---- 6,记作 M6
p q r 111 ---- 7,记作 M7
成假赋值
2009-7-29 离散数学 59
五、主析取范式与主合取范式（续）
任何命题公式的主析取范式和主合取范式一定存在，并且唯一。
定理主析取范式：
主合取范式：
命题公式 A的析取范式中的简单合取式全是极小项。
特别地约定，矛盾式的主析取范式为 0。
命题公式 A的合取范式中的简单析取式全是极大项。
特别地约定，重言式的主合取范式为 1。
2009-7-29 离散数学 60
(4) 将极小项按从小到大的顺序排列，并用 ∑表示如 m1?m4?m5?∑(1,4,5)
给定命题公式 A的 主析取范式的求解步骤,
五、主析取范式与主合取范式（续）
(1) 求 A的析取范式 A'
(2) 若 A'的某简单合取式 B中不含命题变项 pi 或?pi，
则展开 B如下：
B?B? 1?B? (pipi)?(B? pi)? (Bpi)
(3) 消去重复 出现的命题变项、极小项和矛盾式。
2009-7-29 离散数学 61
(4) 将极大项按从小到大的顺序排列，并用 ∏ 表示如 M1?M4?M5?∏(1,4,5)
给定命题公式 A的 主合取范式的求解步骤,
五、主析取范式与主合取范式（续）
(1) 求 A的合取范式 A'
(2) 若 A'的某简单析取式 B中不含命题变项 pi 或?pi，
则展开 B如下：
B?B? 0?B? (pipi)?(B? pi)? (Bpi)
(3) 消去重复 出现的命题变项、极大项和重言式。
2009-7-29 离散数学 62
例 9：求公式 (( p? r)? q)? (q? p)的主析取范式和主合取范式。
六、应用解,(1) 求主析取范式
(( p? r)? q)? (q? p)
((? p? r)? q)? (? q? p)
((? p? r)? (? q? p))? (q? (? q? p))
((? p q)? (? p? p)? (r q)? (r? p))
((q q)? (q? p))
2009-7-29 离散数学 63
六、应用（续）
(? p q)? (r q)? (r? p)? (q? 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 r))? ((r q)? (p p))
((r? p)? (q q))? ((q? p)? (r r))
m0?m1?m5?m6?m7
m1?m0?m5?m1?m7?m5?m7?m6
∑(0,1,5,6,7)
2009-7-29 离散数学 64
六、应用（续）
(2) 求主合取范式
((p? r)? q)? (q? p)
((? p? r)? q)? (? q? p)
(? p? r? q)? (? q? p)
(? p? q? r)? ((p q)? (r r))
(? p? q? r)? (p q r )? (p q? r)
M4?M3?M2
∏(2,3,4)
2009-7-29 离散数学 65
A为重言式，当且仅当 A的主析取范式含所有极小项
A为矛盾式，当且仅当 A的主析取范式不含任何极小项
A为可满足式，当 A的主析取范式中至少含一个极小项为重言式，当且仅当 的主合取范式不含任何极大项为矛盾式，当且仅当 的主合取范式含所有极大项为可满足式，当 的主合取范式中至少含一个极大项六、应用（续）
主析取范式（主合取范式）的用途：
(2) 判断两命题公式是否等值。通过判断两命题公式的主析取范式（主合取范式）是否相等
(3) 判断命题公式的类型。
(1) 求命题公式的成真和成假赋值。
2009-7-29 离散数学 66
例 10：判断下列命题公式的类型
(1)? ( p? q)? q
(2) (( p? q)? p)? q
六、应用（续）
解,(1)? ( p? q)? q
(? p? q)? q
p q? q
0
矛 盾 式
2009-7-29 离散数学 67
例 10：判断下列命题公式的类型
(1)? ( p? q)? q
(2) (( p? q)? p)? q
六、应用（续）
((? p? q)? p)? q
解,(2) (( p? q)? p)? q
( p q) p? q
( p q)? (? p? q)? (? p q)? ( p? q)
重言式
m2?m1?m0?m3?∑(0,1,2,3)
2009-7-29 离散数学 68
六、应用（续）
主析取范式和主合取范式的关系：
设命题公式 含 n个命题变项，其主析取范式中含 k个极小项 …,不含极小项 …,
则主合取范式中含极大项 …
kiii mmm,,,21 knjjj mmm?221,,,
knjjj
MMM
221
,,,
如,A中含 3个命题变项，
A? m0?m1?m6?m7?∑(0,1,6,7)
则 A? M2? M3? M4?M5?∏(2,3,4,5)
2009-7-29 离散数学 69
一、推理的概念推理,从前提推出结论的思维过程。
前提指已知的命题公式，结论是从前提出发按照一定的推理规则推出的命题公式。
逻辑结论 （有效结论）：若 ( A1? A2?…? An )? B
为重言式,则称 A1,A2,…,An推结论 B的推理正确，
B是 A1,A2,…,An的逻辑结论或有效结论。
并记之为 (A1? A2?…? An )? B
§ 1.6 推理理论
2009-7-29 离散数学 70
例 11：判断下面各推理是否正确
(1) 如果天气凉快，小王就不去游泳。天气凉快,
所以小王没去游泳。
(2) 如果我上街，我一定去新华书店。我没上街，
所以我没去新华书店。
二、应用解题思想,
(1) 将命题符号化；
(2) 写出前提、结论和推理的形式结构；
(3) 用真值表法、
等值演算或主析取范式法进行判断。
2009-7-29 离散数学 71
(1) 如果天气凉快，小王就不去游泳。天气凉快,
所以小王没去游泳。
二、应用（续）
解：设 p：天气凉快,q：小王去游泳前提,p q,p
结论,? q
推理的形式结构为
(( p q)? p) q (*)
2009-7-29 离散数学 72
下面判断 (*)式是否为重言式二、应用（续）
(( 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)
m3?m1?m0?m2
推理正确
∑(0,1,2,3)
2009-7-29 离散数学 73
(2) 如果我上街，我一定去新华书店。我没上街，
所以我没去新华书店。
二、应用（续）
解：设 p：我上街,q：我去新华书店前提,p? q,? p
结论,? q
推理的形式结构为
((p? q) p) q (**)
2009-7-29 离散数学 74
下面判断 (**)式是否为重言式二、应用（续）
((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)
m2?m3?m0
推理不正确
∑(0,2,3)
2009-7-29 离散数学 75
三、构造证明法推理规则,在推理过程中，构造证明必须在给定的规则下进行，常用的推理如下：
(1) 前提引入规则,证明的任何步骤上,都可引入前提；
证明,描述推理过程的命题公式序列。
(2) 结论引入规则：证明的任何步骤上,所证明的结论都可作为后续证明的前提；
(3) 置换规则：证明的任何步骤上,命题公式中的任何子命题公式都可以用与之等值的命题公式置换；
2009-7-29 离散数学 76
(4) 假言推理规则,A? B,A |= B
三、构造证明法（续）
(5) 附加规则,A |= A? B
(8) 假言三段论规则,A? B,B? C |= A? C
(11)合取引入规则,A,B |= A? B
(6) 化简规则,A? B |= B
(7) 拒取式规则,A? B,? B |=? A
(10)构造性二难规则,A? B,C? D,A? C |= B? D
(9) 析取三段论规则,A? B,? B |= A
2009-7-29 离散数学 77
例 12：构造下列推理的证明
(1) 前提,p? r,q? s,p? q
结论,r? s
(2) 前提,p? q,p r,s? t,? s? r,? t
结论,q
四、应用
2009-7-29 离散数学 78
(1) 前提,p? r,q? s,p? q 结论,r? s
四、应用（续）
证明,① p? r
② q? s
③ p? q
④ r? s
前提引入前提引入前提引入
①②③ 构造性二难
2009-7-29 离散数学 79
(2) 前提,p? q,p r,s? t,? s? r,? t 结论,q
四、应用（续）
证明,①? t
② s? t
③? s
④? s? r
前提引入前提引入
①② 拒取式
⑦⑧ 析取三段论
⑤ r
⑥ p r
⑦? p
⑧ p? q
⑨ q
前提引入
⑤⑥ 拒取式前提引入前提引入
③ ④ 假言推理
2009-7-29 离散数学 80
例 13,公安局受理某单位发生的一桩案件，已获取如下事实：
(1) 疑犯甲或疑犯乙，至少有一人参与作案；
(2) 如果甲作案，则作案不在上班时间；
(3) 如果乙的证词正确，则大门还未上锁；
(4) 如果乙的证词不正确，则作案发生在上班时间；
(5) 已证实大门上了锁；
试判断谁是作案人？写出推理过程。
四、应用（续）
2009-7-29 离散数学 81
解题思想,将命题符号化； 写出前提和可能结论；
使用构造证明法推演出正确结论。
四、应用（续）
解,设 p：甲作案； q：乙作案；
r：作案发生在上班时间；
s：乙证词正确；
t：大门已上锁。
2009-7-29 离散数学 82
例 13,公安局受理某单位发生的一桩案件，已获取如下事实：
(1) 疑犯甲或疑犯乙，至少有一人参与作案；
(2) 如果甲作案，则作案不在上班时间；
(3) 如果乙的证词正确，则大门还未上锁；
(4) 如果乙的证词不正确，则作案发生在上班时间；
(5) 已证实大门上了锁；
试判断谁是作案人？写出推理过程。
四、应用（续）
p? q
p r
s t
s? r
t
2009-7-29 离散数学 83
前提,p? q,p r,s t,? s? r,t
结论：待定，但只有两种可能（ p或 q）
四、应用（续）
证明,① s t
② t
③? s
④? s? r
前提引入前提引入
①② 拒取式
⑦⑧ 析取三段论
⑤ r
⑥ p r
⑦? p
⑧ p? q
⑨ q
前提引入
③ ④ 假言推理
⑤⑥ 拒取式前提引入前提引入乙作案
2009-7-29 离散数学 84
1,附加前提证明法当要证明的结论是一蕴涵式时，通过等值演算将结论中的前件变成前提，再证明该命题公式。
五、构造证明的技巧
(A1?A2?…?An)?(A?B)? (A1?A2?…?An?A)?B
2,归谬法当要证明结论 B时，将?B作为前提使用，推出矛盾的证明方法。
(A1? A2?…? An)? B (A1? A2?…? An B)
2009-7-29 离散数学 85
例 14：构造下列推理的证明
(1) 前提,p? ( q? r ),? s? p,q
结论,s? r
(2) 前提,p? (? (r? s) q),p,? s
结论,? q
六、应用
2009-7-29 离散数学 86
(1) 前提,p? ( q? r ),? s? p,q 结论,s? r
六、应用（续）
证明,①? s? p
② s
③ p
④ p? ( q? r )
前提引入附加前提引入
⑤ q? r
⑥ q
⑦ r
③ ④ 假言推理
⑤⑥ 假言推理
①② 析取三段论前提引入前提引入
2009-7-29 离散数学 87
(2) 前提,p? (? (r? s) q),p,? s 结论,? q
六、应用（续）
证明,① p? (? (r? s) q)
② p
③? (r? s) q
④? (? q)
前提引入
⑤ q
⑥ r? s
⑦ s
③⑤ 拒取式
①② 假言推理否定结论引入
⑥ 化简
⑧? s
⑦⑧ 合取⑨ s s
④ 置换前提引入前提引入
