离散数学复习题

1、离散数学复习题一 、填空1、 命题中的否定联接词 ；析取联接词 ；蕴含联接词 。2、 一个命题公式，若在所有赋值下取值为真，则称此公式为 永真 式；若假，则.为 永假 式；若至少存在一组赋值，其命题为真，则.为可满足 式。3、 有限布尔代数只能有 2n 个元素。4、 R是定义在集合上的二元关系，若R满足 自反 性、 对称 性、传递 性，则称R是A上的等价关系。5、 全序集（A，）必是 偏序集 ，且是 链 。6、 n阶m条边无向图G是树，当且仅当G是连通点，且m= n-1 。7、 若有向树G中，有一个顶点的入度为 0 ，其余点的入度均 1 ，则称G为根树。8、 有序对具有以下性质（1）当x不等于

2、y时， （2）=的充要条件是x= u 且y= r 。9、关系的性质五 自反 、 反自反 、 对称 、 反对称 、 传递 。10、图中顶点作为边的端点的 条数 称为此顶点的度数。11、设X是格，并对交运算时可分配的，则 格中的并运算对交运算是可分配的 且 格中的交运算对并运算是可分配的 。12、有向图按连通图分为三类 强 连通图、 单向 连通图、 弱 连通图。13、T 为一颗根树，若T的每个分支点 的儿子数都为r ，则称T为r元正则树。14、设A、B是集合，求A与B之间关系（属于、不属于、包含）如果A=1，B=1,1,2，则A 不属于 B、A 不包含 B15、若R是定义在集合A上的一个二元关系，

3、若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

4、、集合的基本运算公式（集代数公式）有哪些？8、群论中的拉格朗日定理9、主析取范式与主合取范式10、鸽巢原理与计数原理三 、判断题1、 设A,B是集合，则AB=AB2、 偶数阶循环群有且只有一个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（QR）

5、主析取范式。2、 写出3次对称群（S3,*）的运算表及所有正规子群。3、 在1,2,3.100这100个自然数中，可以被2或3整除但不能被5整除的数有多少个？4、 设,A=3，PB=64，PAB=256，求B,AB,A-B,AB。5、 设A=a,b,c,d，R=（a,c）,（c,b）,（b,a）,（a,d），求R，rR,sR,t(R)的关系矩阵或关系图6、 命题公式PQ-P(-Q)的真值表7、 写出群(N13-0,13)各元素之阶数8、 集合A=1,2,3,6,8,12，求A 上的整除关系R并画出Hasse图9、 写出（a-4b）c-（7b+d）+（c+8a）的前缀式和后缀式10、 求（N6,6）群的自同态五 、 证明题1、 证明（N13-0，13）是循环群2、 证明不存在含有奇数个面且每个面上有奇数个棱的多面体3、 设（A,*）是代数系统，R是（A,*）上的同余关系，(AR,*)是其商代数，设f是A到A/R的函数，对于A中任意元素a，都有fa=aR证明：f是（A,*）到(AR,*)的同态映射4、 设T是完全k元树，若分枝点为i，树叶数为t，证明：i=(t-1)/(k-1)5、 证明偶数阶群必有二阶子群，且必有奇数个二阶子群6、 R是集合A上的等价关系，证明：对任意x，y属于A在此处键入公式。（1） 若xRy，则xR=yR（2