一階邏輯(數(shù)據(jù)庫)

時間：2022-12-03 06:30:01 | 來源：信息時代

時間：2022-12-03 06:30:01 來源：信息時代

    一階邏輯 : 在命題邏輯基礎(chǔ)上作更為深入與廣泛研究的一門學(xué)科。它研究比命題邏輯更為復(fù)雜的符號邏輯體系及推理規(guī)律。一階邏輯是數(shù)理邏輯中發(fā)展得較為成熟的一個部分,它起源于19世紀(jì),到20世紀(jì)中葉已達(dá)成熟階段,它在為符號語言和推理所建立的形式系統(tǒng)中處于重要和核心地位。
由于謂詞在一階邏輯中的重要性,因此它又稱一階謂詞邏輯或簡稱謂詞邏輯。在該邏輯中量詞僅作用于個體變元,而謂詞不可變,為常值,故稱一階邏輯,而當(dāng)謂詞為可變時,量詞還可作用于謂詞時則稱為二階邏輯,或稱高階邏輯。
一階邏輯在計算機(jī)及數(shù)據(jù)庫領(lǐng)域中具有廣泛、基礎(chǔ)性的作用,它在關(guān)系數(shù)據(jù)模型、謂詞模型的建立中,在演繹數(shù)據(jù)庫、知識庫中以及在多種基礎(chǔ)性應(yīng)用中起著重要的理論指導(dǎo)價值。
1.個體與謂詞
在一階邏輯中進(jìn)一步將原子命題分解成為個體與謂詞兩部分。個體是一階邏輯中基本的組成部分,它可分為個體常元與個體變元,可分別用a,b,c,…及x,y,z,…表示,謂詞刻畫個體的性質(zhì)與關(guān)系。謂詞是與個體緊密關(guān)聯(lián)的,當(dāng)謂詞與一個個體關(guān)聯(lián)時稱為一元謂詞,此時謂詞刻畫個體性質(zhì),當(dāng)謂詞與n個個體關(guān)聯(lián)時稱為n元謂詞,此時它刻畫個體間關(guān)系。謂詞符號一般可用大寫符P,Q,R,…表示,而一元謂詞與n元謂詞則分別可用P(x),P(x₁,x₂,…,x_n)表示,當(dāng)謂詞中的個體變元全部被賦值為個體常元時,此時謂詞必取值為T或F。
2. 量詞與個體域
一階邏輯中的每個個體變元均有一個變化范圍稱個體域,如在謂詞中個體變元對所有個體域中個體均使謂詞為T以及有些個體域中個體謂詞為T是兩個極端不同的概念。因此有必要區(qū)分“所有”與“有些”兩個概念,由于它們具有量上的區(qū)別,因此可稱為量詞,分別用∀x及∃x表示,稱全稱量詞及存在量詞。在量詞符號中的“x”表示量詞所作用的個體變元,稱約束變元,而不受量詞約束的個體變元則稱為自由變元。
3. 函數(shù)
在一階邏輯中個體與個體間有一定關(guān)系,這種關(guān)系稱函數(shù),函數(shù)有一元、二元及n元之分,它們分別可用f(x),f(x,y)及f(x₁,x₂,…,x_n)表示,在函數(shù)中個體經(jīng)函數(shù)作用后所得到的仍為個體,所以它是個體到個體的映射。
4. 公式
一階邏輯的公式是由個體、謂詞、量詞及函數(shù)所組成,其組成規(guī)則如下:
在謂詞邏輯公式中所使用的符號共有七種:
(1)個體常量符: a,b,c,…。
(2)個體變量符:x,y,z,…。
(3)函數(shù)符:f,g,h,…。
(4)謂詞符: F,G,H,…。
(5)聯(lián)結(jié)詞符: , ∧, ∨,→, ↔。
(6)量詞符: ∀, ∃。
(7)括號: (,)。
一個謂詞邏輯公式是由上面七種符號按一定規(guī)則所組成的符號串。
5.項
(1)個體常量是項。
(2)個體變量是項。
(3)設(shè)f為n元函數(shù)符,“t₁,t₂,…,t_n”為項,則f(t₁,t₂,…,t_n)是項。
(4)項由且僅由有限次使用(1)、(2)、(3)而得。
原子公式: 設(shè)P是n元謂詞符,“t₁,t₂,…,t_n”為項,則P(t₁,t₂,…,t_n)是原子公式。
6.謂詞邏輯公式(亦可簡稱公式)
(1)原子公式是公式。
(2)如A, B是公式,則(A),(A∨B),(A∧B),(A→B), (A↔B)是公式。
(3)如A為公式,x為個體變量,則(∀xA),(∃xA)為公式。
(4)公式由且僅由有限次使用(1)、(2)、(3)而得。
7.范式
由于一階邏輯公式的結(jié)構(gòu)混亂在實際使用中極不方便,因此一般采用具有統(tǒng)一結(jié)構(gòu)的范式:
(1)斯科林范式:此種形式適用于數(shù)學(xué)領(lǐng)域。一公式如果僅出現(xiàn)全稱量詞的且在公式首部,而公式尾部出現(xiàn)“∨”、 “∧”及“”符, 此種公式稱斯科林范式。
(2)Horn子句形式:此種形式適用于計算機(jī)領(lǐng)域(特別是人工智能領(lǐng)域)。Horn子句的一般形式是“A_n:—A₁,A₂,…,A_n-1”。它是“A₁∧A₂∧…∧A_n-1→A_n”的另一種表示方法,其中,A_i(i=1,2,…,n)均是謂詞;A_n稱為子句的頭,而“A₁,A₂,…,A_n-1”則稱為子句的體。Horn子句還可以有下面幾種特殊表示:①斷言:當(dāng)Horn子句中n=1時,此子句稱斷言,并可表示為“A_n”。②假設(shè): 當(dāng)Horn子句中A_n不出現(xiàn)時,此子句稱假設(shè),并可表示為“:—A₁,A₂,…,A_n-1”。③空子句: 當(dāng)Horn子句中n=0時,此子句稱空子句,并可表示為“□”。
(3)Datalog子句形式:此種形式適用于數(shù)據(jù)庫領(lǐng)域。Datalog子句是專門為數(shù)據(jù)庫中數(shù)據(jù)模型設(shè)計的一種語言,它的基本形式與Horn子句一樣,但是需加一些限制:①Datalog中的變量必須受限,即Datalog中的變量不能在無限域中變化,必須限制在一個有限域內(nèi),這主要是由于數(shù)據(jù)庫中數(shù)據(jù)是有限的特性所決定,而這種限制一般均在Datalog中增加一些限制性謂詞而實現(xiàn)。②在Datalog中一般只出現(xiàn)自由變量以及存在量詞形式出現(xiàn)的約束變量,在子句的頭中所出現(xiàn)的變量均為自由變量,而在子句的體中所出現(xiàn)的變量(除頭中變量外)均為約束變量。
8.永真公式
在公式中如果賦予個體(自由)變元為個體域中的任一個體,公式均為真,則稱此公式為永真公式。
9. 一階演算
一階邏輯的形式系統(tǒng)稱一階演算,又稱一階謂詞演算或簡稱謂詞演算,有關(guān)形式系統(tǒng)介紹可見參考文獻(xiàn)[1],數(shù)理邏輯在謂詞演算中取一些永真公式為公理,并規(guī)定一些推理規(guī)則,組成一個公理系統(tǒng),它可以推出所有的永真公式。謂詞演算中常用的推理規(guī)則有:
(1)全稱推廣規(guī)則UG:P(x)⊦∀xP(x)。
(2)全稱指定規(guī)則US:∀xP(X)⊦P(x)。
(3)存在推廣規(guī)則EG:P(X)⊦∃xP(x)。
(4)存在指定規(guī)則ES:∃xP(X)⊦P(e)。
10. 一個典型的公理系統(tǒng)
謂詞演算中可以有很多公理系統(tǒng),下面是一個典型的公理系統(tǒng):
系統(tǒng)組成部分: 謂詞邏輯公式(見前)。
推理部分:
(1)公理: 設(shè)P,Q,R為公式,則有公理如下:
p→p;
(P→(Q→R))→(Q→(P→R));
(P→Q)→((Q→R)→(P→R));
(P→(P→Q))→(P→Q);
(P↔Q)→(P→Q);
(P↔Q)→(Q→P);
(P→Q)→((Q→P)→(P↔Q));
P∧Q→Q;
P∧Q→P;
P→(Q→P∧Q);
P→P∨Q;
Q→P∨Q;
(Q→P)→((R→P)→(Q∨R→P));
(P→Q)→(Q→P);P→P;
∀xP(x)→P(x);
P(x)→∃xP(x)。
(2)推理規(guī)則:
分離規(guī)則: P→Q, P⊦Q;
全稱規(guī)則: Q→P(x)⊦Q→∀xP(x);
存在規(guī)則:P(x)→Q⊦∃xP(x)→Q。
上面17個公理與3個規(guī)則中有15個公理與1個規(guī)則是命題邏輯公理系統(tǒng)的,真正屬謂詞邏輯的僅有2個公理與2個規(guī)則。
證明(過程)與定理:
證明(過程)是一個公式序列:P₁,P₂,…,P_n,其中每個P_i(i=1,2,…,n)必須滿足下條件之一:
(1)P_i是公理。
(2)P_i是由P_k,P_r,(k,r<i)施行分離規(guī)則而得。
(3)P_i是由P_k(k<i)施行全稱規(guī)則而得。
(4)P_i是由P_k(k<i)施行存在規(guī)則而得。
最后,P_n＝Q即為定理。
可以證明該公理系統(tǒng)是不矛盾的、完全的但不是獨立的。