《2022年2022年离散数学题库 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学题库 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 离散数学试题 1 一、单项选择题(本大题共15 小题，每小题1 分，共 15 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列句子为命题的是( ) A.走，看电影去B.x+y0 C.空集是任意集合的真子集D.你明天能来吗 ? 2.下列式子不是谓词合式公式的是( ) A.(x)(P(x) ( x)(Q(x) A(x ，y) B.(x)( y)P(x，y) C.(x)P(x) R(y) D.(x)P(x) Q(y，z) 3.下列式子为重言式的是( ) A.PPQ B.(PQ)(P Q) C. (P Q) D.(PQ) (P
2、Q) 4.设个体域为实数集，特定元素a=0，函数 f(x， y)=x-y ，特定谓词F(x， y)为 xy，下列公式真值为真的是( ) A.(x)(y)F(x， f(f(x ，y)，y) B.(x)(y)(F(f(x ，y)，x) C.(x)(y)(z)(F(x，y) F(f(x ，z)，f(y， z) D.(x)F(f(a ，x)，a) 5.对于公式 (x)(y)P(x ，y)Q(x，z)( x)P(x ，y)，下列说法正确的是( ) A.x 是自由变元B.x 是约束变元C.( x)的辖域是 P(x，y) Q(x，z) D.(x)的辖域是P(x，y) 6.设论域为 1，2，与公式 (x)A(
3、X) 等价的是 ( ) A. A(1) A(2) B. A(1) (A2)C. A(1) A(2)D. A(1)A(2)7.设 Z+是正整数集， f：Z+ Z+ Z+，f(n，m)=nm，则 f( ) A.仅是单射B.仅是满射C.是双射D.不是函数8.下列哪个关系矩阵所对应的关系具有自反性( ) A.001111101B.101110001C.001100100D.001010101名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - -
4、- 2 10.在整数集上，下面哪个运算不是二元运算 ( ) A.加法B.减法C.乘法D.除法11.设 A 是奇数集合， 为乘法运算，则是( ) A.半群B.群C.循环群D.交换群12.下面不满足结合律的运算是( ) A.a*b=min(a ，b) B.a*b=max(a ，b) C.a*b=2(a+b) D.a*b=2ab 13.右图的最小入度是( ) A.0 B.1 C.2 D.314.下面既是汉密尔顿图又是欧拉图的图形是( ) 15.一棵树有 3 个 5 度点、 1 个 4 度点、 3 个 2 度点，其它的都是1 度，那么它的边数是( ) A.17 B.18 C.19 D.20 二、填空题
5、 (本大题共 10 小题，每小题2 分，共 20 分 ) 请在每小题的空格中填上正确答案。错填、不填均无分。16.设命题变元为P，Q，R，则小项 m100=_，大项 M010=_。18.一个公式， 如果量词均在全式的_，其作用域延伸到整个公式的_，则该公式称为前束范式。19.请用联结词，表示联结词和联结词：_，_。20.设 A=l ，2，3，4 ，A 上的二元关系R=， ， S=， ，则 RS=_， (RS)-1=_。21.代数系统 是整环，则 是_，是_，且无零因子。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
6、 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 3 22.在实数集 R 上定义运算a b=a+b+ab，则幺元为 _，元素 2 的逆元为 _。23.若回路中，除 _外_各不相同，则此回路称为圈(或初级回路 )。24.偶图记为 Kn,m那么当 _时， Kn,m是平面图，当 _时， Kn,m是非平面图。25.若图中存在 _，它经过图中所有的边恰好_次，则称该图为欧拉图。三、计算题 (本大题共 6 小题，每小题5 分，共 30 分) 26.用等值演算求 (PQ) R 的主合取范式。27.列出 (P (QR) (PQ)的真值表。28设 A=a,b,c,d ，
7、R=，求 R 的传递闭包。29.设 A=2 ，3，6，12，24，36 ，请画出 A 上整除关系的哈斯图，并给出子集6，12，24，36 的下界、下确界、极大元、最大元。31.用矩阵的方法求右图中结点u2，u5之间长为 2 的路径的数目。四、证明题 (本大题共 3 小题，第 32 小题 8 分，第 33、34 小题各 6 分，共 20 分) 32.用推理方法证明：PQ，PR，QS RS。33.设 A=|a，b Z+，Z+为整数集 ，A 上的关系 R=,|ad=bc ，证明 R 是等价关系。五、综合应用题（本大题共2 小题，第 35 小题 6分，第 36 小题 9 分，共 15 分）35符号化下
8、面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。36设 H 是 G 的有限子集，则是群 的子群当且仅当是群 的子代数。离散数学试题 2 一、单项选择题(本大题共15 小题，每小题1 分，共 15 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。1.下列句子为命题的是( ) A.全体起立 ! B.x=0 C.我在说谎D.张三生于 1886 年的春天2.下列式子不是谓词合式公式的是( ) A.),()(),(),()(zxRzzxQyxPxB. ),()(),(),()(yxPxzxQyxPyxC. )()(
9、)()()()(xQxPxxQxPx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 4 D. ),()()(zyQxPx3.下列式子为矛盾式的是( ) A.PPB.)(QPPC.PPD.)(QPQP4.设给定赋值N 如下：个体域为自然数集；特定元素a=0；特定函数f(x,y)=x+y,g(x,y)=xy；特定谓词F(x,y)为 x=y。在赋值 N 下，下列公式为真的是( ) A. ),()(xaxgFxB. ),(),()()
10、(xayfFyaxfFyxC. ),()()(zyxfFzyxD. ),(),()(yxgyxfFyx5.对于公式),()(),(),()(zxRzzxQyxPx，下列说法正确的是( ) A.y 是自由变元B.x 是约束变元C. )(x 的辖域是),()(),(),(zxRzzxQyxPD. )(x 的辖域是 P(x,y) 6.设论域为 l ，2 ，与公式)()(xAx等价的是 ( ) A.A(1)A(2) B. A(1)A(2) C.A(1) D. A(2)A(1) 7.设 Z+是正整数集合，f:Z+Z+，f(n)=2n-2,则 f( ) A.仅是单射B.仅是满射C.是双射D.不是函数8.下
11、列关系矩阵所对应的关系具有反自反性的是( ) A.001110101B. 101110001C. 001100100D. 00101010110.设 A 是奇数集合，下列构成独异点的是( ) A. B. C. D. 11.设 A 是整数集，下列说法正确的是( ) A.有零元B.有零元C.有幺元D.有幺元12.下列说法不正确的是 ( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 5 A.在实数集上，乘法对加法是可分配的B.
12、在实数集上，加法对乘法是可分配的C.在某集合的幂集上，对是可分配的D.在某集合的幂集上，对是可分配的13.右图的最大入度是( ) A.0 B.1 C.2 D.3 14.下列可一笔画成的图形是( ) 15.一棵树有 5 个 3 度结点， 2 个 2 度结点，其它的都是l 度结点，那么这棵树的结点数是( ) A.13 B.14 C.16 D.17 二、填空题 (本大题共 10 小题，每小题2 分，共 20 分) 请在每小题的空格中填上正确答案。错填、不填均不得分。16.请写出表示分配律的两个命题公式等价定理_,_。17.n 个命题变元的 _称为大项，其中每个变元与它的否定不能同时出现，但两者必须_
13、。19.请用联结词，表示联结词和联结词：_，_。20.设 A=1 ，2，3， 4，B=2，4，6，则 A-B=_，AB=_。21.给出 A=l ，2上的一个等价关系_，并给出其对应的划分_。22.设 A=l ，2， 3，4， A 上的二元关系R=， ，S=， ，则 RS =_，(RS)-1=_。23.代数系统 是域，则 _和 _都是交换群。24.若图中存在 _，它经过图中所有的_，则称该图为汉密尔顿图。25.n 点完全图记为Kn，那么当 _时， Kn是平面图，当_时， Kn是非平面图。三、计算题 (本大题共 6小题，每小题5 分，共 30 分) 26.列出)(PQ)(QRP的真值表。27.用等
14、值演算求P(QR)的主析取范式。28.设 A=1,2,3,4 ，给定 A 上的二元关系R=,，求 R 的传递闭包。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 6 31.用矩阵的方法求右图中结点v1，v3之间长度为2 的路径的数目。四、证明题 (本大题共 3小题，第 32 小题 8 分，第 33、34 小题各 6 分，共 20 分 ) 32.用推理方法证明：)(,SPRRQQPS。33.设 H 是 G 的非空子集，则是群 的
15、子群当且仅当对任意a,bH 有 a b-1H。34证明整数集Z 上的大于等于关系“”是一个偏序关系。五、综合应用题(本大题共2 小题，第 35 小题 6 分，第 36 小题 9 分，共 15 分) 35将下面命题符号化，并构造推理证明：所有有理数是实数，有些有理数是整数，所以有些实数是整数。36某城市拟在六个区之间架设有线电话网，其网点间的距离如下列有权矩阵给出，请绘出有权图，给出架设线路的最优方案，并计算线路的总长度。00610500070896703021003040580401092010离散数学试题 3 一、单项选择题（本大题共15 小题，每小题1 分，共 15 分）在每小题列出的四个
16、备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列句子不是命题的是（）A中华人民共和国的首都是北京B张三是学生C雪是黑色的D太好了！2下列式子不是谓词合式公式的是（）A （x）P(x)R(y) B (x) P（x）(x)(P(x) Q(x) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 7 C (x)( y)(P(x)Q(y)( x)R(x) D (x)(P(x,y)Q(x,z)(
17、 z)R(x,z) 3下列式子为重言式的是（）A (PR)QBPQR RC P(PQ) D(PQ)(PQ) 4在指定的解释下，下列公式为真的是（）A (x)(P(x)Q(x),P(x): x=1,Q(x): x=2,论域 : 1,2 B ( x)(P(x)Q(x),P(x): x=1,Q(x): x=2,论域 : 1,2 C ( x)(P(x) Q(x),P(x): x2,Q(x): x=0,论域 : 3,4 D (x)(P(x)Q(x),P(x): x2,Q(x): x=0,论域 : 3,4 5对于公式 (x) ( y)(P(x)Q(y)( x)R(x,y)，下列说法正确的是（）A y 是自
18、由变元By 是约束变元C ( x)的辖域是 R(x, y) D(x)的辖域是 ( y)(P(x)Q(y)( x)R(x,y) 6设论域为 1,2 ，与公式 (x)A(x)等价的是（）A A(1)A(2) BA(1)A(2) C A(1)A(2) DA(2)A(1) 7设 Z+是正整数集， R 是实数集， f: Z+R, f(n)=log2n ,则 f（）A仅是单射B仅是满射C是双射D不是函数8下列关系矩阵所对应的关系具有反对称性的是（）A001110101B101110001C001100100D00101010110下列运算不满足交换律的是（）A a*b=a+2b Ba*b=min( a,b
19、) C a*b=|a-b| Da*b=2ab11设 A 是偶数集合，下列说法正确的是（）A 是群B是群C 是群D, ,都不是群12设 * 是集合 A 上的二元运算，下列说法正确的是（）A在 A 中有关于运算 *的左幺元一定有右幺元B在 A 中有关于运算 *的左右幺元一定有幺元名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 8 C在 A 中有关于运算 *的左右幺元，它们不一定相同D在 A 中有关于运算 *的幺元不一定有左右幺元1
20、3题 13 图的最大出度是（）A 0 B1 C 2 D3 14下列图是欧拉图的是（）15一棵树的3 个 4 度点， 4 个 2 度点，其它的都是1 度，那么这棵树的边数是（）A 13 B14 C 15 D16 二、填空题（本大题共10 小题，每小题2 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16请写出表示德摩根律的两个命题公式等价定理_，_。17 n 个命题变元的_ 称为小项，其中每个变元与它的否定不能同时出现，但两者必须_。19自由变元代入规则是指对某_出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且_。20设 A=,B=2,4 ，则
21、(A)=_，AB_。21设 A=1,2,3,4, A 上的二元关系R=, S=, ，则 R2S=_，(R-1)2=_。22设代数系统 是环，则 是_， 是 _。23在 中，元素 2 的阶为 _，它生成的子群为_，其中7为模 7 乘法。三、计算题（本大题共6 小题，每小题5 分，共 30 分）26给定论域D=1,2 ，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T , 在该赋值下，求式子x(S( f(x)G(x, f(x)的真值。27请通过等值演算法求(PQ)(PQ)的主析取范式。28设 A=1,2,3,4 ，给定 A 上二元关系R=,，求
22、R 的传递闭包。30用矩阵的方法求题30 图中结点 ui， u5之间长度为2 的路径的数目。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 9 31求题 31 图的最小生成树。四、证明题（本大题共3 小题，第 32 小题 8 分，第 33、34 小题各 6 分，共 20 分）32用推理方法证明(AB)(CD),(D F)E AE。33证明：设 是一个群，则对于任意a, bG，必存在惟一的xG 使得 ax=b。34设图 G 有
23、n 个结点， n+1 条边，证明： G 中至少有一个结点度数3。五、应用题（本大题共2 小题，第 35 小题 9 分，第 36 小题 6 分，共 15 分）35符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。36两个等价关系的并集不一定是等价关系，试举例说明。离散数学试题 4 一、单项选择题（本大题共15 小题，每小题1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列为两个命题变元P，Q 的小项是（）A PQ P B PQ C PQ D PPQ 2下列语
24、句中是真命题的是（）A我正在说谎B严禁吸烟C如果 1+2=3，那么雪是黑的D如果 1+2=5，那么雪是黑的3设 P：我们划船， Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A P Q B P Q C （PQ）D （ P Q）4命题公式（ P（PQ） ） Q 是（）A矛盾式B蕴含式C重言式D等价式5命题公式（PQ） R 的成真指派是（）A 000，001，110，B001，011，101，110，111 C全体指派D无6在公式（x ）F（x， y）（y）G（x，y）中变元x 是（）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元名师资料总结 - - -精
25、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 10 7集合 A=1 ，2， , ， 10 上的关系 R=|x+y=10，xA，yA ，则 R 的性质是（）A自反的B对称的C传递的、对称的D反自反的、传递的8若 R 和 S 是集合 A 上的两个关系，则下述结论正确的是（）A若 R 和 S是自反的，则R S 是自反的B若 R 和 S是对称的，则RS 是对称的C若 R 和 S是反对称的，则RS 是反对称的D若 R 和 S是传递的，则R S 是传递的9R=，
26、 ，则下列不是t（R）中元素的是（）A B C D 10设 A=1 ，2，3 ，4，5，6，7，8 ，下列选项正确的是（）A 1A B1，2，3A C 4 ，5A DA 11在自然数集N 上，下列运算是可结合的是（）A a b=a-2bBab=min a， b C ab=-a-bDab=|a-b| 12在代数系统中，整环和域的关系是（）A整环一定是域B域不一定是整环C域一定是整环D域一定不是整环14设 G 为有 n 个结点的简单图，则有（）A (G) nB(G) nC (G)nD(G)n15具有 4个结点的非同构的无向树的数目是（）A 2 B3 C 4 D5 二、填空题（本大题共10 小题，每
27、小题2 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16 （x） （y） （P （ x，y）Q（y，z） ）xP（x，y）中x 的辖域为 _，x 的辖域为 _。17两个重言式的析取是_式，一个重言式与一个矛盾式的析取是_式。18设 N 是自然数集合，f 和 g 是 N 到 N 的函数，且 f（n）=2n+1，g（ n）=n2，那么复合函数（ff） （n）=_（gf） （n） =_。19设复合函数g f 是从 A 到 C 的函数，如果g f 是满射，那么_必是满射，如果gf 是单射，那么 _必是单射。20设 A=1 ，2 ，B=2 ，3 ，则 A-A=_ ，A-B=_ 。
28、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 11 21设 S 是非空有限集，代数系统中，其中P（S）为集合S 的幂集，则P（S）对运算的单位元是 _，零元是 _。22在 中， 2 的阶是 _。24在下图中，结点v2的度数是 _。25设图 D=，V= v1，v2，v3，v4，若 D 的邻接矩阵A=1001001111011010，则 deg-（v1）=_，从 v2到 v4长度为 2 的路有 _条。三、计算题（本大题共5 小
29、题，第 26、27 小题各 5 分，第 28、29 小题各 6 分，第 30 小题 8 分，共 30 分）26已知 A=，1 ，B=，1，1 ，计算 AB，A+B，A 的幂集 P（A） 。27构造命题公式（ （PQ） P） R 的真值表。28下图给出了一个有向图。 （1）求出它的邻接矩阵A； （2）求出 A2，A3，A4及可达矩阵 P。29求下列公式的主合取范式和主析取范式：P（ P（ Q（ QR） ） ）30设 A=1 ，2，3，4，6，8，12，24，R 为 A 上的整除关系，试画的哈斯图，并求A 中的最大元、最小元、极大元、极小元。四、证明题（本大题共3 小题，第 31、32 小题各 6
30、 分，第 33 小题 8 分，共 20 分）31在整数集Z 上定义：Z,2bababa，证明： 是一个群。32R 是集合 A 上自反和传递的关系，试证明：RR=R。五、应用题（本大题共2 小题，第 34 小题 6 分，第 35 小题 9 分，共 15 分）34构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。35今有 n个人，已知他们中任何2 人的朋友合起来一定包含其余n-2 人。试证明：（1）当 n3 时，这 n 个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。（2）当 n4 时，这 n 个人能排成一圆圈，使得每个人是其两旁的人的朋友。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -