1、离散数学自考题真题 2015 年 10 月及答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：15.00)1.设简单无向图 G 有 15 条边，有 3 个 4 度结点，其余结点的度数均为 3，则 G 中的结点个数是_（分数：1.00）A.6B.7C.8D.92.是一个偏序集，其中 A 是正整数 12 的正因子的集合， 为整除关系，元素 6 能盖住元素_（分数：1.00）A.1B.3C.6D.123.下列公式不是合式公式的为_ APQ R BP(QR) CP(PQ) D （分数：1.00）A.B.C.D.4.设 a：小华，P(x)：x 是教授，f(x)：
2、x 的父亲，则语句“小华的父亲是教授”可符号化为_（分数：1.00）A.P(f(a)B.P(a)f(a)C.f(P(a)D.P(a)f(a)5.设 p：天下雨，q：我开车上班。命题“除非不下雨，否则我开车上班”可符号化为_（分数：1.00）A.pqB.qpC.pqD.qp6.设 ， 是集合 A 上的相容关系，则下列关系不一定是相容关系的是_ A B C （分数：1.00）A.B.C.D.7.下列公式中与公式 等价的是_ A B C D （分数：1.00）A.B.C.D.8.设有一个连通平面图 G，共有 7 个结点，12 条边，则 G 的面的个数为_（分数：1.00）A.6B.7C.8D.99.
3、设 R 1 、R 2 都是从 A 到 B 的二元关系，则下列各式成立的为_ A.(R1R 2)-1=R1-1R 2-1 B.(R1R 2)-1=R1-1R 2-1 C.(R1R 2)-1=R1R 2 D.(R1R 2)-1=R1R 2（分数：1.00）A.B.C.D.10.下列语句是假命题的是_ A只有 2 是奇数， 才是无理数 B只要 2 是奇数， 就是无理数 C如果 2 是奇数，那么 就是无理数 D除非 （分数：1.00）A.B.C.D.11.设G，*为群， （分数：1.00）A.B.C.D.12.下列无向图不一定为树的是_（分数：1.00）A.无回路的连通图B.有 n 个结点，n-1 条
4、边的连通图C.每对结点间都有路的图D.连通但删去一条边便不连通的图13.下图中 d 的补元是_ （分数：1.00）A.0B.1C.6Dc14.在自然数集 N 上，下列运算满足结合律的是_ A.a*b=a B.a*b=|a-b| C.a*b=ba D.a*b=2a+b（分数：1.00）A.B.C.D.15.设论域为整数集，下列公式中真值为真的是_ A B C D （分数：1.00）A.B.C.D.二、第部分 非选择题(总题数：10，分数：20.00)16.公式 （分数：2.00）17.设 A=2，3，4，5，a*b=max(a，b)。代数系统A，*的幺元是 1，零元是 2。 （分数：2.00）1
5、8.设无向树 T 有 3 个度数为 3 的结点，其余结点都为树叶，则 T 的结点数为 1。 （分数：2.00）19.命题公式PQR 的二进制编码大项 M i 为 1。 （分数：2.00）20.设 A=4，2，1，B=5，1，3，则 B-A= 1，B （分数：2.00）21.设 F(x)：x 有进取心，要求只能使用全称量词，命题“某些人有进取心”可符号化为 1。 （分数：2.00）22.设 A=a，b，c，d，B=1，2，3，4，A 到 B 的关系 R=a，4，b，1，b，2，B 到 A 的关系 S=4，a，3，b，2，c，则 （分数：2.00）23.命题公式 P(QR)的成真指派有 1 个，成
6、假指派有 2 个。 （分数：2.00）24.设 R=a，2，b，4，b，3，d，2是集合 A=a，b，c，d到集合 B=1，2，3，4的关系，则 ranR= 1，domR= 2。 （分数：2.00）25.设 S=，1，(1，2)，则其幂集 （分数：2.00）三、计算题(总题数：5，分数：30.00)26.构造命题公式(PQ)(QR)的真值表。 （分数：6.00）_27.利用等值演算法求命题公式(PQ)(RQ)的主析取范式。 （分数：6.00）_设 为偏序集，其哈斯图如下图所示。 （分数：6.00）(1).写出偏序关系 （分数：3.00）_(2).设 B=b，d，e，求 B 的极大元、极小元、上
7、界和下界。（分数：3.00）_S=1，2，3，4，5是集合 A=1，2，3，4，5上的一个划分。（分数：6.00）(1).写出由 S 导出的 A 上的等价关系 的有序对集合；（分数：3.00）_(2).写出 的关系矩阵。（分数：3.00）_28.设解释 I 如下：D=2，3，已知 F(2，2)=F(3，3)=0，F(2，3)=F(3，2)=1，f(2，2)=f(2，3)=2，f(3，2)=f(3，3)=3。 求谓词公式 （分数：6.00）_四、证明题(总题数：3，分数：21.00)29.设 A，B，C 是集合。证明：(A-B)-C=A-(BC)。 （分数：7.00）_30.设无向简单图 G 有
8、 9 个结点。证明：G 中至少存在两个度数相同的结点。 （分数：7.00）_31.设G，是群， （分数：7.00）_五、综合应用题(总题数：2，分数：14.00)32.符号化下列命题，并构造推理证明。 每个学生都是勤奋的；每个勤奋而又聪明的人在他的工作生活中都将获得成功；小华是学生，并且是聪明的。所以，小华在他的工作生活中将获得成功。 （分数：7.00）_33.今有 a，b，c，d，e，f，g 共 7 人，已知下列事实： a 会讲法语；b 会讲法语、意大利语和日语；c 会讲法语、汉语；d 会讲日语和意大利语；e 会讲德语、汉语和法语；f 会讲英语、日语和俄语；g 会讲英语和德语。试问：这 7
9、个人应如何围圆桌排座位，才能使每个人和他两边的人可以交谈?(须写出所有可能方案) （分数：7.00）_离散数学自考题真题 2015 年 10 月答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：15.00)1.设简单无向图 G 有 15 条边，有 3 个 4 度结点，其余结点的度数均为 3，则 G 中的结点个数是_（分数：1.00）A.6B.7C.8D.9 解析：解析 设图 G 的结点个数为 n，则 34+(n-3)3=215，解得 n=9。2.是一个偏序集，其中 A 是正整数 12 的正因子的集合， 为整除关系，元素 6 能盖住元素_（分数：1.00
10、）A.1B.3 C.6D.12解析：解析 A=1，2，3，4，6，12，则其哈斯图是3.下列公式不是合式公式的为_ APQ R BP(QR) CP(PQ) D （分数：1.00）A.B.C.D. 解析：4.设 a：小华，P(x)：x 是教授，f(x)：x 的父亲，则语句“小华的父亲是教授”可符号化为_（分数：1.00）A.P(f(a) B.P(a)f(a)C.f(P(a)D.P(a)f(a)解析：5.设 p：天下雨，q：我开车上班。命题“除非不下雨，否则我开车上班”可符号化为_（分数：1.00）A.pqB.qpC.pq D.qp解析：6.设 ， 是集合 A 上的相容关系，则下列关系不一定是相容
11、关系的是_ A B C （分数：1.00）A.B.C. D.解析：解析 举例说明，设 =1，1，1，2，2，1，2，2，=2，3，3，2，2，2，3，3，则 ， 均为相容关系，而 ，显然7.下列公式中与公式 等价的是_ A B C D （分数：1.00）A.B.C. D.解析：8.设有一个连通平面图 G，共有 7 个结点，12 条边，则 G 的面的个数为_（分数：1.00）A.6B.7 C.8D.9解析：解析 设图 G 的面的个数为 r，根据欧拉公式得 7-12+r=2，解得 r=7，即 G 的面的个数为 7。9.设 R 1 、R 2 都是从 A 到 B 的二元关系，则下列各式成立的为_ A.
12、(R1R 2)-1=R1-1R 2-1 B.(R1R 2)-1=R1-1R 2-1 C.(R1R 2)-1=R1R 2 D.(R1R 2)-1=R1R 2（分数：1.00）A.B. C.D.解析：10.下列语句是假命题的是_ A只有 2 是奇数， 才是无理数 B只要 2 是奇数， 就是无理数 C如果 2 是奇数，那么 就是无理数 D除非 （分数：1.00）A. B.C.D.解析：解析 设 P：2 是奇数，Q：11.设G，*为群， （分数：1.00）A.B.C.D. 解析：12.下列无向图不一定为树的是_（分数：1.00）A.无回路的连通图B.有 n 个结点，n-1 条边的连通图C.每对结点间都
13、有路的图 D.连通但删去一条边便不连通的图解析：13.下图中 d 的补元是_ （分数：1.00）A.0B.1C.6Dc 解析：解析 题图所示有界格的全上界为 1，全下界为 0，而 dc=1，dc=0，根据补元的定义知，c为 d 的补元。14.在自然数集 N 上，下列运算满足结合律的是_ A.a*b=a B.a*b=|a-b| C.a*b=ba D.a*b=2a+b（分数：1.00）A. B.C.D.解析：解析 选项 A，a*(b*c)=a*b=a，(a*b)*c=a*c=a，即 a*(b*c)=(a*b)*c，故满足结合律；选项B，a*(b*c)=a*|b-c|=|a-|b-c|，(a*b)*
14、c=|a-b|*c=|a-b|-c|，即 a*(b*c)(a*b)*c；选项 C，a*(b*c)=a*c b =c ab ，(a*b)*c=b a *c=c ba ，即 a*(b*c)(a*b)*c；选项 D，a*(b*c)=a*(2b+c)=2a+2b+c，(a*b)*c=(2a+b)*c=4a+2b+c，即 a*(b*c)(a*b)*c。15.设论域为整数集，下列公式中真值为真的是_ A B C D （分数：1.00）A. B.C.D.解析：二、第部分 非选择题(总题数：10，分数：20.00)16.公式 （分数：2.00）解析：x，z；y17.设 A=2，3，4，5，a*b=max(a，
15、b)。代数系统A，*的幺元是 1，零元是 2。 （分数：2.00）解析：2；518.设无向树 T 有 3 个度数为 3 的结点，其余结点都为树叶，则 T 的结点数为 1。 （分数：2.00）解析：8解析 设树 T 的树叶数为 n，则树 T 有 n+3 个结点，n+2 条边。由结点度数总和与边数的关系知n+33=2(n+2)，故 n=5，则树 T 的结点个数为 5+3=8。19.命题公式PQR 的二进制编码大项 M i 为 1。 （分数：2.00）解析：M 10120.设 A=4，2，1，B=5，1，3，则 B-A= 1，B （分数：2.00）解析：3，5；2，3，4，521.设 F(x)：x
16、有进取心，要求只能使用全称量词，命题“某些人有进取心”可符号化为 1。 （分数：2.00）解析：22.设 A=a，b，c，d，B=1，2，3，4，A 到 B 的关系 R=a，4，b，1，b，2，B 到 A 的关系 S=4，a，3，b，2，c，则 （分数：2.00）解析：a，a，b，c23.命题公式 P(QR)的成真指派有 1 个，成假指派有 2 个。 （分数：2.00）解析：5；3 解析 命题公式 P(QR)的真值表如下表所示。 P Q R R QR P(QR) 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1
17、0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 故公式 P(QR)的成真指派有 5 个，成假指派有 3 个。24.设 R=a，2，b，4，b，3，d，2是集合 A=a，b，c，d到集合 B=1，2，3，4的关系，则 ranR= 1，domR= 2。 （分数：2.00）解析：2，3，4；a，b，d25.设 S=，1，(1，2)，则其幂集 （分数：2.00）解析：8 解析 三、计算题(总题数：5，分数：30.00)26.构造命题公式(PQ)(QR)的真值表。 （分数：6.00）_正确答案：()解析：P Q R P QR PQ (PQ)(QR) 0 0 0 0 1 1 1 1 0 0 1
18、 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 27.利用等值演算法求命题公式(PQ)(RQ)的主析取范式。 （分数：6.00）_正确答案：()解析：设 为偏序集，其哈斯图如下图所示。 （分数：6.00）(1).写出偏序关系 （分数：3.00）_正确答案：()解析：偏序关系 (2).设 B=b，d，e，求 B 的极大元、极小元、上界和下界。（分数：3.00）_正确答案：()解析：B 的极大元：d，e； 极小元：b； 上界：g； 下界：b，a。S=1，2，3，4，
19、5是集合 A=1，2，3，4，5上的一个划分。（分数：6.00）(1).写出由 S 导出的 A 上的等价关系 的有序对集合；（分数：3.00）_正确答案：()解析：=(1，21，2)(33)(4，54，5) =1，1，1，2，2，1，2，2，3，3，4，4，4，5，5，4，5，5；(2).写出 的关系矩阵。（分数：3.00）_正确答案：()解析： 的关系矩阵为28.设解释 I 如下：D=2，3，已知 F(2，2)=F(3，3)=0，F(2，3)=F(3，2)=1，f(2，2)=f(2，3)=2，f(3，2)=f(3，3)=3。 求谓词公式 （分数：6.00）_正确答案：()解析：四、证明题(总
20、题数：3，分数：21.00)29.设 A，B，C 是集合。证明：(A-B)-C=A-(BC)。 （分数：7.00）_正确答案：()解析：证明： (1)若 x(A-B)-C，则 xA-B 但 ， 即 xA 但 即 xA 但 即 xA-(BC)； 所以 (2)若 xA-(BC)，则 xA 但 ； 即 xA 但 即 xA-B 但 即 x(A-B)-C； 所以 30.设无向简单图 G 有 9 个结点。证明：G 中至少存在两个度数相同的结点。 （分数：7.00）_正确答案：()解析：证明：由于 G 是有 9 个结点的无向简单图， 所以 G 的结点的度数只能为 0，1，2，3，4，5，6，7，8 这 9
21、种情况。 但是，度数为 0 和度数为 8 不能同时出现， 因此，G 的结点的度数最多有 8 种不同的值。 由于 G 有 9 个结点，所以至少有两个结点的度数相同。31.设G，是群， （分数：7.00）_正确答案：()解析：证明：G，是群，设 e 是 G 的单位元。显然 eC(G)。 对任意的 m，nC(G)，对任意的 gG， 有(mn)g=m(gn)=g(mn)， 所以 mnC(G)。 又由 mg=gm 可得 gm -1 =m -1 g， 所以 m -1 C(G)。 因此C(G)，是G，的一个子群。五、综合应用题(总题数：2，分数：14.00)32.符号化下列命题，并构造推理证明。 每个学生都
22、是勤奋的；每个勤奋而又聪明的人在他的工作生活中都将获得成功；小华是学生，并且是聪明的。所以，小华在他的工作生活中将获得成功。 （分数：7.00）_正确答案：()解析：解：设个体域为全体人类。 a：小华； M(x)：x 是学生； H(x)：x 是勤奋的； G(x)：x 是聪明的； R(x)：x 在工作生活中将获得成功。 33.今有 a，b，c，d，e，f，g 共 7 人，已知下列事实： a 会讲法语；b 会讲法语、意大利语和日语；c 会讲法语、汉语；d 会讲日语和意大利语；e 会讲德语、汉语和法语；f 会讲英语、日语和俄语；g 会讲英语和德语。试问：这 7 个人应如何围圆桌排座位，才能使每个人和他两边的人可以交谈?(须写出所有可能方案) （分数：7.00）_正确答案：()解析：设无向图 G=V，E，其中 V=a，b，c，d，e，f，g， E=(u，v)|u，vV，且 u 和 v 有共同语言； 作图如下图所示。
