2014年秋离散数学作业题
第一篇：2014年秋离散数学作业题
离散数学作业题
第一章 命题逻辑
p38习题一1、2（1）（3）、3（1）（4）、4（2）（3）、6（2）、7（4）（6）、8（1）（3）（5）补充题：将P Q化成与之等价的并仅含联结词 的公式。
第二章 谓词逻辑
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)：xy>0，试求解下列命题的真假。
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.A B，A∈B能否同时成立，说明原因
求集合A＝{a，{a}}的幂集
2.证明：若B C，则P(B)  P(C)3.如果A∪B=A∪C，是否有B=C？
如果A⊕B=A⊕C，是否有B=C？
4.试求1到10000之间不能被4，5或6整除的整数个数.5.列出所有从A={a,b,c}到B={s}的关系，并指出集合A上的恒等关系和从A到B的全域关系.5.给出A上的关系及其关系图和矩阵表示.{|0≤x-y＜3} A={0，1，2，3，4}
6.已知S={a,b}.R  ={〈x,y〉|x,y∈A∧x y∧A为集合族ρ(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,y∈A}，S={|y-x=1,x,y∈A}.试求：R二叉树公式◦S，R◦R，(R◦S)◦R，R◦(S◦R).11.证明：R是A上的传递关系 R◦R R.12.A={1,2,3,4,5},R={|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系？如果是，求出R的各等价类.13.A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}}，给出由∏所诱导出的A上的等价关系R的集合表达式.14.试给出一个单射但非满射的函数.(对某一集合而言)15.设f：N→N×N，f(n)=,则：
(1)说明f是否为单射和满射，并说明理由.(2)f的反函数是否存在？并说明理由.(3)求ranf.16.已知如果从无限集合A到集合B存在单射f，则B也是无限集合。
设X是无限集合，集合Y≠φ，证明：X与Y的笛卡儿积X×Y是无限集合。
第六章 代数结构
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+a·b(·和+为数集上的乘法和加法).证明：: 是独异点.6.如果是半，且*是可交换的.证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b.7.设是一个,则 a,b,c∈S。
试证明： G中具有消去律,即成立: 如果a·b=a·c ,b·a=c·a 那么b=c.8.设是，a∈G.现定义一种新的二元运算⊙：x⊙y=x*a*y， x,y∈G.证明：也是.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(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.5.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。6.图G如下图所示：
1)写出上图的一个生成子图.（不唯一）2)δ(G)，κ(G)，λ(G).3)说明：δ(G)=min{ d(v)| v V } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 7.在什么条件下无向完全图Kn为欧拉图？
8.证明：有割边的图不是欧拉图.9.证明：有割边的图不是哈密尔顿图.10.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？ 11.给出全部互不同构的4阶简单无向图的平面图形。
12.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.
第二篇：离散数学作业题(截图)
华南理工大学网络教育学院 2014–2015学第一学期 《 离散数学 》作业（解答必须手写体上传，否则酌情扣分）
1．设命题公式为  Q  （P  Q）    P。
（1）求此命题公式的真值表；（2）求此命题公式的析取范式；（3）判断该命题公式的类型。
2．用直接证法证明
前提：P  Q，P  R，Q  S 结论：S  R
《 离散数学作业 》 第 1 页（共 7 页）
3．在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。
《 离散数学作业 》 第 2 页（共 7 页）
4．用直接证法证明：
前提：（ x）（C（x）→ W（x）∧R（x）），（ x）（C（x）∧Q（x））结论：（ x）（Q（x）∧R（x））。
《 离散数学作业 》 第 3 页（共 7 页）
5．设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。
(1)给出关系R；（2）给出COV A
（3）画出关系R的哈斯图；
（4）给出关系R的极大、极小元、最大、最小元。
《 离散数学作业 》 第 4 页（共 7 页）
6．求带权图G的最小生成树，并计算它的权值。
7．给定权为1，9，4，7，3；构造一颗最优二叉树。
《 离散数学作业 》 第 5 页（共 7 页）
8．给定权为2，6，3，9，4；构造一颗最优二叉树。
9、给定权为2，6，5，9，4，1；构造一颗最优二叉树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。