东北大学《离散数学(一)X》考核作业答案

东北大学继续教育学院

离散数学（一）X试卷（作业考核线上2）A卷（共4页）

总分题号—•四五六七八九十

得分

一、（13分）有两个小题

1.分别说明联结词「、八、V、一和6在自然语言中表示什么含义。

解：

表示”…不成立”，“不…”。

表示"并且”、“不但…而且...”、“既…又...”等。

“V”表示“或者”，是可兼取的或。

“一”表示如果…，则…；只要…，就…；只有…，才…；仅当…。

表示“当且仅当”、“充分且必要”。

2.分别列出PvQ、P/\Q、POQ>PfQ的真值表（填下表）。

PQPvQPAQPfQ

解:

PQPvQPAQP->Q

FFTFTF

FTFTTF

TFFTFF

TTTTTT

二.（10分）写出命题公式（Qf[P）fQ的主合取范式。（要求有解题过程）

解：

方法1：等价变换

（Q—P）-Q

一（」QV「P）VQ（去一）

MQAP)VQ(摩根定律)

(吸收律)

yp/\「p)VQ(互补、同一律)

HPVQ)A(-iPVQ)(分配律)

方法2：真值表法

先列(Q-「P)-Q的真值表如下:

pQ-iPQf-1PQf「PfQ

FFTTF

FTTTT

TFFTF

TTFFT

从真值表看出，该命题公式的主合取范式含有大项Mo和M2,即(PVQ)和(「PVQ)。于是此

命题公式的主合取范式为：

(Qf「P)fQu(P\/Q)八(「PVQ)

三、(14分)用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过

程。

VxC(x),3x(A(x)vB(x)),Vx(B(x)—>—«C(x))=3xA(x)

解：

(l)3x(A(x)vB(x))

(2)A(a)vB(a)ES⑴

(3iVxC(x)P

(4)C(a)US(3)

(5)Vx(B(x)^-iC(x))P

(6)B(a)^-.C(a)US(5)

(7HB(a)T(4)(6)

(8iA(a)T(2)(7)

(98x(A(x))EG(8)

四.(12分)令集合A={1,{1}},B={1},P(A)表示A的幕集。分别计算:

(注意：要求有计算过程，不能直接写出结果！)

(l)AXP(B)

⑵A㊉B

⑶P(A)—P(B)

解:

A={I,⑴}，B={1},

(l)AXP(B尸［1,{1))X{①,")}

={<1,0>,<1,{1}>,<{1},0>,<{1},{1)>}

(2)A㊉B=(AUB)-(AnB)

=((1,{1)}U{1})-({1,{1}}0{1})={1,{1()-{1(={{!)}.

⑶P(A)—PB尸{中，{1},{{1}},{1,{1}}一{中，{1}}

五（25分）给定集合A={1,2,3卜定义A上的关系如下：

R={<1,2>,<2,3>,<3J>）

S二AXA（完全关系［全域关系））

T={<L1>,<1,2>,<2,1>,<2,2>,<3,3>}

M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

1.写出关系R的矩阵；再画出上述各个关系的有向图。

2.判断各个关系性质。用”「表示”是”，用“X”表示“否”，填下表:

自反的反自反的对称的反对称的传递的

R

S

T

M

3.上述四个关系中，哪些是等价关系？哪些是偏序关系?

对等价关系，写出此等价关系的各个等价类。

4.求复合关系RoT

解:1.关系S的矩阵如下：

010-

Ms=001

10（）

下面是几个关系的有向图:

2.

自反的反自反的对称的反对称的传递的

RVXVX

SXVXVX

TVXVX

MXXVV

3.

T和R是等价关系。M是偏序关系。

A/T={{1,2},{3})

A/R={{1,2,3}}

4.SOT={<1,1>,vl,2>,<2,3>,<3,1>,<3,2>}

六.(12分)R是实数集合，给出R上的运算如下：X、+、|x-y|、min、max,分别表示乘法、加

法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。

1.判断各个运算性质。用表示”是"，用“X”表示“否”，

填下表：

|x-y|maxXmin4-

有交换性

有结合性

有幕等性

有幺元

有零元

2.指出R对上面哪些运算构成群？.

解:1.

|x-y|maxXmin+

有交换性JVVX

有结合性XJVVX

有事等性XVXJX

有幺元XXVXX

有零元XXJXX

2.

构成半群的有：<R,十〉,<R,X>,<R,max>,<R,min>.

构成独异点的有；<R,+>,<R,X>0

构成群的有：<R,十>。

<R,+>是群的理由：

(1)+在实数集合内满足封闭性。即

任何a,b£R,有a+b£R。

⑵+是可结合的。

(3)0是+运算的么元。任何a£R,有0+a=a=a+0.

(4)任何实数a,都有逆元一a£R,使得(-a)+a=O=a+(-a).所以<R,+>是群。

七.(14分)有三个小题

1.指出下面各个图中哪联是彼此同构的.

E心W

2.上面图b与c显然是不同构的，请说明不同构的理由(说明一个即可。)

3.请画出五个具有五个结点的无向图，使之