离散数学-习题集

第一章算法基础习题1、写出在n个整数中，寻找最小整数的算法。2、写出在n个整数中，寻找最大整数的算法。3、写出在n个整数中，判定是否有相等的数。4、写出针对一个字符串，统计出个字母出现的次数的算法。5、写出判定一个数是奇数还是偶数的算法。6、给定一个整数数组：„,S=s1,s2,s3,sn个关键整数key和一写出在S中找出key的位置的算法，如key在S中不存在，则输出0.7、判断下列程序中x=x+1执行次数的O(f(n))：a:fori=1to2nx=x+1;b:i=1;while(i<=2n){x=x+1;i=i+2;}c:fori=1tonforj=1tonx=x+1;d:fori=1tonforj=1toix=x+1e:i=n;while(i>=1){forj=1tonx=x+1i=[i/2]小于i除以2的最大整//数0

}第二章集合与序列习题1、集合A={1，2，3，4，5，6，7，8，9，10}B={2，4，6，8，10}，C={1，3，5，7，9}，D={3，6，9}。求：A∩B(A-C)∩BA-D)∩BC∪D)∩C2、设全集为为集合U={1,2,3,列出下列集合的元素。A∩(B∪C)„,10}，A={1,4,7,10}，B={1,2,3,4,5}，C={2,4,6,8}，(A∩B)-C3、给定序列A=12345678,判定下列哪些序列是A的子序列B1=1，3，5B2=1,2,4,3B3=5,4,3,2,1B4=2468B5=876543B6=35428B7=23456B8=2344、给定字符串A=12345678,判定下列哪些串是A的子串B1=1，3，5B2=1,2,4,3B3=5,4,3,2,1B4=2468B5=876543B6=35428B7=23456B8=2345、5、对于矩阵1

24A42321B43435计算矩阵C=AXB。第三章习题1、在下列练习中，关系R定义在集合{1，2，3，4，5}上，规则为：如果3整除x-y，则(x，y)∈R。1)列出R的元素。2)列出R-1的元素。3)判定R的性质（自反、对称、反对称、传递、某种次序关系）2、设集合<1，2，3，4，5}上关系R的定义规则为：如果x+y≤6，则(x，y)∈R。1)列出R的元素。2)列出R-1的元素。3)判定R的性质（自反、对称、反对称、传递、某种次序关系）3、设集合<l，2，3，4，5}上关系R的定义规则为：如果x＝y—1，则(x，y)∈R。1)列出R的元素。2)列出R-1的元素。3)判定R的性质（自反、对称、反对称、传递、某种次序关系）4、在下列练习中，判断定义在正整数集上的各关系是否是自反的、对称的、反对称的、传递的，同时或仅是一个偏序。1)如果x＝y，则2(x，y)∈R。2)如果x>y，则(x，y)∈R。3)如果x≥y，则(x，y)∈R。4)如果x＝y，则(x，y)∈R。5)如果3整除x-y，则(x，y)∈R。5、设X是所有4bit字符串(例如0011，010，1000)的集合。在X上定义关系R：如果5l的某个长度为2的子字符串等于s2的某个长度为2的子字符串，则s1Rs2。例如：0111R1010(因为0111和1010都含有子字符串01)。ll0R0001(因为1110和0001不含共同的长度为2的子字符串)。这个关系是自反的吗?是对称的吗?是反对称的吗?是传递的吗?同时或仅是一个偏序吗?6、设R和S是X上的关系。判断下列练习中的陈述是否成立。如果陈述不成立，给出一个反例2

