[音乐] 好,欢迎回来,我们接下来呢,来看看一个真实的一个形式系统,
我们把我们前面所学到的这个命题以及重言式它们
之间的这个变化和演算构造成一个形式系统, 那么这个形式系统呢我们就称它为命题演算形式系统。
简称为PC,那么我们照着这个形式系统,刚才提出来的三要素, 来逐渐看这个PC的构成。
首先呢就是PC的符号系统, 那么PC符号系统呢,它先是由一系列的这个符号,单个的符号来构成的,
这些单个的符号呢就包括命题变元,p,q,r s,或者是呢带下标的p1,q1,r1,s1
那么还有呢,命题常元,用t,f 也可以用呢联结词,还有联结词,就是逻辑联结词,
我们呢,在PC当中有两个联结词,就是否定联结词和蕴含联结词,
当然我们注意到呢,它去掉了其他的三个, 也就是双向蕴含,合取,吸取都不见了,但是我们注意到
否定和蕴含实际上是一个功能完备集,
当然它同时也是一个最小功能完备集,还有呢括号,左括号,右括号,
当然,这个符号系统里,就会有高级的成分,
那么这里的高级成分,规定了说,我这些单个的字符如何组合成 更复杂的一个字符串,是合法组合,
那么这个合法组合就是命题公式的定义,这个我们挺熟悉的,就是那个三句话的证明。
第一呢,就是命题变元和命题常元它是命题公式, 第二,如果说A和B是公式的话,那么
非A加上括号,以及呢A蕴含B,加上括号, 那么它也是命题公式,当然我们结合这个优先级
和这个括号省略的约定,也跟前面是一致的,所以我们可以省略掉一些括号。
第三呢只是有限次的使用上面两条规则得到的符号串,
它才能够叫做命题公式,那么这呢就保证了说命题公式都是有限长度的 这个符号串。
第二个呢我们来看看PC的公理, 那么我们在重言式当中选出了三个公理,
那么实际上呢因为A,B,C都是代表任意公式,所以它对应于重言式而言,
它实际上是一个公理的模板,你任意的公式把它 套进去,都可以叫做公理,那么这里当然A1
这个公理呢,就是A蕴含B蕴含C, A2呢,就是A蕴含B蕴含C,蕴含着A蕴含B,
蕴含A蕴含C,这是一个挺复杂的一个公理, 第三呢是非A蕴含非B,那么蕴含着B蕴含A,
这个看来是个逆否命题这样的, 当然它们全都是重言式。
那么第三部分就是PC的推理规则, 推理规则呢,它只有一条,称之为分离规则,
也就是说在证明或者演绎的过程当中,如果你有A, 有A蕴含B这样的模式的话,
你就可以在公式序列的后边写上B, 那么也就是说由A和A蕴含B就推出了B,
这叫做分离规则,这是PC的推理规则。
那么当然,这么样定义的一个命题演算形式系统,
它应该是一个好的系统,那所谓的,什么一个叫好的系统呢?
我们说它具有三个性质,一个叫合理性,一个呢是一致性,
一个呢是完备性,那么这个呢几乎是 可以称得上是最好的系统了。
那么首先我们来看看什么叫做合理性, 合理性是说,如果一个命题公式A,
它是PC当中的一个定理的话,也就是说 A呢,在PC当中,它能够被证明,
也就是它存在一个序列,序列的最后是这个公式A, 也就是说它是PC当中的定理,
被证明的,我们必须要这里要记清楚一个问题, 就是所谓的定理,那么它就是要必须要有一个证明序列
才能够称作为定理,否则是不能够 在形式系统当中不能称作为定理。
那么合理性是说如果一个公式 A,它是PC的定理的话,那么它就一定是一个重言式,
我们知道重言式呢实际上它并不是PC当中的概念,它是逻辑当中的概念,
也就是说只要它是定理,那么它就一定会是一个逻辑真理,
这是合理性证明,那么在演绎当中,
也是一样的,如果A是公式集合Г的演绎结果,也就存在一个演绎序列,
那么呢,A就是Г的逻辑结果,也就是说在 逻辑上,可以合理地推导出A来,由
Г为前提,可以它是Г的一个逻辑结果。
那么这个呢就说明了说PC当中的 定理和演绎结果,也就是存在着一个推导的一个过程,
一个公式序列的话,那么这个定理和演绎 结果都是合乎逻辑的,都是合乎逻辑的。
那么合理性呢,我们
证明起来可能很费事,但是我们可以试图去说明一下这个 合理性,也算是一个不严格的证明吧!
因为首先呢PC当中的公理A1,A2,A3它实际上都 是重言式,也就是说它是逻辑上的重言式,
那么其次呢,PC的这个分离规则,它是所谓的叫做保真的,
所谓的保真,就是说只要是A真, A蕴含B真,总会有B真,那么也就是说它在逻辑当中,
是保真的,那么这样的话, 由公理和分离规则导出来的这些定理,
那么一定也会是重言式,那么由Г和 公理,以及分离规则导出来的公式,那么在Г中的公式
都为真的前提下,那么导出的这个公式,肯定也是一个真, 也是真理。
第二个呢就是 PC的一致性,那么所谓的一致性呢是说
它不会有一个命题公式A,就是PC当中的这个命题公式A A呢本身是一个定理,能够得到证明,
非A也是一个定理,也能得到证明, 也就是说不会有A和非A同时都是定理的这个情况出现,
那么也就是它在逻辑上不会自相矛盾,那么这叫做一致性。
那么这个一致性呢由PC的合理性是很容易来证明的,
也就是说PC的合理性是表示说,只要你是定理,那么它就一定是逻辑真理,
那么我们知道,由这个矛盾律,你不可能A是逻辑真理,那么非A呢也同时是逻辑真理,
这是不会出现的,所以呢PC的这个一致性是可以得到保证。
第三个呢,是PC的所谓的完备性, 完备性就是说,如果公式A它是一个重言式
的话,也就是说,一个公式是逻辑上的真理, 那么A一定是PC当中的定理,
也就是说,A呢在PC当中一定会有一个证明的序列, 来证明它确实是一个定理。
还有呢如果公式A是公式集合Г的逻辑结果的话,
那么A呢一定是Г在PC当中的一个演绎结果, 那么这个证明呢是很难的,我们
可以略过它,我们只知道这个完备性就很好了。
那么这里头完备性是说明说,只要是合乎逻辑的,
它是逻辑真理,这样的命题呢,在PC当中一定能够
被推导出来,也就是说它一定能够被证明出来。
当然你可能会觉得奇怪,难道会存在一些 逻辑的真理在某一些系统当中它永远得不到证明吗?会有这样的
逻辑真理吗?当然这个就是 我们说问题的这个实质所在,要不然
哥德尔他忙了大半天,实际上他就是希望说明这个