第1章 逻辑代数(上)：命题演算.doc

《离散数学教程》教案与习题解析 理工学院 段景辉
第1章 逻辑代数（上）：命题演算
1.1 逻辑联结词与命题公式
1.1.1 逻辑联结词
否定词(negation)“并非”(not)，用符号 Ø （或 ~ ）表示。设p表示一命题，那么Øp表示命题p的否定。当p真时Øp假，而当p假时Øp真。Øp读作“并非p”或“非p”。用类似表1.1的真值表(truth table)规定联结词的意义。
表1.1
p
Øp
0
1
1
0
合取词(conjunction)“并且”(and)，用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即当p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。
表1.2
p
q
p∧q
0
0
1
1
0
1
0
1
0
0
0
1
析取词(disjunction)“或”(or)用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”，“p或q”。析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。
表1.3
p
q
p∨q
0
0
1
1
0
1
0
1
0
1
1
1
蕴涵词(implication)“如果……，那么……”(if…then…)，用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”，它常被称作条件命题。当p真而q假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，Øp→Øq，Øq→Øp分别叫做p→q的逆命题，否命题，逆否命题。蕴涵词→的意义及复合命题p→q的真值状况规定见表1.4。
表1.4
p
q
p→q
0
0
1
1
0
1
0
1
1
1
0
1
双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号«表示之。设p，q为两命题，那么p«q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p«q为真，否则为假。p«q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。双向蕴涵词的意义及p«q的真值状况由表1.5给出。
表1.5
p
q
p«q
0
0
1
1
0
1
0
1
1
0
0
1
1.1.2 命题公式
定义1.1 归纳定义命题公式（简称公式proposition formula）：
（1）命题常元和命题变元是命题公式，也称为原子公式或原子。
（2）如果A，B是命题公式，那么(ØA)，(A∧B)，(A∨B)，(A→B)，(A«B)也是命题公式。
（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。
定义1.2设公式A含有命题变元p1，p2，…，pn（有时用A(p1，p2，…，pn)表示这一状况），称p1，p2，…，pn每一取值状况为一个指派(assignments)，用希腊字母a，b等表示，当A对取值状况 a 为真时，称指派a弄真A，或a是A的弄真指派，记为a(A) = 1；反之称指派a弄假A，或a是A的弄假指派，记为a(A) = 0。
1.1.3 语句形式化
将自然语言表述的命题“翻译”成命题公式，常称为语句形式化。语句形式化要注意以下几个方面：
l 要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。
l 要注意语句的语用，不同的语用有不同的逻辑含义。例如“狗急跳墙”可能说的是一个规律，也可能说的是一个现象。
l 要善于识别自然语言中的联结词（有时它们被省略）。例如“风雨无阻，我去北京”一句，可理解为“不管是否刮风、是否下雨我都去北京”。
l 否定词的位置要放准确。
l 需要的括号不能省略；而可以省略的括号，在需要提高公式可读性时亦可不省略。
l 注意“只要¼，就¼”“只有¼，才¼”的正确理解。因果关系也常常用蕴涵词来表示，这一点是有争议的。
l 语句的形式化的结果未必是唯一的。

练习1.1题解
1、选择题
（1）设P:我将去镇上，Q:我有时间。命题“我将去镇上，仅当我有时间”符号化为（ ）
A．P→Q ； B. Q→P ； C. P↔Q ； D. Q∨P.。
【答案】：A
（2）设P:张三可以做这件事，Q李四可以做这件事。命题“张三或李四可以做这件事”符号化为（ ）
A．P∨Q ； B.P∨Q ； C. P↔Q ； D. (P∨Q)
【答案】：A
（3）设P:我们划船，Q:我们跑步。命题“我们不能既划船又跑步”符号化为（ ）
A．P∧Q ； B.P∨Q ； C.(P↔Q) ； D. P↔Q
【答案】：B
（4）下列语句中哪个是真命题（ ）
A．我正在说谎
B. 如果1+2=3，那么雪是黑的
C. 如果1+2=5，那么雪是黑的
D. 严禁吸烟
【答案】：C
（5）P→Q的逆命题是（ ）
A .Q→P B. P→Q C.Q→P D.P→Q
【答案】：A
（6）下面哪一个命题是命题“2是偶数或-3是负数”的否定（ ）
A．2是偶数或-3不是负数
B. 2是奇数或-3不是负数
C. 2不是偶数且-3不是负数
D. 2是奇数且-3不是负数
【答案】：C

