第六课：联结词集完备性、形式系统、PC¶
Page 2 — 功能完备集¶
- {¬,∧,∨,→,↔}是功能完备集
- 任意真值函数都可以用主析取范式表示
- 主析取范式中只用到了¬,∧,∨
- ∴ {¬,∧,∨} 是功能完备集
Page 3 — 冗余联结词¶
- 若某联结词可用集合中其他联结词定义，称它为冗余联结词
- A→B ≡ ¬A∨B → →是冗余联结词
- {¬,∧,∨,↔}是否有冗余联结词？
- {¬,∧,∨}是否有冗余联结词？
Page 4 — 极小功能完备集¶
- 不含冗余联结词的功能完备集叫极小的功能完备集
- {¬,→}、{¬,∨}、{¬,∧} 都是极小功能完备集
💡 人话：功能完备集就是"够用"的联结词集合，极小功能完备集就是"刚好够用，一个都不能少"。
Page 5 — 单联结词功能完备集¶
- 定义↓（Peirce记号）：p↓q ≡ ¬(p∨q)
- {↓} 是功能完备集！
- 证明：用↓定义¬和∨
- ¬p ≡ ¬(p∨p) ≡ p↓p
- p∨q ≡ ¬¬(p∨q) ≡ ¬(p↓q) ≡ (p↓q)↓(p↓q)
Page 6 — 非功能完备集证明¶
- {∧}不是功能完备集——不能构成矛盾式
- {¬,↔}不是功能完备集——用它们组成的公式，成真赋值个数总是偶数
- 不能表示成真赋值个数为奇数的真值函数
💡 人话：有些联结词集合不够"强大"，表达不了所有真值函数。比如只用∧，你搞不出永假式；只用{¬,↔}，你搞不出奇数个真值的函数。
Page 7-8 — 形式系统概述¶
- 重言式反映人类逻辑思维基本规律：
- 排中律、矛盾律、假言推理、归谬推理、穷举推理
- 形式系统 = 符号体系
- 公理 + 推理规则 → 推导定理
- 公理和规则确保：正确的前提 → 正确的结论
💡 人话：形式系统就像一种"符号游戏"——给定一些初始符号（公理）和变换规则（推理规则），可以推导出新的符号串（定理）。
Page 9 — 证明（Proof）¶
- 公式序列A₁,A₂,...,Aₘ称作Aₘ的一个证明，若每个Aᵢ：
- 是公理，或
- 由之前的公式用推理规则推得
- 此时称Aₘ为系统的定理，记作 ⊢Aₘ
Page 10 — 演绎（Deduction）¶
- 设Γ为公式集合，公式序列A₁,...,Aₘ称作以Γ为前提的演绎，若每个Aᵢ：
- 是Γ中的公式，或
- 是公理，或
- 由之前的公式用推理规则推得
- 记作 Γ ⊢ Aₘ
- 证明是演绎在Γ为空集时的特例
Page 11-12 — 命题演算形式系统PC¶
- 符号系统：
- 命题变元：p,q,r,s,p₁,q₁,r₁,s₁
- 命题常元：t（真）, f（假）
- 联结词：¬, →（极小功能完备集）
- 括号：(,)
- PC的三条公理（A,B,C表示任意公式）：
- A1: A→(B→A)
- A2: (A→(B→C)) → ((A→B)→(A→C))
- A3: (¬A→¬B) → (B→A)
- 推理规则（仅一条！）：
- 分离规则（Modus Ponens）：A, A→B ⊢ B
💡 人话：PC系统只用¬和→两个联结词，三条公理，一条规则。虽然简单，但它是完备的——所有重言式都能证出来。
Page 13-16 — PC的性质¶
- 合理性（Soundness）：如果⊢A，则⊨A（证明的都是对的）
- 一致性（Consistency）：不存在A使得⊢A且⊢¬A（不自相矛盾）
- 完备性（Completeness）：如果⊨A，则⊢A（所有对的都能证明）
Page 30 — PC定理的判定¶
- 虽然PC中证明很繁琐，但可以借助真值表判定一个公式是否重言式（即是否PC定理）
- 真值表不是PC中的成分，但它是外部的有效判定方法
Page 31 — 命题逻辑的局限¶
- 命题逻辑的最小研究单位是原子命题，没有内部结构
- 命题之间相互独立，没有内在联系
- 经典三段论在命题逻辑中不是永真式：
- 大前提p：所有学校都有学生
- 小前提q：浙大是学校
- 结论r：浙大有学生
- (p∧q)→r 不是永真式（除非把内部结构展开）
Page 32-33 — 从命题逻辑到谓词逻辑¶
- 需要分析命题的内部结构
- 个体：被判断的对象
- 谓词：作出的判断
- 量词：个体的数量（所有、有一些）
- 谓词逻辑（一阶逻辑）将量词作用于个体
Page 34-37 — 谓词逻辑基础概念¶
- 个体常元：a,b,c（确定的个体）
- 个体变元：x,y,z（不确定的个体）
- 个体域D：被讨论对象的全体
- 全总域U：包含一切对象的个体域
- 谓词：表示个体性质或关系
- 单元谓词：P(x)
- 二元谓词：Q(x,y)
- 三元谓词：R(x,y,z)
- 谓词命名式：占位符，如SCHOOL(x)
- 谓词填式：实实在在填入个体，如SCHOOL(浙江大学)
Page 38-39 — 量词¶
- 全称量词 ∀：所有
- 存在量词 ∃：有一些
- 约束变元：受量词约束，可改名不影响含义
- 自由变元：可取值代入
- 辖域：量词作用的范围
- 有限个体域D={a₁,...,aₙ}：
- ∀xP(x) ≡ P(a₁)∧...∧P(aₙ)
- ∃xP(x) ≡ P(a₁)∨...∨P(aₙ)
💡 人话：∀对应于"且"，∃对应于"或"。说"所有人都……"等于说"第一个人……且第二个人……且……"，说"有人……"等于说"第一个人……或第二个人……或……"。