离散数学练习题2 答案

1-1．都是命题： 1-2设

P：明天天气晴朗 Q：我们就去郊游

则 P ?Q：如果明天天气晴朗，我们就去郊游 1-3根据真值表求公式P ? (P∧(Q ?R ))的主析取范式。 解

表1.15

P T T T T F F F F Q T T F F T T F F 例1.42真值表

R T F T F T F T F P ? (P∧(Q ?R)) T F T T T T T T 则

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 )

■

由于任意一组命题变元P1, P2, …, Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定变元在极小项中的排列次序，假设为P1, P2, …, Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P, Q, R（规定次序为P, Q, R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的

– 1 –

错误！文档中没有指定样式的文字。

给定公式的主析取范式。

P ? (P∧(Q ?R )) ? m0∨m1∨m2∨m3∨m4∨m5∨m7（规定P, Q, R的次序为P, Q, R） 公式P ? (P∧(Q ?R ))的主析取范式。 解 P ? (P∧(Q ?R )) ?﹁P∨(P∧(﹁Q∨R )) ? (﹁P∨P)∧(﹁P∨﹁Q∨R) ? (﹁P∨﹁Q∨R ) ? (﹁P∨﹁Q∨R )

1-4试证明(﹁P ? Q )∧(P ?R )∧(﹁Q∨S ) ? S∨R。 证明 （1）﹁P ?Q

（2）﹁Q∨S （3）Q ?S （4）﹁P ?S （5）﹁S ?P （6）P ?R （7）﹁S ?R

(6), I13

（8）﹁﹁S∨R

E16

（9）S∨R

P P T, (2), E16 T, (1), (3), I13 T, (4), E18 P T, (5),

T, (7),

T, (8), E1

– 2 –

图1.1 例1.51证明过程的树表示

错误！文档中没有指定样式的文字。

1-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。

解 设

P：迈克有电冰箱 Q：迈克卖了洗衣机 R：迈克向别人借了钱。

则上述语句可翻译为命题关系式

（1）P ? Q∨R （2）﹁P∨Q∨R （3）﹁ (﹁P∨Q ) ?R （4）﹁﹁P∧﹁Q ?R （5）P∧﹁Q ?R （6）﹁R ?﹁(P∧﹁Q ) （7）﹁R ?﹁P∨Q （8）﹁R （9）﹁P∨Q （10）P ?Q

（11）﹁Q ?﹁P

P ?Q∨R, ﹁R ?﹁Q ?﹁P P T, (1), E16 T, (2), E16 T, (3), E9 T, (4), E1 T, (5), E18 T, (6), E8 P

T, (7), (8), I11 T, (9), E16

T, (10), E18

1-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。

– 3 –

错误！文档中没有指定样式的文字。

解 设

P：今天我没课 Q：我去机房上机

R：我去图书馆查资料 S：机房没有空机器

则上述语句可翻译为命题关系式

P ?Q∨R, S ?﹁Q, P, S ? R

（1）﹁R P （2）P ?Q∨R P （3）﹁P∨Q∨R T, (2), E16 （4）R∨﹁P∨Q T, (3), E3 （5）﹁R ?﹁P∨Q T, (4), E16 （6）﹁P∨Q T, (1), (5), I11 （7）P ?Q T, (6), E16 （8）S ?﹁Q P （9）﹁﹁Q ?﹁S T, (8), E18 （10）Q ?﹁S T, (9), E1 （11）P ?﹁S T, (7), (11), I13 （12）P P

（13）﹁S

T, (11), (12), I11

– 4 –

错误！文档中没有指定样式的文字。

（14）S

P

（15）F

(13), (14)

1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。 甲说：“天津第一，上海第二。” 乙说：“天津第二，广州第三。” 丙说：“北京第二，广州第四。”

比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解 设 P2：北京第二 Q2：上海第二 R1：天津第一 R2：天津第二 S3：广州第三 S4：广州第四 由已知条件：