2、填空题
（1）下列句子中，是命题的有 .
（a）我是教师。
（b）禁止吸烟。
（c）蚊子是鸟类动物。
（d）上课去！
【答案】：（a），（c）
（2）设P：我生病，Q：我去学校
（a）命题“我虽然生病但我仍去学校”可符号化为 。
（b）命题“只有我生病的时候，我才不去学校” 可符号化为 。
（c）命题“只要我生病，我就不去学校” 可符号化为 。
（d）命题“当且仅当我生病，我才不去学校” 可符号化为 。
【答案】：（a）P∧Q；（b）.Q→P；（c）P→Q；（d）P↔Q
（3）“a≥0”表示a>0 a=0 ；“a是非负实数”表示a≥0 a是实数（在空格中填上适当的命题联结词）。
【答案】：∨；∧
（4）在空格中填上表（表1.6）各列所定义的命题联结词：
表1.6
P Q
P Q
P Q
0 0
1
1
0 1
1
0
1 0
0
0
1 1
1
1
【答案】：→；↔
（5）P，Q为两个命题，当且仅当 时，P→Q的真值为0。
【答案】：P真且Q假
（6）公式P→Q的否命题为 ，逆否命题为 。
【答案】：﹁P→﹁Q； ﹁Q→﹁P

3．将下列命题形式化：
（1）你是博士，但我是硕士。
【答案】：可表示为 (p∧q)， 其中p：你是博士；q：我是硕士
（2）我今天或明天去泰山的说法是谣传。
【答案】：可表示为Ø (p∨q)，其中p：我今天去泰山；q：我明天去泰山
（3）如果买不到飞机票，我不去海南岛。
【答案】：可表示为Øp→Øq，其中，p：我买到飞机票，q：我去海南岛
（4）只要他出门，他必买书，不管他带的钱多不多。
【答案】：可表示为(p∧q→r)∧(Øp∧q→r)或q→r，其中p：他带的钱多，q：他出门，r：他买书。
（5）除非你陪伴我或代我雇辆车子，否则我不去。
【答案】：可表示为(p∨q) ↔ r，其中p：你陪伴我，q：你代我雇车，r：我去
（6）只要充分考虑一切论证，就可得到正确见解；必须充分考虑一切论证，才能得到正确见解。
【答案】：可表示为(p→q) ∧(q→p )或p« q，其中p：你充分考虑了一切论证，q：你得到了正确见解
（7） 除非你是成年人，否则只要你身高不超过1米3，就能到儿童游乐场玩耍。
Ø r↔ (Øs→t)，其中r：你是成年人，s：你身高超过1米3，t: 你到儿童游乐场玩耍
（8）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。
【答案】：可表示为(q→p ) →Øq，其中p：我懂得希腊文，q：我了解柏拉图
（9）侈而惰者贫，而力而俭者富。（韩非：《韩非子·显学》）
【答案】：可表示为((p∧q)→r) ∧((Øp∧Øq)→Ør)，其中p：你奢侈，q：你懒惰，r：你贫困
（10）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子·劝学》）
【答案】：可表示为(p→Øq) ∧(s→r) ∧(m∧n→Øo) ∧(m∧Øn→v)，其中p：骐骥一跃，q：骐骥行十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：你将朽木折断，v：你将金石雕刻

