离散数学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．谓词公式xPx∨yRy→Qx中量词x的辖域是（） A．xPx  yRy C．Px∨yRy B．P（x） D．Px, Qx 5．设个体域 A{a,b}，公式xPx∧xSx在 A 中消去量词后应为（） A．Px∧Sx C．Pa∧Sb 6．下列选项中错误的是（） ．． A． C．{} B．∈ D．∈{} B．Pa∧Pb∧Sa∨Sb D．Pa∧Pb∧Sa∨Sb 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 为实数集，函数 fR→R，fx2x，则 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bmax{a, b} C．ab2ab B．abb 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．公式xPx→Qx,y∨zRy, z→Sx中的自由变元为________________，约束变元 为________________。 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}，fX→X，gX→X，f{,,}, g{,,}，则 fg________________，gf________________。 20．设 A{a,b,c}，R 是 A 上的二元关系，且给定R{,,}，则 R 的自反闭包 rR ________________，对称闭包 sR ________________。 21．设 Q 为有理数集，笛卡尔集 SQQ，*是 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AA，画出偏序集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ba*x*b，a,b∈G。证明也是一个群。 33．设图 G 是具有 6 个结点，12 条边的无向简单图，证明图G 是汉密尔顿图。 五、应用题（本大题共 2 小题，第 34 小题 8 分，第 35 小题 7 分，共 15 分） 34．构造下面推理的证明。 如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们 就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。 35．n 个城市用 k 条公路的网络连结。 一条公路定义为两个城市间的一条不穿过任何中间城 1 市的道路。任意两个城市之间至多修一条公路。 证明如果 kn-1n-2，