循环1 S0=?, S1={p, p?q, p??q, q??r, q?r}, S2=?
Res(p?q, p??q)=p
Res(p??q, q??r)=p??r Res(p??q, q?r)= p?r Res(q??r, q?r)=q S2={p?r, p?r, q}
循环2 S0={p, p?q, p??q, q??r, q?r}, S1={p?r, p?r, q}, S2=?
Res(p??q, q)=p Res(q??r, p?r)=p?q
Res(q?r, p??r)=p?q Res(p?r, p??r)=p S2=? 输出“Yes”
第一章 习题课 主要内容
? 命题、真值、简单命题与复合命题、命题符号化 ? 联结词?, ?, ?, ?, ?及复合命题符号化 ? 命题公式及层次 ? 公式的类型 ? 真值表及应用 基本要求
? 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 ? 会求复合命题的真值
? 深刻理解合式公式及重言式、矛盾式、可满足式等概念
? 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型 1. 将下列命题符号化
(1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员.
(4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了.
(6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交通阻塞. 提示：
分清复合命题与简单命题 分清相容或与排斥或
分清必要与充分条件及充分必要条件
答案: (1) 是简单命题 (2) 是合取式
(3) 是析取式（相容或）(4) 是析取式（排斥或） 设 p: 交通阻塞，q: 他迟到
(5) p?q, (6) ?p??q或q?p (7) ?q??p 或p?q, (8) q?p或?p??q
(9) p?q 或?p??q 可见(5)与(7)，(6)与(8) 相同（等值） 2. 设 p : 2是素数
q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值
(1) (p?q)?r （0） (2) (q?r)?(p??r) （1） (3) (q?r)?(p??r) （0） (4) (q?p)?((p??r)?(?r??q)) （0） 3. 用真值表判断下面公式的类型 (1) p?r??(q?p)
(2) ((p?q) ?(?q??p)) ?r (3) (p?q) ?(p?r) (1) p?r??(q?p) p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 q?p 1 1 0 0 1 1 1 1 ?(q?p) p?r??(q?p) 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 矛盾式
(2) ((p?q) ?(?q??p)) ?r
p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
p?q 1 1 1 1 0 0 1 1
?q??p 1 1 1 1 0 0 1 1
((p?q) ?(?q??p)) ?r
1 1 1 1 1 1 1 1
永真式
(3) (p?q) ?(p?r) 非永真式的可满足式
p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 p?q 1 1 1 1 0 0 1 1 p?r 1 1 1 1 0 1 0 1 (p?q) ?(p?r) 1 1 1 1 1 0 0 1 第二章 习题课 主要内容
? 等值式与等值演算
? 基本等值式（16组，24个公式） ? 主析取范式与主合取范式 ? 联结词完备集 ? 消解法
? 深刻理解等值式的概念
? 牢记基本等值式的名称及它们的内容
? 熟练地应用基本等值式及置换规则进行等值演算
? 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念
? 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解
简单析取式与极小项的关系
? 熟练掌握求主范式的方法（等值演算、真值表等）
? 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等
值
? 会将公式等值地化成指定联结词完备集中的公式 ? 会用命题逻辑的概念及运算解决简单的应用问题 ? 掌握消解规则及其性质
? 会用消解算法判断公式的可满足性
1. 设A与B为含n个命题变项的公式，判断下列命题是否为真？ (1) A?B当且仅当A与B有相同的主析取范式 (2) 若A为重言式，则A的主合取范式为0 (3) 若A为矛盾式，则A的主析取范式为1 (4) 任何公式都能等值地化成{?, ?}中的公式 (5) 任何公式都能等值地化成{?, ?, ?}中的公式 说明:
(2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主合析范式不含任何极小项, 为0.
(4) {?, ?}不是完备集，如矛盾式不能写成{?, ?}中的公式. (5) {?, ?}是完备集. 2. 判断下列公式的类型: (1) (p?q)?(?q??p) 解 用等值演算法求主范式
(p?q)?(?q??p)
? ?(?p?q)?(q??p) ? (p??q)?(q??p)
? (p??q)?(?p?q)?(p?q)?(?p??q)
? m2 ? m1 ? m3 ? m0
? m0 ? m1 ? m2 ? m3 主析取范式 ? 1 主合取范式 重言式
(2) ?(p?q)?q
解 用等值演算法求公式的主范式 ?(p?q)?q
? ?(?p?q)?q ? p??q?q
? 0 主析取范式 ? M0 ? M1 ? M2 ? M3 主合取范式 矛盾式
(3) (p?q)??p
解 用等值演算法求公式的主范式 (p?q)??p ? (?p?q)??p ? ?p
? (?p??q)?(?p?q)
? m0 ? m1 主析取范式 ? M2 ? M3 主合取范式 非重言式的可满足式
3．已知命题公式A中含3个命题变项p, q, r，并知道它的成真 赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对 应的真值函数.
解：A的主析取范式为m1 ? m2 ? m7
A的主合取范式为M0 ? M3 ? M4 ? M5 ? M6 p q r F p q r F 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1
4．将A = (p??q)?r改写成下述各联结词集中的公式: (1) {?, ?, ?} (2) {?, ?} (3) {?, ?} (4) {?, ?} (5) {?} (6) {?} 解
(1) (p??q)?r ? (?p??q)?r
(2) (p??q)?r ? ?(p?q)?r (3) (p??q)?r ? (?p??q)?r
? ?(?(?p??q)??r) (4) (p??q)?r ? ?(?(p??q)??r)
? ?((p??q)??r) (5) (p??q)?r ? ?(p?q)?r
? (p?q)?r ? ? ?((p?q)?r)
? ((p?q)?r)?((p?q)?r) (6) (p??q)?r ?(?p??q)?r
? ?(?(?p??q)??r) ? (?p??q)??r
? ((p?p)?(q?q)?(r?r) 说明：答案不惟一
5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选 派一些人出国学习. 选派必须满足以下条件： (1) 若赵去，钱也去.
(2) 李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人. (4) 孙、李两人同去或同不去. (5) 若周去，则赵、钱也去.
用等值演算法分析该公司如何选派他们出国？ 解此类问题的步骤： 1.设简单命题并符号化 2. 用复合命题描述各条件
3. 写出由复合命题组成的合取式
4. 将合取式成析取式（最好是主析取范式） 5. 求成真赋值, 并做出解释和结论 解
1. 设简单命题并符号化
设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去
2. 写出复合命题
(1) 若赵去，钱也去 p?q (2) 李、周两人中至少有一人去 s?u
(3) 钱、孙两人中去且仅去一人 (q??r)?(?q?r) (4) 孙、李两人同去或同不去 (r?s)?(?r??s) (5) 若周去，则赵、钱也去 u?(p?q) 3. 设(1)—(5)构成的合取式为A
A = (p?q)?(s?u)?((q??r)?(?q?r))? ((r?s)?(?r??s))?(u?(p?q))
4. 化成析取式
A ? (?p??q?r?s??u)?(p?q??r??s?u)
结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去） A ? (?p?q)?((q??r)?(?q?r))? (s?u)?(?u?(p?q))?
((r?s)?(?r??s)) B1=(?p?q)?((q??r)?(?q?r))
? ((?p?q??r)?(?p??q?r)?(q??r)) （分配律） B2=(s?u)?(?u?(p?q))
? ((s??u)?(p?q?s)?(p?q?u)) （分配律） B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u) 再令 ((r?s)?(?r??s))=B3，则
B1?B2?B3 ? (?p??q?r?s??u)?(p?q??r??s?u)
6. 构造公式A=(p?q)?( ?q?r)? (?p?q)??r的否证, 从而证明 它是矛盾式. 解 消解序列:
① p?q A的简单析取式 ② ?p?q A的简单析取式 ③ q ①,②消解 ④ ?q?r A的简单析取式 ⑤ ?r A的简单析取式 ⑥ ?q ④,⑤消解 ⑦ ? ③,⑥消解
这是A的一个否证, 从而证明A是矛盾式. 7. 用消解法判断下述公式是否是可满足的: (p??q)?(q??r)?(?q??r) 解 S=(p??q)?(q??r)?(?q??r)
第1次循环 S0=?,S1={p??q, q??r, ?q??r}, S2=? p??q, q??r 消解得到p??r q??r, ?q??r消解得到?r S2={p??r,?r}
第2次循环 S0={p??q, q??r, ?q??r},S1={p??r,?r}, S2=? S2=?
输出“Yes”,计算结束.
(三) 命题逻辑推理理论 二、