资源描述：
《离散数学期末考试.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、单项选择题（本大题共10小题，每小题2分，共20分）1、设集合={，}，={{}，}则=（）。A、B、{}C、{}D、{{}，，}2、设关系={<1，>，<2，2>，<，1>}，={<，>，<，c>，<1，2>}则=（）。A、{<1，>，<1，c>，<，2>}B、{<，>，<，c>，<1，>}C、{<，1>，<1，2>}D、{<，1>，<2，2>，<1，>}3、设集合={1，2，3，4}，则上的关系={<，>+是偶数}具有（）。A、自反性、反对称性和传递性B、反自反性、反对称性和传递性C、反自反性、对称性和传递性D、自反性、对称性和传递性4、设是一棵完全二叉树，则的每个结点都（）。
2、A、至少有两个子结点B、至多有两个子结点C、恰有两个子结点D、可以有任意多个子结点5、设是实数集，“+，—，，”是实数的四则运算，则下面说法正确的是A、<，>是群B、<，+>是群C、<，>是半群D、<，—>是独异点6、下面关系中，函数关系是（）。A、{<，1>，<，2>，<，>}B、{<，>，<，>，<1，>}C、{<1，>，<1，>，<，>}D、{<，>，<，>，<，1>}7、设<，>是一个代数系统，若多任意的，，都有=，则称运算在上满足（）。A、结合律B、交换律C、分配律D、幂等律8、设是整数集，“—”是整数减法，则下列说法正确的是（）。A、<，—>不是代数系统B、<，—>的单位元
3、是0C、<，—>是代数系统D、<，—>的单位元是19、设是无向图中的一条通路，中的顶点各不相同，则是一条（）。A、简单通路B、初级通路C、简单回路D、初级回路10、设有6个3度点，2个4度点，其余顶点的度数均为0，则的边数是（）。A、10B、13C、11D、6二、填空题(本大题共8题，共10个空，每空2分，共20分)1、设关系={<，1>，<2，1>，<2，>}，则逆关系=_______________________________。2、在代数系统<，+>（是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。3、设集合={1，2，3，5}，则的
4、幂集（）包含___________个元素。4、设是一棵有(2)个顶点的树，则有_____________条边。5、设<，>是一个代数系统，是上的二元运算，若存在，对任意，有==，则称是<，>的_______________。6、设<，>是一个代数系统，若满足结合律且<，>中有单位元，则称<，>为一个___________________。7、设是有向图，若的基图是连通图，则称是_________________图8、既不含________________也不含____________________的无向图称为简单图。三、计算题(本大题共3小题，每小题10分，共30分)1、用等值演算法
5、求公式=的主析取范式。2、求公式的前束范式。3、设集合={1，2，3，4，5}，关系={<，>，且整除}，要求：（1）列出的所有元素；（2）写出的关系矩阵；（3）求偏序集<，>的极大元、极小元和最小元。四、应用题(本大题共2小题，每小题5分，共10分)1、用命题公式将下列命题符号化：2和5是偶数，当且仅当5>2。2、用谓词公式将下列命题符号化：每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。五、证明题（本大题共2小题，每小题10分，共20分）1、在命题逻辑系统中用归结法证明下列推理是有效的：前提：，，结论：2、在谓词逻辑系统中写出下列推理的（形式）证明：前
6、提：，，结论：计算题6.设命题公式G=Ø(P→Q)∨(Q∧(ØP→R)),求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)∨(ØP∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(ØP∧R))13.设R和S是集合A＝{a,b,c,d}上的关系，其中R＝{(a
7、,a),(a,c),(b,c),(c,d)},S＝{(a,b),(b,c),(b,d),(d,d)}.(1)试写出R和S的关系矩阵；(2)计算R•S,R∪S,R－1,S－1•R－1.证明题1.利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C=A-(B∪C).3.(本题10分)利用形式演绎法证明：{ØA∨B,ØC→ØB,C→D}蕴涵A→D。4.(本题10分)A,B为两个任意集合，求证：A－(A
