[音乐] 嗨,你好。
那么刚才上一节我们
看了一下,就是如何在PC当中证明定理和进行演绎的推理
那么你肯定会发现呢,这个过程 要去想方设法的去
从三个公理出发,然后去凑它的前件啊 凑它的后件,然后再用单一的这个分离规则,是不是
这个过程呢,特别的复杂,或者说,这个过程
特别的曲折,对吧,当然了,我们接下来呢,来介绍一些方法
能够使得这个证明的过程会更加的顺畅一些
那么这里呢,就介绍的是三个元定理 你可能会觉得,这个词汇很陌生,什么叫元定理
我们说这个元呢,就是meta,比如说我们说,经常
说什么数据就是data,或者是元数据呢,它叫meta data
那么所谓的元,就是关于某事的某 事,比如说元数据,它就是关于数据的一些描述的数据
那我们这个定理,这个元定理,实际上它们之间的关系也是这样的
就说我们接下来要讨论的这三个定理 实际上它并不是PC当中的定理,因为我们知道
所谓PC当中的定理,它是一个命题公式,而且呢,它是需要
经过证明的,就是有一个序列,来进行证明的这些
命题公式才能够称作为定理,而我们这,介绍的这个三个
元定理呢,它实际上是关于定理证明的一些定理 那当然,关于定理的定理,所以它就叫元定理
好,说清楚了这些概念之后呢,我们来看看这三个定理,这三个定理呢
首先第一个,我们来看,演绎定理,演绎定理
那么演绎定理是这样的,它说对于任何的公式集合
Γ和公式的A,B,这两个公式 那么它们会有这样的关系,Γ推出A蕴含B
当且仅当,当且仅当呢就是等价的意思,当且仅当 Γ并集,这个符号我们还没有
接触过,但是可能你们在中学的时候会有见到过 那么这是一个并集的意思,也就是说Γ呢
再加上,它Γ本身是一个公式序列,再加上A 它能够推导出B,能够导出B,能推出B
从这个形式上来看 无非就是把A蕴含B,把它这个前件,挪到了推出符号的左边
挪到推出符号的左边,那么这个呢,就是所谓的演绎定理
也就是说它可以把前件放在左边,也可以呢,从Γ
的公式,这个集合,从左边这个集合里头,随便的取出一个公式来
当作前件,放到右边去,当作右边公式的前件,然后挪到
推出符号的右边,这就是演绎这个元定理
它的内容,那当然,特别的,当如果Γ本身就是一个空集的时候
那么,也就是A蕴含B是一个定理,当且仅当呢 A能够推出B,当且仅当A能够演绎出B
这样,那这个呢,显然也是把A这个前件呢 挪到了推出符号的左边,那从证明变成了演绎
那反过来呢,也可以把演绎变成证明,当然我们可以
不太严格的证明一下这个演绎定理,而我们首先证明这个必要性
也就是说,当这个A蕴含B的时候 A蕴含B的时候,它A蕴含B是定理的时候
它能够,意味着A是能够导出B的
这必要性呢,因为我们首先有了这个A蕴含B作为定理
那么再加上一个A,再加上一个A 那这样呢,按照这个分离规则就可以得到B了
就可以得到B,那么另外,在反过来方向,也就是说如果由A导出B的话
A推出B,那么A蕴含B呢,它就是定理,这个呢,不太
明显,当然我们可以这样来试着证明一下
从左边,从右边来看,我们已经通过A
演绎出B,对吧,那这样呢,在这个演绎序列的时候已经有了B了 然后呢,我们有一个公理A1,就是B蕴含A蕴含B
BAB这样的形式,那这样BAB呢,它的前列呢B 根据这个分离规则,我们就可以得到A蕴含B,当然严格来说呢,这
个A蕴含B呢,它并不是完整的一个定理,而是呢,它是依赖于
这个A的,是由A来推出A蕴含B的 当然,我们因为不太严格嘛,我们可以看到,不管是
A是真,还是说A是假,实际上呢 它都不会影响到A蕴含B的成立,所以从这个角度上来说
是可以把A这个前提给去掉的,也就是,A蕴含B呢,它确实 是一个定理,嗯。
第二个呢,我们来看看,叫作 归谬定理,归谬定理呢就是我们经常用的,所谓的反证法
它也是对于任何的集合,公式集合Γ和公式A,B来说 如果说Γ加上
Γ这个公式集合加上非A,能够推出B
然后,再加上非A呢,能够推出非B,也就是说它
既能够演绎出B,又能够演绎出B的反面 那这个呢,最后的归谬定理的结论是说
那么Γ呢,是可以推出A的,这个推出A,就是非A的反面推出A
那么这个归谬定理的意义就在于说 如果我们同一组的前提,能够推出
相互矛盾的结果,这的相互矛盾就是说它既推出了B 又推出了非B,那它当然是相互矛盾
那么这个说明什么呢,说明这组前提之间 它相互是不一致的,相互不一致,它内部会有自相矛盾
那么既然内部自相矛盾,也就意味着说总有一些前提是其余前提的一个对立面 那既然是对立面,实际上我们就可以把
这个左边这一堆公式里头的任何一个公式 拿出来,然后把它做一个否定,放在右边
那么就可以,这个呢就意味着,它们相互呢是对立面,这样的一个意思
那么这个呢就是归谬定理。
第三呢,我们来看看,这个穷举定理 穷举定理呢,就是分情况证明了,对于任何的公式集合Γ和公式A,B
那么如果说,Γ加上非A能够推出B Γ加上A也一样还是推出B的话
那么就是Γ呢,就可以不依据A,它 就说A成立也好,A不成立也好,它总是能够推出B的
所以呢,就可以把A给它去掉,那么就是Γ 能够推出B。
那么这个呢,穷举定理的意义 就在于说,如果说一个前提能够推出结论
而这个前提的反面,再加上这个前提的反面,也能够推出同样的结论的话
那么这就说明,这个结论的成立,跟这个前提是不是成立,是无关的
那既然无关,就可以把它从前提公式集合里头给它去掉
所以这呢,就把A和非A,A呢就可以去掉,就可以去掉,就剩下说
单单与跟用其余的公式,就Γ 这个公式集合呢,就单单,就可以推导出B了,这就是穷举定理
那既然我们说这个元定理呢,能够简化这方面的证明
就是定理证明,我们来看看两个例子,第一个例子呢,就是
我们要证明非非A蕴含A,它是一个定理
当然如果我们不看这个形式,只是把这个非非,我们知道两个非呢
它应该还是原来那个,那么实际上跟我们前面证明的那个定理,A 蕴含A是一样的,对吧,但是呢,这个形式还在这的话,那我们来
看看如何去证明,而且呢,是用元定理的方式来
简化这个证明的过程,那首先呢,我们还是引用公理A1
就是非非A,然后非A,然后呢非非A,这就是ABA这样的形式
好,我们注意中间的这个非A 那么由这个演绎定理,我们用两次的演绎定理
因为这里有两个那个蕴含的符号 然后我们就可以,第一呢,就把这个非非A挪到这个导
出,推出式的这个左边,然后第二次呢,再把非A 挪到这个推出式的左边,这样呢,就会有
Γ就等于非非A和非A,能够推出非非A
那么我们再用一次公理A1,就是这时候呢,这个ABA呢就换成了
非A,然后非非A,再非A这样的形式,那么再用演绎定理
我们就可以得到,也是用两次,第一次呢把非A挪过去,第二次把非非A挪过去
那这样呢,这个推出式的这个右边,就只有这个非A了 那么当然这个左边的这个Γ的这个公式
它既然是一个集合,那么跟顺序是无关的,我们可以把这个顺序给 它倒一下,把那个非非A呢放到非A的前面,这个主要呢,是为了
要符合我们的这个公式的形式,要符合这个形式 那这样呢,我们就得到了两个这个推导式
第一个呢是,非非A和非A能够推出非非A 第二个呢是,非非A和非A呢,能够推出非A
这个,两个都是没问题的,但是我们仔细的观察它的右边 它们的左边都是一样的,但是右边呢差一个非
也就是说,它们这两个结论,它是自相矛盾的
那么既然自相矛盾,那么我们就可以引用这个 归谬定理,那归谬定理呢,就是把这个原来的这个结论
非非A和非A去掉,而从这个左边的这两个公式里头,挑出一个来
把它否定一下,放在右边,那么既然放 在右边呢,我们就把这个标注成蓝色的这个非A
否定一下,那就是两次的非,那就是还是原来的A 所以呢,就得到了非非A能够推出A
那么最后呢,再用演绎定理,把推出式左边的这个非非A挪到右边来
那么就有非非A蕴含A,那这样呢,我们就完成了我们
定理的证明,当然这个整个过程,我们看好像
没有什么太大的建设性啊 都是在玩这个字符串变换的游戏
那当然或许会在形式系统里头,很多事情可能都是这样的 你只要把这个字符串按照它的这个形式
一步一步的去变换,最后能够得到这个结果
我们来看看,一个更难一些的一个元定理,一个定理的证明
这个呢是,AC,然后BC,然后呢非AB 然后C,非AB,然后C
那么我们根据这个演绎定理,那我们也是 把这个三个嵌套的,这个三个前件,给它
一个一个挪到左边,那么这样呢,这个左边的 公式集合Γ就会有了A蕴含C,然后B蕴含C
然后呢,非A蕴含B这三个公式,然后右边呢,只剩下C了,只剩下C
那我们就,现在呢我们因为要,需要用这个穷举定理
那好,我们就往这个左边加一些公式,左边加一些公式
那么加什么呢,我们把它加一个A进去
左边加一个A呢,那很显然,有A,然后呢,又有这个A蕴含C
那,当然,这个C呢,它 当然就可以蕴含C了,也就是说我们不需要B蕴含C和非A蕴含B这个两个公式
就单凭着A蕴含C和A这两个公式 它就能够推出C,因为它就是一个分离原则,对吧,这是,所以呢
我们说它是很显然的,那既然是穷举定理,我们就要
往里头加一个非A来试试看,那么加了非A
然后我们知道,如果有非A,有这个非A蕴含B 那么我们就会有B,那么同时呢,又有B蕴含C
那么我们就会有C了,所以我们说加了一个非A进去,那么它蕴含C呢
能够推出C这是容易证明的,当然很容易证明 那么这样呢,我们就有了这个穷举定理的先决条件
既然它公式集合加上A能够导出C 加上非A呢,也可以导出C,那这样,那么
它们的这个成立就跟A是无关的,那既然无关,就还是Γ
能够导出C,这个Γ呢就是我们刚才所说的那三个公式,那三个公式 那么根据穷举定理呢,这个事就得到了证明
那么既然得到了证明了,那么很好,我们就可以 按照原来的那个方式,来进行
我们一步一步的,再把每一个公式呢,逐个的挪到右边
挪到右边,那最后呢,又能够得到我们所需要证明的这个公式 所以这样呢,就完成了定理的证明
那么你看看,是不是用了元定理,这个定理的证明和演绎 的过程就简单了很多,而且呢,也非常符合
我们的推理的这个习惯,对吧