离散数学2018年4月考试真题(02324)

小赵、小李、小钱、小孙参加数学建模竞赛，根据下列情况，确定4人中获奖的是哪些人，未获奖的是哪些人。需写出推导过程。

(1)只要小赵或小钱中一人未获奖，小孙和小李就都得奖;

(2) 小孙没获奖或小李没获奖是不可能的;

(3) 小钱获奖了。

证明集合X的幂集P(X)关于对称差运算⊕构成群。

已知n阶简单图G中有m条边，各结点的度数均为3，且满足2n=m+3，求G的阶数，并画出满足条件的所有不同构的G。

设R、S都是A上的二元关系，证明：dom(R∪S)=dom(R)∪dom(S)。

有向图D如图30图所示，回答一下问题：

(1)写出D的邻接矩阵A;

(2)D中长度为1、2、3、4的通路各有多少条?其中回路分别为多少条?

根据关系的性质，填写下表(具备某项性质填写“√”，不具备填写“×”)。

请将下表绘制在答题卡中并作答。

画出下列集合关于整除关系的哈斯图：

{1，2，3，4，6，8，12，24}

并指出它的极小元，极大元，最小元，最大元。

若含n(n≥2)个命题变项的命题公式A的主合取范式包括k个极大项，则A的主析取范式必定包括_______个极小项。

一个n阶(n>2)简单非连通图的边的最大个数是_______。

设A为非空有限集合，P(A)为A的幂集，∩ 为集合的交运算，则群的单位元是_______，零元是_______。

一颗无向树T，有40个1度结点，20个2度结点，31个3度结点，无6度或以上结点，则T中有 _______个4度结点，_______个5度结点。

无向图G有11条边，4个3度结点，起于均为5度结点，则G的阶数为_______，其中5度结点有_______个。

集合A={1，2，3，4}，A上的关系R={<1,1>,<2,1>,<3,2>,<4,3>}，则R²=_______，R^-1=_______。

设有集合A和B，|A|=5，|B|=2，则从A到B不同的满射函数共有 _______个。

设R、S是集合A上的两个偏序关系，则仍然是偏序关系的为()

• A.R∪S
• B.R-S
• C.R。S
• D.R ∩ S

下图中4个偏序集的图形，不能构成格的是()

• A.
• B.
• C.
• D.

设f是从实数集合R到R的函数，则不是双射函数f(x)的是()

• A.x3
• B.x2
• C.2x+1
• D.xe^x

在自然数集合N上，可结合的运算是()

• A.a*b=a-b
• B.a*b=max(a，b)
• C.a*b=a+2b
• D.a*b=|a-b|

要从完全图K₅中得到一颗生成树，需要删除的边数为()

• A.5
• B.6
• C.7
• D.10

对于完全图K_n(≥3)，结点按字母标定，如果字母顺序不同即作为不同回路，那么K_n中哈密顿回路个数为()

• A.n
• B.n(n-1)
• C.2ⁿ
• D.(n-1)!

集合A上的对称关系R的关系矩阵为M，则M的元素必定()

• A.对角线上全是0
• B.对角线上全是1
• C.关于对角线对称
• D.关于反对角线对称

简单无向图G有16条边，每个结点都是2度结点，则G的结点数为()

• A.8
• B.14
• C.16
• D.18

下列谓词恒等式，不正确的是()

• A.
• B.
• C.
• D.

下列度数序列中，不能构成简单无向图的是()

• A.{1，1，1，2，3}
• B.{1，3，3，3}
• C.{2，2，2，2，2}
• D.{3，3，3，3}

• A.等价关系
• B.偏序关系
• C.全序关系
• D.恒等关系

下列图中，是欧拉图的为()

• A.
• B.
• C.
• D.

设A是含n(n≥1)个命题变项的公式，若A是重言式，则A的主析取范式含极小项个数为()

• A.0
• B.1
• C.n
• D.2ⁿ

令F(x)：x是实数，G(x)：x是有理数。命题“实数不全是有理数”的符号化形式为()

• A.
• B.
• C.
• D.

令p：天下大雨，q：小王迟到。命题“除非天下大雨，否则小王不会迟到”的符号化形式为()

• A.p→q
• B.q→p
• C.￢p→q
• D.￢q→p