...menustart
- Week2 数理逻辑： 命题逻辑 及 形式系统
...menuend
- 命题公式的数量是无穷的，但是 可以从真值的 角度进行分类
- 重言式：（永真式）tautology
- 命题变元的所有赋值都是命题公式的成真赋值
- 矛盾式（永假式、不可满足式） contradiction
- 命题变元的所有赋值都是命题公式的成假赋值
- 可满足式 (contingency)
- 命题公式至少有一个成真赋值
- 需要分清的概念
- 永真式都是可满足式
- 矛盾式都不是可满足式
- 非永真式并不都是永假式
- 如果A是永真式，则¬A就是永假式，
- 反之亦然
- 对于任何公式A
- A∨¬A 是重言式（排中律）
- A → A 也是重言式
- A∧¬A 是矛盾式（矛盾律）
- 采用命题公式的真值表证明重言式
- 证明 (p∨q)∧¬p→q 是重言式
- 当命题公式A↔B 是重言式时，则称A 逻辑等价于B，记作A╞╡B ，称作逻辑等价式
- 也可以理解为公式A和公式B 等值
- 逻辑等价体现了两个公式之间的一种 关系：在任何赋值状况下它们都等值
- 任何赋值，如果使得 A 成真，那么B 也必然真； 如果使得A 为假，那么B也必然假。
- eg. 如果A,B 都是永真式, 那么A,B 逻辑等价
- ¬¬A╞╡A（双重否定律）
- A∨A╞╡A，A∧A╞╡A（幂等律）
- v, ∧ 无论作用于自身多少次，都等价于 自身
- 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（吸收律）
- v, ∧ 各作用一次到A， 结果和B没有关系
- A→B╞╡¬A∨B（蕴涵等值式）
- A↔B╞╡(A→B)∧(B→A)（等价等值式）
- A∨t╞╡t，A∧f╞╡f（零律） - A 被吸收
- A∨f╞╡A，A∧t╞╡A（同一律）
- A∨¬A╞╡t， A∧¬A╞╡f（排中律和矛盾律）
- ¬t╞╡f，¬f╞╡t
- A∧B→C╞╡A→(B→C) ╞╡B→(A→C) - A∧B→C╞╡ ¬(A∧B)∨C ╞╡ (¬A∨¬B)vC ╞╡ ¬A∨(¬BvC) ╞╡ A→(¬BvC) ╞╡ A→(B→C)
- A→B╞╡¬B→¬A（假言易位） - 逆否命题
- (A→B)∧(A→¬B)╞╡¬A（归谬论） - A本身 是有问题的，自相矛盾，因为它推出了B ，又推出了¬B , 那么A肯定是不成立的, 所以等价于 ¬A
- A↔B╞╡(A∧B)∨(¬A∧¬B)（等价等值式2） - 等值， A和B 同时成立，或 同时不成立
- 当命题公式A→B是重言式时，则称A逻辑蕴涵B，记作A╞B ，称作逻辑蕴涵式
- 也可以理解为公式A的所有成真赋值都是公式B的成真赋值
- 每个逻辑等价式可以看作两个逻辑蕴涵式， 也就是说A╞╡B 也有 A╞B,B╞A
- A和B等值，所以A→B和B→A都是重言式
- 逻辑蕴涵体现了两个公式AB之间的另一种 关系: 在任何赋值状况下只要A真，B都真
- eg. 如果A,B都为 矛盾式， 那么 A逻辑蕴涵 B
- 逻辑蕴涵式只关心 A成立的情况，A不成立的情况，肯定逻辑蕴涵
- A ╞ A∨B
- 只要A 为真，A∨ 任何东西都为真
- A∧B ╞ A , A∧B ╞ B
- A∧(A→B) ╞ B (分离规则)
- A 成立，同时 A→B 也成立, 则B成立
- (A→B)∧¬B ╞ ¬A
- A推出B, 但是 B不成立, 则A不成立
- ¬A∧(A∨B) ╞ B
- 如果A∨B 成立，同时A不成立，则 B成立
- (A→B)∧(B→C)╞ A→C (蕴涵可传递性)
- (A→B)∧(C→D)╞ (A∧C)→(B∧D)
- 把前件归在一起，把后件归在一起
- (A↔B)∧(B↔C) ╞ A↔C
- 逻辑蕴涵经常会被推广为 Γ╞ B 的形式 ( Γ gamma)
- 其中Γ是一系列公式，表示B是Γ的 逻辑结果
- 即：使Γ中每一个公式成真的赋值，都是公式B的成真赋值
- 即Γ中的 所有公式的合取 逻辑蕴涵B
- 当Γ中仅包含一个公式A时，就是A╞B ；
- 如果Γ中不包含任何公式，记做╞B，表示 “B永真”
- 命题公式关系的自反、对称、传递等性质
- A╞╡B 当且仅当 ╞ A↔B (逻辑等价的定义)
- A╞B 当且仅当 ╞A→B (定义)
- 若A╞╡B，则B╞╡A (对称性)
- 若A╞╡B， B╞╡C，则A╞╡C (传递性)
- 若A╞B，则¬B╞¬A (类似 假言易位)
- 若A╞B， B╞C，则A╞C
- 若A╞B，A╞╡A’，B╞╡B’，则A’╞B’ (可替换性)
- 将重言式A中的某个命题变元p的所有出现都代换为命题公式B，
- 得到的命题公式记作A(B/p)，A(B/p) 也是重言式。
- 因为重言式A的真值与p的取值状况 无关，恒为t，
- 所以将p全部代换后的公式A(B/p)的 真值也恒为t
- 注意：
- 仅代换部分出现本原理不成立
- 如果B中包含了p或者A中的其它变元, 本原理依然成立
- 将命题公式A中的子公式C的部分出现替换为和C逻辑等价的 公式D （C╞╡D ），
- 得到的命题公式记作B，则 A╞╡B 。
- 因为C和D（在任何赋值下）等值， 所以用D替换C不会改变A的真值
- 注意：
- 不要求全部出现都替换
| · | 代入原理RS | 替换原理RR |
|---|---|---|
| 使用对象 | 任意永真式 | 任意命题公式 |
| 代换对象 | 任意命题变元 | 任意子公式 |
| 代换物 | 任意命题公式 | 任意与代换对象等价的命题公式 |
| 代换方式 | 代换同一命题变元的所有出现 | 代换子公式的某些出现 |
| 代换结果 | 仍为永真式 | 与原公式等价 |
- 真值表法：要证明A╞╡B，A╞B，只要：
- 分别列出A↔B和A→B的真值表，最后一列全为真即可。
- 公式一复杂，真值表会非常庞大
- 对赋值进行讨论：要证明A╞B，只要证明：
- A的任意一个成真赋值都是B的成真赋值，或者
- B的任意一个成假赋值都是A的成假赋值。
- 并不是说对每一个赋值进行讨论，对赋值的各种状况进行一个分类，并每一类进行导论。
- 如果每一类都符合我们的要求的话， 那么也就完成了证明
- -> 如果证明了A╞B和B╞A，那么就证明了A╞╡B。
- 推演法：利用已知的重言式、逻辑等价式和逻辑蕴涵式，采用代入原理和替换原理进行推演。
- 先证明(A∨B)→C╞(A→C)∧(B→C)
- 假设α是(A∨B)→C任意一个成真赋值，这样会有两种情况：
- α(A∨B)=f：于是α(A)=α(B)=f，就有α(A→C)=α(B→C)=t 〉 或者，
- α(A∨B)=t，α(C)=t：于是α(A→C)=α(B→C)=t
- 上述两种情况都得到α((A→C)∧(B→C))=t，得证。
- 讨论赋值法证明逻辑等价式：(A∨B)→C╞╡(A→C)∧(B→C)
- 我们发现反过来的证明是比较困难的, 所以我们 也反过来进行假设
- 反过来，假设α是(A∨B)→C任意一个成假赋值，这样只有一种情况：
- α(A∨B)=t，α(C)=f
- 当α(A)=t，α(C)=f时，α(A→C)=f；
- 当α(B)=t，α(C)=f时，α(B→C)=f，
- 不管如何，都有α((A→C)∧(B→C))=f
- 得证
- (A∨B)→C
- ╞╡¬(A∨B)∨C（蕴涵等值式，代入原理）
- ╞╡(¬A∧¬B)∨C（德摩根律，替换原理）
- ╞╡(¬A∨C)∧(¬B∨C)（分配律，代入）
- ╞╡(A→C)∧(¬B∨C)（蕴涵等值式，替换）
- ╞╡(A→C)∧(B→C)（蕴涵等值式，替换）
- A∧B
- ╞B（I2：A∧B╞A）
- ╞¬C∨B（I1：A╞A∨B，代入）
- ╞C→B（蕴涵等值式，代入）
- ╞A∨(C→B)（I1：A╞A∨B，代入）
- ╞¬A→(C→B)（蕴涵等值式，代入）
- 每个命题公式都会存在很多与之逻辑等价的公式
- 范式：在命题公式的多个逻辑等价的 形式中，较为符合“标准”或“规范” 的一种形式
- 文字(literals)：命题常元、变元和它们的否定
- 前者称正文字，后者称负文字，
- 如：p, ¬q, t
- 析取子句(disjunctive clauses)：文字或者若干文字的析取，
- 如：p, p∨q, ¬p∨q
- 合取子句(conjunctive clauses)：文字或者若干文字的合取，
- 如：p, p∧q, ¬p∧q
- 互补文字对(complemental pairs of literals)：指一对正文字和 负文字，
- 如：p和¬p
- 公式A’称作公式A的析取范式，如果：
- A’╞╡A
- A’为合取子句或者若干合取子句 的析取
- eg.
- p→q的析取范式为¬p∨q（合取子句¬p 和q的析取）
- ((p→q)∧¬p)∨¬q的析取范式为 ¬p∨(q∧¬ p)∨¬q
- 公式A’称作公式A的合取范式，如果：
- A’╞╡A
- A’为析取子句或者若干析取子句 的合取
- eg.
- p→q的合取范式为¬p∨q（析取子句 ¬p∨q）
- 和 析取范式 相同的形式
- ((p→q)∧¬p)∨¬q的合取范式为 (¬p∨t)∧(¬p∨¬q)或¬p∨¬q
- p→q的合取范式为¬p∨q（析取子句 ¬p∨q）
- 利用逻辑等价式和代入原理、替换原理，可 以求出任一一个公式的析取范式和合取范式
- eg. 求¬p→¬(p→q)的析取范式及合取范式
- ¬p→¬(p→q)
- ╞╡¬p→¬(¬p∨q)
- ╞╡p∨¬(¬p∨q)
- ╞╡p∨(p∧¬q)（析取范式）
- ╞╡(p∨p)∧(p∨¬q)
- ╞╡p∧(p∨¬q)（合取范式）
- ╞╡p
- 重言式识别
- 合取范式中每个析取子句都包含了至 少一个互补文字对：
- (p∨¬p∨q)∧(p∨q∨¬q)
- 如果一个命题公式，它的某一个合取范式的形式里面，有每一个的析取自居 都包含了至少一个 互补文字对的话，那么这个命题公式就是 重言式。
- 矛盾式识别
- 析取范式中每个合取子句都包含了至 少一个互补文字对：
- (p∧¬p∧q)∨(p∧q∧¬q)
- 消去公式中的联结词→和↔
- p→q化为¬p∨q（蕴涵等值式）
- p↔q化为(¬p∨q)∧(p∨¬q)或者(p∧q)∨(¬p∧¬q)（等价等值式）
- 利用德摩根律 将否定联结词¬向内深入，最后只作用于文字，再将 ¬¬p化为p
- 利用分配律，最后得到需要的析取或者合取范式
- 一个公式的析取范式或合取范式都 不是唯一的
- p, p∨(p∧¬q), (p∧q)∨(p∧¬q)都是¬p→¬(p→q)的析取范式
- p, p∧(p∨¬q), (p∨q)∧(p∨¬q)都是¬p→¬(p→q)的合取范式
- 公式的析取范式有可能同时又是合取范式
- ¬p∨q既是p→q的析取范式又是合取范式
- 能否找到“最为规范”的范式？
- 具备唯一性的范式
- 具有 唯一性的 范式的形式。
- 主析取范式(major disjunctive form)
- 公式A'称作公式A(p1, p2, …pn)的主析取范式，如果：
- A'是A的析取范式
- A'中每一个合取子句里p1, p2, …pn均恰出现一次
- 每一个合取子句 都要包含所有的命题变元，而且 只出现一次
- 公式A'称作公式A(p1, p2, …pn)的主析取范式，如果：
- 主合取范式(major conjunctive form)
- 公式A'称作公式A(p1, p2, …pn)的主合取范式，如果：
- A'是A的合取范式
- A'中每一个析取子句里p1, p2, …pn均恰出现一次
- 公式A'称作公式A(p1, p2, …pn)的主合取范式，如果：
- 主析取范式存在唯一性证明：约定
- 首先，合取子句中的文字按照其包含的变元下标从小到大排列
- 对于包含所有变元p1, p2, …pn的并排列好文字顺序的合取子句，我们称为极小项(min term)，记作mᵢ
- 其中i是一个整数，i对应的n位二进制表示描述了对应下标的变元在合取子句中 的否定状态
- 例p1∧p2∧p3记作m₇（7=111）；p1∧¬p2∧¬p3记作m₄（4=100）
- 主析取范式是极小项按照其下标从小到大排列的析取
- 顺序不影响证明
- 主析取范式存在唯一性证明：极小项赋值引理
- 极小项只有唯一的成真赋值，
- 且成真赋值中每个变元的取值等于极小项下标的二进制形式中变元下标所 对应的二进制位的值：
- p1∧p2∧p3（m7）的唯一成真赋值 是p1=1, p2=1, p3 =1,
- p1∧¬p2∧¬p3（m4）的唯一成真 赋值是p1=1, p2=0, p3 =0
- 主析取范式存在唯一性证明：主析取范式的成真赋值
- 极小项和主析取范式的关系
- 主析取范式包含的极小项的成真赋值 也是主析取范式的成真赋值
- 主析取范式的任一一个成真赋值是其 包含的某个极小项的成真赋值
- 主析取范式不包含的极小项的成真赋值是主析取范式的成假赋值
- 极小项和主析取范式的关系
-
主析取范式存在唯一定理：存在性证明
- 任何命题公式A(p1, p2, …pn)的主析取范式都是存在的，并且是唯一的.
- 假设A'是公式A(p1, p2, …pn)的析取范式
- 如果A'中某个合取子句Ai既不包含pj，也不包含¬pj，那么我们将Ai展成如下 形式：
- Ai╞╡Ai∧1╞╡Ai∧(pj∨¬pj)╞╡(Ai∧pj) ∨(Ai∧¬pj)
- 这样就有 pj 了
- 将合取子句中重复出现的命题变元，矛盾式消去，将重复出现的合取子句消去
- p∧p╞╡p； p∧¬p╞╡0； Ai∨Ai╞╡ Ai
- 最后将所有的合取子句整理变元顺序，成为极小项，并得到主析取范式A'
-
主析取范式存在唯一定理：唯一性证明
- 反证法：假设公式A(p1, p2, …pn)存在两个不同的主析取范式B和C
- 由于A╞╡B且A╞╡C，所以B╞╡C
- 因为B和C是两个不同的主析取范式，那么一定存在某个极小项mᵢ只出现在B或 者只出现在C中，不妨设mᵢ只出现在B中，不出现在C中，这样：
- mᵢ的成真赋值是B的成真赋值，却是C的成假赋值
- 与B╞╡C矛盾
- 所以B和C必然相同，也就是说公式A(p1, p2, …pn)的主析取范式是唯一的
- 存在性证明还给出了主析取范式的构造步骤。
- 具有相同主析取范式的公式都是等值的，属于同一个等值类，否则 属于不同的等值类
- 虽然公式的数量无限多，但等值类的数量是有限的：
- 极小项的数量为 N=2ⁿ ；
- 由极小项组合成的主析取范式的数量为2ᴺ；
- C(N,0) + C(N,1) + C(N,2) + ... + C(N,N) = 2ᴺ
- 等值类的数量等于主析取范式的数量
- 虽然包含n个变元的 命题公式数量是 无穷的，但主析取范式的数量确是有限的
- 极大项和成假赋值
- 主合取范式的存在性和唯一性
- 主合取范式的构造步骤
- 命题公式A(p1, p2, …pn)的等值分类
-
TODO
-
为什么 ∧ , ∨ , ￢ 三个连接词就足以代表所有的命题公式了呢？
-
如果任意一个真值函数都可以用仅包含某个联结词集中的联结词的 命题公式表示，则称这个联结词集为功能完备集
- 目前使用的{¬,∧,∨,→,↔}是功能完备集
- →,↔ 是冗余联结词
- {¬,∧,∨}是功能完备集
- {¬,→}是功能完备集
- 目前使用的{¬,∧,∨,→,↔}是功能完备集
-
如果一个功能完备集中不含冗余联结 词，则称这个功能完备集为极小的。
- {¬,→}， {¬,∧}， {¬,∨}都是极小功 能完备集
-
仅包含单个联结词的功能完备集
- 定义联结词↓（Peirce记号）
- p↓q╞╡¬(p∨q)
- {↓}是功能完备集
- 定义联结词↓（Peirce记号）