离散数学

基本概念

数理逻辑

1. 命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔）

   • 析取∨ 类同于 或
   • 合取∧ 类同于 且
   • 蕴涵→ 如果就
   • 等价 充分必要条件

2. 命题(非真既假的陈述句)

3. 复合命题(由简单命题通过联结词联结而成的命题)

4. 计算规律

   双重否定律: A ⇔ ¬¬A
   幂等律: A ∨ A ⇔ A, A ∧ A ⇔ A
   交换律: A ∧ B ⇔ B ∧ A, A ∨ B ⇔ B ∨ A
   结合律: (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C), (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C)
   分配律: A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C), A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
   德摩根律: ¬(A ∨ B) ⇔ ¬A ∧ ¬B, ¬(A ∧ B) ⇔ ¬A ∨ ¬B
   吸收律: A ∨ (A ∧ B) ⇔ A, A ∧ (A ∨ B) ⇔ A
   零律: A ∨ 1 ⇔ 1, A ∧ 0 ⇔ 0,
   同一律: A ∧ 1 ⇔ A, A ∨ 0 ⇔ A
   排中律: A ∨ ¬A ⇔ 1
   矛盾律: A ∧ ¬A ⇔ 0
   蕴涵等值式: A → B ⇔ ¬A ∨ B
   等价等值式: A ↔ B ⇔ (A → B) ∧ (B → A)
   假言易位: A → B ⇔ ¬B → ¬A
   等价否定等值式: A ↔ B ⇔ ¬A ↔ ¬B
   归谬论: (A → B) ∧ (A → ¬B) ⇔ ¬A
   

5. 范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式

6. 公式类型的判别方法：真值表法、等值演算法、主析取/合取范式法

7. 命题逻辑的推理理论

   有一些重要的重言蕴涵式，称作推理定律。下面给出9条推理定律，它们是：

   1. $A \Rightarrow (A \lor B)$
      附加律

   2. $(A \land B) \Rightarrow A$
      化简律

   3. $(A \rightarrow B) \land A \Rightarrow B$
      假言推理

   4. $(A \rightarrow B) \land \neg B \Rightarrow \neg A$
      拒取式

   5. $(A \lor B) \land \neg B \Rightarrow A$
      析取三段论

   6. $(A \rightarrow B) \land (B \rightarrow C) \Rightarrow (A \rightarrow C)$
      假言三段论

   7. $(A \leftrightarrow B) \land (B \leftrightarrow C) \Rightarrow (A \leftrightarrow C)$
      等价三段论

   8. $(A \rightarrow B) \land (C \rightarrow D) \land (A \lor C) \Rightarrow (B \lor D)$
      构造性二难

      $(A \rightarrow B) \land (\neg A \rightarrow B) \Rightarrow B$
      构造性二难（特殊形式）

   9. $(A \rightarrow B) \land (C \rightarrow D) \land (\neg B \lor \neg D) \Rightarrow (\neg A \lor \neg C)$
      破坏性二难

   其中 $A, B, C, D$ 等是元语言符号，表示任意的命题公式。

集合

1. 集合、元素、集合的表示方法（列元素法、谓词表示法）、子集、空集、全集、集合的包含、相等、幂集

   • 定义 幂集

     设 $A$ 为集合，把 $A$ 的全体子集构成的集合叫做 $A$ 的幂集，记作 $P(A)$（或 $2^A$），符号化表示为

     $$P(A) = \{ x \mid x \subseteq A \}。$$

     若 $A$ 是 $n$ 元集，则 $P(A)$ 有 $2^n$ 个元素。

     例如：$A = \{ a, b, c \}$，$A$ 的幂集：

     $$P(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}。$$

2. 集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）

3. 集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用

• 集合恒等式

  名称	等式
  恒等律	$A \cup \emptyset = A, \, A \cap E = A$​
  支配律	$A \cup E = E, \, A \cap \emptyset = \emptyset$​
  幂等律	$A \cup A = A, \, A \cap A = A$​
  双重否定律	$\sim(\sim A) = A$​
  交换律	$A \cup B = B \cup A, \, A \cap B = B \cap A$​
  结合律	$A \cup (B \cup C) = (A \cup B) \cup C, \, A \cap (B \cap C) = (A \cap B) \cap C$​
  分配率	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C), \, A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$​
  德摩根律	$\sim(A \cup B) = \sim B \cap \sim A, \, \sim(A \cap B) = \sim A \cup \sim B$​
  吸收律	$A \cup (A \cap B) = A, \, A \cap (A \cup B) = A$​
  补律	$A \cap \sim A = \emptyset, \, A \cup \sim A = E$​

