离散数学试卷1

来源：用户分享时间：2025/6/9 10:02:15 本文由

loading 分享下载这篇文档手机版

说明：文章内容仅供预览，部分内容可能不全，需要完整文档或者需要复制内容，请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ：xxxxxx 处理（尽可能给您提供完整文档），感谢您的支持与谅解。

离散数学期末试题(B卷)

一、单项选择题（每小题1分，共15分。四选一）

1、设Φ是一个空集，则下列之一哪一个不成立（　　）。 ①、Φ∈Φ

②、Φ?Φ

③、Φ∈{Φ}

④、Φ?{Φ}

2、如果命题公式G=P∧Q，则下列之一哪一个成立（　　）。 ①、G=?(P→Q)

②、G=?(P→?Q)

③、G=?(?P→Q)

④、G=?(?P→?Q)

3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（　　　）个二元关系。 ①、n

②、m

③、m×n ④、2

m×n

4、在有补分配格中，?a,b∈L，a≤b当切仅当下列（　　）成立。 ①、a?b＝b

②、a?b＝a

③、a＇?b＝0

④、a＇?b＝1

5、若是一个群，则运算“*”一定满足（　　）。 ①、交换律

②、消去律

③、幂等律

④、分配律

6、量词的约束范围称为量词的（　　）。 ①、定义域

②、个体域

③、辖域

④、值域

7、下列公式中，（　　）是析取范式。 ①、?(P∧Q)

②、?(P∨Q)

③、(P∨Q)

④、(P∧Q)

8、设G是一个12阶循环群，则该群一定有（　　）个不变子群。 ①、2

②、4

③、6

④、8

9、图的构成要素是（　　）。 ①、结点

②、边

③、结点与边

④、结点、变和面

10、下列图中，（　　）是平面图。 ①、

11、每个非平凡的无向树至少有（　　）片树叶。 ①、1

②、2

③、3

④、4

②、

③、

④、 12、每个无限循环群有（　　）个生成元。 ①、1

②、2

③、3

④、4

13、设R是集合A＝{1,2,3,4}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则下列（　　）不成立。 ①、R是自反关系

②、R是反自反关系

③、R是反对称关系

④、R是传递关系

14、设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（　　）。 ①、2

②、8

③、16

④、24

15、下列命题中，（　　）不是真命题。。 ①、海水是咸的当切仅当蝙蝠是瞎子

②、如果成都是直辖市，那么北京是中国的首都

③、若太阳从西边落下，则2是奇数 ④、夏天冷当切仅当冬天热

二、多项选择题（每小题1分，共10分。五选二至五）

1、设R是任意集合A上的空关系，则R是（　　　　）。 ①、自反的

②、反自反的

③、对称的

④、反对称的

⑤传递的

2、设G＝{a}，在G上定义一个二元运算“*”，则在G中运算*一定满足（　　　　）。 ①、可结合

②、可交换

③、可幂等

④、可消去

⑤可吸收

3、设S、R都是定义在集合A上的二元关系，则下列不成立的有（　　　　）。 ①、若R、S是自反的，则R?S也是自反的 ③、若R、S是对称的，则R?S也是对称的 ⑤、若R、S是传递的，则R?S也是传递的 4、下列哈斯图中，是格的有（　　　　）。 ①、

5、在整数个体域上，下列各式中，真值为真的有（　　　　）。 ①、(?x)(?y)(xy=1)

②、(?x)(?y)(xy=x)

③、(?y) (?x) (xy=0)

②、

③、

④、

⑤

②、若R、S是反自反的，则R?S也是反自反的 ④、若R、S是反对称的，则R?S也是反对称的

④、(?x)(?y)(?z)(x+y=z) ⑤、(?x)(?y)(?z)(x-y=z)

6、设G是一个13阶群，则G一定是一个（　　　　）。 ①、可换群

②、循环群

③、变换群

④、不变子群

⑤循环半群

7、设G＝?P∨Q，则G一定是一个（　　　　　　　　）。 ①、文字式

8、一棵非平凡的外向树，其对应矩阵满足（　　　　　　　　）。 ①、对角线全为零

②、仅有一行全为零 ⑤至少有二列全为零

1 4

2 5 5 ③、仅有一列全为零

7 6

⑤、

②、短语

③、子句

④、合取范式

⑤、析取范

④、至少有二行全为零

