当前位置：文档之家› 离散数学第9章习题答案

离散数学第9章习题答案

习题9

1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：

因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。■

2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■

3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）

解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：

(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}

每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)

v 1

v 5

v 3

v 4

v 2

将奇数3，3 对应的结点v 2,v 3一组，画一条连线

其他序列可以类式作图，当然大家也可以画图其它不同的图形。■

4．证明：在（n ，m ）图中。

证明：图的点度数是一组非负整数{d(v 1),d(v 2)…d(v n )}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值 = (d(v 1)+d(v 2)…+d(v n ))/n = 2m/n,所以。■

5．证明定理10.2。

【定理10.2】对于任何（n ,m ）有向图G =（V ，E ），

证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。■

6．设G 是（n ，m ）简单二部图，证明：。

证明：本题目，我们只需要说明n 阶的简单二部图的边数的最大值 = 即可。

设n 阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n 。此种情况下，当G 为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n 阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m)) = ,所以n 阶二部图(n,m), ■

v 1 v 5

v 3

v 4

v 2

v 1

v 5

v 3

v 4

v 2

7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。解：根据握手定理有：21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■

10．判断图10.29中的两个图是否同构，并说明理由。

图9-1.15

解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■

13. 设有向图D=如下图10.31所示。

(1) 在图中找出所有长度分别为1，2，3，4的圈(至少用一种表示法写出它们，并以子图形式画出它们)。

