√
M
√
×
×
√
√
3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
解：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>}
六.(12分)R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
“”表示 如果… ，则 …；只要… ，就 …； 只有… , 才…； 仅当 … 。
“”表示“当且仅当”、“充分且必要”。
2．分别列出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
二、(10分)写出命题公式(Q→P)→Q的主合取范式。（要求有解题过程）
2.边数不一样多
3.
2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
(1)是欧拉图但不是汉密尔顿图。
(2)既是欧拉图也是汉密尔顿图。
(3)是完全图K5。
(4)是棵树。
(5)是汉密尔顿图但不是欧拉图。
解：1. a、h、i 同构； b、d同构； c、g同构； e、f同构
东北大学继续教育学院
离散数学X试卷（作业考核线上2）A卷（共4页）
总分
题号
一
二Байду номын сангаас
三
四
五
六
七
八
九
十
得分
一、(13分)有两个小题
1．分别说明联结词、∧、∨、→和在自然语言中表示什么含义。
解：“”表示“…不成立”，“不…”。
“∧”表示“并且”、“不但…而且...”、“既…又 ...”等。
“∨”表示“或者”， 是可兼取的或。
1.判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
填下表：
|x-y|
max
×
min
+
有交换性
√
√
√
√
√
有结合性
×
√
√
√
√
有幂等性
×
√
×
√
×
有幺元
×
×
√
×
√
有零元
×
×
√
×
×
2.指出R对上面哪些运算构成群？.
构成群的有： <R,＋>。
七.(14分)有三个小题
1.指出下面各个图中哪些是彼此同构的.
x(A(x)B(x)) P
⑵ A(a)B(a) ES ⑴
⑶xC(x) P
⑷ C(a) US ⑶
⑸x(B(x)→C(x)) P
⑹ B(a)→C(a) US ⑸
⑺B(a) T ⑷ ⑹ I
⑻ A(a) T ⑵ ⑺ I
⑼xA(x)) EG ⑻
四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
1.写出关系R的矩阵；再画出上述各个关系的有向图。
解：关系S的矩阵如下：
下面是几个关系的有向图：
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
自反的
反自反的
对称的
反对称的
传递的
R
√
×
√
×
√
S
×
√
×
√
×
T
√
×
√
×
（注意：要求有计算过程，不能直接写出结果！）
(1) A×P(B)
(2) A⊕B
(3) P(A)－P(B)
解： A={1,{1}}, B={1}，
⑴ A×P(B)＝{1,{1}}× {Φ,{1}}
＝{<1,Φ>,<1,{1}>,<{1},Φ>,<{1},{1}>}
⑵ A⊕B＝(AB)－(AB)
=({1,{1}}{1})－ ({1,{1}}{1})＝{1,{1}}－{1}＝{{1}}。
等价变换
(QP)Q
(Q∨P)∨Q ( 去)
(Q∧P)∨Q ( 摩根定律 )
Q ( 吸收律 )
(P∧P)∨Q （互补、同一律 ）
(P∨Q)∧(P∨Q) ( 分配律 )
三、(14分)用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。
xC(x),x(A(x)B(x)),x(B(x)C(x))xA(x)
⑶ P(A)－P(B)＝{Φ,{1},{{1}}, {1,{1}}－{Φ,{1}}
＝{{{1}}, {1,{1}}}
五.(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>}