离散数学模拟题B-2009

1离散数学模拟测试题B一、选择题(每题1分，共12分)，下列每题只有一个正确答案,选择正确答案并将序号填写在括号内。1.设A,B,C是任意三个集合，下列关于集合的命题中正确的是（）(A)如果AB且BC，则AC(B)如果AB且BC，则AC(C)如果AB且BC，则AC(D)如果AB且BC，则AC2.下列各关系中具有自反性和反对称性的关系是（）(A)R是自然数集合N上的关系，且xRy当且仅当xy或yx(B)R是自然数集合N上的关系，且xRy当且仅当3xy(C)R是有理数集合Q上的关系，且xRy当且仅当2yx(D)R是自然数集合N上的关系，且xRy当且仅当4xy3.设集合{1,2,3}A，下列关系中不是等价关系的是（）(A){(1,1),(2,2),(3,3)}R(B){(1,1),(2,2),(3,3),(3,2),(2,3)}R(C){(1,1),(2,2),(3,3),(1,4)}R(D){(1,1),(2,2),(1,2),(2,1),(1,3),(3,1),(3,3),(2,3),(3,2)}R4.设,,XYZ为任意集合，且{1,2,3}XY，{2,3,4}XZ，若2Y，则一定有()(A)1Z(B)2Z(C)3Z(D)4Z5.下列命题为假的是（）(A){,{}}{{,{}}}abab(B)({,{}})P(C)XYYX(D){}aXaX6.下面哪个公式是重言式（）(A)()PQR(B)()()PRPQ(C)()()PRQR(D)(())(()())PQRPQPR7.谓词公式()(()()())()xPxyRyQx中的x是（）(A)自由变元(B)约束变元2(C)既是自由变元又是约束变元(D)既不是自由变元又不是约束变元8.设Z为整数集，下面哪个序偶不构成偏序集（）(A)(,)Z（:小于关系）(B)(,)Z（:小于等于关系）(C)(,)Z（:等于关系）(D)(,)Z（:整除关系）9.任何图中必有偶数个（）(A)度数为偶数的结点(B)入度为奇数的结点(C)度数为奇数的结点(D)出度为奇数的结点10.给定无向图(,)GVE如图1所示，下面哪个边集不是其边割集（）(A)1434{(,),(,)}vvvv(B)4546{(,),(,)}vvvv(C)4748{(,),(,)}vvvv(D)1223{(,),(,)}vvvv图11.设图(7,23)G为无向图，则G一定是（）(A)完全图(B)树图1(C)简单图(D)多重图12.下图中是哈密尔顿图的是（）二、填空题(每空1分，共12分)，请将正确的答案填在横线内。1．设{,}ab是字母表，*表示由*上的字符构成的有限长度的串的集合（包含长度为0的字符串，即空串在内）。{,,,,,}Aabaabbaaabbb，{*2}B，{*2}C，则()ABC=。2.设{{{1,2}},{1}}A，则幂集()PA=。3.在1到1000的整数内（含1与1000在内）既不被6整除也不被10整除的数有个。4.设{1,2,,10}A，则A上的自反关系，对称关系有个。5.设偏序集(,)A中，其中{2,3,4,,1000}A，表示整除关系，该偏序集所有极大元构成的集合是。6．设解释I为：个体域{,}Dab，()Fx与()Gx为两个一元谓词，且()0Fa，3()1Fb，()1Ga，()0Gb。在I下，公式(()())xFxGx的真值是。7.令()Fx：x为苹果，(,)Sxy：x与y完全相同，(,)Exy：xy。则命题“没有完全相同的苹果”的符号化形式为：。8.无向图G有11条边，4个3度顶点，其余均为5度顶点，G的阶数n=。9.(,)GVE,1234{,,,}Vvvvv的邻接矩阵0101101111001000A，则1v的入度=，4v的出度=，2v到4v长度为2的路有条。10.有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，则一共有种药品。三、计算题(要求写出计算过程，每题5分，共35分)1.用等值演算法求下面公式的主析取范式((()))pqpqr2.找出下列集合等式成立的充分必要条件，并简单说明理由()()ABAC3.求下面公式的前束范式(()(,,))xFxyGxyz4.设{1,2,3}A，R为AA上的等价关系，且((,),(,))abcdR当且仅当abcd。(1)设I为AA上的恒等关系，求RI；(2)求R对应的AA的划分。5.图G是连通简单平面图，阶数6n，边数12m，求G的各面的次数。6.集合{2,3,6,12,24,36}A上的偏序关系为整除关系。设{6,12}B，{2,3,6}C，试画出的哈斯图，并求,,ABC的最大元，极大元，最小元，极小元。7.设{1,2,3,4}X，{(1,2),(2,4),(3,3)}R，求(),(),()rRsRtR四、证明题(每题5分，共20分)1.设{1,2,3,9}A，在AA上定义关系((,),(,))Rabcd当且仅当adbc，证明R是AA的等价关系。2.R为集合A上二元关系，如果R是反自反的和传递的，则R一定是反对称的。3.若有n个人，每个人都有恰有5个朋友，则n必为偶数。4.利用推理规则证明，前提：()ABC，()EFC，()BAS，结论：BE。4五、综合题(每题7分，共21分)1.一个学校有507，292，312，和344位学生分别选了微积分、离散数学、数据结构和程序设计语言课，且有14人选了微积分和数据结构课，213人选了微积分和程序设计语言课，211人选了离散数学和数据结构课，43人选了离散数学和程序设计语言课，没有学生同时选择微积分和离散数学课，也没有学生同时选数据结构和程序设计语言课，问有多少学生在微积分，离散数学，数据结构或程序设计语言中选了课？2.令P(x),Q(x)和R(x)分别为语句“x是教授”，“x无知”，“x爱慕虚荣”。用量词、逻辑联结符和P(x),Q(x)，R(x)表示下列语句。假定论域是所有人集合。(1)没有无知的教授。(2)所有无知者均爱慕虚荣。(3)没有爱慕虚荣的教授。(4)能从(1)和(2)推出(3)吗？为什么？3.某中学，张、王、李、赵4名教员下学期要承担他们都熟悉的4门课程：数学，物理，化学和英语，(1)试讨论学校安排他们授课的方案数；(2)在上述各方案中，有多少种是完全不同的方案（即每位教员所授课程都不同的方案）