(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。

解：(1)

(2)子图略

C=AA

C=ADA C=Ae4Be7Ce5A

C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A

C=Ae4Be8Ce6De2A

图10.29

长度为三的回路：Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A

长度为四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA

长度为五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA, AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A■

15. 若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。

证明：反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■

17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。

证明：假设G不连通，分支G1，G2．．Ｇｋ，那么他们的边数的最大值ｍａｘ（ｍ）＝Σ（ｎｉ－１）ｎｉ／２≤Σ（ｎｉ－１）（ｎ－１）／２＝（ｎ－１）／２Σ（ｎｉ－１）＝（ｎ－１）（ｎ－ｋ）／２，所以，只有当k=1时，才能满足题设要求，G是连通图。如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件■

18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价:

(1）G无割边；

(2) G中任何两个结点位于同一回路中；

(3) G中任何一结点和任何一边都位于同一回路中；

(4) G中任何两边都在同一回路中。

证明：（1）=〉（2）

因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。

（2）=〉（3）

因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求.

（3）=〉（4）

对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在回路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2…v1v2…u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1…u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求.

(4)=>(1)

因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不

连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边■

19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。

证明：G-v最多产生d(v)个奇数度点，又因为每个连通分支中奇数度点的个数是偶数，即G-v的连通分支最少有两条边和v相连，所以总连通分支数小于等于d(v)/2■

21. 证明:在非平凡连通图G中,e为割边的充要条件是它不包含于G的任何圈中。

证明：1）e为割边 =〉e不包含于G的任何圈中

假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；

2）e不包含于G的任何圈中 =〉e为割边

假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。

根据1），2)可知，题设结论成立■

23. 证明:在具有n（n≥2）个结点的简单无向图G中，至少有两个结点的度数相同。

证明：此题可用鸽笼原理，因为n个结点的简单无向图G中，结点的度数只可能是0，1，2…n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之也然。所以n 个结点，最多有n-1种度数，其中必有至少两个结点的度数相同■

24. 设G是的简单图。证明:G中必有长度至少为的圈。

证明：设ｐ＝ｕ．．．ｖ是满足题设要求图Ｇ中的最长基本道路，那么ｄ（ｕ），ｄ（ｖ）都应该大于等于δ。那么，u,v的邻接点都应该在道路p 上，否则此道路可以延长，与其是最长路假设矛盾。如果u，v是邻结点，那么可以构成一个圈c= u…vu，其长度≥δ＋１。如果ｕ，ｖ不是邻结点，那么从ｐ的终点开始删除点，直到其为ｕ的邻结点为止，得到道路ｐ＇,可知道路p’，依然保持ｕ的所有邻结点都在ｐ＇上的性质，所以可构成一个圈ｃ＇＝ｕ．．．ｕ＇ｕ，其长度≥δ＋１，证毕■

25. 证明:G是单向连通图当且仅当存在一条包含G中全部结点的有向道路。

证明：假设不存在包含全部结点的有向道路，那么设ｐ＝ｖ１ｖ２．．．ｖｋ是Ｇ中最长的有向道路，且ｕ结点不包含在此有向道路中。ｕ和此道路中任何中间结点都不可能双向可达，且ｕ不能到达ｖ１，且ｖｋ也不能到达ｕ，否则，此最长路可扩充。那么由于道路上的每个结点和ｕ都单向可达，所以此最长路和ｕ之间的可达关系必然如下图所示：

当ｋ为偶数时，道路可扩充为v 1…v k/2…u …v k/2+1…v k ,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■

26. 无向图G 如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。

图10.32

解：标注如下所示：

ｖｋ／２＋１

ｖｋ／２

ｋ为偶数ｕ

ｖｋ＋１／２ｖｋ＋１／２－１

ｋ为奇数

ｕ

ｖｋ＋１／２＋１

ｕ６

ｕ５

ｕ４

ｕ３

ｕ２

ｕ１

ｕ７

ｕ８

ｕ９

根据标记后的图，可求得割点分别为：ｕ４，ｕ７，ｕ８，割边分别为：ｕ４ｕ５，ｕ７ｕ８，ｕ８ｕ９■

27. 求图10.33的全部强分图和单向分图。

图10.33

解：将图重新标记如下：

那么此图的邻接矩阵为，通过计算可求得其强分图矩阵为：

因此，此图有两个强分图，一个包含一个结点Ｖ９，一个包含其它的８个节点。由于两个强分图之间存在有向道路，因此全部９个结点，构成了单向分图■

28. 证明：一个连通无向简单图中，任意两条最长路至少有一个公共顶点。

证明：假设两条最长路ｐ１＝ｖ１ｖ２．．．ｖｋ，ｐ２＝ｕ１ｕ２．．．ｕｋ没有公共点，那么两条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是ｐ１上ｍ点，终点是ｐ２上的ｗ点．可根据如下情况进行调论：（１）ｍ，ｗ是ｐ１，ｐ２的中间结点，那么可构成新道路Ｐ＝ｖ１ｖ２．．．ｍ．．．ｗ．．．ｕｋ，此路至少比Ｐ１长1，矛盾。（2）假设m 和w 不能均分p1,p2,那么可以将两个长路段和m,w 之间的道路进行拼接，那么可得到比p1长的道路，与ｐ１，ｐ２是最长路矛盾。因此任意两条最长路至少有一个公共顶点■

29. 证明：若G 是n 阶无向简单图，G 中每一对不相邻的顶点的度数之和至少是n -1，则G 是连通图。

ｖ４

ｖ１

ｖ９

ｖ２

ｖ３

ｖ５

ｖ６

ｖ７

ｖ８

证明：假设G 不是连通图，G1，G2 是G 的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2≤n 。对G1中任意结点v1,和G2中任意结点v2而言，v1的最大点度为n1-1,v2的最大结点度为n2-1;则v1,v2的点度之和，最大为n1+n2-2≤n-2

30. 求出图10.34

的邻接矩阵、可达性矩阵、强分图和关联矩阵。

图10.34

解：对图的结点和边进行编号如下：

邻接矩阵：

因此可达矩阵为：强分图

矩

阵

为：关联矩

阵

为

：

■

ｅ１２

ｅ１１

ｅ１０ｅ９

ｅ８

ｅ７

ｅ６

ｅ５

ｅ３

ｅ２ｅ１ｅ４

ｖ７

ｖ１ｖ３ｖ６

ｖ５

ｖ４

ｖ２

习题十一

1. 设一个树中度为k的结点数是n k（2≤k），求它的叶的数目。

解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有：

t + n2 + n3 + …+ n k = n (1)

t + 2n2 + 3n3 + …k(n k) = 2(n-1) (2) 握手定理

(1),(2)联立求解得：

t = n3 + 2n4+ … (k-2)n k + 2■

2. 证明：树T中最长道路的起点和终点必都是T的叶。

证明：假设T中最长道路P=v i1v i2…v ik的起点或终点不是T的叶结点，设d(v i1)>1,则v i1的所有邻接点(v‘1,v’2…,v’l)都在P中，那么在T中可以找到一个回路,那么截取道路P, 得到回路C= v i1…v’l v i1 .与T中无回路矛盾。对于d(v ik)>1时同理。因此，假设不成立，即最长道路P的起点和终点都是T的叶节点■

6. 证明：如果T是树且Δ≥k，则T中至少有k个叶结点。

证明：当T为非平凡树时，根据T的定义，T中每个枝点都是割点，当删除d(v)=Δ的节点时，ω（T-v）=Δ，每个分支都是数，如果分支都是平凡树，则这些节点都是T的叶，叶节点数为Δ。如果分支有非平凡数，那么至少有两个叶节点，其中至少一个是删除v时就存在的，因此总的叶节点个数≥Δ≥k。因此Ｔ中至少有ｋ个叶结点■

7. 设G为n（n≥5）阶简单图，证明G或中必含圈。

证明：反证法，假设G和中都不含圈，那么G和的所有分支都是树。则G所包含的最大边数|E(G)|=n-1, 则所包含的最大边数|E()|=n-1. 因为G及的边数总和|E(G)|+ |E()| = n(n-1)/2, 但根据假设条件，max|E(G)|+max |E()|=2(n-1) < n(n-1)/2, 矛盾.因此，G或中必含圈■

10.设e是连通图G的一条边。证明：e是G的割边当且仅当e含于G的每个生成树中。

证明：

1）充分性：e是G的割边则e含于G的每个生成树中

假设e不包含在某棵生成树T中，那么e一定在T的树补边集中，那么G-{e }中依然包含树T,因此G-{e }连通，与e是割边矛盾，因此e含于G的每个生成树中；

2)必要性：e含于G的每个生成树中则e是G的割边

