2022年2022年离散数学期末考试 2.pdf

《2022年2022年离散数学期末考试 2.pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学期末考试 2.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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是实数集，“+，”是实数的四则运算，则下面说法正确的是A、是群

2、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、11 D、6 二

3、、填空题 (本大题共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上的二元运算，若存在S，对任意

4、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 分，共 10 分)1、用

5、命题公式将下列命题符号化：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 . 答案：1-5 B

8、ADBB 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 表示 2 是偶数

9、；令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（x）EI规则（

10、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(PR) = (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(y)xR(x) =

11、 (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)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)bacdr(R)bacds(R)bacdt(R)名师资料总结 - - -精

12、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 11. G(PQ)(PQR) (P QR)(PQR)(PQR) m6m7m3 (3, 6, 7) H = (P(QR)(Q(PR) (P Q)(QR)(PQR) (P QR)(PQR)(PQR)(PQR)( PQR) (P QR)(PQR)(PQR) m6m3m7 (3, 6, 7) G,H的主析取范式相同，所以G = H. 13. (1)0000100001000101RM1000000011000010

13、SM(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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7

14、 页 - - - - - - - - - (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(AB) (AA)(AB) (AB) (AB) AB 而 (AB)B = (AB)B = (AB)(BB) = (AB)= AB 所以： A (AB) = (AB)B. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -