离散数学B卷

武汉理工大学武汉理工大学《离散数学》考试试题《离散数学》考试试题 (B (B 卷卷) ) 站点：姓名：专业：层次 一、单项选择题（本大题共15 小题，每小题 1 分，共 15 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括 号内。错选、多选或未选均无分。 1． 令 P： 今天下雪了， Q： 路滑， 则命题 “虽然今天下雪了， 但是路不滑” 可符号化为 （） ． A．P→ Q C．P∧Q 2．下列命题公式为重言式的是（） A．Q→（P∧Q） C． （P∧Q）→P B．P→（P∧Q） D． （P∨Q）→Q B．P∨ Q D．P∧ Q 3．下列 4 个推理定律中，不正确的是（） ． A．A（A∧B） C． （A→B）∧AB B． （A∨B）∧ AB D． （A→B）∧ BA 4．谓词公式x(P(x)∨yR(y))→Q(x)中量词x的辖域是（） A．x(P(x)  yR(y)) C．(P(x)∨yR(y)) B．P（x） D．P(x), Q(x) 5．设个体域 A={a,b}，公式xP(x)∧xS(x)在 A 中消去量词后应为（） A．P(x)∧S(x) C．P(a)∧S(b) 6．下列选项中错误的是（） ．． A．ØØ C．Ø{Ø} B．Ø∈Ø D．Ø∈{Ø} B．P(a)∧P(b)∧(S(a)∨S(b)) D．P(a)∧P(b)∧S(a)∨S(b) 7．设 A={a,b,c,d}，A 上的等价关系 R={, , , }∪IA，则对应于 R 的 A 的划分是（） A．{{a},{b, c},{d}} C．{{a},{b},{c},{d}} B．{{a, b},{c}, {d}} D．{{a, b}, {c,d}} 8．设 R 为实数集，函数 f：R→R，f(x)=2x，则 f 是（） A．满射函数 C．双射函数 B．入射函数 D．非入射非满射 9．设R 为实数集，R+={x|x∈R∧x0}，*是数的乘法运算，是一个群，则下列集合 关于数的乘法运算构成该群的子群的是（） A．{R+中的有理数} C．{R+中的自然数} B．{R+中的无理数} D．{1，2，3} 10．下列运算中关于整数集不能构成半群的是（） ． A．ab=max{a, b} C．ab=2ab B．ab=b D．ab=|a-b| 11．设 Z 是整数集，+，分别是普通加法和乘法，则（Z，+，）是（） A．域 C．整环 B．整环和域 D．含零因子环 12． 设A={a, b, c}， R是A上的二元关系， R={, , , }， 那么R是 （） A．反自反的 C．可传递的 B．反对称的 D．不可传递的 13．设 D=为有向图，V={a, b, c, d, e, f}, E={, , , , }是 （） A．强连通图 C．弱连通图 B．单向连通图 D．不连通图 14．在有 n 个结点的连通图中，其边数（） A．最多有 n-1 条 C．最多有 n 条 B．至少有 n-1 条 D．至少有 n 条 15．连通图 G 是一棵树，当且仅当G 中（） A．有些边不是割边 C．无割边集 B．每条边都是割边 D．每条边都不是割边 二、填空题（本大题共 10 小题，每小题 2 分，共 20 分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．任意两个不同的小项的合取为________________式，全体小项的析取式必为 ________________式。 17．公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元 为________________。 18．设集合 M={x|1≤x≤12,x 被 2 整除，x∈Z},N={x|1≤x≤12,x 被 3 整除，x∈Z}，则 M∩N=________________，M∪N=________________。 19．设 X={1，2，3}，f：X→X，g：X→X，f={,,}, g={,,}，则 fg=________________，gf=________________。 20．设 A={a,b,c}，R 是 A 上的二元关系，且给定R={,,}，则 R 的自反闭包 r(R)= ________________，对称闭包 s(R)= ________________。 21．设 Q 为有理数集，笛卡尔集 S=Q×Q，*是 S 上的二元运算，,∈S, *=, 则*运算的幺元是________________。∈S, 若 a≠0， 则的逆元是________________。 22．设*是集合 S 上的二元运算，若运算*满足________________且存在________________， 则称为独异点。 23．令 A={a, b, c}，是循环群，a 是单位元，则 b2=________________，c 的阶是 ________________。 24．如下无向图割点是________________，割边是________________。 25． 无向图G具有生成树， 当且仅当________________。 G的所有生成树中________________ 的生成树称为最小生成树。 三、计算题（本大题共5 小题，第 26、27 小题各 5 分，第 28、29 小题各 6 分，第 30 小题 8 分，共 30 分） 26．集合 A={a, b, c, d, e}上的二元关系 R 为 R={, , , , , , , , ,,,, , } （1）写出 R 的关系矩阵； （2）判断 R 是不是偏序关系，为什么？ 27．利用真值表判断公式（ （ P∨Q）∧（Q→R） ）→ （P∧ R）是否为重言式。 28．给定图 G 如下所示， （1）写出 G 的可达矩阵； （2）G 中长度为 4 的路有几条？ 29．求下列公式的主析取范式和主合取范式： （P→Q）∧（Q→R） 30． 设 A 为 54 的因子构成的集合， RA×A，画出偏序集x,y∈A, xRyx 整除 y。 的哈斯图，并求 A 中的最大元，最小元，极大元，极小元。 五、证明题（本大题共 3 小题，第 31、32 小题各 6 分，第 33 小题 8 分，共 20 分） 31．设 R 是 A 上的一个自反关系，证明：R 是一个等价关系，当且仅当若∈R， ∈R，则∈R。 32．设是一个群，x∈G，定义：ab=a*x*b，a,b∈G。证明：也是一个群。 33．设图 G 是具有 6 个结点，12 条边的无向简单图，证明图G 是汉密尔顿图。 五、应用题（本大题共 2 小题，第 34 小题 8 分，第 35 小题 7 分，共 15 分） 34．构造下面推理的证明。 如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们 就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。 35．n 个城市用 k 条公路的网络连结。 一条公路定义为两个城市间的一条不穿过任何中间城 1 市的道路。任意两个城市之间至多修一条公路。 证明如果 k(n-1)(n-2)，