当前位置:文档之家› 2020年7月份东北大学《离散数学》 作业答案

2020年7月份东北大学《离散数学》 作业答案


课程名称:离散数学 X
6
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
课程名称:离散数学 X
7
={{{1}}, {1,{1}}}
五. (25 分)给定集合 A={1,2,3},定义 A 上的关系如下:
课程名称:离散数学 X
3
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
R={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系(全域关系))
课程名称:离散数学 X
5
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
七. (14 分) 有三个小题 1. 指出下面各个图中哪些是彼此同构的.
解:a、 h 、 i 同构; b、 d 同构; c、g 同构 e、f 同构; 2. 上面图 b 与 c 显然是不同构的,请说明不同构的理由(说明一个即可。)
解:两个无向图的关联矩阵经过行或者列交换以后完全不相同,那么这两个图不是同构。
B 图有 5 个结点,两两结合。而 C 图并没有两两结合。 3.请画出五个具有五个结点的无向图,使之分别满足: (1) 是欧拉图但不是汉密尔顿图。 (2) 既是欧拉图也是汉密尔顿图。 (3) 是完全图 K5。 (4) 是棵树。 (5) 是汉密尔顿图但不是欧拉图 。
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} 1. 写出关系 R 的矩阵;再画出上述各个关系的有向图。
解:关系 S 的矩阵如下: 下
010 MS 001
100
面是几个关系的有向图:
1

。 2 。3
M
1

。。
2
有幺元
有零元
2.指出 R 对上面哪些运算构成群?.
解:1.
|x-y|
max
×
min

有交换性




×
有结合性
×



×
有幂等性
×

×

×
有幺元
×
×

×
×
有零元
×
×

×
×
2. 构成半群的有:<R,+>, <R,×>, <R,max>, <R,min>. 构成独异点的有: <R,+>, <R,×>。 构成群的有: <R,+>。
3
T
1

。。
2
3
S
1

。2 。3
R
2.判断各个关系性质。用“√”表示“是”,用“×”表示“否”,填下表:
自反的
反自反的
对称的 反对称的 传递的
R
S
T
M 解
自反的
反自反的
对称的
反对称的
传递的
R

×

×

S
×

×

×
T

×

×

M

×
×


3.上述四个关系中,哪些是等价关系?哪些是偏序关系?
课程名称:离散数学 X
4
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
对等价关系,写出此等价关系的各个等价类。
解:T 和 R 是等价关系。 M 是偏序关系。
A/T={{1,2},{3}}
A/R={{1,2,3}}
4.求复合关系 RoT
解:SoT={<1,1>,<1,2>,<2,3>,<3,1>,<3,2>}
(1) A×P(B) (2) A⊕B (3) P(A)-P(B)(B)={1,{1}}× {Φ,{1}}
={<1,Φ>,<1,{1}>,<{1},Φ>,<{1},{1}>} ⑵ A⊕B=(AB)-(AB)
=({1,{1}}{1})- ({1,{1}} {1})={1,{1}}-{1}={{1}}。 ⑶ P(A)-P(B)={Φ,{1},{{1}}, {1,{1}}-{Φ,{1}}
三、(14 分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过 程。
xC(x), x(A(x) B(x)), x(B(x) C(x)) xA(x)
课程名称:离散数学 X
2
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
四.(12 分)令集合 A={1,{1}},B={1},P(A)表示 A 的幂集。分别计算: (注意:要求有计算过程,不能直接写出结果!)
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
东北大学继续教育学院
离散数学 X 试 卷(作业考核 线上 2) A 卷(共 4 页) 总分 题号 一 二 三 四 五 六 七 八 九 十
得分
一、 (13 分)有两个小题 1.分别说明联结词 、∧、∨、→和 在自然语言中表示什么含义。
六. (12 分) R 是实数集合,给出 R 上的运算如下:×、+、|x-y|、min、max,分别表示乘法、 加法、x-y 的绝对值、两个数中取最小的、两个数中取最大的运算。 1. 判断各个运算性质。用“√”表示“是”,用“×”表示“否”, 填下表:
|x-y|
max
×
min
+
有交换性
有结合性
有幂等性
PQ
PQ
PQ
PQ
PQ
解:
P
Q
PQ
PQ
PQ
PQ
F
F
T
F
T
F
F
T
F
T
T
F
T
F
F
T
F
F
T
T
T
T
T
T
课程名称:离散数学 X
1
学习中心 贵州六盘水奥鹏学习中心[5]VIP 院校学号:C03858012030004 姓名
王健
二、 (10 分)写出命题公式 (Q→ P)→Q 的主合取范式。(要求有解题过程)
解:
方法 1:等价变换
(QP)Q
(Q∨P)∨Q
( 去 )
(Q∧P)∨Q
( 摩根定律 )
Q
( 吸收律 )
(P∧P)∨Q
(互补、同一律 )
(P∨Q)∧(P∨Q) ( 分配律 )
方法 2:真值表法
先列(QP)Q 的真值表如下:
P
Q
P
QP
(QP)Q
F
F
T
T
F
F
T
T
T
T
T
F
F
T
F
T
T
F
F
T
从真值表看出,该命题公式的主合取范式含有大项 M0 和 M2,即(P∨Q)和 (P∨Q)。于是此命题公式的主合取范式为: (QP)Q (P∨Q)∧(P∨Q)
解:“”表示“…不成立”,“不…”。 “∧”表示“并且”、“不但…而且...”、“既…又 ...”等。 “∨”表示“或者”, 是可兼取的或。 “”表示 如果… ,则 …;只要… ,就 …; 只有… , 才…; “”表示“当且仅当”、“充分且必要”。
仅当 … 。
2.分别列出 P Q、P Q、P Q、P Q 的真值表(填下表)。
相关主题