离散数学模拟试题讲解

1、离散数学模拟试题一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1设，下面哪个命题为假（ A ）。A、； B、；C、； D、。2设，则BA是（ C ）。A、； B、； C、； D、。3右图描述的偏序集中，子集的上界为 （ B ）。A、b，c； B、a，b； C、b； D、a，b，c。4设和都是X上的双射函数，则为（ C ）。A、； B、； C、； D、。5下面集合（ B ）关于减法运算是封闭的。A、N ； B、； C、； D、。6具有如下定义的代数系统，（ D ）不构成群。A、G=1，

2、10，*是模11乘 ； B、G=1，3，4，5，9，*是模11乘 ；C、G=Q（有理数集），*是普通加法； D、G=Q（有理数集），*是普通乘法。7设，*为普通乘法。则代数系统的幺元为（ B）。A、不存在 ； B、； C、； D、。8下面集合（ C ）关于整除关系构成格。A、2，3，6，12，24，36 ； B、1，2，3，4，6，8，12 ；C、1，2，3，5，6，15，30 ； D、3，6，9，12。9设，则有向图是（C ）。A、强连通的 ； B、单向连通的 ； C、弱连通的 ； D、不连通的。10下面那一个图是欧拉图（ A ）。11在任何图中必定有偶数个（ C）。A、度数为偶数的结点 ；

3、 B、入度为奇数的结点 ；C、度数为奇数的结点 ； D、出度为奇数的结点 。12含有3个命题变元的具有不同真值的命题公式的个数为（ C ）。A、； B、； C、； D、。13下列集合中哪个是最小联结词集（ A ）。A、； B、； C、； D、。14下面哪个命题公式是重言式（ B ）。A、； B、；C、； D、。15在谓词演算中，下列各式哪个是正确的（ A ）。A、； B、；C、； D、。二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。3121、设A1,2,3，则右图所示A上

4、的关系具有（ 2）4)5) ）。 1).自反性 2).反自反性 3).对称性 4).反对称性 5).传递性2、下列语句是命题的有（ 1）3) ）。 1). 明年中秋节的晚上是晴天； 2).； 3). 当且仅当x和y都大于0； 4).我正在说谎。3、A，B为二合式公式，且，则（ 1）2)3)4)5) ）。 1).为重言式； 2).；3).； 4).； 5).为重言式。4、右图所示的图一定不是（ 1）2)3)5) ）。 1).平面图2).二部图3).欧拉图 4).哈密而顿图5).树5、设R和S是集合A上的任意关系，下列命题不成立（ 2）3)4) ）。 1).若R和S是自反的，则RS也是自反的。 2

5、).若R和S是反自反的，则RS也是反自反的。 3).若R和S是对称的，则RS也是对称的。 4).若R和S是传递的，则RS也是传递的三、填空题（本大题共5小题，每题2分，共10分）1、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为（1） PQ或QP ；“虽然你努力了，但还是失败了”的翻译为（2）PQ 。2、设A=2，3，4，5，6上的二元关系，则R=, , （枚举法）。R的关系矩阵MR= *a b cabca b cb b cc c b3、设代数系统，其中A=a，b，c,则幺元是 （1）a ；是否有幂等性 （2）F 。4、设A=1，2，3，则A上既不是对称的又不是反对称的关系R=

6、, ；A上既是对称的又是反对称的关系R= , 。5、n个结点的无向完全图Kn的边数为 （1）n(n1)/2 ，欧拉图的充要条件是图中无奇度结点且连通 。四、演算题（本大题共5小题，每题7分，共35分 ）1、设A=1，2，A上所有函数的集合记为AA, 是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元。解：AA=ff:AA，f1x：1，1，2，1；f2x：1，2，2，2 f3x：1，1，2，2；f4x：1，2，2，1 f1f2f3f4f1 f1f1f1f1f2f2f2f2f2f3f1f2f3f4f4f2f1f4f3幺元为f3，f3、f4有逆元2、设是布尔代数上的一

