汪展鵬 蘭笛 周潔

【摘要】本文主要對離散數(shù)學(xué)中的一些只含一個(gè)個(gè)體變元的謂詞邏輯等值式在個(gè)體變元多于兩個(gè)時(shí)的簡單形式的推廣，并加以證明和舉例說明，從而可以簡化多元謂詞問題.

【關(guān)鍵詞】離散數(shù)學(xué);多元謂詞;等值式;形式推廣

引 言

由于命題邏輯的局限性，有些命題在命題邏輯中不能判斷其正確性.例如，著名的“蘇格拉底（Socrates，古希臘哲學(xué)家，公元前470—前399）論證”就是如此[1].由此，人們引入了謂詞邏輯，將簡單命題進(jìn)一步分解為個(gè)體詞、謂詞和量詞.謂詞邏輯就是研究它們的形式結(jié)構(gòu)、邏輯性質(zhì)、謂詞關(guān)系及從中導(dǎo)出的規(guī)律.謂詞邏輯在數(shù)據(jù)庫（如用謂詞邏輯將關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)子語言表示出來并優(yōu)化）、教育（如智能答疑系統(tǒng)）、人工智能科學(xué)等方面都有很廣泛的應(yīng)用，它既是程序設(shè)計(jì)理論、語義形式化及程序邏輯研究的重要基礎(chǔ)，又是程序驗(yàn)證、程序分析、綜合及自動(dòng)生成、定理證明和知識(shí)表示的有力工具，顯示了謂詞邏輯在計(jì)算機(jī)科學(xué)中的重要性.

而隨著謂詞邏輯基本等值式的應(yīng)用，過程過于煩瑣復(fù)雜的謂詞邏輯演算也變得簡單.本文主要對離散數(shù)學(xué)中的一些主要的、只含一個(gè)個(gè)體變元的謂詞邏輯等值式在個(gè)體變元多于兩個(gè)時(shí)的簡單形式的推廣，從而可以簡化多元謂詞問題，并加以證明和舉例說明，對于本文未給出的謂詞邏輯等值式，其在個(gè)體變元多于兩個(gè)時(shí)的簡單形式推廣可以參考本文證明過程.

1 基本知識(shí)

對于謂詞邏輯的基本理論知識(shí)，我們建議讀者參看參考文獻(xiàn)[1].

定義1.1 令A(yù)，B為一階語言的合式公式，若AB為邏輯有效式，則稱A和B等值，記為AB.稱AB是等值式.

定理1.1 設(shè)Q不含自由變項(xiàng)x，則下列等值式成立.

（1）xPxxPx

（2）x（P（x）∨Q）xP（x）∨Q

（3）x（P（x）→Q（x））x（P（x））→x（Q（x））

（4）x（P（x）∧Q（x））x（P（x））∧x（Q（x））

（5）xyP（x，y）yxP（x，y）

在對一元或二元謂詞邏輯問題的求解過程中，通過以上等值式的替換，往往可以使問題簡單化.但是，以上的等值式，由于其中謂詞所含個(gè)體變元數(shù)目的限制，故對于多元或更加一般的謂詞邏輯問題就沒有應(yīng)用價(jià)值.

例1 設(shè)T（x，y）：x被y認(rèn)可，再令x是“學(xué)生”集合中的元素，y是“老師”集合中的元素，判斷命題（xyT（x，y））與命題xy（T（x，y））是否等值.

由于上述等值式不適用，只能單純地從其語義來判斷或者將“學(xué)生”和“老師”集合中的元素代入之后再判斷，下面選擇用語義角度解決該問題.

（xyT（x，y））表示：不是每名學(xué)生都有老師認(rèn)可.而命題xy（T（x，y））表示：有的同學(xué)，所有老師都不認(rèn)可.兩者意思一致，因此，兩者等值.

雖然從語義判斷也是可行的，但是在多元謂詞演算過程中，如果每一步都這樣來判斷，那么工作量會(huì)很大.因此，以下給出上述等值式在n（n≥2）元謂詞邏輯的簡單形式的推廣，并加以嚴(yán)格的理論證明.

2 記 號(hào)

我們作如下符號(hào)注記：

（1）∏ni=1Qixi表示Q1x1Q2x2…Qnxn，其中Qi是量詞，即Qi∈{，}.

（2）P（n）表示P（x1，x2，…，xn）.

（3）P（k，y1，y2，…，yi）表示P（x1，x2，…，xk，y1，y2，…，yi），其中xi為自由變項(xiàng)，yi為個(gè)體常項(xiàng).

3 主要結(jié)論

結(jié)論3.1? ∏ni=1QixiP（n）∏ni=1Rixi（P（n）），其中Qi和Ri表示不同的量詞，即若Qi取，那么Ri取;反之亦然.

證明 我們對變元個(gè)數(shù)運(yùn)用第一數(shù)學(xué)歸納法：

