应用这些变形于第三个例子的表达式CpCNqCNCqpr与CqCNCqpr我们得到:(α)CpCNqCNCqpr~CpCNCqpCNqr由Ⅵ;CpCNCqpCNqr~CNCqpCpCNqr由Ⅴ;CNCqpCpCNqr~CqpCNpCpCNqr由Ⅲ;CqpCNpCqCNqr~CNqCNpCpCNqr,CpCNpCpCNqr由Ⅳ。
(β)CqCNCqpr~CNCqpCqr由Ⅴ;CNCqpCqr~CqpCNpCqr由Ⅲ;CqpCNpCqr~CNqCNpCqr,CpCNpCqr由Ⅳ。
这样CCpqCqpp化归为四个初等表达式:CNqCNpCpCCNqr,CpCNpCpCNqr,CNqCNpCqr与CpCNpCqr。
变形Ⅶ用于复杂前件出现在第四个位置或者更远的地方的所有那些情况。
这个变形允许我们减少前件的数目;事实上,NCpNq与Kpq的意思是一样的,并且S12与S13相应地都是输入定律与输出定律的另外的形式。
现在CNCαNβγ,像CKαβγ一样,只有一个前件,而其等值的表达式CαCβγ有两个前件。
所以,如果一个复杂的表达式出现于第四个位置,如δ在CαCβCγCδ∈中那样,我们相继应用Ⅶ和Ⅵ能够把它移至
-- 175
32。化归为初等表达式A 361
第三个位置:
CαCβCγCδ∈~CNCαNCγCδ∈由Ⅶ;
CNCαNβCγCδ∈~CNCαNβCδCγ∈由Ⅵ。
从这个最后的表达式,我们由Ⅶ的逆向的应用(the
ConCverse
aplication)得到公式:
CNCαNβCδCγ∈~CαCβCδCγ∈由Ⅶ。
现在用Ⅵ和Ⅴ就易于将δ带到第一个位置:CαCβCδCγ∈~CαCδCβCγ∈由Ⅵ,CαCβCδCγ∈~CαCδCβCγ∈由Ⅴ。
重复地在两个方向应用变形Ⅶ我们能够把任何前件从第n个位置移到第一个位置,如果它是复杂的,就用Ⅱ、Ⅲ与Ⅳ使之变形为一个简单表达式。
定理(TB)
的证明就这样完成了。
现在容易表明这个定理推出对于演绎理论C—N系统的判定的证明。
如果一个给定的表达式α已经被化归为若干初等表达式,而所有这些初等表达式都是真的,亦即,如果在它们的诸前件中有两个P与Np型的表达式,那么α就是一个断定命题并必须加以断定。
另一方面,如果α已经化归成的初等表达式中,至少有一个表达式在其中没有两个前件是P与Np型的,那么α必须被排斥。
在第一种情况下,我们能用断定命题S1—S13来证明。
在第二种情况下,我们能够反驳它,除了用上面的断定命题外,还得加上两条新的:S14。
CpCpqS15。
NCp,以及排斥的公理:
-- 176
461第五章 判定问题
PS16。
P。
用两个例子来把这一点说清楚。
第一个例子:断定命题CpCpqq的证明。
这个断定命题必须首先化归为初等表达式。
这是由以下的分析(L)作出的:
CpCpq~CNCpCpqr由Ⅰ;
CNCpCpqr~CpCNCpqr由Ⅲ;
CpCNCpqr~CNCpqCpr由Ⅴ;
CNCpqCpr~CpqCNqCpr由Ⅲ;
CpqCNqCpr~CNpCNqCpr,CqCNqCpr由Ⅳ。
CpCpqq化归成的初等表达式是CNpCNqCpr与CqCNCqCpr。
像所有曾应用过变形Ⅰ的表达式一样,这两个都有一个不在前件中出现的变项作为最后一个词项。
这样的表达式只有在它们有两个前件是P与Np型的条件下,才能是真的,并且这类的任何表达式都能用变形Ⅴ,Ⅵ与Ⅶ化归为S1的一个代入式,一个断定命题的证明总必须由此开始。
这里就是所需要的推演:
S1。
qCNqr×(1)
](1)CpCNpCNqr
S10。
qNp,rCNqr×C(1)—(2)
](2)CNpCpCNqr
S1。
pNp,qp,rNq,sr×C(2)—(3)
](3)CNpCNqCpr
S1。
pq,qCpr×(4)
](4)CqCNqCpr。
-- 177
32。化归为初等表达式A 561
在(3)和(4)之中已得到了与我们的分析(L)之末达到的相同的初等表达式,现在我们用这些相继的变形所依靠的那些断定命题从它们进到其左方的等值式,这样,一步一步地,借助于S9,S6,S10与S2,我们得到我们原来的断定命题:
S9。
rCNqCpr×C(3)—C(4)—(5)
](5)CCpqCNqCpr
S6。
pCpq,rCpr×C(5)—(6)
](6)CNCpqCpr
S10。
pNCpq,qp×C(6)—(7)
](7)CpCNCpqr
S6。
qCCpq×C(7)—(8)
](8)CNCpCpqr(8)
rCpCpq×(9)
](9)CNCpCpqCpCpq
S2。
pCpCpq×C(9)—(10)
](10)CpCpq。
凭借这种方式,我们能够证明任何我们想要证明的断定命题。
第二个例子:表达式CCNpqq的反驳。
我们首先在以下分析的基础上把这个表达式化归为初等表达式:CNpq~CNCNpqr由Ⅰ;CNCNpqr~CNpqCNqr由Ⅲ;CNpqCNqr~CNpCNqr,CqCNqr由Ⅳ;CNpCNqr~CpCNqr由Ⅱ。
-- 178
61第五章 判定问题
表达式CCNpqq就这样化归为两个初等表达式,CqCNqr与CpCNqr,其中第一个是一个断定命题,但第二个不是真的,因为它没有两个p与Np型的前件。
所以,导致这个不真的后果的表达式CCNpqq必须加以排斥。
我们根据给定的变形相继地应用断定命题S1,S5,S7与S3来从头开始这一反驳:
S1。
pCCNpq,qr×(1)
] ](1)CCNpqCNCNpqr
S5。
pCNpq×(12)
](12)CCNCNpqrCNpqCNqr
S7。
pNp,rCNqr×(13)
](13)CCNpqCNqrCNpCNqr
S3。
qCNqr×(14)
](14)CCNpCNqrCpCNqr。
现在我们必须反驳表达式CpCNqr;为此目的我们需要新的断定命题S14与S15以及排斥的公理。
S14。
pNNCp,qp×CS15—(15)
] ](15)CCNCp(15)×C(16)—S16c(P16)CNCp
S14。
pCpCNpq,qCNCp×CS1—(17)
](17)CCpCNpqCNCpCNCp(17)×C(P18)—(P16)
(P18)CCpCNpqCNCp(P18)×(P19)pCpCNpq,qNCp,rp](P19)CpCNqr
-- 179
32。