离散数学期末复习总结

### 离散数学期末复习知识点总结 #### 第一章：基本逻辑概念及转换 **1.1 命题符号化** - **定义**：将自然语言中的语句用形式逻辑的语言表示出来。 - **例子**： - 只要不下雨，我就骑自行车上班：\( \neg p \rightarrow q \) - 只有不下雨，我才骑自行车上班：\( q \rightarrow \neg p \) - 除非下雨，否则我就骑自行车上班：\( \neg p \rightarrow q \) - 如果下雨，我就不骑自行车上班：\( p \rightarrow \neg q \) **1.2 命题定义** - **定义**：一个命题是指判断结果唯一的陈述句。 - **非命题**：感叹句、祈使句、疑问句以及那些结果不确定的陈述句。 **1.3 逻辑运算符** - **必要条件与充分条件**： - \( p \)为\( q \)的必要条件：\( q \rightarrow p \) - \( p \)为\( q \)的充分条件：\( p \rightarrow q \) - **逻辑等价**： - \( p \leftrightarrow q \)表示\( p \)与\( q \)同真或同假。 **1.4 逻辑等式** - **双重否定律**：\(\neg\neg A \equiv A\) - **等幂律**：\(A \land A \equiv A, A \lor A \equiv A\) - **交换律**：\(A \land B \equiv B \land A, A \lor B \equiv B \lor A\) - **结合律**：\((A \land B) \land C \equiv A \land (B \land C), (A \lor B) \lor C \equiv A \lor (B \lor C)\) - **分配律**：\(A \land (B \lor C) \equiv (A \land B) \lor (A \land C), A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\) - **德·摩根律**：\(\neg (A \land B) \equiv \neg A \lor \neg B, \neg (A \lor B) \equiv \neg A \land \neg B\) - **吸收律**：\(A \land (A \lor B) \equiv A, A \lor (A \land B) \equiv A\) - **零律与同一律**：\(A \land 0 \equiv 0, A \lor 1 \equiv 1, A \lor 0 \equiv A, A \land 1 \equiv A\) - **排中律与矛盾律**：\(A \lor \neg A \equiv 1, A \land \neg A \equiv 0\) - **蕴涵与等价等值式**：\(A \rightarrow B \equiv \neg A \lor B, A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)\) - **假言易位**：\(A \rightarrow B \equiv \neg B \rightarrow \neg A\) - **等价否定等值式**：\(A \leftrightarrow B \equiv \neg A \leftrightarrow \neg B\) - **归谬论**：\((A \rightarrow B) \land (\neg B \rightarrow \neg A) \rightarrow A\) **1.5 对偶原理** - 若\( A(B) \)，则\( A^*(B^*) \)，其中\( A^* \)和\( B^* \)分别是对\( A \)和\( B \)进行替换的结果。 **1.6 公式的范式** - **步骤**： 1. 消去公式中的\( \neg\neg \)操作。 2. 将否定符号移动到最内层。 3. 使用分配律展开。 - **主析取范式与主合取范式**： - **重言式**：含有所有可能的极小项。 - **矛盾式**：不含任何极小项。 - **可满足式**：至少含有一个极小项但不包含所有极小项。 #### 第二章至第三章（略） #### 第七章：图论基础 **7.1 握手定理** - 任意无向图中所有顶点度数之和等于边数的两倍。 - 有向图中所有顶点入度之和等于出度之和。 **7.2 图的类型** - **环**：长度为1的圈。 - **平行边**：构成长度为2的圈。 **7.3 连通性** - **点割集**与**边割集**：移除这些集合中的元素后图不再连通。 - **强连通**、**单向连通**、**弱连通**：指有向图的不同连通程度。 **7.4 定理** - 强连通判别法：图强连通当且仅当图中存在经过每个顶点至少一次的回路。 以上总结了离散数学中的一些关键知识点，包括基本逻辑概念、命题符号化、逻辑等式、对偶原理、范式、图论等。这些内容对于理解离散数学的基础概念及其应用至关重要。