离散数学(本)2016年10月份试题讲解

1离散数学（本）2016年10月份试题一、单项选择题（每小题3分，本题共15分）1．若集合A＝{1,2,3,4}，则下列表述不正确的是()．A．1AB．{1,2,3}AC．{1,2,3}AD．A2．设A＝｛1,2,3｝，B={1,2,3,4}，A到B的关系R＝｛〈x,y〉|x=y｝，则R为()．A.{1,2,2,3}B.{1,1,1,2,1,3,1,4,1,5}C.{1,1,2,1}D.{1,1,2,2,3,3}3．无向图G的边数是10，则图G的结点度数之和为（）．A.10B.20C.30D.54．设连通平面图G有v个结点，e条边，r个面，则（）．A．r+v-e=2B．v+e-r=4C．v+e–r=–4D．v+e-r=25．设个体域D是整数集合，则命题xy(x=y+2)的真值是（）．A.不确定B.TC.由y的取值确定D.F二、填空题（每小题3分，本题共15分）6．设集合A={a,b,c}，B={b,c,d}，C={c,d,e}，则(BC)–A等于．7．设A={2,3}，B={1,2}，C={3,4}，从A到B的函数f={2,2,3,1}，从B到C的函数g={1，3,2，4}，则Dom(gf)等于．8．若图G=V,E，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为．9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G-S中的连通分支数不超过．10．设个体域D＝{1,2,3,4}，A(x)为“x小于10”，则谓词公式(x)A(x)的真值为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“小明是学生，小张是飞行员．”翻译成命题公式．12．将语句“当大家都进入教室，则讨论会开始进行．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）13．空集的幂集是空集．14．(x)(P(x)→Q(y)∨R(z))中的约束变元有x与y．五．计算题（每小题12分，本题共36分）15．设A={1,2,3}，R={x,y|xA，yA且x+y=4}，S={x,y|xA，yA且x=y}，试求R，S，R-1，r(S)．16．图G=V,E，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d),(c,2e),(d,e)}，对应边的权值依次为2、3、4、5、6、7，6及2，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．17．试画一棵带权为1,2,4,5,6的最优二叉树,并计算该最优二叉树的权．六、证明题（本题共8分）18．试证明：P→QP→（(P∨Q)）．3离散数学（本）2016年10月份试题参考解答一、单项选择题（每小题3分，本题共15分）1．C2．D3．B4．A5．B二、填空题（每小题3分，本题共15分）6．{d}7．{2，3}8．(b,c)9．610．真（或T，或1）三、逻辑公式翻译（每小题6分，本题共12分）11．设P：小明是学生，Q：小张是飞行员．（2分）则命题公式为：P∧Q．（6分）12．设P：大家都进入教室，Q：讨论会开始进行．（2分）则命题公式为：P→Q．（6分）四、判断说明题（每小题7分，本题共14分）13．错误．（3分）空集的幂集不为空，为{}（7分）14．错误．（3分）约束变元仅有x．（7分）五．计算题（每小题12分，本题共36分）15．解：R={1,3,2,2,3,1}（3分）S={1,1,2,2,3,3}（6分）R-1={3,1,2,2,1,3}（9分）r(S)={1,1,2,2,3,3}（12分）说明：对于每一个求解项，如果基本求出了解，可以给对应1分．16．解：（1）G的图形表示为：（3分）4（2）邻接矩阵：0110010111110110110101110（6分）（3）粗线表示的图是最小生成树，（10分）权值为11（12分）17．解：（10分）权为13+23+42+52+62=39．（12分）六、证明题（本题共8分）18．证明：（1）P→QP（1分）（2）PP（附加前提）（3分）（3）QT（1）（2）I（5分）（4）P∧QT（2）（3）I（6分）（5）(P∨Q)T（4）E（7分）（6）P→(P∨Q)CP规则（8分）另证：设P→（(P∨Q)）为F，（1分）则P为T，(P∨Q)为F，（3分）即P∧Q为F．（4分）所以P为T，Q为F，（5分）从而P→Q也为F．（6分）所以P→QP→((P∨Q))．（8分）说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。另，可以用真值表验证。125634711185离散数学（本）2016年7月份试题一、单项选择题（每小题3分，本题共15分）1．若集合A＝{1,2,3,4}，B＝{1,3,5}，则下列表述正确的是()．A．A＝BB．BAC．BAD．BA2．设A＝｛1,2,3｝，B={2,4,6}，A到B的关系R＝｛〈x,y〉|2x=y｝，则R=()．A.{1,3,2,4,3,5}B.{2,1,4,3,6,5}C.{1,1,2,2,3,3}D.{1,2,2,4,3,6}3．无向图G是棵树，边数是10，则G的结点度数之和是（）．A.20B.9C.10D.114．下面的推理正确的是（）．A．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．B．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．C．(1)（x）(F（x）→G（x））前提引入(2)F（y）→G（x）ES（1）．D．(1)（x）（F（x）→G（x））前提引入(2)F（y）→G（y）US（1）．5．设个体域为整数集，则公式xy(x+y=2)的解释可为()．A.任一整数x，对任意整数y满足x+y=2B.对任一整数x，存在整数y满足x+y=2C.存在一整数x，对任意整数y满足x+y=2D.存在一整数x，有整数y满足x+y=2二、填空题（每小题3分，本题共15分）6．设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则B∪(A–C)等于．7．设A={1,2}，B={2,3}，C={3，4}，从A到B的函数f={1,2,2,3}，从B到C的函数g={2,3,3,4}，则Ran(gf)等于．8．两个图同构的必要条件包括结点数相等、边数相等与．9．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，v值为5，e值为4则r的值为．10．设个体域D＝{1,2,3,4}，则谓词公式(x)A(x)消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“昨天下雨，今天仍然下雨．”翻译成命题公式．12．将语句“若不下雨，我们就去参加比赛．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）13．若图G是一个欧拉图，则图G中存在欧拉路．614．无向图G的结点数比边数多1，则G是树．五．计算题（每小题12分，本题共36分）15．设集合A={1,2,3,4}上的关系：R={1，2,2，3,3，4}，S={1，1,2，2,3，3}，试计算（1）RS；（2）R1；（3）r（RS）．16．图G=V,E，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．17．求（P∨Q）∨R的析取范式与主合取范式．六、证明题（本题共8分）18．设A，B，C均为任意集合，试证明：A(BC)=(AB)(AC)．7离散数学（本）2016年1月份试题参考解答一、单项选择题（每小题3分，本题共15分）1．C2．D3．A4．D5．B二、填空题（每小题3分，本题共15分）6．{1,2,3,4}7．{3,4}8．度数相同的结点数相等9．110．A(1)∨A(2)∨A(3)∨A(4)三、逻辑公式翻译（每小题6分，本题共12分）11．设P：昨天下雨，Q：今天下雨．（2分）则命题公式为：P∧Q．（6分）12．设P：下雨，Q：我们去参加比赛．（2分）则命题公式为：P→Q．（或Q→P）（6分）四、判断说明题（每小题7分，本题共14分）13．正确．（3分）因为若图G是一个欧拉图，则图中存在欧拉回路．（5分）按定义知，欧拉回路也是欧拉路．（7分）14．错误．（3分）反例：如图G的结点数比边数多1，但不是树．（或：按定义有：无向图G是树当且仅当无向图G是连通图且边数比结点数少1．）（7分）说明：举出符合条件的反例均给分．五．计算题（每小题12分，本题共36分）15．解：（1）RS=={1，2，2，3}；（4分）（2）R1={2，1,3，2,4，3}；（8分）（3）r（RS）={1，1,2，2,3，3,4，4}（12分）16．解：G的图形表示为：8（3分）邻接矩阵：0111101111011110（6分）粗线表示的图是最小的生成树，权为5：（9分）（12分）17．解：（P∨Q）∨R(P∧Q)∨R析取范式（5分）(P∨R)∧(Q∨R)（7分）((P∨R)∨(Q∧Q))∧(Q∨R)（9分）((P∨R)∨(Q∧Q))∧((Q∨R)∨(P∧P))（10分）(P∨R∨Q)∧(P∨R∨Q)∧(Q∨R∨P)∧(Q∨R∨P)（11分）(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)主合取范式（12分）六、证明题（本题共8分）18．证明：设S=A(BC)，T=(AB)(AC)，若x∈S，则x∈A且x∈BC，即x∈A，并且x∈B且xC，（2分）所以x∈(AB)且x(AC)，得x∈T，（3分）所以ST．（4分）反之，若x∈T，则x∈(AB)且x(AC)，（5分）即x∈A，x∈B，且xC，则得x∈BC，（6分）即得x∈A(BC)，即x∈S，所以TS．（7分）因此T=S．（8分）另，可以用恒等式替换的方法证明．9离散数学数理逻辑部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是数理逻辑部分的综合练习。一、单项选择题1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为()A．PQB．QPC．QPD．QP2．设命题公式G：)(RQP,则使公式G取真值为1的P，Q，R赋值分别是()A．0,0,0B．0,0,1C．0,1,0D．1,0,03．下列公式()为重言式．A．PQPQB．(Q(PQ))(Q(PQ))C．(P(QP))(P(PQ))D．(P(PQ))Q4．下列等价公式成立的为()．A．PQPQB．P(QP)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)Q5．命题公式)(QP的主析取范式是(A)．A．QPB．QPC．QPD．QP6．命题公式（P∨Q）→R的析取范式是(B)A．（P∨Q）∨RB．（P∧Q）∨RC．（P∨Q）∨RD．（P∧Q）∨R7．设C(x):x是国家级运动员，G(x):x是健壮的，则