7、个布尔表达式，试写出其主析取范式和主合取范式。解：函数表为：00000011010101111001101111011110主析取范式：主合取范式：3、如右图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。解： 用克鲁斯克尔（Kruskal）算法求产生的最优树。算法为： 结果如图：树权C(T)=23+1+4+9+3+17=57（万元）即为总造价。4、已知有如右图的偏序关系，求出其子集A=b,c,d,e的极大元、极小元、最大元、最小元、最小上界和最大下界。解：极大元：e 极小元：b,d 最大元：e 最小

8、元：无 最小上界：e 最大下界：a5、设，A上的关系 ，求出 。解： ， ，五、证明题（本大题共3小题，每题10分，共30分 ）1、证明：(P(QS)( RP)QRS证：（1）R 附加前提（2）RP P（3）P T(1)(2)，I（4）P(QS) P（5）QS T(3)(4)，I（6）Q P（7）S T(5)(6)，I（8）RS CP2、如果集合A上的关系R和S是自反的、对称的和传递的， 证明：是A上的等价关系。证明：（1） 自反。 （2），若，则由R ，S对称，所以，所以 对称。 （3），若则由R ，S传递性知，从而 所以，传递。 综上所述，是A上的等价关系。3、若无向图G中只有两个奇数度结

9、点，则这两个结点一定连通。证：由题设，在无向图G中只有两个奇数度结点，因此，在这两个奇数度结点之间作一条边，则在该图中所有的结点的度数都是偶数，由欧拉图的充要条件，在图中必然存在一条欧拉回路，将此边从欧拉回路中删除，在这两个奇数度结点间还存在一条欧拉道路，所以，这两个结点一定连通。离散数学模拟试题一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1、设，则 有（ D ）个元素。 A. 3； B 6； C 7； D 8 。2、设，定义上的等价关系则由R产生的上一个划分共有（ B ）个分块

10、。A4； B5； C6； D9 。 解释：SS=1，1，1，2，1，3，2，1，2，2，2，3，3，1，3，2，3，31，1=1，1，2，2，3，31，2=1，2，2，3，1，3=1，3，3，1=3，13，2=3，23、设，S上关系R的关系图如右图所示，则R具有（ D ）性质。 A自反性、对称性、传递性； B反自反性、反对称性； C反自反性、反对称性、传递性； D自反性 。4、设 为普通加法和乘法，则（ A ）是域。 A B C D= N 。5、下面偏序集（ B ）能构成格。 6、在如图所示的有向图中，从V1到V4长度为3 的道路有（ B ）条。 A1； B2； C3； D4 。7、在如下各图

11、中（ B ）是欧拉图。 8、“人总是要死的”谓词公式表示为（ C ）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。 A. ； B. C.； D.9、公式的解释I为：个体域D=2，P(x)：x3, Q(x)：x=4则A的真值为（ A ）。 A. 1； B. 0； C. 可满足式； D. 无法判定。10、下列等价关系正确的是（ B ）。 A.； B.； C.； D. 。11、下列推理步骤错在（ B ）。PUSPESTIEGA. ； B. ； C. ； D. 12、下列命题公式为重言式的是（ A ）。Ap (pq) B(pp)q Cqq Dpq 13、下列语句中是真命题的是

12、（C）。 A我正在说谎 B严禁吸烟 C如果1+2=5，那么雪是黑的 D 如果1+2=3，那么雪是黑的14、设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ D）。 Apq Bpq Cpq Dpq 15、设A=1，2，3，A上二元关系S=，则S是（ D ） 。A自反关系； B反自反关系； C对称关系； D传递关系；二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。1、下面在集合论和逻辑学中正确的公式有( 1)2）4） )。1) PPRQ； 2)

13、 RQPP； 3) ； 4) AB=ACB=C；2、设有如下命题A)如果地上有水，则天上下雨 B)如果天上下雨，则地上有水C)如果地上没有水，则天上不下雨D)如果天上不下雨，则地上没有水哪些命题等价的（ 2）4） ）。1）. A)与B)等价 ； 2）. A)与D)等价； 3). A)与C)等价 ；4）. B)与C)等价3、G=0,1,2,n，nN，定义为模n加法，即xy=(x+y) mod n，则代数系统(G，)( 1)2） )。1). 是循环群 2). 是交换群 3). 是半群但不是群 4). 是无限群4、设G是一个35阶群，aG，则a的周期不可能是（ 1）2）3）4） ）。 1).12).