假设ｅ不是Ｇ的割边，那么Ｇ－｛ｅ｝依然连通，具有生成树，这些生成树也是Ｇ的生成树，且不包含ｅ，与e含于G的每个生成树中前提矛盾，因此e是G的割边。

综上所述，题设结论：e是G的割边当且仅当e含于G的每个生成树中成立■

11.设T 1和T 2是连通图G 的两个不同的生成树，a 是在T 1中但不在T 2中的一条边。证明：T 2中存在一条边b ，使得（T 1-a ）+b 和（T 2-b ）+a 也是G 的两个不同的生成树。

证明：从T 1中删除边ａ，得树T 1－１和T 1－２，分别用Ｖ１，Ｖ２表示这两棵子树的结点集合，设Ea ＝｛ｅ｜ｅ的两个端点分别属于Ｖ１，Ｖ２｝，显然，ａ∈Ea ．因为ａ不在T 2中，所以ａ是T 2的树补边。设C （a ）为在中T 2增加边a 后所得到的圈，则C(a)中必然存在T 2 的树边b 不在T 1中但在Ea 中。否则，C(a)上的T 2的所有树边均在T 1中或均不在Ea 中。如果C(a)上的T 2的所有树边均在T 1中，则C(a)上的所有边都在T 1中，与T 1是树矛盾。如果C(a)上的T 2的所有树边均不在Ea 中，则C(a)中除ａ外所有的边的端点均在Ｖ１或Ｖ２中，与C(a)是基本回路矛盾。所以C(a)中必然存在不在T 1中但在T 2中的的树边，设ｂ是其中的一条。则（T 1-a ）+b 连通且无回路是Ｇ的生成子图，它是Ｇ的生成树。同理（T 2-b ）+a 也是Ｇ的生成树■