1)如果R和5是传递的，则R∪S是传递的。2)如果R和S是传递的，则R∩S是传递的。3)如果R和S是传递的，则RoS是传递的。4)如果R是传递的，则R-1是传递的。5)如果R和S是自反的，则R∪S是自反的。6)如果R和S是自反的，则R∩S是自反的。7)如果R和S是自反的，则RoS是自反的。8)如果R是自反的，则R-1是自反的。9)如果R和S是对称的，则R∪S是对称的。10)如果R和S是对称的，则R∩S是对称的。11)如果R和S是对称的，则RoS是对称的。12)如果R是对称的，则R-1是对称的。13)如果R和S是反对称的，则R∪S是反对称的。14)如果R和S是反对称的，则R∩S是反对称的。15)如果R和S是反对称的，则RoS是反对称的。16)如果只是反对称的，则R-1是反对称的。7、关系R定义在由实数集的所有非空子集构成的集合上，如果对任意的ε>0，存在a∈A和b∈B使得|a-b|<ε，则(a，b)∈R。判断R是否是自反的、对称的、反对称的、传递的，同时或仅是某种类型的次序关系。8、在下列练习中，判断给出的关系是否是{1，2，3，4，5}上的等价关系。如果关系是一个等价关系，列出等价类。{(，1)，(2，2)，(3，3)，(4，4)，(5，5)，(1，3)，(3，1)}1){(1，1)，(2，2)，(3，3)，(4，4)，(5，5)，(1，3)，(3，1)，(3，4)，(4，3)}2){(1，1)，(2，2)，(3，3)，(4，4))3){(1，1)，(2，2)，(3，3)，(4，4)，(5，5)，(1，5)，(5，1)，(3，5)，(5，3)，(1，3)，(3，1)}4){(x，y)，1≤x≤5，1≤y≤5}5){(x，y)|4整除x-y}6){(x，y)|3整除x+y}7){(x，y)|x整除2-y}9．设A=(1，2，3，4，5，6}，A上的二元关系R={(1，1)，(2，2)，(3，3)，(3，4)，(4，4)，(5，3)，(5，4)，(5，5)}，试求：(1)写出R的关系矩阵和关系图；(2)并画出哈斯图，判定R是A上的何种次序关系。1、确定以下各题的f是否为从A到B的函数，并对其中的函数f:A-->B指出它是单射、满射或双射?如果不是，请说明理由A=(1，2，3，4，5}，B={6，7，8，9，10}，f={(1，8)，(3，9)，(4，10)，(2，6)，3

(5，9)}。A=(1，2，3，4，5}，B={6，7，8，9，10}，f={(1，8)，(3，10)，(2，6)，(4，9)}。B为实数集，f(x)=x2-x;。B为实数集,f(x)=x3;。B为实数集，f(x)=1/x。B为正整数集，f(x)=x+1。A，B同正整数集,f(x)=1x=1f(x)=x-1x>1第四章逻辑与证明习题1将下列语句用命题公式表示：(1)明天晴到多云，西北风四—五级，有时六级。(2)她既长得不漂亮又不文雅。(3)若要人不知，除非己莫为。(4)没有共产党就没有新中国。(5)黄色染料与红色染料合成为棕色或橙色染料。(6)天黑了，外面有狼，你还是在这里过一宿吧。(7)不劳动者不能食。(8)你去不去都没有关系。(9)我没有去接你是不对的，而你没有等我也是不对的。(10)南京热，重庆热。南京与重庆都热，没有不热的南京，也没有不热的重庆。2、对于P＝F，Q＝TR=F，计算练习下面的每个命题的真值。P∨QP∨QP∨QP∨(Q∧R)(P∨Q)∧(P∨R)(P∨┐R)∧┐((Q∨R)∨┐(R∨P))3、写出练习19～26中每个命题的真值表。P∧Q(P∨Q)∨P4

(P∨Q)∧P(P∧Q)∧P(P∧Q)∨(P∨q)(P∧Q)∨(r∧P)(P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q)(P∧Q)∨(Q∨r)4、在下列练习中，用文字表示符号表达式，设P：我学习计算机科学，Q：我学习数学。P→QP∧QP∨Q5、在练习36～40中，用文字表示符号表达式，设P：今天是星期一，Q：天正在下雨，R：天气热。P∨QP∧(Q∨R)P∨Q∧R(P∧Q)∧(R∨P)(P∧(Q∨R))∧(R∨(Q∨P))6、用符号表示练习41～46中的命题，设P：有飓风，Q：正在下雨。没有飓风。有飓风并且正在下雨。有飓风但是没有下雨。没有飓风也没有下雨。或者有飓风，或者正在下雨(或者又有飓风又下雨)。或者有飓风，或者正在下雨但是没有飓风。7、用符号表示练习下面的句子，设P：你听过FlyinQPiQs"摇滚音乐会，Q：你听过"Y2K"摇滚音乐会，R：你耳鼓疼。你听过"FlyinQPiQs"你听过"FlyinQPiQs"你听过"FlyinQPiQs”摇滚音乐会，你听过"Y2K"摇滚音乐会，并且你耳鼓疼。你或者听过"FlyinQPiQs"摇滚音乐会，或者听过"Y2K"摇滚音乐会，但是你没有耳鼓摇滚音乐会，并且你耳鼓疼。摇滚音乐会，但是你没有耳鼓疼。疼。你没有听过"FlyinQPiQs"摇滚音乐会，并且也没有听过"Y2K”摇滚音乐会，但是你耳鼓疼。下面的说法不对：或者你听过"FlyinQPiQs"摇滚音乐会，或者你听过"Y2K"摇滚音乐会，或者你没有耳鼓疼。在练习中，用条件命题的形式重新描述每个命题。Joey将通过离散数学考试，如果他学习努力。Rosa可以毕业，如果她获得160学分。5

