項的代入定理

趙正波

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714000)

項的代入定理

趙正波

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714000)

引入兩個引理分析了一階語言中賦值的性質(zhì)，簡化了項的代入定理的證明，新的證明過程更能反映一階語言的結(jié)構(gòu)和等價的賦值之間的關(guān)系.

一階語言;一階謂詞演算;項;賦值

0 引言

一階謂詞邏輯演算是比命題邏輯演算更廣泛的一種邏輯系統(tǒng).文獻［1］對命題演算和一階謂詞演算都做了系統(tǒng)的論述，它們都是經(jīng)典數(shù)理邏輯的重要組成部分.近年來，模糊命題邏輯得到迅速發(fā)展，文獻［1］也對多值邏輯演算理論作了系統(tǒng)的論述，但是相應(yīng)的模糊謂詞邏輯的論述卻比較少，我們對項的代入定理的證明進行改進，有利于我們把項的代入定理引入到模糊謂詞邏輯中.另外一階謂詞本身也有許多實際應(yīng)用［2－3］，文獻［4］介紹了一階模糊謂詞系統(tǒng)的相關(guān)基本概念.

1 一階語言的賦值與滿足

下面我們先介紹一階語言及其相關(guān)的項、合式公式、解釋、賦值和滿足等概念.本文中不加定義的概念參閱文獻［1］.

定義1 一階語言L含有以下符號:(i)某些變元符號:xi;(ii)某些個體常元:ai;(iii)某些謂詞符號: A; (iv)某些函數(shù)符號:f;(v)連接詞:?與→;(vi)標點符號:(，)，’;(vii)量詞符號:.

定義2 設(shè)L是一階語言，則L中的項(term)定義如下:

(i)變元和L中的個體常元是項;

(iii)L中的項均由以上兩種方式生成.

(i)原子公式均為合式公式;

(iii)合式公式均由以上兩種方式生成.

合式公式也簡稱公式，L中的所有合式公式記為F(L).

定義5 設(shè)L是一階語言，公式A(xi)是含有變元xi的公式，t是一個項.如果:

(i)xi不是A(xi)中的自由變元;

或

(ii)xi是A(xi)中的自由變元，且t中的變元在A(t)中都是自由變元，

則稱t關(guān)于A(xi)中的xi是自由的.

定義6 設(shè)L是一階語言，L的解釋I的組成如下:

(i)一個非空集DI，叫解釋I的論域;

(ii)DI中的一組與L中的個體常元a1，a2，…相對應(yīng)的特定元

(iii)DI上的一組與L中的謂詞符號 {A}相對應(yīng)的關(guān)系，這里，即是DI上的n元關(guān)系;

(iv)DI上的一組與L中的函數(shù)符號 {f}相對應(yīng)的函數(shù)，這里是DI上的n元函數(shù).

一階語言L在有了解釋I之后，L中的個體常元、函數(shù)符號、項、謂詞符號等就有了在DI中的明確涵義.L中的公式就成為論域DI中關(guān)于它的所有變元的一種論斷，這個論斷正確與否取決于所涉及的變元在DI中被怎樣賦值而定，下面將給出賦值與滿足的一些概念.

定義7 設(shè)L是一階語言，I是L的一個解釋.L在I中的賦值ν是從L的項集T到DI的一個映射ν: T→DI，滿足條件:

(i)ν(ai)=，這里ai是L中的個體常元;

定義9 設(shè)L是一階語言，I是L的一個解釋，ν是L在I中的一個賦值，A是L中的一個公式.ν滿足A可以歸納地定義如下:

(ii)若A是?B，則ν滿足A是指ν不滿足B;

(iii)若A是B→C，則ν滿足A是指ν滿足C或ν不滿足B;

2 賦值的等價關(guān)系的兩個引理

引理1 設(shè)L是一階語言，I是L的一個解釋，ν，ν/，w，w/是L在I中的賦值，若

(1)t中不含xj的項(i≠j);

(2)ν/與ν是i－等價的賦值，并且ν/(xi)=v(t);

(3)w/與ν/是j－等價的;

(4)令w(xk)=w/(xk)(當k≠i，k≠j時)，w(xj)=w/(xj)，w(xi)=ν(xi)

則w與w/是i－等價的賦值，與ν是j－等價的賦值，并且w/(xi)=w(t).

證明 因為w(xk)=w/(xk)(當k≠i，k≠j時)，w(xj)=w/(xj)，所以w與w/是i－等價的賦值;

w(xk)=w/(xk)=ν/(xk)=ν(xk)(當k≠i，k≠j時)，w(xi)=ν(xi)，w與ν是j－等價的賦值;

另外，w/(xi)=ν/(xi)=ν(t)=w(t).

引理2 設(shè)L是一階語言，I是L的一個解釋，ν，ν/，w，w/是L在I中的賦值，若

(1)t中不含xj的項(i≠j);

(2)v/與ν是i－等價的，并且ν/(xi)=ν(t);

(3)w與ν是j－等價的賦值;

(4)令w/(xk)=w(xk)(當k≠i，k≠j時)，w/(xj)=w(xj)，w/(xi)=ν/(xi)

則w/與w是i－等價的賦值，與ν/是j－等價的賦值，且w/(xi)=w(t).

