======数理逻辑:命题逻辑和形式系统======
Coursera 离散数学概论笔记:第二周\\
E1. ¬¬A╞╡A
**E2.幂等律**
\\
理解:任意一个公式与自身的合取和析取都等价于自身。
E2. A∨A╞╡A,A∧A╞╡A
**E3.E4.E5:交换律、结合律、分配律**
\\
理解:命题的公式的合取、析取都遵循像四则运算一样的交换律、结合律、分配律。
E3. A∨B╞╡B∨A, A∧B╞╡B∧A //交换律
E4. (A∨B)∨C╞╡A∨(B∨C),(A∧B)∧C╞╡A∧(B∧C) //结合律
E5. A∧(B∨C)╞╡(A∧B)∨(A∧C),A∨(B∧C)╞╡(A∨B)∧(A∨C) //分配律
**E6.德摩根律**
\\
理解:两个公式析取(合取)的否定,与这两个公式自身的否定的合取(析取)等价。
E6. ¬(A∨B)╞╡¬A∧¬B, ¬(A∧B)╞╡¬A∨¬B
**E7. 吸收律**
\\
理解:一个命题公式与别的公式先合取(析取),再与自身析取(合取),结果与自身等价。因为结果实际上与别的公式没有关系,看起来像是被吸收了,所以被称为吸收律。
E7. A∨(A∧B)╞╡A, A∧(A∨B)╞╡A
**E8. 蕴含等值式**
\\
理解:很重要的逻辑等价式,证明可以通过真值表验证。
E8. A→B╞╡¬A∨B
**E9. 等价等值式**
\\
理解:两个公式等价,当且仅当他们之间能相互推导。
E9. A↔B╞╡(A→B)∧(B→A)
**E10.E11.E12.E13. 零律、同一律、排中律与矛盾律、非真既假**
\\
理解:
* 零律:命题公式**与真析取**恒为真,**与假合取**恒为假。
* 同一律:命题公式**与假析取**,**与真合取**都等同于自身。
* 排中律:命题与自身的否定的析取恒为真,即自身与自身的否定必有一个是正确的。
* 矛盾律:命题与自身的否定的合取恒为假,即自身与自身的否定不可能同时正确。
* 非真既假:字面意思。
E10. A∨t╞╡t,A∧f╞╡f //零律
E11. A∨f╞╡A,A∧t╞╡A //同一律
E12. A∨¬A╞╡t, A∧¬A╞╡f //排中律和矛盾律
E13. ¬t╞╡f,¬f╞╡t //非真既假
**E14. 级联加蕴含**
E14. A∧B→C╞╡A→(B→C)
/* 推导过程:使用蕴涵等值式 、德摩根律 */
A∧B→C╞╡¬(A∧B)∨C ╞╡ (¬A∨¬B)∨C ╞╡ ¬A∨(¬B∨C) ╞╡ A→(¬B∨C) ╞╡ A→(B→C)
**E15.假言易位**
\\
理解:逆否命题。
E15. A→B╞╡¬B→¬A
**E16.归谬论**
\\
理解:一个命题不可能同时推出另一个命题和它的否定。
E16. (A→B)∧(A→¬B)╞╡¬A
**E17.等价等值式II**
\\
理解:如果两个命题等价:要么这两个命题都成立,要么这两个命题都不成立。
E17. A↔B╞╡(A∧B)∨(¬A∧¬B)
===逻辑蕴涵式 Logical Implication===
命题公式还有一种很重要的关系:逻辑蕴涵。这种命题表现为蕴涵,即 $A→B$。如果这个命题是重言式,那么我们就称 $A$ **逻辑蕴涵** $B$,记做 $A╞B$。
\\
\\
关于逻辑蕴涵式,有几点需要注意的是:
* 逻辑蕴涵式可以理解为**公式 $A$ 所有的成真赋值都是公式 $B$ 的成真赋值**。
* 相对于逻辑等价式,逻辑蕴涵式需要公式 $A$ 作为条件,即 $A$ 成立,那么 $B$ 一定成立。
* 显然的是,逻辑等价式可以看做两个逻辑蕴涵式,即 $A╞B$ 并且 $B╞A$;也就是说, $A→B$ 和 $B→A$ 都是重言式。
==重要的逻辑蕴涵式==
**I1**: $A╞ A∨B$
\\
理解:只要一个命题公式为真,那么它与任何公式合取都为真。
\\
\\
**I2**: $A∧B╞ A$ 和 $A∧B╞ B$
\\
理解:如果$A$ 和 $B$ 合取成立,那么肯定能推出命题公式 $A$ 和 $B$ 都成立。
\\
\\
**I3**: $A∧(A→B)╞ B$
\\
理解:一个命题公式成立,而且它可以推导出另外一个命题公式,那么另外一个命题公式也成立。该蕴涵式被称为**分离规则**,是非常重要的一个蕴涵式。
\\
\\
**I4** : $(A→B)∧¬B╞ ¬A$
\\
理解:命题公式 $A$ 可以推出 $B$,如果 $B$ 不成立,那么 $A$ 一定不成立。
\\
\\
**I5**: $¬A∧(A∨B)╞ B$
\\
理解:命题公式 $A$ 不成立,如果命题 $A$ 和 $B$ 至少有一个成立,那么成立的肯定是 $B$。
\\
\\
**I6**: $(A→B)∧(B→C)╞ A→C$
\\
理解:如果命题公式 $A$ 能推出 $B$,且 $B$ 能推出 $C$,那么 $A$ 一定能推出 $C$(蕴涵的可传递性)。
\\
\\
**I7**: $(A→B)∧(C→D)╞ (A∧C)→(B∧D)$
\\
理解:命题公式 $A$、$C$ 如果能分别推出 $B$、$D$,那么$A$、$C$ 的合取也一定能推出 $B$、$D$ 的合取。
\\
\\
**I8**: $(A↔B)∧(B↔C)╞ A↔C$
\\
理解:命题公式$A$、$B$ 等价,且命题公式 $B$、$C$ 等价,那么 $A$、$C$ 也等价(等价的可传递性) 。
===命题公式的逻辑结果===
逻辑蕴涵式往往被作为推理的公式使用,因此它经常被推广为**条件加上结果**的的形式,即:
\\
\\
$$Γ╞B$$
\\
公式中的 $Γ$ (读作 //Gamma//) 代表了一系列的公式,(可以理解为**前提条件公式的序列**),而 $B$ 则是 $Γ$ 的逻辑结果。
\\
\\
很显然的是,该公式有几个特点:
* 使得 $Γ$ 中每一个公式都成真的赋值,都是公式 $B$ 的成真赋值,即 $Γ$ 中所有公式的合取逻辑蕴涵 $B$。
* 特殊化 I:当 $Γ$ 中只有一个公式 $A$ 时,那么就是标准的 $A$ 逻辑蕴涵 $B$ 的形式。
* 特殊化 II:如果 $Γ$ 是空集,那么 $B$ 就不需要任何前提条件,即 $B$ 自身是重言式。
===逻辑蕴涵式 / 等价式的性质===
逻辑等价式和逻辑蕴涵式都有其自身的特性,并在某种情况下可以转换。常见的特性有:**自反**、**对称**、**传递**。参考逻辑等价式和逻辑蕴涵式的定义和上述特性,我们可以总结出一些性质:
\\
\\
**定义**
* $A╞╡B$ 当且仅当 $╞ A↔B$ (逻辑等价)
* $A╞ B$ 当且仅当 $╞ A→B$ (逻辑蕴涵)
**自反性(显然的)**
* $A↔A$
**对称性**
* 若 $A╞╡B$,则 $B╞╡A$
**可传递性**
* 若$A╞╡B$, $B╞╡C$,则 $A╞╡C$
* 若$A╞ B$, $B╞ C$,则 $A╞ C$
**其他**
* 若$A╞ B$,则 $¬B╞ ¬A$ (逆否)
* 若 $A╞ B$,$A╞╡A’$,$B╞╡B’$,则 $A’╞ B’$ (可替换性)
===命题公式的代入与替换===
命题公式有两个比较重要的原理:**代入原理**和**替换原理**。
==代入原理 Rule of substitution==
代入原理又称重言式代入原理。该原理定义如下:
>将**重言式** $A$ 中的某个命题变元 $p$ 的所有出现都代换为命题公式 $B$ , 得到的命题公式记作 $A(B/p)$,则 $A(B/p)$ 也是重言式。
因为重言式的真值恒为真,与 $p$ 的取值没有关系。因此,将所有的 $p$ 替换成 $B$ 以后得到的公式 $A(B/p)$ 也是重言式。
需要注意的是:
* 部分替换 $p$ 会导致原理不成立。
* 如果 $B$ 中包含了 $p$ 或者 $A$ 中的其他变元,那么本原理也成立。
==替换原理 Rule of replacement==
替换原理的定义如下:
>将命题公式 $A$ 中的子公式 $C$ 的部分出现替换为和 $C $逻辑等价的 公式 $D$(即 $C╞╡D$),得到命题公式记做 $B$,可得:$A╞╡B$。
替换原理生效的原理是:$C$ 和 $D$ 在任何复制下都等值,因此用 $D$ 替换 $C$ 并不会影响 $A$ 的真值。
\\
\\
==代入原理与替换原理的区别==
^ ^ 代入原理 ^ 替换原理 ^
^ 使用对象 | 永真式 | 命题公式 |
^ 被代换对象 | 命题变元 | 子公式 |
^ 代换对象 | 命题公式 | 与代换对象**等价**的命题公式 |
^ 代换方式 | 代换同一命题变元的所有出现 | 代换子公式的某些出现 |
^ 代换后结果 | 永真式 | 与原公式等价 |
===逻辑蕴涵式 / 等价式的证明===
常用的证明逻辑蕴涵式和逻辑等价式的方法有三种:**真值表法**、**对赋值进行讨论**、**推演法**。
\\
\\
**真值表法**:
* 证明 $A╞╡B$,$A╞B$,只要构造出双向蕴涵的真值表 / 蕴涵真值表,如果最后一列全为真,那么就可以得证。该方法一目了然,但对于复杂的命题公式来说,构造真值表的工作量较大。
**对赋值进行讨论**:
* 使用该方法证明$A$ 蕴涵 $B$ 只需要证明 $A$ 的任意一个成真赋值都是 $B$ 的成真赋值,反过来也适用。
* 证明逻辑等价只需要上述两个蕴涵关系均得证即可。
**推演法**:
* 推演法利用已知的重言式、逻辑等价式、逻辑蕴涵式,使用代入原理和替换原理进行推演。
==E.g. 赋值法证明逻辑等价式==
证明:(A∨B)→C╞╡(A→C)∧(B→C)
/*先证明 (A∨B)→C╞ A→C)∧(B→C) */
/*证明 (A∨B)→C 为真,那么 (A∨B) 有两种情况,分别证明即可。*/
假设 a 为 (A∨B)→C 的成真赋值,那么有如下两种情况:
/*第一种情况*/
如果 a(A∨B) = F,那么显然有 a(A) = F,a(B) = F //析取为F, 那么元素应全为F
那么显然有 a(A→C) = T、a((B→C) =T //蕴涵在前提为假的情况下恒为真
因此在 a(A∨B) = F 的假设下, (A→C)∧(B→C) 为真。
/*第二种情况*/
如果 a(A∨B) = T,那么显然有 a(C) = T //蕴涵前提为真,那么结果必须为真才能保证命题为真
那么显然有 a(A→C) = T,a(B→C) =T
因此在 a(A∨B) = T下, (A→C)∧(B→C) 也为真。
得证。
/*再证明(A→C)∧(B→C)╞ (A∨B)→C */
假设 a 是 (A∨B)→C 的成假赋值,那么只有如下一种情况:
a(A∨B) = T,a(C) = F。
当 a(A) = T, a(C) = F,a(A→C) = F;
当 a(B) = T, a(C) = F,a(B→C) = F;
因此 当(A∨B)→C 为假,(A→C)∧(B→C) 恒为假。
得证。
==E.g.推演法证明逻辑等价式==
证明:(A∨B)→C╞╡(A→C)∧(B→C)
(A∨B)→C ╞╡ ¬(A∨B) ∨C //蕴涵等值式,代入
¬(A∨B) ∨C ╞╡(¬A∧¬B)∨C //德摩根律。替换
(¬A∧¬B)∨C ╞╡(¬A∨C)∧(¬B∨C) //分配律,代入
(¬A∨C)∧(¬B∨C)╞╡(A→C)∧(B→C) //蕴涵等值式,替换
==E.g.推演法证明逻辑等价式.II==
证明 A∧B╞¬A→(C→B)
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//):包含命题常元 / 变元, 以及他们的否定形式。前者称为**正文字**,后者称为**负文字**。
* 析取字句(//Disjunctive clauses//):包含了文字或者若干的文字的析取形式,比如 $p, p∨q, ¬p∨q$。
* 合区字句(//Conjunctive clauses//):包含了文字或者若干文字的合取形式,比如 $p, p∧q, ¬p∧q$。
* 互补文字对(//Complemental pairs of Literals//):指一对正文字和负文字,比如 $p, ¬p$。
===析取范式===
析取范式 (//Disjunctive normal form//)的定义如下:
>公式 $A’$ 称作公式 $A$ 的析取范式,如果:
>1. $A’╞╡A$
>2. $A’$ 为**合取子句**或者若干**合取子句的析取**
一些例子如下:
* $p→q$ 的析取范式为 $¬p∨q$(合取子句 $¬p$ 和 $q$ 的析取)
* $((p→q)∧¬p)∨¬q$ 的析取范式为 $¬p∨(q∧¬ p)∨¬q$
===合取范式===
合取范式(//Conjunctive normal form//)的定义如下:
>公式 $A’$ 称作公式 $A$ 的**合取范式**,如果:
>1. $A’╞╡A$
>2. $A’$ 为**析取子句**或者若干**析取子句的合取**
一些合取范式的例子如下:
* $p→q$ 的合取范式为 $¬p∨q$(同时也是析取子句 $¬p∨q$)
* $((p→q)∧¬p)∨¬q$ 的合取范式为 $(¬p∨t)∧(¬p∨¬q)$ 或 $¬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, 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的析取范式又是合取范式
====主范式====
由上一节的范式的唯一性可知,范式不是唯一的。因此,为了更好的规范化我们的命题公式的写法,我们需要一种具有**唯一性的范式**。这种范式,我们称为**主范式**。
\\
\\
根据组合关系的不同,主范式也同样分为**主合取范式**和**主析取范式**。
===极小项和极大项===
前面说过,主析取范式和主合取范式最大的优势就是其唯一性。为了精确的表达这个唯一性,我们需要引进两个概念:**极小项**和**极大项**。
\\
\\
==极小项==
极小项(//Min term//)可以通俗的描述如下:
- 假设我们有一个公式 $A(p_1,p_2,…p_n)$,该公式中所有命题变元按照一定的顺序排列起来。
- 按照该公式中命题变元的排序,我们用**合取**的方式将这些变元联结起来。
- 每个命题变元只能出现一次,出现的形式其自身或者其自身的否定。
- 满足以上要求的字符串,我们就称为该命题公式的**极小项**,记做 $M_i$
前面的析取范式中主要存在两个问题导致了析取范式的不唯一性:互补文字对与文字的重复。而极小项通过对命题变元的排序,和限制命题变元的出现改善了上述的两个问题。总的说来,就是控制了析取元素的**长度**与**顺序**。
\\
\\
我们还注意到极小项记做 $M_i$。这里的下标 $i$ 也是有含义的:
* 极小项中的每一个命题单元,都可以表示成其自身 $p_x$ 或者其自身的否定 $¬p_x$。
* 因此,如果命题公式由 $n$ 个命题变元组成,那么我们可以总共得到 $2^n$ 个极小项。
* 而 $i$,它的**二进制**就用来表示每一个命题变元是其自身 $p_x$,还是其自身的否定 $¬p_x$。如果是其自身(正文字),那么在该命题变元所处的位置上,值为 $1$;反之,值为 $0$。
具体的例子如下图:
\\
\\
/*证明思路:如果能用 ↓ 表示已知功能完备集中的每一个联结词,那么就说明 {↓} 也是完备集*/
¬p╞╡¬(p∨p)╞╡p↓p //用 ↓ 代表 ¬p
p∨q╞╡¬¬(p∨q)╞╡¬(p↓q)╞╡(p↓q)↓(p↓q) //用 ↓ 代表析取
因为 {¬, ∨} 是功能完备集,那么 {↓} 也是功能完备集。
不过反过来,证明某个联结词的集合是不是功能完备集是比较麻烦的,因为没有比较统一的办法。比如如下例子:
* {∧}不是功能完备集,因为不能构成矛盾式。
* ${¬,↔}$ 不是功能完备集,由 ${¬,↔}$ 组成的命题公 式其成真赋值的个数总是偶数,不能表示那些成真赋值个数为奇数的真值函数。
* 某些非功能完备集不能仅用重言式、逻辑等价式和代入、 替换原理推演证明。
====形式系统====
证明:┠PC A→A
第1步:(A→((A→A)→A))→((A→(A→A))→(A→A)) //用(A→A) 替换 B,A 替换 C,再套用公理A2得到
第2步:A→((A→A)→A) //用(A→A) 替换 B,A 替换 C,再套用公理 A1 得到
第3步:(A→(A→A))→(A→A) // 发现第二步得到的推论是第一步推论的前件,由分离规则得到本步骤的推论
第4步:A→(A→A) // 再次使用公理 A1,用 A 分别替换 B 和 C
第5步:A→A //第四步的结论是第三部的前件,由分离规则可得到本步结论,得证。
演绎:{A,B→(A→C)}┠B→C
/*由题可知本题有两个前提*/
前提1:A
前提2:B→(A→C)
/*正式演绎*/
第1步:A→(B→A) // 将 B 替换为 A,使用公理A1
第2步:B→A // :对前提1和第一步使用分离规则
第3步:(B→(A→C))→((B→A)→(B→C)) //对前提2 应用公理 A2
第4步:(B→A)→(B→C) //对前提2和第三步使用分离规则
第5步:B→C //对第二步和第四步使用分离规则,得证。
====三个元定理====
使用 PC 系统的公理和规则来证明一些复杂命题的时候,我们往往需要想方设法的去凑出能证明结论的形式。这样做有时候是非常麻烦的;为此,我们可以总结出一些定理,来帮助我们简化整个命题过程。PC 系统中主要使用的这种类型的定理有三个,我们也称之为三个元定理。
\\
\\
为什么要称作**元**定理?**元**是对英文 //Meta// 的翻译,Meta 的本身意思就是描述事物的事物。比如 Metadata,就是用于描述数据的数据,比如数据的采集者,采集时间等等。因为我们要讨论的这些定理,他们并不是 PC 系统中的定理(没有在 PC系统中证明过的定理),而是用于描述如何证明定理的定理,因此,这三个定理被称为**元定理**。
===演绎定理===
演绎定理的定义如下:
>对任意公式集合 $Γ$ 和公式 $A,B$:
>1. $Γ┠A→B$ 当且仅当 $Γ∪{A}┠B$
>2. 当 $Γ=ø$ 时,$┠A→B$ 当且仅当 ${A}┠B$,或 $A┠B$
从形式上来看,就是把右边蕴涵关系里的 $A$,移到了左边作为前提条件的一部分。
\\
\\
而这个定理用自然语言来描述就是:
* 前提的集合能推导出 $A$ 蕴含 $B$ 的条件是:当且仅当**前提集合**与 $A$ 的**并集**能够推导出 $B$;换句话说,如果 $B$ 可以由 $A$ 演绎而来,那么 $A→B$ 是一定可以证明的。
* 如果前提集合是空集,那么显然 $A┠B$ 可以演绎出 $A→B$ 。
==演绎定理的证明==
必要性:
当 A→B 是定理的时候, 根据分离规则,A 可推出 B。
因此 Γ∪A 也能推出 B。
充分性:
从 Γ∪A┠B 可以得知, B 成立。
将 B 和 A 代入公理 A1,有:B→(A→B)
根据分离规则,有 A→B 成立。
===归谬定理===
归谬定理又称为反证法,其定义如下:
>对任意公式集合 $Γ$ 和公式 $A,B$:
>1. 若 $Γ∪{¬A}┠B,Γ∪{¬A}┠¬B$
>2. 那么 $Γ┠A$
试想一下,如果一组前提能同时推出另一个命题的正反面,那么这组前提里肯定有相互矛盾的命题在里面。那么很显然,如果我们对产生矛盾的某个命题做一个否定,那么这个命题的否定是肯定被前提集合所包含的,也肯定能被前提集合所推出。
===穷举定理===
穷举定理的定义如下:
>对任何公式集合 $Γ$ 和公式 $A,B$
>1. 若 $Γ∪{¬A}┠B,Γ∪{A}┠B$
>2. 那么 $Γ┠B$
穷举定理的意义在于如果一个前提能推出结论,这个前提 的反面也能推出同样的结论,说明结论的成立与此前提是否成立无关。既然无关,那么 $A$ 与前提集合就没有什么关系了,因此可以去掉。
===元定理应用实例===
证明:┠¬¬A→A
第一步:¬¬A→(¬A→¬¬A) //由公理 A1 可得
第二步:{¬¬A,¬A }┠¬¬A //演绎定理
第三步:¬A→(¬¬A→¬A) // 公理A1
第四步:{¬A, ¬¬A} ┠¬A // 演绎定理
第五步:{¬¬A} ┠A //因为第三步和第五步推出的结果自相矛盾,因此利用归谬定理(左边可以想象成{¬¬A}∪{¬A})
第六步:┠¬¬A→A //演绎定理
证明:┠(A→C)→(((B→C)→((¬A→B)→C))
第一步:{¬A→B, B→C, A→C}┠C //演绎定理,将嵌套的前件按顺序移到左边(只是变形)
/*接下来利用穷举定理证明第一步的变形*/
第二步:{¬A→B, B→C, A→C,A}┠C // 往前提集合里添加一个 A,因为有 A→C,那么推出 C是显然的
第三步:{¬A→B, B→C, A→C,¬A}┠C // 往前提集合里添加一个¬A,因为¬A→B, B→C,那么也能推出 C
第四步:{¬A→B, B→C, A→C}┠C //根据穷举定理,{¬A→B, B→C, A→C} ∪¬A 或者 A 都能推出 C,因此这个集合能直接推出 C,得证。
====定理判定问题====
我们判定一个定理是否成立,实际上就是看能否找到该定理之前的证明序列。而我们知道,在形式系统中有三个部分:符号系统、公理、推理规则。通过这三个基本元素进行推演,我们就能得到定理。由于形式系统是符号系统,因此,我们得到的定理实际上就是使用一系列构造规则,通过**有限步的构造**产生的特定字符串。因此可以说,定理在形式系统中的证明过程,就是符号的构造过程;而定理本身在形式系统中的状态,就是一个**字符串**。
\\
\\
明白了以上内容以后,那么判定一个定理是否是某个形式系统中的定理,实际上就是能不能找出这个字符串在该形式系统中的构造过程了。不过有时候,这个过程会很 tricky。我们来看看下面这个有趣的例子:
===GEB / MIU ===
这个例子描述了一个简单的形式系统 //MIU//,来自 GEB 书中。这个 //MIU// 系统的定义如下:
* 符号系统:M、I、U
* 公理(初始字符串):MI
* 推理规则:
* 如果串的最后一位符号是 I,那么在后面加上一个 U 后,该串仍然属于 MIU 系统,即如果xI是定理,那么xIU也是定理。
* 如果串符合Mx,则可以再加上x而生成Mxx,x代表任何 一个由M,I,U组成的串,即如果Mx是定理,那么Mxx也是定理。
* 如果串中出现连续3个I,则可以用U代替III得到新串,即如果xIIIy是定理,那么xUy也是定理
* 如果串中出现UU,则可以将UU删去得到新串,即如果xUUy是定理,那么xy也是定理
看完上述之后,我们有一个问题:能否能判定 MU 是 MIU 形式系统中的定理呢?
\\
\\
结论是 MU 并不属于 MIU 系统。但很遗憾的是,这个结论并不是直接使用 MIU 系统里的公理和规则推出来的。倘若该字符串不属于本形式系统,我们肯定无法在有限步骤内找到这个字符串的。这样就很尴尬了;你也不能证明它存在,也不能证明它不存在。幸好聪明的数学家们提出了另外一个方法:**同构**。
===同构===
什么是同构?同构就是构造另外一个形式系统。该形式系统与之前的形式系统结构相同,只是使用了另外的符号来代表。针对于 MIU 系统,人们构造了一个新的形式系统 //310//:即用数字 3 代替 M,用数字 1 代替 I,用 数字 0 代替 U。
\\
\\
经过这么一代替之后,我们发现之前的 MIU 系统,已经被我们改造为一个自然数的系统了。很显然,既然牵涉到自然数,我们就可以使用一些数论的结论来讨论 //310// 的一些性质了。接下来我们接着做一些翻译的工作:
* 公理的翻译: MI 对应 自然数 31
* 规则的翻译:
* 规则1:如果集合中有数以 1 结尾,则添一个 0 也是集合中的数
* 规则2:如果集合中有数以 3 开始,则把 3 后面的数再重复一次添在 末尾也是集合中的数
* 规则3:如果集合中有数包含 111,则把 111 替换成 0 也是集合中的 数
* 规则4:如果集合中有数包含 00,则去掉 00 的数也是集合中的数
那么问题也可以翻译成:30 是不是该集合中的数?
\\
\\
有了以上信息,我们再来分析一下这个问题应该怎么证明:
- 首先我们经过观察发现一个性质://310// 系统中的所有数都不能被 ''3'' 整除。
- 公理:31 不能被 ''3'' 整除
- 通过规则1-4 都无法生成被 ''3'' 整除的数
- 而 30 是能被 ''3'' 整除的
- 因此,30 不属于形式系统 //310//
既然证明了 30 不属于系统 //310//,那么很显然,MU 也是不属于 MI 的了。
===定理判定的总结===
可以看到的是,如果仅通过形式系统本身的公理 \ 规则,是很难(或者说不可能)在有限的步骤内判定一个命题公式是否是该形式系统内的定理的;PC 系统也是如此。而**同构**的方式可以很好的解决这个问题。 PC 系统本身也具有自己的同构系统:**真值函数运算系统**。因此,判定 PC 系统中的命题公式是否为定理就非常简单了:**我们只需要用真值表判断命题公式对应的真值函数是否是重言式,就可以判断该命题公式是否是 PC 中的定理。** 而利用真值表计算代替使用PC系统自身元素推演,就像是利用数论解决MIU系统的难题一样,有一个最大的优势:前者的计算都是可以在**有限步骤内完成**的。
====参考与扩展====
* [[http://www.lai18.com/content/5739725.html|范式和命题逻辑推理理论]]
* [[https://github.com/mebusy/notes/blob/master/dev_notes/DiscreteMathematics_week2.md#7e1c75481dcf092f6d461dfeae1d31a4|mebusy_notes]]
* [[http://qinqianshan.com/propositional-logic-and-formal-system/|数理逻辑-命题逻辑及形式系统]]
* [[http://blog.sina.com.cn/s/blog_5e1e1ce70100cixy.html|极小项”和“极大项”的概念]]
* [[http://www.icourses.cn/jpk/changeforVideo.action?resId=695955&courseId=6106|命题逻辑-极小项与极大项]]