离散数学练习解答

《离散数学练习解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《离散数学》练习解答第一篇数理逻辑解答题：1、将下列命题符号化：（1）明天不下雨又有空的话，我就会去打球。（2）只要她生病了，我都会去看她（只有她生病了，我才会去看她）。（3）每个旅客或坐头等舱或坐二等舱。（4）有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。解（1）设：明天不下雨；：明天我有空；：明天我去打球。则该命题可符号化为。（2）设：她生病；：我去看她。则该命题可符号化为。（3）设是旅客；坐；是头等舱位；是二等舱位。则该命题可符号化为。（4）设是汽车；是火车；比慢。则该命题可符号化为2、求公式的主合

2、取范式和主析取范式，并求使取值为真的所有指派。解：的主析取范式：所以的主合取范式为使取值为真的所有指派为：第二篇集合论6二、解答题1、设集合，为上的整除关系，试求：（1）画出偏序集的Hasse图；（2）写出中的最大元、最小元、极大元、极小元；（3）写出的子集的上界、下界及上、下确界。解：（1）的Hasse图如下：111796312241058（2）中没有最大元；最小元是1；极小元也是1；极大元有7，8，9，10，11，12。（3）没有上界，也就没有上确界；下界是1；下确界也是1。2、（自然映射问题）习题八（P1

3、62）第16题。（屈婉玲《离散数学》，下同）设，R为上的等价关系，且求自然映射。解：，，3、（计数问题）习题六（P99）第21，23题。（1）某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。解：设S为该班学生集合，A、B、C分别表示会打篮球、排球和网球的学生集合，则据题设，有，，，，，，因为会打网球的人都会打蓝球或排球，因此有于是由包含排斥原理知或从而不会打球的人数为三、证明题61、设是非

4、空集合上的等价关系，试证的逆关系也是上的等价关系。证明1）具有自反性：，因为是上的等价关系，具有自反性，有，从而，即具有自反性。2）具有对称性：，若，则。因为具有对称性，因此，从而，即具有对称性。3）具有传递性：，若，则。因为具有传递性，因此，从而，即具有传递性。所以是上的等价关系。2、设是非空集合上的偏序关系，试证的逆关系也是上的偏序关系。证明1）具有自反性：，因为是上的等价关系，具有自反性，有，从而，即具有自反性。2）具有反对称性：，若，则。因为具有反对称性，因此，即也具有反对称性。3）具有传递性：，若，则

5、。因为具有传递性，因此，从而，即具有传递性。所以是上的偏序关系。第三篇代数系统二、解答题1、设，，试列出中的所有函数，并给出上合成运算的运算表。（P178第2题）解：中的所有函数共有四个，分别是：；；；。运算表如下：63、已知3次对称群，若。（1）试验证是的一个正规子群；（2）求出子群的所有左陪集及在的指数；（3）求出的子群格，并画出它的偏序图。解：（1）因为，故是的一个正规子群。（2）的子群：1阶子群有；2阶子群有，和；3阶子群有;6阶子群有.所以的子群格为，它的偏序图如下：<(12)><(13)><(23)

6、><(123)>S3(3)子群的所有左陪集为：，，第四篇图论二、计算题1、设图G为平面图，它的边数是区域数的2倍，并且有一个6次顶点，四个3次顶点，三个2次顶点，其余顶点都是1次的。试求图G的顶点数、边数和区域数。6解设图的顶点数与边数分别为，则由欧拉公式知的区域数为（1）根据题设，有或（2）又由图论握手定理根据题设，即得亦即（3）联立（1）、（2）、（3）解得2、一棵树有2个2次分枝点，1个3次分枝点，3个4次分枝点，其余顶点都是树叶，问这棵树有几片树叶？解设该树的顶点数与边数分别为，而树叶的总片数为。则由树

7、的性质，有又依题设，有于是可得又由图论握手定理根据题设，即得或将代入上式，即得所以有3、设有无向图，其中，而的邻接矩阵，且当时，边的权数为。试画出图，并求图的一个最小生成树及最小生成树的权数。解：图G如下。6a13a2a58a35a469765a13a2a4a5a3565应用破圈法可得最小生成树，其权为。三、应用及证明题：3、试证，在完全二叉树中，边的总条数应该等于,其中的是树叶的总片数。解设完全二叉树中，边的总条数和顶点数分别为，则由树的性质，有在完全二叉树中，除树根的次数为2，树叶的次数为1，其余顶点的次数

8、均为3，于是由图论握手定理可得将代入上式，即得所以证毕。6