9、下列图中，那些是右图的强分图。（　　　　　　　　） 1 ①、

1 ②、

1 ③、 2 3

3 6 ④、 4 4 4 3 3 10、下列图中，是二分图的有（　　　　　　　　）。 ①、

三、名词解释（每小题2.5分，共10分） 1、试述谓词公式中解释的定义。 2、试述函数中单射函数的定义。 3、试述代数系统中子代数的定义。

②、

③、 ④、 ⑤

4、试述一个简单有向图是单向连通图的定义。四、判断分析改错题（每小题5分，共15分）

1、若R是集合A上的对称关系和传递关系，则R一定是A上的自反关系吗？为什么？ 2、右图是二分图吗？为什么？

3、设是一个代数系统，R是实数集合，“＋”是一般的加法运算，R上的函数f为：f(x)=x+5，2 则函数f能构成代数系统的自同构吗？为什么？五、计算题（每小题7分，共28分）

1、求命题公式 (P→Q)?R 的主析取范式和主合取范式。

2、给定一个偏序的哈斯图如下，试求集合B={a,b,c,d}的八种特殊元素（如果有的话）。 3、设有代数系统，运算“*”定义如下：?a,b∈I，有：

a*b=a+b+2

试验证该代数系统是否是一个循环群？如是，请求出该循环群的全部生成元，幺元，每个元素的逆元。

4、求下图的最小生成树，并求出该最小生成树的权值之和。六、综合证明题（共22分）

1、符号化下列语句，并用演绎法加以证明。

V1 1 15 V8 e a 7 8 3 g b d V7 4 V6 9 V5 f c 1 610 9 4 5

18 2 3 6 7 13 11 V9 10 8 V10 9 V2 21 5 5 12 V11 8 16 6 25 17 V13 2 11 V12 14 V19 V4 23 （7分） 3 每个计算机专业的学生都要学习离散数学；有些大学生没有学习离散数学。所以有的大学生不是计算机专业的学生。 2、设是一个群，定义集合G上的一个关系R如下：

-1

（7分）

R={|(x,y∈G)且（存在Q∈G使得y=Q*x*Q）}

证明：R是集合G上的一个等价关系。

3、设是一个群，B是G的一个非空子集，且满足2×|B|＞|G|，证明：对G中的任意一个元素a，在B中必存在元素b1，b2，使得

a=b1*b2。

（提示：考察集合C={a*b|b∈B}）

-1

（8分）

参考答案及评分标准

一、1、①

6、③

2、② 7、④ 12、②

3、④ 8、③ 13、①

4、④ 9、③ 14、③

5、② 10、③ 15、③ 4、③④

5、②③⑤

11、②

二、1、②③④⑤

6、①②④⑤ 三、略

2、①②③④ 7、③④⑤

3、②③④⑤ 8、①③

9、③④⑤ 10、②③④

四、1、不一定。例如A为任一非空集合，R是A上的空关系，则R是对称的和传递的，但不是自反的。

2、该图不是二分图。因为一个图是二分图当切仅当该图中所有回路的长度均为偶数，而图中回路123451的长度为奇数。

3、函数f不能构成代数系统的自同构。因为f(x+y)=x+y+5，f(x)+f(y)=x+5+y+5=x+y+10，因此f(x+y)≠f(x)+f(y)，f不满足同态式，所以f不是同态映射，故f不能构成代数系统的自同构。五、1、方法1：

P Q R P→Q (P→Q)?R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 主析取范式为（使公式为1的解释所对应的极小项的析取）： (?P∧?Q∧R)∨(?P∧Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R) 主合取范式为（使公式为0的解释所对应的极大项的合取）： (P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) 方法2：

(P→Q)?R = ((P→Q)→R)∧(R→(P→Q))

= (?(P→Q)∨R)∧(?R∨(P→Q)) = (?(?P∨Q)∨R)∧(?R∨?P∨Q) = ((?(?P)∧?Q)∨R)∧(?P∨Q∨?R) = ((P∧?Q)∨R)∧(?P∨Q∨?R) = (P∨R)∧(?Q∨R)∧(?P∨Q∨?R)

= (P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)∧(?P∨Q∨?R)

搜索更多关于：离散数学试卷1 的文档

离散数学试卷1.doc 将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印

下载这篇word文档

本文链接：https://www.diyifanwen.net/c2tbp5398o31ujtp7zfpn_1.html（转载请注明文章来源）