Fernando购买一台计算机的必要条件是他得到2000美元。Katrina选修算法课程的充分条件是她学过离散数学。当制造更好的汽车时，Buick会制造它们。当老师讲课时，学生会睡觉。几只有程序具有良好的结构，才是可读的。写出练习9的每个命题的逆命题。写出练习9的每个命题的逆否命题。12、设P和r为假，Q和‘为真，给出练习中每个命题的真值。P→QP→QP→Q(P→Q)∧(Q→r)(P→Q)→rP→(Q→r)(s→(P∧r))∧((P→(r∨Q))∧s)((P∧Q)+(Q∧r))→(s∨┐Q)13、在练习32～37中，用文字表示符号表达式P:今天是星期→Q：天正在下雨r：天气热P→QQ→(r∧P)P→(Q∨r)P∨Q→r(P∧(Q∨r))→(r∨(Q∨P))(P∨(┐P∧┐(Q∨R)))→(P∨┐(R∨Q))14、对练习中的每对命题P和Q，说明是否有P=Q。P=P，Q＝P∨QP=P∧Q，Q＝P∨QP＝P→Q，Q=┐P∨QP＝P∧(Q∨r)，Q＝P∨(Q∧r)P＝P∧(Q∨r)，Q＝(P∨Q)∧(P∨r)P＝P→q，Q=q→pP=(P→q)∧(Q→R)，Q＝P→RP＝(P→Q)→r，Q=P→(q→R)15、用符号表示练习11—15的证明过程，并说明每个证明过程是否有效。设P：我努力学习。Q：我的成绩是A,r：我发财了。6

1）如果我努力学习，则我的成绩是A。我努力学习结论：我的成绩是A2）如果我努力学习，则我的成绩是A结论：我发财了3）我努力学习当且仅当我发财了。我发财了结论：我努力学习4)如果我努力学习或者如果我发财了，则我的成绩是A。结论：如果我不努力学习，则我发财了5)如果我努力学习，则我的成绩是A或者我发财了。我的成绩不是A且我没有发财结论：我不努力学习16使用归结法导出练习的结论。提示：在练习中，使用逻辑等价表达式“或”和“与”替换。1）P∨Q∨RQR结论：P2）P∨RR∨QP结论：Q3）P∨JQ∨JR∨U结论：P∨Q∨r∨Us∨t∨u4）P→QP∨Q结论：Q17、设谓词p(x，y)表示“x等于y”，个体域D={1,2，3}。求下列各式的真值。xP(x,3)yP(1,y)xyP(x,y)xyP(x,y)xyP(x,y)7

yxP(x,y)18令谓词P(x，y)表示“x访问过y”，其中x的个体域是学校全体学生，y的个体域是所有网站的集合。用自然语言表达下列各式。(1)P(方元，WWW．hziee．edu．cn)。(2)xP(x，www．google．com)。(3)yP(冯娟，y)。(4)y(P(吴笛，y)∧P(钱华，y))。(5)yz(y<>黄帅∧(P(黄帅，z)→P(y，z)))。(6)xyyz((x<>y)∧(P(x，z)→P(y，z)))19令谓词P(x)表示“x说德语”，Q(x)表示“x了解计算机语言C++”，个体域为计算机应用专业全体学生的集合。用P(x)、Q(x)、量词和逻辑连接词符号化下列语句。(1)计算机应用有个学生既会说德语又了解C++。(2)计算机应用有个学生会说德语，但不了解C++。(3)计算机应用所有学生或会说德语，或了解C++。(4)计算机应用没有学生会说德语或了解C++．假设个体域为全总个体域，谓词M(x)表示“x是计算机应用学生”。用P(x)、Q(x)、M(x)、量词和逻辑连接词再次符号化上面的4条语句。20令谓词P(x，y)表示“x爱y”，个体域是全世界所有人的集合。用户(x,y)、量词和逻辑连接词符号化下列语句。(1)每个人都爱王平。(2)每个人都爱某个人。(3)有个人人都爱的人。(4)没有人爱所有的人。(5)有个张键不爱的人。(6)有个人人都不爱的人。(7)恰有一个人人都爱的人。(8)成龙爱的人恰有两个。(9)每个人都爱自己。(10)有人除自己以外谁都不爱。21．令谓词P(x，y)表示“x给y发过电子邮件”，Q(x，少)表示“x给y打过电话”，个体域是实验班所有同学。用P(x，y)、Q(x，y)、量词和逻辑连接词符号化下列语句。(1)周叶从未给李强发过电子邮件。(2)方芳万华发过电子邮件，或打过电话。(3)实验班每个同学都给余涛发过电子邮件。(4)实验班没有人给吕键打过电话。8

