# 离散数学2.1-等值式

等值式：若A`⇔`B为永真式，则称A、B是等值的记作A⇔B

## **一、等值式**

### **基础定律**

| **名称** | **公式** | **直觉锚点** |
| --- | --- | --- |
| **双重否定律** | `¬¬p ⇔ p` | 否定两次回到原样 |
| **幂等律** | `p ∨ p ⇔ p` |  |
|  | `p ∧ p ⇔ p` | 自己或自己、自己且自己，还是自己 |
| **交换律** | `p ∨ q ⇔ q ∨ p` |  |
|  | `p ∧ q ⇔ q ∧ p` | 顺序不影响结果 |
| **结合律** | `(p∨q)∨r ⇔ p∨(q∨r)` |  |
|  | `(p∧q)∧r ⇔ p∧(q∧r)` | 连续或、连续且，括号随便放 |
| **分配律** | `p∨(q∧r) ⇔ (p∨q)∧(p∨r)` |  |
|  | `p∧(q∨r) ⇔ (p∧q)∨(p∧r)` | 或对且分配、且对或分配，注意两条都成立 |

### **德摩根律**

tips：其实就是括号外面有`¬`，直接分配律一套然后`∧`和`∨`符号互换

<table style="min-width: 50px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p><code>¬(p ∧ q) ⇔ ¬p ∨ ¬q</code></p></td><td colspan="1" rowspan="1"><p>非号往里进，且变或</p></td></tr><tr><td colspan="1" rowspan="1"><p><code>¬(p ∨ q) ⇔ ¬p ∧ ¬q</code></p></td><td colspan="1" rowspan="1"><p>非号往里进，或变且</p></td></tr></tbody></table>

### 吸收律

tips：其实就是括号外面符号和括号内不一致，直接化简为括号外的符号

<table style="min-width: 50px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p><code>p ∨ (p ∧ q) ⇔ p</code></p></td><td colspan="1" rowspan="1"><p>p 已经把 p∧q 包含在内，或上去直接吸收</p></td></tr><tr><td colspan="1" rowspan="1"><p><code>p ∧ (p ∨ q) ⇔ p</code></p></td><td colspan="1" rowspan="1"><p>p 且上任何含 p 的或，还是 p 本身</p></td></tr></tbody></table>

### 拓展部分

核心思想把`∧`和`∨`可看成集合里的交集和并集，1看成全集（什么都包含），0则是空集，什么都没有

<table style="min-width: 75px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p><strong>同一律</strong></p></td><td colspan="1" rowspan="1"><p><code>p ∨ 0 ⇔ p</code><br><code>p ∧ 1 ⇔ p</code></p></td><td colspan="1" rowspan="1"><p>p<code>∨</code>空集<code>⇔</code>p（本身）<code>p ∧ 全集 ⇔ p</code></p></td></tr><tr><td colspan="1" rowspan="1"><p><strong>零律</strong></p></td><td colspan="1" rowspan="1"><p><code>p ∨ 1 ⇔ 1</code><br><code>p ∧ 0 ⇔ 0</code></p></td><td colspan="1" rowspan="1"><p>同上</p></td></tr><tr><td colspan="1" rowspan="1"><p><strong>排中律</strong></p></td><td colspan="1" rowspan="1"><p><code>p ∨ ¬p ⇔ 1</code></p></td><td colspan="1" rowspan="1"><p><code>¬p</code>就是取p没取到的，<code>∨</code>p那就是全集<code>1</code></p></td></tr><tr><td colspan="1" rowspan="1"><p><strong>矛盾律</strong></p></td><td colspan="1" rowspan="1"><p><code>p ∧ ¬p ⇔ 0</code></p></td><td colspan="1" rowspan="1"><p>同上，两者取交集肯定是没有交集，空集<code>0</code></p></td></tr><tr><td colspan="1" rowspan="1"><p><strong>补元唯一性</strong></p></td><td colspan="1" rowspan="1"><p>若&nbsp;<code>p ∨ q ⇔ 1</code>&nbsp;且&nbsp;<code>p ∧ q ⇔ 0</code>，则&nbsp;<code>q ⇔ ¬p</code></p></td><td colspan="1" rowspan="1"><p>这就是补元的定义（布尔代数里常用）</p></td></tr></tbody></table>