14、23).34).45).5 5、下列哈斯图中，是格的有（ 3）4） ）。1).2).3).4). 5). 三、填空题（本大题共5小题，每题2分，共10分）1设，请在下列每对集合中填入适当的符号： , (2) 。2设，N为自然数集，若，则是双 射的；若，则是 （2） 满 射的。3设图G = 中有7个结点，各结点的次数分别为2，4，4，6，5，5， 2，则G中有（1） 14 条边，根据 （2） ViVdegv i=2E 。4两个重言式的析取是 （1）重言式，一个重言式和一个矛盾式的合是 （2）矛盾式 。5设个体域为自然数集，命题“不存在最大自然数”符号化为 xyyx 。四、演算题（本大题共5小题，

15、每题7分，共35分 ）1、设集合Aa，b，c，A上的关系R1，R2， 。计算R1R2，R1R2，R1-1，rR1，sR1，tR1解：2、有向图G如右图所示，试求：(1)求G的邻接矩阵A。(2)求出可达矩阵P。(3)所有强分图。解 (1)求G的邻接矩阵为： (2) 可达矩阵为。(3)因为，所以，构成G的强分图。3、右图给出的赋权图表示五个城市及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。解：此问题的最优设计方案即要求该图的最小生成树，由破圈法或避圈法得最小生成树为：其权数为1+1+3+4 = 9 。4、已知有如图的偏序关系，并求出其子集A=b,c,d,e的极大元

16、、极小元、最大元、最小元、最小上界和最大下界。解：极大元：e 极小元：b,d 最大元：e 最小元：无 最小上界：e 最大下界：a5、已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？解：因为G对于是封闭的，同时满足结合律，1是幺元，3和5，2和4，6和6互为逆元，所以构成群。是循环群，生成元是（3）。30=1，31=3，32=2，33=6，34=4，35=5五、证明题（本大题共3小题，每题10分，共30分 ）1、x(P(x)Q(x)，xP(x)$x Q(x)证明：(1)xP(x) P(2)P(c) T(1)，US(3)x(P(x)Q(x) P(4)P(c)Q(c) T(3)

17、，US(5)Q(c) T(2)(4)，I(6)$x Q(x) T(5)，EG2、p=A1，A2，An是集合A的一个划分，定义R=|a、bAi，i=1，2，n，则R是A上的等价关系。证明见教材3、设是一个代数系统，*是R上的二元运算，即对 a，bR，a*b=a+b+ab， +，是普通加法和乘法运算，则0是幺元且是含幺半群。证明：幺 ，即 闭 ，由于+，在R封闭。所以 即*在R上封闭。结 因此 ， R，*是含幺半群。离散数学模拟试题一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1 下列命

18、题公式是永真式的是（ B ）。A（PP）Q B（PQ）Q）Q C（PQ）Q D（PP）（PP）2 命题公式A不存在主合取范式，则A是 （C ）A矛盾式 B可满足式 C 永真式 D都不对3 谓词公式（x）P（X）（$x）P（X） 是（D ）A可满足式 B矛盾式 C无法判别 D永真式4 公式（x）（$y）（P（x,y）Q（z）R（x） 中的x （C ）A仅是约束变元 B仅是自由变元C既是约束变元又是自由变元 D既不是约束变元也不是自由变元5 设A、B、C是集合，下列四个命题中，( D )在任何情况下都是正确的。A.若AB且BC，则AC B. 若AB且BC，则ACC.若AB且BC，则AC D.若AB

19、且BC，则AC6 下面的表达哪个不正确 （ A ）Aaa BaaCaa，aDaa，a7 若集合A中共有n个元素，那么A上不同二元关系的个数为 （ B ）An2 B2n2 C2n2-1 D都不对8 下列判断正确的是 （ C ）A若R，S是自反的，则R-S是自反的B若R，S是对称的，则RS是对称的C若R，S是传递的，则R S是传递的D若R，S是传递的，则R S是传递的9 设R，S是非空集合上的等价关系，则RS是（ C ）A一定具有自反性，但不一定保持对称性 B一定具有对称性，但不一定保持自反性C一定具有自反性和对称性D是等价关系10 在5个元素的集合上可以定义的单射数目为 （ D ）A5 B10

20、C60 D12011 设函数f：XY；X，Y 是有限集合， f是单射，那么下列关系一定不成立的是 （ B ）A|X|=|Y| B|X|Y| C|X|Y| DXY12 平面非连通图G，n-m+f 的值为 （ C ）A2 B（G） C（G）+1 D313 若一棵树G（n，n-1） 只有两个叶节点，则 （ B ）不正确A不包含点度大于等于3的枝点 B节点总度数大于等于4C最少包含2个节点 D节点总度数=2+2（n-2）14 设10阶简单连通图有32条边，则最少要去掉 （ D ）条边才能使其成为平面图A10 B12 C32 D815.下列代数系统中，哪个是群？（ D ）A. ，*是模7加法 B. （有

21、理数集合），*是一般乘法C. （整数集合），*是一般减法 D. ，*是模11乘法二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。3121. 设A1,2,3，则右图所示A上的关系具有（BDE）。1).自反性 2).反自反性 3).对称性4).反对称性 5).传递性2. 设Aa，Ba，a，则（ABD）。1).AB2).AB3).AB4).AB5).AB 3. 下列命题公式中，（CD）在解释P，Q，R 下为真。1).(PQ)R 2).(PQ)R 3).(RQ)P4).P(QR)

