--- description: 发布于 2023-06-18 categories: - study date: 2023-06-18 slug: discrete-mathematics-final-review title: 离散数学 期末复习 updated: tags: - study - discrete-mathematics copyright: false --- # 离散数学 期末复习 ## 第 1 章 命题逻辑 ### 1.2 等值演算 ![扫描件_等值式_1](https://media.opennet.top/i/2023/06/16/648bfe9e965de.jpg) #### 真值表法 ![扫描件_例1-7试用真值表法判断](https://media.opennet.top/i/2023/06/16/648bff990ee18.jpg) #### 等值演算法 ![扫描件_例1-9用等值演算方判断](https://media.opennet.top/i/2023/06/16/648c001390a0a.jpg) #### 题：等值演算 ![IMG_1066](https://media.opennet.top/i/2023/06/16/648c03227adfc.png) #### 题：等值演算 ![image-20230618151259715](https://media.opennet.top/i/2023/06/18/648eae7c9d3bd.png) ### 1.3 范式 由合取式析取起来的式子是析取范式 由析取式合取起来的式子是合取范式 主析取范式和主合取范式互补 #### 主析取范式 主合取范式 ![扫描书籍_离散数学概论_1](https://media.opennet.top/i/2023/06/16/648c077c7cc7b.jpg) ![扫描书籍_离散数学概论_2](https://media.opennet.top/i/2023/06/16/648c079ba1b08.jpg) #### 题：主析取范式 主合取范式 主析取范式最好用 $m_x$ 的析取来表示 ![IMG_1067](https://media.opennet.top/i/2023/06/16/648c05dd7e949.png) ## 第 2 章 一阶逻辑 ### 2.1 一阶逻辑概念 #### 个体词 谓词 个体词：个体常项 或 个体变项 个体域：个体词的范围 谓词描述关系 P(x) 或 M(x) 表示一个一元谓词逻辑 #### 量词 ![扫描件_定义2_3量词是描述个体常项与个体变项之_1](https://media.opennet.top/i/2023/06/16/648c0916a5990.jpg) ![扫描件_第2章一阶逻辑_1](https://media.opennet.top/i/2023/06/16/648c0a790c6d9.jpg) 量词不能随意调换顺序 量词的优先级比逻辑联结词高 ### 2.2 谓词逻辑解释 分类 #### 辖域 约束变元 自由变元 ![扫描书籍_离散数学概论_1(1)](https://media.opennet.top/i/2023/06/16/648c0c3382921.jpg) 约束变元换名规则：把指导变元和被指导的约束变元换名 自由变元换名规则：把自由出现的变元换名 ![扫描书籍_离散数学概论_2(1)](https://media.opennet.top/i/2023/06/16/648c0cf03c861.jpg) #### 解释 ![扫描书籍_离散数学概论_2(1) - 副本](https://media.opennet.top/i/2023/06/16/648c0d2fa25b9.jpg) ![扫描件_例2-10给定解释I如下](https://media.opennet.top/i/2023/06/16/648c0dbf22454.jpg) #### 题：解释 ![image-20230618174416183](https://media.opennet.top/i/2023/06/18/648ed1f07d5f2.png) ![image-20230618174425409](https://media.opennet.top/i/2023/06/18/648ed1f9d918b.png) #### 分类 永真式、永假式、可满足式 ### 2.3 逻辑等值式 前束范式 #### 一阶逻辑等值式 ![扫描件_定理2-2否定等值式_1](https://media.opennet.top/i/2023/06/16/648c1e702d20e.jpg) ![扫描件_定理24量词分配律_1](https://media.opennet.top/i/2023/06/16/648c1e87b2223.jpg) #### 前束范式 ![扫描件_一个谓词公式可以演算成与之等值的标准形式_1](https://media.opennet.top/i/2023/06/16/648c1f5964762.jpg) #### 题：前束范式 注意运算前先换名 ![IMG_1069](https://media.opennet.top/i/2023/06/16/648c20f9b6d24.png) #### 题：消去量词 ![image-20230618174252782](https://media.opennet.top/i/2023/06/18/648ed19d6ef89.png) ![image-20230618174303742](https://media.opennet.top/i/2023/06/18/648ed1a7d3ae8.png) ### 2.4 逻辑推理 #### 构造证明法 ![扫描件_构造证明法_1](https://media.opennet.top/i/2023/06/16/648c2e9c43b43.jpg) ![扫描件_构造证明法_2](https://media.opennet.top/i/2023/06/16/648c2eac9812d.jpg) #### 附加前提证明法 ![扫描件_附加前提证明法_1](https://media.opennet.top/i/2023/06/16/648c2fa452c51.jpg) #### 归谬法（反证法） ![扫描件_归谬法是把要证结论的否定式与原前提组成新_1](https://media.opennet.top/i/2023/06/16/648c3043d77ca.jpg) #### 题：命题逻辑推理 ![IMG_1070](https://media.opennet.top/i/2023/06/16/648c31ab12874.png) #### 一阶逻辑推理 ![扫描件_全称实例_1](https://media.opennet.top/i/2023/06/16/648c341353a54.jpg) ![Screenshot_2023-06-16-18-08-37-322_com.quark.browser-edit](https://media.opennet.top/i/2023/06/16/648c34d13f91d.jpg) #### 题：一阶逻辑推理 ![IMG_1071](https://media.opennet.top/i/2023/06/16/648c3791269c7.png) #### 题：一阶逻辑推理 ![image-20230618151358257](https://media.opennet.top/i/2023/06/18/648eaeb6beb2e.png) ![image-20230618151413845](https://media.opennet.top/i/2023/06/18/648eaec69fbe0.png) ## 第 3 章 集合和矩阵 ### 3.1 集合 空集 Ø 全集 E #### 幂集 ![扫描件_ZZpBP1144图31AN的文氏图图3_1](https://media.opennet.top/i/2023/06/17/648d39c8bfe61.jpg) #### 相对补 绝对补 对称差 ![扫描件_定义3-10设AB为两个集合由在集合A中_1](https://media.opennet.top/i/2023/06/17/648d3ab805189.jpg) ![扫描件_定义3-10设AB为两个集合由在集合A中_2](https://media.opennet.top/i/2023/06/17/648d3abdf3a69.jpg) #### 题：集合运算 ![IMG_1074](https://media.opennet.top/i/2023/06/18/648eba08c1d75.png) #### 集合证明 ![扫描件_同一律_1](https://media.opennet.top/i/2023/06/17/648d3c1b616ff.jpg) #### 命题演算法 ![扫描件_例3-9证明(AB)=AB_1](https://media.opennet.top/i/2023/06/17/648d3d9df2d8a.jpg) #### 等式代入法 ![扫描件_例3-11证明(AB)(AC)=(BC)_1](https://media.opennet.top/i/2023/06/17/648d3e0c9b743.jpg) #### 题：集合证明 ![IMG_1072](https://media.opennet.top/i/2023/06/17/648d42243b73e.png) ### 3.2 矩阵 #### 乘法 布尔矩阵 ![扫描件_布尔矩阵运算_1](https://media.opennet.top/i/2023/06/17/648d98fe21760.jpg) ## 第 4 章 关系和函数 ### 4.1 关系 #### 有序对 元组 ![扫描件_定义4_1由元素a和b按一定的顺序排列成_1](https://media.opennet.top/i/2023/06/17/648d99cca75fd.jpg) #### 笛卡尔积 ![扫描件_定义4-3设AB为集合有序对a b的第一_1](https://media.opennet.top/i/2023/06/17/648d9a263c3de.jpg) #### 二元关系 全域关系 $E_A$ 恒等关系 $I_A$ ![扫描件_定义4_5若一个集合是空集或它的元素都是_1](https://media.opennet.top/i/2023/06/17/648d9b82b8a99.jpg) #### 集合表示法 ![扫描件_集合表示方法_1](https://media.opennet.top/i/2023/06/17/648db31d18b5e.jpg) #### 关系图表示法 ![扫描件_关系图表示方法_1](https://media.opennet.top/i/2023/06/17/648db3ec5f7e5.jpg) ![扫描件_关系图表示方法_2](https://media.opennet.top/i/2023/06/17/648db3f87e0b8.jpg) #### 矩阵表示法 ![扫描件_矩阵表示方法_1](https://media.opennet.top/i/2023/06/17/648db59c034e2.jpg) #### 定义域 值域 域 ![扫描件_定义4-10设R是一个二元关系由R的所有_1 - 副本](https://media.opennet.top/i/2023/06/17/648db6f34bb01.jpg) #### 关系的逆 ![扫描件_定义4-10设R是一个二元关系由R的所有_1](https://media.opennet.top/i/2023/06/17/648db72276aeb.jpg) ![image-20230618155802533](https://media.opennet.top/i/2023/06/18/648eb90b1e9c0.png) #### 复合关系 ![扫描件_RoR=RR(x)_1](https://media.opennet.top/i/2023/06/17/648db8990b2bf.jpg) #### 关系幂集 ![扫描件_RoR=RR(x)_2](https://media.opennet.top/i/2023/06/17/648db8aeca690.jpg) #### 题：关系运算 ![image-20230618165036488](https://media.opennet.top/i/2023/06/18/648ec55d1631a.png) ![image-20230618165049564](https://media.opennet.top/i/2023/06/18/648ec569b9c1d.png) #### 自反 对称 传递 反自反就是任何一个元素都不满足自反 不自反的关系不一定是反自反关系，反自反关系一定是不自反的关系 对称同理 ![扫描件_自反关系_1](https://media.opennet.top/i/2023/06/17/648dba60e5218.jpg) ![扫描件_自反关系_2](https://media.opennet.top/i/2023/06/17/648dba7524d5e.jpg) ![扫描件_自反关系_3](https://media.opennet.top/i/2023/06/17/648dba7f03ae8.jpg) ![扫描件_当关系是传递关系时有下面定理存在_1](https://media.opennet.top/i/2023/06/17/648dbb676b31c.jpg) ![image-20230617215216762](https://media.opennet.top/i/2023/06/17/648dba9187c2c.png) #### 题：自反 对称 传递 ![image-20230618122907607](https://media.opennet.top/i/2023/06/18/648e8819c0b48.png) #### 题：自反 对称 传递 ![image-20230618173618033](https://media.opennet.top/i/2023/06/18/648ed0128be9a.png) ![扫描件_(2)7_1](https://media.opennet.top/i/2023/06/18/648ed04a6f87b.jpg) #### 关系闭包 ![扫描件_有序对来扩展R使扩展的R具有对称性扩展后_1](https://media.opennet.top/i/2023/06/17/648dbcb9c106b.jpg) ![扫描件_有序对来扩展R使扩展的R具有对称性扩展后_2](https://media.opennet.top/i/2023/06/17/648dbcc82a681.jpg) ![扫描件_有序对来扩展R使扩展的R具有对称性扩展后_3](https://media.opennet.top/i/2023/06/17/648dbccfb3027.jpg) #### 等价关系 ![扫描件_定义4-20设R是非空集合A上的二元关系_1](https://media.opennet.top/i/2023/06/17/648dbe08e2af1.jpg) #### 等价类 ![扫描件_定义4-21设R是非空集合A上的等价关系_1](https://media.opennet.top/i/2023/06/17/648dbede7e092.jpg) ![扫描件_定义4-21设R是非空集合A上的等价关系_2](https://media.opennet.top/i/2023/06/17/648dbee69913f.jpg) #### 商集 划分 等价类是集合，商集就是所有等价类构成的集合 ![扫描件_定义4-22设R是非空集合A上的等价关系_1](https://media.opennet.top/i/2023/06/17/648dc2a86d161.jpg) ![扫描件_定义4-22设R是非空集合A上的等价关系_2](https://media.opennet.top/i/2023/06/17/648dc2b16a4b8.jpg) #### 题：商集 ![IMG_1075](https://media.opennet.top/i/2023/06/18/648ebb2779559.png) #### 题：商集 ![image-20230618173018545](https://media.opennet.top/i/2023/06/18/648eceab15352.png) ![image-20230618173035122](https://media.opennet.top/i/2023/06/18/648ecebb6b099.png) #### 偏序关系 ![扫描件_集合上的另一种重要关系是偏序关系它是集合_1](https://media.opennet.top/i/2023/06/17/648dc3efde083.jpg) #### 哈斯图 ![扫描件_定义4-25设S R为偏序集对于任意元素_1](https://media.opennet.top/i/2023/06/17/648dc4889ec10.jpg) ![扫描件_定义4-25设S R为偏序集对于任意元素_2](https://media.opennet.top/i/2023/06/17/648dc494b62bc.jpg) ![扫描件_定义4-25设S R为偏序集对于任意元素_3](https://media.opennet.top/i/2023/06/17/648dc49d0ff65.jpg) #### 题：哈斯图 ![image-20230618154407815](https://media.opennet.top/i/2023/06/18/648eb5c86e6ca.png) #### 题：哈斯图 ![image-20230618173231785](https://media.opennet.top/i/2023/06/18/648ecf300d22f.png) ![扫描件_T 3(1)_1](https://media.opennet.top/i/2023/06/18/648ecf88b1467.jpg) #### 最小元 极小元 下界 下确界 ![扫描件_定义4-26设S为偏序集若任意的a bS_1](https://media.opennet.top/i/2023/06/17/648dc7be0f137.jpg) ![扫描件_定义4-26设S为偏序集若任意的a bS_2](https://media.opennet.top/i/2023/06/17/648dc7ced1907.jpg) ### 4.2 函数 ![扫描件_任意x唯一y_1](https://media.opennet.top/i/2023/06/17/648dcb1b03b9c.jpg) ![扫描件_任意x唯一y_2](https://media.opennet.top/i/2023/06/17/648dcb25450d6.jpg) ![扫描件_任意x唯一y_3](https://media.opennet.top/i/2023/06/17/648dcb31f1dce.jpg) #### 单射 满射 双射 ![扫描件_定义4-32设f是从集合A到集合B的函数_1](https://media.opennet.top/i/2023/06/17/648dcbca912b5.jpg) ![扫描件_定义4-34设f是从集合A到集合B的函数_1](https://media.opennet.top/i/2023/06/17/648dcc381df46.jpg) #### 题：双射函数 ![image-20230618154300594](https://media.opennet.top/i/2023/06/18/648eb58570b1c.png) #### 逆函数 ![扫描件_函数运算_1](https://media.opennet.top/i/2023/06/17/648dccb506277.jpg) #### 题：逆函数 ![IMG_1073](https://media.opennet.top/i/2023/06/17/648dd86cce2ae.png) #### 复合函数 ![扫描件_定义4-36设f是从集合B到集合C的函数_1](https://media.opennet.top/i/2023/06/17/648dcd4893f34.jpg) ## 第 5 章 图的概念 矩阵表示 ### 5.1 图的基本概念 #### 顶点 阶 边 环 零图 平凡图 ![扫描件_定义5-1图(Graph)是由顶点集合和_1](https://media.opennet.top/i/2023/06/18/648e89c5dd057.jpg) #### 多重图 线图 简单图 ![扫描件_定义5-1图(Graph)是由顶点集合和_2](https://media.opennet.top/i/2023/06/18/648e89ceb4fc9.jpg) ### 5.2 度 度序列 #### 度 度序列 正则图 ![扫描件_最大度8(G)_1](https://media.opennet.top/i/2023/06/18/648e8ae1eb655.jpg) ### 5.3 握手定理 #### 握手定理及其推论 ![扫描件_度=25边_1](https://media.opennet.top/i/2023/06/18/648e8b753a6bf.jpg) ### 5.4 完全图 #### 完全图 补图 ![扫描件_完全图_1](https://media.opennet.top/i/2023/06/18/648e9473885d0.jpg) ### 5.5 图的同构与子图 #### 同构 ![扫描件_5C一个图的图形表示不一定是唯一的一些看_1](https://media.opennet.top/i/2023/06/18/648e95e441ff6.jpg) #### 子图 真子图 生成子图 ![扫描件_5C一个图的图形表示不一定是唯一的一些看_2](https://media.opennet.top/i/2023/06/18/648e95ee7334a.jpg) ### 5.7 通路 回路 #### 通路 回路 简单通路：没有重复点 迹：没有重复边 ![扫描件_在图的研究中常常考虑从一个顶点出发沿着一_1](https://media.opennet.top/i/2023/06/18/648e97c20affb.jpg) #### 通路 回路 计算 ![image-20230618135126272](https://media.opennet.top/i/2023/06/18/648e9b5f32cd0.png) ![image-20230618135138026](https://media.opennet.top/i/2023/06/18/648e9b6aaf59b.png) ### 5.8 连通性 #### 连通分支 割点 割边 ![扫描件_设uv为无向图G=V E中的两个顶点若u_1](https://media.opennet.top/i/2023/06/18/648e993cb8d54.jpg) ![扫描件_设uv为无向图G=V E中的两个顶点若u_2](https://media.opennet.top/i/2023/06/18/648e995aac774.jpg) #### 连通度 ![扫描件_定义5-14设无向图连通图G=V E称x_1](https://media.opennet.top/i/2023/06/18/648e9a6a3f675.jpg) #### 弱连通 单连通 强连通 ![扫描件_定义5-14设无向图连通图G=V E称x_2](https://media.opennet.top/i/2023/06/18/648e9a7369ad4.jpg) ### 5.9 矩阵表示 #### 邻接矩阵 ![扫描件_设有向图G=V E顶点集_1](https://media.opennet.top/i/2023/06/18/648e9bfbbb230.jpg) ![扫描件_设有向图G=V E顶点集_2](https://media.opennet.top/i/2023/06/18/648e9c03e4cca.jpg) #### 可达矩阵 ![扫描件_给定图G=V E顶点集1_1](https://media.opennet.top/i/2023/06/18/648e9cb01e232.jpg) ![扫描件_给定图G=V E顶点集1_2](https://media.opennet.top/i/2023/06/18/648e9cb86326b.jpg) #### 关联矩阵 ![扫描件_设G=V_E是一个无环的至少有一条有向边_1](https://media.opennet.top/i/2023/06/18/648e9d8f10d8a.jpg) #### 连通性与矩阵 ![扫描件_设G=V_E是一个无环的至少有一条有向边_2](https://media.opennet.top/i/2023/06/18/648e9da3df490.jpg) ## 第 6 章 特殊的图 ### 6.1 欧拉图 #### 欧拉图 定义 判定 ![扫描件_基本概念_1](https://media.opennet.top/i/2023/06/18/648ea461abe31.jpg) ![扫描件_基本概念_2](https://media.opennet.top/i/2023/06/18/648ea4693b1bc.jpg) #### 欧拉图 判定方法 ![扫描件_基本概念_3](https://media.opennet.top/i/2023/06/18/648ea46fee0d4.jpg) ![扫描件_基本概念_4](https://media.opennet.top/i/2023/06/18/648ea47767b03.jpg) #### 题：欧拉图 ![image-20230618154554715](https://media.opennet.top/i/2023/06/18/648eb63485adf.png) ### 6.2 哈密顿图 #### 哈密顿图 定义 判定 ![扫描件_定义6_3设G是一个连通图若G中存在一条_1](https://media.opennet.top/i/2023/06/18/648ea5cf050cd.jpg) ![扫描件_定义6_3设G是一个连通图若G中存在一条_2](https://media.opennet.top/i/2023/06/18/648ea5d81bdb9.jpg) ![扫描件_定义6_3设G是一个连通图若G中存在一条_3](https://media.opennet.top/i/2023/06/18/648ea5e4e69d3.jpg) ![扫描件_定义6_3设G是一个连通图若G中存在一条_4](https://media.opennet.top/i/2023/06/18/648ea5ec56c12.jpg) #### 题：哈密顿图 ![image-20230618150647518](https://media.opennet.top/i/2023/06/18/648ead084d3bd.png) ### 6.3 二部图 #### 二部图 定义 判定 二部图 = 偶图 = 二分图 ![扫描件_定义6-4给定简单无向图G=V E且V=_1](https://media.opennet.top/i/2023/06/18/648ea764c2008.jpg) #### 匹配 ![扫描件_定义6-4给定简单无向图G=V E且V=_2](https://media.opennet.top/i/2023/06/18/648ea76e6923e.jpg) #### 霍尔定理 ![扫描件_定义6-4给定简单无向图G=V E且V=_3](https://media.opennet.top/i/2023/06/18/648ea77612d3d.jpg) ### 6.4 平面图 #### 平面图 定义 性质 ![扫描件_定义6_7如果能把一个无向图G的所有顶点_1](https://media.opennet.top/i/2023/06/18/648ea8772d746.jpg) ![扫描件_定义6_7如果能把一个无向图G的所有顶点_2](https://media.opennet.top/i/2023/06/18/648ea87e40281.jpg) #### 欧拉公式 ![扫描件_定义6_7如果能把一个无向图G的所有顶点_3](https://media.opennet.top/i/2023/06/18/648ea88d4d18c.jpg) ### 6.5 图的着色 #### 对偶图 ![扫描件_定义6_11将平面图G嵌入平面后通过以下_1](https://media.opennet.top/i/2023/06/18/648eaa0a9f7c8.jpg) #### 面着色 ![扫描件_定义6_11将平面图G嵌入平面后通过以下_2](https://media.opennet.top/i/2023/06/18/648eaa154b328.jpg) #### 点着色 ![扫描件_定义6_11将平面图G嵌入平面后通过以下_3](https://media.opennet.top/i/2023/06/18/648eaa1dc153a.jpg) ![扫描件_定义6_11将平面图G嵌入平面后通过以下_4](https://media.opennet.top/i/2023/06/18/648eaa24bcd24.jpg)