15. 证明: 简单连通无向图G 的任何一条边，都是G 的某一棵生成树的边。

证明：简单连通无向图G 的任何一条边，要么是割边，要么是非割边。如果是割边，那么此边是所有生成树的树边；如果不是割边，设边为ｅ，那么G-{e}连通，可以求出生存树Ｔ，此Ｔ也是Ｇ的生存数，且不包含ｅ，那么ｅ是Ｔ的树补边。则Ｔ+{e},有唯一一个圈Ｃ，删除圈上任意一条非ｅ边，便得到一颗包含ｅ边的树■

16. 证明:在完全二又树中,边的数目等于2(t -1)，式中t 是叶的数目。

证明：设Ｔ中的结点数为ｎ，枝点数为ｉ；根据完全二叉树的定义，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程组，得到m=2(t-1) ■

18. 给出公式的根树表示。

解：将标示符号看成叶结点，逻辑连接词作为分支结点，按公式的先后顺序构造根树如下：

■

19. 给定权1,4,9,1,2,6,4,6,8,10,构造一个最优二叉树。

解：根据带权最优二叉树定理构造过程如下：

■

21. 证明:正则二叉树必有奇数个结点，且树叶数t 与结点数n 之间有：t =（n -1）/2。

证明：因为正则二叉树的边数ｍ与分支点数ｉ的关系为：ｍ＝２ｉ，又因为是树，因此结点数ｎ满足：ｎ＝ｍ－１＝２ｉ－１，必为奇数。叶结点数ｔ和枝点数之和为ｎ，即：ｔ＋ｉ＝ｎ，因此t =（n -1）/2■

1 4 9 1

2 6 4 6 8 10

1 1

2 4 4 6 6 8 9 10 重新排序 ====

2 2 4 4 6 6 8 9 10 ====

4 4 4 6 6 8 9 10 ======

8 4 6 6 8 9 10 ====

8 10 6 8 9 10 ====

8 10 14 9 10

8 9 14 10 10 交换10，9 ========

17 14 10 10 ==== 17 14 20 =============

31 20 ============= 51

8 6 6

习题十二

1．证明下面3个图都是平面图。

证明：因为所给图都可以平面图的方式画出来，如下：

■

2．下面3个图都是平面图，先给图中各边标定顺序，然后求出图中各面的边界和面度。解：略■

3. 设G是阶数不小于11的图。证明：G或中至少有一个是非平面图。

证明：假设G和都是平面图，因为，所以至少有一个图的边数，设，有因为是平面图，所以有，求解得ｎ≤１０．与题设G是阶数不小于11的图矛盾，因此G或中至少有一个是非平面图■

4. 证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。

证明：因为是简单连通平面图，因此根据欧拉公式有６－１２＋ｆ＝２，所以有８个面。根据面度和与边的关系有，Σｄ（ｆｉ）＝２ｍ＝２４；因为要在平面上围成一个面，至少需要３边，所以８个面，Σｄ（ｆｉ）≥２４。因此，不存在面度大于３的面，所有面的度数都是３■

5. 证明：少于30条边的简单平面图至少有一个顶点的度不大于4。

证明：假设图Ｇ（ｎ，ｍ）的每个结点的点度都大于等于５，根据握手定理及平面图的判定定理有：５ｎ≤２ｍ＜６０（１）握手定理ｍ≤３ｎ－６（２）根据（１）得到：ｎ<１２结合（１）（２）得到：５ｎ／２≤３ｎ－６，所以ｎ≥１２，矛盾。因此假设不成立，题设结论成立■

6. 设G 是具有k （k ≥2）个连通分支的平面图，则 n –m +f =k +1。