甲猜对了一半，(﹁R1∧Q2 )∨(R1∧﹁Q2 )在真值指派f下为T； 乙猜对了一半，(﹁R2∧S3 )∨(R2∧﹁S3 )在真值指派f下为T； 丙猜对了一半，(﹁P2∧S4 )∨(P2∧﹁S4 )在真值指派f下为T。 由事实知，每个城市只能得一个名次即R1∧R2, S3∧S4为永假式。

再由题意，没有并列名次可得：P2∧Q2, P2∧R2, R2∧Q2在真值指派f下为F。

– 5 –

错误！文档中没有指定样式的文字。

由于关系是一种特殊的集合，在证明此类问题时，通常任选一个关系的元素，然后得出它也属于另一个关系。

设R, S, T均为A上的二元关系，那么证明(S∪T)?R=(S?R)∪(T?R) 证明 选择任意的使得∈(S∪T)?R，推导如下：

∈(S∪T)·R??y(∈(S∪T)∧∈R) ??y((∈S∨∈T)∧∈R)

??y(∈S∧∈R)∨?y(∈T∧∈R) ?∈S?R∨∈T?R ?∈(S?R)∪(T?R)

ni?1

3.11 “找出三个元素的集合A和A上关系R，使R, R2, R3, R4两两不等”是可能的吗？如可能请具体做出，并说明这一现象与t(R)=

解 是可能的。 令A={a, b, c}

R={, , , }

R2={, , , , }

R3={, , , , , , , } R4={, , , , , , } R, R, R, R两两不等, 但此时所以这一现象与t(R)=

ni?12

3

4

Ri不矛盾。

3i?1R=

i4i?1Ri

Ri不矛盾。

3.12 将n个元素的集合划分成两个分块，共有多少种不同的分块？

解 划分成两个分块，则每个分块至少有一个元素，一个分块取i个元素的不同分类法

12n?1与取n?i个元素的不同分类法一样，故共有： (Cn+Cn+?+Cn)/2=(2n?2)/2=2n?1?1(种)。

3.13 设A={1, 2, 3, 4, 5}，那么

– 11 –

错误！文档中没有指定样式的文字。

（1）A上共有多少个二元关系？

（2）上述关系中，有多少个是等价关系？

解 （1）考虑A上的关系矩阵的数目，一个关系矩阵唯一地确定了一个二元关系——由于集合中有5个元素，所以关系矩阵是一个5?5的矩阵，共有25个元素，每个元素可以是0，也可以是1，所以共有225个不同的二元关系。

（2）由于某集合上的划分与该集合上的等价关系之间是一一对应的关系，所以A有多少种划分就有多少个等价关系。以划分中等价类中元素数目分类：

① 等价类中元素最多的只有一个元素的划分只有1种；

223② 等价类中元素最多的有两个的划分共有C5+C5?C5=40种； 33③ 等价类中元素最多的有三个的划分共有C5+C5=20种；

4④ 等价类中元素最多的有四个的划分共有C5=5种；

⑤ 等价类中元素最多的有五个的划分只有1种。 因此，总共的等价关系共有1+40+20+5+1=67种。 请读者根据此题归纳出一般的结论。

■

3.14已知N及其关系R如下，试说明R是等价关系，并指出等价类是什么。N是自然数集，R={ | ni/nj能表示成2n形式，n为任意整数}。

解 ?ni∈X，有ni/nj=1=20，故∈R，所以R是自反的。

?ni, nj∈X，若∈R，即ni/nj=2k（k是整数），所以nj/ni=2?k，所以∈R，所以R是对称的。

2k, k是整数）?ni, nj, np∈X，若∈R∧∈R，则ni/nj=2k1∧ni/nj=2k（，则ni/np=2k1+k2，12

则∈R，故R是传递的。

– 12 –

错误！文档中没有指定样式的文字。

总之，R是X上的等价关系，等价类是： [1]R={1, 2, 4, 8, 16, …, 2n, …} [3]R={3, 3?21, 3?22, …, 3?2n, …} [5]R={5, 5?21, 5?22, …, 5?2n, …} ?

3.15 图（a）为一有序集的哈斯图。 （1）下列命题那些为真？

aRb，dRa，cRd，cRb，bRe，aRa，eRa

（2）恢复R的关系图。

（3）指出R的最大、最小元，极大、极小元。

（4）求出子集B1={c, d, e}，B2={b, c, d, e}，B3={b, c, d, e}的上、下界，上、下确界。 解 （1）为真的命题有aRa，eRa，dRa。 （2）R的关系图如图（b）所示。

图 哈斯图和关系图

（3）A的最大元素为a，A的最小元素不存在；极大元为a，极小元为d, e。 （4）子集B1={c, d, e}的上界为a和c，下界不存在，上确界为c； 子集B2={b, c, d}的上界为a，下界为d，上确界为a，下确界为d；

– 13 –

错误！文档中没有指定样式的文字。

子集B3={b, c, d, e}的上界为a，下界不存在，上确界为a。

4.1找出下图中所有不同的圈。 解 C3：v8v9v10v8, v2 v3 v6 v2, v2 v6 v7 v2

C4：v2 v3 v6 v7 v2, v3 v4 v5 v6 v3 C5：v2 v3 v4 v5 v6 v2 C6：v2 v3 v4 v5 v6 v7 v2

图 含圈、路的简单无向图

10-3 给定一图G=(V, E)如右图所示。图 G

解

??01000?101??10100?00?02000?

A????01000?? A2???10100???00001?????00010? ??00010????00001??

– 14 –

错误！文档中没有指定样式的文字。

?0?2?3A??0??0??02020002000000010??20?040???40? A??20??1??00?0???0020200000100?0??0? ?0?1??从上面的矩阵中可以看到一些结论，如v1与v2之间有两条长度为3的路，结点v1与v3之间有一条长度为2

的路，在结点v2有四条长度为4的回路。

– 15 –

错误！文档中没有指定样式的文字。

【例10.10】 图10.29的两个图是否同构？

解 图10.29的两个图虽然形状不同，但它们表示了同一个图 其中

V(G)={a, b, c, d} E(G)={e1, e2, e3, e4, e5, e6}={(a, b),(a, c),(b, d),(b, c),(d, c),(a, d)},

a的邻接点为b, c, d，b的邻接点为a, c, d，c的邻接点为b, a , d，d的邻接点为b, c, a。 ■

【例10.11】 证明在连通图G中任意两条最长的通路必有一个公共结点。 证明 用反证法。

若G中有两条最长的通路P1、P2，无公共顶点。因G连通，故P1上有任—点u与P2

上的任一点v必是连通的，不妨设u是(u, v)-通路上最后一个在P1上的点，v是最先一个在P2上的点，如图10.30所示。

G=(V(G), E(G))

图10.29 例10.10图 图10.30 例10.11图

l， 2令(u, v)-通路为P3 ，设最长通路的长为l，u将P1分为两段，必有一段的长≥设为P4；同理v分P2为两段，有一段设为P5，其长≥

l。于是|P4+P3+P5|>l，此与P1、P2最2长相矛盾（此处“+”意指二通路相接）。 ■

?v?【例10.12】（1）证明若有v个结点的G是简单图，且? ＞???1，则G连通。

?2??v?（2）当v为偶数时，找出一个非连通的(???1)-正则简单图。

?2?

– 16 –

错误！文档中没有指定样式的文字。

?v?证明 （1）用反证法。假设G至少有两个连通分支，但至少有一个分支的结点个数≤??，

?2??v??v?这个分支中结点的度数最大为???1，这是因为G是简单的，这与? ＞???1矛盾。

?2??2??v?（2）有两个连通分支，每个分支有??个结点的完全图，即为所求的图。 ■

?2?【例10.13】 在8?8棋盘的64个方格中分别填入1～64个数字。求证：无论怎么填入这些数，总能找到两个具有公共边的两方格，里面所填数字之差不少于5。

证明 假设在64个方格中已填好64个数字。以这64个数字为结点集V构作简单无向图G=(V, E), ij?E? i和j所在的两方格有公共边。易知，G的直径d(G)≤7?7?14。若相邻两结点数字之差≤4，则G中任何两结点数字之差≤4?14=56。但存在两结点数字分别为1和64，且64?1=63＞56，矛盾。

■

【例10.14】 证明若G是简单图且?≥k，则G有一条长为k的路。 证明 若P是G中的一条最长路，它的长l小于k，设P为v1v2v3dG(v1)≥?≥k?l，从而在P外存在一结点v0和v1邻接，于是v0v1v2vlvl?1，由假定

vl?1是G中长于P的

一条路，这和P是G中最长路矛盾，故l≥k。我们可以在P中取一段长为k的路，故G中存在长为k的路。 ■

?v?1?【例10.15】 （1）证明若G为?条边、v个结点的简单图，且????则G是连通的。

2???v?1?（2）对v＞l，求一个非连通单图G使得????。

2??证明 （1）若G不连通，可分为两个结点数分别为v1, v2的互不连通子图G1, G2。 易知 于是

vi≥1(i?1, 2)

v1+v2=v

?(G)≤?1???2??11?22≤

2222????(v?1)(v1?v2?2)(v?1)(v?2)≤?22

?v?1?????2?– 17 –

?v??v?v(v?1)v(v?1)错误！文档中没有指定样式的文字。

?v?1?这与????矛盾。

2??（2）G?Kv?1?K1即为所求的单图。

■

【例10.16】 试证：若G是连通单图，但不是完全图，则G存在如下三个结点u, v和w，满足uv，vw ? E，uw ? E。

证明 由假定G不是完全图，故存在u, w1?V，uw1?E；由于G是连通的，故存在一条连接u, w1?V的最短路，设为uu1u2显然uu2?E，否则和最短路假定矛盾。unw1, n≥1。

■

于是我们令u1?v, u2?w（当n=1时，u2=w1），即为所求。

【例10.17】 试证：若?≥2，则G含有圈。

证明 由于?≥2，从而由v0出发到vk的路可以向前延伸，又由于G是有限个结点，从而延伸到某一点后再往下延伸时，必然要和已走过结点相重，于是我们就得到G中的一个圈。

【例10.18】 设：M是图G的关联矩阵，而A是图G的邻接矩阵。试证： （1）M的列和为2。 （2）A的列和是多少?

证明 （1）按M的定义，它的第j列是对应ej和V(G)中结点的关联次数所成的向量，由于一条边只有二个端点，故M的列和为2。

（2）根据定义，A的第i列的列和恰为与vi关联的边的数目。 【例10.19】 设图G的邻接矩阵为

?0?0A???1??1101001000?1?? 1??0?■

■

求G的可达性矩阵。

解

– 18 –

错误！文档中没有指定样式的文字。

?0?22A???1??0011110101??2?11?3? A???21???0??0122001111??1?21?4? A=??32???1??2223112201?3?? 3??1?故

?3?5234B4?A?A?A?A???7??3457224413??1?6?? P=?1?17???2??1111111111?1?? 1??1?

由此可知图G中任意两个结点间均是可达的，并且任意一个结点均有回路，此图是连通图。 上述计算可达性矩阵的方法还是比较复杂，因为可达性矩阵是一个元素为0或1的布尔矩阵，由于在每个Al中，对于两个结点间的路的数目不感兴趣，它所关心的是该两结点间是否有路存在，因此可将矩阵A，A2，?，An分别改为布尔矩阵A, A(2), ?, A(n)，故P=A∨A(2)∨?∨A(n)，其中A(i)表示在布尔运算下A的i次方。 ■

【例10.20】 计算图10.27a对应的完全关联矩阵的秩数，以验证定理10.10。

?1?01??001M(r?1)(G)????00??00?????????0??

100解 设完全关联矩阵

M(G):

v1 v2 v3 v4 v5 e1 0 0 0 1 1 e2 0 0 1 1 0 e3 0 0 1 0 1 e4 0 1 1 0 0 e5 0 1 0 0 1 e6 1 1 0 0 0 e7 1 0 0 0 1 – 19 –

错误！文档中没有指定样式的文字。

??1 1 0 0 0 0 0??1 1 0 0 0 0 0??0 0 0 1 1 1 0????0 0 0 1 1 1 0?第4行与第1行对调??0 1 1 1 0 0 0?第1行加第5行??0 1 1 1 0 0 0? ?0 0 0 0 0 1 1??????0 0 0 0 0 1 1??1 0 1 0 1 0 1????0 1 1 0 1 0 1????1 1 0 0 0 0 0??0 1 1 1 0 0 0????1 1 0 0 0 0 0??0 1 1 1 0 0 0??第2行与第3行对调??0 0 0 1 1 1 0?第2行加第5行?0 0 0 1 1 1 0??0 0 0 0 0 1 1?????0 0 0 0 0 1 1?

??0 1 1 0 1 0 1????0 0 0 1 1 0 1????1 1 0 0 0 0 0??0 1 1 1 0 0 0????1 1 0 0 0 0 0??0 1 1 1 0 0 0??第3列与第4列对调??0 0 1 0 1 1 0?第3行加第5行?0 0 1 0 1 1 0?

?0 0 0 0 0 1 1????0 0 0 0 0 1 1???????0 0 1 0 1 0 1?0 0 0 0 0 1 1????1 1 0 0 0 0 0??1 1 0 0 0 0 0??0 1 1 0 0 1 0????0 1 1 0 0 1 0??第4列与第6列对调??0 0 1 1 1 0 0?第4行加第5行?0 0 1 1 1 0 0?

?0 0 0 1 0 0 1?????0 0 0 1 0 0 1???0 0 0 1 0 0 1????0 0 0 0 0 0 0??最后一个矩阵其秩为4，即

rankM(G)=5?1=4

【例12.2】 应用算法12.1求图G的最小生成树，G如图12.5（a）所示。

图12.5 求最小生成树

解

– 20 –

错误！文档中没有指定样式的文字。

（1）根据Kruskal算法，首先根据图G得到按权值的边排序表L：e5, e9, e2, e4, e6, e8, e7, e1, e10, e3, e11

（2）然后，令S??。

（3）接下来，依次将e5, e7, e2, e4, e6, e1放入S中；边e8, e9被忽略，因为它们的加入会形成圈。

（4）此时S中有6条边，满足S?n?1，所以算法结束。 得到的最小生成树T如图12.5（b）所示，树权为10。 最小生成树的构造还可以使用其他算法。 算法12.2 （Prim算法）

（1）选出结点v，令V(T)={v}，E(T)??；

（2）在所有u?V(T)的结点中，若连接结点u和w的边e=uw是最小权重边，其中，w?V(T)，则令V(T)?V(T){u}，E(T)?E(T){uw}；

■

（3）若|E(T)|=n?1，算法停止，输出E(T)。否则，转（2），继续向树中增加新结点。 【例12.3】 使用Prim算法求图12.5（a）的最小生成树。 解 不失一般性，选出结点v1，令V(T)={v1}，E(T)??。 图12.6（a）～（g）显示出按照Prim算法求最小生成树的过程。

■

图12.6 Prim算法求最小生成树

– 21 –

错误！文档中没有指定样式的文字。

注意，例12.3求得的图12.5（a）的最小生成树（图（g））不同于例12.2（图（b））。这也说明一个图的最小生成树不唯一

【例12.4】 请用前序、中序和后序遍历算法遍历图12.13所示的二叉树。 解 （1）前序遍历结果为ABDEHCFGIK J； （2）中序遍历结果为DBHEAFCKIG J；

（3）后序遍历结果为DHEBFKIJGC A。

图12.13 二叉树的遍历

11-1 问开区间(0, 1)中的有理数集合按有理数的大小排序是否构成完全格？闭区间［0, 1］呢？

解 开区间(0, 1)中的有理数集合按有理数的大小排序不构成完全格。闭区间［0, 1］中的有理数集合按有理数的大小排序构成完全格。

– 22 –

本文来源：https://www.bwwdw.com/article/2sgv.html