1、离散数学自考题真题 2016年 04月及答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：15.00)1.下列命题公式为永假式的是_（分数：1.00）A.(PQ)B.(PQ)QC.(PQ)QD.P(PQ)2.偏序关系一定不是_（分数：1.00）A.自反的B.传递的C.反自反的D.反对称的3.下列语句为复合命题的是_（分数：1.00）A.今天天气凉爽B.今天天气炎热，有雷阵雨C.x+y16D.今天天气多好呀，外面景色多美呀4.设 R(x)：x 是实数，L (x，y)：xy，语句“没有最大的实数”可符号化为_ A B C D （分数：1.00）A.B.C.
2、D.5.下列集合关于数的加法和乘法运算不能构成环的是_（分数：1.00）A.自然数集合B.整数集合C.有理数集合D.实数集合6.5个结点的非同构的无向树的数目是_（分数：1.00）A.5B.4C.3D.27.设 A=1，2，3，4，5，6， （分数：1.00）A.1B.3C.4D.68.一棵树有 2个 3度结点，其余结点都是叶子，则叶子数是_（分数：1.00）A.7B.6C.5D.49.设 p：他怕困难，q：他获得成功。命题“他只有不怕困难，才能获得成功”可符号化为_（分数：1.00）A.pqB.qpC.pqD.qp10.谓词公式 （分数：1.00）A.约束变元B.既是自由变元，也是约束变元C
3、.自由变元D.既不是自由变元，也不是约束变元11.下列图对应的格是有补格的是_ A B C D （分数：1.00）A.B.C.D.12.在整数集 Z上，下列运算满足结合律的是_（分数：1.00）A.a*b=|a-b|B.a*b=ab+1C.a*b=2a+bD.a*b=a+b+113.设论域为整数集，下列公式中真值为假的是_ A B C D （分数：1.00）A.B.C.D.14.设 S=1，1，1，2，则既是 S的元素又是 S的子集的为_（分数：1.00）AB.1C.1D.1，215.设简单无向图 G有 16条边，有 3个 4度结点，有 4个 3度结点，其余结点的度数均大于 3，则 G中的结点
4、个数至多为_（分数：1.00）A.9B.10C.11D.12二、第部分 非选择题(总题数：10，分数：20.00)16.设集合 A=1，3，4以及 A上的一个二无关系 R=1，3，3，4，3，3，则自反闭包 r(R)= 1，R -1 = 2。 （分数：2.00）17.设 A=1，2，3，4，B=1，2，4，5，A 到 B的关系 R=2，4，1，1，4，2，B 到 A的关系 S=4，1，1，4，2，3，则 （分数：2.00）18.设 A=3，2，4，B=2，5，3，则 A （分数：2.00）19.若连通平面图 G有 10条边，4 个面，则 G有 1 个顶点。 （分数：2.00）20.设 R=3，
5、1，2，3，5，3，3，4是集合 A=1，2，3，4，5上的关系，则 domR= 1，ranR= 2。 （分数：2.00）21.设集合 A有 3个元素，则 A上的等价关系有 1 个。 （分数：2.00）22.设 A=2，4，6，12，a*b=gcd(a，b)，即 a、b 的最大公约数。代数系统A，*的幺元是 1，零元是 2。 （分数：2.00）23.命题公式PQR 的小项编码为 1。 （分数：2.00）24.一个具有 10个顶点的简单连通无向图的边数至少为 1，至多为 2。 （分数：2.00）25.设 S(x)：x 是人，G(x)：x 会思考，则命题“人都会思考”可符号化为 1。 （分数：2.
6、00）三、计算题(总题数：5，分数：30.00)26.构造命题公式(PQ)(QR)的真值表。 （分数：6.00）_27.利用等值演算法求命题公式(P(QR)Q 的主合取范式。 （分数：6.00）_设 （分数：6.00）(1).画出 R的哈斯图；（分数：3.00）_(2).设 B=b，a，b，b，c，求 B的极大元、极小元、上界和下界。（分数：3.00）_设图 G如下图所示。 （分数：6.00）(1).写出图 G的邻接矩阵；（分数：2.00）_(2).G中长为 4的通路有几条?（分数：2.00）_(3).其中有几条回路?（分数：2.00）_28.设解释 I如下：D=2，3，已知 f(2)=3，f
7、(3)=2，F(2)=0，F(3)=1，G(2，2)=G(2，3) =0，G(3，2)=G(3，3)=1。 求谓词公式 （分数：6.00）_四、证明题(总题数：3，分数：21.00)29.设 G是无向简单图，有 2n个结点且每个结点度数均为 n。证明：G 是连通图。 （分数：7.00）_30.设S，是独异点，e 是单位元，且 S中任意 x，有 xx=e。证明：S，是交换群。 （分数：7.00）_31.设 A，B，C 是集合。证明：A(BC)=(AB)(AC)。 （分数：7.00）_五、综合应用题(总题数：2，分数：14.00)32.符号化下列命题，并构造推理证明。 中华牙防组委员会成员都是教授
8、，并且是牙医；有些中华牙防组委员会成员是资深专家。所以，有的中华牙防组委员会成员是牙医，且是资深专家。 （分数：7.00）_33.用 Kruskal算法求下图中的一棵最小生成树。要求写出详细过程，并画出该最小生成树。 （分数：7.00）_离散数学自考题真题 2016年 04月答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：15.00)1.下列命题公式为永假式的是_（分数：1.00）A.(PQ)B.(PQ)Q C.(PQ)QD.P(PQ)解析：解析 当且仅当 P的真值为 T，Q 的真值为 F时，PQ 为 F，其余情况 PQ 为 T。则选项 A的真值可为
9、 T也可为 F。同理选项 C、选项 D可为 F亦可为 T，只有选项 B在任何情况下均为 F。2.偏序关系一定不是_（分数：1.00）A.自反的B.传递的C.反自反的 D.反对称的解析：3.下列语句为复合命题的是_（分数：1.00）A.今天天气凉爽B.今天天气炎热，有雷阵雨 C.x+y16D.今天天气多好呀，外面景色多美呀解析：解析 判断命题有两个条件：(1)语句本身是陈述句；(2)它有唯一的真值。因此 C、D 不是命题更不是复合命题；A 是简单命题；只有 B是复合命题。4.设 R(x)：x 是实数，L (x，y)：xy，语句“没有最大的实数”可符号化为_ A B C D （分数：1.00）A.
10、 B.C.D.解析：5.下列集合关于数的加法和乘法运算不能构成环的是_（分数：1.00）A.自然数集合 B.整数集合C.有理数集合D.实数集合解析：6.5个结点的非同构的无向树的数目是_（分数：1.00）A.5B.4C.3 D.2解析：解析 5 个结点的非同构无向树有 3个，具体如下： 7.设 A=1，2，3，4，5，6， （分数：1.00）A.1 B.3C.4D.6解析：解析 A=1，2，3，4，5，6，则其哈斯图为8.一棵树有 2个 3度结点，其余结点都是叶子，则叶子数是_（分数：1.00）A.7B.6C.5D.4 解析：解析 设树的结点个数为 n，则 23+(n-2)1=2(n-1)，解
11、得 n=6，n-2=4，则此树有 4个叶结点。9.设 p：他怕困难，q：他获得成功。命题“他只有不怕困难，才能获得成功”可符号化为_（分数：1.00）A.pqB.qpC.pqD.qp 解析：10.谓词公式 （分数：1.00）A.约束变元B.既是自由变元，也是约束变元 C.自由变元D.既不是自由变元，也不是约束变元解析：11.下列图对应的格是有补格的是_ A B C D （分数：1.00）A. B.C.D.解析：12.在整数集 Z上，下列运算满足结合律的是_（分数：1.00）A.a*b=|a-b|B.a*b=ab+1C.a*b=2a+bD.a*b=a+b+1 解析：解析 选项 A，a*(b*c)
12、=a*|b-c|=|a-|b-c|，(a*b)*c=|a-b|*c=|a-b|-c|，即 a*(b*c)(a*b)*c；选项 B，a*(b*c)=a*(bc+1)=a(bc+1)+1=abc+a+1，(a*b)*c=(ab+1)*c=(ab+1)c+1=abc+c+1，即 a*(b*c)(a*b)*c；选项 C，a*(b*c)=a*(2b+c)=2a+2b+c；(a*b)*c=(2a+b)*c=4a+2b+c，即 a*(b*c)(a*b)*c；选项 D，a*(b*c)=a*(b+c+1)=a+b+c+2，(a*b)*c=(a+b+1)*c=a+b+c+2，即 a*(b*c)=(a*b)*c，故
13、满足结合律。13.设论域为整数集，下列公式中真值为假的是_ A B C D （分数：1.00）A.B. C.D.解析：14.设 S=1，1，1，2，则既是 S的元素又是 S的子集的为_（分数：1.00）AB.1C.1 D.1，2解析：15.设简单无向图 G有 16条边，有 3个 4度结点，有 4个 3度结点，其余结点的度数均大于 3，则 G中的结点个数至多为_（分数：1.00）A.9 B.10C.11D.12解析：解析 设图 G至多有 n个结点，则 34+43+(n-7)4216，解得 n9。二、第部分 非选择题(总题数：10，分数：20.00)16.设集合 A=1，3，4以及 A上的一个二无
14、关系 R=1，3，3，4，3，3，则自反闭包 r(R)= 1，R -1 = 2。 （分数：2.00）解析：1，1，1，3，3，4，3，3，4，4；3，1，4，3，3，317.设 A=1，2，3，4，B=1，2，4，5，A 到 B的关系 R=2，4，1，1，4，2，B 到 A的关系 S=4，1，1，4，2，3，则 （分数：2.00）解析：4，1，1，2解析 R=2，4，1，1，4，2，S=4，1，1，4，2，3，则18.设 A=3，2，4，B=2，5，3，则 A （分数：2.00）解析：4，5；419.若连通平面图 G有 10条边，4 个面，则 G有 1 个顶点。 （分数：2.00）解析：820
15、.设 R=3，1，2，3，5，3，3，4是集合 A=1，2，3，4，5上的关系，则 domR= 1，ranR= 2。 （分数：2.00）解析：2，3，5；1，3，421.设集合 A有 3个元素，则 A上的等价关系有 1 个。 （分数：2.00）解析：522.设 A=2，4，6，12，a*b=gcd(a，b)，即 a、b 的最大公约数。代数系统A，*的幺元是 1，零元是 2。 （分数：2.00）解析：12；223.命题公式PQR 的小项编码为 1。 （分数：2.00）解析：m 01024.一个具有 10个顶点的简单连通无向图的边数至少为 1，至多为 2。 （分数：2.00）解析：9；45解析 连
16、通图的必要条件是至少有 n-1条边，即 10-1=9；至多有25.设 S(x)：x 是人，G(x)：x 会思考，则命题“人都会思考”可符号化为 1。 （分数：2.00）解析：三、计算题(总题数：5，分数：30.00)26.构造命题公式(PQ)(QR)的真值表。 （分数：6.00）_正确答案：()解析：P Q R PQ QR (PQ)(QR) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 27.利用等值演算法求命题公式(P(QR)Q 的主合取范式。 （
17、分数：6.00）_正确答案：()解析：设 （分数：6.00）(1).画出 R的哈斯图；（分数：3.00）_正确答案：()解析：哈斯图: (2).设 B=b，a，b，b，c，求 B的极大元、极小元、上界和下界。（分数：3.00）_正确答案：()解析：B 的极大元：a，b，b，c； 极小元：b； 上界：a，b，c； 下界： 设图 G如下图所示。 （分数：6.00）(1).写出图 G的邻接矩阵；（分数：2.00）_正确答案：()解析：G 的邻接矩阵(2).G中长为 4的通路有几条?（分数：2.00）_正确答案：()解析：(3).其中有几条回路?（分数：2.00）_正确答案：()解析：G 中长为 4的
18、回路有 7条。28.设解释 I如下：D=2，3，已知 f(2)=3，f(3)=2，F(2)=0，F(3)=1，G(2，2)=G(2，3) =0，G(3，2)=G(3，3)=1。 求谓词公式 （分数：6.00）_正确答案：()解析：四、证明题(总题数：3，分数：21.00)29.设 G是无向简单图，有 2n个结点且每个结点度数均为 n。证明：G 是连通图。 （分数：7.00）_正确答案：()解析：证明：假设 G不是连通图，设 H是 G的一个连通分支。 由于图 G是简单图且每个结点的度数为 n， 所以子图 H与 G-H也是简单图且每个结点的度数为 n。 因此，H 与 G-H中的结点数均至少为 n+
19、1。 于是 G的结点数大于等于 2n+2， 这与 G的结点数为 2n矛盾。 因此假设为谬，所以 G是连通图。30.设S，是独异点，e 是单位元，且 S中任意 x，有 xx=e。证明：S，是交换群。 （分数：7.00）_正确答案：()解析：证明：由于S，是独异点，e 是单位元，且 S中任意 x，有 xx=e。 所以S，是群，且每个元素的逆元等于它本身。 于是，对任意 x，yS，有 xy=x -1 y -1 =(yx) -1 =yx。 所以，S，是交换群。31.设 A，B，C 是集合。证明：A(BC)=(AB)(AC)。 （分数：7.00）_正确答案：()解析：证明： (1)若 xA(BC)，则
20、xA 且 xBC； 即 xA 且 xB，或者 xA 且 xC； 即 x(AB)(AC)； 所以 (2)若 x(AB)(AC)，则 xAB 或者 xAC； 即 xA 且 xB，或者 xA 且 xC； 即 xA 且 xBC； 即 xA(BC)； 所以 五、综合应用题(总题数：2，分数：14.00)32.符号化下列命题，并构造推理证明。 中华牙防组委员会成员都是教授，并且是牙医；有些中华牙防组委员会成员是资深专家。所以，有的中华牙防组委员会成员是牙医，且是资深专家。 （分数：7.00）_正确答案：()解析：(1)符号化：设个体域为全总个体域。 M(x)：x 是中华牙防组委员会成员； H(x)：x 是教授； G(x)：x 是牙医； R(x)：x 是资深专家。 (2) (3)证明： 33.用 Kruskal算法求下图中的一棵最小生成树。要求写出详细过程，并画出该最小生成树。 （分数：7.00）_正确答案：()解析：解：根据 Kruskal算法， 取权为 1的边 e 1 =(v 1 ，v 2 )；取权为 3的边 e 2 =(v 2 ，v 3 )； 取权为 4的边 e 3 =(v 3 ，v 4 )；取权为 4的边 e 4 =(v 3 ，v 5 )； 取权为 7的边 e 5 =(v 5 ，v 6 )； 最小生成树如下图所示。
