温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(3545)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'欧拉函数phi(m)',
blogAbstract:'欧拉函数phi(m)：当m&1是，phi(m)表示比m小且与m互质的正整数个数1、费马定理：a的p-1次方mod p余1。（其中p是素数，a是不能被p整除的正整数。2、欧拉定理&&& 2.1 欧拉函数（RSA的证明用到）&&&&&&&&& 定义：欧拉函数phi(m)：当m&1是，phi(m)表示比m小且与m互质的正整数个数&&&&&&&&&&&&&& 如：phi(24)=8&&& （1，5，7，11，13，17，19，23）&&&&&&&&& ',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:5,
publishTime:6,
permalink:'blog/static/',
commentCount:2,
mainCommentCount:1,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}5211《离散数学》题库及答案_离散数学习题答案-牛宝宝文章网
Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P?(P?Q)=>?P答：在第三章里" />
5211《离散数学》题库及答案 离散数学习题答案
《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？(
)(1)?Q=&Q→P (2)?Q=&P→Q (3)P=&P→Q (4)?P?(P?Q)=&?P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？(
)(1)(┐P?Q)→(Q→?R) (2)P→(Q→Q) (3)(P?Q)→P
(4)P→(P?Q) 答：（2），（3），（4） 可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?(
)(1)P=&P?Q (2) P?Q=&P (3) P?Q=&P?Q(4)P?(P→Q)=&Q
(5) ?(P→Q)=&P
(6) ?P?(P?Q)=&?P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)?B(y，x))? ?z C(y，z))?D(x)中，自由变元是(
)，约束变元是(
)。答：x,y,
x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。若是，给出命题的真值。(
)(1) 北京是中华人民共和国的首都。 (2)
陕西师大是一座工厂。(3) 你喜欢唱歌吗？
若7+8＞18，则三角形有4条边。(5) 前进！
给我一杯水吧！答：（1） 是，T
（2） 是，F
（3） 不是 （4） 是，T
（5） 不是
（6） 不是 （命题必须满足是陈述句，不能是疑问句或者祈使句。）6、命题“存在一些人是大学生”的否定是(
)，而命题“所有的人都是要死的”的否定是(
)。答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“?换成存在?，?换成?”，然后将命题的结论否定，“且变或 或变且”）7、设P：我生病，Q：我去学校，则下列命题可符号化为(
)。(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） ?Q?P （注意“只有??才??”和“除非??就??”两者都是一个形式的）
（2） P??Q
（3） P??Q
（4）?P?Q8、设个体域为整数集，则下列公式的意义是(
?x?y(x+y=0)
(2) ?y?x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) ?x?y (xy=y)
(2) ?x?y(x+y=y)
)(3) ?x?y(x+y=x)
(4) ?x?y(y=2x)
)答：（1） F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2） F （同理）
（3）F （同理）
（4）T（对任一整数x存在整数 y满足条件 y=2x 很明显是正确的）10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 ?x(P(x)?Q(x))在哪个个体域中为真?(
)(1) 自然数
(1)--(3)均成立答：（1）（在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了）11、命题“2是偶数或-3是负数”的否定是（
）。答：2不是偶数且-3不是负数。12、永真式的否定是（
）(1) 永真式 (2) 永假式 (3) 可满足式 (4)
(1)--(3)均有可能 答：（2）（这个记住就行了）13、公式(?P?Q)?(?P?为（
）。 ?Q)化简为（
），公式 Q?(P?(P?Q))可化简答：?P ，Q?P（考查分配率和蕴含等值式知识的掌握）14、谓词公式?x(P(x)? ?yR(y))?Q(x)中量词?x的辖域是（
）。 答：P(x)? ?yR(y)（一对括号就是一个辖域）15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（
）。答：??x(R(x)?Q(x))（集合论部分）16、设A={a,{a}}，下列命题错误的是（
）。(1) {a}?P(A) (2) {a}?P(A) (3) {{a}}?P(A) (4) {{a}}?P(A) 答：(2) （{a}是P（A）的一个元素）17、在0（
）?之间写上正确的符号。(1) = (2) ? (3) ? (4) ?答：(4)（空集没有任何元素，且是任何集合的子集）18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（
）。答：32（2的5次方 考查幂集的定义，即幂集是集合S的全体子集构成的集合）19、设P={x|(x+1)2?4且x?R},Q={x|5?x2+16且x?R},则下列命题哪个正确（
(2) Q?P (3) P?Q (4) P=Q答：（3）（Q是集合R，P只是R中的一部分，所以P是Q的真子集）20、下列各集合中，哪几个分别相等(
)。(1) A1={a,b}
A3={a,b,a} (4) A4={a,b,c}(5)
A5={x|(x-a)(x-b)(x-c)=0}
A6={x|x2-(a+b)x+ab=0} 答：A1=A2=A3=A6， A4=A5（集合具有无序性、确定性和互异性）21、若A-B=Ф，则下列哪个结论不可能正确？(
(2) B=Ф (3) A?B
(4) B?A答：（4）（差集的定义）22、判断下列命题哪个为真?(
)(1) A-B=B-A =& A=B
(2) 空集是任何集合的真子集(3) 空集只是非空集合的子集
(4) 若A的一个元素属于B，则A=B 答：（1）（考查空集和差集的相关知识）23、判断下列命题哪几个为正确？(
)(1) {Ф}∈{Ф,{{Ф}}}
(2) {Ф}?{Ф,{{Ф}}}
(3) Ф∈{{Ф}}(4) Ф?{Ф}
(5) {a,b}∈{a,b,{a},{b}}答：（2），（4）24、判断下列命题哪几个正确？(
)(1) 所有空集都不相等 (2) {Ф}?Ф
(4) 若A为非空集，则A?A成立。 答：（2）25、设A∩B=A∩C，A∩B=A∩C，则B( )C。答：=（等于）26、判断下列命题哪几个正确？(
)(1) 若A∪B＝A∪C，则B＝C (2) {a,b}={b,a}(3) P(A∩B)?P(A)∩P(B) （P(S)表示S的幂集）(4) 若A为非空集，则A?A∪A成立。答：（2）27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：(1) A?B，B?C=& A?C
(2) A?B，B?C=& A∈B (3) A∈B，B∈C=& A∈C 答：（1） （（3）的反例 C为{｛0，1｝，0｝ B为｛0，1｝，A为1 很明显结论不对）（二元关系部分）28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2求(1)R
R-1答：（1）R={&1,1&,&4,2&}
(2) R?1={&1,1&,&2,4&}（考查二元关系的定义，R?1为R的逆关系，即R?1=｛&x,y&｝|&y,x& ∈R）29、举出集合A上的既是等价关系又是偏序关系的一个例子。(
) 答：A上的恒等关系30、集合A上的等价关系的三个性质是什么？(
)答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么？(
)答：自反性、反对称性和传递性(题29，30，31全是考查定义)32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝ 求(1)R?R
R-1 。答：R?R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}（考查F?G ={&x,y&|?t(&x,t&∈F?&t,y&∈G)}）R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {(
)} R={&1,1&,&2,2&,&3,3&,&4,4&,&5,5&,&6,6&,&1,2&,&1,3&,&1,4&,&1,5&,&1,6&,&2,4&,&2,6&,&3,6&}34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R
。答：（1）R={&1,1&,&4,2&,&6,3&}
(2) R?1={&1,1&,&2,4&,(36&}35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。5211《离散数学》题库及答案_离散数学习题答案?1?0?0答：R的关系矩阵=??0??0????1?0?0
R?1的关系矩阵=???0???00?0??0??0 ?0??36、集合A={1,2,?,10}上的关系R={&x,y&|x+y=10,x,y?A}，则R 的性质为（
）。(1) 自反的
(2) 对称的
(3) 传递的，对称的 (4) 传递的 答：（2）（考查自反 对称 传递的定义）（代数系统部分）37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点&A,*&中，单位元是(
)，零元是(
)。答：2，6（单位元和零元的定义，单位元：e。x=x
零元：θ。x=θ）38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点&A,*&中，单位元是(
)，零元是(
)；答：9，3（半群与群部分）39、设〈G,*〉是一个群，则(1)
若a,b,x∈G，a?x=b，则x=(
若a,b,x∈G，a?x=a?b，则x=(
)。答： （1） a?1?b
（2） b （考查群的性质，即群满足消去律）40、设a是12阶群的生成元， 则a2是(
)阶元素，a3是(
)阶元素。 答： 6,441、代数系统&G,*&是一个群，则G的等幂元是(
)。答：单位元（由a^2=a,用归纳法可证a^n=a*a^(n-1)=a*a=a，所以等幂元一定是幂等元，反之若a^n=a对一切N成立，则对n=2也成立，所以幂等元一定是等幂元，并且在群&G,*&中，除幺元即单位元e外不可能有任何别的幂等元）42、设a是10阶群的生成元， 则a4是(
)阶元素，a3是(
)阶元素答：5，10（若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=&a&表示，且称a为一个生成元。并且一元素的阶整除群的阶）43、群&G,*&的等幂元是(
)个。答：单位元，1 （在群&G,*&中，除幺元即单位元e外不可能有任何别的幂等元）44、素数阶群一定是(
)群, 它的生成元是(
)。答：循环群，任一非单位元（证明如下：任一元素的阶整除群的阶。现在群的阶是素数p，所以元素的阶要么是1要么是p。G中只有一个单位元，其它元素的阶都不等于1，所以都是p。任取一个非单位元，它的阶等于p，所以它生成的G的循环子群的阶也是p，从而等于整个群G。所以G等于它的任一非单位元生成的循环群）45、设〈G,*〉是一个群，a,b,c∈G，则(1)
若c?a=b，则c=(
若c?a=b?a，则c=(
)。 答：（1） b?a?1
b（群的性质）46、&H,,?&是&G,,?&的子群的充分必要条件是(
)。答：&H,,?&是群 或 ? a，b ?G， a?b?H，a-1?H 或? a,b ?G，a?b-1?H47、群＜A,*＞的等幂元有(
)，零元有(
)个。 答：1，单位元，048、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是(
)。 答：k49、在自然数集N上，下列哪种运算是可结合的？（
）(1) a*b=a-b
(2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 答：(2)50、任意一个具有2个或以上元的半群，它（
）。(1) 不可能是群
(2) 不一定是群(3) 一定是群
(4) 是交换群答：(1)51、6阶有限群的任何子群一定不是（
）。(1) 2阶
(4) 6 阶答：(3)（格与布尔代数部分）52、下列哪个偏序集构成有界格（
）(1) （N,?） (2) （Z,?）(3) （{2,3,4,6,12},|（整除关系））
(4) (P(A),?)答：(4)（考查幂集的定义）53、有限布尔代数的元素的个数一定等于（
2的正整数次幂 答：(4)（图论部分）54、设G是一个哈密尔顿图，则G一定是(
)。(1) 欧拉图
(3) 平面图
(4) 连通图答：(4)（考察图的定义）55、下面给出的集合中，哪一个是前缀码？(
)(1) {0，10，110，101111}
(2) {01，001，000，1}(3) {b，c，aa，ab，aba}
(4) {1，11，101，001，0011} 答：（2）56、一个图的哈密尔顿路是一条通过图中(
)的路。答：所有结点一次且恰好一次57、在有向图中，结点v的出度deg+(v)表示(
)，入度deg-(v)表示(
)答：以v为起点的边的条数， 以v为终点的边的条数58、设G是一棵树，则G 的生成树有(
)棵。(1) 0
(4) 不能确定答：159、n阶无向完全图Kn 的边数是(
)，每个结点的度数是(
)。。答：n(n?1)2, n-160、一棵无向树的顶点数n与边数m关系是(
)。答：m=n-161、一个图的欧拉回路是一条通过图中(
)的回路。答：所有边一次且恰好一次62、有n个结点的树，其结点度数之和是(
)。答：2n-2（结点度数的定义）63、下面给出的集合中，哪一个不是前缀码(
)。(1) {a，ab，110，a1b11}
(2) {01，001，000，1}(3) {1，2，00，01，0210}
(4) {12，11，101，002，0011}答：(1)64、n个结点的有向完全图边数是(
)，每个结点的度数是(
)。 答：n(n-1),2n-265、一个无向图有生成树的充分必要条件是(
)。答：它是连通图66、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答：（3）67、设T=〈V,E〉是一棵树，若|V|&1，则T中至少存在(
)片树叶。 答：268、任何连通无向图G至少有(
)棵生成树，当且仅当G 是(
)，G的生成树只有一棵。答：1， 树69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:(1) m-n+2
(2) n-m-2 (3) n+m-2 (4) m+n+2。答：（1）70、设T是一棵树，则T是一个连通且(
)图。答：无简单回路71、设无向图G有16条边且每个顶点的度数都是2，则图G有(
)个顶点。(1)
(4) 16答：（4）72、设无向图G有18条边且每个顶点的度数都是3，则图G有(
)个顶点。(1)
(4) 12答：(4)73、设图G=&V，E&，V={a，b，c，d，e}，E={&a,b&,&a,c&,&b,c&,&c,d&,&d,e&},则G是有向图还是无向图？答：有向图74、任一有向图中，度数为奇数的结点有(
)个。答：偶数75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由(
)条边围成？(1) 2
(4) 5答：（3）76、在有n个顶点的连通图中，其边数（
）。(1) 最多有n-1条
(2) 至少有n-1 条(3) 最多有n条
(4) 至少有n 条答：（2）77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（
(4) 9答：（4）78、若一棵完全二元（叉）树有2n-1个顶点，则它（
）片树叶。(1) n
(4) 25211《离散数学》题库及答案_离散数学习题答案答：（1）79、下列哪一种图不一定是树（
）。(1) 无简单回路的连通图
(2) 有n个顶点n-1条边的连通图(3) 每对顶点间都有通路的图
(4) 连通但删去一条边便不连通的图答：（3）80、连通图G是一棵树当且仅当G中（
）。(1) 有些边是割边
(2) 每条边都是割边(3) 所有边都不是割边
(4) 图中存在一条欧拉路径答：（2）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式：1、(P→Q)?R解：(P→Q)?R?(?P?Q )?R?(?P?R)?(Q?R) （析取范式）?(?P?(Q??Q)?R)?((?P?P)?Q?R)?(?P?Q?R)?(?P??Q?R)?(?P?Q?R)?(P?Q?R)?(?P?Q?R)?(?P??Q?R)?(P?Q?R)（主析取范式）?((P→Q)?R)?(?P??Q??R)?(?P?Q??R)?(P??Q?R)?(P?Q??R)?( P??Q??R)（原公式否定的主析取范式）(P→Q)?R?(P?Q?R)?(P??Q?R)?(?P?Q??R)?(?P??Q?R)?(?P?Q?R)（主合取范式）2、(P?R)?(Q?R)??P解： (P?R)?(Q?R)??P（析取范式）?(P?(Q??Q)?R)?((P??P)?Q?R)?(?P?(Q??Q)?(R??R))?(P?Q?R)?(P??Q?R)?(P?Q?R)?(?P?Q?R)?( ?P?Q?R)?( ?P?Q??R)?(?P??Q?R)?(?P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P?Q??R)(?P??Q?R)?(?P??Q??R) (主析取范式)??（(P?R)?(Q?R)??P）?(P??Q??R)?(P?Q??R）（原公式否定的主析取范式） (P?R)?(Q?R)??P ?(?P?Q?R)?(?P??Q?R)（主合取范式）3、(?P→Q)?(R?P)解：(?P→Q)?(R?P)?????(P?Q)?(R?P)（合取范式） (P?Q?(R??R))?(P?(Q??Q))?R) (P?Q?R)?(P?Q??R)?(P?Q?R)?(P??Q?R)
(P?Q?R)?(P?Q??R)?(P??Q?R)（主合取范式）
((?P→Q)?(R?P))?(P??Q??R)?(?P?Q?R)?(?P??Q?R)?(?P?Q??R)?(?P??Q??R)（原公式否定的主合取范式）(?P→Q)?(R?P)?(?P?Q?R)?(P??Q??R)?(P?Q??R)?(P??Q?R)?(P?Q?R) （主析取范式）4、Q→(P??R)解：Q→(P??R)???Q?P??R（主合取范式） （Q→(P??R)）?(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)Q?R)?(P?Q??R)?(P?Q?R）（原公式否定的主合取范式） ?(P??Q→(P??R)?(P?Q?R)?(P?Q??R)?(P??Q?R)?(P??Q??R)?(?P?Q??R) ?(?P??Q?R)?(?P??Q??R）（主析取范式）5、P→(P?(Q→P))解：P→(P?(Q→P))?????P?(P?(?Q?P)) P?P
T (主合取范式)?(?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式） 6、?(P→Q)?(R?P)解： ?(P→Q)?(R?P)??(?P?Q)?(R?P)??(P??Q)?(R?P)（析取范式） (P??Q?(R??R))?(P?(?Q?Q)?R)(P??Q?R)?(P??Q??R)?(P??Q?R)?(P?Q?R)(P??Q?R)?(P??Q??R)?(P?Q?R)（主析取范式） ???(?(P→Q)?(R?P))?(P?Q??R)?(?P?Q?R)?(?P??Q?R)? (?P??Q??R)?(?P?Q??R)（原公式否定的主析取范式） ?(P→Q)?(R?P)?(?P??Q?R)?(P??Q??R)?(P?Q??R)?(P?Q?R)?(P??Q?R)（主合取范式）7、P?(P→Q)解：P?(P→Q)?P?(?P?Q)?(P??P)?Q??T(主合取范式) (?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式）8、(R→Q)?P解：(R→Q)?P?(?R?Q )?P????? (?R?P)?(Q?P) （析取范式）
(?R?(Q??Q)?P)?((?R?R)?Q?P) (?R?Q?P)?(?R??Q?P)?(?R?Q?P)?(R?Q?P) (P?Q??R)?(P??Q??R)?(P?Q?R)（主析取范式） ((R→Q)?P)?(?P??Q??R)?(?P?Q??R）?(P??Q?R)?(?P?Q?R)?(?P??Q?R)（原公式否定的主析取范式）(R→Q)?P?(P?Q?R)?(P??Q?R)?(?P?Q??R)?(P??Q??R)?(P?Q??R)（主合取范式）9、P→Q解：P→Q??P?Q（主合取范式）?(?P?(Q??Q))?((?P?P)?Q)(?P?Q)?(?P??Q)?(?P?Q)?(P?Q)??(?P?Q)?(?P??Q)?(P?Q)（主析取范式）?10、 P?Q解：
P??Q （主合取范式）???(P?(?Q?Q))?((?P?P)??Q） (P??Q)?(P?Q)?(?P??Q)?(P??Q） (P??Q)?(P?Q)?(?P??Q)（主析取范式）11、P?Q解：P?Q（主析取范式）?(P?(Q??Q))?((P??P)?Q)??(P??Q)?(P?Q)?(P?Q)?(?P?Q) (P??Q)?(P?Q)?(?P?Q)（主合取范式）12、（P?R）?Q解：（P?R）?Q?????????(P?R)?Q (?P??R)?Q (?P?Q)?(?R?Q)（合取范式） (?P?Q?(R??R))?((?P?P)?Q??R) (?P?Q?R)?(?P?Q??R)?(?P?Q??R)?(P?Q??R) (?P?Q?R)?(?P?Q??R)?(?P?Q??R)?(P?Q??R) (?P?Q?R)?(?P?Q??R)?(P?Q??R)（主合取范式） （P?R）?Q?(?P??Q?R)?(?P??Q??R)?(P?Q?R)?(P??Q?R)?(P??Q??R)（原公式否定的主析取范式）（P?R）?Q?(P?Q??R)?(P?Q?R)?(?P??Q??R)?(?P?Q??R)P?Q?R)（主析取范式） ?(?13、（P?Q）?R解：（P?Q）?R???(?P?Q)?R (P??Q)?R(析取范式)??(P??Q?(R??R))?((P??P)?(Q??Q)?R) (P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(P??Q??R)?(P?Q?R)?(?P?Q?R)P??Q?R)(主析取范式） ?(?（P?Q）?R???????(?P?Q)?R (P??Q)?R(析取范式) (P?R)?(?Q?R)(合取范式) (P?(Q??Q)?R)?((P??P)??Q?R) (P?Q?R)?(P??Q?R)?(P??Q?R)?(?P??Q?R) (P?Q?R)?(P??Q?R)?(?P??Q?R)(主合取范式)?14、(P?(Q?R))?(?P?(?Q?R))解：(P?(Q?R))?(?P?(?Q??R))???(?P?(Q?R))?(P?(?Q??R)) (?P?Q)?(?P?R)?(P??Q)?(P??R)（合取范式） (?P?Q?(R??R))?(?P?(Q??Q)?R)?(P??Q?(R??R))?(P?(Q??Q)??R)?(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(P??Q??R)?(P?Q??R)?(P??Q??R) ?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(P??Q?R)?(P?Q??R)?(P??Q??R)(主合取范式)?(P?(Q?R))?(?P?(?Q??R))?(?P??Q??R)?(P?Q?R)(原公式否定的主合取范式) (P?(Q?R))?(?P?(?Q??R))?(P?Q?R)?(?P??Q??R)(主析取范式)15、P?(?P?(Q?(?Q?R)))解：P?(?P?(Q?(?Q?R)))? P?(P?(Q?(Q?R)))5211《离散数学》题库及答案_离散数学习题答案?? P?Q?R(主合取范式) (P?Q?R)?(P??Q?R)?(P??Q??R)?(P?Q??R)?(?P?Q?R)P?Q??R)?(?P??Q?R)?(?P??Q??R) ?(?(原公式否定的主合取范式)(P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)?(P??Q??R)Q?R)?(P?Q??R)?(P?Q?R)(主析取范式) ?(P??16、(P?Q)?(P?R)解、(P?Q)?(P?R)????(?P?Q)?(?P?R) (合取范式) (?P?Q?(R??R)?(?P?(?Q?Q)?R) (?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(?P?Q?R) (?P?Q?R)?(?P?Q??R)?(?P??Q?R)(主合取范式) (P?Q)?(P?R)?(?P?Q)?(?P?R)P?(Q?R)(合取范式) ????(?P?(Q??Q)?(R??R))?((?P?P)?Q?R) (?P?Q?R)?(?P??Q?R)?(?P?Q??R)?(?P??Q?R)P?Q?R)?(P?Q?R) ?(??(?P?Q?R)?(?P??Q?R)?(?P?Q??R)?(?P??Q?R)?(P?Q?R)(主析取范式)三、证明：1、P→Q，?Q?R，?R，?S?P=&?S证明：(1)
（1），（2）(4)
（3），（4）(6) ?S?P
（5），（6）2、A→(B→C)，C→(?D?E)，?F→(D??E),A=&B→F 证明：(1)
（1），（2）(4)
附加前提(5)
（3），（4）(6)
（5），（6）(8)
?F→(D??E) 前提(9)
（7），（8）(10)
CP3、P?Q， P→R, Q→S
=& R?S 证明：(1)
附加前提(2)
（1），（2）(4)
（3），（4）(6)
（5），（6）(8)
CP，（1），（8）4、(P→Q)?(R→S)，(Q→W)?(S→X)，证明：（1）
假设前提?(W?X)，P→R =& ?P（2）
（1），（2）（4） (P→Q)?(R→S) 前提（5）
（4）（6）
（5）（7）
（1），（5）（8）
（3），（6）（9） (Q→W)?(S→X)
前提（10） Q→W
（9）（11） S→X
（10）（12）
（7），（10）（13）
（8），（11）（14）
（12），（13）（15） ?(W?X)
前提（16） ?(W?X)?(W?X)
（14），（15）5、(U?V)→(M?N), U?P, P→(Q?S)，?Q?证明：(1)
?Q?（2）（3）（4）（5）（6）（7）（8）（9） ??S =&M
附加前提 P→(Q?S)
（1），（2）
（3），（4）
（5） (U?V)→(M?N)
（8）6、?B?D，(E→?F)→?D，?E=&?B 证明：(1)
附加前提(2)
（1），（2）(4)
(E→?F)→?D
（3），（4）(6)
（7），（8）7、P→(Q→R)，R→(Q→S) =& P→(Q→S) 证明：（1）
附加前提（2）
附加前提（3）
（1），（3）（5）
（2），（4）（6）
（5），（6）（8）
（2），（7）（9）
CP，（2），（8）（10） P→(Q→S)
CP，（1），（9）8、P→?Q，?P→R，R→?S =&S→?Q
证明：（1）
附加前提（2）
（1），（2）（4）
（3），（4）（6）
(5），（6）（8）
CP，（1），（7）9、P→(Q→R) =& (P→Q)→(P→R) 证明：(1)
附加前提(2)
附加前提(3)
(1),(2)(4)
P→(Q→R) 前提(5)
(2),(4)(6)
(3),(5)(7)
CP,(2),(6)(8) (P→Q) →(P→R) CP,(1),(7)10、P→(?Q→?R)，Q→?P,S→R,P =&?S 证明：（1）
P→(?Q→?R)
(1)，(2)（4）
(1)，(4)（6）
(3),(5)（7）
(6)，(7)11、A，A→B， A→C， B→(D→?C) =& ?D 证明：（1）
(1)，(2)（4）
(1)，(4)（6） B→(D→?C) 前提5211《离散数学》题库及答案_离散数学习题答案（7）
(3)，(6)（8）
?，(7)12、A→(C?B)，B→?A，D→?C =& A→?D证明：（1）
附加前提(2)
（1），（2）(4)
（1），（4）(6)
（3），（5）(7)
（6），（7）(9)
CP，（1），（8）13、(P?Q)?(R?Q) ?（P?R）?Q证明、(P?Q)?(R?Q)??(?P?Q)?(?R?Q) (?P??R)?Q??（P?R）?Q?(P?R)?Q?14、P?(Q?P)?证明、P?(Q?P)??????P?(P??Q) P?(?Q?P) (?P)?(?P??Q) P?(P??Q)15、（P?Q）?（P?R），?(Q?R)，S?P?S证明、(1)
（P?Q）?（P?R）
（2），(3)(5)
(4),(5)16、P??Q，Q??R，R??S? ?P证明、(1)
附加前提（2）
（1），（2）（4）
（3），（4）(6 )
（6）（8）
（5），（7）17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ)证明、列出两个公式的真值表：由定义可知，这两个公式是等价的18、P→Q?P→(P?Q)证明：设P→(P?Q)为F，则P为T，P?Q为F。所以P为T，Q为F ，从而P→Q也为F。所以P→Q?P→(P?Q)。19、用先求主范式的方法证明(P→Q)?(P→R) ? (P→（Q?R） 证明：先求出左右两个公式 的主合取范式(P→Q)?(P→R) ?(?P?Q)?(?P?R)???(?P?Q?(R??R)))?(?P?(Q??Q)?R)
(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)
(?P?Q??R)?(?P?Q?R)?(?P??Q?R)(P→（Q?R）) ?(?P?（Q?R）)?(?P?Q)?(?P?R)???(?P?Q?(R??R))?(?P?(Q??Q)?R)
(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)
(?P?Q??R)?(?P?Q?R)?(?P??Q?R)它们有一样的主合取范式，所以它们等价。20、(P→Q)?证明： ?(Q?R) ??P设(P→Q)??(Q?R)为T，则P→Q和?(Q?R)都为T。即P→Q和?Q??R都为T。故P→Q，?Q和?R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即?P为T。从而(P→Q)??(Q?R) ??P21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?前提: (1)
若A队得第一，则B队或C队获亚军;(2) 若C队获亚军，则A队不能获冠军;(3) 若D队获亚军，则B队不能获亚军;(4) A 队获第一;结论: (5) D队不是亚军。证明：设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A?（B?C），C??A，D??B，A；结论符号化为 ?D。本题即证明 A?（B?C），C??A，D??B，A??D（1）
前提（2） A?（B?C）前提（3）
（1），（2）（4）
（1），（4）（6）
（3），（5）（7）
（6），（7）22、用推理规则证明P?Q, ?(Q?R),P?R不能同时为真。 证明：(1)
(2),(3)(5)
(4),(7)(集合论部分)四、设Ａ，Ｂ，Ｃ是三个集合，证明：1、A? (B－C)＝(A?B)－(A?C)
证明：(A?B)－(A?C)= (A?B) ?A?C=(A?B) ?（A?C） =(A?B?A)?(A?B?C)= A?B?C=A?（B?C） =A?（B-C）2、(A－B)?(A－C)=A－(B?C) 证明：(A-B)?(A-C)=(A?B)?(A?C) =A? (B?C)=A?B?C= A-(B?C)3、A?B=A?C，A?B=A?C，则C=B
证明：B=B?(A?A)=(B?A)? (B?A) =(C?A)? (C?A)=C?(A?A)=C4、A?B=A?(B-A) 证明：A?(B-A)=A?(B?A)=(A?B)?(A?A)=(A?B)?U= A?B5、A=B
证明：?设A=B，则A?B=（A-B）?（B-A）=???=?。 ?设A?B=?，则A?B=（A-B）?（B-A）=?。故A-B=?，从而A?B，B?A，故A=B。6、A?B = A?C，A?B=A?C，则C=B 证明：B=B?(A?B)= B?(A?C)= (B?A)?(B?C) = (A?C)?(B∩C)= C?(A?B) = C?(A?C)=C7、A?B=A?C，A?B=A?C，则C=B
证明：B=B?(A?A)=(B?A)?(B?A) =(C?A)?(C?A)=C?(A?A) =C8、A－(B?C)＝(A－B)－C
证明：A－(B?C)= A?B?CB-A=?，5211《离散数学》题库及答案_离散数学习题答案=A?(B?C)=(A?B)?C=(A-B)?C=(A-B)-C9、(A－B)?(A－C)=A－(B?C)证明：(A-B)?(A－C)=(A?B)?(A?C)=(A?A)?(B?C)=A?B?C=A－(B?C)10、A-B=B，则A=B=?证明：因为B=A-B，所以B=B?B=（A-B）?B=?。从而A=A-B=B=?。11、A=(A-B)?(A-C)?A?B?C=?证明：?
因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)=A?B?C= A-(B?C)，且A=(A-B)?(A-C)，所以A= A-(B?C)，故A?B?C=?。? 因为A?B?C=?，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，所以A=(A-B)?(A-C)。12、(A-B)?(A-C)=?证明：??A?B?C
因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)=A?B?C= A-(B?C)，且(A-B)?(A-C)=?，所以?= A-(B?C)，故A?B?C。? 因为A?B?C，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，所以A=(A-B)?(A-C)。13、(A-B)?(B-A)=A ? B=?证明：?
因为(A-B)?(B-A)=A，所以B-A?A。但(B-A)?A=?，故B-A=?。即B?A，从而B=?（否则A-B?A，从而与(A-B)?(B-A)=A矛盾）。? 因为B=?，所以A-B=A且B-A=?。从而(A-B)?(B-A)=A。14、(A-B)-C?A-(B-C)证明：?x?(A-B)-C，有x?A-B且x?C，即x?A，x?B且x?C。从而x?A，x?B-C，故x?A-(B-C)。从而(A-B)-C?A-(B-C)15、P(A)?P(B)?P(A?B) （P(S)表示S的幂集）证明：?S?P(A)?P(B)，有S?P(A)或S?P(B)，所以S?A或S?B。从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)16、P(A)?P(B)=P(A?B) （P(S)表示S的幂集）证明：?S?P(A)?P(B)，有S?P(A)且S?P(B)，所以S?A且S?B。从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)。?S?P(A?B)，有S?A?B，所以S?A且S?B。从而S?P(A)且S?P(B)，故S?P(A)?P(B)。即P(A?B)?P(A)?P(B)。故P(A?B)=P(A)?P(B)17、（A-B）?B=（A?B）-B当且仅当B=?。证明：?当B=?时，因为（A-B）?B=（A-?）??=A，（A?B）-B=（A??）-?=A，所以（A-B）?B=（A?B）-B。?用反证法证明。假设B??，则存在b?B。因为b?B且b? A?B，所以b?（A?B）-B。而显然b?（A-B）?B。故这与已知（A-B）?B=（A?B）-B矛盾。五、证明或解答：（数理逻辑、集合论与二元关系部分）1、设个体域是自然数，将下列各式翻译成自然语言：(1)
?x?y（xy=1）;
?x?y(xy=1);(3)
?x?y (xy=0);
?x?y（xy=0）;(5)
?x?y (xy=x);
?x?y（xy=x）;(7)
?x?y?z (x-y=z)答：（1）存在自然数x，对任意自然数y满足xy=1;（2）对每个自然数x，存在自然数y满足xy=1;（3）对每个自然数x，存在自然数y满足xy=0;（4）存在自然数x，对任意自然数y满足xy=1;（5）对每个自然数x，存在自然数y满足xy=x;（6）存在自然数x，对任意自然数y满足xy=x;（7）对任意自然数x,y，存在自然数z满足x-y=z。2、设A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): x&y, G(x,y): x&y， 个体域为自然数。将下列命题符号化：（1）没有小于0的自然数;（2）x&z是x&y且y&z的必要条件;（3）若x&y，则存在某些z，使z&0, xz&（4）存在x，对任意y 使得xy=y;（5）对任意x，存在y使x+y=x。答：（1）?x（G(x,0)?M（0,0,x））
或??x L(x,0)（2）?x?y?z ((L(x,y)?L(y,z))?L(x,z))（3）?x?y ((L(x,y)??z(L(z,0)?G(xz,yz)))（4）?x?yM（x,y,y）（5）?x?yA(x,y,x)3、列出下列二元关系的所有元素：（1）A={0,1,2}，B={0,2,4}，R={&x,y&|x,y?A?B};（2）A={1,2,3,4,5}，B={1,2}，R={&x,y&|2?x+y?4且x?A且y?B};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={&x,y&||x|=|y|且x?A且y?B}; 解：(1)
R={&0,0&,&0,2&,&2,0&,&2,2&}(2)
R={&1,1&,&1,2&,&2,1&,&2,2&,&3,1&};(3)
R={&1,1&,&1,-1&,&2,-2&,&3,-3&}。4、对任意集合A,B，证明：若A?A=B?B，则B=B。证明：若B=?，则B?B=?。从而A?A =?。故A=?。从而B=A。若B??，则B?B??。从而A?A??。对?x?B, &x,x&?B?B。因为A?A=B?B，则&x,x&?A?A。从而x?A。故B?A。 同理可证，A?B。故B=A。5、对任意集合A,B，证明：若A??，A?B=A?C，则B=C。证明：若B=?，则A?B=?。从而A?C =?。因为A??，所以C=?。即B=C。若B??，则A?B??。从而A?C??。对?x?B,因为A??，所以存在y?A, 使&y,x&?A?B。因为A?B=A?C，则&y,x&?A?C。从而x?C。故B?C。同理可证，C?B。故B=C。6、设A={a,b}, B={c}。求下列集合：(1)
A?{0,1}?B；
P(A)?A。解：（1） A?{0,1}?B={&a,0,c&,&a,1,c&,&b,0,c&,&b,1,c&};（2） B2?A={&c,c,a&,&c,c,b&};（3） (A?B)={&a,c,a,c&,&a,c,b,c&,&b,c,a,c&,&b,c,b,c&};（4） P(A)?A={&?,a&,&?,b&,&{a},a&,&{a},b&,&{b},a&,&{b},b&,&A,a&,&A,b&}。27、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合：（1）A?B?C； （2）A?B?C；（3）(A?B)?C;（4）P(A)-P(B); （5）(A-B)?(B-C); （6）(A?B)?C;解 ：(1)
A?B?C={a};
(2) A?B?C={a,b,c,d,e};(3)
（A?B）?C={b,d};
P(A)-P(B)={{d},{a,d}};(5)
(A-B)?(B-C)={d,c,a};
(A?B) ?C={b,d}。8、设A,B,C是任意集合，证明或否定下列断言：（1）若A?B，且B?C，则A?C；（2）若A?B，且B?C，则A?C;（3）若A?B，且B?C，则A?C；（4）若A?B，且B?C，则A?C；证明：(1)
成立。对?x?A, 因为A?B，所以x?B。又因为B?C，所以x?C。即A?C。(2)
不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然A?B，且B?C，但A?C。(3)
不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然A?B，且B?C，但A?C。(4)
成立。因为A?B, 且B?C，所以A?C。9、A上的任一良序关系一定是A上的全序关系。证明：?a，b∈A，则{a,b}是A的一个非空子集。?≤是A上的良序关系，?{a,b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序关系。10、若R和S都是非空集A上的等价关系，则R?S是A上的等价关系。
证明：?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xR?Sx。从而R?S是自反的。5211《离散数学》题库及答案_离散数学习题答案?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bR?Sa。从而R?S是对称的。?a,b,c∈A，aR?Sb且bR?Sc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aR?Sc。从而R?S是传递的。故R?S是A上的等价关系。11、设R?A×A，则R自反 ?IA?R。证明：????x?A，?R是自反的，?xRx。即&x,x&?R，故IA?R。 x?A，?IA?R，?&x,x&?R。即xRx，故R是自反的。12、设A是集合，R?A×A，则R是对称的?R＝R－1。证明：??&x,y&?R ，即&y,x&?R，故&x,y&?R_1 。从而R?R-1。 ?R是对称的，?yRx。反之?&y,x&?R-1,即&x,y&?R 。?R是对称的，?yRx。即&y,x&?R， R_1?R。 故R=R-1。??x，y?A，若&x,y&?R ，即&y,x&?R-1。? R=R-1，?&y,x&?R。即yRx，故R是对称的。13、设A,B,C和D均是集合，R?A×B，S?B×C，T?C×D，则 (1)
R?(S?T)=(R?S)?(R?T)； (2)
R?(S?T)?(R?S)?(R?T)；证明：（1）?&x，z&?R?(S?T)，则由合成关系的定义知?y?B，使得&x，y&?R且&y，z&?S?T。从而&x，y&?R且&y，z&?S或&x，y&?R且&y，z&?T，即&x，z&?R?S或&x，z&?R?T。故&x，z&?（R?S）?（R?T） 。从而R?(S?T)?（R?S）?（R?T）。同理可证（R?S）?（R?T）?R?(S?T)。 故R?(S?T)=（R?S）?（R?T）。(2) ?&x，z&?R?(S?T)，则由合成关系的定义知?y?B，使得&x，y&?R且&y，z&?S?T。从而&x，y&?R且&y，z&?S且&y，z&?T，即&x，z&?R?S且&x，z&?R?T。故&x，z&?（R?S）?（R?T） 。从而R?(S?T)?(R?S）?（R?T）。14、设〈A,≤〉为偏序集，??B?A，若B有最大(小)元、上(下)确界，则它们是惟一的。证明：设a,b都是B的最大元，则由最大元的定义a?b，b?a。??是A上的偏序关系，?a=b。即B如果有最大元则它是惟一的。15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：解：?0?（1）R={&2,1&,&3,1&,&2,3&};MR=?1?1?0000??1?;它是反自反的、反对称的、传递的； 0??1011??1?;它是反自反的、0???0?（2）R={&1,2&,&2,1&,&1,3&,&3,1&,&2,3&,&3,2&};MR=?1?1?对称的；?0?（3）R={&1,2&,&2,1&,&1,3&,&3,3&};MR=?1?0?1001??0?;它既不是自反的、反自反的、1??也不是对称的、反对称的、传递的。16、设A={1,2,?,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？（1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}; （3）D={{1,2,7},{3,5,10},{4,6,8},{9}}解：（1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是IA?{&1,2&,&2,1&,&1,7&,&7,1&,&2,7&,&7,2&,&3,5&,&5,3&,&3,10&,&10,3&,&10,5&,&5,10&,&4,6&,&6,4&,&4,8&,&8,4&,&6,8&,&8,6&}。17、R是A={1,2,3,4,5,6}上的等价关系，R=IA?{&1,5&,&5,1&,&2,4&,&4,2&,&3,6&,&6,3&}求R诱导的划分。解：R诱导的划分为{{1,5},{2,4},{3,6}}。18、A上的偏序关系?的Hasse图如下。（1） 下列哪些关系式成立：a?b,b?a,c?e,e?f,d?f,c?f；（2） 分别求出下列集合关于?的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} 解：(1) b?a,c?e,d?f,c?f成立；(2) (a)的极大元为a,e,f,极小元为c;无最大元，c是最小元；无上界，下界是c;无上确界，下确界是c。(b)的极大元为b,d,极小元为b,d;无最大元和最小元；上界是e，下界是c;上确界是e，下确界是c。(c)的极大元为e,极小元为b;最大元是e，b是最小元；上界是e，下界是b;上确界是e，下确界是b。(d)的极大元为e,极小元为b,d;最大元是e，无最小元；上界是e，下界是c;上确界是e，下确界是c。（半群与群部分）19、求循环群C12={e,a,a2,?,a11}中H={e,a4,a8}的所有右陪集。解：因为|C12|=12，|H|=3，所以H 的不同右陪集有4 个：H，{a,a,a},{a,a,a},{a,a,a}。592610371120、求下列置换的运算：解：?1（1）??2?24334??1????1???4233324??1???1=??1?23344?? 2???1（2）??4?25253232464653536??1?=??1???423253532414652536??1????41???6??1?=??4???122253332444655536?? ?1?2=???1?46??1????61???6?? 6??21、试求出8阶循环群的所有生成元和所有子群。解：设G是8阶循环群，a是它的生成元。则G={e,a,a2,..,a7}。由于ak是G的生成元的充分必要条件是k与8互素，故a,a3,a5,a7是G的所有生成元。因为循环群的子群也是循环群，且子群的阶数是G 的阶数的因子，故G的子群只能是1 阶的、2阶的、4 阶的或8阶的。因为|e|=1,|a|=|a|=|a|=8,|a|=|a|=8, |a4|=2,且G 的子群的生成元是该子群中a的最小正幂，故G的所有子群除两个平凡子群外，还有{e,a4},{e,a2,a4,a6}。352622、I上的二元运算*定义为：a*b=a+b-2。试问&I,*&是循环群吗？?a,b?I，解：&I,*&是循环群。因为&I,*&是无限阶的循环群，则它只有两个生成元。1和3是它的两个生成元。因为a=na-2(n-1)，故1=n-2(n-1)=2-n。从而对任一个k?I,k=2-(2-k)=12-k，故1是的生成元。又因为1和3 关于*互为逆元，故3 也是&I,*&的生成元。nn23、设&G,?&是群，a?G。令H={x?G|a?x=x?a}。试证：H 是G 的子群。证明：?c，d?H，则对?c，d?HK，c?a=a?c,d?a=a?d。故(c?d) ?a=c?(d?a)=c?(a?d)=(c?a) ?d=(a?c) ?d=a?(c?d)。从而c?d?H。由于c?a=a?c,且?满足消去律，所以a ?c-1=c-1?a。故c-1?H。 从而H 是G的子群。24、证明：偶数阶群中阶为2 的元素的个数一定是奇数。证明：设&G,?&是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下的元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。25、证明：有限群中阶大于2的元素的个数一定是偶数。证明：设&G,?&是有限群，则?a?G，有|a|=|a-1|。且当a 阶大于2时，a?a-1。故阶数大于2 的元素成对出现，从而其个数必为偶数。26、试求&N6,+6&中每个元素的阶。解：0是&N6,+6&中关于+6的单位元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。27、设&G,?&是群，a,b?G，a?e，且a4?b=b?a5。试证a?b?b?a。证明：用反证法证明。假设a?b=b?a。则a4?b= a3?（a?b）= a3?(b?a)=(a5?b)?a=(a2?(a?b))?a=（a2?（b?a））?a=((a2?b)?a)?a=(a?(a?b))?(a?a) =(a?(b?a))?a2=((a?b)?a)?a2 =((b?a)?a)?a2=(b?a2)?a2224=b?(a?a)=b?a。因为a4?b= b?a5，所以b?a5= b?a4。由消去律得，a=e。 这与已知矛盾。28、I上的二元运算*定义为：?a,b?I，a*b=a+b-2。试证：&I,*&为群。证明：（1）?a,b,c?I，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c) =a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。（2）记e=2。对?a?I，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。5211《离散数学》题库及答案_离散数学习题答案（3）对?a?I，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。综上所述，&I,*&为群。29、设&S,?&为半群，a?S。令Sa={ai | i?I+ }。试证&Sa,?&是&S,?&的子半群。证明：?b，c?Sa，则存在k,l?I+，使得b=ak,c=al。从而b?c=ak?al=ak+l。因为k+l?I+，所以b?c?Sa，即Sa关于运算?封闭。故&Sa,?&是&S,?&的子半群。30、单位元有惟一逆元。证明：设&G,?&是一个群，e是关于运算?的单位元。若e1,e2都是e的逆元，即e1*e=e且e2*e=e。因为e是关于运算?的单位元，所以e1=e1*e=e=e2*e=e2。即单位元有惟一逆元。31、设e和0是关于A上二元运算*的单位元和零元，如果|A|&1，则e?0。 证明：用反证法证明。假设e=0。对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|&1矛盾。从而假设错误。即e?0。32、证明在元素不少于两个的群中不存在零元。证明：（用反证法证明）设在素不少于两个的群&G,?&中存在零元?。对?a?G, 由零元的定义有 a*?=?。? &G,?&是群，即G中只有一个元素，这与|G|?2?关于*消去律成立。? a=e。矛盾。故在元素不少于两个的群中不存在零元。33、证明在一个群中单位元是惟一的。证明：设e1,e2都是群〈G,*〉的单位元。
则e1=e1*e2=e2。所以单位元是惟一的。34、设a是一个群〈G，*〉的生成元，则a-1也是它的生成元。证明：?x?G，因为a是〈G，*〉的生成元，所以存在整数k，使得x=ak。-1故x=((ak)?1)?1=((a?1)k)?1=(a?1)?k。从而a也是〈G，*〉的生成元。35、在一个偶数阶群中一定存在一个2阶元素。证明：群中的每一个元素的阶均不为0 且单位元是其中惟一的阶为1的元素。因为任一阶大于2 的元素和它的逆元的阶相等。且当一个元素的阶大于2 时，其逆元和它本身不相等。故阶大于2 的元素是成对的。从而阶为1的元素与阶大于2 的元素个数之和是奇数。因为该群的阶是偶数，从而它一定有阶为2 的元素。36、代数系统&G,*&是一个群，则G除单位元以外无其它等幂元。 证明：设e是该群的单位元。若a是&G,*&的等幂元，即a*a=a。因为a*e=a，所以a*a=a*e。由于运算*满足消去律，所以a=e。即G除单位元以外无其它等幂元。37、设&G,?&是一个群，则对于a,b∈G，必有唯一的x∈G，使得a?x=b。 证明：因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有x∈G，使得a?x=b。若x1,x2都满足要求。即a?x1=b且a?x2=b。故a?x1=a?x2。由于*满足消去律，故x1=x2。从而对于a,b∈G，必有唯一的x∈G，使得a?x=b。38、设半群&S,?&中消去律成立，则&S,?&是可交换半群当且仅当?a,b?S，（a?b）2=a2?b2。证明：??a,b?S，（a?b）2=(a?b)?(a?b)=((a?b)?a)?b=(a?(a?b))?b=((a?a)?b)?b=(a?a)?(b?b)=a2?b2;??a,b?S，因为（a?b）2=a2?b2，所以(a?b)?(a?b)=(a?a)?(b?b)。故a?((b?a)?b)=a?(a?(b?b))。由于?满足消去律，所以(b?a)?b=a?(b?b)，即(b?a)?b=(a?b)?b。从而a?b=b?a。故?满足交换律。39、设群&G,＊&除单位元外每个元素的阶均为2，则&G,＊&是交换群。 证明：对任一a?G，由已知可得a*a=e，即a-1=a。对任一a,b?G，因为a*b=(a*b)-1=b-1*a-1=b*a，所以运算*满足交换律。从而＜G,*＞是交换群。40、设*是集合A上可结合的二元运算，且?a,b?A,若a*b=b*a，则a=b。试证明：（1）?a?A,a*a=a，即a是等幂元；（2） ?a,b?A,a*b*a=a;（3） ?a,b,c?A,a*b*c=a*c。证明：（1）?a?A,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。（2）?a,b?A,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，从而a*b*a=a。（3） ?a,b,c?A,（a*b*c）*（a*c）=（（a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。由（2）可知a*(b*c)*a=a且c*(a*b)*c=c，故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)= a*(c*(a*b)*c))= a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。从而由已知条件知，a*b*c=a*c。41、设&G,?&是群，作f:G?G,a?a-1。证明：f是G的自同构?G是交换群。证明：? 设-1f -1-1是G的自-1同构-1。对-1?-1a，b?G，a?b=(b?a)=(f(b) ?f(a))=(f(b?a))=((b?a))=b?a。故运算?满足交换律 ，即G是可交换群。?因为当a?b时，a-1?b-1，即f(a)?f(b)，故f是G到G中的一个单一函数。又对?a?G，有f(a-1)=(a-1)-1=a。故f是G到G上的满函数。从而f是G到G上的自同构。对?a，b?G，因为G是可交换群，故f(a?b)=(a?b)-1=(b?a)-1=a-1?b-1=f(a)?f(b)。故f满足同态方程。从而f是G 的自同构。42、若群&G,＊&的子群&H,＊&满足|G|＝2|H|，则&H,＊&一定是群&G,＊&的正规子群。证明：由已知可知，G关于H 有两个不同的左陪集H，H1和两个不同的右陪集H，H2。因为H?H1=?且H?H1=G，H?H2=?且H?H2=G，故H1=G-H=H2。对?a?G，若a?H，则aH=H,Ha=H。否则因为a?G-H，故aH?H,Ha?H。从而aH=Ha=G-H。故H是G的不变子群。43、设H和K都 是G的不变子群。证明：H?K也是G 的不变子群。 证明：因为H和K都 是G的不变子群，所以H?K是G 的子群。对?a?G，h?H?K，有a?h?a-1?a?H?a-1，?h?a-1?a?K?a-1。因为H和K都 是G的不变子群，所以a?h?a-1?H且a?h?a-1?K。从而a?h?a-1?H?K。故H?K是G 的不变子群。44、设群G的中心为C（G）={a?G|?x?G,a?x=x?a}。证明C（G）是G的不变子群。证明：先证C（G）是G的子群。?a,b?C（G），对?x?G,有a?x=x?a ，b?x=x?b。故（a?b）?x= a?(b?x)= a?(x?b)=(a?x)?b=(x?a)?b=x?(a?b), a-1?x=x?a-1。从而a?b，a-1?C（G）。
故C（G）是G 的子群。再证C（G）是G的不变子群。对?a?G，?h?C(G)，记b=a?h?a-1。下证b?C(G)。因为h?C(G)，所以b=(a?h) ?a=（h?a）?a=h?(a?a)=h?C(G)。故C（G）是G的不变子群。 -1-1-145、设&G,?&是没有非平凡子群的有限群。试证：G是平凡群或质数阶的循环群。证明：若G是平凡群，则结论显然成立。否则设&G,?&的阶为n。任取a?G且a?e,记H=（a）(由a生成的G的子群)。显然H?{e}，且G没有非平凡子群，故H=G。从而G一定是循环群，且a是G 的生成元。若n是合数，则存在大于1 的整数k,m，使得n=mk。记H={e,ak,(ak)2,?,(ak)m-1}，易证H是G 的子群，但1&|H|=m&n，故H是G 的非平凡子群。这与已知矛盾。从而n是质数。故G是质数阶的循环群。综上所述，G是平凡群或质数阶的循环群。46、设H和K都是G 的有限子群，且|H|与|K|互质。试证：H?K={e}。 证明：用反证法证明。若H?K?{e}。则H?K是一个元素个数大于1的有限集。先证H?K也是G的子群，从而也是H和K的子群。?a,b? H?K,则a,b? H且a,b?K。因为H和K都 是G的子群，故 a?b,a-1? H且a?b,a-1? K。从而a?b? H?K,a-1? H?K。故H?K是G的子群，从而也是H和K的子群。由拉格朗日定理可知，|H?K|是|H|和|K|的因子，这与已知矛盾。47、素数阶循环群的每个非单位元都是生成元。证明：设&G,*&是p阶循环群，p是素数。对G中任一非单位元a。设a的阶为k,则k?1。5211《离散数学》题库及答案_离散数学习题答案由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。48、若&S,?&是可交换独异点，T为S中所有等幂元的集合，则&T,?&是&S,?&的子独异点。证明：e?e=e，?e?T，即??T是S的非空子集。a,b?T,? &S，?&是可交换独异点,?(a?b)?(a?b)=((a?b)?a)?b=(a?(b?a))?b=（a?(a?b)）?b =((a?a)?b)?b=(a?a)?(b?b) =a?b,即a?b?T。故&T,?&是&S,?&的子独异点。49、设&G,?&是群，且a∈G的阶为n，k∈I，则|ak|＝为k和n的最大公因子。证明：记p=m|p。n(k,n)n(k,n)，其中(k,n),q=k(k,n),｜ak｜＝m。由n和p的定义，显然有(ak)p=e。故m?p且又由于akm=e，所以由定理5.2.5知，n|km。即p|qm。但p和q 互质，故p|m。 由于p和m都是正整数，所以p=m。即｜ak｜＝n(k,n)。50、设&G,?&是有限群，|G|＝n，则?a∈G，|a|?n。证明：?a?G，由封闭性及|G|=n可知a,a2,?,an,an+1中必有相同的元素，不妨设为ak=am,k&m。 由消去律得 am-k=e。从而|a|?m-k?n。51、设G＝(a)，若G为无限群，则G只有两个生成元a和a-1；证明：?b?G＝(a)，则?n?I,使b=an。故b=(a-n)-1=(a-1)-n,从而a-1也是G的生成元。若c是G的生成元，则?k,m?I，分别满足c=ak和a=cm。从而c= (cm)k= cmk。若km?1，则由消去律可知c的阶是有限的，这与|G|无限矛盾。从而km=1，即k=1,m=1或k=-1,m=-1。故c=a或c=a-1。从而G只有两个生成元a和a。-152、设G＝(a)，{e}?H?G，am是H中a 的最小正幂，则 （1）
H＝(am)；（2）
若G为无限群，则H也是无限群；证明：（1）?b?H, ?k?I, 使得b=ak。令k=mq+r, 0?r&m。 则ar=ak-mq=ak?a-mq=b?(am)-q。 因为b,am?H, 且H?G，所以ar?H。由于0?r&m，且a是H中a 的最小正幂，故r=0,即k=mq。 从而b=(a)。故a是H的生成元。（2）因为{e}?H，故H的生成元为am （m?0）。因为G是无限群，所以a的阶是无限的，从而am的阶也是无限的，故H也是无限群。mqmm53、设G＝(a)，|G|＝n，则对于n 的每一正因子d，有且仅有一个d阶子群。因此n阶循环群的子群的个数恰为 n的正因子数。证明：?对n 的每一正因子d，令k=nd,b=ak, H={e,b,b2,?,bd-1}。因为|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。 从而H中的元素是两两不同的，易证H?G。 故|H|=d。所以是G的一个d阶子群。设H1是G的任一d阶子群。则由定理5.4.4知，H1＝(am)，其中am是H1中a 的最小正幂，且|H|=惟一d阶子群。?nm。因为|H|=d，所以m=nd=k，即H=H1。从而H是G的设H是G的惟一的d阶子群。若d=1 ,则结论显然成立。否则H＝(am)，其nm中am是H中a 的最小正幂。由定理5.4.4知，d=。故d是n的一个正因子。54、设h是从群&G1,?&到&G2,?&的群同态，G1和G2的单位元分别为e1和e2，则（1）
h(e1)=e2；（2）
?a?G1，h(a-1)=h(a)-1； （3）
若H?G1，则h(H)?G2；（4）
若h为单一同态，则?a?G1，|h(a)|=|a|。证明：(1)
因为h(e1)?h(e1)=h(e1?e1)= h(e1)= e2?h(e1),所以h(e1)=e2。 (2)
?a∈G1，h(a)?h(a)=h(a?a)= h(e1)= e2, h(a-1)?h(a)=h(a-1?a)= h(e1)= e2,故h(a-1)=h(a)-1。(3)
?c,d∈h(H),?a,b∈H，使得c=h(a),d=h(b)。故c?d=h(a)?h(b) =h(a?b)。因为H?G，所以a?b ∈H ，故c?d∈h(H)。又c-1=(h(a))-1=h(a-1)且a-1∈H，故c-1∈h(H)。由定理5.3.2知h(H)?G2。(4)
若|a|=n,则an=e1。故(h(a))n=h(an)=h(e1)=e2。从而h(a)的阶也有限，且|h(a)|?n。设|h(a)|=m,则h(a)= (h(a))= h(e1)=e2。因为h是单一同态，所以a=e1。即|a|?m。故|h(a)|=|a|。若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。故结论成立。mmm-1-155、有限群G的每个元素的阶均能整除G的阶。证明：设|G|=n，?a?G，则|a|=m。令H={e,a,a2,?,am-1}。则H是G的子群且|H|=m。由Lagrange定理知|H|能整除|G|，故a的阶能整除G的阶。56、证明：在同构意义下，只有两个四阶群，且都是循环群。证明：在4阶群 G中，由Lagrange定理知，G中的元素的阶只能是1，2或4。阶为1 的元素恰有一个，就是单位元e.若G有一个4阶元素，不妨设为a，则G=（a）,即G是循环群 ，从而是可交换群。若G没有4阶元素，则除单位元e外，G的其余3个阶均为2。不妨记为a,b,c。因为a,b,c的阶均为2，故a-1=a,b-1=b,c-1=c。从而a?b?a, a?b?b, a?b?e,故a?b=c。同理可得a?c=c?a=b, c?b=b?c=a, b?a=c。57、在一个群&G,*&中，若G中的元素a的阶是k，即|a|=k，则a-1的阶也是k。证明：因为| a |=k，所以ak=e。即（a-1）k=(ak)-1=e。 从而a的阶是有限的，且|a|?k。 同理可证，a的阶小于等于|a-1|。 故a-1的阶也是k。-1-158、在一个群&G,*&中，若A和B 都是G的子群。若A?B=G，则A=G或B=G。证明：用反证法证明。若A?G且B?G，则有a?A,a?B且b?B,b?A。因为A，B都是G的子群，故a,b?G，从而a*b?G。因为a?A,所以a?1?A。若a*b?A,则b= a?1*(a*b)?A，这与a?B矛盾。从而a*b?A。同理可证a*b?B。综合可得a*b?A?B=G，这与已知矛盾。从而假设错误，得证A=G或B=G。59、设e是奇数阶交换群&G,*&的单位元，则G的所有元素之积为e。证明：设G=&{e,a1,a2,?,a2n},*&，n为正整数。因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2 阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a?1不是它本身，且G中不同的元素有不同的逆元。由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G 是交换群，故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。60、设S=Q?Q，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d)?S,有(a,b)*(c,d)=(ac,ad+b),求出S关于二元运算*的单位元，以及当a?0时，(a,b)关于*的逆元。解：设S关于*的单位元为(a,b)。根据*和单位元的定义，对?(x,y)?S,有(a,b)*(x,y)=(ax,ay+b)=(x,y), (x,y)*(a,b)=(ax,xb+y)=(x,y)。即ax=x,ay+b=y,xb+y=y对?x,y?Q都成立。解得a=1,b=0。所以S关于*的单位元为(1,0)。当a?0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有(a,b)*(c,d)= (ac,ad+b)=(1,0) (c,d)*(a,b)= (ac,cb+d)=(1,0)即ac=1,ad+b=0,cb+d=0。解得c=
所以(a,b)关于*的逆元为(1a1a,d=-baba。,-)。61、设&G,*&是一个群，H、K是其子群。定义G上的关系R：对任意a,b∈G，aRb ?存在 h∈H,k∈K, 使得b=h*a*k，则R是G上的等价关系。证明：?a∈G，因为H、K是G的子群，所以e∈H且e∈K。令h=k=e,则a=e*a*a=h*e*k,从而aRa。即R是自反的。?a,b∈G，若aRb，则存在 h∈H，k∈K, 使得b=h*a*k。因为H、K是G的子群，所以h-1∈H且k-1∈K。故a=h-1*a*k-1,从而bRa。即R是对称的。?a,b,c∈G，若aRb,bRc,则存在 h,g∈H，k,l∈K, 使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。因为H、K是G的子群，所以g*h∈H且k*l∈K。从而aRc。即R是传递的。综上所述，R是G上的等价关系。62、设H是G的子群，则下列条件等价：5211《离散数学》题库及答案_离散数学习题答案（1）
H是G的不变子群；（2）
?a∈G，a?H?a-1?H；（3）
?a∈G，a-1?H?a?H；（4）
?a∈G，?h∈G，a?h?a-1?H。证明：(1)?(2) ?a∈G，则对h∈H,令h1=a?h?a-1，因为a?h ? a?H且H?a=a?H，-1-1所以?h2∈H，使得a?h=h2?a。故h1=（h2?a）?a=h2?H。故 a?H?a?H。(2)?(3) ?a∈G，对h∈H,令h1=a-1?h?a，则（h1）-1= a?h-1?a-1。因为h-1∈H，所以（h1）-1= a?h-1?a-1∈a?H?a-1。由（2）可知（h1）-1∈H,从而h1?H。故a-1?H?a?H 。(3)?(4) 类似于（2）?(3)的证明。(4)?(1) ?a∈G，对?b∈a?H，则?h∈H，使得b=a?h。故b=(a?h) ?(a?a)=(a?h?a)?a。由于a?h?a∈H，所以b∈H?a。即a?H?H?a。 -1-1-1反之对?b∈H?a，则?h∈H，使得b=h?a。故b=(a?a-1)由于a?h?(a)∈H，所以b∈a?H。?(h?a)=a?(a?h?a)=a?(a?h?(a))。-1-1-1-1-1-1-1即H?a?a?H。即H?a=a?H。从而H是G的不变子群。63、在半群&G,*&中，若对?a,b?G，方程a*x=b 和y*a=b都有惟一解，则&G,*&是一个群。证明：任意取定a?G，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对?b?G，记方程y*a=b的惟一解为y。?&G,*&是半群，?运算*满足结合律。?b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对?b?G，记方程a*x=b的惟一解为x。?&G,*&是半群，?运算*满足结合律。?eL*b=eL*(a*x)=(eL*a)*x=a*x=b。从而在半群&G,*&中, 关于运算*存在单位元，记为e。现证G中每个元素关于运算*存在逆元。对?b?G，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。则b*d=(b*c)*b=e*b=b。?b*e=b,且方程b*x=b?b*c=c*b=e。从而有惟一解，?d=e。 c为b关于运算的逆元。综上所述，&G,*&是一个群。64、设&G，*&是群， H和K都是G的子群，令HK={h*s | s∈K，h∈H}, KH={s*h |s∈K,h∈H},&HK,*&，&KH,*&是G的子群的充分必要条件是HK=KH。 证明：?HK是G的子群。?c?HK，则c-1?HK，故存在a?H,b?K ,使得c-1=a?b。因为c=（a?b）-1=b-1?a-1。因为H和K都是G 的子群，所以a-1?H,b-1?K ，即c?KH。从而HK?KH。 ?c?KH，则存在a?H,b?K ,使得c=b?a。因为c=（a-1?b-1）-1。因为H和K都是G 的子群，所以a-1?H,b-1?K ，即a-1?b-1?HK。因为HK是G的子群，所以c=（a-1?b-1）-1?HK。从而KH?HK。故HK=KH。?HK=KH。对?c，d?HK，有a1,a2?H,b1,b2?K ,使得c=a1?b1 ,d=a2?b2。则c?d=( a1?b1)?(a2?b2)=(( a1?b1)?a2)?b2=( a1?(b1?a2))?b2。因为b1?a2?KH=KH，所以存在a3?H,b3?K ,使得b1?a2 =a3?b3。从而c?d=( a1?（b1?a2）?b2=(a1?（a3?b3）)?b2=(a1?a3)?(b3?b2)。因为H和K都是G的子群，故a1?a3?H, b3?b2?K。从而c?d?HK。又c=(a1?b1)=b1?a1。因为H和K都是G的子群，故a1?H, b1?K。从而c-1?KH。因为HK=KH，所以c-1?HK。综上所述，HK是G的子群。 -1-1-1-1-1-165、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 证明：先证HK是G 的子群。对?a?HK，有h?H，k?K，使得a=h?k。因为a=h?k=(h?k?h-1)?h，且K是G 的不变子群，所以h?k?h-1?K。故a?KH。从而HK?KH。同理可证，KH?HK。故HK=KH。从而HK是G的子群。下证HK是G的不变子群。对?a?G，b?HK，有h?H，k?K，使得b=h?k。故a?b?a-1=a?(h?k)?a-1=(a?h?a-1)?(a?k?a-1)。因为H和K都是G的不变子群，所以a?h?a-1?H且a?k?a-1?K。从而a?b?a-1?HK。故HK是G 的不变子群。66、设&G,*&为群，a,b,c?G。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m,n，则c的阶整除m与n的最大公因子(m,n)。证明：设c的阶为k。在a*b=c*b*a两边同时右乘bn?1，再由a*b=c*b*a得a*bn=(c*b*a)*bn?1=(c*b)*(a*b)*bn?2=(c*b)*(c*b*a)*bn?2=(c*b)2*a*bn?2=(c*b)2*(a*b)*bn?3=(c*b)2*(c*b*a)*bn?3=(c*b)3*a*bn?3=?=(c*b)n*a,再由b*c=c*b及b 的阶为n得a=a*bn= (c*b)n*a=(cn*bn)*a=cn*a,所以cn=e。故由元素阶的定义有k|n。由a*b=c*b*a,a*c=c*a,b*c=c*b得a*b=b*a*c，两边同时左乘am?1，再由a*b=b*a*c得am*b=am?1*(b*a*c)= am?2* (a*b)*(a*c)= am?2*(b*a*c)*(a*c)= am?2*b*(a*c)2= am?3*(a*b)*(a*c)2= am?3*(b*a*c)*(a*c)2= am?3*b*(a*c)3=?=b*(a*c)m,再由a*c=c*a及a 的阶为m得b= am*b= b*(a*c)m=b* am * cm=b*cm,所以cm=e。故由元素阶的定义有k|m。由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。（格与布尔代数）67、当n分别是24，36，110时，&Sn,|&是布尔代数吗？若是，则求出其原子集。解：因为|S24|=8，|S36|=9，|S110|=8，故&S36,|&不是布尔代数。在&S24,|&中12没有补元，故它也不是布尔代数。&S110,|&是布尔代数，其原子集为{2,5,11}。68、设L是有界格，且|L|&1。证明：0?1。证明：用反证法证明。设0=1。则任取a?L，则由于L是有界格，故a?1且0?a。即0?a?1。因为0=1且?是L上的偏序关系，所以a=0。这与已知|L|&1矛盾。69、设(L,≤)是格，若a,b,c?L，a≤b≤c，则a?b=b⊙c ,
(a⊙b)?(b⊙c)=(a?b)⊙(a?c)证明：因为a?b?c，所以a?b=a，a?b=b=b，且b=b?c，以c=b?c。从而a?b=b?c。 (a?b)?(b?c)=a?(b?c)=a?(a?b)=(a?a) ?b=a?b=b， (a?b)?(a?c)=(b?c)?(a?c)=b?(c?(a?c))=b?c=b。70、在布尔代数中，证明恒等式a?(a??b)=a?b 证明：a?(a??b)=(a?a?)?(a?b)=1?(a?b)=a?b71、设&L, ?&是格，a1,a2,?,an?L。试证：a1?a2???an= a1?a2???an当且仅当a1=a2=?=an。证明：??显然是成立的。
对任一k=1,2,..,n，a1?a2???an?ak，ak?a1?a2???an。 因为a1?a2???an= a1?a2???an，且?是L上的偏序关系，故ak=a1?a2???an。从而a1=a2=?=an。72、在布尔代数中，证明恒等式(a?c)?(a??b)?(b?c)=(a?c)?(a??b) 证明：((a?c)?(a??b))?(b?c)=((a?c)?(b?c))?((a??b)?(b?c))=(a?b?c)?(a??b?c)=(a?a?)?b?c=1?b?c=b?c,故 b?c?(a?c)?(a??b)，从而(a?c)?(a??b)?(b?c)=(a?c)?(a??b)。73、在布尔代数中，证明恒等式(a?b)?(a??c)?(b??c)=(a?b)?c 证明：(a?b)?(a??c)?(b??c)=(a?b)?((a??b?)?c)=(a?b)?((a?b)??c)=(a?b)?c。74、设&L, ?&是格，a,b,c,d?L。试证：若a?b且c?d，则
a?c?b?d证明：因为a?b，c?d，所以a=a?b,c=c?d。从而(a?c)?(b?d)=((a?c)?b)?d=(b?(a?c))?d=((b?a)?c)?d =a?(c?d)=a?c，所以a?c?b?d。75、当n分别是10,45时，画出&Sn,|&的哈斯图。解：
1176、在布尔代数中，证明恒等式(a?证明：(a?b?)?(b?c?)?(c?a?)=(a?b?c)?(a?b?a?)?(a?c??a?)?(a?c??c)?(b??b?c) ?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a) (b??c??c)?(b??c??a?)?(b??b?a?)=(a?b?c)?(b??c??a?)， (a??b)?(b??c)?(c??a)=(a??b??c?)?(a??b??a)?(a??c?c?)?(a??c?a)?(b?b??c?)5211《离散数学》题库及答案_离散数学习题答案?(b?b??a)?(b?c?c?)?(b?c?a)=(a?b?c)?(a??b??c?)，故(a?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a)。77、设&L,≤&是格，a,b?L，且a≤b，记I[a,b]={x?L|a≤x≤b}则&I[a,b],≤&是&L,≤&的子格。证明：?x,y?I[a,b],a≤x≤b且a≤y≤b。由定理6.1.1有a≤x?y≤b且a≤x?y≤b。从而x?y?I[a,b]且x?y?I[a,b]。故I[a,b] 关于?和?是封闭的，从而&I[a,b]，≤&是&L，≤&的子格。78、设A＝{a,b,c}，求&P(A),?&的子格（P(A)表示A的幂集）。 解：P(A)={?,{a},{b},{c},{a,b},{a,c},{b,c},A}。在P(A)的所有非空子集中，只要它关于?和?是封闭的，则它就是&P(A),?&的子格。显然&P(A),?&和&{?},?&是&P(A),?&的子格。&{?,{a}},?&、&{?,{b}},?&、&{?,{c}},?&、&{?,{a,b}},?&、&{?,{a,c}},?&、&{?,{b,c}},?&、&{?,A},?&、&{?,{c},{a,c},{b,c},A }，?&等都是&P(A),?&的子格。79、证明：在同构意义下，4阶格只有2个。证明：若≤是L上的全序关系，则它一定是良序关系(因为任一有限的全序集一定是良序集)。若设L={a,b,c,d}，则L的四个元素满足：a≤b≤c≤d。若≤不是L上的全序关系，则L中一定存在两个元素（不妨设为b,c），b≤c和c≤b都不成立。因此b?c和b?c既不可能相等，也不可能是b和c。不妨记a=b?c,d=b?c。故&L,≤&的四个元素a,b,c,d满足a≤a,b≤b,c≤c,d≤d,a≤b,a≤c,a≤d,b≤d,c≤d。d
aa80、设&A，?&是有界格，?是A上的全序关系。若|A|＞2，则?a?A-{0,1}，a无补元。证明：用反证法证明。若? a?A-{0,1}，a有补元a'。即a?a'=1，a?a'=0。因为?是A上的全序关系，所以a?a'或a'?a。若a?a'，则a= a?a'=0。若a'?a，则a= a?a'=1。无论如何，这与a?0,a?1矛盾。81、格&L,?,?&是模格??a,b,c?L，有a?(b?(a?c))=(a?b)?(a?c)证明：? ?a,b,c?L，记d= a?c。所以a?d,从而a?(b?(a?c))= a?(b?d)= (a?b)?d=(a?b)?(a?c)。? ?a,b,c?L，若a?c，则c= a?c。所以(a?b)?c= (a?b)?（a?c）= a?(b?(a?c))= a?(b?c)。82、设&L,?,?&是分配格， a,b,c?L。若(a?b)＝(a?c)且(a?b)＝(a?c)，则b＝c。证明：由吸收律、分配律和交换律有b=b?(a?b)＝b?(a?c)=（b?a）?（b?c）=(a?c) ?(b?c)=c?(a?b)= c?(a?c)＝c。83、证明：在有补分配格中，每个元素的补元一定惟一。证明：设&L,?&是一个有补分配格。?a?L,设b和c都是a 的补元，即a?b=1,a?c=1,a?b=0,a?c=0。由吸收律、分配律和交换律有b= b?0＝b?(a?c)=(b?a)?(b?c)=1?(b?c)=b?c,c= c?0=c?(a?b)＝(c?a)?(c?b)=1?(c?b)=c?b。故b=c。从而每个元素的补元是惟一的。84、设&L,?,?&是格，则L是分配格当且仅当?a,b,c?L，有(a?b)?c?a?(b?c)证明：?设L是分配格。对?a,b,c?L，有(a?b)?c=(a?c)?(b?c)因为a?c?a，故(a?c)?(b?c) ?a?(b?c)。从而(a?b)?c?a?(b?c)?对?a,b,c?L，因为a?c?a,a?c? c,a? a?b,b?c? c,b?c? b,b? a?b,所以a?c? a?b，a?c? c，b?c? c,b?c? a?b，从而(a?c)?(b?c)?(a?b)?c。又由已知有(a?b)?c=((b?a)?c)?c?(b?(a?c))?c=((a?c)?b)?c?(a?c)?(b?c)。故(a?b)?c=((a?c)?b)?c?(a?c)?(b?c)。从而L是分配格。85、设&S,?,⊙,′,0,1&是一布尔代数，则&S,＋&是一个交换群，其中＋定义为a+b=(a⊙b′)?(a′⊙b)。证明：?a,b?S，?＜S,?,⊙,′,0,1&是一布尔代数，a+b=(a⊙b′)?? (a′⊙b)= (b⊙a′)?(b′⊙a)=b+a。运算+满足交换律。 ??a,b,c?S，(a+b)+c=((a⊙b′)?(a′⊙b))+c=(((a⊙b′)?(a′⊙b))⊙c′)?(((a⊙b′)?(a′⊙b))′⊙c)=(a⊙b′⊙c′)?(a′⊙b⊙c′) ?((a′?b)⊙(a?b′)⊙c)=(a⊙b′⊙c′)?(a′⊙b⊙c′)?(((a′⊙b′)?(b⊙a))) ⊙c)=(a⊙b′⊙c′)?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(a⊙b⊙c)a+(b+c)=(c+b)+a=(c⊙b′⊙a′)?(c′⊙b⊙a′)? (c′⊙b′⊙a) ?(c⊙b⊙a)=(a⊙b′⊙c′)?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(a⊙b⊙c)=(a+b)+c运算+满足结合律。 ??a?S，?＜S,?,⊙,′,0,1&是一布尔代数，(a′⊙0)= (a⊙1)?0=a。 a+0=(a⊙0′)??0??关于运算+的单位元。 a?S，?＜S,?,⊙,′,0,1&是一布尔代数，a+a=(a⊙a′)?(a′⊙a)=0?0=0。a是a关于运算+的逆元。 ? ?综上所述，&S,＋&是一个交换群。86、设&S,?,⊙,′,0,1&是一布尔代数，则R={&a,b& | a?b=b}是S上的偏序关系。证明：?? a?S，??满足等幂律，? a?a=a，故aRa。即R是自反的。 a,b?S，若aRb且bRa,? ?满足交换律，? b=a?b=b?a=a。即R是反对称的。?a,b,c?S，若aRb且bRc,? ?满足结合律，? c=c?b=c?（b?a） =(c?b)?a=c?a,故aRc。即R是反对称的。综上所述，R={&a,b& | a?b=b}是S上的偏序关系。87、设&S,?,⊙,′,0,1&是一布尔代数，则关系?={&a,b& | a⊙b=a}是S上的偏序关系。证明：??a?S，因为⊙满足等幂律，所以a⊙a=a，故a?a。即?是自反的。 a,b?S，若a?b且b?a,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即?是反对称的。?a,b,c?S，若a?b且b?c,因为⊙满足结合律，因为a=a⊙b=a⊙(b⊙c)=(a⊙b)⊙c=a⊙c,故a?c。即?是反对称的。综上所述，?={&a,b& | a⊙b=a}是S上的偏序关系。（图论部分）88、证明在有n个结点的树中，其结点度数之和是2n-2。证明：设T=&V,E&是任一棵树，则|V|=n，且|E|=n-1。由欧拉握手定理，树中所有结点的度数之和等于2|E|.从而结点度数之和是2n-2。88、任一图中度数为奇数的结点是偶数个。证明：设G=〈V,E〉是任一图。设|V|=n。由欧拉握手定理可得 ?deg(v)=2|E|可得，图中所有结点度数之和是偶数。v?V显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。证明：不对。反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。90、设T=&V,E&是一棵树，若|V|&1，则T中至少存在两片树叶。 证明：（用反证法证明）设|V|=n。因为T=〈V,E〉是一棵树，所以|E|=n-1。5211《离散数学》题库及答案_离散数学习题答案由欧拉握手定理可得 ?deg(v)=2|E|=2n-2。v?V假设T中最多只有1片树叶，则?deg(v)?2(n-1)+1&2n-2。v?V得出矛盾。91、画一个使它分别满足： (1) 有欧拉回路和哈密尔顿回路； (2) 有欧拉回路，但无条哈密尔顿回路； (3) 无欧拉回路，但有哈密尔顿回路； (4) 既无欧拉回路，又无哈密尔顿回路。解?92、设无向图G=&V,E&，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？解：设G中度数小于3的顶点有k个，由欧拉握手定理
24=?deg(v)v?V知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。93、设图G=&V,E&，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知2m=?deg(v)=knk+(k+1)(n-nk)=(k+1)n+-nkv?V故nk=(k+1)-2m。94、设G=&V,E&是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。证明：(用反证法证明） 设|V|=n，则|E|=n-1。由欧拉握手定理可得 ?deg(v)=2|E|=2n-2。v?V因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则?v?Vdeg(v)?2n&2n-2。得出矛盾。95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。证明：（用反证法证明）设G=&V,E&有n-1条边且|V|=n。 由欧拉握手定理可得 ?deg(v)=2|E|=2n-2。v?V因为G是连通图，所以G中任一结点的度数都大于等于1。假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故?v?Vdeg(v)?2(n-1)+1&2n-2,得出矛盾。96、若G有n个结点，m条边，f个面，且每个面至少由k(k?3)条边围成，则
m?k(ｎ－2)／(ｋ－2)。证明：设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。
由已知对任一f?F, deg(f)?k。由公式?deg(f)=2|E|可得，2|E|?k|F|。f?F再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+即k(n-2)?(k-2)m。所以m?k(ｎ－2)／(ｋ－2)。2k|E|?2。97、设G=&V,E&是连通的简单平面图，|V|=n?3，面数为k,则k?2n-4。证明：记|E|=m。因为G=&V,E&是连通的简单平面图，故每个面的度数都不小于3。从而由公式?deg(f)=2|E|可得f?F3k?2m再由欧拉公式|V|-|E|+|F|=2有
m=n+k-2 及32k?n+k-2故
k?2n-4。98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。证明：若结点个数小于等于3时，结论显然成立。 当结点多于3 个时，用反证法证明。 记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得?deg(v)=2|E|得
5n?2m。v?V又因为G=〈V,E,F〉是一个连通简单无向平面图， 所以对每个面f,deg(f)?3。 由公式?deg(f)=2|E|可得，2m?3k。f?F再由欧拉公式|V|-|E|+|F|=2可得2?从而30?m,这与已知矛盾。25m-m+23m=115m99、在一个连通简单无向平面图G=〈V，E，F〉中若|V|?3，则 |E|?3|V|－6。证明：?|V|?3，且G=〈V，E，F〉是一个连通简单无向平面图，?d(f) ?3，?f?F。f?F由公式?deg (f)=2|E|可得，2|E|?3|F|。 再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+?|E|?3|V|－6。23|E|?2。100、给定连通简单平面图G=&V,E,F&，且|V|=6, |E|=12, 则对于任意f?F, d(f)=3。证明：因为|V|=6?3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f?F，deg(f)?3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式?deg(f)=2|E|，?deg(f)=24。f?Ff?F因为对任一f?F，deg(f)?3，故要使上述等式成立， 对任一f?F，deg(f)=3。101、设G=&V,E&是n个顶点的无向图(n&2)，若对任意u,v?V，有d(u)+d(v)?n，则G是连通图。证明：用反证法证明。若G 不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|-2=n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则
d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2 =n-2&n，这与已知矛盾。 故G是连通图。102、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？证明：可以。将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。103、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。证明：将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。则原命题相当于在该无向图中一定存在两个顶点的度数相等。设该简单无向图中有n个顶点，则图中n个顶点的度数只能为0，1，2，?，n-1。若图中有两个或两个以上的顶点度数为0，则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相等。设该简单无向图中n个顶点中任何一对顶点的度数都不相等，即这n个顶点的度数两两不同。但每个顶点的度数只能是1,2,?,n-1这n-1个数中的某一种，这显然产生了矛盾。因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。104、设有如下有向图G=&V,E&，（1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？5211《离散数学》题库及答案_离散数学习题答案解：?1?1（1） A=??0??0100011010??2??012?，A=??01???0??0?32?213A=??00??0021101??1? 0??1?320074104??3? 0??1?2??5??134?，A=??01???0??0（2） G中v1到v4的长度为4 的通路有4条； （3） G中经过v1的长度为3 的回路有3条；（4） G中长度不超过4 的通路有72条，其中有19条回路。v3105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。解：a
?f在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。在这个有向图中d(a)=3,d(b)=4, d(c)=3, dd?(b)=2,d?(c)=1, d?(a)=2。ad
?e?cb?f?(a)=2, d?(a)=1, d?(b)=2 ,106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。解：它的一个子图它的一个生成子图由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图由顶点集{a,b,d,f}诱导出的子图107、求下列赋权图顶点间的距离。?
?f解：d(a,b)=3, d(a,c)=3, d(a,d)=?, d(a,e)=8, d(a,f)=16,d(b,c)=1, d(b,d)=?, d(b,e)=6, d(b,f)=13, d(c,d)=?, d(c,e)=5, d(c,f)=12, d(d,e)=?, d(d,f)=?, d(e,f)=7,108、求下列赋权图中v1到其他顶点的距离。6解：S
4 {v1, v2, v3}
6 {v1,v2, v3, v5}
7 {v1,v2, v3, v5, v4}
9 {v1,v2, v3, v5, v4, v6}故v1到v2, v3, v4, v5, v6的距离分别是3，4，7，6，9。109、求下图的可达矩阵。解：该图的邻接矩阵为?1??1A=?0?0???010100201000000010??0?0? 1??0??1200010100000100??0?0? 0??1??则?1??12A=?0?0??0?1010001000000010??0?0? 1??0???2??1=?1?0??0??3??33A=?1?0???0?6??44A=?3?0???031200451000??0?0?
1??0??0??0?0? 0??1??故图的可达矩阵为?1??1P =?1?0???0111001110000??00?00? 11??11??110、求下列图的生成树。解：下面是它的两棵生成树：111、在一个有n个顶点的G=&V,E&中，u,v?V。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。证明：设v0e1v1e2?el vl是从u=v0到v=vl的长为l的通路。5211《离散数学》题库及答案_离散数学习题答案若l?n-1，则结论显然成立。否则因为l+1&n，故v0，v1，?，vl中必有一个顶点是重复出现的。不妨设vi=vj(0?i&j?l)，则新通路v0e1v1e2?viej+1vl+1ej+2vj+2?elvl是一条从u 到v的通路，且此通路长度比原通路长度至少少1。若新通路的长度?n-1，则结论得证。否则对新通路重复上述过程，必可以得到一条从u到v的长为n-1的通路。112、设简单平面图G中顶点数n=7，边数m=15。证明：G是连通的。证明：设G具有k个连通分支G1，G2，?，Gk。设Gi的顶点数为ni，边数为mi，i=1,2,?,k。 先证每个连通分支的顶点数都大于1。否则说明G中有孤立结点。由于G是简单图，从而要使G的边数是15，则G只有两个连通分支，其中一个是由孤立结点导出的，另一个是K6。但K6不是平面图，故要每个连通分支的顶点数都大于1。同理可证，每个连通分支的顶点数都大于2。 由此可得，G的每个连通分支至少有3 个顶点。从而
mi?3ni-6kk即m=?mi?i?1?(3ni?1i?6)=3n-6k从而15?21-6k，即k?1。从而k=1，故G是连通图。113、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？解：设它有k个1度顶点，则由欧拉握手定理?v?Vdeg(v)=2|E|可得 2|E|=k+4+3+12=k+19。再由于它是一棵树，故|E|=k+2+1+3-1=k+5从而2(k+5)=k+19, k=9。故它有9个1度顶点。114、有向图G是强连通的?G中有一回路，它至少通过每个顶点一次。证明：?设G=&V,E&是强连通图。任取u,v?V，则u和v相互可达，即从u到v有路径P1，从v到u有路径P1。故从P1和P2首尾相接可得到一条经过u和v的回路C1。若C1经过G中所有顶点至少一次，则C1就是满足结论要求的回路。否则若C1没有经过顶点w，则类似地我们可得到一条经过u和w的回路C2。从C1和C2我们可得到一条经过更多顶点的回路C（先从u经过P1到v,再从v经过C2回到v,再从v3经过P2回到u）。对C3重复上述过程，直到得到一条经过所有顶点的回路为止。?若G中存在一条经过G中所有顶点至少一次的回路，则G中任意两个顶点是相互可达的，从而G是强连通的。115、一个有向图是单向连通图? 它有一条经过所有结点的路。证明：?设G=&V,E&是单向连通图。任取u,v?V，则u可达v或v可达u。不妨设u可达v，即从u到v有路径P1。若P1经过G中所有顶点至少一次，则P1就是满足结论要求的路径。否则若P1没有经过顶点w，则如果v经过路径T可达w, 连接P1和T我们可得一条经过P1经过的所有顶点及w的更长的路径P2；否则若w经过路径S可达u，连接S和P1我们也可得一条经过w及P1经过的所有顶点的更长的路径P2；再否则我们一定可以找到P1经过的两个相邻顶点t和s，t到s有边，t经过路径T1 可达w，w经过路径T2可达s（否则就与u可达w，w可达v矛盾），我们构造这样一条路径P2：从u出发经过P1到达t,t经过路径T1到达w，再从w出发经过路径T2到达s，然后从s出发经过P1到达v。这是一条经过w及P1所经过的所有顶点的更长的路径。
T2?w对P2重复上述过程，直到得到一条经过所有顶点的路径为止。?若G中存在一条经过G中所有顶点至少一次的路径，则G中任意两个顶点中至少有一个可达另一个，从而G是单向连通的。寄语： 希望大家能在考试中取到好的成绩，谢谢！欢迎您转载分享：
更多精彩：