离散数学(本)复习题

离散数学（本）复习题

1.请给出公式G=（P（QP））（P（PQ））的真值表。

2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系RC。

3.R，S是集合A上的两个关系。试证明下列等式：

（1）(R•S)-1= S-1•R-1

（2）(R-1)-1= R

（3）(R∪S)-1= R-1∪S-1

（4）(R∩S)-1= R-1∩S-1

4.设R是集合A上的关系，令

R+={(x, y)|xA，yA，并且存在n>0，使得xRny}，

则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。

5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。

6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，

1

R）的Hasse图。

7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？

8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a  b可得b  a，再由传递性得a  a”。你的意见呢？

9.若集合A上的关系R，S具有对称性，证明：R•S具有对称性的充要条件为R•S= S•R。

10.若R是等价关系，试证明R-1也是等价关系。

11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：

a) (P(QR))((PQ)(RS))

b) ((PQ)R)(((PQ)R)S)

c) ((PQ)R)((QP)(RS))

d) (P(Q(RP)))(QS)

12.试将下列公式化成等价的前束范式：

(1)x(P(x)yQ(x，y))；

2

(2)x((yP(x，y))(zQ(z)R(x)))；

(3)xy(zP(x，y，z)(uQ(x，u)vQ(y，v)))。

13.设S={G1，…，Gn}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。

14.证明下面的等价式：

(1) (P(QR))(QR)(PR)=R

(2) P(QP)=P(PQ)

(3) P(QR)=(PQ)(PR)

(4) (PQ)(RQ)=(PR)Q

15．找出下面公式的Skolem范式：

(1)(xP(x)yzQ(y，z))；

(2)x(E(x，0)(y(E(y，g(x))z(E(z，g(x))E(y，z)))))。

16．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：nC2m表示m中取2的组合数。

3

C2m ，其中

17．设G是有限图，M，A分别是G的关联矩阵和相邻矩阵，证明：MM’和A2的对角线上的元素是G中所有点的度。

18．设G为图（可能无限），无回路，但若任意外加一边于G后就形成一回路，试证G必为树。

19．试举出一个连通的(即漠视为图后是连通的)，但无根的有向图。

20．设G是有向图，其中含一有向路(e1，…，en)，其中fin(en)=init(e1)，证明：G不是有向树。

21．设(I，+)为整数加群，（5I，+）为I的子群，请给出mI的所有陪集。

22．证明：若一个图G的任意两点度数之和n-1，n=|P(G)|，则该图有Hamilton路。

23．给出一个具有5个点的边数最多的非Hamilton图。

24．给出代数格的定义。

25．设G为有向图，若G具有有向树定义中的1)和2)，并且没有有向回路。问：若G有限，G是否是有向树？若G不是有限的，如何？

26．设 * 是集合S上的二元代数运算，且满足结合律，设x，y是S中任意元素，如果x * y = y * x，则x = y。试证明 * 满足等幂律。

27．请给出一个布尔代数。

4

28．设R,S是A上的传递关系，证明或者反驳：

(1) RS是传递关系；

(2) RS是传递关系。

29．试用演绎法证明{PQ，QR，PM，M}共同蕴涵R(PQ)

30. 设H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合。求证HN是G的子群。

31．请求出3次对称群中每个元素的周期。

32．设H是群G的一个有限非空子集，求证只要H中任意两个元素的积仍在H内，则H是G的子群。

33．求证循环群的子群仍是循环群。

34．求证若G的元数是一个质数，则G必是循环群。

35．设K和H都是群G的子群，试证明：若H·K是G的子群，则K·H = H·K。

36．什么是等价关系？

37．如果A上的一个等价关系为R，如何求出一个等价类？

5

38．给出命题公式PQ的真值表。

39．Skolem范式中的母式有什么特点？

40．什么是Euler图？举一个例子

41．什么是主析取范式？举一个例子。

42．什么是谓词逻辑的解释？举一个例子。

43．什么是代数格？举一个例子。

44．半序子格与代数子格是什么关系？

45.什么是域？举一个有限域的例子。

6