(5.5)--离散数学试卷离散数学.doc

《(5.5)--离散数学试卷离散数学.doc》由会员分享，可在线阅读，更多相关《(5.5)--离散数学试卷离散数学.doc（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|

11、 (x+1)24, Q=x | x2+165x ，则下列各式中成立的是： 【 】A. QP B. QP C. PQ D. PQ2、,下列式子中正确的有： 【 】 A. 1(S) B. 1(S) C. 1(S) D. 以上都不是3、P：你努力，Q：你失败。“虽然你努力了，但还是失败了”符号化为： 【 】A. PQ B. QP C. PQ D. PQ4、设论域E=a, b ，且P(a,a)=T， P(a,b)=F， P(b,a)=T， P(b,b)=F； 则在下列公式中真值为T的是： 【 】A$xyP(x,y) BxyP(x,y) CxP(x,x) Dx$yP(x,y) 5、谓词公式中，变元x是：

12、 【 】A自由出现 B约束出现 C既是约束出现，又是自由出现 D以上都不是6、.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条： 【 】A汉密尔顿回路 B欧拉回路 C汉密尔顿通路D初级回路7、设|V|1，G= 是强连通图，当且仅当： 【 】AG中至少有一条通路 BG中至少有一条回路CG中有通过每个结点至少一次的通路 DG中有通过每个结点至少一次的回路8、由5个结点构成的根树中，其边数m最多为： 【 】A2； B3； C5； D4 ；9、设A=1，2，3，A上二元关系S=，则S具有的性质是：【 】A自反关系 B传递关系 C对称关系 D反自反关系10、集合A上的等价关系R，决定

13、了A的一个划分，该划分就是： 【 】 AA与R的并集AR BA与R的交集，记作AR CA与R的商集，记作A/R DA与R的差集，记作A - R二、填空题(本大题共10小题，每题2分,共20分)11、已知集合A=1，1，2，则A的幂集为 。12、设P是所有人的集合，在P上定义关系R、S为R=|a，bPa是b的父亲，S=|a，bPa是b的母亲，那么关系|a，bx a是b的祖母的表达式为 .。13、P、Q为两个命题，当且仅当 时，PQ的真值为114、n个命题变元的_称为极小项，其中每个变元与它的否定不能同时出现，但两者必须_。 15、设，则M= ，N= ， MN= ，M N= 。16、个体域为自然数

14、集，P（x）：x为奇数，Q（x）：x为素数，则命题“存在既是奇数又是素数的自然数”形式化为： 。17 、设R为非空集合A上的等价关系，其等价类记为xR。 x,yA，若x,yR，则xR与yR的关系是_ _，而若x,y R，则xRyR=_。18Kn是 个结点的完全图，则K5有_条边，每个结点的度数为_。19设S=1，2，则S上可以定义 个不同的二元关系，其中有 个是等价关系。20在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树有 个4度顶点。三、 简答题（本大题共6小题，每题6分，共36分）四、 21、构造命题公式(p (q r)p的真值表。22、是否可以分别画出无向简单图，使各点的度

15、与下面给出的序列一致。如可能，画出符合条件的无向图，如不可能，说明原因。（1）1，1，2，2，3 （2）1，2，2，2，1 23、求公式（PQ）（ PR）的主析取范式，并根据主析取范式直接确定公式的成真赋值和成假赋值。 24、设集合A=1,2,3，A上关系R=|xA yAx +3y8,关系S= ,。求Dom（R），Ran（R），R。S，R-1，r（R）及s（R）25. 某班有学生30人，其中16人会打篮球，14人会打排球，10人会打篮球和排球，8人会打篮球和网球，还有5人会打这三种球，而11个会打网球的人都会打两外一种球（指篮球或排球），求不会打这三种球的人数。26、设A1，3，5，9，15，

16、45，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。四、 证明题(2小题，每题5分，共10分。)27、设A,B,C是任意四个集合，证明: A（B C）=(AB)(AC) 28、证明：$x(A(x)B(x) xA(x)$xB(x)五、综合应用题（本题共2小题，每题7分，共14分）29、今有a，b，c，d，e，f，g共7人，已知下列事实：a会讲汉语和英语；b会讲英语和韩语；c会讲英语和意大利语；d会讲法语、俄语和意大利语；e会讲俄语和韩语；f会讲汉语；g会讲法语和汉语。试问这7个人应如何排座位（圆桌），才能使每个人和他身边的人交谈?。30、如果他是计算机系本科生或者是计

17、算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，构造该推理的证明。新疆大学2013至2014学年第一学期期末考试 离散数学 试题A标准答案及评分标准第一部分 选择题（共20分）一、单项选择题（每题只有一个正确答案，答对一题得2分，共20 分）1、A 2、A 3、C 4、C 5、D 6、B 7、D 8、D 9、B 10、C第二部分 非选择题（共80 分）二、填空题 (本大题共10小题，每题2分，共20分。)11、P(A)= ,12、x=11, y=4 13、

18、P为真，Q为假（p=1，q=0） 14、P 15、6,12, 2,4,8,1016、（） 17、相等（等价）、18、n=3,且每一对顶点度之和=n 19、 2nm、 2n2 20、9三、简答题（本大题有4个小题,每题5分，共20分。）21、|s|-|AB|=50-(26+21-14)=17人 22、(1) 不符合握手定理，所以不能画出图 （2）符合条件的无向图为：23、=P（3）P（5）P（7）=111=1 为真24、dom（R）=A，RS=，R=， r(R)=， s（R）=，25、析取范式：pq，合取范式：q（pq）； 主析取范式：pq23612弄真指派：（1,1） ，弄假指派：（0,0），

19、（0,1），（1,0）最大元：6 极大元：6最小元：没有 极小元：2，326、哈斯图为：四、证明题(3小题，每题5分，共15分。)27、对任一x，所以：A-(BC)=(A-B)(A-C)28、 xy(P(x)Q(y) x（ P(x)y Q(y)）（因为P（x）中不含y，所以y可以移入Q前） x P(x)y Q(y) （因为Q（y）中不含x，所以x可以移入P前） 证毕29、证明：（1）对任意一序偶，又有R2 = RR R2 z(R R) 根据R的传递性，有R,所以，R2 R （2） 任意序偶 R, 又因为R自反性，则有R 所以：RR,根据合成运算的规则，可得：RR=R2 所以：R R2 由（1）（2）可得：当关系R传递且自反时，R2=R六、应用题（1小题，共10分）30、解 将每个人作为一个项点，如果两个人会讲同一种语言，就在代表他们的二个项点间连一条边，边上标明二人公用的语言，这样就可得一简单无向图G。根据图GGECABDF德语汉语俄语英语意大利语日语法语无向图G，又因为A只会讲英语，而B只会讲汉语，所以不能给出符合条件的方案。离散数学试题A 第 11页（共6页）