证明：针对每个连通分支而言，满足欧拉公式及：n i-m i+f i = 2,因此Σni – Σmi + Σfi = 2k.因为对G 图而言只有一个外部面，但在针对每个连通分支引用欧拉欧式的时候都计算了一次外部面，因此外部面多计数k-1次，所以总面数比求和公式少k-1个面，因此有Σni – Σmi + Σfi-(k-1) = 2k-(k-1) 得 n –m +f =k +1■

10.举例说明同构的平面图，其对偶图不一定同构。

解：举例如下：

■

11. 设某校某专业的学生在某学期共选修了n 门选修课，期末考试前必须提前将这n 门选修课程先考完，要求每天每人在下午考一门课，问至少需要几天考完这n 门课？解：此类题可转化为求图的点色数的问题，可将课程集合作为图的点集合Ｖ＝｛ｖ１，ｖ２．．．ｖｎ｝

．构造每门课程的学生选修集合Ｓ（ｖｉ），如果有同学同时选修了ｖｉ，和ｖｊ课程，则添加边（ｖｉ，ｖｊ）到图中。生成图Ｇ后，求Ｇ的点色数χ（Ｇ）即可■

12. 在11题中，设n = 9，并且课程1和2，1和6，1和4，1和7，2和3，2和6，3和7，3和9，4和7，4和8，5和6，5和8，5和9都有人同时选，问至少几天能将9门课考完。

解：按１１题的要求，作出如下课程图：

原图同构

对偶图不同构

所以至少需要３天才能考完■

完成题目［１，２，３，４，５，6，7，８，９，１０，１１，１２］

ｖ２

ｖ１

ｖ９

ｖ３

ｖ４

ｖ５

ｖ６ｖ７

ｖ８

习题十三

1. 构造(n , m )欧拉图使满足条件：(1) m 和n 奇偶性相同；(2) m 和n 奇偶性相反。解：

■

5. 在图13.10中求中国邮递员问题的解。

解：略，请参考书中解法■

6. 设G 是有两个奇度点的连通图,设计一个构造G 的欧拉道路的算法。

解：step1: 添加连接两个奇度点的边 Step2: 调用一般的欧拉回路的算法

Step3: 在回路中删除添加的边■

7. n 为何值时，无向完全图Kn 是欧拉图？n 为何值时，无向完全图Kn 仅存在欧拉道路而不存在欧拉回路？

解：当n 为大于2的奇数时，无向完全图Kn 是欧拉图，因为每个节点的度数为偶数。当n 为2时，K 2，是唯一存在两个奇度点的完全图，因此此图只存在欧拉道路■

8. n （n ≥2）个结点的有向完全图中，哪些是欧拉图？

m 和n 奇偶性相同

m 和n 奇偶性相反

解：n （n ≥2）个结点的有向完全图中，每个都是欧拉图，因为每个节点都有相同的入度和出度，可以找到有向欧拉回路■

9. 证明:凡有割点的图都不是哈密顿图。

证明：反证法，假设存在有割点v 的图是哈密顿图，那么此图存在哈密顿圈。在此圈中删除割点v ，那么剩下的节点依然连通。这和割点的定义相矛盾，所以题设命题成立■

10. 证明: 4k +l 阶的所有2k 正则简单图都是哈密顿图。

证明：因为图是的正则简单图，因此对任意的u ，v ∈V, 有d(u) + d(v) = 4k. 根据定理13.4，存在哈密顿道路P= v 1v 2…v 4k+1.

1）如果 v 1v 4k+1∈E, 则v 1v 2…v 4k+1v 1构成一个H 圈； 2）如果v 1v 4k+1E ，则是v 1的邻接点，那么必为v 4k+1的邻接点。否则，v 4k+1点度为4k-1-2k=2k-1,与题设矛盾。假设v it-1v 4k+1∈E ，那么可构造H 圈如下：v 1…v it-1v 4k+1 v 4k …v it v 1 因此，此图为哈密顿图■

11．在无向完全图Kn 中有多少条没有公共边的哈密尔顿回路？

解：1) 设n=2k+1,将节点编号为0,1,2…2k,并作如下图示，

