离散数学练习(部分)解答.doc

离散数学练习解答福建农林大学东方学院2009 2010 学年第二学期第一篇 数理逻辑二、解答题：1、 将下列命题符号化：（1） 明天不下雨又有空的话，我就会去打球。（2） 只要她生病了，我都会去看她（只有她生病了，我才会去看她）。（3） 每个旅客或坐头等舱或坐二等舱。（4） 有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。解 （1） 设：明天不下雨；：明天我有空；：明天我去打球。则该命题可符号化为 。（2）设 ：她生病；：我去看她。则该命题可符号化为 。（3）设 是旅客；坐；是头等舱位；是二等舱位。则该命题可符号化为 。（4）设 是汽车；是火车；比慢。则该命题可符号化为 2、 求公式的主合取范式和主析取范式，并求使取值为真的所有指派。解：的主析取范式： 练习解答第1页（共9页）所以的主合取范式为使取值为真的所有指派为：注意：若没有要求用等值演算，也可采用真值表求。三、逻辑推理题1、用演绎法证明：P（QR），SP，Q, RS.（应注明每一步推理所采用的推理规则）。证明：（1） （假设，否定结论引入） （2） （1）置换，T规则）（3） （前提，P规则）（4） （2），（3）析取三段论，T规则）（5） （前提，P规则）（6） （4），（5）假言推理，T规则）（7） （前提，P规则） （8） （7），（6）假言推理，T规则） （9） （前提，P规则） （10） （8），（9）合取，T规则）所以2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。（1） 规则（前提引入）（2） (1) （3） 规则（前提引入）（4）(3) （5） (2),(4)假言推理（6） (5) 练习解答第2页（共9页）解 该推导过程中由（3）推出结论（4）是错误的。这是因为第（2）步中已有变元出现，因此由第（3）步中应用规则时,不能再引入变元。 3分结论是有效的，其正确推导过程为：（1） 规则（2）(1) （3） 规则（4） (3) （5） (2),(4)假言推理（6） (5) 3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。（要求：设：白队第一；：黄队第二；：红队第三；：绿队第四。并写出前提和结论的符号化及推理过程。）解 前提：结论： 证明：（1） 附加前提引入 （2） 前提引入 （3） （1），（2）析取三段论（4） 前提引入（5） （3），（4）假言推理（6） 前提引入 （7） （6），（5）拒取第二篇 集合论二、解答题1、设集合，为上的整除关系 ，试求：（1）画出偏序集的Hasse图；（2）写出中的最大元、最小元、极大元、极小元；（3）写出的子集的上界、下界及上、下确界。练习解答第3页（共9页）解：（1）的Hasse图如下：111796312241058（2）中没有最大元；最小元是1；极小元也是1；极大元有7，8，9，10，11，12。（3）没有上界，也就没有上确界；下界是1；下确界也是1。2、（自然映射问题）习题八（P162）第16题。 （屈婉玲离散数学，下同）设，R为上的等价关系，且求自然映射。解：因为，所以，3、（计数问题）习题六（P99）第21，23题。（1）某班有25个学生，其中14人会打篮球，12人会打排球， 6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。解：设S为该班学生集合，A、B、C分别表示会打篮球、排球和网球的学生集合，则据题设，有，因为会打网球的人都会打蓝球或排球，因此有于是由包含排斥原理知 或 从而不会打球的人数为 （2）使用包含排斥原理求不超过120的素数个数。解：因为112=121，故不超过120的合数至少含有2、3、5或7这些素因数之一。为此，设练习解答第4页（共9页）现在先要求出不能被这4个素数整除的数的个数。 由于 ，且因此，不能被2、3、5及7整除的整数有又因为2、3、5及7不满足上述条件，被“筛掉”，但它们是素数，而数 1 则相反。故不超过120的素数有个*4、（特征函数问题）习题八（P162）第14题。设S为集合，A，B是S的子集，表示T的特征函数。若，求。*5、设，则，cardA 2 。A上可定义个二元关系。其中 4 个自反关系， 4 个反自反关系， 8 个对称关系， 12 个反对称关系， 2 个等价关系， 3 个偏序关系。 练习解答第5页（共9页） 注意：A上的二元关系是的一个子集，若，则的子集有个。空关系即空集既是反自反的，也是对称的，还是反对称的。应掌握本例中每一类关系具体的有哪些。S中有个函数，其中 2 个是双射。*6、（哈斯图问题）（P127例7.19）设集合，为幂集上的包含关系 ，试求：（1）画出偏序集的Hasse图；（2）写出中的最大元、最小元、极大元、极小元；（3）写出的子集的上界、下界及上、下确界。*7、（哈斯图问题）（P127例7.20）已知偏序集的哈斯图如下，求关系R的集合表示。三、证明题1、设是非空集合上的等价关系，试证的逆关系也是上的等价关系。证明 1）具有自反性：，因为是上的等价关系，具有自反性，有，从而，即具有自反性。2）具有对称性：，若，则。因为具有对称性，因此，从而，即具有对称性。3）具有传递性：，若，则。因为具有传递性，因此，从而，即具有传递性。所以是上的等价关系。2、设是非空集合上的偏序关系，试证的逆关系也是上的偏序关系。练习解答第6页（共9页）证明 1）具有自反性：，因为是上的等价关系，具有自反性，有，从而，即具有自反性。2）具有反对称性：，若，则。因为具有反对称性，因此，即也具有反对称性。3）具有传递性：，若，则。因为具有传递性，因此，从而，即具有传递性。所以是上的偏序关系。3、设（0，1）和0，1为实数区间，证明：提示：参考课本第148页例8.9（5）的解答。第四篇 图论三、应用及证明题：1、（哈米尔顿回路问题）习题十五（P306）第15题。某工厂生产由6种颜色的纱织成的双色布。已知在一批双色布中，每种颜色至少与其他3种颜色相搭配。证明可以从这批双色布中挑出3种，它们由不同颜色的纱织成。解：构造无向简单图，使其中表示6种颜色之一，而由已知条件可知，有 于是根据无向简单图有哈密顿回路的判定定理，为哈密顿图。设 为中的一条哈密顿回路，任何两个顶点若在C中相邻，则在这批布中有这两个顶点代表的颜色搭配成的双色布。于是，在这批布中有与，与以及与搭配成的3种双色布，它们使用了全部6种颜色。练习解答第7页（共9页）*2、（最短路问题）习题十五（P307）第22题。某工厂使用一台设备，每年年初要决定是继续使用，还是购买新的。预计该设备第一年的价格为11万元，以后每年涨1万元。使用的第1年，第2年，第5年的维修费分别为5，6，8，11，18万元。使用1年后的残值为4万元，以后每使用1年残值减少1万元。试制定购买维修该设备的5年计划，使总支出最小。解：第年初购买使用到第年初（或第年末）所需的总费用（购买费+维修费-残值）如下表；ji2 3 4 5 6 1 2 3 4 5 12 19 28 40 59 13 20 29 41 14 21 30 15 22 1640593028211912 13 14 15 1622v1 v2 v3 v4 v5 v6 20 41 29根据上表构造有向带权图G，其中顶点表示第年初（或第年末），到的边表示在第年初购买设备使用到第年末，其权为所需的总费用。练习解答第8页（共9页）应用Dijkstra标号法计算结果如下表：步骤顶点1 2 3 4 5 6 V1 V2 V3 V4V5V6（V1，0）* （V1，） （V1，12）*（V1，） （V1，19） （V1，19）*（V1，） （V1，28） （V1，28） （V1，28）*（V1，） （V1，40） （V1，40） （V1，40） （V1，40）*（V1，） （V1，59） （V2，53） （V3，49） （V3，49） （V3，49）*从顶点1到6的最短路径v1 v3 v6，距离为4