4．根据命题公式的定义和括号省略的约定，判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（p,q,r,s为原子命题）：
（1）Ø (p)
【答案】：Ø (p) 不是公式
（2）(p∨qr)→s
【答案】：(p∨qr)→s 不是公式
（3）(p∨q)→p
【答案】：(p∨q)→p 是公式，其真值表如表1.7所示：
表1.7
p
q
p∨q
(p∨q)→p
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
1
（4）p→(p∨q)
【答案】：p→(p∨q) 是公式，其真值表如表1.8所示（恒真）：
表1.8
p
q
p∨q
p→(p∨q)
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
1
（5）p∧(p→q)→q
【答案】：p∧(p→q)→q 是公式，其真值表如表1.9所示（恒真）：
表1.9
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
（6）p∧(p→q)∧(p→Øq)
【答案】：p∧(p→q)∧(p→Øq) 是公式，其真值表如表1.10所示（恒假）：
表1.10
p
q
┐q
p→q
p∧(p→q)
p→┐q
p∧(p→q)∧(p→Øq)
0
0
1
1
0
1
0
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
（7）Ø (p∨q) «Øq∧Øp
【答案】：Ø (p∨q) «Øq∧Øp 是公式，其真值表如表1.11所示（恒真）：
表1.11
p
q
Ø p
Ø q
p∨q
Ø (p∨q)
Øq∧Øp
(p→q) « (Ø q→Ø p)
0
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
0
1
0
0
1
（8）Ø p∨q« (p→q)
【答案】：Ø p∨q«(p→q) 是公式，其真值表如表1.12所示（恒真）：
表1.12
p
q
Øp
Øp∨q
p→q
Øp∨q« (p→q)
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
0
1
1
1
（9）(p→q)∧(q→r)→(p→ r )
【答案】：(p→q)∧(q→r)→(p→r) 是公式，其真值表如表1.13所示（恒真）：
表1.13
p
q
r
p→q
q→r
p→r
(p→q)∧(q→r)
(p→q)∧(q→r)→(p→r)
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
（10）(p∨q→r) « (p→r)∧(q→r)
【答案】：(p∨q→r) « (p→r)∧(q→r) 是公式，其真值表如表1.14所示（恒真）：
表1.14
p
q
r
p∨q
p∨q→r
p→r
q→r
(p→r)∧(q→r)
(p∨q→r)« (p→r)∧(q→r)
0
0
0
0
1
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1

5．给出弄真下列命题公式的指派：
（1）((p→q)∧q)→┐p
【答案】：弄真指派有(0,0)，(0,1)，(1,0)
（2）((p→q)→r)→((q→p)→r)
【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1)
（3）((p«q)→r)→((q→p) «r)
【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)， (1,0,1)，(1,1,0)，(1,1,1)
（4）Ø ((p∨q)∧r)→(r→p)
【答案】：弄真指派有(0,0,0)，(0,1,0)， (0,1,1)，(1,0,0)，(1,0,1)，(1,1,0)，(1,1,1)