(5)实验班每个人或给肖琴打过电话或给她发过电子邮件。(6)实验班有个学生给班上其他人都发过电子邮件。(7)实验班有个学生给班上其他人或打过电话，或发过电子邮件。(8)实验班有两个学生互发过电子邮件。(9)实验班有个学生给自己发过电子邮件。(10)实验班至少有两个学生，一个给另一个发过电子邮件，而另一个给这个打过电话。9

第五章图论习题1、在下列练习中，画出给定特征的图或解释为什么这种图不存在a)具有6十顶点，每个顶点的度为3．b)只有5个顶点，每个顶点的度为3。c)具有5个顶点，每个顶点的度为1。d)具有6个顶点，4条边。e)具有4条边，4十度分别为1，2，3，4的顶点．f)具有4个度分别为1，2，3，4的顶点．g)一个具有6个顶点度分别为l，2，3，4，5，5的简单图：h)一个具有5个顶点度分别为2，3，3，4，4的筒单图．i)一个具有5个顶点度分别为2，2，4，4，4的简单图。2、写出以下图形的邻接矩阵，并判定其类型：无向图、有向图、权重图、二部图、欧拉图、连通图、完全图。V1V1V2V5V4V2V3V5V4V3abV1V1V4V2V5V3V3V4V2cd10V18V4V127V2V3V35V3V2ef3、根据以下图形的邻接矩阵，画出其图形，并判定其类型：无向图、有向图、权重图、二部图、完全二部图、欧拉图、连通图、完全图。0111101111011101045101001d10111010010100a001b306c110111032011100111100010001000e4、判断图B-E中那些是图A的子图。V1V5V3V2V4A11V1V1V5V5V2V2V3V3BCv1v2v3v1011v2v3101110Dv1v2v3v1011v2110010Ev35、在什么情况下一个完全图Kn中包含一个Euler回路，并说明理由。6、在什么情况下一个完全二部图Kmn包含一个Euler回路，并说明理由。12第六章网络模型习题1、在下面的网络中，计算没有标出的流量。6,?b4,4Rw16,59,?8,?6,55,?7,3zacw2w38,?5,?4,38,?3,?dS2计算第一题图的最大流量。3在一个计算机网路中，从计算机A到计算机C点可以直通，也可以经过计算机B。A到B带宽是2M，B到C带宽1M，A到C带宽是3M。请画出从A到C的网络图，写出其并计算一小时间可下载的最大字节数。4写出下面网络图的容量矩阵和流量矩阵。2,2db4,34,23,25,3az2,1ec2,25、对于下面的网络模型，计算：A=_____B=_____13C=_____D=_____该网络的最大流量是：_____第七章代数系统习题1、下面所述数的加、减、乘、除是否为集合上的二元运算：实数集R；非0实数集：R*=R-{0}正整数集Z+奇整数集A={2n+1|n∈Z)2、下面所述数的加与乘是否在集合上封闭：A={0，1}B={一1，1}C=(x|x为复数，且|x|=1}D={Ix|x为素数}3、设s={x|x为素数且x<100}，在S上定义二元运算*如下，试问这四个(S,*)是否构成代数系统?x*y=max(x，y)x*y二min(z，y)x*y=lcm(x，y)x*y=gcm(x，y)(lcm与gcm分别表示最小公倍数与最大公约数)4、设B={a，b，c，d}上的二元运算定义如下表，设S1={b，d}，S2={b，c}及S3={a，c，d}，试问(S1，*，o)，(S2，*，o)及(S3，*，o)是否为(B，*，o)的子代数?*abcdaabcdbbbddccdcddddddoabcdaaaba14bababcaacddabcd5、设有集合S与二元运算*，试证明下列4个中哪几个构成代数系统?S=R,a*b=abS={1,2,...,8},a*b=lcm(a,b)S={1,-1,2,3,-3,4,5},a*b=|b|S=Z,a*b=|a-b|6、在R上定义如下运算：(对x，y∈R)，分别判定是否满足结合律?交换律?是否有单位元、逆元?x*y=x+y-xyxoy=1/2(x+y)x&y=x+1/2y7、设有实数集R上的运算。定义如下：a*b=a+b+2ab试回答如下问题：(R，*)