离散数学重要复习题

离散数学重要复习题

1．请给出集合的吸收率。

2．设A={a，b，c}，问IA，EA是否具有自反性，反自反性，对称性，反对称性，传递性？ 3．设A={1，2}，请给出A上的所有关系。

4．设A={1，2，3}，请给出A上的两个不同的等价关系。

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

6．A={1，2，3，4，5，6，7，8，9，10}，R为A上的整除关系，请给出A的Hasse图，并求出所有的极大元素，极小元素，最大元素，最小元素。

7．设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 8．有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？

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

-1

10．若R是等价关系，试证明R也是等价关系。

11．给出一个群的例子，并指出单位元素及各元素的逆。 12．指出下列公式哪些是恒真的哪些是恒假的： (1)P?（P? Q）?Q

(2)（P? Q）?（?P?Q）

(3)（P? Q）? （Q?R）?（P? R ） (4)（P? Q）?（P? Q??P?? Q）

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)))))。

2216．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n?Cm ，其中Cm 表示

m中取2的组合数。

2

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

18．什么是半序格？请举一例。

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．R，S是集合A上的两个关系。试证明下列等式：

1

（1）(R?S)= S?R

-1-1

（2）(R)= R

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

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

28．请给出3元置换群中的所有元素，并指出哪个是单位元。 29．试用演绎法证明{P?Q，Q?R，P?M，?M}共同蕴涵R?(P?Q)

30. 求证G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。

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

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，如何求出一个等价类？ 38．请给出?P，P?Q，P?Q的真值表。 39．Skolem范式中的母式有什么特点？ 40．有根的有向图，是否一定是强连通的？ 41．最优树是否一定唯一？

42．什么是谓词逻辑中的项？43．什么是代数格？ 44．半序子格与代数子格是什么关系？

45．设A={1，2，3}，B={2，3，4}，求A?B，?(A)??(B)。

46．设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。

(1) ?xR(x)??xS(x) (2) ?x(P(x)?Q(x)) (3)?x?P(x)??xP(x)

47．举例说明不要求可除条件而要求消去条件，即要求由ax=ay可推出x=y，由x·a=y·a可推出x=y，则G不见得是一个群，若G有限怎么样？

48．设G=?x?yP(x,y), D={a,b}，请给出一个满足G的解释。 49．证明：连通图中任意两条最长的简单路必有公共点。 50．给出环的定义。

-1-1-1

2

本文来源：https://www.bwwdw.com/article/wmid.html