离散数学试题与参考答案.doc

《离散数学试题与参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《离散数学》试题及答案一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。1.命题公式为()(A)矛盾式(B)可满足式(C)重言式(D)合取范式2．设P表示“天下大雨”，Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）。(A)．；　(B)．；　　(C)．；　(D)．．3.设集合A={{1,2,3},{4,5},{6,7,8}}，则下式为真的是()(A)1ÎA(B){1,2,3}ÍA(C){{4,5}}ÌA(D)ÆÎA4.设A＝{1,2},B={a,b,c},C={c,d},则A×(BÇ

2、C)=()(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}5.设G如右图：那么G不是().(A)哈密顿图；(B)完全图；(C)欧拉图；(D)平面图.二、填空题：本大题共5小题，每小题4分，共20分。把答案填在对应题号后的横线上。6.设集合A={Æ,{a}}，则A的幂集P(A)=7.设集合A={1,2,3,4},B={6,8,12},A到B的关系R＝,那么R－1＝8.在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9.写出一个不含“”的逻辑联结词的完备集.10.设X＝{

3、a,b,c}，R是X上的二元关系，其关系矩阵为MR＝，那么R的关系图为三、证明题（共30分）11.（10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)12.（10分）构造证明：(P®(Q®S))∧(ØR∨P)∧QÞR®S13.（10分）证明与，与等势。四、解答题(共35分)14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个方阵，且方阵中的每一行,每一列及主、副对角线上的各数之和都相等.）15.（8分）求命题公式的真值表.4/416.（10分）设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{}

4、的二元关系，R1={<1,a>,<1,b>,<2,c>},R2={,}求R1·R2的集合表达式.17.（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？三个条件：(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。ahhcbh第10题答案图一、单项选择题(每小题3分，共15分)1.B2.C3.C4.A5.B二、填空题(每小题4分，共20分)6.7.{<6,3>,<8,4>}8.老乡9.或或或10.见第10题答案图.11.证明：∵xÎA∩（B∪C）ÛxÎA∧xÎ（B∪

5、C）2分ÛxÎA∧（xÎB∨xÎC）3分Û（xÎA∧xÎB）∨（xÎA∧xÎC）5分ÛxÎ（A∩B）∨xÎA∩C7分ÛxÎ（A∩B）∪（A∩C）9分∴A∩（B∪C）=（A∩B）∪（A∩C）10分12.证明：（1）R附加前提（2）ØR∨PP2分（3）PT(1)(2)，I3分（4）P®(Q®S)P4分（5）Q®ST(3)(4)，I5分（6）QP6分（7）ST(5)(6)，I8分（8）R®SCP10分13.证明：a)设，作如下：2分5分b)设，作如下：7分4/410分14.492357816填对每个格得1分。15.PQPÙQØPØQØPÚØQ(PÙQ)Ù(ØPÚØQ)

6、0001110010101010001101110000表中最后一列的数中，每对1个数得2分.16.(2分)(4分)(6分)(10分)17.解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：A®CÅD，Ø(B∧C)，C®ØD必须同时成立。2分因此(A®CÅD)∧Ø(B∧C)∧(C®ØD)Û(ØA∨(C∧ØD)∨(ØC∧D))∧(ØB∨ØC)∧(ØC∨ØD)Û(ØA∨(C∧ØD)∨(ØC∧D))∧((ØB∧ØC)∨(ØB∧ØD)∨ØC∨(ØC∧ØD))Û(ØA∧ØB∧ØC)∨(ØA∧ØB∧ØD)∨(ØA∧ØC)∨(ØA∧ØC∧ØD)∨(C

7、∧ØD∧ØB∧ØC)∨(C∧ØD∧ØB∧ØD)∨(C∧ØD∧ØC)∨(C∧ØD∧ØC∧ØD)∨(ØC∧D∧ØB∧ØC)∨(ØC∧D∧ØB∧ØD)∨(ØC∧D∧ØC)∨(ØC∧D∧ØC∧ØD)ÛF∨F∨(ØA∧ØC)∨F∨F∨(C∧ØD∧ØB)∨F∨F∨(ØC∧D∧ØB)∨F∨(ØC∧D)∨FÛ(ØA∧ØC)∨(ØB∧C∧ØD)∨(ØC∧D∧ØB)∨(ØC∧D)Û(ØA∧ØC)∨(ØB∧C∧ØD)∨(ØC∧D)4/4ÛT8分故有三种派法：B∧D，A∧C，A∧D。10分4/4