年月离散数学期末考试题(参考答案)

1上海海事大学试卷2011—2012学年第一学期期末考试《离散数学》（A卷）参考答案注：N={0,1,2,3,….}1.(7’)设：c:=我的计算是正确的;b:=我支付电费账单;r:=我花光所有的钱;p:=电源未被切断。(c,b,r,p)条件：(c∧b)→r,﹃b→﹃p.结论：(﹃r∧p)→﹃c证明：①(c∧b)→rP②﹃c∨﹃b∨rT①E③﹃b→﹃pP④b∨﹃pT③E⑤﹃c∨﹃p∨rT②④I⑥﹃r∧p附加前提⑦﹃rT⑥I⑧pT⑥I⑨﹃c∨﹃pT⑤⑦I⑩﹃cT⑧⑨I2.(5’)(a))]())()[((zxzyyxzyx;论域R；真值T。(b))]()[(nppmpnm；论域N；真值F。(c)][nmmn；论域N；真值F。3.(6’)(a)70(b)100(c)100≥CB=70+65-CB，所以CB≥35。(d)0。(e))()(CABA=)(CBA=CBACBA≥50+70-100=20，所以当BC时，最小值为20.4.(5’)(a)是。m≡m(mod3)或n≡n(mod5)一定成立，所以((m,n),(m,n))∈R(b)是。m≡p(mod3)或n≡q(mod5)蕴含着p≡m(mod3)或q≡n(mod5)成立.(c)否。反例如下：((0,0),(0,1))和((0,1),(1,1))属于R，但((0,0),(1,1))不--------------------------------------------------------------------------------------装订线------------------------------------------------------------------------------------2属于R。(d)否，因为传递性不满足。5.(5’)①设R是传递的，考虑(s,u)∈R2,由R2的定义，存在t∈S使得(s,t)∈R且(t,u)∈R。因为R时传递的，所以(s,u)∈R，故R2⊆R。②另一方面，设R2⊆R。考虑(s,t)∈R且(t,u)∈R.则(s,u)∈R2,所以(s,u)∈R，故R是传递的。6.(6’)R1是偏序关系，但不是格。偏序关系全部极大链如下：①{1,2,4}；②{1,2,6};③{1,3,6};④{1,5}.R3是等价关系。等价类为：[1]={1,3,5};[2]={2,4,6}7.(7’)(a)1000001010101000101000011;(b)0010000010100000101100010;(c)1010001010101000101100011;(d)1010001010101000101100011;(e)1010001011101000101101011;(f)[1]={1,2,4};[3]={3,5}.8.(5’)定义域是[0,2]，共域是[-4,0]；由于x≤2，所以04,42)(1yyyf。9.(6’)(a)四个函数都是满射的。(b)四个函数都不是单射的。(c))4(SUM有5个元素；)4(PROD有3个元素；)4(MAX有9个元素；)4(MIN有无穷多个元素。10.(5’)(a)假定S是无穷集合（有限集合已经是可数的）。设f:S→T是一个一一对应，其中T是可数的。由于T是可数的，所以T与正整数集合P之间存在一一对应g:T→P。于是PSfg:也是一一对应的，故S是可数的。(b)设f:S→T是一个一一对应，其中T是不可数的。由于T是不可数的，所以T与实数集合R之间存在一一对应g:T→R。于是RSfg:也是一一对应的，故S是不可数的。【也可用反证法证明】※在下面的两题111和112中任意选作一题111.(8’)(选作1)(a)因为是双射的，所以1-也是双射的。对任意u,v∈B2,设)(),(1-1-vyux,则)()())(())()(()(1-1-1-1-1-vuyxyxyxvu，3同理可证：)()()(1-1-1-vuvu。同时，)())(())(()(1-1-1-1-uxxxu。证毕(b)设12，因为12和是双射的，所以它们的复合函数也是是双射的。用与(a)类似的方法证明)()()()()()()()(xxyxyxyxyx，，(c))()()()()()()(yxyyxyyxyyxyx(d)①设a是B1的原子，则B1中的a≠0,因为是单射的，所以B2中的)(a≠0。假设)(a不是原子，则存在z∈B2使)(0az。由于1-是一个布尔代数同构，则根据(c)部分序关系保持的性质可得，azaz)(0)),(()()0(1-1-1-1-即，与a是B1的原子矛盾。②设)(a是B2中的原子，由上面已证的(a)和①可得，aa))((1-是B1的原子。112(8’)(选作2)(a)+6012345001234511234502234501334501244501235501234*6012345000000010123452024024303030340420425054321(b)(Z6,+6)是交换群，当然也是半群，是独异点。其中幺元是0，逆元可从表中读出。(c)),(66Z是满足交换性的独异点，当然也是半群，但不是群。独异点的幺元是1，但一些元素比如0没有逆元。(d)),}0{\(66Z甚至连半群都不是，因为它在乘法运算下不封闭。例如2,3是4}0{\6Z的元素，但2*3=0不属于}0{\6Z。(b)(Z6,+6)的所有生成元是1和5。(b)(Z6,+6)的所有子群如下：0,1=5=Z6,2=4,3。12.(8’)(a)（1,0,0,0）∨（0,0,0,1）。(b)（1,0,0）∨（0,0,1）(c)（0,0,1,0,0）∨(0,0,0,1,0)。(d){1}∨{3}.(e)xyzzyxzyxzyx，其中乘积表示”∧”。※在下面的两题131和132中任意选作一题131.(5’)(选作1)(a)5658C(b)1+6+6×5=37(c)8×7+8×7×6+8×7×6×6=2408132.(5’)(选作2)(a)这个半群是独异点，其幺元是恒等关系{(s,s)|s∈S}(b))(SS满足交换的充要条件是|S|=1。因为如果x,y∈S，且x≠y，设R1={(x,y)}，R2={(y,x)}，则R1R2={(x,x)}≠{(y,y)}=R2R114.(5’)(a)(b)用归纳法证。n=2时，2n-2=2，取d1=1，d2=1，此时这颗只有一条边的树就是符合要求的树。设n=k时命题成立，即各定点度数和d1+d2+…dk=2k-2时存在一颗具有k个顶点的树，各顶点的度数为d1,d2,…,dk.当n=k+1时，各定点度数和d1+d2+…dk+dk+1=2(k+1)-2=(2k-2)+2,比k个顶点时的度数和多2，由归纳假设满足条件的k个顶点的树存在，所以只要在该树的任意节点上向外连一条悬挂边，就变成度数增加2，边数增加1，顶点数增加1的k+1个顶点的树，并且各顶点的度数序列为d1,d2,…,dk+1(c)d1=5,d2=3,d3=2,d4=…=d9=1,并且16=2×9-215.(5’)(a)成立。(b)成立，因为t=2h.(c)成立，因为n=2h+1-1,所以n+1=2h+1，故)(log)1(log122nnh(d)成立。516.(6’)(a)(b)2个。(c)在G中任选两个顶点u和v。若它们在G中无边连接，则它们在G的补图中有边连接。若它们在G中有边连接，则它们在G的同一个连通分支中。在其他连通分支中选w。则uwv是补图中的一条路。两种情形下，u和v在补图中都有路连接。所以补图是连通的。(d)跟自己的补图同构的图如下：(e)不成立，(d)的图可作为一个反例。17.(6’)(a)权重值为3的那条对角线边。(b)最左边那条权重值为2的边。(c)2+4+2+1+2+3+4=18(d)28。(绕外圈边形成的回路是仅有的Hamilton回路)(e)2+4+2+1+2+3+5=19(f)没有Euler回路，因为有度数为3的顶点。有Euler路，权重为所有边的权重总和=42.x43544213442222x6参考答案待续