分 图四 最小生成树的权为分 试画棵带权为，的最优二叉树，并计算该最优二叉树的权 解最优二叉树如图二所示 分 图二     权为 设谓词公式，试 写出量词的辖域指出该公式的自由变元和约束变元 量词的辖域为，，分 量词的辖域为，分 量词的辖域为，分 自由变元为，中的，以及，中的分 约束变元为  ， 且，试求， 解 ∩ 设，且真式 五计算题每小题分，本题共分 设集合，试计算 ∩∩ 解∩ 真式 解正确因为，由真值表 ∧∨   图     可知，该命题公式为永 则存在条欧拉回路 设是个有个结点条边的连通图，则为平面图 解，不满足设是个有个结点条边的连通简单平面图，若，则 命题公式为永同时结点度数都是偶数 设是个连通平面图，且有个结点条边，则有个面 答案正确 定理，连通平面图的结点数为，边数是，面数为，则欧拉公式 成立 所以或，所以是集合中的最大元按照最 小元的定义，在集合中不存在最小元 如果图是无向图，且其结点度数均为偶数，则图存在条欧拉回路 答如果图是无向图，且图是连通的，有最大元，也没有最小元 其中是极大元 若偏序集的哈斯图如图所示，则集合的最大元为，最小元不存在 解正确 对于集合的任意元素，均有， 所以，∪∩是自反的 若偏序集的哈斯图如图所示， 则集合的最大元为，最小元不存在 答，集合没是自反的 因为但是所以不是对称的 如果和是上的自反关系，判断结论∪∩是自反的是 否成立并说明理由 答成立因为任意，有，，都有且结果唯。 若集合上的二元关系，则是自反的关系是对称的关系 答因为所以不 答不构成函数因为，但没有定义，所以不构成函数 不构成函数因为，但没有定义，所以不构成函数 满足。因为任意函数，并 说明理由 ， 是人，学习努力，  四判断说明题每小题分，本题共分判断下列各题正误，并说明理由 设集合，判断下列关系是否构成为 将语句有人去上课翻译成谓词公式 解设是人，去上课，分  将语句所有的人都学习努力翻译成命题公式 解设下午五点开，次列车下午六点开，分 命题公式为∧∨∧ 将语句小张学习努力，小王取得好成绩翻译成命题 设小张学习努力，小王取得好成绩，分 则命题公式为下午五点开，次列车下午六点开，分 命题公式为∧∨∧ 将语句小张学习努力，小王取得好成绩翻译成命题 设小张学习努力，小王取得好成绩，分 则命题公式为 将语句有人去上课翻译成谓词公式 解设是人，去上课，分  将语句所有的人都学习努力翻译成命题公式 解设是人，学习努力，  四判断说明题每小题分，本题共分判断下列各题正误，并说明理由 设集合，判断下列关系是否构成函数，并 说明理由 ， 答不构成函数因为，但没有定义，所以不构成函数 不构成函数因为，但没有定义，所以不构成函数 满足。因为任意，都有且结果唯。 若集合上的二元关系，则是自反的关系是对称的关系 答因为所以不是自反的 因为但是所以不是对称的 如果和是上的自反关系，判断结论∪∩是自反的是 否成立并说明理由 答成立因为任意，有， 所以，∪∩是自反的 若偏序集的哈斯图如图所示， 则集合的最大元为，最小元不存在 答，集合没有最大元，也没有最小元 其中是极大元 若偏序集的哈斯图如图所示，则集合的最大元为，最小元不存在 解正确 对于集合的任意元素，均有或，所以是集合中的最大元按照最 小元的定义，在集合中不存在最小元 如果图是无向图，且其结点度数均为偶数，则图存在条欧拉回路 答如果图是无向图，且图是连通的，同时结点度数都是偶数 设是个连通平面图，且有个结点条边，则有个面 答案正确 定理，连通平面图的结点数为，边数是，面数为，则欧拉公式 成立 所以 则存在条欧拉回路 设是个有个结点条边的连通图，则为平面图 解，不满足设是个有个结点条边的连通简单平面图，若，则 命题公式为永真式 解正确因为，由真值表 ∧∨   图     可知，该命题公式为永真式 五计算题每小题分，本题共分 设集合，试计算 ∩∩ 解∩  ∩ 设，且， 且，试求， 解  图，其中，试 画出的图形表示 求出每个结点的度数 画出图的补图的图形 解关系图 补图 设集合，或，试 写出的有序对表示 画出的关系图 说明满足自反性，不满足传递性 解分 关系图为 因为均属于，即的每个元素构成的有序对均在中， 故在上是自反的。 因有与属于，但不属于，所以在上不是传递的。              设集合试计算  解，分 ，分 求出如图所示赋权图中的最小生成树要求写出求解步骤，并求此最小生成树 的权 解用算法求产生的最小生成树步骤为 ，选 ，选 ，选 ，选 ，选 ，选分 最小生成树如图四所示 分 图四 最小生成树的权为分 试画棵带权为，的最优二叉树，并计算该最优二叉树的权 解最优二叉树如图二所示 分 图二     权为 设谓词公式，试 写出量词的辖域指出该公式的自由变元和约束变元 量词的辖域为，，分 量词的辖域为，分 量词的辖域为，分 自由变元为，中的，以及，中的分 约束变元为，中的与中的，以及，中的 设谓词公式，，试 写出量词的辖域指出该公式的自由变元和约束变元 量词的辖域为分 量词的辖域为，分 自由变元为公式中的与中的，分 约束变元为，的与 求命题公式的主析取范式主合取范式 解 极小项极大项         主析取范式极小项析取   主合取范式极大项合取 求∨∨的析取范式，合取范式 解∨∨ ∨∨∨分 ∧∨∨ ∨∨∧∨∨∨∨析取合取范式 六证明题本题共分 试证明集合等式 证明设∩∪，∩∪∩，若∈，则∈且∈∪，即∈ 且∈或∈且∈， 也即∈∩或∈∩，即∈，所以 反之，若∈，则∈∩或∈∩， 即∈且∈或∈且∈ 也即∈且∈∪，即∈，所以 因此 试证明∧∧ 证明 ∧ ∧   ∧ 离散数学复习资料年月 单项选择题每小题分，本题共分 若集合则下列表述正确的是 ，且，且，且，且 设有向图与如图所示，则下列结论成立的是 图 是强连通的是强连通的 是强连通的是强连通的 设图的邻接矩阵为                 则的边数为 无向简单图是棵树，当且仅当 连通且边数比结点数少连通且结点数比边数少 的边数比结点数少中没有回路 下列公式为重言式   设是到的二元关系，且， ，则不是从到的函数 和 和 设是上的整除关系则集合的最大元 最小元上界下界依次为 无无 若集合的元素个数为，则其幂集的元素个数为 设完全图有个结点，条边，当时，中存在欧拉回路 为奇数为偶数为奇数为偶数 已知图的邻接矩阵为 ， 则有 点，边点，边 点，边点，边 无向完全图的不同构的生成子图的个数为 阶无向完全图中的边数为  在图中，结点总度数与边数的关系是      二填空题每小题分，本题共分 命题公式的真值是 若，，则的自反闭包为 已知棵无向树中有个结点，度，度，度的分支点各个，的树叶数为 ∨，中的自由变元为，中的 设集合那么集合的幂集是 如果和是上的自反关系，则∪，∩，中自反关系有个 设图是有个结点的连通图，结点的总度数为，则可从中删去 条边后使之变成树 无向图存在欧拉回路，当且仅当所有结点的度数全为偶数且连通