《离散数学考试模拟试题及详细参考答案共四套.docx》由会员分享，可在线阅读，更多相关《离散数学考试模拟试题及详细参考答案共四套.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散模拟答案11命题符号化共6小题，每题3分，共计18分1. 用命题逻辑把以下命题符号化a) 假设上午不下雨，我去看电影，否那么就在家里读书或看报。b) 我今日进城，除非下雨。c) 仅当你走，我将留下。2. 用谓词逻辑把以下命题符号化a) 有些实数不是有理数b) 对于全部非零实数x，总存在y使得xy=1。c) f 是从A到B函数当且仅当对于每个aA存在唯一bB，使得f(a)=b.一、 简答题共6道题，共32分1. 求命题公式(P(QR)(R(QP)主析取范式、主合取范式，并写出全部成真赋值。5分2. 设个体域为1,2,3，求以下命题真值4分a) x$y(x+y=4)b) $yx (x+y=4)
2、3. 求x(F(x)G(x)($xF(x)$xG(x)前束范式。4分4. 推断下面命题真假，并说明缘由。每题2分，共4分a) ABC=(A-B) (A-C)b) 假设f是从集合A到集合B入射函数，那么|A|B|5. 设A是有穷集，|A|=5，问每题2分，共4分a) A上有多少种不同等价关系？b) 从A到A不同双射函数有多少个？6. 设有偏序集，其哈斯图如图1，求子集B=b,d,e最小元，最大元、极大元、微小元、上界集合、下界集合、上确界、下确界，(5分)f g d e b ca图17. 有限集S=a1,a2,an,N为自然数集合，R为实数集合，求以下集合基数S;P(S);N,Nn;P(N);R
3、,RR,o,1N写出即可(6分)二、 证明题共3小题，共计40分1. 运用构造性证明，证明下面推理有效性。每题5分，共10分a) A(BC),(EF)C, B(AS)BEb) x(P(x)Q(x), x(Q(x)R(x)，$xR(x) $xP(x)2. 设R1是A上等价关系，R2是B上等价关系，A且B，关系R满意：,R，当且仅当R1且R2。试证明：R是AB上等价关系。10分3. 用伯恩斯坦定理证明0,1和(a,b)等势。10分4. 设R是集合A上等价关系，A元素个数为n，R作为集合有s个元素，假设A关于R商集A/R有r个元素，证明：rsn2。10分三、 应用题10分在一个道路上连接有8个城市，
4、分别标记为a,b,c,d,e,f,g,h。城市之间干脆连接道路是单向，有ab, ac, bg, gb, cf, fe, bd, df.对每一个城市求出从它动身所可以到达全部其他城市。离散数学 考试题答案一、 命题符号化共6小题，每题3分，共计18分1. 用命题逻辑把以下命题符号化a) 设P表示命题“上午下雨，Q表示命题“我去看电影，R表示命题“在家里读书，S表示命题“在家看报，命题符号化为：PQ(PRS)b) 设P表示命题“我今日进城，Q表示命题“天下雨，命题符号化为：QP或PQc) 设P表示命题“你走，Q表示命题“我留下，命题符号化为： QP2. 用谓词逻辑把以下命题符号化a) 设R(x)表
5、示“x是实数，Q(x)表示“x是有理数，命题符号化为：$x(R(x) Q(x) 或 x(R(x) Q(x)b) 设R(x)表示“x是实数，E(x,y)表示“x=y,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) $y(R(y) E(f(x,y),1)c) 设F(f)表示“f是从A到B函数, A(x)表示“xA, B(x)表示“xB,E(x,y)表示“x=y, 命题符号化为：F(f)a(A(a)$b(B(b) E(f(a),b) c(S(c) E(f(a),c) E(a,b)二、 简答题共6道题，共32分1. (P(QR)(R(QP)PQR(PQR) (PQR(PQR) (PQ
6、R) PQR).(PQR (PQR) (PQR) PQR)(PQR) (PQR) 这是主合取范式公式全部成真赋值为000,001,010,100,101,111,故主析取范式为PQR)PQR)PQR)PQR)PQR)PQR)2. a) T b) F3. x(F(x)G(x)($xF(x)$xG(x) x(F(x)G(x)($yF(y)$zG(z) x(F(x)G(x)y$z(F(y)G(z) $xy$z(F(x)G(x) (F(y)G(z)4. a) 真命题。因为ABC=ABC=ACBC=A-CB-Cb) 真命题。因为假如f是从集合A到集合B入射函数，那么|ranf|=|A|，且ranfB,故
7、命题成立。5. a) 52 b) 5!=1206. B最小元是b，无最大元、极大元是d和e、微小元是b、上界集合是g、下界集合是a,b、上确界是g、下确界是b.7. KS=n; KP(S)=; KN=0,KNn=0, KP(N)=; KR=, K=RR= ,K0,1N= 三、 证明题共3小题，共计40分1. a) 证 1B P(附加条件) 2B(AS) P (3) AS T(1)(2) I (4) A T(3) I (5) A(BC) P (6) BC T(4)(5) I (7) C T(6) I (8) (EF)C P (9) (EF) T(7)(8) I (10) EF T(9) E (1
8、1) E T(10) I (12) BE CPb) 证 (1) $xR(x) P (2) R(c) ES(1) (3) x(Q(x)R(x) P (4) Q(c)R(c) US(3) (5) Q(c) T(2)(4) I (6) x(P(x)Q(x) P (7) P(c)Q(c) US(6) (8) P(c) T(5)(7) I (9) $xP(x) EG(8)2. 证 任取,ABxA yBR1R2,R，故R是自反任取,RR1R2R1R2,R.故R是对称。任取,R,RR1R2R1R2(R1R1)(R2R2) R1R2,R, 故R是传递。综上所述R是AB上等价关系。3. 证 构造函数f：0,1(
9、a,b)，f(x)=,明显f是入射函数 构造函数g: (a,b)0,1，,明显g是入射函数， 故0,1和(a,b)等势。由于，所以4. 证 设商集A/Rr个等价类元素个数分别为m1,m2,mr，由于一个划分对应一个等价关系，m1+m2+mr=n， 由于r个数平方平均值大于等于这r个数平均值平方，所以，即四、 应用题10分解 把8个城市作为集合A元素，即A=a,b,c,d,e,f,g,h，在A上定义二元关系R，R当且仅当从x到y有干脆连接道路，即R=,那么该问题即变为求R传递闭包。利用Warshal算法，求得t(R)=那么从城市x动身能到达城市为，故有离散考试模拟试题及答案2一、填空题 1 设集
10、合A,B，其中A1,2,3, B= 1,2, 那么A - B_; r(A) - r(B) _ .2. 设有限集合A, |A| = n, 那么 |r(AA)| = _.3. 设集合A = a, b, B = 1, 2, 那么从A到B全部映射是_ _, 其中双射是_.4. 命题公式G(PQ)R，那么G主析取范式是_.5.设G是完全二叉树，G有7个点，其中4个叶点，那么G总度数为_，分枝点数为_.6 设A、B为两个集合, A= 1,2,4, B = 3,4, 那么从AB_; AB_;AB _ .7. 设R是集合A上等价关系，那么R所具有关系三个特性是_, _, _.8. 设命题公式G(P(QR)，那
11、么使公式G为真说明有_，_, _.9. 设集合A1,2,3,4, A上关系R1 = (1,4),(2,3),(3,2), R1 = (2,1),(3,2),(4,3), 那么R1R2 = _,R2R1 =_,R12 =_.10. 设有限集A, B，|A| = m, |B| = n, 那么| |r(AB)| = _.11 设A,B,R是三个集合，其中R是实数集，A = x | -1x1, xR, B = x | 0x 6 (D)下午有会吗？5 设I是如下一个说明：Da,b, 那么在说明I下取真值为1公式是( ).(A)$xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)x$y
12、P(x,y).6. 假设供选择答案中数值表示一个简洁图中各个顶点度，能画出图是( ).(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).7. 设G、H是一阶逻辑公式，P是一个谓词，G$xP(x), HxP(x),那么一阶逻辑公式GH是( ).(A)恒真 (B)恒假 (C)可满意 (D)前束范式.8 设命题公式G(PQ)，HP(QP)，那么G与H关系是( )。(A)GH (B)HG (C)GH (D)以上都不是.9 设A, B为集合，当( )时ABB.(A)AB(B)AB(C)BA(D)AB.10 设集合A = 1
13、,2,3,4, A上关系R(1,1),(2,3),(2,4),(3,4), 那么R具有( )。(A)自反性 (B)传递性(C)对称性 (D)以上答案都不对11 以下关于集合表示中正确为( )。(A)aa,b,c (B)aa,b,c(C)a,b,c (D)a,ba,b,c12 命题xG(x)取真值1充分必要条件是( ).(A) 对随意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1. (D)以上答案都不对.13. 设G是连通平面图，有5个顶点，6个面，那么G边数是( ).(A) 9条 (B) 5条 (C) 6条 (D) 11条.14. 设G
14、是5个顶点完全图，那么从G中删去( )条边可以得到树.(A)6 (B)5 (C)10 (D)4.15. 设图G相邻矩阵为，那么G顶点数与边数分别为( ).(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.三、计算证明题1.设集合A1, 2, 3, 4, 6, 8, 9, 12，R为整除关系。(1) 画出半序集(A,R)哈斯图；(2) 写出A子集B = 3,6,9,12上界，下界，最小上界，最大下界；(3) 写出A最大元，最小元，极大元，微小元。2. 设集合A1, 2, 3, 4，A上关系R(x,y) | x, yA 且 x y, 求 (1) 画出R关系图；(2) 写出R关系矩阵
15、.3. 设R是实数集合，s,t,j是R上三个映射，s(x) = x+3, t(x) = 2x, j(x) x/4,试求复合映射st，ss, sj, jt，sjt.4. 设I是如下一个说明：D = 2, 3, abf (2)f (3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011试求 (1) P(a, f (a)P(b, f (b);(2) x$y P (y, x).5. 设集合A1, 2, 4, 6, 8, 12，R为A上整除关系。(1) 画出半序集(A,R)哈斯图；(2) 写出A最大元，最小元，极大元，微小元；(3) 写出A子集B = 4, 6, 8, 12上界，下
16、界，最小上界，最大下界.6. 设命题公式G = (PQ)(Q(PR), 求G主析取范式。7. (9分)设一阶逻辑公式：G = (xP(x)$yQ(y)xR(x)，把G化成前束范式.9. 设R是集合A = a, b, c, d. R是A上二元关系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出r(R), s(R), t(R)；(2) 画出r(R), s(R), t(R)关系图.11. 通过求主析取范式推断以下命题公式是否等价：(1) G = (PQ)(PQR) (2) H = (P(QR)(Q(PR)13. 设R和S是集合Aa, b, c, d上关系，其中R(a,
17、a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b, d),(d, d).(1) 试写出R和S关系矩阵；(2) 计算RS, RS, R1, S1R1.四、证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。2. 设A,B为随意集合，证明：(A-B)-C = A-(BC).3. (此题10分)利用形式演绎法证明：AB, CB, CD蕴涵AD。4. (此题10分)A, B为两个随意集合，求证：A(AB) = (AB)B .参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3. 2. .3. a1= (a,1), (b,1), a2= (a,2),
18、 (b,2),a3= (a,1), (b,2), a4= (a,2), (b,1); a3, a4.4. (PQR).5. 12, 3. 6. 4, 1, 2, 3, 4, 1, 2. 7. 自反性；对称性；传递性.8. (1, 0, 0), (1, 0, 1), (1, 1, 0).9. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2mn.11. x | -1x 0, xR; x | 1 x 2, xR; x | 0x1, xR.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(
19、4, 4),(5, 5),(6, 6).14. $x(P(x)Q(x).15. 21.16. (R(a)R(b)(S(a)S(b).17. (1, 3),(2, 2); (1, 1),(1, 2),(1, 3). 二、选择题 1. C. 2. D. 3. B. 4. B.5. D. 6. C. 7. C.8. A. 9. D. 10. B. 11. B. 13. A. 14. A.15. D三、计算证明题1. (1)(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.(3) A无最大元，最小元是1，极大元8, 12, 90+; 微小元是1.2.R = (1,1),(2,1),(2,2
20、),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1) (2)3. (1)sts(t(x)t(x)+32x+32x+3.(2)sss(s(x)s(x)+3(x+3)+3x+6,(3)sjs(j(x)j(x)+3x/4+3, (4)jtj(t(x)t(x)/42x/4 = x/2,(5)sjts(jt)jt+32x/4+3x/2+3.4. (1) P(a, f (a)P(b, f (b) = P(3, f (3)P(2, f (2)= P(3, 2)P(2, 3)= 10= 0. (2) x$y P (y, x) = x (P (2, x)P (3, x)
21、 = (P (2, 2)P (3, 2)(P (2, 3)P (3, 3)= (01)(01)= 11= 1.5. (1)(2) 无最大元，最小元1，极大元8, 12; 微小元是1.(3) B无上界，无最小上界。下界1, 2; 最大下界2.6. G = (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).7. G = (xP(x)$yQ(y)xR(x)= (xP(x)$y
22、Q(y)xR(x)= (xP(x)$yQ(y)xR(x)= ($xP(x)yQ(y)zR(z)= $xyz(P(x)Q(y)R(z)9. (1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)关系图:11. G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3 (3
23、, 6, 7)H = (P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7 (3, 6, 7)G,H主析取范式一样，所以G = H.13. (1) (2)RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c).四 证明题1. 证明：PQ, RS, PR蕴涵QS(1) PRP(2) RPQ(1)(3) PQP(4) RQQ(2)(3)
24、(5) QRQ(4)(6) RSP(7) QSQ(5)(6)(8) QSQ(7)2. 证明：(A-B)-C = (AB)C = A(BC)= A(BC)= A-(BC)3.证明：AB, CB, CD蕴涵AD(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, CD蕴涵AD.4. 证明：A(AB) = A(AB)A(AB)(AA)(AB)(AB)(AB)AB而 (AB)B= (AB)B= (AB)(BB)= (AB)= AB所以：A(AB) = (A
25、B)B.离散考试模拟试题及答案3一、填空题：1设，请在以下每对集合中填入适当符号：。 1 , (2) 。2设，N为自然数集， 假设，那么是 射，假设，那么是 射。3设图G = 中有7个结点，各结点次数分别为2，4，4，6，5，5，2，那么G中有 条边，依据 。4两个重言式析取是 ，一个重言式和一个冲突式合取是 。5设个体域为自然数集，命题“不存在最大自然数符号化为 。6设S为非空有限集，代数系统中幺元为 ，零元为 。7设P、Q为两个命题，其De-Morden律可表示为 。8当时，群只能有 阶非平凡子群，不能有 阶子群，平凡子群为 。二、单项选择题：每题1分，本大题共15分1设，下面哪个命题为假
26、 。 A、 ； B、 ；C、 ； D、。2设，那么BA是 。A、 ； B、 ； C、 ； D、。3以下图描绘偏序集中，子集上界为 。A、 ； B、 ； C、 ； D、。4设和都是X上双射函数，那么为 。A、 ； B、 ； C、 ； D、。5下面集合 关于减法运算是封闭。A、N ； B、 ； C、 ； D、。6具有如下定义代数系统， 不构成群。A、，*是模11乘 ； B、，*是模11乘 ；C、有理数集，*是一般加法 ； D、有理数集，*是一般乘法。7设，*为一般乘法。那么代数系统幺元为 。A、不存在 ； B、 ； C、 ； D、。8下面集合 关于整除关系构成格。A、2，3，6，12，24，36
27、； B、1，2，3，4，6，8，12 ；C、1，2，3，5，6，15，30 ； D、3，6，9，12。9设，那么有向图是 。A、强连通 ； B、单侧连通 ； C、弱连通 ； D、不连通。10下面那一个图可一笔画出 。11在任何图中必定有偶数个 。A、度数为偶数结点 ； B、入度为奇数结点 ；C、度数为奇数结点 ； D、出度为奇数结点 。12含有3个命题变元具有不同真值命题公式个数为 。A、 ； B、 ； C、 ； D、 。13以下集合中哪个是最小联结词集 。A、 ； B、 ； C、 ； D、 。14下面哪个命题公式是重言式 。A、 ； B、 ；C、 ； D、 。15在谓词演算中，以下各式哪个是
28、正确 。A、 ； B、 ；C、 ； D、 。三、推断改正题：每题2分，本大题共20分1设，那么 。其中为PA ( )2设，那么 。 3集合A上恒等关系是一个双射函数。 4设Q为有理数集，Q上运算 * 定义为，那么是半群。 5阶数为偶数有限群中，周期为2元素个数肯定为偶数。 6在完全二元树中，假设有片叶子，那么边总数 。 7能一笔画出图不肯定是欧拉图。 8设P，Q是两个命题，当且仅当P，Q真值均为T时，值为T。 9命题公式是重言式。 10设 命题“全部探讨生都读过高校符号化为：。 四、简答题：25分1设，A上关系 ，求出 。2集合上偏序关系为整除关系。设，试画出哈斯图，并求A，B，C最大元素、极
29、大元素、下界、上确界。3图给出赋权图表示五个城市及对应两城镇间马路长度。试给出一个最优化设计方案使得各城市间可以有马路连通。4，为模7乘法。试说明是否构成群？是否为循环群？假设是，生成元是什么？5给定命题公式，试给出相应二元树。五、证明题：25分1假如集合A上关系R和S是反自反、对称和传递，证明：是A上等价关系。2用推理规那么证明是 有效结论。3假设有n个人，每个人都恰有三个挚友，那么n必为偶数。4设G是11，m图，证明G或其补图是非平面图。离散考试模拟试题及答案4一、填空题11 ， 2。 2双射 ， 满射。 314 ， 。4重言式 ，冲突式 。 5 ， 6 ，S 。 7； 。82，4； 3，
30、5，6，7；。二、单项选择题题号123456789101112131415答案ACBCBDBCCACCABA三、推断改正题1 。2 3 。4 。 5 阶数为偶数有限群中周期为2 元素个数肯定为奇数。6 完全二叉树中，边数。 7 。 8 当且仅当P，Q真值一样时，真值为T。 9 。 10 。四、简答案题1解， ， ，。2解：哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无63解此问题最优设计方案即要求该图最小生成树， 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。4解：既构成群，又构成循环群，其生成元为3，5。因为：运算表为： 1234561123456224613533625144415263553164266543211由运算表知，封闭；2可结合可自证明31为幺元；4，综上所述，构成群。 由，。所以，3为其生成元，3