2012—离散数学作业答案

2012春课件作业题解分析与答案第一部分集合论第一章集合的基本概念和运算1-1设集合A={{1，2}，a，4，3}，下面命题为真是（选择题）[C]A．2∈A；B．1∈A；C．3∈A；D．{1，2}A。题解与分析：A是集合，2，5不是他的元素。所以，（A）,(C)无可争议的是错误。然而，某集合若是另一集合子集，则子集也可以成为集合的元素，二者从而产生隶属关系,例如，本题的集合A与集合{2}。而Ｄ说{2}是A的子集而不是元素,就是错误的了．所以，只有（B）为正确。1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D]A．C；B．A；C．B；D．Ø。题解与分析：因为A，B，C均为任意集合，当然可以是Ø，所以，结果只能选D.因为Ø的子集合可以是Ø。1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题）（1）NQ，Q∈S，则NS，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］题解与分析：S实际上是实数集合R，自然数集合N，有理数集合Q的集合，诸如“NS”，“-1∈S”之类的命题都是错误的。所以，(1）,(2)都错。1-4设集合B={4，3}∩Ø，C={4，3}∩{Ø}，D={3，4，Ø}，E={x│x∈R并且x2-7x+12=0}，F={4，Ø，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A]题解与分析：A.C;B.D;C.E;D.F.1-5用列元法表示下列集合A={x│x∈N且3－x〈3}（选择题）题解与分析：本题以谓词给出集合的表达式。要求把解析表达式所含的元素列出；有的集合的元素需要通过计算才能得到，如下：（选择题）A={1，2，3，4，……}=Z+；所以选[D]A.N;B.Z;C.Q;D.Z+第二章二元关系2-1给定X=（3,2，1），R是X上的二元关系，其表达式如下：R={〈x，y〉x，y∈X且x≤y}（综合题）求：(1)domR=?;(2)ranR=?;(3)R的性质。题解与分析：所谓谓词表达法，即是将集合中所有元素的共同性质用一个谓词概括起来，如本题几例所示。有的书上称其为抽象原则。反过来，列元法则是遵照元素的性质和要求，逐一将他们列出来，以备下用,结果如下：R={2，3，1,2，1,3}∪Ix；(1)DomR={R中所有有序对的x}={3,2,1};(2)RanR={R中所有有序对的y}={3,2,1}；(3)R的性质:自反,反对称,传递性质.2-2设R是正整数集合上的关系，由方程x+3y=12决定，即R={〈x，y〉│x，y∈Z+且x+3y=12}，试给出dom（R。R）。（选择题）题解与分析：在求解关系的诸问题时，较好的办法是列出关系的每个有序对，以及解决其他问题。根据方程式有：y=4-x/3，x只能取3，6,9。结果如下：因为有R={〈3，3〉,〈6，2〉,〈9，1〉}；且有R。R={3,3}.然后,给出R。R的定义域,即dom（R。R）={3}。所以选[B]A.3；B.{3}；C.〈3，3〉；D.{〈3，3〉}。2-3判断下列映射f是否是A到B的函数；并指出f：A→B中的双射函数。（1）A={1，2，3}，B={4，5}，f={〈1，4〉〈2，4〉〈3，5〉}。（2）A={1，2，3}=B，f={〈1，1〉〈2，2〉〈3，3〉}。（3）A=B=R，f=x。（4）A=B=N，f=x2。（5）A=B=N，f=x+1。分析与题解：判断映射的性质，要分三步考虑：第一，是否函数？第二，是否A到B的函数？第三，是否单射、满射,双射。（选择题）（1）是A到B的函数，是满射而不是单射；（2）是双射；（3）是双射；（4）是单射，而不是满射；（5）是单射而不是满射。所以选[B]A.（1）和（2）；B.（2）和（3）；C.（3）和（4）；D.（4）和（5）2-4设A={1，2，3，4}，A上的二元关系R={〈x，y〉︱（x-y）能被3整除}，则自然映射g：A→A/R使g(1)=[C]A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。分析与题解：大家明白，在本题条件下，只有0和3才能被3整除，这样一来，在关系Ｒ中，必有1,1,4,1两个有序对出现，就是说，自然映射g：A→A/R使g(1)=［1］＝｛1,4｝．2-5设A={1，2，3}，则商集A/IA=[D]A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。分析与题解：记住商集的元素是等价类．而各元素的等价类分别为[1]＝{1}，[2]＝{2}，[3]＝{3}．所以有A/IA＝Ｄ．2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]A．x+1；B．x-1；C．x；D．x2。分析与题解：函数的合成运算很简单．即将g(x)做为一个整体代入到f(x)的x处即可．本题为：f(g(x))=((x-1)+1)=x.第三章结构代数(群论初步)(3-1)，(3-2)为选择题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}，二元运算*是普通乘法。分析与题解：一个代数系统，通常由三个条件构成。第一，要有一个集合；第二，要有若干个n元运算；第三，n元运算在集合内自我封闭。所以，我们的结论应是：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。所以选[A]A．不构成代数系统；B．只是代数系统。；C．半群；D．群。（2）由二元运算的定义不难知道，。在S2内是封闭的，所以，〈S2，。〉构成代数系统；然后看该代数系统的类型：该代数系统只是半群。所以选[C]A．不能构成代数系统；B．只是代数系统；C．半群；D．群。（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异点；而0为零元；结论：仅为独异点，而不是群。所以选[C]A．不能构成代数系统；B．半群；C．独异点；D．群。3-2在自然数集合上，下列那种运算是可结合的［A］A．x*y=max(x,y)；B．x*y=2x+y；C．x*y=x2+y2；D．x*y=︱x-y︱..分析与题解：结合律的验证很简单．然而，没有窍门．只有在（x*y）*z=x*(y*z)时，才可以得出满足结合律的结论．3-3设Z为整数集合，在Z上定义二元运算。，对于所有x，y∈Z都有x。y=x+y-4，试问〈Z，。〉能否构成群，为什麽？（综合题）分析与题解：判别一个代数系统是否是群，当然要满足群的定义条件。然而，判别过程要分步走。因为题中以代数系统形式给出，第一步封闭性问题判断可省去.之所以说该步骤可以略去,是在题中已经告知代数系统成立的前提下.否则要进行讨论:此二元运算中,只有加法,在集合Z中必然满足封闭性；第二步，二元运算满足结合律，以决定半群；第三步，有幺元为4，为独异点.必须记住,求特殊元素时,都要解联立方程.假设代数系统的幺元是集合中的元素e,则一个方程来自于二元运算定义,即e。x=e+x-4，一个方程来自该特殊元素的定义的性质,即e。x=x.由此而来的两个方程联立结果就有:e+x=x成立.削去x,e=4的结果不是就有了吗!；第四步，每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理：设y是x的逆，则一个方程为y。x=y+x-4,另一个方程为y。x=4,联立结果得到y=8-x；第五步，结论是：代数系统〈Z，。〉构成群。第二部分图论方法第四章图4-110个顶点的简单图G中有4个奇度顶点，问G的补图中有r个偶数度顶点。题解分析：提到图的补图，必须首先想到完全图.因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图G的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有相同数个偶数度顶点。所以选[C]A．r=10；B．r=6；C．r=4；D．r=9。4-2是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点.[是]分析与题解：由握手定理有：20＝4x3＋2ｘ，所以，x＝4，即4个2度顶点，共8个顶点．4-3填空补缺：1条边的图G中，所有顶点的度数之和为2。分析与题解：握手定理是普适定理．任何无向图中，所有顶点的度数之和都是边的两倍．第五章树（5-1），（5-2）为计算题5-1握手定理的应用（指无向树）（1）在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，共几个顶点[11]（2）一棵树有两个4度顶点，3个3度顶点，其余都是树叶，问有几片叶[9]题解分析：对于图论中树的有关问题的解决，无非是利用握手定理以及利用树是连续而无回路的性质，即Σd（Vi）=2m定理和利用n—1=m定理。所以有如下结果：（1）有1个4度顶点。即：1+7+3=11；（2）9个1度顶点。5-2一棵树中有i个顶点的度数为i（=2，…k），其余顶点都是树叶，问树叶多少片？题解分析：假设有x片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数x=Σi（i—2）i+2，（i=2，3，……k）。5-3求最优2元树：用Huffman算法求带权为1，2，3，5，7，8的最优2元树T。试问：T的权W（T）=(61)；树高(4)层。（填空题）题解分析：用Huffman算法，以1，2，3，5，7，8为权，最优2元树T；然后，计算并回答所求问题：T的权W（T）=61；树高几层：4层树高。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}[非]题解分析：根据前缀码的定义，判断B1，B2是前缀码，而B3，B4不是。5-511阶无向连通图G中有17条边，其任一棵生成树T中必有6条树枝[非]题解分析：ｎ阶无向连通图G的任一棵生成树T中必有ｎ－１条树枝，而与边数无关．Ｔ所对应的基本回路数才与边数有关系．务必注意此点！！！5-6二元正则树有奇数个顶点。[是]题解分析：在书中第页，正则条件是：s=(t-1)/(r-1)．当ｒ＝２时，分母消失，便有ｓ（＝ｎ－ｔ）＝ｔ－！，得到ｎ＝2ｔ-1，由此可判断顶点数为奇数．5-7通信中a，b，c，d，e，f,g,h出现的频率分别为30%;20%;15%.10%,10%,5%,5%,5%;求传输他们的最佳前缀码。（综合题）1、最优二元树T；2、二元树的权W（T）=275；3、每个字母的码字；。10060。30。。a。4015。。c10。。。20。b。。f。。ghde编码如下：g（00000），h（00001），f（0001），d（100），e（101）,c(001),b(11),a(01)。第三部分逻辑推理理论第六章命题逻辑6-1判断下列语句是否命题，简单命题或复合命题。（填空题）（1）2月17号新学期开始。（是简单）命题（2）离散数学很重要。（是简单）命题（3）离散数学难学吗？（不是）命题（4）C语言具有高级语言的简洁性和汇编语言的灵活性。（是复合）命题（5）x+52。（不是）命题（6）今天没有下雨，也没有太阳，是阴天。（是复合）命题题解与分析：该习题要求了解命题的概念。命题必须是具有确切结果的陈述句。若一个陈述句不能拆成两个以上的陈述句，则这个陈述句所构成的命题叫做简单命题或原子命题。自然，原子命题是一切复杂命题的组成单元。根据此原理判断：（1），（2），（4），（6）是命题；其中（4），（6）是复合命题。6-2将下列命题符号化.（填空题）（1）2是偶素数。（2）小李不是不聪明，而是不好学。（3）明天考试英语或考数学。（兼容或）题解与分析：命题的符号化必须把握住一个概念：一个符号不能对一个复合命题符号化，而只能对一个简单命题符号化。而复合命题的符