北京大学2012秋离散数学课件作业

2012秋离散数学课件作业第一部分集合论第一章集合的基本概念和运算1-1设集合A={{1，2}，a，4，3}，下面命题为真是（选择题）[C]A．2∈A；B．1∈A；C．3∈A；D．{1，2}A。1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D]A．C；B．A；C．B；D．Ø。1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题）（1）NQ，Q∈S，则NS，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］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，……}所以选[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是正整数集合上的关系，即R={〈x，y〉│x，y∈Z+且x+3y=12}，（选择题）试给出dom（R。R）。[B]A.3；B.{3}；C.〈3，3〉；D.{〈3，3〉}。2-3判断下列映射f：A→B中的双射函数。（选择题）[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.（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｝。2-5设A={1，2，3}，则商集A/IA=[D]A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]A．x+1；B．x-1；C．x；D．x2。第三章结构代数(群论初步)(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}，二元运算*是普通乘法。（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︱..3-3设Z为整数集合，在Z上定义二元运算。，对于所有x，y∈Z都有x。y=x-y试问〈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个偶数度顶点。[C]A．r=10；B．r=6；C．r=4；D．r=9。4-2无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有几个顶点.[8个顶点]4-31条边的图G中，所有顶点的度数之和为2。第五章树（5-1），（5-2）为计算题5-1握手定理的应用（指无向树）（1）在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，全树几个顶点[11]（2）一棵树有两个4度顶点，3个3度顶点，其余都是树叶，问有几片叶[9]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。问：权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}[非]5-511阶无向连通图G中有17条边，其任一棵生成树T中必有6条树枝[非]5-6二元正则树有奇数个顶点。[是]5-7通信中a，b，c，d，e，f,g,h出现的频率分别为35%;20%;15%.10%,10%,5%,3%,2%;求传输他们的最佳前缀码。（综合题）1、最优二元树T；2、二元树的权W（T）；3、每个字母的码字；答：。a。100。4060。。b15。30。。2010。。f。。。。ghde7.3..42..2..2..1..1111编码如下：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）今天没有下雨，也没有太阳，是阴天。（是复合）命题6-2将下列命题符号化.（填空题）（1）2是偶素数。p∧q（2）小李不是不聪明，而是不好学。p∧﹃q（3）明天考试英语或考数学。（兼容或）p∨q6-3求下列命题公式的主析取范式，并由此指出该公式的类型（等值演算）（1）﹃（p→q）∧q=0，永假式。（2）（（p→q）∧p）→q=Σ（0，1，2，3），永真式。（3）（p→q）∧q=Σ（1，3），可满足式。6-4令p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p．6-5p：天气好；q：我去游玩．命题”如果天气好，则我去游玩”符号化为［A］A．p→q；B．q→p；C．p∧q；D．﹁q→p6-6将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题）如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：方法1：等值演算法（（p→﹃q）∧p）→﹃q﹤＝﹥1；方法2:主范式法(略);方法3:真值表法(略);方法4：构造证明法,如下:将公式分成前提及结论。前提：（p→﹃q），p；结论：﹃q；证明：（1）（p→﹃q）前提引入（2）p前提引入（3）（p→﹃q）∧p（1）（2）假言推理（4）﹃q扣题：要证明的结论与证明结果一致，所以推理正确。第七章谓词逻辑7-1在谓词逻辑中用0元谓词将下列命题符号化（填空题）（1）这台机器不能用。﹃F（a）。（2）如果2＞3，则2＞5。L（a，b）→H（a，z）。7-2设域为整数集合Ｚ＋，命题xy彐z（x-y=z）的真值为1(填空题）7-3在谓词逻辑中将下列命题符号化（填空题）人固有一死。x（M（x）→F（x））。《附录》习题符号集Ø空集,∪并,∩交,⊕对称差,～绝对补,∑累加或主析取范式表达式缩写,－普通减法,÷普通除法,㏑自然对数,㏒对数，﹃非，量词”所有”，”每个”，∨析取联结词，∧合取联结词，彐量词”存在”，”有的”。2012年8月1号.