2013年秋离散数学作业题

离散数学作业题第一章 命题逻辑 p38 习题一 1、2（1）（3）、3（1）（4）、4（2）（3）、6（2）、7（4）（6）、8（1）（3）（5）补充题：将PQ化成与之等价的并仅含联结词的公式。第二章 谓词逻辑P70 习题二 2（2）（4）、3（1）（3）、4（3）（4）、10（4）补充题：1. 谓词符号化：1) 所有的鱼都生活在水中。2) 没有大于2的偶素数。3) 并不是每个人都聪明。2. 设个体域D=a,b，将一阶公式(x)(F(x)($y)G(y)中的量词消除3. 设个体域为整数集，令P(x,y)：x+y=1；Q(x,y)：xy0，试求解下列命题的真假。1) (x) ($y)P(x,y). 2) ($x) (y)Q(x,y). 4. 求前束范式：1) ($x)F(x)(x)R(x). 2) (x)P(x)($y)Q(y)(x)R(x). 5. 证明：前提：(x)(A(x) B(x)C(x)，($x)(A(x)D(x)结论：($x)(C(x)D(x) 6. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。写出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程) 第三章 集合、关系与映射P133 习题三：7、9、11、17补充题1. AB，AB能否同时成立，说明原因 求集合Aa，a的幂集 2. 证明：若BC，则P(B) P(C)3. 如果AB=AC，是否有B=C？ 如果AB=AC，是否有B=C？ 4. 试求1到10000之间不能被4，5或6整除的整数个数.5. 列出所有从A=a,b,c到B=s的关系，并指出集合A上的恒等关系和从A到B的全域关系.5. 给出A上的关系及其关系图和矩阵表示.|0x-y3 A=0，1，2，3，4 6. 已知S=a,b. R =x,y|x,yAxyA为集合族(S).试写出关系R.7. 已知： A=a,b,c, R=a,b,a,c,b,c该关系具有什么性质？ (自反，反自反，对称，反对称，传递性)8. 设A=a,b,c,R=a,b,a,c 计算：r(R)，sr(R)，tr(R)，str(R).9. 设A是含有4个元素的集合，试求： (1)在A上可以定义多少种对称关系？ (2)在A上可以定义多少种既是自反的，又是对称的关系？(3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系？10. 设集合A=0，1，2，3，4. R=|x+y=4,x,yA ，S=|y-x=1,x,yA. 试求：RS，RR，(RS)R，R(SR).11. 证明：R是A上的传递关系RRR.12. A=1,2,3,4,5,R=|x,yAx-y可被2整除，试问R是否是A上的等价关系？如果是，求出R的各等价类.13. A=1,2,3,4,5,A上的划分=1,2,3,4,5，给出由所诱导出的A上的等价关系R的集合表达式.14. 试给出一个单射但非满射的函数.(对某一集合而言)15. 设f：NNN，f(n)=,则： (1)说明f是否为单射和满射，并说明理由. (2) f的反函数是否存在？并说明理由. (3)求ranf. 16. 已知如果从无限集合A到集合B存在单射f，则B也是无限集合。设X是无限集合，集合Y，证明：X与Y的笛卡儿积XY是无限集合。 第六章 代数结构P247 习题六：4（1）（3）、6、16、21补充题：1. 以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有可逆元素的逆元.1) P(B)关于对称差运算，其中P(B)为幂集. 2) A=a,b,c，*运算如下表所示：2. 设集合A=a,b，那么（1）在A上可以定义多少不同的二元运算？（2）在A上可以定义多少不同的具有交换律的二元运算？3. 设A=1,2,B是A上的等价关系的集合.1) 列出B的元素. 2) 给出代数系统V=的运算表.3) 求出V的幺元、零元和所有可逆元素的逆元. 4) 说明V是否为半群、独异点和群？ 4. 设A=a,b,c，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律.1) 给出关于*运算的一个运算表.其中表中？位置可以是a、b、c。2) *运算是否满足结合律，为什么？5. 设是一个代数系统。*是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+ab(和+为数集上的乘法和加法). 证明：: 是独异点.6. 如果是半群，且*是可交换的. 证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b. 7. 设是一个群,则a,b,cS。 试证明： 群G中具有消去律,即成立: 如果ab=ac ,ba=ca 那么b=c.8. 设是群，aG . 现定义一种新的二元运算：xy=x*a*y，x,yG . 证明：也是群 . 9. 试写出模6加法群的每个子群及其相应的左陪集. 的运算表如下所示： 10. 设A=1,2,5,10,11,22,55,110.1) A关于整除关系是否构成偏序集？ 2) 如果构成偏序集合，画出其对应的哈斯图.3) 如果构成偏序集，该偏序集合构成哪种格？ (分配格、有界格、有补格、布尔格).第七题 图论P295 习题七：2、9、10补充题：1. 是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.2. 求下图的补图3. 1）试画一个具有5个顶点的自补图 2） 是否存在具有6个顶点的自补图，试说明理由。4. 设图G为n(n2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.5. 无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。6. 图G如下图所示：1) 写出上图的一个生成子图.（不唯一）2) (G)，(G)，(G). 3) 说明：(G)=min d(v) | vV ；(G)=min |V| |V是图G的点割集 ； (G)=min |E| |E是图G的边割集7. 在什么条件下无向完全图Kn为欧拉图？ 8. 证明：有割边的图不是欧拉图.9. 证明：有割