謂詞邏輯等值式在多元謂詞的推廣

汪展鵬 蘭笛 周潔

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

【關鍵詞】離散數學;多元謂詞;等值式;形式推廣

引 言

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

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

1 基本知識

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

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

定理1.1 設Q不含自由變項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）

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

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

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

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

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

2 記 號

我們作如下符號注記：

（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為自由變項，yi為個體常項.

3 主要結論

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

證明 我們對變元個數運用第一數學歸納法：

（1）當n=1時即為結論（1），顯然成立.

（2）假設當n=k（k≥1，k∈N）時結論亦成立，下面證明n=k+1時結論成立，對Qk+1分以下兩種情況進行討論：

①Qk+1取時：

不妨令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）.

而此時yi（i=1，2，…，m）都是個體常項，上式中各項都從k+1元謂詞變為k元謂詞，所以上式等價于：

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

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

②Qk+1取時：同理可證.

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

所以，該結論對n=k+1成立.

綜合（1）（2），對一切自然數n≥1，上述結論成立.

有了這個結論，再來看上述例題：當n=2時，很顯然有xyT（x，y）xyT（x，y）成立.體現出多元推廣后等值式的實用性.

結論3.2 設W不含自由變項xi（i=1，2，…，n），則下列等值式成立.

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

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

當n=2時，下面通過一個實例來論證該結論.

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

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

結論3.3 ∏ni=1xiP（n）→W（n）∏ni=1xiP（n）→∏ni=1xiW（n）.

證明 只證n=2時的結論，其他情況類似可證.

假設論域有限，設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） .

根據“∨”的交換律和結合律，上式可化為：

（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）.

根據利用結論3.1，即證.

當n=2時，下面通過一個實例來論證該結論.

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

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

結論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）.

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

當n=2時，下面通過一個實例來論證該結論（1）式.

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

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

當n=2時，下面通過一個實例來論證該結論（2）式.

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

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

結論3.5 ∏ni=1xiP（n）∏ni=1xtiP（n），

∏ni=1

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

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

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

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

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

若Qi≠Qi+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的任意排列.

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

※注意：

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

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

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

證明過程如下：

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

再由結論3.2，上式可化為：

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

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

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

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

【參考文獻】

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

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