證明 因為w/(xk)=w(xk)(當k≠i，k≠j時)，w/(xj)=w(xj)，所以w/是與wi－等價的賦值;

w/(xk)=w(xk)=ν(xk)=ν/(xk)(當k≠i，k≠j時)，w/(xi)=ν/(xi)所以w/與ν/是j－等價的賦值;

另外，w/(xi)=ν/(xi)=ν(t)=w(t).

3 項的代入定理

定理1 設(shè)L是一階語言，I是L的一個解釋，A(xi)∈F(L)，xi是A(xi)中的自由變元.設(shè)t是關(guān)于A(xi)中的xi自由的項，ν是L在I中的賦值，ν/與v是i－等價的賦值且ν/(xi)=ν(t)，則ν滿足A(t)當且僅當ν/滿足A(xi).

證明 第一步，先考慮關(guān)于項中變元的代換問題.設(shè)u是L中的含xi的項，u/是在u中用t取代xi所得之項，則

事實上，我們有

(1)設(shè)u是L中的變元或個體常元，u/是在u中用t取代xi所得之項，則

ⅰ)若u=xi，則u/=t，則ν(u/)=v(t)=ν/(xi)=ν/(u);

ⅱ)若u=xj(j≠i)，則u/=u=xj，則ν(u/)=ν(xj)=ν/(xj)=ν/(u);

ⅲ)若u=ai，則u/=ai，則ν(u/)=ν(u)=

即(1)成立.

這就證明了(1)式.

第二步，回到公式中變元代換問題.先考慮原子公式.設(shè)A(xi)是A(u1，…，un)，則A(t)是A(u，…，u).設(shè)ν/滿足A(xi)，即(u1，…un)在DI中成立，則由(1)式知(u，…u)在DI中成立，即ν滿足A(t).

第三步，考慮一般公式變元的代換問題，用歸納法證明.

(1)設(shè)A(xi)是?B(xi)，且定理對B(xi)已成立，則

ν/滿足A(xi):當且僅當ν/不滿足B(xi);

當且僅當ν不滿足B(t);

當且僅當ν滿足A(t).

(2)設(shè)A(xi)是B(xi)→C(xi)，且定理對B(xi)和C(xi)已成立，則

ν/滿足A(xi):當且僅當ν/滿足C(xi)或ν/不滿足B(xi);

當且僅當ν滿足C(t)或ν不滿足B(t);

當且僅當ν滿足A(t).

(3)設(shè)A(xi)是(xj)B(xi)(j≠i)，且定理對B(xi)已成立，因為t是關(guān)于A(xi)(即(xj)B(xi))中的xi自由的項，所以xj不在t中出現(xiàn).

ⅰ)對于與ν/是j－等價的任意賦值w/，我們有賦值w如下:

則有w與w/是i－等價的賦值，與ν是j－等價的賦值，且w/(xi)=w(t)，因而有，若ν滿足A(t)，則w滿足B(t)，w/滿足B(xi)，ν/滿足A(xi);

ⅱ)對于與ν是j－等價的任意賦值w，我們有賦值w/如下:

則有w/與w是i－等價的賦值，與ν/是j－等價的賦值，且w/(xi)=w(t)，因而有，若ν/滿足A(xi)，則w/滿足B(xi);w滿足B(t);ν滿足A(t).

這就證明了項的代入定理.對于項的代入定理，直接有下面推論:

推論 設(shè)L是一階語言，I是L的一個解釋，A(xi)是含有自由變元xi的公式，ν是L在I中的賦值.則

ⅱ)若ν滿足A(c)，c是L中的個體常元，則ν滿足公式(xi)A(xi).

4 結(jié)語

通過引理的引入改進了項的代入定理的反證法部分，證明過程更能反映一階語言的結(jié)構(gòu)，方便我們把項的代入定理引入到模糊謂詞邏輯中，從而對項的代入定理的相關(guān)問題進行進一步討論.

［1］王國俊.數(shù)理邏輯引論與歸結(jié)原理［M］.第2版.北京:科學(xué)出版社，2006.

［2］趙正波.關(guān)于函數(shù)極限及其不等式性質(zhì)的思考［J］.渭南師范學(xué)院學(xué)報，2004，19(5):49－52.

［3］趙正波.數(shù)列構(gòu)造方法在否定命題中的應(yīng)用［J］.渭南師范學(xué)院學(xué)報，2005，20(5):22－25.

［4］趙正波.模糊有效公式［J］.渭南師范學(xué)院學(xué)報，2011，26(10):54－57.

【責(zé)任編輯 牛懷崗】

On Substitution Theorem of Term

ZHAO Zheng-bo
(School of Mathematics and Information Science，Weinan Normal University，Weinan 714000，China)

The relationship of i-equivalence and j-equivalence of valuation predigests the proof of substitution theorem of term.And the proof shows structure of first-order language and the relation among valuations in first-order language.

first-order language;first-order predicate;term;valuation

book=104,ebook=77

O141.1

A

1009—5128(2012)06—0013—04

2012—02—17

趙正波(1966—)，男，陜西華縣人，渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院講師，理學(xué)碩士.研究方向:非經(jīng)典邏輯.