离散数学题库(3)

21．设S是非空有限集，代数系统中，其中P（S）为集合S的幂集，则P（S）对∪运算的

单位元是________，零元是________。

+>中，2的阶是________。 22．在

24．在下图中，结点v2的度数是________。

?0125．设图D=，V={v1，v2，v3，v4}，若D的邻接矩阵A=??1??1101001001?1?，则deg-（v）=________，

1

0?1??从v2到v4长度为2的路有________条。

三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）

+B，A的幂集P（A）26．已知A={{?}，{?，1}}，B={{?，1}，{1}}，计算A∪B，A○。

27．构造命题公式（（P∧Q）→P）∨R的真值表。

28．下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，A4及可达矩阵P。

29．求下列公式的主合取范式和主析取范式：P∨（? P→（Q∨（? Q→R）））

30．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画的哈斯图，并求A中的最大

元、最小元、极大元、极小元。

四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分） 31．在整数集Z上定义：a?b?a?b?2,?a,b?Z，证明：是一个群。 32．R是集合A上自反和传递的关系，试证明：R?R=R。

五、应用题（本大题共2小题，第34小题6分，第35小题9分，共15分） 34．构造下面推理的证明。

如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。

35．今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：

（1）当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边

（或右边）的人的朋友。

（2）当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。

11

12