离散数学期末习题

前言：

        本文适用于应对HUEL离散数学期末考试，重点整理了HUEL离散数学期末考试范围内的题型，既可以应对HUEL离散数学期末考试，亦可以作为数据结构与算法的预备知识。

目录

例题【数理逻辑专题】：

例题【集合论专题】：

例题【图论专题】：

例题【数理逻辑专题】：

 谓词公式

 本题考察量词辖域收缩与扩张等值式 （《离散数学》第二版 74页）

约束变元与自由变元

命题的判断 

1.

2. 

量词辖域

1.

 2.

3.

前束范式问题

 前束范式的定义：

命题逻辑推理

例题【集合论专题】：

二元关系

1.

2.推荐阅读：关系中，对称和反对称可以同时成立吗？ -来自知乎问题 

​

3.

​

关系图表： 

​

关系闭包

​

关系的闭包有三类：

自反闭包:添加有序对, 变成自反的最小的二元关系

对称闭包:添加有序对, 变成对称的最小的二元关系

传递闭包:添加有序对, 变成传递的最小的二元关系

例如有如下关系：

​

自反闭包：每个结点都加上环，变成自反闭包

​

对称闭包：在有单向边的两个结点间再添加一条逆向的边

​

传递闭包：a→b，b→c，则必须添加a→c；

再举个例子：

​

空集的定义

1.只需记住一点：空集是任何集合的子集，空集是任何非空集合的真子集

​

2.幂集是一个集合中所有的子集构成的集合

​

 等价关系、偏序关系和相容关系：

推荐阅读：集合论—等价关系与偏序关系 CSDN博主：白水baishui

等价关系的定义：

​

 偏序关系的定义：

​

相容关系的定义：

定义：设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R 是相容关系

​

关系图：

​

例题【图论专题】：

欧拉回路和通路

欧拉回路定义：图中所有边一次且仅有一次遍历所有顶点的回路；

判定：图 G为无向连通图，且图G所有结点的度数均为偶数

           图 G为有向连通图，且所有节点入度等于出度

欧拉通路定义：图中所有边一次且仅有一次遍历所有顶点的通路；

判定：图 G为无向连通图，且图G有0或2个奇度结点

           图 G为有向连通图，除了两端点外其余节点入度=出度，1个端点入度比出度大1，1个端点入度比出度小1建议只记忆欧拉回路的判定

回路和通路的区别？

树的基本定义

哈斯图问题 

1.

推荐阅读：哈斯图 寻找 极小元与极大元 最小元与最大元 上界与下界 最小上界(上确界)和最大下界(下确界)（一看就会）附一练习题 CSDN博主：我不想起名字呀

哈斯图的画法，以及利用哈斯图寻找极大元之类 知乎题主：被吊打的学渣

2.

欧拉图问题

推荐阅读：欧拉图的基本概念以及判定方法 CSDN博主：我是鶸

1.有向图一般不考

汉密尔顿图：

汉密尔顿通路：图G中一条路径经过了每个点，那么这条路径即为汉密尔顿通路；

汉密尔顿回路：图G中一条路径经过了除 SS 外每个点并且 SS 只经过过两次，即为汉密尔顿回路

割边的定义：

费用最低问题：

推荐阅读：Kruskal求最小生成树的权值之和 CSDN博主：五星上将美玉

Express my thanks to DX·Xing