离散数学 习题课.ppt

《离散数学 习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章习题课一、本章的主要内容及要求1．基本内容等值式与等值演算基本的等值式（24个公式）主析取与主合取范式联结词全功能集判断推理是否正确的不同方法①真值表法②等值演算法③主析取范式法④构造证明法2.要求深刻理解等值式的概念牢记基本等值式的名称及内容了解简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解主析取范式与极小项的关系熟练掌握求主范式的方法（真值表）熟练掌握用公式的主范式求公式的成真、成假赋值及判断公式的类型及简单应用会将任何公式化成任何联结词完备集中的公式理解并记住推理形式结构的如下形式

2、：①(A1ÙA2Ù…ÙAk)®B②前提：A1,A2,…,Ak结论：B熟练掌握判断推理是否正确的方法（如真值表法、构造证明法等）牢记各条推理定律（内容与名称）掌握附加前提证明法及归谬法1．已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取范式.答案A的主析取范式为m1Úm2Úm7A的主合取范式为M0ÙM3ÙM4ÙM5ÙM6二、练习题2．在以下各联结词集中各求一个公式与A=q等值。(1){,}(2){,∧}(3){,∨}(4){}(5){}解:(1)Aqqq满足要求(1)(2)A(q)

3、∨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∧

4、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

5、®q)ÙØq®ØpÛØ((pÚq)ÙØq)ÚØpÛ(ØpÙØq)ÚqÚØpÛ((ØpÚq)Ù(ØqÚq))ÚØpÛØpÚq易知10是成假赋值，故(*)不是重言式，所以推理不正确.方法二主析取范式法经过演算后可知(*)Ûm0Úm1Úm3未含m2,故(*)不是重言式.方法三真值表法(*)的真值表为:pq(Øp®q)ÙØq®Øp000110111101结论（不正确）是对的方法四直接观察出10是成假赋值解（2）答案：推理正确方法一真值表法（自己做）方法二等值演算法（自己做）方法三主析取范式法（自己做）方法四构造证明法证明：（直接证明法）①p®ØrP②r®ØpT①③q®rP④

6、q®ØpT③②请用附加前提证明法证明