(完整word版)离散数学期末考试.pdf
《(完整word版)离散数学期末考试.pdf》由会员分享,可在线阅读,更多相关《(完整word版)离散数学期末考试.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、是群B、是群C、是半群D、是独
2、异点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 二、填空题(本大题共8 题,共 10 个空,每空
3、2 分,共 20 分)1、设关系R=,则R逆关系R1=_。2、在代数系统(Q是有理数集,“+”是有理数加法)中,单位元是_,2 的逆元是 _。3、设集合M=1,2,3,5,则M的幂集P(M)包含 _个元素。4、设T是一棵有n(n2)个顶点的树,则T有_条边。5、设 是一个代数系统,是S上的二元运算,若存在S,对任意xS,有x=x=,则称是的_。6、设 是一个代数系统,若满足结合律且中有单位元,则称为一个_。7、设D是有向图,若D的基图是连通图,则称D是_图8、既不含 _也不含 _的无向图称为简单图。三、计算题(本大题共3 小题,每小题10 分,共 30 分)1、用等值演算法求公式A=)()(r
4、pqp的主析取范式。2、求公式)()()()(zyzHyyPsxGxQx,的前束范式。3、设集合A=1,2,3,4,5,关系R=x,yA且x整除y,要求:(1)列出R的所有元素;(2)写出R的关系矩阵MR;(3)求偏序集 的极大元、极小元和最小元。四、应用题(本大题共2 小题,每小题5 分,共 10 分)1、用命题公式将下列命题符号化:2 和 5 是偶数,当且仅当52。2、用谓词公式将下列命题符号化:每个计算机专业的学生都要学编译原理,但有些计算机专业的学生不学经济学。五、证明题(本大题共2 小题,每小题10 分,共 20 分)1、在命题逻辑系统中用归结法证明下列推理是有效的:前提:qs,qp
5、,s结论:p2、在谓词逻辑系统中写出下列推理的(形式)证明:前提:)()(xPxMx,)()(xGxMx,)(xGx结论:)(xxP计算题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=(P Q)(PQR)(2)H=(P(QR)(
6、Q(PR)13.设 R 和 S是集合 Aa,b,c,d上的关系,其中R(a,a),(a,c),(b,c),(c,d),S文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10
7、 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8
8、X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6
9、文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:C
10、Y1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5
11、Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 H
12、V5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6(a,b),(b,c),(b,d),(d,d).
13、(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 BADBB 6-10 BBABB 1.,2.0,-2 3.16 4.n-1 5.零元6.半群7.弱连通8.平行边环三1.101111010011)()()()()()()()(mmmmrqprqprqprqprpqprpqp2.),()()
14、,()(),()(),()(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 是偶数;令q 表示 5 是偶数;r 表示 52;rqp)(2.S(x):x 是计算机专业的学生;G(x):x 要学编译原理;F(x):x 学经济学;)()()()(xFxSxxGxSx五1,(1)s 前提引入(2)qs前提引入(3)sq置换规则文档编码:CY1F1I5Y3E6 HV5
15、S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q1
16、0L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 Z
17、R1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3
18、V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档
19、编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1
20、F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3
21、E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6(4)q 1,3 析取三段论(5)qp前提引入(6)p4,5 拒取(1))()(xGxMx前提引入(2)M(x)v G(x)EI规则(3))(xGx前提引入(4))(xGAI 规则(5)M(x)2,4 析取三
22、段论(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(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)
23、,(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)文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1
24、U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3
25、L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码:CY1F1I5Y3E6 HV5S6P8Q10L10 ZR1U8X3V3L6文档编码
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 离散数学 期末 考试
限制150内