（1）當(dāng)n=1時(shí)即為結(jié)論（1），顯然成立.

（2）假設(shè)當(dāng)n=k（k≥1，k∈N）時(shí)結(jié)論亦成立，下面證明n=k+1時(shí)結(jié)論成立，對Qk+1分以下兩種情況進(jìn)行討論：

①Q(mào)k+1取時(shí)：

不妨令xk+1是集合{y1，y2，…，ym}中的元素，所以∏ki=1Qixixk+1P（k+1）

∏ki=1QixiP（k，y1）∧…∧∏ki=1QixiP（k，ym）

∏ki=1QixiPk，y1∨…∨∏ki=1QixiP（k，ym）.

而此時(shí)yi（i=1，2，…，m）都是個(gè)體常項(xiàng)，上式中各項(xiàng)都從k+1元謂詞變?yōu)閗元謂詞，所以上式等價(jià)于：

∏ki=1Rixi（P（k，y1））∨…∨∏ki=1Rixi（P（k，ym））

∏ki=1Rixixk+1P（k+1）.

②Qk+1取時(shí)：同理可證.

∏ki=1Qixixk+1P（k+1）∏ki=1Rixixk+1P（k+1）.

所以，該結(jié)論對n=k+1成立.

綜合（1）（2），對一切自然數(shù)n≥1，上述結(jié)論成立.

有了這個(gè)結(jié)論，再來看上述例題：當(dāng)n=2時(shí)，很顯然有xyT（x，y）xyT（x，y）成立.體現(xiàn)出多元推廣后等值式的實(shí)用性.

結(jié)論3.2 設(shè)W不含自由變項(xiàng)xi（i=1，2，…，n），則下列等值式成立.

∏ni=1xiP（n）∨W∏ni=1xiP（n）∨W.

證明 類似于結(jié)論3.1的證明過程，同樣對變元個(gè)數(shù)用第一數(shù)學(xué)歸納法即可.（歸納步驟需要用到“∨”對“∧”的分配律）

當(dāng)n=2時(shí)，下面通過一個(gè)實(shí)例來論證該結(jié)論.

例2 設(shè)P（x，y）：x在y，再令x是“學(xué)生”集合中的元素，y是“教室”集合中的元素，Q：外面下雨.判斷命題xy（P（x，y）∨Q）與命題xyP（x，y）∨Q是否等值.

下面從其語義來判斷兩個(gè)命題是否等值.首先將“學(xué)生”和“教室”集合中的元素代入之后再判斷.命題xy（P（x，y）∨Q）表示：任意學(xué)生在外面下雨時(shí)都在自己的教室，而命題xyP（x，y）∨Q表示：外面下雨時(shí)任意一個(gè)學(xué)生都在自己的教室.兩者意思一致，因此，兩者等值.

結(jié)論3.3 ∏ni=1xiP（n）→W（n）∏ni=1xiP（n）→∏ni=1xiW（n）.

證明 只證n=2時(shí)的結(jié)論，其他情況類似可證.

假設(shè)論域有限，設(shè)xi∈{yi，1，yi，2，…，yi，mi}，則：

∏2i=1xi（P（2）→W（2））∏2i=1xi（P（2）∨W（2））

x1（（P（1，y2，1）∨W（1，y2，1））∨…∨（P（1，y2，m2）∨W（1，y2，m2））

…P（y1，1，y2，1）∨W（y1，1，y2，1）∨…∨P（y1，m1，y2，m2）∨W（y1，m1，y2，m2） .

根據(jù)“∨”的交換律和結(jié)合律，上式可化為：

（P（y1，1，y2，1）∨…∨P（y1，m1，y2，m2））∨（W（y1，1，y2，1）∨…∨W（y1，m1，y2，m2））

∏2i=1xi（P（2））∨∏2i=1xiW（2）.

根據(jù)利用結(jié)論3.1，即證.

當(dāng)n=2時(shí)，下面通過一個(gè)實(shí)例來論證該結(jié)論.

例3 設(shè)P（x，y）：x≥y，W（x，y）：x>y，再令x是實(shí)數(shù)集合中的元素，y是實(shí)數(shù)集合中的元素，判斷命題xy（P（x，y）→W（x，y））與命題xyP（x，y）→xyW（x，y）是否等值.

下面從其語義來判斷兩個(gè)命題是否等值.首先將實(shí)數(shù)集合中的元素代入之后再判斷.命題xy（P（x，y）→W（x，y））表示：存在實(shí)數(shù)x，y，有當(dāng)x≥y時(shí)，x>y.而命題xyP（x，y）→xyW（x，y）表示：對所有的實(shí)數(shù)x≥y，存在實(shí)數(shù)x，y，滿足x>y.兩者意思一致，因此，兩者等值.

結(jié)論3.4

（1）∏ni=1xiP（n）∧W（n）∏ni=1xiP（n）∧∏ni=1xiW（n）.