22、5). (PQ)R 4. 树是（CDE）。1).欧拉图2).哈密顿图 3). 二部图 4). 平面图5). 连通图5. 在一个环（R，+，.）中，以下命题不一定成立的有（DE）。1) a.0=02) a.(-b)=-(a.b)3) -a.(-b)=a.b4) a.b=0，则a=0或b=0 5) a.b=a.c，则b=c三、填空题（本大题共5小题，每题2分，共10分）1设，请在下列每对集合中填入适当的符号：（1） , (2) 。2设，N为自然数集，若，则是(1) 双 射的，若，则是(2) 满 射的。3设图G = 中有7个结点，各结点的度数分别为2，4，4，6，5，5，2，则G中有 （1） 14

23、条边，根据 （2） 握手定理 。4两个重言式的析取是（1） 重言式 ，一个重言式和一个矛盾式的合取是 （2）矛盾式 。5设个体域为自然数集，命题“不存在最大自然数”符号化为 （1）x$y(yx) 。四、演算题（本大题共5小题，每题7分，共35分 ）1写出（PR）（SP）的主析取范式。 解：（PR）（SP）= （PRS）（PRS）（PRS）2把下面的命题符号化成逻辑公式：每个旅客要么坐硬座要么坐软座，每个旅客当且仅当富裕时坐软座，并非每个旅客都富裕。因此，有些旅客坐硬座。解： 设 P（x）：x为旅客；Q（x）：坐硬座；R（x）：坐软座；S（x）：旅客富有（x）（P（x）（Q（x）R（x）（x）（

24、P（x）（S（x）Q（x）（$x）（P（x）S（x）=（$x）（P（x）R（x）V1V2V3V43利用矩阵方法求如图所示的所有强分图：(写出运算过程)。解：三个强分图顶点集合为：V1 V4 V2，V34将置换123 4 5 651 6 3 2 4 表示成循环之积，并求其逆置换。解：=（1 5 2）（3 6 4）-1 =（1）-1 =（1 2 5）（3 4 6）5无向图G有21条边，12个3度顶点，其余顶点的度数均为2，求G的阶数n（写出求解过程）。解： 2m = d（v）2x21 = 12x3 + （n-12）x 2n = 15五、证明题（本大题共3小题，每题10分，共30分 ）1证明a+b2

