离散数学习题课

1、第一章第一章 习题课习题课一、一、 本章的主要内容及要求本章的主要内容及要求 1 基本内容基本内容 等值式与等值演算等值式与等值演算 基本的等值式（基本的等值式（24个公式）个公式） 主析取与主合取范式主析取与主合取范式 联结词全功能集联结词全功能集 判断推理是否正确的不同方法判断推理是否正确的不同方法真值表法真值表法等值演算法等值演算法 主析取范式法主析取范式法 构造证明法构造证明法2. 要求要求 深刻理解等值式的概念深刻理解等值式的概念 牢记基本等值式的名称及内容牢记基本等值式的名称及内容 了解简单析取式、简单合取式、析取范式、合取范式了解简单析取式、简单合取式、析取范式、合取范式的概念的

2、概念 深刻理解极小项、极大项的概念、名称及下角标与成深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解主析取范式与极小项的真、成假赋值的关系，并理解主析取范式与极小项的关系关系 熟练掌握求主范式的方法（真值表）熟练掌握求主范式的方法（真值表） 熟练掌握熟练掌握用公式的主范式求公式的成真、成假赋值及用公式的主范式求公式的成真、成假赋值及判断公判断公式的类型及简单应用式的类型及简单应用 会将任何公式化成任何联结词完备集中的公式会将任何公式化成任何联结词完备集中的公式 理解并记住推理形式结构的如下形式：理解并记住推理形式结构的如下形式： (a1 a2 ak)b 前提：前提： a

3、1, a2, , ak 结论：结论：b 熟练掌握判断推理是否正确的方法（如真值表法、熟练掌握判断推理是否正确的方法（如真值表法、构造证明法构造证明法等）等） 牢记牢记各条推理定律（内容与名称）各条推理定律（内容与名称） 掌握附加前提证明法及归谬法掌握附加前提证明法及归谬法 1已知命题公式a 中含 3 个命题变项p, q, r，并知道它的成真赋值为001, 010, 111, 求 a 的主析取范式和主合取范式. 答案 a 的主析取范式为 m1 m2 m7 a 的主合取范式为 m0 m3 m4 m5 m6 二、练习题二、练习题2在以下各联结词集中各求一个公式与在以下各联结词集中各求一个公式与a=

4、q a= q 等值。等值。 (1) , (2) , (3) , (4) (5) 解解: (1)aq qq 满足要求满足要求(1) (2)a( q) q 满足要求满足要求(3) (3)a( q q) 满足要求满足要求(2) (4)a q q (q q) (q q) 满足要求满足要求(4) (5)a qq (q q) (q q) 满足要求满足要求(5)3 3、设计一个符合如下要求的室内照明控制线路：在房间的、设计一个符合如下要求的室内照明控制线路：在房间的门外、门内及床头分别装有控制同一个电灯门外、门内及床头分别装有控制同一个电灯f f的的3 3个开关个开关a a、b b、c c，当且仅当一个开关

5、的搬键向上或，当且仅当一个开关的搬键向上或3 3个开关的搬键向上时电个开关的搬键向上时电灯亮。证明灯亮。证明f f的逻辑关系可表示为的逻辑关系可表示为a a (b(b c)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

6、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） 前提：pq, q 结论：p （2） 前提：qr, pr 结论：qp 解 （1）答案：不正确）答案：不正确 验证答案，需将推理形式结构改为另一种形式验证答案，需将推理形式结构改为另一种形式 ( pq ) q p (* *) 只需证明只需证明 (* *)不是重言式不是重言式 方法一方法一 等值演算等值演算 ( pq) q p (p q) q) p ( p q) q p

7、( p q) ( q q) p p q 易知易知10是成假赋值，故是成假赋值，故(* *)不是重言式，所以推理不正确不是重言式，所以推理不正确. 方法二方法二 主析取范式法主析取范式法 经过演算后可知经过演算后可知 (* *) m0 m1 m3 未含未含 m2, 故故(* *)不是重言式不是重言式. 方法三方法三 真值表法真值表法 (* *)的真值表为的真值表为: : p q ( pq) q p 0 0 0 1 1 0 1 1 1 1 0 1 结论（不正确）是对的结论（不正确）是对的 方法四方法四 直接观察出直接观察出 10 是成假赋值是成假赋值 解（解（2）答案：推理正确）答案：推理正确 方法一方法一 真值表法（自己做）真值表法（自己做） 方法二方法二 等值演算法（自己做）等值演算法（自己做） 方法三方法三 主析取