离散数学期末考试试题(配答案)

第1页共5页广东技术师范学院模拟试题科目：离散数学考试形式：闭卷考试时间:120分钟系别、班级：姓名：学号：一．填空题（每小题2分，共10分）1.谓词公式)()(xxQxxP的前束范式是__∃x∃y¬P(x)∨Q(y)__________。2.设全集,5,2,3,2,1,5,4,3,2,1BAE则A∩B=__{2}__，A_{4,5}____，BA__{1,3,4,5}_____3.设baBcbaA,,,,，则)()(BA__{{c},{a,c},{b,c},{a,b,c}}__________，)()(AB_____Φ_______。4.在代数系统（N，+）中，其单位元是0，仅有_1___有逆元。5．如果连通平面图G有n个顶点，e条边，则G有___e+2-n____个面。二．选择题（每小题2分，共10分）1.与命题公式)(RQP等价的公式是（）（A）RQP)(（B）RQP)(（C）)(RQP（D）)(RQP2.设集合cbaA,,,A上的二元关系bbaaR,,,不具备关系()性质（A）(A)传递性(B)反对称性(C)对称性(D)自反性3.在图EVG,中,结点总度数与边数的关系是()(A)Evi2)deg((B)Evi)deg((C)VviEv2)deg((D)VviEv)deg(4.设D是有n个结点的有向完全图,则图D的边数为()(A))1(nn(B))1(nn(C)2/)1(nn(D)2/)1(nn5.无向图G是欧拉图,当且仅当()(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数第2页共5页(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。三．计算题（共43分）1.求命题公式rqp的主合取范式与主析取范式。（6分）解：主合取方式：p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)=∏0.2.4主析取范式：p∧q∨r⇔(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)∨(p∧¬q∧r)=∑1.3.5.6.72.设集合dcbaA,,,上的二元关系R的关系矩阵为1000000011010001RM,求)(),(),(RtRsRr的关系矩阵，并画出R，)(),(),(RtRsRr的关系图。（10分）3无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分）第3页共5页解：∵G（V,E），|E|=V，d（Vi）3,设至少有x个节点，由握手定理得：2×12=∑d（Vi）6×3+(x-6)×32(x-6)=＞x8故G中至少有9个节点。4求下面两个图的最小生成树。（12分）5.试判断),(z是否为格？说明理由。（5分）解：（Z,≤）是格，理由如下：对于任意a∈Z，a≤a成立，满足自反性；对于任意a∈Z，b∈Z，若a≤b且b≤a，则a=b，满足反对称性；对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。（注：什么是格？）第4页共5页四．证明题（共37分）1.用推理规则证明DDACCBBA)(,)(,。（10分）证明：编号公式依据（1）（¬B∨C）∧¬C前提（2）¬B∨C，¬C（1）（3）¬B（2）（4）A→B（3）（5）¬A（3）（4）（6）¬（¬A∧D）前提（7）A∨¬D（6）（8）¬D（5）（6）2.设R是实数集，babafRRRf),(,:，abbagRRRg),(,:。求证：gf和都是满射，但不是单射。（10分）证明：要证f是满射，即∀y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。3.无向图G有9个结点，每个结点的度数不是5就是6，求证：G中至少有5个6度结点或6个5度结点。（10分）第5页共5页证明：设G中至多有4个6度结点且5个5度结点，∴d（Vi）=49不是偶数，故它不是一个图，矛盾。（下面只供参考，个人答案）4.设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）证明：设任意两点间的读书和恰好为1，则满足：∑d（Vi）=2ed（Vi）≤6∴6×100≥2ee≤300故最多只有300条边，即300对点距离恰好为1.