• 集合运算定律

  • 幂等律：

    • $A \cup A = A$
    • $A \cap A = A$

  
  

  • 结合律：

    • $(A \cup B) \cup C = A \cup (B \cup C)$

  
  

  • 交换律：

    • $A \cup B = B \cup A$
    • $A \cap B = B \cap A$

  
  

  • 分配律：

    • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
    • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

  
  

  • 同一律：

    • $A \cup \emptyset = A$
    • $A \cap U = A$

  
  

  • 零律：

    • $A \cup U = U$
    • $A \cap \emptyset = \emptyset$

  
  

  • 排中律：

    • $A \cup \sim A = U$

  
  

  • 矛盾律：

    • $A \cap \sim A = \emptyset$

  
  

  • 吸收律：

    • $A \cup (A \cap B) = A$
    • $A \cap (A \cup B) = A$

  
  

  • 德摩根律：

    • $A - (B \cup C) = (A - B) \cap (A - C)$
    • $A - (B \cap C) = (A - B) \cup (A - C)$
    • $\sim (B \cup C) = \sim B \cap \sim C$
    • $\sim (B \cap C) = \sim B \cup \sim C$
    • $\sim \emptyset = U$
    • $\sim U = \emptyset$

  
  

  • 双重否定律：

    • $\sim (\sim A) = A$

  
  
  
  

‍

二元关系

1. 了解序偶与笛卡尔积的概念，掌握笛卡尔积的运算。

2. 理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

   • 定义 7.3 二元关系

     一个集合被称为二元关系（记作 RR），如果它满足以下条件之一：

     1. 集合非空，且它的元素都是有序对；
     2. 集合是空集。

     对于二元关系 RR，如果 ⟨x,y⟩∈R⟨x,y⟩∈R，则记作 xRyxRy；如果 ⟨x,y⟩∉R⟨x,y⟩∈/R，则记作 xR̸yxRy。

     示例：

     • R1={⟨1,2⟩,⟨a,b⟩}R1={⟨1,2⟩,⟨a,b⟩} 是二元关系。
     • R2={⟨1,2⟩,a,b}R2={⟨1,2⟩,a,b} 不是二元关系，除非将 aa 和 bb 定义为有序对。

   
   

   • 定义 7.4 从 AA 到 BB 的二元关系

     设 AA 和 BB 为集合，A×BA×B 的任何子集所定义的二元关系称为从 AA 到 BB 的二元关系。特别地，当 A=BA=B 时，称为 AA 上的二元关系。

     示例：

     • A={0,1}A={0,1}，B={1,2,3}B={1,2,3}。

     • R1={⟨0,2⟩}R1={⟨0,2⟩}，R2=A×BR2=A×B，R3=∅R3=∅，R4={⟨0,1⟩}R4={⟨0,1⟩} 都是从 AA 到 BB 的二元关系。

     • R3R3 和 R4R4 同时也是 AA 上的二元关系。

     • 对于任何集合 AA，空集 ∅∅ 是 A×AA×A 的子集，称为 AA 上的空关系。此外，定义 AA 上的以下两种关系：

       1. 全域关系 EAEA：包含 A×AA×A 中的所有有序对，即 EA=A×AEA=A×A。
       2. 恒等关系 IAIA：包含所有形如 ⟨a,a⟩⟨a,a⟩ 的有序对，其中 a∈Aa∈A，即 IA={⟨a,a⟩∣a∈A}IA={⟨a,a⟩∣a∈A}。

       这些关系在集合论和离散数学中具有重要的应用，用于描述集合元素之间的特定联系。

   
   
   
   
   
   



3. 掌握求复合关系与逆关系的方法。




4. 理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图）。

   • 自反性：全部顶点均有环；反自反性：全部顶点均无环；对称性：有边均双边（无单边，顶点有无环不影响） ；反对称性：有边均单边（顶点有无环不影响）（无平行边）

     传递性：a到b有边，b到c有边，则a到c也有边，否则不然。




5. 掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。

   • 换言之：r=加自环 s=单边变双边 t:努力变传递




6. 理解等价关系和划分、掌握等价类和划分的求法




7. 理解偏序关系的概念，掌握画哈斯图的方法，极大/小元、最大/小元的求法。

   • 哈斯图的方法

     如图7.7：5,9,6,8,7均是极大元，1是极小元，无最大元，最小元为1；右边： {a，b，c}是极大元，∅是极小元，最大元是 {a，b，c}，最小元为∅

‍

函数

图论