离散数学复习题

离散数学复习题一、填空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、有序对x,y具有以下性质（1）当x不等于y时，x,y≠y,x（2）x,y=u,r的充要条件是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上的一个二元关系，若R满足自反性、反对称性、可传递性则称R是偏序关系。16、设集合A={1,2,3,4}，A上二元关系R={1,11,32,13,33,44,3}，则逆序关系R−1={1,13,11,23,34,33,4}。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⨁B=A⨁B2、偶数阶循环群有且只有一个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并画出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，都有f(a)=|a|R证明：f是（A,∗）到(AR⁄,∗)的同态映射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阶子群