一阶逻辑定理证明

发布 2019-06-19 04:08:15 阅读 3125

令a是pl的公式,x在a中自由出现:

101,├xa(x)ya(y)

101 ├xa(x)ya(y)

102,├xa(x)xa(x)

103,├xa(x)xa(x)

104,├xa(x)xa(x)

105,├xa(x)xa(x)

令a,b是pl的公式,x在a,b中自由出现:

106,├xya(x,y)y xa(x,y)107,├xya(x,y)yxa(x,y)108,├xya(x,y)yxa(x,y);反之不成立。

令a,b是pl的公式,x在a,b中自由出现:

109,├x(a∧b)xa∧x b

110,├x(ab)xax b

111,├x(a→b)→(xa→x b),反之不成立。

112,├x(ab)→(xax b),反之不成立。

113,├(xa∨x b)→x(a∨b)反之不成立。

114,├x(a∧b)xa∧x b,反之不成立。

令a,b是pl的公式,x在b中自由出现并且在a中非自由出现,则有:

115,├x(a∨b)a∨x b

116,├x(a∨b)a∨x b

117,├x(a∧b)a∧x b

118,├x(a∧b)a∧x b

119,├x(a→b)(a→x b)

120,├x(a→b)(a→x b)

121,├x(b→a)(x b→a)

122,├x( b→a)xb→a

123,├x(a→a)

124,├x(a∨a)

125,├x(a∧a)

证明102 :├xa(x)xa(x)

xap xap

a(apxap

a(aa(a) ⑶r

xa6xa∧xa (1)(7

xa∧ xa (2),(3)―(8

xa2)—(9

xap a(ap,a要符号条件。

xap(12)+

xa11)r

a(a12)—(14)—

xa(x/a15)a要符合条件。

xa(x)xa(x) (1)—(10),(11)—(16)+证明103:├xa(x)xa(x)

xa(xp

a(apxa(xp

a(aa(ar

xa(x xa(x

xa(xp

xa(xp

a(ap( a不出现在(8)(9)(14)中。

xa(x10)+

xa(x9)r

a(a10)—(12)+

xa(x13)+

xa(x8)r

xa(x9)—(15)—

xa(x)xa(x) (1)—(16)+

证明104:├xa(x)xa(x)

xa(xp

xa(xp

a(ap(a符合条件)

xa(xpa(a

a(arxa(x

xa(x xa(xr

xa(x xa(xp

a(ap(a符合条件)

xa(x12)+

xa(x11)r

a(a12)—(14)+(a符合条件)

xa(x13)+

xa(x)xa(x1)—(10),(11)—(16)+证明105:├xa(x)xa(x)

xa(xp

a(apxa(xp

a(a3)—

a(a2) xa(x3)—(5)+

xa(x1),(2)—(6)—

xa(xp

xapa(ap(a符合条件)

xa(x/a10)+

xa9)r a(a10)—(12)—

xa(x/a13)+(a符合条件)

xa(x8)r

xa9)—(15)—

xa(x)xa(x) (1)—(7),(8)—(16) +下面的证明不再写出右面的依据,可以作为练习自己填入。

证明106:├xya(x,y)y xa(x,y)xya ya(a,y)

a(a,b)

x a(x,b)

y xa(x,y)

y xa(x,y)

xa(x,b)

a(a,b)

ya(a,y)

xya(x,y)

xya(x,y)y xa(x,y)

证明107:├xya(x,y)yxa(x,y)xya(x,y)

ya(a,y)

a(a,b)

xa(x,b)

y xa(x,y)

y xa(x,y)

y xa(x,y)

yxa(x,y)

xa(x,b)

a(a,b)

ya(a,y)

y xa(x,y)

yxa(x,y)

yxa(x,y)

xya(x,y)y xa(x,y)

证明108:├xya(x,y)yxa(x,y);反之不成立。

xya(x,y)

ya(a,y)

a(a,b)

xa(x,b)

yxa(x,y)

yxa(x,y)

xya(x,y)yxa(x,y)

反之不成立,是因为“所有的y同有的x之间有关系a的那个x”,不一定就是“同所有的y有关系a的那个x”。我们可以用一个解释证明yxa(x,y)xya(x,y)是不成立的。令y是偶数,x是质数,a是y能x整除,yxa(x,y)的意思是“所有的偶数都能被某个质数整除”因此是真的命题,我们可以找到这个质数,即2。

xya(x,y)的意思是:“有一个质数,它能被所有的偶数整除”这显然是假命题。

证明109:├x(a∧b)xa∧x b(自证)证明110:├x(ab)xax b

x(ab)

a(a)b(a)