离散数学习题集(十五套)---答案.docx
《离散数学习题集(十五套)---答案.docx》由会员分享,可在线阅读,更多相关《离散数学习题集(十五套)---答案.docx(54页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、离散数学试题及答案试卷一一、填空 20% (每小题2分)A B C1设 (N:自然数集,E+ 正偶数) 则 。2A,B,C表示三个集合,文图中阴影部分的集合表达式为 3设P,Q 的真值为0,R,S的真值为1,则的真值= 。4公式的主合取范式为5若解释I的论域D仅包含一个元素,则 在I下真值为6设A=1,2,3,4,A上关系图为则 R2 = 。7设A=a,b,c,d,其上偏序关系R的哈斯图为则 R= 。8图的补图为 。9设A=a,b,c,d ,A上二元运算如下:*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别
2、为 。10下图所示的偏序集中,是格的为 。二、选择 20% (每小题 2分)1、下列是真命题的有()A ; B;C ; D 。2、下列集合中相等的有( ) A4,3;B,3,4;C4,3,3;D 3,4。3、设A=1,2,3,则A上的二元关系有( )个。 A 23 ; B 32 ; C ; D 。4、设R,S是集合A上的关系,则下列说法正确的是( ) A若R,S 是自反的, 则是自反的; B若R,S 是反自反的, 则是反自反的; C若R,S 是对称的, 则是对称的; D若R,S 是传递的, 则是传递的。5、设A=1,2,3,4,P(A)(A的幂集)上规定二元系如下则P(A)/ R=( )AA
3、;BP(A) ;C1,1,2,1,2,3,1,2,3,4;D,2,2,3,2,3,4,A6、设A=,1,1,3,1,2,3则A上包含关系“”的哈斯图为( )7、下列函数是双射的为( )Af : IE , f (x) = 2x ; Bf : NNN, f (n) = ;Cf : RI , f (x) = x ; Df :IN, f (x) = | x | 。(注:I整数集,E偶数集, N自然数集,R实数集)8、图 中 从v1到v3长度为3 的通路有( )条。A 0;B 1;C 2;D 3。9、下图中既不是Eular图,也不是Hamilton图的图是( )10、在一棵树中有7片树叶,3个3度结点,
4、其余都是4度结点则该树有( )个4度结点。A1;B2;C3;D4 。三、证明 26%、 R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当 和在R中有在R中。(8分)、 f和g都是群到的同态映射,证明是的一个子群。其中C= (8分)、 G= (|V| = v,|E|=e ) 是每一个面至少由k(k3)条边围成的连通平面图,则, 由此证明彼得森图(Peterson)图是非平面图。(11分)四、逻辑推演 16%用CP规则证明下题(每小题 8分)1、2、五、计算 18%1、设集合A=a,b,c,d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 (9分)2、如下图所示的赋权
5、图表示某七个城市及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。(分)试卷二试题及答案一、填空 20% (每小题2分)1、 P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻译为 ;“虽然你努力了,但还是失败了”的翻译为2、论域D=1,2,指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。2、 设S=a1 ,a2 ,a8,Bi是S的子集,则由B31所表达的子集是3、 设A=2,3,4,5,6上的二元关系,则R= (列举法)。R的关系矩阵MR=5、设A=1,2,3,则A上既不是对称的又不是反对称的关
6、系R= ;A上既是对称的又是反对称的关系R= 。*a b cabca b cb b cc c b6、设代数系统,其中A=a,b,c,则幺元是 ;是否有幂等 性 ;是否有对称性 。7、4阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n个结点的无向完全图Kn的边数为 ,欧拉图的充要条件是10、公式的根树表示为二、选择 20% (每小题2分)1、在下述公式中是重言式为( )A;B;C; D。2、命题公式 中极小项的个数为( ),成真赋值的个数为( )。A0; B1; C2; D3 。3、设,则 有( )个元素。A3; B6; C7; D8 。4、 设,定义上的等价关系则由 R产 生的上一个划
7、分共有( )个分块。A4; B5; C6; D9 。5、设,S上关系R的关系图为则R具有( )性质。A自反性、对称性、传递性; B反自反性、反对称性;C反自反性、反对称性、传递性; D自反性 。6、设 为普通加法和乘法,则( )是域。A BC D= N 。7、下面偏序集( )能构成格。8、在如下的有向图中,从V1到V4长度为3 的道路有( )条。A1; B2; C3; D4 。9、在如下各图中( )欧拉图。10、设R是实数集合,“”为普通乘法,则代数系统 是( )。A群; B独异点; C半群 。三、证明 46%1、 设R是A上一个二元关系,试证明若R是A上一个等价关系,则S也是A上的一个等价关
8、系。(9分)2、 用逻辑推理证明:所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分)3、 若是从A到B的函数,定义一个函数对任意有,证明:若f是A到B的满射,则g是从B到 的单射。(10分)4、 若无向图G中只有两个奇数度结点,则这两个结点一定连通。(8分)5、 设G是具有n个结点的无向简单图,其边数,则G是Hamilton图(8分)四、计算 14%1、 设是一个群,这里+6是模6加法,Z6=0 ,1,2,3,4,5,试求出的所有子群及其相应左陪集。(7分)2、 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分)试卷二答案:试
9、卷三试题及答案一、 填空 20% (每空 2分)1、 设 f,g是自然数集N上的函数,则 。2、 设A=a,b,c,A上二元关系R= , , , 则s(R)= 。3、 A=1,2,3,4,5,6,A上二元关系,则用列举法 T= ;T的关系图为T具有 性质。4、 集合的幂集= 。5、 P,Q真值为0 ;R,S真值为1。则的真值为 。6、 的主合取范式为 。7、 设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。则谓词的自然语言是8、 谓词的前束范式为二、 选择 20% (每小题 2分)1、 下述命题公式中,是重言式的为( )。A、; B、;C、;
10、D、。2、 的主析取范式中含极小项的个数为( )。A 、2; B、 3; C、5; D、0; E、 8 。3、 给定推理PUSPESTIUG推理过程中错在( )。A、-; B、-; C、-; D、-; E、-4、 设S1=1,2,8,9,S2=2,4,6,8,S3=1,3,5,7,9,S4=3,4,5,S5=3,5,在条件下X及( )集合相等。A、 X=S2或S5 ; B、X=S4或S5;C、X=S1,S2或S4; D、X及S1,S5中任何集合都不等。5、 设R和S是P上的关系,P是所有人的集合,则表示关系 ( )。A、;B、;C、 ; D、。6、 下面函数( )是单射而非满射。A、;B、;C
11、、;D、。其中R为实数集,Z为整数集,R+,Z+分别表示正实数及正整数集。7、 设S=1,2,3,R为S上的关系,其关系图为 则R具有( )的性质。A、 自反、对称、传递; B、什么性质也没有;C、反自反、反对称、传递; D、自反、对称、反对称、传递。8、 设,则有( )。A、1,2 ;B、1,2 ; C、1 ; D、2 。9、 设A=1 ,2 ,3 ,则A上有( )个二元关系。A、23 ; B、32 ; C、; D、。10、全体小项合取式为( )。A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。三、 用CP规则证明 16% (每小题 8分)1、2、四、(14%) 集合X
12、=, , , ,R=,|x1+y2 = x2+y1 。1、 证明R是X上的等价关系。 (10分)2、 求出X关于R的商集。(4分)五、(10%)设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分)六、(20%)1、(10分)设f和g是函数,证明也是函数。2、(10分)设函数,证明 有一左逆函数当且仅当f是入射函数。答案:一、 填空 20%(每空2分)1、2(x+1);2、;3、;4、反对称性、反自反性;4、;5、1;6、;7、任意x,如果x是素数则存在一个y,y是奇数且y整除x ;8、。二、 选择
13、20%(每小题 2分)题目12345678910答案CCCCABDADC三、 证明 16%(每小题8分)1、P(附加前提)TIPTITITIPTICP2、 P(附加前提)TEESPUSTIEGCP四、 14%(1) 证明:1、 自反性:2、 对称性:3、 传递性:即由(1)(2)(3)知:R是X上的先等价关系。2、X/R=五、 10%1、; 关系图2、t (R)= , , , , , , , , 。 六、 20%1、(1)(2)2、证明:试卷四试题及答案一、 填空 10% (每小题 2分)1、 若P,Q,为二命题,真值为0 当且仅当 。2、 命题“对于任意给定的正实数,都存在比它大的实数”令F
14、(x):x为实数,则命题的逻辑谓词公式为 。3、 谓词合式公式的前束范式为 。4、 将量词辖域中出现的 和指导变元交换为另一变元符号,公式其余的部分不变,这种方法称为换名规则。5、 设x是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y是自由的,则 被称为存在量词消去规则,记为ES。二、 选择 25% (每小题 2.5分)1、 下列语句是命题的有( )。A、 明年中秋节的晚上是晴天; B、;C、当且仅当x和y都大于0; D、我正在说谎。2、 下列各命题中真值为真的命题有( )。A、 2+2=4当且仅当3是奇数;B、2+2=4当且仅当3不是奇数;C、2+24当且仅当3是奇数; D、2+
15、24当且仅当3不是奇数;3、 下列符号串是合式公式的有( )A、;B、;C、;D、。4、 下列等价式成立的有( )。A、;B、;C、 ; D、。5、 若和B为wff,且则( )。A、称为B的前件; B、称B为的有效结论C、当且仅当;D、当且仅当。6、 A,B为二合式公式,且,则( )。A、为重言式; B、;C、; D、; E、为重言式。7、 “人总是要死的”谓词公式表示为( )。(论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。A、; B、C、;D、8、 公式的解释I为:个体域D=2,P(x):x3, Q(x):x=4则A的真值为( )。A、1; B、0; C、可满足式;
16、D、无法判定。9、 下列等价关系正确的是( )。A、;B、;C、;D、。10、 下列推理步骤错在( )。PUSPESTIEGA、;B、;C、;D、三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式的类型。(10分)2、 下列问题,若成立请证明,若不成立请举出反例:(10分)(1) 已知,问成立吗?(2) 已知,问成立吗?3、 如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了厂长。问:若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。(10分)四、计算10%1、 设命题A1,A2的真值为1,A3,A4真值为0,求命题的真值。(5分)2、 利用主析取范式,求公式的
17、类型。(5分)五、谓词逻辑推理 15%符号化语句:“有些人喜欢所有的花,但是人们不喜欢杂草,那么花不是杂草”。并推证其结论。六、证明:(10%)设论域D=a , b , c,求证:。答案:六、 填空 10%(每小题2分)1、P真值为1,Q的真值为0;2、;3、;4、约束变元;5、,y为D的某些元素。七、 选择 25%(每小题2.5分)题目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)八、 逻辑判断 30%1、(1)等值演算法(2)真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。2、(1)不成立。若取但A及B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 习题集 十五 答案
限制150内