《离散数学模拟测验》由会员分享，可在线阅读，更多相关《离散数学模拟测验（11页珍藏版）》请在金锄头文库上搜索。
1、新疆大学20132014学年度第二学期期末考试离散数学试卷A第一部分 选择题（共20 分）一、单项选择题（本大题共10小题，每题只有一个正确答案，答对一题得2分共20分） 1、对任意集合A、B、和C，下列论断中正确的是： 【 】A. 若AB，BC，则AC B. 若AB，BC，则AC C. 若AB，BC，则AC D. 若AB，BC，则AC2、设A=a,a,下列式子中正确的有： 【 】 A. a(A) B. a(A) C. a(A) D. 以上都不是3、P：我将去镇上。Q：我有时间。命题“我将去镇上，当且仅当我有时间”符号化为： 【 】A. PQ B. QP C. PQ D. QP4、命题公式：（
2、P（PQ）Q 是 【 】A矛盾式 B. 可满足式 C. 重言式 D. 不能确定5、谓词公式中，量词的辖域是：【 】A. B. C. D. 6、在如下各图中，哪一个是欧拉图？ 【 】7、设|V|1，G= 是强连通图，当且仅当： 【 】AG中至少有一条通路 BG中至少有一条回路CG中有通过每个结点至少一次的通路 DG中有通过每个结点至少一次的回路8、设，则 (S) 有多少个元素？ 【 】A3； B6； C7； D8 ；9、集合A=1，2，3，4，5，6，7，8，9，10上的关系R= | x + y = 10，则R的性质为：【 】A自反的； B对称的； C传递的、对称的； D反自反的、传递的10、集
3、合A上的等价关系R，其等价类集合 aR | a A称为： 【 】 AA与R的并集，记作AR BA与R的交集，记作AR CA与R的商集，记作A/R DA与R的差集，记作A - R二、填空题(本大题共10小题，每题2分,共20分)11、已知集合A=,，则A的幂集为 。12、已知序偶=，则x= ; y= 。13、P、Q为两个命题，当且仅当 时，PQ的真值为014、（PQ）（PQ）可化简为： 。15、设，则 MN= ，M N= 16、个体域为自然数集，P（x）：x为奇数，Q（x）：x为偶数，则命题“不存在既是奇数又是偶数的自然数”形式化为： 。17 、设R为非空集合A上的等价关系，其等价类记为xR。
4、x,yA，若x,yR，则xR与yR的关系是_ _，而若x,y R，则xRyR=_。18Kn为汉米顿图，当且仅当 。19设A、B为集合，|A|=n，|B|=m，则A到B的二元关系共有 个，A上的二元关系共有 个。20一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有 个度数为1的结点？三、计算题 （本大题共6小题，其中21、22、23三题每题5分，24、25、26三题每题7分，共36分）21、某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有14人在两次考试都得优，那么两次考试中都没得优的学生有多少人？ 22、是否可以分别画出无向简单图，使各点的度与下面
5、给出的序列一致。如可能，画出符合条件的无向图，如不可能，说明原因。（1）1，1，2，2，3 （2）1，1，2，2，2 23、给定个体域D=3，5，7，P（x）解释为“x是素数”，求公式的真值。24、设集合A=1,2,3，A上关系R=|xA yAx +3y8,关系S= ,。求Dom（R），Ran（R），RS，R，r（R）及s（R）25. 求公式q（pq）的析取范式、合取范式、主析取范式，并根据主析取范式直接确定公式的弄真指派和弄假指派。26、对2，3，6，12集合上的整除关系画出哈斯图，并对子集2，3，6找出最大元素，最小元素，极大元素，极小元素。四、证明题(3小题，每题5分，共15分。)27、
6、证明：A(BC)=(AB)(AC)28、证明逻辑等价式xy(P(x)Q(y) x P(x)y Q(y)。（方法不限）五、应用题（本大题共1小题，9分）30、有七位客人入席，A只会讲英语；B会讲汉语；C会讲英语、意大利语及俄语；D会讲汉语及日语；E会讲意大利语及德语；F会讲法语，日语及俄语；G会讲德语和法语。问主人能否把七位客人安排在一张圆桌上，使每一位客人与左右邻不用翻译便可交谈。若能安排，请给出一个方案。新疆大学2013至2014学年第第二学期期末考试离散数学 试题A标第一部分 选择题（共20分）一、单项选择题（每题只有一个正确答案，答对一题得2分，共20 分）1、C 2、A 3、C 4、B
7、 5、 6、B 7、D 8、D 9、B 10、C第二部分 非选择题（共80 分）二、填空题 (本大题共10小题，每题2分，共20分。)11、P(A)= ,1,1，2,1,1，2 12、R13、P与Q的真值相同时 14、合取（或），出现一个15、M=3，6，9，12，15，18，N=4，8，12，16，12, 3，6，9，15，1816、）17、相等、18、n=3,且每一对顶点度之和=n19、 16、220、 9三、简答题（本大题共6小题，每题6分，共36分。）21、真值表如下：pqrqrp(qr)p(p (q r)p000011100101110100111011111110000011010
8、0011100001111110022、(1) 不符合握手定理，所以不能画出图 （2）符合条件的无向图为：23、主析取范式：(PQR)(PQR)(PQR)(PQR) 或者 主析取范式=m1m3m6m7 成真赋值为：001，011，110，111 成假赋值为：000，010，100，10124、dom（R）=A，Ran(R)=1,2,RS=，R-1=， r(R)=， s（R）=，25、不会打这三种球的人数为：X=10A、B、C为会打篮球、排球、网球的人的集合，则有：|S|=30 |A|=16,|B|=14,|C|=11,|AB|=10,|AC|=8,|BC|=8,|ABC|=5X=|S|-(|A
9、|+|B|+|C|)+(|AB|+|AC|+|BC|)-|ABC|=1026、R=,根据R中元素，可知R是偏序关系，其哈斯图为：最大元：45，最小元：1，极大元：45，极小元：1四、证明题(2小题，每题5分，共10分。)27、28、证明 ：$x(A(x)B(x)$x(A(x)B(x)$xA(x)$xB(x)xA(x)$xB(x)xA(x)$xB(x) 五、综合应用题（本题共2小题，每题7分，共14分）29、解 能安排，其方案为： H=（A，C，B，E，D，G，F，A） 将每个人作为一个项点，如果两个人会讲同一种语言，就在代表他们的二个项点间连一条边，边上标明二人公用的语言，这样就可得一简单无向
10、图G。所求问题转化为图G中有无Hamilton回路问题。 而上边指出的回路H正好是图G的一条Hamilton回路，因此问题得到解决。30、令p：他是计算机系本科生q：他是计算机系研究生r：他学过DELPHI语言s:他学过C+语言t:他会编程序前提：(pq)(rs),(rs)t结论：pt证p P(附加前提)pq T附加规则(pq)(rs) (前提引入)rs T假言推理规则r T花间规则rs T附加规则(rs)t (前提引入)t T假言推理规则新疆大学20132014学年度第二学期期末考试离散数学试卷A一、单项选择题（本大题共10小题，每题只有一个正确答案，答对一题得2分共20分） 1、设P=x| (x+1)24, Q=x | x2+165x ，则下列各式中成立的是： 【 】A. QP B. QP C. PQ D. PQ2、,下列式子中正确的有： 【 】 A. 1(S) B. 1(S) C. 1
