离散数学核心公式终极汇总（命题逻辑+谓词逻辑+推理规则）
一、命题逻辑核心公式
（一）命题联结词与真值关系
| 联结词 | 符号 | 定义公式 | 真值条件 | 等价转换公式 |
|---|---|---|---|---|
| 否定 | ┐ | ┐P | 与P真值相反 | - |
| 合取 | ∧ | P∧Q | 仅P、Q同真为真 | - |
| 析取 | ∨ | P∨Q | 仅P、Q同假为假 | - |
| 蕴涵 | → | P→Q | 仅P真Q假为假 | P→Q ≡ ┐P∨Q |
| 等价 | ↔ | P↔Q | P、Q同真同假为真 | P↔Q ≡ (P→Q)∧(Q→P) ≡ (P∧Q)∨(┐P∧┐Q) |
| 异或 | ⊕ | P⊕Q | P、Q真值不同为真 | P⊕Q ≡ ┐(P↔Q) |
| 与非 | ↑ | P↑Q | 等价于┐(P∧Q) | P↑Q ≡ ┐(P∧Q) |
| 或非 | ↓ | P↓Q | 等价于┐(P∨Q) | P↓Q ≡ ┐(P∨Q) |
（二）24组基本等价公式
1. 基础定律
- E1：┐(┐P) ≡ P（双重否定律）
- E2：P∨P ≡ P（幂等律）
- E3：P∧P ≡ P（幂等律）
- E4：P∨Q ≡ Q∨P（交换律）
- E5：P∧Q ≡ Q∧P（交换律）
- E6：(P∨Q)∨R ≡ P∨(Q∨R)（结合律）
- E7：(P∧Q)∧R ≡ P∧(Q∧R)（结合律）
2. 分配与吸收定律
- E8：P∨(Q∧R) ≡ (P∨Q)∧(P∨R)（分配律）
- E9：P∧(Q∨R) ≡ (P∧Q)∨(P∧R)（分配律）
- E10：P∨(P∧Q) ≡ P（吸收律）
- E11：P∧(P∨Q) ≡ P（吸收律）
3. 同一、零律与否定律
- E12：P∨F ≡ P（同一律）
- E13：P∧T ≡ P（同一律）
- E14：P∨T ≡ T（零律）
- E15：P∧F ≡ F（零律）
- E16：P∨┐P ≡ T（排中律）
- E17：P∧┐P ≡ F（矛盾律）
4. 德摩根与推理相关等价
- E18：┐(P∨Q) ≡ ┐P∧┐Q（德摩根律）
- E19：┐(P∧Q) ≡ ┐P∨┐Q（德摩根律）
- E20：P→Q ≡ ┐Q→┐P（假言易位）
- E21：P→(Q→R) ≡ (P∧Q)→R（蕴涵结合）
- E22：┐(P→Q) ≡ P∧┐Q（否定蕴涵）
- E23：P↔Q ≡ ┐P↔┐Q（等价否定）
- E24：(P→Q)∧(P→┐Q) ≡ ┐P（归谬论）
二、谓词逻辑核心公式
（一）基本概念与符号定义
- 个体词：常量（a,b,c…）、变量（x,y,z…）
- 谓词：n元谓词P(x₁,x₂,…,xₙ)（刻画个体性质/关系）
- 量词：全称量词∀x（所有x）、存在量词∃x（存在x）
- 特性谓词：刻画个体域范围，全称量词后作蕴涵前件（∀x(U(x)→P(x))），存在量词后作合取项（∃x(U(x)∧P(x))）
（二）谓词等价公式（12组核心）
1. 量词否定与改名
- E25：┐(∀x)G(x) ≡ (∃x)┐G(x)（全称否定→存在否定）
- E26：┐(∃x)G(x) ≡ (∀x)┐G(x)（存在否定→全称否定）
- E27：(∀x)G(x) ≡ (∀y)G(y)（全称改名）
- E28：(∃x)G(x) ≡ (∃y)G(y)（存在改名）
2. 量词辖域扩张与收缩
- E29：(∀x)(G(x)∨S) ≡ (∀x)G(x)∨S（S不含x）
- E30：(∀x)(G(x)∧S) ≡ (∀x)G(x)∧S（S不含x）
- E31：(∃x)(G(x)∨S) ≡ (∃x)G(x)∨S（S不含x）
- E32：(∃x)(G(x)∧S) ≡ (∃x)G(x)∧S（S不含x）
3. 量词分配
- E33：(∀x)(G(x)∧H(x)) ≡ (∀x)G(x)∧(∀x)H(x)（∀对∧分配）
- E34：(∃x)(G(x)∨H(x)) ≡ (∃x)G(x)∨(∃x)H(x)（∃对∨分配）
- E35：(∀x)G(x)∨(∀x)H(x) ≡ (∀x)(∀y)(G(x)∨H(y))（x≠y）
- E36：(∃x)G(x)∧(∃x)H(x) ≡ (∃x)(∃y)(G(x)∧H(y))（x≠y）
（三）谓词范式公式
- 前束范式：(Q₁x₁)(Q₂x₂)...(Qₙxₙ)M(x₁...xₙ)（M为无量词母式）
- Skolem转换：∃x在∀x₁…∀xₖ后→G(f(x₁…xₖ),x₁…xₖ)；∃x在最前→G(c)（c为常量）
三、推理规则核心公式
（一）命题逻辑推理规则
1. 基础规则
- P规则：推导中可随时引入前提
- T规则：可引入前序公式的逻辑结果（基于等价式/蕴涵式）
- CP规则：Γ⇒P→Q ⇔ Γ∪{P}⇒Q（附加前提）
- 反证法：Γ⇒H ⇔ Γ∪{┐H}⇒R∧┐R（R为任意公式）
2. 16组推理定律
- I1：G∧H⇒G（简化）
- I2：G∧H⇒H（简化）
- I3：G⇒G∨H（添加）
- I4：H⇒G∨H（添加）
- I5：┐G⇒G→H（蕴涵引入）
- I6：H⇒G→H（蕴涵引入）
- I7：┐(G→H)⇒G（否定蕴涵前件）
- I8：┐(G→H)⇒┐H（否定蕴涵后件）
- I9：G,H⇒G∧H（合取引入）
- I10：┐G,G∨H⇒H（选言三段论）
- I11：G,G→H⇒H（分离规则/MP）
- I12：┐H,G→H⇒┐G（否定后件/MT）
- I13：G→H,H→I⇒G→I（假言三段论/HS）
- I14：G∨H,G→I,H→I⇒I（二难推论）
- I15：G→H,G→┐H⇒┐G（归谬论）
- I16：G↔H⇒G→H；G↔H⇒H→G（等价分解）
（二）谓词逻辑推理规则
1. 量词消去与引入规则
| 规则名称 | 符号表示 | 约束条件 |
|---|---|---|
| 全称特指（US） | (∀x)G(x)⇒G(y) 或 G(c) | G(x)对y自由；c为任意常量 |
| 存在特指（ES） | (∃x)G(x)⇒G(c) | c为使G(c)为真的特定常量；含其他自由变元时用函数替换 |
| 全称推广（UG） | G(y)⇒(∀x)G(x) | G(y)对x自由；无自由x；y非ES引入 |
| 存在推广（EG） | G(c)或G(y)⇒(∃x)G(x) | G(c)/G(y)对x自由；无自由x |
2. 量词相关推理定律
- I17：(∀x)G(x)⇒(∃x)G(x)（全称推存在）
- I18：(∀x)(G(x)→H(x))⇒(∀x)G(x)→(∀x)H(x)
- I19：(∀x)(G(x)→H(x))⇒(∃x)G(x)→(∃x)H(x)
- I20：(∃x)(G(x)∧H(x))⇒(∃x)G(x)∧(∃x)H(x)
- I21：(∃x)(∀y)G(x,y)⇒(∀y)(∃x)G(x,y)（量词顺序蕴涵）
- I22：(∀x)(∀y)G(x,y)⇒(∃y)(∀x)G(x,y)
3. 推理限制规则
- 消去顺序：先ES后US，避免个体常量冲突
- 多存在量词：不同(∃x)消去用不同常量
- 量词添加：ES引入的变量仅能EG，US引入的变量可EG/UG
要不要我帮你整理一份公式速查卡片？按“命题逻辑-谓词逻辑-推理规则”分类，提炼核心公式和使用场景，方便快速查阅记忆。