离散数学课试卷B

1、课程名称：课程名称： 离散数学离散数学 ( B 卷卷 闭卷闭卷) 适用专业年级：通信工程专业适用专业年级：通信工程专业 05 级级 考试时间考试时间:100 分钟分钟 题号题号一一二二三三四四五五六六总分总分 题分题分15122038510100 统分人统分人 签签名名 得分得分 考生注意事项：1、本试卷共 2 页，试卷如有缺页或破损，请立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。(答案请写在密封 线内和纸卷正面，否则不记分) 一、填空题(每空 1.5 分，共 15 分) 1、 （ ）是用数学方法研究逻辑学中（ ）的一种分支学科。 2、设 A 为一个命题公式

2、，若 A 在它的各种赋值下取值均为假，则称 A 为（ ） 。 3、表示抽象的性质、关系的谓词或泛指的谓词称为（ ） 。 4、设集合 A=3,5,7,4，集合 B=7,3,9,2，则 AB 的结果为（ ） 。 5、 设关系 F=,，关系 G=,，则 GF 的结果为 （ ） 。 6、设 A=a,b,c，A 上的关系 R=,，则 R 的自反闭包 r(R)=（ ）, R 的对称闭包 s(R)=（ ） 。 7、设无向完全图 G=有 10 个顶点，则图 G 共有（ ）条边。 8、在有向图 G 中，设所有顶点的入度和为 m，出度和为 n，则 m 与 n 应该是（ ）的。 二、单项选择题(每空一选 每选 2

3、分 共 12 分) 1、在下面四项陈述中，可称为命题的是（ ） 。 A天气多好啊！ B x=4。 C南昌起义那天下雪了。 D我只给不给自己理发的人理发。 2、若 P：他聪明；Q：他用功；则“他虽然聪明，但不用功。 ”可符号化为（ ） 。 APQ B PQ CPQ D PQ 3、已知谓词公式为x F(x)xG(x),则以下哪一项不是该谓词公式的前束范式（ ） 。 Ax(F(x)G(x)Bxy( G(y) F(x) Cxy(F(x)G(y)Dyx (F(x)G(y) 4、以下命题为假的是（ ） 。 A 空集包含空集 B 空集被任一集合包含 C 空集是唯一的 D 空集属于任一集合 5、设, ，R 为

4、 S 上的关系；其关系矩阵是如下图所示，则 RR 中有（ ）个有序对。 A 7 B 6 C8 D 5 6、在一个有向简单图中，已知该图有 8 个顶点，则该图不可能具有的边数为（ ） 。 A1 B55 C34 D57 三、判断题：(正确的打，错误的打，每题一分，共 20 分) ( )1、 “外太空存在生物。 ”是假命题。 ( )2、在命题变元确定的情况下，按照命题公式的定义可以形成无限的不同的命题公式。 ( )3、在谓词公式中，可以用公式中未出现的变项符号代替某自由出现的个体变项，但必须处处代替。 ( )4、命题公式中的重言式的代换实例在谓词公式中不一定是重言式。 ( )5、在使用量词辖域收缩与

5、扩张等值式时，公式 A（x）中可以有 x 的约束出现。 ( )6、集合 A=1,2,5,2,1，集合 B=5,2,1，则集合 A 与 B 是相等的。 ( )7、在一个R2 的二元关系 R 中，有序对之间的顺序是不可交换的。 ( )8、设 FA为集合 A 在二元关系 F 下的像，则 FA一定不是二元关系。 ( )9、在一个二元关系 R 中不可能同时具备自反性与反自反性。 ( )10、设 R 与 S 为集合 A 上的对称关系，则 RS 也是集合 A 上的对称关系。 ( )11、在集合 A 中任取两个元素 x 和 y，则等价类x与y的交集可以是x的真子集。 ( )12、所有的二元关系都可以称为函数。

6、 ( )13、设集合 A=1,2,3,4，则 A 上的关系 R=具有对称性与传递性。 ( )14、设*为 S 上的二元运算，如果 S 上关于运算*存在左幺元 el与右幺元 er，则 el=er。 ( )15、逆元是针对二元运算而言的。 ( )16、在一个有向图 G=中，如果所有顶点度的和为 180，则该图共有 90 条有向边。 ( )17、对于一个命题公式 A，其析取范式可有多种表达形式，但其主析取范式是唯一的。 ( )18、在一阶逻辑中存在量词分配等值式：x（A(x)B(X)）(xA(x)xB(x)。 ( )19、等价类是一个集合。 ( )20、在有向图中，如果某顶点的入度是 3，出度是 4

7、，则该顶点的度是 1。 湖南工业大学考试试卷纸 系(院) 课程名称 班级 姓名 学号 密封线 第 1 页 共 2 页 湖南工业大学考试试卷纸 系(院) 课程名称 班级 姓名 学号 湖南工业大学考试答卷纸 系(院) 课程名称 班级 姓名 学号 密封线 四、综合题：(共 38 分) 1、用等值演算法证明等值式（pq）（pr） ）（p（qr） ） 。 （5 分） 2、求命题公式（p（qr） ）(pqr)的主析取范式。 （8 分） 3、在一阶逻辑中将命题“任何金属都可以溶解在某种液体中。 ”符号化。 （3 分） 4、已知集合 A=a,b,c,d,e,B=f,e,g,c,d。试求：AB、AB、A-B、AB。 （8 分） 5、已知集合 A=a，b，c，d。R，S 为集合 A 上的关系。R=, S=,。试求：RS、SR、R2、S3。 （6 分） 6、已知集合 A=a,b,c,d,e,A 上的关系 R=,。试求: （1）画出 R 的关系矩阵。 （2）R 的自反闭包。 （3）R 的对称闭包。 （4）R 的传递闭包。 （8 分） 五、推理题：（共 5 分） 1、构造下面推理