在上图中先取一条哈密顿回路为0,1,2,2k,3,2k-1,4,…k+3,k,k+2,k+1,0,然后将圆周上的结点按逆时针方向依次转动一个位置，然后可以得到另一条回路为：0,2,3,1,4,2k,5,…k+4,k+1,k+3,k+2,0;显然，这两条回路是没有公共边。继续这样做下去，共可产生条无公共边的哈密顿回路。

若n=2k+2,那么只要在中间增加一个结点ｕ，就可以同样地得到条无公共边的哈密顿回路■

12. 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同，问11人共进午餐最多能有多少天？

解：将１１个学生分别用结点表示，由于每个同学都可能邻座，因此每两个结点之间都有一条边，因此得到无向完全图Ｋ１１，每次午餐时学生都按照一条哈密顿回路落座，如果两条哈

2 3 4

K+1

K+2

2k 2k-1 2k-2

K+3

密顿回路有公共边，则公共边端点所代表的学生就是相邻的。因此上述问题转化为求Ｋ１１有多少条无公共边的哈密顿回路问题，利用１１题的结论，共有(11-1)/2=5条无公共边的哈密顿回路，因此这１１个学生共进午餐最多能有５天■

13. 假定在n个人的团体中,任何2人合起来认识其余的n-2个人。证明:

(1)这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

(2)当月时,这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人。

证明：因为任意两个人加起来认识其余的ｎ－２个人，那么每个人至少认识n-2个人。否则，设ｖ不认识ｕ，ｔ两人，那么ｕ和ｔ两个人将不能认识完剩下的ｎ－２个人，矛盾。当ｎ≥3时，将n个人看成图的结点，相互认识则在相关两个结点间有一条边，构成一个简单无向图G。此图中，任何两个结点的点度之和d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密顿道路，即这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

当n≥4, 任何两个结点的点度之和d(u)+d(v)≥2(n-2)≥n,因此图中存在哈密顿回路，即这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人■

14. 设G是(n, m)简单图。若,证明G必是哈密顿图。

证明：假设此图中存在两个点v,u 其点度之和d(v)+d(u)≤n-1,那么剩余n-2个结点的点度之和最大值为(n-2)(n-3) + n-1,那么整个图的最大点度之和为(n-2)(n-3)+n-1+n-1=n2-3n+4,但根据题设条件，点度之和Σd(u) = 2m ≥n2-3n+6.矛盾，因此任意两结点点度之和d(v)+d(u)≥n，因此图G必是哈密顿图■

15. 用两种以上的办法判别图13.11不是哈密顿图。

解：

方法1 ：删点法，如下

由上图可知，删除7个黑色点后，此图变成为具有9个分支的子图，根据哈密顿图的必要性判定定理ω(G-S)≤|S|可知，此图不是哈密顿图。

删除任何结点之前的原图删除黑色结点之后

方法2：根据平面哈密顿图的面度公式：此图只有4度面，因此如果是哈图，则必须满足其中，代表内部面数，代表外部面数。但是，面的总数是13，无论如何不能成立，因此不是哈密顿图■

离散数学复习题及答案

1. 写出命题公式﹁（P →（P ∨ Q ））的真值表。答案： 2.证明答案： 3. 证明以下蕴涵关系成立：答案： 4. 写出下列式子的主析取范式：答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?

①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化：所有鱼都生活在水中。答案：令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的则上述命题符号化为 10. 请将下列命题符号化：对于所有的正实数x,y ，都有x+y ≥x 。答案：令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化：每个人都要参加一些课外活动。答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??

离散数学题库及答案

数理逻辑部分选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。

《离散数学》考试题库及答案(三)

