离散10_answer

《离散数学》试卷（10）参考答案与评分标准

一、单项选择题（本大题共10道小题，每小题2分，共20分） 1．设A、B均为非空集合，则下列命题正确的是( C )

A

AB B AB C ABA D ABA

2．设R是Z上的关系，r（R）是R的自反闭包，则r(R)=（ B ）。

A．R B.Rx,xxZ C.x,xxZ D.Rx,xxZ

4则3+36

3．下面命题中为假的命题是（B ）

A.若2+2=4 则3+3=6 B. 若2+2=4 则3+36 C 若2+24 则3+3=6 D. 若2+24．设 是一代数系统，则下列说法正确的是（ B ）。

A．一定有单位元 B.若单位元存在，则必唯一C．零元素一定存在 D.若单位元存在，单位元可能不唯一

5．群中每一元素的逆元（A ）

A 存在且唯一 B 存在但不唯一 C 可能不存在 D 若存在，一定与零元相同 6．图G（n，m），其中VA 2mv1,v2,,vn则deg(vi)（ C ）

i1n2 B 2m1 C 2m D 2m1

7．下列是命题的为 （C ）

A 坐下！ B 你住在那里？C 实践是检验真理的唯一标准。 D 今天天气真好啊！ 8．设命题公式G=（P∧Q）→P则G是（ B ）

A 恒假的 B 恒真的 C 可满足的 D 析取范式 9．在自然数集N 上定义二元运算，满足交换律的是（ C ）。

A．a*b=a-b B．a*b=a+2b C．a*b=a D．a*b=

ab

10.当且仅当为下面条件中的哪一个时，无向图G是欧拉图？（ C ）。

A．G的所有结点的度数为偶数； B．G的所有结点的度数为奇数；

C．G连通且所有结点的度数为偶数； D．G连通且所有结点的度数为奇数。

二、填空题（本大题共10空，每空2分，共20分） 1．设Ea,b,c,d,e,f，Aa,b，Ba,c,d，则～A∪～B={b,c,d,e,f}

2．设P：a是偶数，Q：b是偶数，R：a+b是偶数；则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为_____PQR_____________________________。 3.设T是树，T有15个结点，则T的总度数为 28 。 4． 命题公式(pq)q的类型是_____矛盾式_______________________。

5． 在布尔代数中，有aabab,则该式的对偶式为 a(ab)ab 。

6．无向完全图G有n个结点，则G的边数m n(n-1)/2

《离散数学》试卷10答案 第 1 页 共 3 页

7．设A={a,b,c}，A上关系R的关系图为，则具有性质 传递性 。

8．谓词公式x(P(x)yQ(y))R(x)中x的辖域是 P(x)yQ(y) 。 9．集合A={1,2,„,10}上的关系R为整除关系，则R为 等价 关系。 10．设B(x):x是鸟；F（x）：x会飞，“鸟都会飞”可符号化为：x(B(x)F(x)). 三、判断题（本大题共10小题，每小题1分，共10分） 1. （√ ）若A={Ф},B=P（A）,则有{Ф}B及{Ф}B。 2. （× ）设A,B为无限集，则A-B还是无限集。 3. （× ）欧拉通路一定是初级通路。

4. （√ ）简单连通图 G(n,m),若m=n-1,则它一定是树。

5. （× ）集合R上的关系满足对称性与传递性，则一定满足自反性。 6. （× ）群中既有零元又有单位元。

7. （× ）命题公式pq的所有成真赋值是00、01和10。 8. （× ）设图GV,E,G=,若VV且EE，则G是G的生成子图。 P(QP)是重言式。

9. （√ ）命题公式

10. （× ）如果太阳从西边升起，则雪是黑的。这句话不是命题。 四、证明题（本大题共3小题，每小题各6分，共18分）

1．设集合Ａ＝{０，１，２，３，４，５}，Ｒ＝{＜０,０＞，＜１，１＞，＜１，２＞，＜１,３＞，＜２,１＞，＜２,２＞，＜２,３＞，＜３,１＞，＜３,２＞，＜３,３＞，＜４，４＞，＜４，５＞，＜５，４＞，＜５,５＞}，试用关系图验证Ｒ是Ａ是上的等价关系。

证明：只需证R满足自反性、对称性、传递性。（6分） 2.在一阶逻辑中符号化下述命题，并推证之。

凡人必有一死，苏格拉底是人，所以苏格拉底会死的。 证明：令F(x)：x是人，G(x)：x是要死的，a：苏格拉底 前提：x(F(x)→G(x))，F(a)

结论：G(a) （2分） 证明：① F(a) 前提引入 ② x(F(x)→G(x)) 前提引入 ③ F(a)→G(a) ②UI

④ G(a) ①③假言推理 （4分） 3．证明不存在具有奇数个面且每个面都具有奇数条棱的多面体。

证 用反证法. 假设存在这样的多面体, 作无向图G=, 其中 V={v | v为多面体的面},

E={(u,v) | u,vVu与v有公共的棱uv}.（3分）根据假设,|V|为奇数且vV,

d(v)为奇数。这与握手定理的推论矛盾。（3分）

五、计算、应用题（本大题共5小题，1-4小题各6分，第5小题8分，共32分）

1． 设有一棵树，它有两个结点度数为3，三个结点度数为2，一个结点度数为4，问它有几个结点度数为1？ 解：设有x片树叶,12+16+x=2*（2+3+4+x-1），28+x=16+x

《离散数学》试卷10答案 第 2 页 共 3 页

解得x=12，故T有12片树叶。 2． 求Q(Q→R)的主析取范式及主合取范式。（6分）

解：Q(Q→R)Q

(QR)(QQ)R

T(主合取范式) （3分）

(QR)(QR)(QR)(QR)（主析取范式） （3分）

3． 有10个人参加聚会，每个人都认识其中的7个，问能否安排坐在一个圆桌上，使每个人认识与坐在他两边的

人是认识的？为什么？（6分） 解：可以。（2分）

将每个人对应成相应的顶点，若两人认识，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都等于7，故图中任两个不相邻的顶点的度数和14大于等于10，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可以了。（4分）

4． 设G是具有四个节点的有向图，它的邻接矩阵表示如下

00

001011010011 10（1） 画出图G。（3分）

（2） G是单向连通还是强连通？（3分） 解：（1）图略（3分）

（2）G单向连通的（3分）

1005．A={1,2,3}，R为A上关系，关系矩阵为110， 101(1) 画出关系图。 (2) 求RR，R-1。

(3) 指出R具有的性质。 (4) R是偏序关系吗？若是画出哈斯图。 解：(1)

（2分）

(2) RR={<1,1>，<2,1>，<2,2>，<3,1>，<3,3>} R={<1,1>，<1,2>，<1,3>，<2,2>，<3,3>} （2分） (3) R的性质：自反性、反对称性、传递性。（2分） (4) R是偏序。（2分）

-1

《离散数学》试卷10答案 第 3 页 共 3 页