离散数学复习题_离散数学期末复习题

离散数学复习题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学期末复习题”。

离散数学复习题

一、填空

1、命题中的否定联接词；蕴含联接词

2、一个命题公式，若在所有赋值下取值为真，则称此公式为式；若……假，则……..为 永假 式；若至少存在一组赋值，其命题为真，则…….为可满足式。

3、有限布尔代数只能有n4、R是定义在集合上的二元关系，若R满足性、性，则称R是A上的等价关系。

5、全序集（A，≤）必是，且是

6、n阶m条边无向图G是树，当且仅当G是连通点，且m=

7、若有向树G中，有一个顶点的入度为，则称G为根树。

8、有序对具有以下性质

（1）当x不等于y时，≠

（2）=的充要条件是x=u且y=r。

9、关系的性质五。

10、图中顶点作为边的端点的称为此顶点的度数。

11、设X是格，并对交运算时可分配的，则且 格中的交运算对并运算是可分配的。

12、有向图按连通图分为三类连通图、连通图、连通图。

13、T 为一颗根树，若T的每个分支点则称T为r元正则树。

14、设A、B是集合，求A与B之间关系（属于、不属于、包含…）如果A={1}，B={1,{1,2}}，则A不属于B、A不包含B15、若R是定义在集合A上的一个二元关系，若R满足、性、可传递性则称R是偏序关系。

16、设集合A={1,2,3,4}，A上二元关系R={}，则逆序关系R−1。

17、在有补分配格中，每个元素（的补元）都是的。

18、在无向图中，度数为奇数的顶点个数必为数。

19、若图中通路P中所有边互不相同，则称P为通路，若通路中所有顶点互不相同，则称P为 基本 通路。

二、简述题

1、偏序关系与格

2、设R是A爱上的二元关系，如果R是自反的，反对称的，传递的二元关系，则称R是A上的偏序关系或者半序关系；

2、等价关系与集合的划分

3、握手定理

4、对偶式与对偶原理

5、正规子群

6、什么是域，有限整环是不是域，为什么？

7、集合的基本运算公式（集代数公式）有哪些？

8、群论中的拉格朗日定理

9、主析取范式与主合取范式

10、鸽巢原理与计数原理

三、判断题

1、设A,B是集合，则A⨁=

2、偶数阶循环群有且只有一个2阶元素

3、设（G,∗）是n阶群，且有k阶子群，则k丨n4、有限格必是有界格

5、偶数阶群中比存在非幺元a，使得a∗a=e6、不存在含有奇数个面且每个面上有奇数条棱的多面体

7、设（A，∗）是独异点，B是A的子集，且（B，∗）是独异点，则（B，∗）一定是（A，∗）的子独异点8、3阶群同构意义下唯一

9、（N=（0），⊗）是一个群

10、素数阶群一定没有非平凡子群

四、计算题

1、求命题公式P∧（Q→R）主析取范式。

2、写出3次对称群（S3,∗）的运算表及所有正规子群。

3、在1,2,3…….100这100个自然数中，可以被2或3整除但不能被5整除的数有多少个？

4、设, A =3，P B=64，P A⋃B=256，求 B , A⋂B , A−B , A⊕B。

5、设A={a,b,c,d}，R={（a,c）,（c,b）,（b,a）,（a,d）}，求R，r R ,s R ,t(R)的关系矩阵或关系图

6、命题公式 P∧Q ∨ −P ∧(−Q)的真值表

7、写出群(N13− 0,⨂13)各元素之阶数

8、集合A={1,2,3,6,8,12}，求A 上的整除关系R并画出Hae图

9、写出（（a−4b）c−（7b+d））+（c+8a）的前缀式和后缀式

10、求（N6,⨂6）群的自同态

五、证明题

1、证明（N13− 0，⨂13）是循环群

2、证明不存在含有奇数个面且每个面上有奇数个棱的多面体

3、设（A,∗）是代数系统，R是（A,∗）上的同余关系，(A R,∗)是其商代数，设f是A到A/R的函数，对于A中任意元素a，都有f a = a R

证明：f是（A,∗）到(A R,∗)的同态映射

4、设T是完全k元树，若分枝点为i，树叶数为t，证明：i=(t−1)/(k−1)

5、证明偶数阶群必有二阶子群，且必有奇数个二阶子群

6、R是集合A上的等价关系，证明：对任意x，y属于A在此处键入公式。

（1）若xRy，则 x R= y R

（2）若(x,y)∉R，则 x R∩ x R=∅

7、证明下列说法是等价的（1）A≤B（2）A−B=∅（3）A∩B=A（4）A∪B=B8、证明逻辑等价式P↔Q⟺ P⋀Q ⋁(−P⋀−Q)

9、证明10阶群必有5阶子群