离散数学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：其实就是括号外面有¬，直接分配律一套然后∧和∨符号互换

¬(p ∧ q) ⇔ ¬p ∨ ¬q	非号往里进，且变或
¬(p ∨ q) ⇔ ¬p ∧ ¬q	非号往里进，或变且

吸收律

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

p ∨ (p ∧ q) ⇔ p	p 已经把 p∧q 包含在内，或上去直接吸收
p ∧ (p ∨ q) ⇔ p	p 且上任何含 p 的或，还是 p 本身

拓展部分

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

同一律	p ∨ 0 ⇔ p p ∧ 1 ⇔ p	p∨空集⇔p（本身）p ∧ 全集 ⇔ p
零律	p ∨ 1 ⇔ 1 p ∧ 0 ⇔ 0	同上
排中律	p ∨ ¬p ⇔ 1	¬p就是取p没取到的，∨p那就是全集1
矛盾律	p ∧ ¬p ⇔ 0	同上，两者取交集肯定是没有交集，空集0
补元唯一性	若 p ∨ q ⇔ 1 且 p ∧ q ⇔ 0，则 q ⇔ ¬p	这就是补元的定义（布尔代数里常用）

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

一. 蕴含等值律：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)