### 蕴含与等价的核心等值式（根公式）

**一. 蕴含等值律：**`p → q ⇔ ¬p ∨ q`

1.  先问：`p → q` 什么时候为**假**？  
    只有一种情况：**p 真且 q 假**。  
    用符号写，就是 `p ∧ ¬q`。  
    这是蕴含的**唯一反例**。
    
2.  既然反例是 `p ∧ ¬q`，那么“不是反例”就是 `p → q` 为**真**的情况。  
    因此：  
    `p → q` ⇔ `¬(p ∧ ¬q)`
    
3.  对右边用德摩根律：  
    `¬(p ∧ ¬q)` ⇔ `¬p ∨ ¬(¬q)`  
    ⇔ `¬p ∨ q` （双重否定）
    
4.  所以：  
    `p → q ⇔ ¬p ∨ q`
    

**一句口诀**：蕴含就是把它的唯一反例否定掉，再用德摩根展开。

**二. 等价等值律法：**`p ↔ q ⇔ (p → q) ∧ (q → p)`

**定义本身就是推导，前后能互相推导**

“p 与 q 等价”就是说：p 和 q 一模一样真。  
那就必须满足两个条件：

*   p 真的时候，q 必须真 → `p → q`
    
*   q 真的时候，p 必须真 → `q → p`
    

两者同时成立，才是等价。  
所以：  
`p ↔ q ⇔ (p → q) ∧ (q → p)`

如果你愿意，可以进一步把两个蕴含都换成 `¬p ∨ q` 的形式，得到合取范式。

**三. 假言易位律：**`p → q ⇔ ¬q → ¬p`

**四.归谬论**：`(p → q) ∧ (p → ¬q) ⇔ ¬p`

## 速查表

`双重否定律` `¬¬p ⇔ p`

`幂等律` `p ∨ p ⇔ p`  
`幂等律` `p ∧ p ⇔ p`

`交换律` `p ∨ q ⇔ q ∨ p`  
`交换律` `p ∧ q ⇔ q ∧ p`

`结合律` `(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)`  
`结合律` `(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)`

`分配律` `p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)`  
`分配律` `p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)`

`德摩根律` `¬(p ∧ q) ⇔ ¬p ∨ ¬q`  
`德摩根律` `¬(p ∨ q) ⇔ ¬p ∧ ¬q`

`吸收律` `p ∨ (p ∧ q) ⇔ p`  
`吸收律` `p ∧ (p ∨ q) ⇔ p`

`同一律` `p ∨ 0 ⇔ p`  
`同一律` `p ∧ 1 ⇔ p`

`零律` `p ∨ 1 ⇔ 1`  
`零律` `p ∧ 0 ⇔ 0`

`排中律` `p ∨ ¬p ⇔ 1`

`矛盾律` `p ∧ ¬p ⇔ 0`

`蕴含等值式` `p → q ⇔ ¬p ∨ q`

`等价等值式` `p ↔ q ⇔ (p → q) ∧ (q → p)`

`等价析取形式` `p ↔ q ⇔ (p ∧ q) ∨ (¬p ∧ ¬q)`

`假言易位` `p → q ⇔ ¬q → ¬p`

`等价否定` `p ↔ q ⇔ ¬p ↔ ¬q`

`归谬论` `(p → q) ∧ (p → ¬q) ⇔ ¬p`

`归谬论` `(¬p → q) ∧ (¬p → ¬q) ⇔ p`

`输出律` `(p ∧ q) → r ⇔ p → (q → r)`