2020年7月份东北大学《离散数学》 作业答案Word格式文档下载.doc

2020年7月份东北大学《离散数学》 作业答案Word格式文档下载.doc

《2020年7月份东北大学《离散数学》 作业答案Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《2020年7月份东北大学《离散数学》 作业答案Word格式文档下载.doc（5页珍藏版）》请在冰点文库上搜索。

、∧、∨、→和«

在自然语言中表示什么含义。

解：

“Ø

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

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

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

“®

”表示如果…，则…；

只要…，就…；

只有…,才…；

仅当…。

“«

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

2．分别列出PÚ

Q、PÙ

Q、P«

Q、P®

Q的真值表（填下表）。

P

Q

P«

PÚ

P®

PÙ

F

T

二、（10分）写出命题公式（Q→Ø

P）→Q的主合取范式。

（要求有解题过程）

先列（Q®

P）®

Q的真值表如下：

Q®

（Q®

从真值表看出，该命题公式的主合取范式含有大项M0和M2，即（P∨Q）和（Ø

P∨Q）。

于是此命题公式的主合取范式为：

Ø

QÛ

（P∨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）

（1）A×

P（B）={1,{1}}×

{F,{1}}={<

1,F>

<

1,{1}>

{1},F>

{1},{1}>

}

（2）A⊕B＝（AÈ

B）－（AÇ

B）=（{1,{1}}È

{1}）－（{1,{1}}Ç

{1}）＝{1,{1}}－{1}＝{{1}}。

（3）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>

2,1>

2,2>

3,3>

M={<

1,3>

1.写出关系R的矩阵；

再画出上述各个关系的有向图。

关系R的矩阵如下：

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

2.判断各个关系性质。

用“√”表示“是”，用“×

”表示“否”，填下表：

自反的

反自反的

对称的

反对称的

传递的

R

×

√

S

M

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

哪些是偏序关系？

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

T和S是等价关系。

M是偏序关系。

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

4.求复合关系RoT

解：

RoT＝{<

3,2>

六.（12分）R是实数集合，给出R上的运算如下：

、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。

1.判断各个运算性质。

”表示“否”，

填下表：

|x-y|

max

min

+

有交换性

有结合性

有幂等性

有幺元

有零元

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

.

构成半群的有：

<

R,＋>

，<

R,×

>

R,max>

<

R,min>

构成独异点的有：

<

。

构成群的有：

七.（14分）有三个小题

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

1．a,,h,i同构

2．b,d同构

3．c,g同构

4．E,f同构

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

b和c同构，则必有A与A'

对应

b中，与c关联的B有环，

b'

中，与c'

关联的结点没有环

∴不同构

3.请画出五个具有五个结点的无向图，使之分别满足：

（1）是欧拉图但不是汉密尔顿图。

（2）既是欧拉图也是汉密尔顿图。

（3）是完全图K5。

（4）是棵树。

（5）是汉密尔顿图但不是欧拉图。