篇一 : 5211《离散数学》题库及答案

《离散数学》题库与答案

1、下列哪些公式为永真蕴含式？( )

答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）

2、下列公式中哪些是永真式？( )

3、设有下列公式，请问哪几个是永真蕴涵式?( )

答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式

答：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) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！

答：（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?Q

8、设个体域为整数集，则下列公式的意义是( )。

答：（1）对任一整数x存在整数 y满足x+y=0

（2）存在整数y对任一整数x满足x+y=0

9、设全体域D是正整数集合，确定下列命题的真值：

答：（1） F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2） F （同理） （3）F （同理） （4）T（对任一整数x存在整数 y满足条件 y=2x 很明显是正确的）

答：（1）（在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了）

11、命题“2是偶数或-3是负数”的否定是（ ）。

答：2不是偶数且-3不是负数。

12、永真式的否定是（ ）

答：?P ，Q?P（考查分配率和蕴含等值式知识的掌握）

15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。

16、设A={a,{a}}，下列命题错误的是（ ）。

17、在0（ ）?之间写上正确的符号。

答：(4)（空集没有任何元素，且是任何集合的子集）

18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。

答：32（2的5次方 考查幂集的定义，即幂集是集合S的全体子集构成的集合）

答：（3）（Q是集合R，P只是R中的一部分，所以P是Q的真子集）

20、下列各集合中，哪几个分别相等( )。

21、若A-B=Ф，则下列哪个结论不可能正确？( )

答：（4）（差集的定义）

22、判断下列命题哪个为真?( )