《离散数学》考试题库及答案一、填空 10% （每小题 2分） 1、若P ，Q 为二命题，Q P ?真值为1，当且仅当。 2、对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的公式为。 3、 )) (()(x xG x xF ??∧?的前束范式为。 4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则被称为全称量词消去规则，记为US 。 5、与非门的逻辑网络为。二、选择 30% （每小题 3分） 1、下列各符号串，不是合式公式的有（）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、下列语句是命题的有（）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、下列公式是重言式的有（）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、下列问题成立的有（）。 A 、若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、命题逻辑演绎的CP 规则为（）。 A 、在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；

离散数学复习题参考带答案

一、选择题：（每题2’） 1、下列语句中不是命题的有（）。 A ．离散数学是计算机专业的一门必修课。 B ．鸡有三只脚。 C ．太阳系以外的星球上有生物。 D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（）。 A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的 C ．当A 的真值为真时，B 的真值也为真 D ． A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（）。 A ． 010，100，101，110，111 B ． 010，100，101，111 C ．全体赋值 D ．不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为（）。 A ．2 B ．3 C ．5 D ．0 5、一个公式在等价意义下，下面哪个写法是唯一的（）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 6、下述公式中是重言式的有（）。 A ．(P ∧Q) (P ∨Q) B ．(P Q) (( P Q)∧(Q P)) C ．(P Q)∧Q D ．P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为（），成真赋值的个数为（）。 A ．0 B ．1 C ．2 D ．3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（）。 A ．m 001∧m 011∧m 110∧m 111 B ．M 000∧M 010∧M 100∧M 101 C ．M 001∧M 011∧M 110∧M 111 D ．m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是（）。 A ．(x)A(x) ( x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（）。 A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C ．x ( P(x) Q ) x P(x) Q D ． x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（）。 A ．x y （x·y=1） B ．x y （x·y=0） C ． x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（）S 。 A ．{{1,2}} B ．{1,2 } C ．{1} D ．{2} 13、下列是真命题的有（）。 A ．{a}{{a}} B ．{{}}{,{}} C ．{,{}} D ．{}{,{}}

离散数学试题与答案

试卷二试题与参考答案一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等性 ;就是否有对称性。 6、4阶群必就是群或群。 7、下面偏序格就是分配格的就是。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学习题

第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。（2）5能被2整除。（3）现在开会吗？（4）x+5>0 （5）这朵花真是好看！（6）2是素数当且仅当三角形有三条边。（7）雪是黑色的当且仅当太阳是从东方升起。（8）2000年10月1日天气晴好。（9）太阳系以外的星球上有生物。（10）小李在宿舍里。（11）全体起立。（12）4是2的倍数或是3的倍数。（13）4是偶数且是奇数。（14）李明和王华是同学。（15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。（1）若2+2=4，则3+3=6；（2）若2+2=4，则3+3≠6；（3）若2+2≠=4，则3+3=6；（4）若2+2≠=4，则3+3≠=6；（5）2+2=4，当且仅当3+3=6；（6）2+2=4，当且仅当3+3≠6；（7）2+2≠4，当且仅当3+3=6；（8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。（1）如果今天是1号，则明天是2号；（2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。（1）2是偶数不是素数；（2）小王不但聪明而且用功；（3）虽然天气冷。老王还是来了；（4）他一边吃饭，一边看电视；（5）如果天下大雨，他就乘公交汽车来；（6）只有天下大雨，他才乘公交汽车来；（7）除非天下大雨，否则他不乘公交汽车来；（8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);

离散数学习题三含答案

离散数学习题三 11、填充下面推理证明中没有写出的推理规则。前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。（2）证明从此前提出发，推任何结论的推理都是正确的。证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??

②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。（2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明：（1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理：前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理即根据附加前提证明法，推理正确。

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。（2）解：原子命题：我爱北京天安门。复合命题：如果不是练健美操，我就出外旅游拉。（3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：

离散数学例题整理

第一章定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律）证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)

离散数学课后习题答案第二章

第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.

离散数学试题及答案(1)

离散数学试题及答案一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

离散数学题目大汇总

离散数学试题一（A 卷答案）一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。七、（15分）若是群，H 是G 的非空子集，则是的子群对任意的a 、b ∈H 有 a * b －1∈H 。八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗离散数学试题一（B 卷答案）一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w