1.2 逻辑等价式和逻辑蕴涵式
1.2.1 重言式
定义1.3 如果对命题公式A中命题变元的一切指派均弄真A，那么，称A为重言式(tautology)；重言式又称永真式；如果至少有一个这样的指派弄真A，那么，称A为可满足式(satisfactable formula)，否则称A为不可满足式或永假式、矛盾式。
1.2.2 逻辑等价式和逻辑蕴涵式
定义1.4 当命题公式A«B为永真式时，称A逻辑等价于B，记为A┝┥B，它又称为逻辑等价式(logically equivalent)。
以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式：
E1 ØØA┝┥A 双重否定律
E2 A∨A┝┥A ，A∧A┝┥A 幂等律
E3 A∨B┝┥B∨A ，A∧B┝┥B∧A 交换律
E4 (A∨B)∨C┝┥A∨(B∨C) 结合律
(A∧B)∧C┝┥A∧(B∧C)
E5 A∧(B∨C)┝┥(A∧B)∨(A∧C) 分配律
A∨(B∧C)┝┥(A∨B)∧(A∨C)
E6 Ø (A∨B)┝┥ØA∧ØB 德摩根律
Ø (A∧B)┝┥ØA∨ØB
E7 A∨(A∧B)┝┥A 吸收律
A∧(A∨B)┝┥A
E8 A→B┝┥ØA∨B
E9 A« B┝┥(A→B)∧(B→A)
E10 A∨t┝┥t ， A∧f┝┥f
E11 A∨f┝┥A ， A∧t┝┥A
E12 A∨ØA┝┥t ，A∧ØA┝┥f
E13 Øt┝┥f, Øf┝┥t
E14 A∧B→C┝┥A→(B→C)
E15 A∨B→C┝┥(A→C)∧(B→C)
E16 A→B┝┥ØB→ØA
E17 (A→B)∧(A→ØB)┝┥ØA
E18 A« B┝┥(A∧B)∨(ØA∧ØB)
定义1.5 当命题公式A→B为永真式时，称A逻辑蕴涵B，记为A┝ B，它又称为逻辑蕴涵式(logically implication)。
一些十分重要的逻辑蕴涵式：
I1 A┝ A∨B，B┝ A∨B
I2 A∧B┝ A，A∧B┝ B
I3 B┝A→B
I4 A∧(A→B)┝ B
I5 (A→B)∧ØB┝ØA
I6 ØA∧(A∨B)┝ B，ØB∧(A∨B)┝ A
I7 (A→B)∧(B→C)┝ A→C
I8 (A→B)∧(C→D)┝ (A∧C)→(B∧D)
I9 (A«B)∧(B«C)┝ A«C
I10 A┝ t ； f┝ A
逻辑等价式与逻辑蕴涵式有如下明显性质。
定理1.1 对任意命题公式A，B，C，A'，B'，
（1）A┝┥B当且仅当┝ A«B
（2）A┝ B当且仅当┝ A→B
（3）若A┝┥B，则B┝┥A
（4）若A┝┥B，B┝┥C，则A┝┥C
（5）若A┝ B，则┐B┝ ┐A
（6）若A┝ B，B┝ C，则A┝ C
（7）若A┝ B，A┝┥A'，B┝┥B'，则A'┝ B'
定理1.2 设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。
定理1.2常被称为代入原理(rule of substitution)，简记为RS
定理1.3 设A为一命题公式，C为A的子公式，且C┝┥D。若将A中子公式C的某些（未必全部）出现替换为D后得到的公式记为B，那么A┝┥B。
定理1.3常被称为替换原理(rule of replacement)简记为RR。
请注意RS与RR的区别，详见表1.15。
表1.15

代入原理 RS
替换原理 RR
使用对象
任意永真式
任一命题公式
被代换对象
任一命题变元
任一子公式
代换对象
任一命题公式
任一与代换对象等价的命题公式
代换方式
代换同一命题变元的所有出现
代换子公式的某些出现
代换结果
仍为永真式
与原公式等价
当然，证明逻辑蕴涵式A┝ B不成立的方法只有一个，那就是：找出一个指派使得A为真，却使 B为假。证明逻辑等价式A┝┥B不成立的方法是：证明A┝ B不成立或者证明B┝A不成立。推而广之，为证 G┝ B（G 为公式集合）不成立，只要找出一个指派使得G中所有公式为真，却使B为假。
1.2.3 对偶原理
定义1.6 设公式A仅含联结词 Ø，∧，∨，A*为将A中符号∧，∨，t，f分别改换为∨，∧，f，t后所得的公式，那么称A*为A的对偶(dual)。
下面两定理所描述的事实常称为对偶原理。
定理1.4 设公式A中仅含命题变元p1,…,pn，及联结词Ø，∧，∨，那么
A┝┥ØA* (Øp1／p1，…，Øpn／pn)
这里，A* (Øp1／p1，…，Øpn／pn)表示在A*中对p1,…,pn分别作代入Øp1,…, Øpn后所得的公式。
定理1.5 设A，B为仅含联结词Ø，∧，∨和命题变元p1,…,pn的命题公式，且满足A┝B，那么有B*┝ A*。进而当A┝┥B时有A*┝┥B*。
定义1.7 B*┝ A*，A*┝┥B*分别称为A┝ B和A┝┥B的对偶式。
1.2.4 应用逻辑
命题逻辑的相关知识，特别是逻辑等价式和逻辑蕴含式所反映的逻辑思维规律，如，排中律、矛盾律、双重否定律、德摩根律等，是人们逻辑推理的基础，在逻辑训练和实际生活中有十分广泛的应用。

