离散数学与 习题课 .pptVIP

第一章 习题课 一、 本章的主要内容及要求 1 ． 基本内容 等值式与等值演算 基本的等值式（ 24 个公式） 主析取与主合取范式 联结词全功能集 判断推理是否正确的不同方法 ① 真值表法 ② 等值演算法 ③ 主析取范式法 ④ 构造证明法 2. 要求 深刻理解等值式的概念 牢记基本等值式的名称及内容 了解简单析取式、简单合取式、析取范式、合取范式 的概念 深刻理解极小项、极大项的概念、名称及下角标与成 真、成假赋值的关系，并理解主析取范式与极小项的 关系 熟练掌握求主范式的方法（真值表） 熟练掌握用公式的主范式求公式的成真、成假赋值及 判断公式的类型及简单应用 会将任何公式化成任何联结词完备集中的公式 理解并记住推理形式结构的如下形式： ① ( A 1 ù A 2 ù … ù A k ) ? B ② 前提： A 1 , A 2 , … , A k 结论： B 熟练掌握判断推理是否正确的方法（如真值表法、 构造证明法等） 牢记 各条推理定律（内容与名称） 掌握附加前提证明法及归谬法 1 ．已知命题公式 A 中含 3 个命题变项 p , q , r ，并知道它 的成真赋值为 001, 010, 111, 求 A 的主析取范式和主 合取范式 . 答案 A 的主析取范式为 m 1 ú m 2 ú m 7 A 的主合取范式为 M 0 ù M 3 ù M 4 ù M 5 ù M 6 二、练习题 2 ．在以下各联结词集中各求一个公式与A= q 等值。 (1) { ?, ?} (2) {?, ∧} (3) {?, ∨} (4) {?} (5) {?} 解: (1)A?q? ?q?q 满足要求(1) (2)A??(?q)∨ q 满足要求(3) (3)A??(?q ∧ ? q) 满足要求(2) (4)A? q ∨ q ? (q ? q) ? (q ? q) 满足要求(4) (5)A? q∧q ?(q?q)?(q?q) 满足要求(5) 3、设计一个符合如下要求的室内照明控制线路：在房间的门外、门内及床头分别装有控制同一个电灯F的3个开关A、B、C，当且仅当一个开关的搬键向上或3个开关的搬键向上时电灯亮。证明F的逻辑关系可表示为A?(B?C)。 分析：设A、B、C分别表示3个开关状态的命题变项，且开关的搬键向上时对应的命题变项的真值为1，开关的搬键向下时对应的命题变项的真值为0，于是有： F ?(?A ∧?B ∧C)∨(?A ∧B ∧?C) ∨(A ∧ ? B ∧?C) ∨(A ∧ B ∧C) ?(?A ∧((?B ∧C)∨ (B ∧?C))) ∨(A ∧ ((? B ∧?C) ∨(B ∧C))) ?(?A ∧ (B?C )) ∨(A ∧ ((? B ∨ C) ∧(B ∨ ?C))) ?(?A ∧ (B?C )) ∨(A ∧ ?((B ∧ ?C) ∨(?B ∨ C))) ?(?A ∧ (B?C )) ∨(A ∧ ?(B?C )) ?A ? (B?C) 4 ． 用不同的方法验证下面推理是否正确 . 对于正确 的推理还要 给出证明 . （ 1 ） 前提： ? p ? q , ? q 结论： ? p （ 2 ） 前提： q ? r , p ? ? r 结论： q ? ? p 解 （ 1 ）答案：不正确 验证答案，需将推理形式结构改为另一种形式 ( ? p ? q ) ù ? q ? ? p ( * ) 只需证明 ( * ) 不是重言式 方法一 等值演算 ( ? p ? q ) ù ? q ? ? p ? ? (( p ú q ) ù ? q ) ú ? p ? ( ? p ù ? q ) ú q ú ? p ? (( ? p ú q ) ù ( ? q ú q )) ú ? p ? ? p ú q 易知 10 是成假赋值，故 ( * ) 不是重言式，所以推理不正确 . 方法二 主析取范式法 经过演算后可知 ( * ) ? m 0 ú m 1 ú m 3 未含 m 2 , 故 ( * ) 不是重言式 .