《2022年2022年离散数学期末考试 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学期末考试 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、单项选择题（本大题共10 小题，每小题2 分，共 20 分）1、设集合M=a，N =a ， 则MN=（） 。A、 B、 C、a D、a，a 2、设关系F=， ，G=， 则FG=（） 。A、， ， B、， C、， D、， 3、设集合H=1， 2，3，4，则H上的关系R=x+y是偶数 具有（） 。A、自反性、反对称性和传递性B、反自反性、反对称性和传递性C、反自反性、对称性和传递性D、自反性、对称性和传递性4、设T是一棵完全二叉树，则T的每个结点都（） 。A、至少有两个子结点B、至多有两个子结点C、恰有两个子结点D、可以有任意多个子结点5、设R是实数集，“+，”是实数的四则运算，则下面说法正确
2、的是A、是群B、是群C、是半群D、是独异点6、下面关系中，函数关系是（） 。A、， ， B、， C、， D、， 7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（） 。A、结合律B、交换律C、分配律D、幂等律8、设Z是整数集，“”是整数减法，则下列说法正确的是（） 。A、不是代数系统B、的单位元是0 C、是代数系统D、的单位元是1 9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（） 。A、简单通路B、初级通路C、简单回路D、初级回路10、设G有 6 个 3 度点， 2 个 4 度点，其余顶点的度数均为0，则G的边数是（） 。A、10 B、13 C、1
3、1 D、 6 二、填空题 (本大题共8 题，共 10 个空，每空2 分，共 20 分 )1 、设关系R= ， ， ，则R逆关系R1=_。2、在代数系统 （Q是有理数集， “+”是有理数加法）中，单位元是_，2 的逆元是 _。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 3、设集合M=1，2， 3，5，则M的幂集P（M）包含 _个元素。4、设T是一棵有n(n2)个顶点的树，则T有_条边。5、设 是一个代数系统，是S上的二元运算，
4、若存在S，对任意xS，有x=x=，则称是的_。6、设是一个代数系统，若满足结合律且中有单位元，则称为一个_。7、设D是有向图，若D的基图是连通图，则称D是_图8、既不含 _也不含 _的无向图称为简单图。三、计算题 (本大题共3 小题，每小题10 分，共 30 分)1、用等值演算法求公式A=)()(rpqp的主析取范式。2、求公式)()()()(zyzHyyPsxGxQx，的前束范式。3、设集合A=1，2，3，4，5，关系R=x，yA且x整除y，要求：（1）列出R的所有元素； （2）写出R的关系矩阵MR；（3）求偏序集 的极大元、极小元和最小元。四、应用题 (本大题共2 小题，每小题5 分，共
5、10 分 )1、用命题公式将下列命题符号化：2 和 5 是偶数，当且仅当52。2、用谓词公式将下列命题符号化：每个计算机专业的学生都要学编译原理，但有些计算机专业的学生不学经济学。五、证明题（本大题共2 小题，每小题10 分，共 20 分）1、在命题逻辑系统中用归结法证明下列推理是有效的：前提：qs，qp，s结论：p2、在谓词逻辑系统中写出下列推理的（形式）证明：前提：)()(xPxMx，)()(xGxMx，)(xGx结论：)(xxP计算题6. 设命题公式G = (PQ)(Q(PR), 求 G 的主析取范式。7. (9 分)设一阶逻辑公式：G = ( xP(x) yQ(y)xR(x)，把 G
6、化成前束范式. 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 = (P Q)(PQR) (2) H = (P(QR)(Q(PR) 13. 设 R 和 S是集合 Aa, b, c, d上的关系，其中R(a, a),(a, c),(b, c),(c, d), S名师资料总结 - - -精品资料欢迎下载 - - - - - - -
7、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - (a, b),(b, c),(b, d),(d, d). (1) 试写出 R和 S的关系矩阵； (2) 计算 R?S , RS, R1, S1?R1. 证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵 QS 。2. 设 A,B 为任意集合，证明：(A-B)-C = A-(B C). 3. (本题 10 分)利用形式演绎法证明：AB, CB, CD蕴涵 AD。4. (本题 10 分)A, B为两个任意集合，求证：A(AB) = (AB) B
8、. 答案：1-5 BADBB 6-10 BBABB 1. ， 2. 0， -2 3. 16 4. n-1 5.零元 6.半群 7.弱连通8.平行边环三1.101111010011)()()()()()()()(mmmmrqprqprqprqprpqprpqp2.),()(),()(),()(),()(zyHyPsxGxQxzyzyHyPzysxGxQx3.4, 2,5, 1,4, 1,3, 1,2, 1,5,5,4,4,3,3,2,2,1 , 1)1(R10000501000400100301010211111154321)2(RM（3）最小元 =1 极小元 =1 极大元 =5 四1.令 p
9、表示 2 是偶数；令q 表示 5 是偶数； r 表示 52；rqp)(2.S（x） ：x 是计算机专业的学生；G（x） ：x 要学编译原理 ；F（x） ：x 学经济学；)()()()(xFxSxxGxSx五1， （1）s 前提引入（2）qs前提引入（3）sq置换规则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - （4）q 1,3 析取三段论（5）qp前提引入（6）p4,5 拒取（1）)()(xGxMx前提引入（2）M（x）v G
10、（x）EI规则（3）)(xGx前提引入（4）)(xGAI 规则（5）M(x) 2,4 析取三段论（6）)()(xPxMx前提引入（7）M(x) P（x）AI 规则（8）P（x）5,7 假言推理（9）)(xxPEG规则6. G = (PQ)(Q (P R) = (PQ)(Q(PR) = (PQ) (Q(PR) = (PQ) (QP)(QR) = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = (PQR)(PQR)(PQR)(PQR)(PQR) = m3m4m5m6m7 = (3, 4, 5, 6, 7). 7. G = ( xP(x) yQ(y)xR(x) = (xP(x)yQ
11、(y)xR(x) = (xP(x)yQ(y)xR(x) = ( xP(x)y Q(y)zR (z) = x yz(P(x)Q(y)R(z) 9. (1) r(R)R IA (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) RR2 R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d) ；关系图 : (2)bacdr(R)bacds(R)bacdt(R)
12、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 11. G(PQ)(PQR) (P QR)(P QR)(PQR) m6m7m3 (3, 6, 7) H = (P(QR)(Q (PR) (P Q)(QR) (P QR) (P QR)(P QR)(PQR) (PQ R)(P QR) (P QR)(PQR)(PQR) m6m3m7 (3, 6, 7) G,H的主析取范式相同，所以G = H. 13. (1)00001000010001
13、01RM1000000011000010SM(2)R?S(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),S1?R1(b, a),(d, c). 四 证明题1. 证明： PQ, RS, PR蕴涵 QS(1) PRP (2) RPQ(1) (3) PQ P (4) RQQ(2)(3) (5) QRQ(4) (6) RSP 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
14、 - - - - - 第 5 页，共 7 页 - - - - - - - - - (7) QSQ(5)(6) (8) QS Q(7) 2. 证明： (A-B)-C = (AB)C = A (BC) = A (BC) = A-(BC) 3. 证明： AB, CB, CD蕴涵 AD (1) A D(附加 ) (2) AB P (3) B Q(1)(2) (4) CB P (5) BC Q(4) (6) C Q(3)(5) (7) CD P (8) D Q(6)(7) (9) AD D(1)(8) 所以 AB, CB, CD蕴涵 AD. 1.证明： A(AB) = A (AB) A(A B) (AA)(AB) (AB) (AB) AB 而 (AB)B = (AB)B = (AB) (BB) = (AB)= A B 所以： A (AB) = (AB)B. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -