离散数学练习题2答案.doc

Error! No text of specified style in document.1-1都是命题：1-2设P：明天天气晴朗Q：我们就去郊游则P Q：如果明天天气晴朗，我们就去郊游1-3根据真值表求公式P (P(Q R )的主析取范式。解表1.15例1.42真值表PQRP (P(Q R)TTTTTTFFTFTTTFFTFTTTFTFTFFTTFFFT则P (P(Q R ) (PQR )(PQR )(PQR )(PQR )(PQR )(PQR )(PQR )由于任意一组命题变元P1, P2, , Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定变元在极小项中的排列次序，假设为P1, P2, , Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P, Q, R（规定次序为P, Q, R）的极小项PQR的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的给定公式的主析取范式。P (P(Q R ) m0m1m2m3m4m5m7（规定P, Q, R的次序为P, Q, R）公式P (P(Q R )的主析取范式。解P (P(Q R )P(P(QR ) (PP)(PQR) (PQR ) (PQR )1-4试证明(P Q )(P R )(QS ) SR。证明 （1）P QP（2）QSP（3）Q ST, (2), E16（4）P ST, (1), (3), I13（5）S PT, (4), E18（6）P RP（7）S RT, (5), (6), I13（8）SRT, (7), E16图1.1 例1.51证明过程的树表示（9）SRT, (8), E11-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。解设P：迈克有电冰箱Q：迈克卖了洗衣机R：迈克向别人借了钱。则上述语句可翻译为命题关系式P QR, R Q P（1）P QRP（2）PQRT, (1), E16（3） (PQ ) RT, (2), E16（4）PQ RT, (3), E9（5）PQ RT, (4), E1（6）R (PQ )T, (5), E18（7）R PQT, (6), E8（8）RP（9）PQT, (7), (8), I11（10）P QT, (9), E16（11）Q PT, (10), E181-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。解设P：今天我没课Q：我去机房上机R：我去图书馆查资料S：机房没有空机器则上述语句可翻译为命题关系式 P QR, S Q, P, S R（1）RP（2）P QRP（3）PQRT, (2), E16（4）RPQT, (3), E3（5）R PQT, (4), E16（6）PQT, (1), (5), I11（7）P QT, (6), E16（8）S QP（9）Q ST, (8), E18（10）Q ST, (9), E1（11）P ST, (7), (11), I13（12）PP（13）ST, (11), (12), I11（14）SP（15）F(13), (14)1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。” 乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解设P2：北京第二Q2：上海第二R1：天津第一R2：天津第二S3：广州第三S4：广州第四由已知条件：甲猜对了一半，(R1Q2 )(R1Q2 )在真值指派f下为T；乙猜对了一半，(R2S3 )(R2S3 )在真值指派f下为T；丙猜对了一半，(P2S4 )(P2S4 )在真值指派f下为T。由事实知，每个城市只能得一个名次即R1R2, S3S4为永假式。再由题意，没有并列名次可得：P2Q2, P2R2, R2Q2在真值指派f下为F。以上8个方程组成的方程组可解得f为P2=T, Q2=F, R1=T, R2=F, S3=T, S4=F因此，实际名次为：天津第一、北京第二、广州第三、上海第四。2-1 说明下列各式中量词的辖域与变元约束的情况：（1）(x)A(y)（2）(x)(A(x)B(x)（3）(x)(A(x)($y)B(x, y)（4）(x)(y)(A(x, y)B(y, z)($x)A(x, y)（5）(x)(A(x)($x)B(x, z)($y)C(x, y)B(x, y)（6）(x)(A(x)B(x)($x)C(x)D(x)解 （1）(x)的辖域是A(y)，其中x为约束出现，y为自由出现。（2）(x)的辖域是A(x)B(x), x为约束出现。（3）(x)的辖域是A(x)($y)B(x, y), ($y)的辖域是B(x, y)，其中x, y都为约束出现。（4）(x)的辖域是(y)(A(x, y)B(y, z)，(y)的辖域是A(x, y)B(y, z)，($x)的辖域是A(x, y)，其中在(x)(y)(A(x, y)B(y, z)中，x，y都为约束出现，z为自由出现，在($x)A(x, y)中，x为约束出现，y为自由出现。（5）(x)的辖域是(A(x)($x)B(x, z)($y)C(x, y)，其中x的3次出现都为约束出现，但第2次出现是受量词($x)的约束，而第1次、第3次出现是受量词(x)的约束，z为自由出现，($x)的辖域是B(x, z)。($y)的辖域是C(x, y)，其中y为约束出现，B(x, y)中的x, y都为自由出现。（6）(x)的辖域是A(x)B(x)，x为约束出现，($x)的辖域是C(x), x也为约束出现，D(x)中x的出现为自由出现。2-2将公式(x)P(x)($x)Q(x)化成前缀范式。解(x)P(x)($x)Q(x)(x)P(x)($x)Q(x)($x)P(x)($x)Q(x)($x)(P(x)Q(x)2.3 将公式(x)(y)($z)(P(x, z)P(y, z)($v)Q(x, y, v)化成前缀范式。解(x)(y)($z)(P(x, z)P(y, z)($v)Q(z, y, v)(x)(y)($z)(P(x, z)P(y, z)($v)Q(x, y, v)(x)(y)(z)(P(x, z)P(y, z)($v)Q(x, y, v)(x)(y)(z)($v)(P(x, z)P(y, z)Q(x, y, v)3-1设集合X=a, b, c, d，其上的关系R=, , , ，求t(R)。解R=, , , R2=, , , R3=, , , R4=, , , t(R)=RR2R3R4=, , , , , , , , 3-2设集合A的幂集上的包含关系，试对（1）A=a（2）A=a, b（3）A=a, b, c分别画出偏序集(A), )的哈斯图及其最小元、最大元、极小元和极大元。 解它们的哈斯图分别对应于图4.8（a），（b），（c）。图4.8 哈斯图（1）最小元、极小元都为，最大元、极大元都为a；（2）最小元、极小元都为，最大元、极大元都为a, b；（3）最小元、极小元都为，最大元、极大元都为a, b, c。读者很容易看出，对一个偏序集而言，最大（小）元不一定存在，若最大（小）元存在，则必是唯一的。而且一定是极大（小）元。出现在偏序关系哈斯图中最高（低）部分的所有元素，都是极大（小）元。不同的极大（小）元是不可比的。在非空有限偏序集合中，极大（小）元必存在，不一定唯一。3.3 X=a, b, c；Y=a, b, d，S= | x, yXY，求S的元素。解首先求出XY=a, b，那么从题意分析可知，关系S就是集合XY上的全域关系，故S=, , , 。3.4 设A=a, b, c，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性，并画出R的关系图。图4.9 关系图分析：如果R不满足自反性和反自反性，则其关系图GR上应该有的结点有自圈，有的结点没有自圈；如果R不满足对称性和反对称性，则其关系图GR上应该同时存在一对结点之间只有单向边，而同时又应该有另外一对结点之间有一对反向的单向边；如果R不满足传递性，只要GR同时存在从第一个结点到第二个结点的一条边以及从第二个结点到第三个结点的一条边，但是却不存在从第一个结点到第三个结点的边即可。例如：A上的二元关系R=, , , ，其关系图如图4.9所示。3.5 设n, mZ+（正整数集合），若集合A中恰有n个元素，那么求在A上能有多少个不同的m元关系？解因为A上共有nm个不同的m元序偶。因此，A上全关系中应当包含nm个元素，而该全关系的任一个子集都是A上的m元关系。故A上m元关系数目应当为个。3.6 若关系R和S都是对称的和传递的，试证明RS也是对称的和传递的。证明不失一般性，我们假设R和S都是定义在集合X上的二元关系。对任意的RS，那么R且S。因为R是对称的，故R，又因为S也是对称的，故S。因此RS，从而RS也是对称的。对任意的RS, RS，有R且R, S且S，因为R和S都是传递的，故R且S，那么RS，因此RS也是传递的。3.7 设A为3元素集，问：（1）A上自反且对称的关系有多少个？（2）A上反对称的关系有多少个？（3）A上既不是对称，也不是反对称的关系有多少个？解解这类题目的关键在于分析具有自反、反自反、对称、反对称性质的关系矩阵的特点，为了将这种题目的解法更加一般化，这里将A中元素的数目记为n。（1）设R为A上自反的并且对称的关系，其关系矩阵MR的主对角线元素全部为1并且是一个对称矩阵。所以，我们只要关心它的下三角矩阵即可。因为它的下三角矩阵有(n2n)/2个元素，而每个元素有两种取值（0或者1），因此，这样的关系共有个。（2）设R为A上反对称的关系，于是MR的对角元素可以任意取值，并且，考虑其下三角的任何一个位置(i, j)与其对称位置(j, i)处元素的取值，只有3种情况：均取0、(i, j)处元素取值为0而(j, i)处元素取值为1、(i, j)处元素取值为1而(j, i)处元素取值为0。因此，A上反对称的二元关系的数目为个。（3）在回答此问之前，先考虑A上对称的二元关系有多少个呢？这个问题与（1）相比，少了一个自反的限制，于是，对角线上的元素可以任意从0和1之间取值了。于是，总的数目为。再考虑到A上所有的二元关系共有个。并且在问题（2）中得知，A上反对称的二元关系的数目为个。而既对称又反对称的二元关系有2n个。于是，既不对称、也不反对称的二元关系共有+2n个。令n=3，就得本题的结果。 关系性质的证明分析：在二元关系中，由于关系的性质的定义全部是按“如则”来描述的。因此，在证明时不能采用一般的证明方法，而应采用离散数学中所特有的按定义证明方法。即证明时，首先叙述定义的前半部分“如”，将这部分的内容称为“附加的已知条件”，此时利用该“附加的已知条件”和题目本身所给的已知条件证明出定义的后半部分“则”，这部分的内容称为定义中的结论。这种证明问题的方法在于：证明时不能单纯利用题目所给的已知条件，而应同时利用定义中的“已知”，推出的并非整个定义，而推出的是定义中的结论。这与一般的证明思路：已知中间结果结论是完全不同的。另外。由于关系是一种特殊的集合，当用集合的手段来描述关系的性质时，其证明的方法也是按集合中的按定义证明方法来证。总之，在关系这一章中，可以说所有的证明几乎都采用按定义证明方法。大家只要掌握了这种方法，证明问题就变得简单多了。3.8 R是二元关系，且R=RRRR，选择下面的哪一个一定是传递的。（1）R （2）RR （3）RRR （4）RRRR解根据定理4.10知，若二元关系R传递的，一定有RR R。注意到R=RRRR，所以RRR=RR(RRRR)=(RRR) (RRR)。于是，R的三次幂一定是传递的。那么正确答案是（3）。3.9 求关系的合成。设A=1, 2, 3, 4，A上二元关系R1, R2分别定义为R1=, , ，R2=, , , ，请计算R1R2，R2R1，R12，R22。解R1R2=, R2R1=R12=, , R22=, , 3.10 证明题。在这类证明题中，通常为证明两个关系之间的等于，包含及被包含关系。由于关系是一种特殊的集合，在证明此类问题时，通常任选一个关系的元素，然后得出它也属于另一个关系。设R, S, T均为A上的二元关系，那么证明(ST)R=(SR)(TR)证明选择任意的使得(ST)R，推导如下：(ST)R$y(ST)R)$y(ST)R)$y(SR)$y(TR)SRTR(SR)(TR)3.11 “找出三个元素的集合A和A上关系R，使R, R2, R3, R4两两不等”是可能的吗？如可能请具体做出，并说明这一现象与t(R)=不矛盾。解是可能的。令A=a, b, cR=, , , R2=, , , , R3=, , , , , , , R4=, , , , , , R, R2, R3, R4两两不等, 但此时=所以这一现象与t(R)=不矛盾。3.12 将n个元素的集合划分成两个分块，共有多少种不同的分块？解划分成两个分块，则每个分块至少有一个元素，一个分块取i个元素的不同分类法与取ni个元素的不同分类法一样，故共有： (+)/2=(2n2)/2=2n11(种)。3.13 设A=1, 2, 3, 4, 5，那么（1）A上共有多少个二元关系？（2）上述关系中，有多少个是等价关系？解 （1）考虑A上的关系矩阵的数目，一个关系矩阵唯一地确定了一个二元关系由于集合中有5个元素，所以关系矩阵是一个55的矩阵，共有25个元素，每个元素可以是0，也可以是1，所以共有225个不同的二元关系。（2）由于某集合上的划分与该集合上的等价关系之间是一一对应的关系，所以A有多少种划分就有多少个等价关系。以划分中等价类中元素数目分类： 等价类中元素最多的只有一个元素的划分只有1种； 等价类中元素最多的有两个的划分共有+=40种； 等价类中元素最多的有三个的划分共有+=20种； 等价类中元素最多的有四个的划分共有=5种； 等价类中元素最多的有五个的划分只有1种。因此，总共的等价关系共有1+40+20+5+1=67种。请读者根据此题归纳出一般的结论。3.14已知N及其关系R如下，试说明R是等价关系，并指出等价类是什么。N是自然数集，R= | ni/nj能表示成2n形式，n为任意整数。解niX，有ni/nj=1=20，故R，所以R是自反的。ni, njX，若R，即ni/nj=2k（k是整数），所以nj/ni=2k，所以R，所以R是对称的。ni, nj, npX，若RR，则ni/nj=2k1ni/nj=2k2（k1, k2是整数），则ni/np=2k1+k2，则R，故R是传递的。总之，R是X上的等价关系，等价类是：1R=1, 2, 4, 8, 16, , 2n, 3R=3, 321, 322, , 32n, 5R=5, 521, 522, , 52n, 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；子集B3=b, c, d, e的上界为a，下界不存在，上确界为a。4.1找出下图中所有不同的圈。解C3：, v2 v3 v6 v2, v2 v6 v7 v2C4：v2 v3 v6 v7 v2, v3 v4 v5 v6 v3C5：v2 v3 v4 v5 v6 v2C6：v2 v3 v4 v5 v6 v7 v2 图 含圈、路的简单无向图10-3 给定一图G=(V, E)如右图所示。图 G解从上面的矩阵中可以看到一些结论，如v1与v2之间有两条长度为3的路，结点v1与v3之间有一条长度为2的路，在结点v2有四条长度为4的回路。【例10.10】 图10.29的两个图是否同构？解图10.29的两个图虽然形状不同，但它们表示了同一个图G=(V(G), E(G)其中V(G)=a, b, c, dE(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所示。 图10.29 例10.10图 图10.30 例10.11图令(u, v)-通路为P3 ，设最长通路的长为l，u将P1分为两段，必有一段的长，设为P4；同理v分P2为两段，有一段设为P5，其长。于是|P4+P3+P5|l，此与P1、P2最长相矛盾（此处“+”意指二通路相接）。【例10.12】 （1）证明若有v个结点的G是简单图，且d1，则G连通。（2）当v为偶数时，找出一个非连通的(1)-正则简单图。证明 （1）用反证法。假设G至少有两个连通分支，但至少有一个分支的结点个数，这个分支中结点的度数最大为1，这是因为G是简单的，这与d1矛盾。（2）有两个连通分支，每个分支有个结点的完全图，即为所求的图。【例10.13】 在88棋盘的64个方格中分别填入164个数字。求证：无论怎么填入这些数，总能找到两个具有公共边的两方格，里面所填数字之差不少于5。证明假设在64个方格中已填好64个数字。以这64个数字为结点集V构作简单无向图 i和j所在的两方格有公共边。易知，G的直径。若相邻两结点数字之差4，则G中任何两结点数字之差414=56。但存在两结点数字分别为1和64，且641=6356，矛盾。【例10.14】 证明若G是简单图且，则G有一条长为k的路。证明若P是G中的一条最长路，它的长l小于k，设P为，由假定，从而在P外存在一结点v0和v1邻接，于是是G中长于P的一条路，这和P是G中最长路矛盾，故。我们可以在P中取一段长为k的路，故G中存在长为k的路。【例10.15】 （1）证明若G为e条边、v个结点的简单图，且则G是连通的。（2）对vl，求一个非连通单图G使得。证明 （1）若G不连通，可分为两个结点数分别为v1, v2的互不连通子图G1, G2。易知v1+v2=v于是这与矛盾。（2）即为所求的单图。【例10.16】 试证：若G是连通单图，但不是完全图，则G存在如下三个结点u, v和w，满足uv，vw E，uw E。证明由假定G不是完全图，故存在，；由于G是连通的，故存在一条连接的最短路，设为。显然，否则和最短路假定矛盾。于是我们令（当n=1时，u2=w1），即为所求。【例10.17】 试证：若，则G含有圈。证明由于，从而由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的邻接矩阵为求G的可达性矩阵。解故由此可知图G中任意两个结点间均是可达的，并且任意一个结点均有回路，此图是连通图。上述计算可达性矩阵的方法还是比较复杂，因为可达性矩阵是一个元素为0或1的布尔矩阵，由于在每个Al中，对于两个结点间的路的数目不感兴趣，它所关心的是该两结点间是否有路存在，因此可将矩阵A，A2，An分别改为布尔矩阵A, A(2), , A(n)，故P=AA(2)A(n)，其中A(i)表示在布尔运算下A的i次方。【例10.20】 计算图10.27a对应的完全关联矩阵的秩