练习1.2题解
1．选择题
（1）K是重言式，那么K的否定是（ ）
A.重言式 B.矛盾式 C.可满足式 D. 不能确定
【答案】：B
（2）K不是重言式，那么它是（ ）
A.永假式 B.矛盾式 C.可满足式 D.不能确定
【答案】：C
（3）命题公式(P∧(P→Q)) →Q是（ ）
A．矛盾式 B. 可满足式 C. 重言式 D. 不能确定
【答案】：C
（4）命题公式(P∧(ØP∨Q)) ∧Q是（ ）
A．矛盾式 B. 可满足式 C. 重言式 D. 不能确定
【答案】：B
（5）如果P→Q为真时我们称命题P强于Q，那么最强的命题是（ ），最弱的命题是（ ）。
A．永假式 B. 可满足式 C. 永真式 D. 不能确定
【答案】：A，C

2．填空题
（1）两个重言式的析取是 ，一个重言式与一个矛盾式的析取是 。
两个重言式的合取是 ，一个重言式与一个矛盾式的合取是 。
一个重言式蕴涵一个矛盾式的是 ，一个矛盾式蕴涵一个重言式的是 。
【答案】：重言式，重言式，重言式，矛盾式，矛盾式，重言式
（2）在下列各式中，是永真式的有 。
（a）(P∧(P→Q)) →Q
（b）P→(P∨Q)
（c）Q→(P∧Q)
（d）(﹁P∧(P∨Q))→Q
（e）(P→Q)→Q
【答案】：(a)，（b），（d）
（3）化简下列各式：
（a）(﹁P∧Q) ∨(﹁P∧﹁Q)可化简为 。
（b）Q→(P∨(P∧Q))可化简为 。
（c）((﹁P∨Q)↔(Q∨﹁P))∧P可化简为 。
【答案】：（a）﹁P；（b）Q→P；（c）P
（4）公式(P∨Q)→R的只含联结词，∧的等价式为 ，它的对偶式为 。
【答案】：((P∧Q)∧R)；(P∧Q) ∧R

3．试判定以下各式是否为重言式：
（1）(p→q)→(q→p)
【答案】：否
（2）﹁p→(p→q)
【答案】：是
（3）q→(p→q)
【答案】：是
（4）p∧q→(p«q)
【答案】：是
（5）(p→q)∨(r→q)→((p∨r)→q)
【答案】：否
（6）(p→q)∨(r→s)→((p∨r)→(q∨s))
【答案】：否

4．试用真值表验证E6，E8，E15，E17。
（1）【答案】： E6 ﹁(A∨B)┝┥﹁A∧﹁B的真值表如表1.16所示：
表1.16
A
B
A∨B
﹁(A∨B)
﹁A
﹁B
﹁A∧﹁B
﹁(A∨B) «﹁A∧﹁B
0
0
0
1
1
1
1
1
0
1
1
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
0
0
1
﹁(A∧B)┝┥﹁A∨﹁B的真值表如表1.17所示：
表1.17
A
B
A∧B
﹁(A∧B)
﹁A
﹁B
﹁A∨﹁B
﹁(A∧B) «﹁A∨﹁B
0
0
0
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
1
（2）【答案】： E8 A→B┝┥﹁A∨B的真值表如表1.18所示：
表1.18
A
B
A→B
﹁A
﹁A∨B
A→B«﹁A∨B
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
（3）【答案】：E15 A∨B→C┝┥(A→C)∧(B→C) 的真值表如表1.19所示：
表1.19
A
B
C
A∨B
A∨B→C
A→C
B→C
(A→C)∧(B→C)

