(pq) (pq) T 该式是永真式
摩根律 交换律 排中律
19
例题
化简公式 (p q) (p q)
解 (pq)(pq)
p(qq) 分配律
pT
排中律
p
同一律
20
例题
对于图1.3.1所示的逻辑电路，可否用更简单的电路实现该逻
辑关系？
p
q
p
q
F
p q
解：F (pq)(pq)(pq)
(pq)q
3
命题公式的真值表
真值表: 命题公式在所有可能的赋值下的取值的列表 含n个变项的公式有2n个赋值 例 给出公式的真值表 (1) p(q r) (2) (pq)(pq) (3) ( pq)q
4
(1) p(qr)
pqr 000 001 010 011 100 101 110 111
例题(续)
r
qr
p(qr)
pq
p
q
F
21
全功能联结词集
定义1.3.2 设G是一个联结词的集合，若任意一个命题公式都 可用G中的联结词构成的公式来表示，则称G为全功能联结词 集。如在G中去掉任何一个联结词，就不再具有这种特性，就 称其为最小全功能联结词集。 {、、}，{、}，{、}，{、}，{}和{}都是全 功能联结词集，而{、}，{、}，{、}，{}和{}都 是最小全功能联结词集。
定义1.2.3 设A为一个命题公式 (1)若A在它的各种赋值下取值均为真，则称A为重言式或永真式。 (2)若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式。 (3)若至少存在一种赋值使A的真值为真，则称A为可满足式。
例如 (1) p(qr) 为非重言式的可满足式 （2）(p q)( p q)为重言式 (3) (pq)q 为矛盾式
15
例题
例1.3.3 证明pqqp
解 pq pq
蕴涵等价式
(q) p qp
交换律和双重否定式 蕴涵等价式
条件命题： pq
否命题：pq
逆命题： qp
逆否命题：qp
条件命题和它的逆否命题等价
16
例题
例1.3.4 利用命题的等价运算判断下列公式的类型。
（1）p(pq)
解 p(pq)p(pq) 蕴涵等价式
定义1.2.2 若命题公式A含有的全部命题变元为p1, p2, … , pn， 给p1, p2, … , pn指定一组真值，称为对A的一个解释或赋值。使 A的真值为真的赋值称为成真赋值，使A的真值为假的赋值称为 成假赋值。 说明 通常赋值与命题变元之间按下标或字母顺序对应, 即当
A的全部命题变元为p1, p2, … , pn时, 给A赋值12…n，是指 p1=1,p2=2,…,pn=n;当A的全部命题变元为p,q,r,…时, 给A赋值 123…是指p=1, q=2, r=3, …。
p q 和p q ， p q和 p q，p (q r)和p (q r)， pq和pq 都互为对偶式
25
对偶式
设A(p1，p2，…pn) 和A*(p1，p2，…pn)互为对偶式，其中p1，p2，…pn是出 现在A和A*中的全部的命题变元，则
A(p1，p2，…pn) A*( p1，p2，…pn) A( p1，p2，…pn) A*(p1，p2，…pn) 定理1.3.1 设A和B为两个命题公式，A和A*，B和B*互为对偶式，若AB， 则A*B*。 证明 因为A(p1，p2，…pn) A*( p1，p2，…pn)，B(p1，p2，…pn) B*( p1，p2，…pn)，若A(p1，p2，…pn) B(p1，p2，…pn)，则 A*( p1，p2，…pn) B*( p1，p2，…pn)，即A*(p1， p2，…pn)B*( p1，p2，…pn)，则A*(p1，p2，…pn)B*(p1， p2，…pn)。
000
0
0
001
0
0
010
0
0
011
0
0
100
0
0
101
1
1
110
1
1
111
1
1
所以有： p(qr)和(p q)(pr)等价 12
等价关系式
双重否定律 同一律 零元律 等幂律 交换律 结合律
pp p0p, p1p p11, p00 ppp, ppp pqqp, pqqp (pq)rp(qr)
德摩根律
14
等价运算
置换规则 若公式G中的一部分A(包含G中几个连续的符号)是公式， 称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。
利用已知的等价关系式，将其中的子公式用和它等价的公式 置换可以推出其它一些等价关系式，这一过程称为命题的等价运算。 利用命题的等价运算，可以 •判断两个命题是否等价 •判断命题公式的类型 •命题公式的化简等。
(pq)rp(qr) (pq)pq
(pq)pq
吸收律
p(pq)p, p(pq)p
13
基本等值式(续)
分配律
p(qr)(pq)(pr)
p(qr) (pq)(pr)
排中律
pp1
矛盾律 蕴涵等值式 等价等值式
pp0 pqpq pq(pq)(qp)
假言易位
pqqp
等价否定等值式 pqpq
归谬论
(pq)(pq) p
1
0
1
0
0
1
1
1
1
0
0
1
1
0
0
0
0
0
ห้องสมุดไป่ตู้
1
1
1
0
0
0
5
例题(续)
（2） (pq)(pq)
pq
pq
00
1
01
1
10
0
11
1
pq
0 1 1 1
(pq)(pq)
1 1 1 1
6
例题(续)
(3) (pq)q p q p
pq
(pq)
(pq) q
00 1
0
1
0
01 1
1
0
0
10 0
1
0
0
11 0
1
0
0
7
命题公式的分类
8
命题公式的分类
这三类公式之间有下面的关系： •公式A永真，则A永假，反之亦然。 •公式A是可满足的，当且仅当A不是永真式。 •公式A不是可满足的，则一定是永假式。 •公式A不是永假式，则一定是可满足的。
判断命题公式类型的方法：构造真值表
9
1.3 命题演算的关系式
等价关系式 定义1.3.1 设A和B是两个命题(或命题公式)，若AB是永 真式，命题A和B称为逻辑等价的，可记为AB。 说明：AB是永真式，表示命题公式A和B在所有的赋值下都 有相同的真值，也就是说命题公式A和B有相同的真值表。
26
例题
求公式Ap (p (q q))的对偶式。 解 公式A的对偶式A*为：
A* p(p(qq)) 重言式A的对偶式A*是矛盾式
27
1
命题公式
•一个含有命题变元的命题公式的真值是不确定的. •只有当公式中的所有命题变元被指定代表特定的命题时，命 题公式才成为命题，其真值才唯一确定。 例如，命题公式p q 若指定 p为“2是素数”，q为“3是奇数”
则p q为真命题 若指定 p为“2是素数”，q为“3是偶数”
则p q为假命题
2
公式的赋值
的电路就可以实现任何逻辑运算。
p
p
q
pq
q
pq
与非门
或非门
23
例题
用只有一种与非门的逻辑电路实现F(pq)(pq)( pq)。 解： F (pq)(pq)(pq)
pq
(pq)
(pp) q
p
p
q
F
24
对偶式
定义1.3.3 在仅含有联结词， ， 的公式A中，将其中的 换成 ， 换成 ，T(或1)换成F(或0)，F(或0)换成T(或1)， 其它符号不变得到的公式称为A的对偶式，记为A*。
可以用真值表判定两个命题是否等价。
10
例题
证明：p q和pq等价。
证 列出真值表
pq
pq
p
00
1
1
01
1
1
10
0
0
11
1
0
所以有: p q pq
pq 1 1 0 1
11
例题
证明p (qr )和(p q) (p r)逻辑等价
证 列出真值表
pqr
p (qr ) (p q) (p r)
1.2 命题公式及其分类
命题常元: 代表特定简单命题 命题变元: 代表任意命题，取值1(真)或0(假)的变量 定义1.2.1 命题公式（公式）的定义如下：
1.每一个命题常元或命题变元都是命题公式。 2.如果A是命题公式，则(A)是命题公式。 3.如果A和B都是命题公式，则(AB)，(AB)，(AB)， (AB)都是命题公式。 4.一个由命题常元或命题变元、联结词和括号所组成的符号串 是命题公式，当且仅当这个符号串是有限次应用上面的步骤得 到的。
AAAAA BBBB ((AA((AABA)BB)B)B(B)AA()ABB)
22
例题
证明：{},{}是最小全功能联结词集
证 ： p (pp) pp
pq (pq) (pq) (pq)(pq)
得证{}是联结词完备集. 对于{}可类似证明.
只用一个或就可以实现联结词，，、、表示
的逻辑关系。在数字电子技术中，只用与非门或者或非门组成
p(pq)
摩根律
(pp)q
结合律
Fq
矛盾式
F
零元律