項(xiàng)的代入定理

趙正波

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

項(xiàng)的代入定理

趙正波

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

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

一階語言;一階謂詞演算;項(xiàng);賦值

0 引言

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

1 一階語言的賦值與滿足

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

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

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

(i)變?cè)蚅中的個(gè)體常元是項(xiàng);

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

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

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

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

定義5 設(shè)L是一階語言，公式A(xi)是含有變?cè)獂i的公式，t是一個(gè)項(xiàng).如果:

(i)xi不是A(xi)中的自由變?cè)?

或

(ii)xi是A(xi)中的自由變?cè)襱中的變?cè)贏(t)中都是自由變?cè)?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)令w(xk)=w/(xk)(當(dāng)k≠i，k≠j時(shí))，w(xj)=w/(xj)，w(xi)=ν(xi)

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

證明 因?yàn)閣(xk)=w/(xk)(當(dāng)k≠i，k≠j時(shí))，w(xj)=w/(xj)，所以w與w/是i－等價(jià)的賦值;

w(xk)=w/(xk)=ν/(xk)=ν(xk)(當(dāng)k≠i，k≠j時(shí))，w(xi)=ν(xi)，w與ν是j－等價(jià)的賦值;

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

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

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

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

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

(4)令w/(xk)=w(xk)(當(dāng)k≠i，k≠j時(shí))，w/(xj)=w(xj)，w/(xi)=ν/(xi)

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

證明 因?yàn)閣/(xk)=w(xk)(當(dāng)k≠i，k≠j時(shí))，w/(xj)=w(xj)，所以w/是與wi－等價(jià)的賦值;

w/(xk)=w(xk)=ν(xk)=ν/(xk)(當(dāng)k≠i，k≠j時(shí))，w/(xi)=ν/(xi)所以w/與ν/是j－等價(jià)的賦值;

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

3 項(xiàng)的代入定理

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

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

事實(shí)上，我們有

(1)設(shè)u是L中的變?cè)騻€(gè)體常元，u/是在u中用t取代xi所得之項(xiàng)，則

ⅰ)若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)式.

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

第三步，考慮一般公式變?cè)拇鷵Q問題，用歸納法證明.

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

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

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

當(dāng)且僅當(dāng)ν滿足A(t).

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

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

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

當(dāng)且僅當(dāng)ν滿足A(t).

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

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

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

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

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

這就證明了項(xiàng)的代入定理.對(duì)于項(xiàng)的代入定理，直接有下面推論:

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

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

4 結(jié)語

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

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

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

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

［4］趙正波.模糊有效公式［J］.渭南師范學(xué)院學(xué)報(bào)，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)典邏輯.