(A∨B→C)«(A→C)∧(B→C)
0
0
0
0
1
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
（4）【答案】：E17 (A→B)∧(A→ØB)┝┥ØA的真值表如表1.20所示：
表1.20
A
B
A→B
A→ØB
(A→B)∧(A→ØB)
ØA
(A→B)∧(A→ØB) «ØA
0
0
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
0
0
0
1

5．不用真值表，用代入、替换原理证明E16，E17。
（1）E16 A→B┝┥ØB→ØA
【答案】： A→B┝┥﹁A∨B 据E8
┝┥﹁A∨﹁ (﹁B) 　　　据E1用RR
┝┥ØB→ØA 　　　 对E8用RS
（2）E17 (A→B)∧(A→﹁B)┝┥﹁A
【答案】：(A→B)∧(A→﹁B)┝┥(﹁A∨B) ∧(﹁A∨﹁B) 据E8用RR
┝┥﹁A∨ (B∧﹁B) 对E5用RS
┝┥﹁A∨f 据E12用RR
┝┥﹁A 据E11用RS

6．试用真值表验证I3，I4，I6，I7。
（1）【答案】： I3 B┝A→B的真值表如表1.21所示：
表1.21
A
B
A→B
B→(A→B)
0
0
1
1
0
1
1
1
1
0
0
1
1
1
1
1
（2）【答案】：I4 A∧ (A→B)┝B的真值表如表1.22所示：
表1.22
A
B
A→B
A∧ (A→B)
A∧ (A→B) →B
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
（3）【答案】：I6 ﹁A∧(A∨B) ┝B 的真值表如表1.23所示：
表1.23
A
B
﹁A
A∨B
﹁A∧(A∨B)
﹁A∧(A∨B)→B
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
﹁B∧(A∨B) ┝A的真值表如表1.24所示：
表1.24
A
B
﹁B
A∨B
﹁B∧(A∨B)
﹁B∧(A∨B)→A
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
1
0
1
（4）【答案】：I7 (A→B) ∧(B→C) ┝(A→C) 的真值表如表1.25所示：
表1.25
A
B
C
A→B
B→C
A→C
(A→B)∧(B→C)
I7
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1

7．不用真值表，用代入、替换原理证明I8，I9 。
【答案】：（1）I8：(A→B)∧(C→D)┝ (A∧C)→(B∧D)
证 (A→B)∧(C→D) ∧(A∧C) ┝┥(﹁A∨B)∧(﹁C∨D) ∧(A∧C)
┝┥(﹁A∧﹁C∧A∧C) ∨(B∧﹁C∧A∧C) ∨(﹁A∧D∧A∧C) ∨(B∧D∧A∧C)
┝┥f∨f∨f∨(A∧B∧C∧D)
┝┥A∧B∧C∧D
┝B∧D
因此，(A→B)∧(C→D) ∧(A∧C) →(B∧D)为一重言式
又(A→B)∧(C→D) ∧(A∧C) →(B∧D) ┝┥(A→B)∧(C→D) →((A∧C) →(B∧D))
所以(A→B)∧(C→D) →((A∧C) →(B∧D)) 为一重言式
即(A→B)∧(C→D)┝ (A∧C)→(B∧D)
【答案】：（2）I9：(A«B)∧(B«C)┝ (A«C)
证 (A«B)∧(B«C)∧A ┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)∧A
┝ (A→B)∧(B→C)∧A
┝┥(﹁A∨B) ∧(﹁B∨C) ∧A
┝┥(﹁A∧﹁B∧A) ∨(﹁A∧C∧A) ∨(B∧﹁B∧A) ∨(B∧C∧A)
┝┥f∨f∨f∨(A∧B∧C)
┝┥A∧B∧C
┝ C
因此，(A«B)∧(B«C)∧A →C为一重言式
又(A«B)∧(B«C)∧A →C ┝┥(A«B)∧(B«C)→(A →C)
所以(A«B)∧(B«C)→(A →C) 为一重言式
仿上可证(A«B)∧(B«C)→(C →A) 为一重言式
又根据（1），((A«B)∧(B«C)→(A →C)) ∧((A«B)∧(B«C)→(C →A))
┝(A«B)∧(B«C) →(A →C) ∧(C →A)
┝┥(A«B)∧(B«C) →(A«C)
所以(A«B)∧(B«C) →(A«C)也是重言式，
即(A«B)∧(B«C)┝ (A«C)

