离散数学习题.doc

第一篇 绪论内容：（三句话）典型题例：1、离散数学是计算机科学所涉及的 和 的总称。2、离散数学是数学中的一个分支，它以 作为其主要研究对象，非常重视 问题的研究。3、要解决一个问题，首先要证明此问题解的 ，还需要找出得到此问题的步骤来，而且其步骤必须是 ，有规则的，这就是所谓“能行性”问题的研究。第二篇 集合论内容：典型题例：1、设集合，那么下列命题中正确的是 。A、 B、 C、 D、2、设A，B是集合，如果，则 。A、 B、 C、 D、3、设集合，那么下列命题中错误的是。A、 B、 C、 D、4、设集合，,则 。A、 B、 C、 D、5、设，那么集合A，B的对称差A+B= 。A、 B、 C、 D、6、集合，X上的一个划分，那么所对应的等价关系R应有有 个序偶。A、8 B、9 C、10 D、137、设集合上的二元关系，则R不具有。A、传递性 B、自反性 C、对称性 D、反对称性8、设集合，X上的关系，则R具有 。A、自反性 B、非自反性 C、对称性 D、传递性9、设集合，A上的二元关系，则关系。A、 B、 C、 D、10、设集合，和都是X上的二元关系，其中，则。A、 B、 C、 D、11、，那么可以定义 种不同的从A到B的映射。A、8 B、16 C、32 D、6412、设R是实数集，函数，则f是。A、单射 B、满射 C、双射 D、既不是单射，也不是满射13、设R是实数集，映射，则f是。A、单射 B、满射 C、双射 D、都不是14、设，集合的这种表示方法称为；Y=xx是正偶数，集合的这种表示方法称为。15、设全集 ，则：，A+B= 。16、A，B，C为 任意三集合，则 。17、 ， 。18、设，则 。19、设集合，R是A上的整除关系，则A的极大元是，极小元是。20、设集合，R是X上的整除关系，则X的极大元是，极小元是。21、对于一个关系R，它可能具有 、 、 、 、 等五种性质。22、对于一个等价关系，则它对应的等价类为 。23、设集合，A上的等价关系，则它所对应的等价类为 。24、设集合，A上的一个划分，那么所对应的等价关系R应有个序偶。25、凡与自然数集等势的集合都是可列集，那么整数集Z是 ，实数集R是 。26、一集合为无限集，则它必含有与其的真子集，在无限集中，最小的无限集是，其次是。27、集合A=a,b,c的幂集（A）上的“”关系是一个偏序关系，设B=a,b,b,c,b,c,，则B的极大元素为 ，极小元为 ，上确界为 ，下确界为 。28、设A，B为有限集，且，那么A与B间存在双射，当且仅当 。29、设集合，则从A到B的所有映射有个，其中满射有个。30、设集合，则从A到B的所有映射有个，其中双射有个。31、证明题设A，B，C为任意集合，试证明：。32、简答题 试解释偏序关系和等价关系的概念，并给出一个集合上的关系，使它既是偏序关系又是等价关系。33、设，并设是NN上的关系，其定义为：若ad=bc，则有（a,b）(c,d)，试证明：是一个等价关系。34、计算题1、 设集合，求：。2、 设集合，求：。3、 设集合，求：。4、设集合，A上二元关系，求（1）复合关系，（2）求R与的逆关系的关系矩阵。5、 集合，求，和。6、设集合，A的二元关系（1）画出偏序集（A，R）的哈斯图；（2）写出A的最大元、最小元；（3）判定偏序集（A，R）是不是格？元素b的补元素是什么？7、设，S上的偏序关系R=(a,a), (b,a), (b,b),(c,a),(c,c),(d,a),(d,b),(d,c),(d,d),(e,a),(e,c),(e,e),(f,f)。 （1）试画出偏序集（S，R）的哈斯图； （2）写出（S，R）的最大(小)元，极大（小）元。第三篇 代数系统内容：典型题例：1、下面的代数系统（G，*）中，不是群。A、G=Q，*是加法 B、G=Q，*是乘法C、，*是加法 D、，*是加法2、设G是含6个元素的循环群，a是生成元，则下列为G的子群的是。 A、 B、 C、 D、3、下面的代数系统（G，*）中，*是普通加法运算，则 不是群。A、G为有理数集合 B、G为整数集合C、G为实数集合 D、G为自然数集合4、设是环，是它的子代数，是的子环的充要条件是 。 A、 B、 C、 D、存在单位元5、下面的代数系统（G，*）中，不是群。A、G为n阶方阵的集合，*为矩阵乘法 B、G为有理数集合，*为加法C、G为整数集，*为加法 D、G为偶数集，*为加法6、一个群，而H是G的子集，那么是的子群的充要条件是。 A、 则 B、 则 C、则 D、存在单位元，存在逆元7、在群中，其单位元为 ，2的逆元素为 ，而2的周期为 。8、在群中，其单位元为 ，所有可能的子群为 。9、设集合上的两个变换与分别为：，则= 。10、集合上的两个变换与分别为，则= 。11、在群中，其单位元为，2的逆元素为，而2的周期为。12、集合上的两个变换与分别为，则=。13、设，二元运算*定义为a*b=min(a,b),那么在（A，*）中，单位元是，零元是。14、在群中，其单位元为，所有可能的子群为。15、分析题 1、设在有理数集Q上的有运算定义为：。 （1）是代数系统吗： （2）是半群吗？是可换半群吗？ （3）有单位元吗？单位元是什么？ （4）中每个元素有逆元素吗？任一元素的逆元素是什么？2、设Q为有理数集，在Q上定义集合，运算*是普通乘法。 （1）是代数系统吗? （2）是半群吗？是可换半群吗？ （3）有单位元吗？单位元是什么？ （4）中每个元素有逆元素吗？任一元素的逆元素是什么？3、设是正整数集，（即a,b的最小公倍数），试问：（1）是半群吗？（2）有单位元吗？单位元是什么？（3）是否每个元素都有逆元素？16、计算题：1、 求中子群H=0，3，6，9的左、右陪集，并问左、右陪集是否相等？。2、 找出的所有子群。14、试证若群（G，*）的每个元素的逆元素都是它自己，则该群必是可换群。第四篇 图论内容：典型题例：1、设G是由5个顶点组成的完全图，则从G中删去 条边可以得到树。A、10 B、5 C、4 D、 62、一有向图G=，其对应的邻接矩阵为，则对于，它的引入次数为 。A、 B、 C、 D、 3、设连通图G=，其中，则要删去G中 条边，才能确定G的一棵生成树。A、n-m-1 B、n-m+1 C、m-n+1 D、m-n-14、无向连通图G中结点间存在欧拉通路的充要条件是G中的次数均为 ，而其他结点的次数为 。5、一个有向（n, m）图中任何基本通路长度均小于或等于 ，而任何基本回路长度均小于或等于 。6、在图G=V，E中，结点次数与边数的关系是 。7、在有向图的邻接矩阵中，第i行元素之和为 ，而中的任一个元素代表的含义为 。8、D是具有结点的有向图，它的邻接矩阵表示如下： （1）D是单向连通的，还是强连通的？ （2）求从到，长度为3的通路数。9、设有向图D=V，E，其中V=a1,a2,a3,a4,a5，E=(a1,a2),(a2,a4),(a3,a1),(a4,a5),(a5,a2)，（1） 求D的邻接矩阵。（2）利用可达性矩阵判断其连通性。10、D是具有结点的有向图，它的邻接矩阵表示如下： （1）利用可达性矩阵的特性，判断D的连通性； （2）求从到，到，到长度是3的通路数。11、设，画出无向图G=，其中：，再求每个结点的次数。12、设，画出无向图G=，其中：，再求每个结点的次数。第五篇 数理逻辑内容：典型题例：1、设命题公式，则G是 。A、恒真的 B、恒假的 C、可满足的 D、合取范式2、设命题公式G=，则使G为真的解释是 。A、（F，F，F） B、（F，F，T） C、（F，T，F） D、（T，F，F）3、n个命题变元可以组成也只能组成 个不等的公式。A、 B、 C、 D、4、命题公式是。A、矛盾式 B、蕴含式 C、重言式 D、等价式5、下列命题中， 是重言式。A、 B、 C、 D、 6、设L(X)：x是演员，J(x)：x是教师，A（x,y）x佩服y，命题“所有演员都佩服某些教师”可符号化为。A、 B、C、 D、7、设A(X)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”可符号化为。A、 B、C、 D、8、设命题公式，则使G为真的解释是 。9、谓词演算的公理系统中，全称规则为： ；存在规则为 。10、语句“对所有x”称为全称量词，记作，语句“存在某些x”称为存在量词，记作。11、若命题变元P，