东大21年12月考试《离散数学X》考核作业[答案]

东大21年12月考试《离散数学X》考核作业[答案]答案

东 北 大 学 继 续 教 育 学 院 离散数学 X 试 卷（作业考核 线上2） A 卷（共 4 页） 总分 题号 一 二 三 四 五 六 七 八 九 十 得分 一、 (13分)有两个小题 1．分别说明联结词、、、和在自然语言中表示什么含义。 2 ．分别列出P Q 、P Q 、P Q 、P Q 的真值表(填下表

东北大学继续教育学院
离散数学 X试 卷（作业考核 线上2） A 卷（共 4 页）
总分题号一二三四五六七八九十
得分
一、(13分)有两个小题
1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。





2．分别列出PÚQ、PÙQ、P«Q、P®Q的真值表(填下表)。
PQPÚQPÙQP«QP®Q

正确答案:-----

二. (10分)写出命题公式 (Q→ØP)→Q 的主合取范式。（要求有解题过程）


















三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。
xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)









四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
（注意：要求有计算过程，不能直接写出结果！）
(1) A×P(B)
(2) A⊕B
(3) P(A)－P(B)












五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系（全域关系）)
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
自反的反自反的对称的反对称的传递的
R
S
T
M
3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT














六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
1.判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
填下表：
|x-y|max×min+
有交换性
有结合性
有幂等性
有幺元
有零元
2.指出R对上面哪些运算构成群？.





















七. (14分) 有三个小题
1.指出下面各个图中哪些是彼此同构的.

2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
(1) 是欧拉图但不是汉密尔顿图。
(2) 既是欧拉图也是汉密尔顿图。
(3) 是完全图K5。
(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。

正确答案:-----

------分隔线----------------------------

东大21年12月考试《离散数学X》考核作业[答案]历年参考题目如下：

20秋学期《离散数学X》在线平时作业3

试卷总分:100 得分:100

一、单选题 (共 10 道试题,共 40 分)

1.设命题P、Q、R所代表的意义如下：

P：天气好。

Q：我去上街。

命题“如果天气好，则我上街；否则我就不上街。”的符号表达式为（ ）。

A.Ø (P?Q) ?ØQ，

B.(P?Q) Ú (ØP ?ØQ)，

C.(P?Q) Ù(ØP ?ØQ)

D.(P ?Q) ?(ØP ? ØQ)

2.

A.

B.

C.

D.

3.

A.自然数集合

B.整数集合

C.有理数集合

D.实数集合

4.

A.B:①：⑵⑶⑺⑻

B.B:②：⑶⑷⑻

C.B:③：⑶⑹⑺⑻

D.B:④：⑶⑺

5.命题公式(P?Q)?Q的主合取范式是（ ）。

A.P∨ØQ；

B.P∨Q；

C.(ØP∨Q)∧(P∨ØQ )；

D.(P∨Q )∧(Ø P∨ØQ ) 。

6.

A.

B.

C.

D.

7.

A.矛盾式

B.重言式

C.无法确定

D.不知道

8.

A.等价

B.不等价

C.无法确定

D.不知道

9.

A.重言式

B.矛盾式

C.无法确定

D.不知道

10.单选题。 无向图是连通的，当且仅当（ ）。

A.任何两个结点之间都有通路；

B.任何两个结点之间都有唯一路；

C.任何两个结点之间都有路；

D.任何两个结点之间都有迹。

二、多选题 (共 5 道试题,共 20 分)

11.R是实数集合，给定R上的五个关系如下:

A={|x=y2} B={|y=x+6}

C={|y=(x+1)-1} D={|y=2x}

E={|x2+y2=4}

上述五个关系中，如果是函数，则是从R到R的入射函数的分别是（ ）。

A.A

B.B

C.C

D.D

E.E

12.多选题。下面数的序列中，哪些可能不是简单图的结点度序列?

A.(1,2,3,4,5)

B.(2,2,2,2,2)

C.(1,2,3,2,4)

D.(1,1,1,1,4)

E.(1,2, 2,4,5)

13.试题见图片{图}

A.A图

B.B图

C.C图

14.

A.A：⑴⑵⑶

B.B：⑴⑵⑷

C.C：⑵⑶⑷

D.D：⑴⑵⑶⑷

15.多选题。写出独异点定义中满足下面哪些性质。

A.封闭性；

B.可结合性；

C.可交换性；

D.有么元；

E.有零元。

F.每个元素有逆元；

G.幂等性。

三、判断题 (共 10 道试题,共 40 分)

16.设A={Φ}，B=P(P(A))。判断下面命题的真值。

17.设A={Φ}，B=P(P(A))。判断下面命题的真值。

18.R是A上关系，判断下面命题的真值。

19.判断下面命题的真值。

20.R是A上关系，判断下面命题的真值。

21.判断下面命题的真值。

22.判断下面命题的真值

23.判断下面命题的真值。

24.判断题 。判断下面的说法是否正确。

R和S都是A上任何传递关系，则R∩S 也传递。

25.判断题 。判断下面的说法是否正确。

R和S是A上任何自反关系，则R∩S 也自反。