8．用三种不同方法证明下列逻辑等价式和逻辑蕴涵式：
（1）A«B┝┥(A∧B)∨(﹁A∧﹁B)
【答案】证法1：真值表（表1.26）的最后两列等值，故A«B┝┥(A∧B)∨(﹁A∧﹁B)
表1.26
A
B
A∧B
﹁A
﹁B
﹁A∧﹁B
A«B
(A∧B)∨(﹁A∧﹁B)
0
0
0
1
1
1
1
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
1
1
证法2：A«B┝┥(A→B)∧(B→A)
┝┥(﹁A∨B)∧(﹁B∨A)
┝┥(﹁A∧﹁B)∨(﹁A∧A)∨(B∧﹁B)∨(B∧A)
┝┥(A∧B)∨(﹁A∧﹁B)
证法3： 先证A«B┝ (A∧B)∨(﹁A∧﹁B) (a)
设a为任一指派，使(A«B)=1，那么a (A)= a (B)=1或a(A)= a (B)=0，从而
a (A∧B)=1或a (﹁A∧﹁B)=1，即a ((A∧B)∨(﹁A∧﹁B))=1。(a)得证；
再证(A∧B)∨(﹁A∧﹁B)┝ A«B (b)
设a为任一指派，使a (A«B)=0，那么a (A)=1，a(B)=0，或者a(A)=0，a
a(B)=1，从而a(A∧B)=0且a (﹁A∧﹁B)=0，即a ((A∧B)∨(﹁A∧﹁B))=0。(b)得证。
（2）A→(B→C)┝┥B→(A→C)
【答案】证法1：真值表（表1.27）的最后两列等值，故A→(B→C)┝┥B→(A→C)
表1.27
A
B
C
B→C
A→C
A→(B→C)
B→(A→C)
0
0
0
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
1
1
1
证法2：A→(B→C)┝┥﹁A∨(﹁B∨C)
┝┥(﹁A∨﹁B)∨C
┝┥(﹁B∨﹁A)∨C
┝┥﹁B∨(﹁A∨C)
┝┥B→(A→C)
证法3：先证A→(B→C)┝ B→(A→C) (a)
设a为任一指派，使a (A→(B→C))=1，那么
ⅰ）a (A)= 0，则a ( A→C)=1，从而a ( B→(A→C))=1
ⅱ）a (A)= 1，a (B)=0，则a ( B→(A→C))=1
ⅲ）a (A)= a (B)=a (C)=1，则a ( B→(A→C))=1
综上，(a)得证；同理可证B→(A→C)┝ A→(B→C)。
（3）A→(A→B)┝┥A→B
【答案】证法1：真值表（表1.28）的最后两列等值，故A→(A→B)┝┥A→B
表1.28
A
B
A→B
A→(A→B)
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
证法2：A→(A→B)┝┥A∧A→B
┝┥A→B
证法3：先证A→(A→B)┝ A→B (a)
设a为任一指派，使a( A→B)=0，那么a (A)=1，a(B)=0，从而
a ( A→(A→B))=0。(a)得证；
再证A→B┝ A→(A→B) (b)
设a为任一指派，使a (A→(A→B))=0，那么a (A)=1，a (A→B)=0。(b)得证。
（4）A→(B→C)┝┥(A→B)→(A→C)
【答案】证法1：真值表（表1.29）的最后两列等值，故A→(B→C)┝┥(A→B)→(A→C)
表1.29
A
B
C
B→C
A→B
A→C
A→(B→C)
(A→B)→(A→C)
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
0
0
1
1
1
0
1