离散数学复习与思考1

第一篇绪论内容：（三句话）典型题例：2、要解决一个问题，首先要证明此问题解的，还需要找出得到此问题的步骤来，而且其步骤必须是，有规则的，这就是所谓“能行性”问题的研究。第二篇集合论内容：典型题例：1、设A、B是任意集合，命题A-B=。A、BAB、BAC、ABD、不能判定3、设a是集合A的元素，则以下正确的是。A、}{aaB、Aa}{C、AaD、Ba}{7、设R是非空集合A上的关系，Q是A上的恒等关系，如果QR，则R不具有关系的性质。A、自反性B、对称性C、非对称性D、传递性9、设集合2,1X上的二元关系)2,2(),1,1(R，则R。A、是等价关系但不是偏序关系B、是偏序关系不是等价关系C、既是等价关系又是偏序关系D、既不是等价关系也不是偏序关系A、8B、16C、32D、6411、设R是实数集，函数43)(,:xxfRRf，则f是A、单射B、满射C、双射D、都不是12、设函数2)(,:,12)(,:rrgRRgrrfRRf，则有反函数。A、fgB、gfC、fD、g13、A，B是无限集，则一定是无限集。A、BAB、BAC、BAD、BA14、如果9,7,5,3,1A，10,8,3,1B，则：BA，BA，A+B=。15、A，B，C为任意三集合，则CBACBA)()(。16、}{，}}{,{a。17、设}{,baA，则)(A。19、集合24,12,8,6,3,2A，R是定义在A上的整除关系，则A的最大元是，最小元是，极小元是。21、对于一个等价关系)4,4(),2,4(),3,3(),1,3(),4,2(),2,2(),3,1(),1,1(R，则它对应的等价类为。22、凡与自然数集等势的集合都是可列集，那么整数集Z是，实数集R是。25、关系R具有自反性，则它所对应的关系图具有的特性，它所对应的关系矩阵有的特性。27、设A，B为有限集，且nBmA,，那么A与B间存在双射，当且仅当。29、证明题设A，B，C为任意三个集合，试证明：)()()(CBCACBA。31、计算题1、设集合aA,，3,2,1B，C，求：CBABAAA,,)(。3、设集合4,3,2,1A，A上二元关系2),(abbaR，2/1),(ababbaS或，求（1）复合关系RSSR,，（2）求SR的逆关系的关系矩阵。6、设fedcbaS,,,,,，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）的最大(小)元，极大（小）元。第三篇代数系统内容：典型题例：3、下面的代数系统（G，*）中，*是普通加法运算，则不是群。A、G为有理数集合B、G为整数集合C、G为实数集合D、G为自然数集合5、设G是群，若G中有个元素，则不能肯定G是可换集。A、1B、2C、3D、69、在群88,Z中，其单位元为，[2]的逆元素为，而[2]的周期为。11、分析题P966.112、计算题：1、求),(1212Z中子群H={[0]，[3]，[6]，[9]}的左、右陪集，并问左、右陪集是否相等？。2、P11326第四篇图论内容：典型题例：3、设连通图G=V,E，其中mEnV,，则要删去G中条边，才能确定G的一棵生成树。A、n-m-1B、n-m+1C、m-n+1D、m-n-15、一个有向（n,m）图中任何基本通路长度均小于或等于，而任何基本回路长度均小于或等于。6、在图G=＜V，E＞中，结点次数与边数的关系是。7、在有向图的邻接矩阵nnijaA)(中，第i行元素之和为，而3AB中的任一个元素ijb代表的含义为。10、设无向图G=V,E,其中)},,(),,(),,(),,(),,(),,(),,(),,(),,(),,{(},,,,,,,,{gfhdhcgcdcgbfbebeabaEhgfedcbaV试求：（1）a到h所有基本通路；（2）（2）从a到h的所有简单通路；（3）从a到h的距离。第五篇数理逻辑内容：典型题例：1、设命题公式G=)(PPP，则G的类型是。A、恒真的B、恒假的C、可满足的D、合取范式4、设命题公式PQPG)(，则G是。A、恒真的B、恒假的C、可满足的D、析取范式5、下列命题中，是重言式。A、)()(PQQPB、PQP)(C、)(QPD、)()(QPQP6、公式),()(yxyQxxP的前束范式为。A、)),()((yuQxPyxB、)),()((yuQxPyxC、)),()((yuQxPyxD、)),()((yuQxPyx10、设A，B为任意集合，命题BABA的真值是。11、若命题变元P，Q，R，的一个指派为（T，F，T），则命题公式)())((QPRQPG的真值是。12、设P：天下雪，Q：我去市里，R：我有时间，则命题“如果天不下雪，我有时间，那么我就去市里”符号化为。14、试求公式)()(RPQP的特异析取范式和特异合取范式。17、证明：)()()))(((RPQRQQP。