用户名:
    密码:
转播到腾讯微博

你的位置:首页 > 逻辑学

张清宇:系统Z中的范式和插入定理
录入: 哲学网编辑部 发表时间: 2013-06-07 点击: 1173 次 我要收藏

系统Z 是我在文〔1〕中建立的经典命题逻辑的一个公理系统。 这系统只用一种初始联结词——广义析舍,而且采用括号记法,因而使得系统的陈述更为直接明了。它的可判定性、可靠性、完全性和独立性等证明也都很简单。系统Z是很有独特之处的, 分离规则和双重否定规则在其中都不成立。
本文将继续这方面的工作。首先,我们提出一种析舍范式,并阐明它跟合取范式和析取范式的联系。其次,我们陈述并证明插入定理。通常插入定理的证明很少或几乎没有直接以公理系统为基础进行的,而我们的证明则是施归纳于系统Z中证明的长度进行的,这是系统Z的独特性带来的一大好处。
本文中的语形和语义方面的基本概念及记号都参照文〔1〕和〔2〕中的用法。
一、析舍范式 我们将称公式〔A[,0],…,A[,n-1]〕为它的直接子公式A[,0]、……、A[,n-1]的析舍,并称这些直接子公式为它的析舍支。析舍式〔A[,0],…,A[,n-1]〕为不可满足的,当且仅当,它的析舍支都是重言式。析舍式〔A[,0],…,A[,n-1]〕为重言式,当且仅当,它的全部析舍支所形成的集合{A[,0],…,A[,n-1]}为不可满足的。当析舍支A[,0]、……、A[,n-1] 都是原子析舍时,我们称公式〔A[,0],…,A[,n-1]〕为析舍范式。为n为0时,析舍范式〔A[,0],…,A[,n-1]〕为公式〔〕;而当n为1时,析舍范式〔A[,0],…,A[,n-1] 〕则为原子析舍的否定。因此,恒假公式和原子析舍的否定都是析舍范式。空析舍恒假。
析舍范式可以显示公式的不可满足性。原子析舍是重言式,当且仅当,它是系统Z的公理;即,它是有〔〕为直接子公式的原子析舍, 或者是有某个命题符及其否定同时为直接子公式的原子析舍。因此,一析舍范式为不可满足的公式与否是极易识别的,只须弄清它的各个析舍支是否以〔〕为直接子公式,或者是否以某个命题符与其否定同时为直接子公式。例如,析取范式〔〔p,q〕,〔p,〔r〕〕,〔〔p〕,〔q〕,r〕〕不是不可满足的,因为它的三个析舍支都不是系统Z的公理;当p、q都真时,该析舍范式为真,所以原公式是可满足的。
令A为公式,如果某个析舍范式B与A等值,则称B为A 的一个析舍范式。给定一个公式A, 我们可以有下述两种方法找出它的一个析舍范式。
方法一是利用A的真值表来找。如果A恒真或恒假,则只须取恒真公式〔〔〕〕或恒假公式〔〕就行。如果A既不恒真又不恒假,则A中必出现有命题符。假定出现在A中的全部命题符为P[,1],……,P[,k], 则A的真值表共有2[k]行,A相应于这2[k]行的值既有真又有假。现在考虑A取值为真的行,设它们共有m行(m≥1), 并从上往下依次编成第1行、……、第m行。对于第j行,j=1,…,m,我们可以配上一个A[,j]如下:
A[,j]=〔P[j][,1],…,P[j][,k]〕;
这里,当 P[,i]在第j行中的值为真时p[j][,i]为p[,i],否则P[j][,i]为〔p[,i]〕。显然,A[,j](j=1,…,m)都是原子析舍。最后,取B为公式〔A[,1],…,A[,m]〕就行。
例如公式〔〔〔〔q,r〕,〔〔q〕,〔r〕〕〕,〔p 〕〕〕(用通常的符号表达,则为
附图
的真值表如下:  q r p 〔〔〔〔q,r〕,〔〔q〕,〔r〕〕〕,〔p〕〕〕
1 1 1  0
1 1 0  1
1 0 1  0
1 0 0  0
0 1 1  0
0 1 0  0
0 0 1  0
0 0 0  1

其中只有两行使原公式为真。易见,A[,1]=〔q,r,〔p〕〕并且A[,2]=〔〔q〕,〔r〕,〔p〕〕。公式〔A[,1],A[,2]〕=〔〔q,r,〔p〕〕,〔〔q〕,〔r〕,〔p〕〕〕为原公式的一个析舍范式。
第二种方法是利用文〔1〕中构作树图来找。首先构作公式A的否定〔A〕的树图。当完成时图中各分枝的顶端都是原子析舍。 当这些原子析舍都是系统Z的公理时,A的否定〔A〕就是系统Z的一个定理,从而是重言式,因此A是恒假公式,公式〔〕就是A的一个析舍范式。当这些原子析舍不全是系统Z的公理时,将其中不是公理的那些析舍起来, 所得到的公式就是A的一个析舍范式。
例如上例中公式的否定〔〔〔〔〔q,r〕,〔〔q〕,〔r〕〕〕,〔p〕〕〕〕的树图如下:
附图
顶端上的原子析舍都不是Z的公理,它们的析舍为〔〔q,r,〔p〕〕,〔〔q〕,〔r〕,〔p〕〕〕,这是原公式〔〔〔〔q,r〕,〔〔q〕,〔r〕〕〕,〔p〕〕〕的一个析舍范式。
我们将称公式〔〕和〔〔〕〕互为对偶,命题符p与其否定〔p〕互为对偶。任一个原子析舍A直接等值于一个析取式A′,这析取式的所有析取支正好是该原子析舍的直接子公式的全部对偶。例如,原子析舍〔〔〕,p,〔p〕〕等值于公式〔〔〔〔〕〕〕,〔〔p〕〕,〔q〕〕,即,〔〔〕〕∨〔p〕∨q。类似地,任一个原子析舍A的否定〔A〕直接就是一个合取式,这合取式的所有合取支正好是该原子析舍的全部直接子公式。例如,原子析舍〔〔〕,p,〔q〕〕的否定〔〔〔〕,p,〔q〕〕〕是〔〕、p、〔q〕的合取。
析舍范式跟通常的合取范式、析取范式的联系是非常密切的。 令A为任意一个公式。从A的一个析舍范式〔A[,0],…,A[,n-1] 〕(这里,诸A[,i]都是原子析舍)可以立即得到A的一个析取范式,因为析舍范式〔A[,0],…,A[,n-1]〕等值于〔〔〔A[,0]〕〕,…,〔〔A[,n-1]〕〕〕,并且由上一段落的论述可知诸〔A[,i] 〕直接就是一个由公式〔〕、命题符、或命题符的否定组成的合取式,从而〔〔〔A[,0] 〕〕,…,〔〔A[,n-1]〕〕〕为A的一个析取范式。类似地, 从否定式〔A〕的一个析舍范式〔A[,0],…,A[,n-1]〕可以立即得到A 的一个合取范式,因为此时A等值于〔〔A[,0],…,A[,n-1]〕〕,并且对小于n的i而言A[,i]等值于一个析取式A′[,i],A′[,i]的全部析取支正好是原子析舍A[,i]的直接子公式的所有对偶,从而〔〔A′[,0],…,A′[,n-1]〕〕为A的一个合取范式。
例如取A为公式〔〔〔〔q,r〕,〔〔q〕,〔r〕〕,〔p〕〕〕,则A的一个析舍范式为〔〔q,r,〔p〕〕,〔〔q〕,
附图
〔A[,ij]〕,…〕,…〕〕,因此A等值于〔…,〔…,〔A[,ij]〕,…,〕…〕,从而等值于析舍范式〔…,〔…,A′[,ij],…〕,…〕,这里A′[,ij]如下确定:
┌〔〕,  当A[,ij]为〔〔〕〕时;
A′[,ij]=< 〔p〕,  当A[,ij]为p时; │ p,   当A[,ij]为〔p〕时; └空符,  当A[,ij]为〔〕时。 附图 二、插入定理 在证明系统Z的插入定理以前, 我们先引进一些记法和定义。 下面,我们将以大写希腊字母

文章的脚注信息由WordPress的wp-posturl插件自动生成


分享到:

标签 :
版权声明:版权归 哲学网:哲学学术门户网站,Philosophy,哲学家,哲学名言大全 所有,转载请注明出处!

转载请保留链接: http://www.zhexue.org/f/logic/4482.html

已有 0 条评论
关于我们 | 图站地图 | 版权声明 | 广告刊例 | 加入团队 | 联系我们 |
哲学网编辑部 未经授权禁止复制或建立镜像,采用Wordpress架构,采用知识共享署名进行许可
官方邮箱:admin#zhexue.org (#换成@)索非制作|优畅优化|阿里云强力驱动
ICP证号:沪 ICP备13018407号
网站加载1.208秒
知识共享许可协议