离散数学期末考试试题配答案Word文件下载.docx

离散数学期末考试试题配答案Word文件下载.docx

《离散数学期末考试试题配答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《离散数学期末考试试题配答案Word文件下载.docx（7页珍藏版）》请在冰点文库上搜索。

一．填空题（每小题2分，共10分）

1.谓词公式

的前束范式是__∃x∃y¬

P（x）∨Q（y）__________。

2.设全集

则A∩B=__{2}__，

_{4,5}____，

__{1,3,4,5}_____

3.设

，则

__{{c},{a,c},{b,c},{a,b,c}}__________，

_____Φ_______。

4.在代数系统（N，+）中，其单位元是0，仅有_1___有逆元。

5．如果连通平面图G有

个顶点，

条边，则G有___e+2-n____个面。

二．选择题（每小题2分，共10分）

解：

主合取方式：

p∧q∨r⇔（p∨q∨r）∧（p∨¬

q∨r）∧（¬

p∨q∨r）=∏0.2.4

主析取范式：

p∧q∨r⇔（p∧q∧r）∨（p∧q∧¬

r）∨（¬

p∧q∧r）∨（¬

p∧¬

q∧r）∨（p∧¬

q∧r）=∑1.3.5.6.7

2.设集合

上的二元关系R的关系矩阵为

求

的关系矩阵，并画出R，

的关系图。

（10分）

3无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？

∵G（V,E），|E|=V，d（Vi）<

3,

设至少有x个节点，由握手定理得：

2×

12=∑d（Vi）<

6×

3+（x-6）×

3

2<

（x-6）=＞x>

8

故G中至少有9个节点。

4求下面两个图的最小生成树。

（12分）

5.试判断

是否为格？

说明理由。

（5分）

（Z,≤）是格，理由如下：

对于任意a∈Z，a≤a成立，满足自反性；

对于任意a∈Z，b∈Z，若a≤b且b≤a，则a=b，满足反对称性；

对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；

而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。

（注：

什么是格？

）

四．证明题（共37分）

1.用推理规则证明

。

证明：

编号公式依据

（1）（¬

B∨C）∧¬

C前提

（2）¬

B∨C，¬

C

（1）

（3）¬

B

（2）

（4）A→B（3）

（5）¬

A（3）（4）

（6）¬

（¬

A∧D）前提

（7）A∨¬

D（6）

（8）¬

D（5）（6）

2.设R是实数集，

，

求证：

都是满射，但不是单射。

要证f是满射，即∀y∈R,都存在（x1，x2）∈R×

R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；

再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×

R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；

最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：

g（x1，x2）=g（x2，x1），取x1≠x2，即证得。

3.无向图G有9个结点，每个结点的度数不是5就是6，求证：

G中至少有5个6度结点或6个5度结点。

设G中至多有4个6度结点且5个5度结点，

∴d（Vi）=49不是偶数，

故它不是一个图，矛盾。

（下面只供参考，个人答案）

4.设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。

（7分）

设任意两点间的读书和恰好为1，则满足：

∑d（Vi）=2e

d（Vi）≤6

∴6×

100≥2e

e≤300

故最多只有300条边，即300对点距离恰好为1.