(3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B 答：（1）（考查空集和差集的相关知识）

23、判断下列命题哪几个为正确？( )

24、判断下列命题哪几个正确？( )

26、判断下列命题哪几个正确？( )

(4) 若A为非空集，则A?A∪A成立。

27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：

29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系

30、集合A上的等价关系的三个性质是什么？( )

答：自反性、对称性和传递性

31、集合A上的偏序关系的三个性质是什么？( )

答：自反性、反对称性和传递性(题29，30，31全是考查定义)

33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {( )}

求R和R-1的关系矩阵。

5211《离散数学》题库及答案_离散数学习题答案

(1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 答：（2）（考查自反 对称 传递的定义）

答：2，6（单位元和零元的定义，单位元：e。x=x 零元：θ。x=θ）

39、设〈G,*〉是一个群，则

答： （1） a?1?b （2） b （考查群的性质，即群满足消去律）

40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。 答： 6,4

答：单位元（由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为一个生成元。并且一元素的阶整除群的阶）

答：单位元，1 （在群<G,*>中，除幺元即单位元e外不可能有任何别的幂等元）

44、素数阶群一定是( )群, 它的生成元是( )。

答：循环群，任一非单位元（证明如下：任一元素的阶整除群的阶。现在群的阶是素数p，所以元素的阶要么是1要么是p。G中只有一个单位元，其它元素的阶都不等于1，所以都是p。任取一个非单位元，它的阶等于p，所以它生成的G的循环子群的阶也是p，从而等于整个群G。所以G等于它的任一非单位元生成的循环群）

45、设〈G,*〉是一个群，a,b,c∈G，则

47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。 答：1，单位元，0

48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。 答：k

49、在自然数集N上，下列哪种运算是可结合的？（ ）

50、任意一个具有2个或以上元的半群，它（ ）。

(1) 不可能是群 (2) 不一定是群

51、6阶有限群的任何子群一定不是（ ）。

52、下列哪个偏序集构成有界格（ ）

答：(4)（考查幂集的定义）

53、有限布尔代数的元素的个数一定等于（ ）。

54、设G是一个哈密尔顿图，则G一定是( )。

答：(4)（考察图的定义）

55、下面给出的集合中，哪一个是前缀码？( )

56、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )答：以v为起点的边的条数， 以v为终点的边的条数

58、设G是一棵树，则G 的生成树有( )棵。

59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。

60、一棵无向树的顶点数n与边数m关系是( )。

61、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次

62、有n个结点的树，其结点度数之和是( )。

答：2n-2（结点度数的定义）

63、下面给出的集合中，哪一个不是前缀码( )。

64、n个结点的有向完全图边数是( )，每个结点的度数是( )。 答：n(n-1),2n-2

65、一个无向图有生成树的充分必要条件是( )。

66、设G是一棵树，n,m分别表示顶点数和边数，则

67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 答：2

68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:

70、设T是一棵树，则T是一个连通且( )图。

71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

74、任一有向图中，度数为奇数的结点有( )个。

75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？

76、在有n个顶点的连通图中，其边数（ ）。

77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。

78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。

5211《离散数学》题库及答案_离散数学习题答案

79、下列哪一种图不一定是树（ ）。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图

(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图

80、连通图G是一棵树当且仅当G中（ ）。

(1) 有些边是割边 (2) 每条边都是割边

(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

二、求下列各公式的主析取范式和主合取范式：

?(?P??Q??R)（原公式否定的主合取范式）

解：P→Q??P?Q（主合取范式）

解： P??Q （主合取范式）

（原公式否定的主析取范式）

5211《离散数学》题库及答案_离散数学习题答案

(原公式否定的主合取范式)

（3） R （1），（2）

（7） Q （1），（5）

（8） S （3），（6）

（4） Q→R （1），（3）

（5） R （2），（4）

（7） Q→S （5），（6）

（8） S （2），（7）

（5） P （3），（4）

5211《离散数学》题库及答案_离散数学习题答案

17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ)

列出两个公式的真值表：

由定义可知，这两个公式是等价的18、P→Q?P→(P?Q)

先求出左右两个公式 的主合取范式

它们有一样的主合取范式，所以它们等价。

21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?

前提: (1) 若A队得第一，则B队或C队获亚军;

(2) 若C队获亚军，则A队不能获冠军;

(3) 若D队获亚军，则B队不能获亚军;

结论: (5) D队不是亚军。

设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A?（B?C），C??A，D??B，A；结论符号化为 ?D。

（6） B （3），（5）

四、设Ａ，Ｂ，Ｃ是三个集合，证明：

5211《离散数学》题库及答案_离散数学习题答案

?用反证法证明。假设B??，则存在b?B。因为b?B且b? A?B，所以

（数理逻辑、集合论与二元关系部分）

1、设个体域是自然数，将下列各式翻译成自然语言：

（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。

（1）没有小于0的自然数;

（4）存在x，对任意y 使得xy=y;

（5）对任意x，存在y使x+y=x。

3、列出下列二元关系的所有元素：

8、设A,B,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《离散数学》题库及答案_离散数学习题答案

上的等价关系，所以aRc且aSc。故aR?Sc。从而R?S是传递的。

故R?S是A上的等价关系。

12、设A是集合，R?A×A，则R是对称的?R＝R－1。

14、设〈A,≤〉为偏序集，??B?A，若B有最大(小)元、上(下)确界，则

设a,b都是B的最大元，则由最大元的定义a?b，b?a。??是A上的偏序关

系，?a=b。即B如果有最大元则它是惟一的。

15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：

1?;它是反自反的、反对称的、传递的； 0??

1?;它是反自反的、0??

0?;它既不是自反的、反自反的、1??

也不是对称的、反对称的、传递的。

16、设A={1,2,?,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？

（1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是

18、A上的偏序关系?的Hasse图如下。

（2） 分别求出下列集合关于?的极大（小）元、最大（小）元、上（下）

(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。

20、求下列置换的运算：

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}。

24、证明：偶数阶群中阶为2 的元素的个数一定是奇数。

设<G,·>是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下的元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。

25、证明：有限群中阶大于2的元素的个数一定是偶数。

设<G,·>是有限群，则?a?G，有|a|=|a-1|。且当a 阶大于2时，a?a-1。故阶数大于2 的元素成对出现，从而其个数必为偶数。

5211《离散数学》题库及答案_离散数学习题答案

30、单位元有惟一逆元。

设<G,?>是一个群，e是关于运算?的单位元。

31、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e?0。 证明：

用反证法证明。假设e=0。

对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，

从而假设错误。即e?0。

32、证明在元素不少于两个的群中不存在零元。

证明：（用反证法证明）

设在素不少于两个的群<G,?>中存在零元?。对?a?G, 由零元的定义有 a*?=?。

矛盾。故在元素不少于两个的群中不存在零元。

33、证明在一个群中单位元是惟一的。

34、设a是一个群〈G，*〉的生成元，则a-1也是它的生成元。

?x?G，因为a是〈G，*〉的生成元，所以存在整数k，使得x=ak。

35、在一个偶数阶群中一定存在一个2阶元素。

群中的每一个元素的阶均不为0 且单位元是其中惟一的阶为1的元素。因为任一阶大于2 的元素和它的逆元的阶相等。且当一个元素的阶大于2 时，其逆元和它本身不相等。故阶大于2 的元素是成对的。从而阶为1的元素与阶大于2 的元素个数之和是奇数。

因为该群的阶是偶数，从而它一定有阶为2 的元素。

36、代数系统<G,*>是一个群，则G除单位元以外无其它等幂元。 证明：

因为a*e=a，所以a*a=a*e。由于运算*满足消去律，所以a=e。

即G除单位元以外无其它等幂元。

由于*满足消去律，故x1=x2。

从而对于a,b∈G，必有唯一的x∈G，使得a?x=b。

39、设群<G,＊>除单位元外每个元素的阶均为2，则<G,＊>是交换群。 证明：

从而＜G,*＞是交换群。

40、设*是集合A上可结合的二元运算，且?a,b?A,若a*b=b*a，则a=b。试证明：

从而由已知条件知，a*b*c=a*c。

换律 ，即G是可交换群。

从而f是G 的自同构。

43、设H和K都 是G的不变子群。证明：H?K也是G 的不变子群。 证明：

先证C（G）是G的子群。

再证C（G）是G的不变子群。

45、设<G,·>是没有非平凡子群的有限群。试证：G是平凡群或质数阶的循环群。

若G是平凡群，则结论显然成立。

否则设<G,·>的阶为n。任取a?G且a?e,记H=（a）(由a生成的G的子群)。显然H?{e}，且G没有非平凡子群，故H=G。从而G一定是循环群，且a是G 的生成元。

故G是质数阶的循环群。

综上所述，G是平凡群或质数阶的循环群。

46、设H和K都是G 的有限子群，且|H|与|K|互质。试证：H?K={e}。 证明：

若H?K?{e}。则H?K是一个元素个数大于1的有限集。

先证H?K也是G的子群，从而也是H和K的子群。

由拉格朗日定理可知，|H?K|是|H|和|K|的因子，这与已知矛盾。

47、素数阶循环群的每个非单位元都是生成元。

对G中任一非单位元a。设a的阶为k,则k?1。

5211《离散数学》题库及答案_离散数学习题答案

由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。

又由于akm=e，所以由定理5.2.5知，n|km。即p|qm。但p和q 互质，故p|m。 由于p和m都是正整数，所以p=m。即｜ak｜＝

51、设G＝(a)，若G为无限群，则G只有两个生成元a和a-1；

从而G只有两个生成元a和a。

（2） 若G为无限群，则H也是无限群；

（2）因为{e}?H，故H的生成元为am （m?0）。因为G是无限群，所以a的阶是无限的，从而am的阶也是无限的，故H也是无限群。

53、设G＝(a)，|G|＝n，则对于n 的每一正因子d，有且仅有一个d阶子群。因此n阶循环群的子群的个数恰为 n的正因子数。

对n 的每一正因子d，令k=

设H1是G的任一d阶子群。则由定理5.4.4知，H1＝(am)，其中am是H1中a 的最小正幂，且|H|=惟一d阶子群。

设H是G的惟一的d阶子群。若d=1 ,则结论显然成立。否则H＝(am)，其

中am是H中a 的最小正幂。由定理5.4.4知，d=。故d是n的一个正因子。

若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。

55、有限群G的每个元素的阶均能整除G的阶。

则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是循环群 ，从而是可交换群。

综合可得a*b?A?B=G，这与已知矛盾。从而假设错误，得证A=G或B=G。

59、设e是奇数阶交换群<G,*>的单位元，则G的所有元素之积为e。

因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2 阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a?1不是它本身，且G中不同的元素有不同的逆元。

由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G 是交换群，

故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。

求出S关于二元运算*的单位元，以及当a?0时，(a,b)关于*的逆元。

设S关于*的单位元为(a,b)。根据*和单位元的定义，对?(x,y)?S,有

所以S关于*的单位元为(1,0)。

当a?0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有

从而aRa。即R是自反的。

综上所述，R是G上的等价关系。

62、设H是G的子群，则下列条件等价：

5211《离散数学》题库及答案_离散数学习题答案

（1） H是G的不变子群；

即H?a=a?H。从而H是G的不变子群。

下证eR为关于运算*的右单位元。

对?b?G，记方程y*a=b的惟一解为y。

类似地，记方程y*a=a的唯一解为eL。即eL*a=a。

下证eL为关于运算*的左单位元。

对?b?G，记方程a*x=b的惟一解为x。

从而在半群<G,*>中, 关于运算*存在单位元，记为e。

现证G中每个元素关于运算*存在逆元。

对?b?G，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。

?b*c=c*b=e。从而有惟一解，?d=e。 c为b关于运算的逆元。

65、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 证明：

先证HK是G 的子群。

同理可证，KH?HK。

故HK=KH。从而HK是G的子群。

下证HK是G的不变子群。

所以cn=e。故由元素阶的定义有k|n。

所以cm=e。故由元素阶的定义有k|m。

由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。

67、当n分别是24，36，110时，<Sn,|>是布尔代数吗？若是，则求出其原

设0=1。则任取a?L，则由于L是有界格，故a?1且0?a。即0?a?1。因为0=1且?是L上的偏序关系，所以a=0。这与已知|L|>1矛盾。

70、在布尔代数中，证明恒等式a?(a??b)=a?b 证明：

76、在布尔代数中，证明恒等式

5211《离散数学》题库及答案_离散数学习题答案

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。

由吸收律、分配律和交换律有

83、证明：在有补分配格中，每个元素的补元一定惟一。

由吸收律、分配律和交换律有

故b=c。从而每个元素的补元是惟一的。

运算+满足交换律。 ?

运算+满足结合律。 ?

a是a关于运算+的逆元。 ? ?

综上所述，<S,＋>是一个交换群。

?a?S，因为⊙满足等幂律，所以a⊙a=a，故a?a。即?是自反的。 a,b?S，若a?b且b?a,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即?是反对称的。

88、证明在有n个结点的树中，其结点度数之和是2n-2。

由欧拉握手定理，树中所有结点的度数之和等于2|E|.

从而结点度数之和是2n-2。

88、任一图中度数为奇数的结点是偶数个。

由欧拉握手定理可得 ?deg(v)=2|E|可得，图中所有结点度数之和是偶数。

显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。

89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。

反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。

（用反证法证明）设|V|=n。

5211《离散数学》题库及答案_离散数学习题答案

91、画一个使它分别满足： (1) 有欧拉回路和哈密尔顿回路； (2) 有欧拉回路，但无条哈密尔顿回路； (3) 无欧拉回路，但有哈密尔顿回路； (4) 既无欧拉回路，又无哈密尔顿回路。

92、设无向图G=<V,E>，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？

设G中度数小于3的顶点有k个，由欧拉握手定理 24=?deg(v)

知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。

由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知

因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则

95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。

因为G是连通图，所以G中任一结点的度数都大于等于1。

假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故

96、若G有n个结点，m条边，f个面，且每个面至少由k(k?3)条边围成，则 m?k(ｎ－2)／(ｋ－2)。

记|E|=m。因为G=<V,E>是连通的简单平面图，故每个面的度数都不小于3。从而由公式?deg(f)=2|E|可得

98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。

若结点个数小于等于3时，结论显然成立。 当结点多于3 个时，用反证法证明。 记|V|=n,|E|=m,|F|=k。

假设图中所有结点的度数都大于等于5。

|V|?3，且G=〈V，E，F〉是一个连通简单无向平面图，

若G 不连通，则它可分成两个独立的子图G1和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个数中的某一种，这显然产生了矛盾。

因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。

（1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？

5211《离散数学》题库及答案_离散数学习题答案

（2） G中v1到v4的长度为4 的通路有4条； （3） G中经过v1的长度为3 的回路有3条；

（4） G中长度不超过4 的通路有72条，其中有19条回路。

105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。

106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。

由顶点集{a,b,d,f}诱导出的子图

107、求下列赋权图顶点间的距离。

108、求下列赋权图中v1到其他顶点的距离。

109、求下图的可达矩阵。

110、求下列图的生成树。

下面是它的两棵生成树：

111、在一个有n个顶点的G=<V,E>中，u,v?V。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。

5211《离散数学》题库及答案_离散数学习题答案

若l?n-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-6

113、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？

设它有k个1度顶点，则由欧拉握手定理

114、有向图G是强连通的?G中有一回路，它至少通过每个顶点一次。

径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、一个有向图是单向连通图? 它有一条经过所有结点的路。

可达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所经过的所有顶点的更长的路径。 P1 P1

对P2重复上述过程，直到得到一条经过所有顶点的路径为止。

若G中存在一条经过G中所有顶点至少一次的路径，则G中任意两个顶点中

至少有一个可达另一个，从而G是单向连通的。

寄语： 希望大家能在考试中取到好的成绩，谢谢！

篇二 : 离散数学期末考试试题与答案[1]

格? 分配格? 分配格 ? 有补格? 有补格 布尔格

5. 已知 f: A→B, g: B→C, f是单射 是单射,证明 f 是单射,g是单射 证明g 是单射 是单射 证明 是单射. 是满射,证明 是满射. 是单射 若gf是满射 证明 是满射 是满射 证明g是满射

(i=m+1,m+2,…) 则可以说明φ为 的双射, 则可以说明 为A→A∪B的双射, ∪ 的双射 故结论得证. 故结论得证. 也是可数无限集, (如果只用一句话说, A∪B也是可数无限集,可以得 分) 如果只用一句话说, ∪ 也是可数无限集 可以得2分

7. (5分) 画出 个顶点的自互补图.证明当 个顶点的自互补图. 分 画出

5个顶点的自互补图 证明当n=4k 或4k+1时才 时才 若一个图和它的补图同构,说它是自互补图. 有. 若一个图和它的补图同构,说它是自互补图. 解:(1)

8. (5分) 证明 G或者 有一个是连通图. 或者G有一个是连通图 分 证明: 或者 有一个是连通图. 证明:因为 不连通 不连通, 可以分为若干连通子图: 证明:因为G不连通,则G可以分为若干连通子图 可以分为若干连通子图 G1=(V1,E1), ,Gn=(Vn,En) ),--( , ), ( , ) 根据G的补图的构造过程知 的补图的构造过程知V1中每个顶点与其它 根据 的补图的构造过程知 中每个顶点与其它 顶点集V2, 中顶点有边相连. 顶点集 ,--- ,Vn中顶点有边相连. 这样, 在 中顶点有边相连 这样, G的补图中,有 的补图中, 的补图中 分别属于两个顶点子集Vi与 中的任意两个顶点 分别属于两个顶点子集 与Vj中的任意两个顶点 之间有边直接相连, 之间有边直接相连, 属于同一个顶点子集Vi的任意两个顶点借助顶点 属于同一个顶点子集 的任意两个顶点借助顶点 子集Vj的任意一个顶点连通 的任意一个顶点连通. 子集 的任意一个顶点连通. 所以,根据连通的定义知: 的补图一定连通 所以,根据连通的定义知:G的补图一定连通 .

9. (4分) 一个有奇数条边,偶数个顶点的欧拉图,但不是哈 一个有奇数条边,偶数个顶点的欧拉图, 密尔顿图. 密尔顿图.

11. (5分) 证明 多于一个顶点的树,至少有两片树叶. 分 证明: 多于一个顶点的树,至少有两片树叶.

证明: 是一棵树, 中最多只有一片树叶, 证明:设 T=(V,E)是一棵树,若T中最多只有一片树叶, 是一棵树 中最多只有一片树叶 则有

对于gG, 在代数运算*下的逆元记为 *-1 对于 在代数运算 下的逆元记为g 下的逆元记为 于是, 于是 g*-1=ug-1u 这里, 这里 g-1是在代数运算下的逆元

15. (4分) 下列哪些是循环群 分 下列哪些是循环群:

所以任何公式α均可以由集合{, →}中的联结词表 达出来的公式与之等价. 达出来的公式与之等价. 故集合{ 是完备的. 故集合 , →}是完备的. 是完备的

17. (4分) 试求公式 ( ∧q)→((q→r) 的主析 分 p∧ p)的主析 取范式和主合取范式. 取范式和主合取范式

18. (6分) 将下列语句化为含有量词的谓词演算公式 分 (1) 不是每个人都能干 但一定有人能干 不是每个人都能干,但一定有人能干 但一定有人能干. (2) 有一种气体可以腐蚀任何金属 有一种气体可以腐蚀任何金属. (3) 凡是对顶角一定相等. 凡是对顶角一定相等 解: (1) ( x(P(x) →A(x))) ∧(x(P(x) ∧A(x)) (2) x(G(x) ∧(y(M(y)