（2）∏ni=1xiP（n）∨W（n）∏ni=1xiP（n）∨∏ni=1xiW（n）.

證明 同結(jié)論3.3的證明過程類似，依次將謂詞展開再利用“∧”的交換律和結(jié)合律即可.

當(dāng)n=2時(shí)，下面通過一個(gè)實(shí)例來論證該結(jié)論（1）式.

例4 設(shè)P（x，y）：x>y，W（x，y）：x≠y，再令x是實(shí)數(shù)集合中的元素，y是實(shí)數(shù)集合中的元素，判斷命題xy（P（x，y）∧W（x，y））與命題xyP（x，y）∧xyW（x，y）是否等值.

下面從其語義來判斷兩個(gè)命題是否等值.首先將實(shí)數(shù)集合中的元素代入之后再判斷.命題xy（P（x，y）∧W（x，y））表示：對所有的實(shí)數(shù)x，y，都有x>y且x≠y.而命題xyP（x，y）∧xyW（x，y）表示：對所有的實(shí)數(shù)x>y，都有x≠y.兩者意思一致，因此，兩者等值.

當(dāng)n=2時(shí)，下面通過一個(gè)實(shí)例來論證該結(jié)論（2）式.

例5 設(shè)P（x，y）：x>y，W（x，y）：x=y，再令x是實(shí)數(shù)集合中的元素，y是實(shí)數(shù)集合中的元素，判斷命題xy（P（x，y）∨W（x，y））與命題xyP（x，y）∨xyW（x，y）是否等值.

下面從其語義來判斷兩個(gè)命題是否等值.首先將實(shí)數(shù)集合中的元素代入之后再判斷.命題xy（P（x，y）∨W（x，y））表示：存在實(shí)數(shù)x，y，有x>y或者x=y.而命題xyP（x，y）∨xyW（x，y）表示：存在實(shí)數(shù)x>y，或者存在實(shí)數(shù)x=y.兩者意思一致，因此，兩者等值.

結(jié)論3.5 ∏ni=1xiP（n）∏ni=1xtiP（n），

∏ni=1

xiP（n）∏ni=1xtiP（n），其中t1，t2，…，tn為1，2，…，n的任一排列.

證明 同結(jié)論3.3的證明過程類似，依次將謂詞展開，再分別利用“∧”和“∨”的交換律和結(jié)合律即可.

還可以將結(jié)論3.5一般化，得到一個(gè)適用范圍更廣的推論3.5.1.

推論3.5.1 對于nn≥2元謂詞命題∏ni=1QixiP（n）：

若Q1=Q2=…=Qn，則為結(jié)論2.5中的情形.

若Qi≠Q(mào)i+1=…=Qn，其中i=1，2，…，n-1，則Qi+1xi+1，…，Qn-1xn-1，Qnxn可以任意交換位置，即：

Q1x1Q2x2…QnxnP（x1，x2，…，xn）Q1x1…QixiQti+1xti+1…，

Qtn-1xtn-1QtnxtnP（x1，x2，…，xn）.

其中ti+1，…，tn-1，tn是i+1，…，n-1，n的任意排列.

由于證明過程與結(jié)論3.5類似，所以不再贅述.

※注意：

（1）本文僅僅是從謂詞邏輯的所有等值式中選出幾個(gè)比較基本的加以推廣，引理未提及的等值式推廣形式的證明均可仿照本文相應(yīng)部分或者利用本文結(jié)論.

如，要證明Q→xP（x）x（Q→P（x））在n（n≥2）時(shí)的推廣形式：

Q→∏ni=1xiP（n）∏ni=1xiQ→P（n）.

證明過程如下：

Q→∏ni=1xiP（n）Q∨∏ni=1xiP（n）.

再由結(jié)論3.2，上式可化為：

∏ni=1xiQ∨P（n）∏ni=1xiQ→P（n）.

（2）對于推論3.5.1，只有Qi+1xi+1，…，Qn-1xn-1，Qnxn可以交換位置，其他的量詞及其所限制變元的位置一定保持不變，否則可能是錯(cuò)誤的，下面舉例說明.

例6 設(shè)P（x，y）表示x+y=a（a為一固定常數(shù)），因此，xyP（x，y）在實(shí)數(shù)R上的含義就是對任意實(shí)數(shù)x存在實(shí)數(shù)y滿足x+y=a，其真值為1;而xyP（x，y）在實(shí)數(shù)域R上的含義就是存在實(shí)數(shù)y對任意的實(shí)數(shù)x都滿足x+y=a，其真值為0.因此，兩者不等值，即：

xyP（x，y）≠xyP（x，y）.

【參考文獻(xiàn)】

[1]李世群，馬千里.離散數(shù)學(xué)[M].天津：天津大學(xué)出版社，2010.

[2]祝深有，張會(huì)凌.帶有多重量詞的謂詞公式的否定[J].甘肅廣播電視大學(xué)學(xué)報(bào)，2008（03），36-37.