25、| a，bI，+，为环（+，为普通加法和乘法）。证明：（1）为交换群a）封闭性b）0为幺元c）a+b2 与 a-b2互为逆元d）+ 可交换（2）为半群（3）分配律成立2证明：简单连通无向图G的任何一条边都是G的某一棵生成树的边。证明：反证法，假设$e G（n，m），不是任何一棵生成树的边，那么，任选一棵生成数T（n，n-1），增加边e，可以在T+e中形成一个圈，然后，删掉T+e中圈的任一条非e的边，使的删边子图成为一棵树，并且，包含e。与假设矛盾。原命题结论成立。3证明P（QS）是P（QR），R（QS）的逻辑结果。离散数学模拟试题一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列

26、出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1、结点数为奇数且所有结点的度数也为奇数的连通图必定是（ D ）。 A欧拉图 B汉密尔顿图 C非平面图 D不存在的 2、平面图(如下)的三个面的次数分别是（ A ）。 A11，3，4 B11，3，5 C12，3，6 D10，4，3 。3、下列式子中( D )是永真的。 A.(PQ)(PQ)； B.(PQ)(PQ)； C.(PQ)(PQ)； D.(PQ)(PQ)4、设R是A上的二元关系，且RR=R，则可以肯定R应是( B )。 A.自反关系； B.传递关系； C.反对称关系； D.等价关系5、永真命题公

27、式( A )。 A.只存在主析取范式； B.只存在主合取范式； C.既存在主析取范式也存在主合取范式； D.都不对6、设集合A=1，2，3，4，下列A上的关系构成A到A的映射的是（ D ）。 A. f1=(2,1),(2,4),(3,4),(4,1) B. f2=(4,4),(3,1),(1,2),(4,2) C. f3=(1,1),(2,1),(1,2),(3,4) D. f4=(1,4),(2,1),(3,4),(4,1) 7、设R是A上的二元关系,，且RRUR=R，则( C )。 A. r(R)=R； B.S( R )=R； C . t( R )=R； D . R=IA 。8、下面关于集

28、合基数正确的说法是( D )。 A.一个集合不可能和它的真子集等势； B.实数集合的基数最大； C.没有最小的基数； D.素数集合与有理数集合等势9、在自然数集上，下列哪种运算是可结合的？（ B ） A. B. C. D. 10、 下列代数系统中，哪个是群？（ D ）A. ，*是模7加法 B. （有理数集合），*是一般乘法C. （整数集合），*是一般减法 D. ，*是模11乘法11、 下面哪个集合关于指定的运算构成环？（ C ）A. ，关于数的加法和乘法； B.阶实数矩阵，关于矩阵的加法和乘法；C. ，关于数的加法和乘法； D. ，关于矩阵的加法和乘法；12、 在代数系统中，整环和域的关系为（

29、 A ）。A. 域一定是整环 B.域不一定是整环 C. 整环一定是域 D. 域一定不是整环13、 是自然数集，是小于等于关系，则是（ C ）。A. 有界格 ； B.有补格； C. 分配格； D. 有补分配格abcdefg14、右图给出的哈斯图表示的格中哪个元素无补元？（ B ） A. ； B. ； C. ； D. 15、 给定下列序列，可构成无向简单图的结点度数序列的是（ D ）。A.（1，1，2，2，3） B.（1，3，4，4，5）C.（0，1，3，3，3） D.（1，1，2，2，2）二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的

30、，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。1.设A1,2,3，则右图所示A上的关系具有（BDE）。3121).自反性 2).反自反性 3).对称性4).反对称性 5).传递性2.设Aa，Ba，a，则（ABD）。1).AB2).AB3).AB4).AB5).AB 3.下列命题公式中，（ACD）在解释P，Q，R 下为真。1).(PQ)R 2).(PQ)R 3).(RQ)P 4).P(QR) 5). (PQ)R 4.树是（CDE）。1).欧拉图2).哈密顿图 3). 二部图 4). 平面图5). 连通图5.在一个环（R，+，.）中，以下命题不一定成立的有（DE）。1) a.0=02) a.(-b)=-(a.b)3) -a.(-b)=a.b4) a.b=0，则a=0或b=0 5) a.b=a.c，则b=c三、填空