离散数学课件作业.doc

离散数学课件作业 第一部分 集合论第一章 集合的基本概念和运算 1-1 设集合 A =1，2，a，4，3，下面命题为真是 A2 A； B1 A； C5 A； D2 A。1-2 A,B为任意集合，则他们的共同子集是 AA； BB； CAB； D 。 1-3 设 S = N，Z，Q，R，判断下列命题是否成立 ？（1） N Q，Q S，则 N S （2）-1 Z，Z S， 则 -1 S 1-4 设集合 A =3，4，B = 4，3 ， C = 4，3 ，D = 3，4， ，E = xx R 并且 x2 - 7x + 12 = 0，F = 4， ，3，3，试问哪两个集合之间可用等号表示 ？1-5 用列元法表示下列集合（1）A = xx N 且 x2 9 （2）A = xx N 且 3x 3 第二章 二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = x，yx，y X 且 x y 求：(1)domR =?; (2)ranR =?; (3)R 的性质。2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = x，yx，y Z+ 且 x + 3y = 12，试求：（1）R 的列元表达式； （2）给出 dom（R 。R）。 2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：AB 指出他的性质，即是否单射、满射和双射，并说明为什么。 （1）A = 1，2，3，B = 4，5， f = 1，42，43，5。（2）A = 1，2，3 = B， f = 1，12，23，3。（3）A = B = R， f = x 。（4）A = B = N， f = x2 。（5）A = B = N， f = x + 1 。2-4 设 A =1，2，3，4，A 上的二元关系 R =x，y（x-y）能被3整除，则自然映射 g：AA/R使 g(1) = A1,2； B1,3； C1,4； D1。2-5 设 A =1，2，3，则商集A/IA = A3； B2； C1； D1，2，3。2-6设(x)x+1，(x)x-1 都是从实数集合到的函数，则。 Ax+1； Bx-1； Cx； Dx2。 第三章 结构代数(群论初步)3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？（1）S1 = 1，1/4,1/3,1/2,2，3，4，二元运算 * 是普通乘法。（2）S2 = a1，a2，an，ai R，i = 1，2，n ；二元运算 。定义如下：对于所有 ai，aj S2，都有 ai 。aj = ai 。（3）S3 = 0，1，二元运算 * 是普通乘法。3-2 在自然数集合上，下列那种运算是可结合的 Ax*y = max(x,y) ； Bx*y = 2x+y ；Cx*y = x2+y2 ； Dx*y =x-y.3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x + y ，试问Z，。能否构成群，为什麽 ？ 第二部分 图论方法第四章 图 4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. 4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 第五章 树5-1 握手定理的应用（指无向树）（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个？（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片？5-2 一棵树中有 i 个顶点的度数为 i（i=2，k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1） T 的权 W（T）？ （2）树高几层 ？ 5-4 以下给出的符号串集合中，那些是前缀码？将结果填入 内. B1 = 0，10，110，1111 B2 = 1，01，001，000 B3 = a，b，c，aa，ac，aba，abb，abc B4 = 1，11，101，001，0011 5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 5-6(是非判断题)二元正则树有奇数个顶点。 5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%. 求传输他们的最佳前缀码。 1、最优二元树 T； 2.每个字母的码字；第三部分 逻辑推理理论第六章 命题逻辑 6-1 判断下列语句是否命题，简单命题或复合命题。（1）2月 17 号新学期开始。 （2）离散数学很重要。 （3）离散数学难学吗 ？ （4）C 语言具有高级语言的简洁性和汇编语言的灵活性。 （5）x + 5 大于 2 。 （6）今天没有下雨，也没有太阳，是阴天。 6-2 将下列命题符号化.（1）2 是偶素数。（2）小李不是不聪明，而是不好学。（3）明天考试英语或考数学。（兼容或）（4）你明天不去上海，就去北京。（排斥或）6-3 分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）（pq） q； （2）（pq） p）q； （3）（pq） q。以下两题(6-4;6-5)为选择题,将正确者填入 内.6-4 令 p：经一堑；q：长一智。命题只有经一堑，才能长一智符号化为 A pq； B qp； C pq； D qp6-5 p：天气好；q：我去游玩命题 ”如果天气好，则我去游玩” 符号化为 A pq； B qp； C pq； D qp6-6 证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。 第七章 谓词逻辑 7-1 在谓词逻辑中用 0 元谓词将下列命题符号化（1）这台机器不能用。（2）如果 2 3，则 2 5。7-2 填空补缺题：设域为整数集合，命题xy彐z（x-y=z）的真值为（）7-3 在谓词逻辑中将下列命题符号化（1）有的马比所有的