每個人都曾試圖在平淡的學習、工作和生活中寫一篇文章。寫作是培養人的觀察、聯想、想象、思維和記憶的重要手段。寫范文的時候需要注意什么呢？有哪些格式需要注意呢？接下來小編就給大家介紹一下優秀的范文該怎么寫，我們一起來看一看吧。

謂詞邏輯公式篇一

1.將下列命題用謂詞符號化。（1）小王學過英語和法語。（3）3不是偶數。

（2）2大于3僅當2大于4。（4）2或3是質數。

（5）除非李鍵是東北人，否則他一定怕冷。解：

(1)令p(x)：x學過英語，q(x)：x學過法語，c：小王，命題符號化為p(c)?q(c)(2)令p(x,y)：x大于y, 命題符號化為p(2,4)?p(2,3)(3)令p(x)：x是偶數，命題符號化為?p(3)(4)令p(x)：x是質數，命題符號化為p(2)?p(3)

(5)令p(x)：x是北方人；q(x)：x怕冷；c：李鍵；命題符號化為q(c)??p(x)

b，c}，消去下列各式的量詞。2.設個體域d?{a，（1）?x?y(p(x)?q(y))（3）?xp(x)??yq(y)

（2）?x?y(p(x)?q(y))（4）?x(p(x，y)??yq(y))

解：

(1)中a(x)??y(p(x)?q(y))，顯然a(x)對y是自由的，故可使用ue規則，得到

a(y)??y(p(y)?q(y))，因此?x?y(p(x)?q(y))??y(p(y)?q(y))，再用es規則，?y(p(y)?q(y))?p(z)?q(z)，z?d，所以?x?y(p(x)?q(y))?p(z)?q(z)

（2）中a(x)??y(p(x)?q(y))，它對y不是自由的，故不能用ui規則，然而，對

a(x)中約束變元y改名z，得到?z(p(x)?q(z))，這時用ui規則，可得：

?x?y(p(x)?q(y))

??x?z(p(x)?q(z))

??z(p(x)?q(z))（3）略（4）略，2，3}。求下列各式3.設謂詞p(x，y)表示“x等于y”，個體變元x和y的個體域都是d?{1（1）?xp(x，3)

的真值。，y)（2）?yp(1y)（4）?x?yp(x，y)（6）?y?xp(x，y)

（3）?x?yp(x，y)（5）?x?yp(x，解：

(2)當x?3時可使式子成立，所以為ture。

(3)當y?1時就不成立，所以為false。

(4)任意的x,y使得x?y，顯然有x?y的情況出現，所以為false。

(4)存在x,y使得x?y，顯然當x?1,y?1時是一種情況，所以為ture。

(5)存在x，任意的y使得x?y成立，顯然不成立，所以為false。

(6)任意的y，存在x，使得x?y成立，顯然不成立，所以為false。

4.令謂詞p(x)表示“x說德語”，q(x)表示“x了解計算機語言c++”，個體域為杭電全體學生的集合。用p(x)、q(x)、量詞和邏輯聯接詞符號化下列語句。

（1）杭電有個學生既會說德語又了解c++。（2）杭電有個學生會說德語，但不了解c++。（3）杭電所有學生或會說德語，或了解c++。（4）杭電沒有學生會說德語或了解c++。

假設個體域為全總個體域，謂詞m(x)表示“x是杭電學生”。用p(x)、q(x)、m(x)、量詞和邏輯聯接詞再次符號化上面的4條語句。解：（ⅰ）個體域為杭電全體學生的集合時：

（1）?x(p(x)?q(x))（2）?x(p(x)??q(x))（3）?x(p(x)?q(x))（4）?x?(p(x)?q(x))

（ⅱ）假設個體域為全總個體域，謂詞m(x)表示“x是杭電學生”時：

（1）?x(m(x)?p(x)?q(x))（2）?x(m(x)?p(x)??q(x))（3）?x(m(x)?(p(x)?q(x)))（4）?x(m(x)??(p(x)?q(x)))

5.令謂詞p(x，y)表示“x愛y”，其中x和y的個體域都是全世界所有人的集合。用p(x，y)、量詞和邏輯聯接詞符號化下列語句。

（1）每個人都愛王平。

（2）每個人都愛某個人。（4）沒有人愛所有的人。（6）有個人人都不愛的人。（8）成龍愛的人恰有兩個。

（3）有個人人都愛的人。

（5）有個張鍵不愛的人。

（7）恰有一個人人都愛的人。

（9）每個人都愛自己。

（10）有人除自己以外誰都不愛。

解：a：王平b：張鍵

c：張龍

(1)?xp(x,a）

(2)?x?yp(x,y)(3)?y?xp(x,y)

(4)?x?y?p(x,y)(5)?x?p(b，x)

(6)?x?y?p(x,y)(7)?x(?yp(y,x)??z((??p(?,z))?z?x))

(8)?x?y(x?y?p(c,x)?p(c)??z(p(c，z)?(z?x?z?y)))(9)?xp(x,x)

(10)?x?y(p(x,y)?x?y)§2.2 謂詞公式及其解釋

習題2.2 1.指出下列謂詞公式的指導變元、量詞轄域、約束變元和自由變元。

（1）?x(p(x)?q(x，y))（2）?xp(x，y)??yq(x，y)

（3）?x?y(p(x，y)?q(y，z))??xr(x，y，z)

解：（1）x是指導變元，?x的轄域是p(x)?q(x,y)，對于?x的轄域而言，x是約束變元，y是自由變元。

（2）x,y都為指導變元，?x的轄域是p(x，y)??yq(x，y)，?y的轄域是q(x，y)；對于?x的轄域而言，x,y都為約束變元，對于?y的轄域而言，x是自由變元，y是約束變元。

（3）x,y為指導變元，?x的轄域是?y(p(x，y)?q(y，z))??xr(x，y，z)，?y的轄域是(p(x，y)?q(y，z))??xr(x，y，z)，?x的轄域是r(x，y，z)；對于?x的轄域而言，x,y為約束變元，z為自由變元，對于?y的轄域而言，z為自由變元，y為約束變元，x即為約束變元也為自由變元，對于?x的轄域而言，x為約束變元，y,z是自由變元。在整個公式中，x,y即為約束變元又為自由變元，z為自由變元。

2.判斷下列謂詞公式哪些是永真式，哪些是永假式，哪些是可滿足式，并說明理由。（1）?x(p(x)?q(x))?(?xp(x)??yq(y))（2）?x(p(x)?q(x))?(?xp(x)??yq(y))（3）?(?xp(x)??yq(y))??yq(y)（4）?x(p(y)?q(x))?(p(y)??xq(x))（5）?x(p(x)?q(x))?(p(x)??xq(x))（6）?(p(x)?(?yq(x，y)?p(x)))（7）p(x，y)?(q(x，y)?p(x，y))

解：（1）易知公式是(p?q)?(p?q)的代換實例，而

(p?q)?(p?q)??(p?q)?(p?q)?1 是永真式，所以公式是永真式。

（2）易知公式是(p?q)?(p?q)的代換實例，而

(p?q)?(p?q)??(p?q)?(p?q)?1 是永真式，所以公式是永真式。

（3）易知公式是?(p?q)?q的代換實例，而

?(p?q)?q??(?p?q)?q?p??q?q?0 是永假式，所以公式是永假式。

（4）易知公式是(p?q)?(p?q)的代換實例，而

(p?q)?(p?q)??(p?q)?(p?q)?1 是永真式，所以公式是永真式。

（5）易知公式是(p?q)?(p?q)的代換實例，而

(p?q)?(p?q)??(p?q)?(p?q)?1 是永真式，所以公式是永真式。

（6）易知公式是?(p?(q?p))的代換實例，而

?(p?(q?p))??(?p?(?q?p))?p?q??p?0 是永假式，所以公式是永假式。

（7）易知公式是p?q?p的代換實例，而

p?q?p??(?p?q)?p?(p??q)?p 是可滿足式，所以公式是可滿足式。§2.3 謂詞公式的等價演算與范式

習題2.3 1.將下列命題符號化，要求用兩種不同的等價形式。（1）沒有小于負數的正數。

（2）相等的兩個角未必都是對頂角。

解：（1）p(x)：x為負數，q(x)：x是正數，r(x,y)：x小于y，命題可符號化為：?x?y(r(p(x),q(y)))或?x?y?(?r(p(x),q(y)))

（2）略

2.設p(x)、q(x)和r(x，y)都是謂詞，證明下列各等價式（1）??x(p(x)?q(x))??x(p(x)??q(x))（2）??x(p(x)?q(x))??x(p(x)??q(x))

（3）??x?y(p(x)?q(y)?r(x，y))??x?y(p(x)?q(y)??r(x，y))（4）??x?y(p(x)?q(y)?r(x，y))??x?y(p(x)?q(y)??r(x，y))證明：（1）左邊＝?x?(p(x)?q(x))

＝?x(?p(x)??q(x))＝?x(p(x)??q(x))＝右邊

（2）左邊 ＝?x?(p(x)?q(x))

＝?x?(?p(x)?q(x))

＝?x(p(x)??q(x))＝右邊

（3）左邊＝?x?y?(p(x)?q(y)?r(x,y))

＝?x?y?(?(p(x)?q(y))?r(x,y))

＝?x?y(p(x)?q(y)??r(x，y))＝右邊

（4）左邊＝?x?y?(p(x)?q(y)?r(x,y)

＝?x?y?(p(x)?q(y))??r(x,y)

＝?x?y(p(x)?q(y)??r(x，y))＝右邊

3.求下列謂詞公式的前束析取范式和前束合取范式。（1）?xp(x)??yq(x，y)

（2）?x(p(x，y)??yq(x，y，z))（3）?x??yp(x，y)?(?zq(z)?r(x))

（4）?x(p(x)?q(x，y))?(?y(r(y)??zs(y，z))

解：（1）原式??x?yp(x)?q(z,y)??x?y(?p(x)?q(z,y))

前束析取范式

??x?y?(p(x)??q(z,y))

前束合取范式

（2）原式??x?t(p(x,y)?q(x,t,z)??x?t(?p(x,y)?q(x,t,z)前束析取范式

??x?t?(p(x,y)??q(x,t,z)

前束合取范式（3）原式??x?y?z(?p(x,y)?(q(z)?r(t))

??x?y?z(p(x,y)??q(z)?r(t))

前束析取范式

??x?y?z?(?p(x,y)?q(z)??r(t))

前束合取范式（4）原式??x(p(x)?q(x，y))?(?t(r(t)??zs(t，z))

??x?t?z((p(x)?q(x,y))?(r(t)?s(t,z)))

??x?t?z(?(?p(x)?q(x,y))?(?r(t)?s(t,z)))

??x?t?z((p(x)?q(x,y)??r(t))?(p(x)?q(x,y)?s(t,z)))

??x?t?z((p(x)?(?r(t)?s(t,z))?(q(x,y)??r(t)?s(t,z)

§2.4 謂詞公式的推理演算

習題2.4 1.證明：?x(a(x)?b(x))??x(a(x)?b(x))

證明：（1）左邊????x(a(x)?b(x))???x?(a(x)?b(x))

??x??(a(x)?b(x))＝?x(a(x)?b(x))2.指出下面演繹推理中的錯誤，并給出正確的推導過程。（1）①?xp(x)?q(x)

②p(y)?q(y)

p規則 us規則：① p規則 us規則：① p規則 es規則：① p規則 ug規則：① p規則 eg規則：① p規則 eg規則：①（2）①?x(p(x)?q(x))

②p(a)?q(b)

（3）①p(x)??xq(x)

②p(a)?q(a)（4）①p(a)?g(a)

②?x(p(x)?g(x))

（5）①p(a)?g(b)

②?x(p(x)?g(x))

（6）①p(y)?q(y)

②?x(p(c)?q(x))

解：（1）②錯，使用us,ug,es,eg規則應對前束范式，而①中公式不是前束范式，所以不能用us規則。

a(x)?p(x)?q(x)，(2)②錯，①中公式為?xa(x)，這時，因而使用us規則時，應得a(a)(或a(y)),故應有p(a)?q(a)，而不能為p(a)?q(b)。

3.用演繹法證明下列推理式

?xp(x)??y((p(y)?q(y))?r(y))，?xp(x)??xr(x)

證明：① ?xp(x)前提引入

② p(a)es①

③ ?xp(x)??y((p(y)?q(y))?r(y))

前提引入

④ ?y((p(y)?q(y))?r(y))t①③

⑤(p(a)?q(a))?r(a)us④

⑥ p(a)?q(a)

t②

⑦ r(a)t⑤⑥

⑧ ?xr(x)eg⑦

4.將下列命題符號化，并用演繹推理法證明其結論是有效的。（1）有理數、無理數都是實數；虛數不是實數。因此，虛數既不是有理數，也不是無理數。（個體域取全總個體域）（2）所有的舞蹈者都很有風度；萬英是個學生并且是個舞蹈者。因此，有些學生很有風度。（個體域取人類全體組成的集合）（3）每個喜歡步行的人都不喜歡騎自行車；每個人或者喜歡騎自行車或者喜歡乘汽車；有的人不喜歡乘汽車。所以有的人不喜歡步行。（個體域取人類全體組成的集合）（4）每個旅客或者坐頭等艙或者坐經濟艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐經濟艙。（個體域取全體旅客組成的集合）

解：(2)證明：設p(x)：x 是個舞蹈者； q(x)：x很有風度； s(x)：x是個學生； a：王華

上述句子符號化為：

前提：?x(p(x)?q(x))、s(a)?p(a)結論：?x(s(x)?q(x))

（1）s(a)?p(a)p（2）?x(p(x)?q(x))p（3）p(a)?q(a)（4）p(a)（5）q(a).（6）s(a)（7）s(a)?q(a)（8）?x(s(x)?q(x)

]（3）命題符號化為：f(x)：x喜歡步行,g(x)：x喜歡騎自行車，h(x)：x喜歡坐汽車。

us（2）t（1）i t（3）（4）i t（1）i t（5）（6）i eg（7）

前提：?x(f(x)??g(x))，?x(g(x)?h(x))，?x(?h(x))

結論：?x(?f(x)).證明：(1)?x(?h(x))p(2)?h(c)es(1)(3)?x(g(x)?h(x))

p(4)g(c)?h(c)us(3)(5)g(c)t(2)(4)i(6)?x(f(x)??g(x))

p(7)f(c)?g(c)us(6)(8)?f(c)t(5)(7)i(9)?x(?f(x))

eg(8)

（4）命題符號化為：f(x)：x坐頭等艙, g(x)：x坐經濟艙，h(x)：x富裕。

前提：?x(f(x)?g(x))，?x(f(x)?h(x))，?x(h(x))，?x(?h(x))

結論：?x(g(x)).證明：(1)?x(?h(x))p(2)?h(c)es(1)(3)?x(f(x)?h(x))

p(4)f(c)?h(c)us(3)(5)?f(c)t(2)(4)i(6)?x(f(x)?g(x))

p

(7)f(c)?g(c)us(6)(8)g(c)t(5)(7)i(9)?x(g(x))

eg(8)

5.令謂詞p(x)、q(x)、r(x)和s(x)分別表示“x是嬰兒”，表示“x的行為符合邏輯”、“x能管理鱷魚”和“x被人輕視”，個體域為所有人的集合。用p(x)、q(x)、r(x)、s(x)、量詞和邏輯聯接詞符號化下列語句。

（1）嬰兒行為不合邏輯。（2）能管理鱷魚的人不被人輕視。（3）行為不合邏輯的人被人輕視。

（4）嬰兒不能管理鱷魚。

請問，能從（1）、（2）和（3）推出（4）嗎？若不能，請寫出（1）、（2）和（3）的一個有效結論，并用演繹推理法證明之。解：（1）?x(p(x)??q(x))

（2）?x(r(x)??s(x))

（3）?x(?q(x)?s(x))

（4）?x(p(x)??r(x))能從（1）（2）（3）推出（4）。

證明：（1）

p(x)

（2）

?x(p(x)??q(x))

（3）

?q(x))

（4）

?x(?q(x)?s(x))

（5）

s(x)

（6）

?x(r(x)??s(x))

（7）

?r(x)

（8）

?x(p(x)??r(x))

前提假設

前提引入

t 規則：(1)，(2)

p規則

t 規則：(3)，(4)p規則 拒取式 ug規則

謂詞邏輯公式篇二

第三章復習

對當關系性質

1.矛盾關系：不可同真，不可同假。

2.反對關系：不可同真，可以同假。

3.下反對關系：不可同假，可以同真。

4.差等關系：上真下真，下假上假。

命題變形推理

換質法：兩變兩不變

1.變：變質、謂項變成矛盾概念；

2.不變：主、謂項位置不變、量不變。

換位法：一變一不變

1.變：主、謂項位置變。

2.不變：質不變。

3.前提中不周延的項在結論中不得周延。

三段論

1.三段論規則

2.三段論的格式

3.周延性。

4.三段論有效性的檢驗

5.省略三段論的檢驗

6.三段論證明

例：一組三段論包括兩個有效三段論，它們的大前提和結論都不同真不同假。請列出所有符合上述條件的有效三段論形式（以組為單位，兩個三段論為一組），并寫出推導過程。

證明：

1.結論與大前提都是矛盾關系。為ao或ei。

2.結論為ao，結論為a的是第一格aaa式。

結論為o的，大前提一定是mop，小前提是mas，第一格aaa式與第三格oao。

3.結論是ei，結論為i的，其大前提為mip或pim,小前提為mas。

結論為e的，大前提為pem或mep，小前提為sam。符合條件的有： 第一格eae式與第三格iai式；第一格eae式與與第四格iai式；第二格eae式與第三格iai式；第二格eae式與第四格iai式。

共五組

謂詞邏輯公式篇三

2.3 謂詞邏輯歸結法基礎

由于謂詞邏輯與命題邏輯不同，有量詞、變量和函數，所以在生成子句集之前要對邏輯公式做處理，具體的說就是要將其轉化為skolem標準形，然后在子句集的基礎上再進行歸結，雖然基本的歸結的基本方法都相同，但是其過程較之命題公式的歸結過程要復雜得多。

本節針對謂詞邏輯歸結法介紹了skolem標準形、子句集等一些必要的概念和定理。

2．3．1 skolem 標準形

skolem標準形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為skolem標準形，任何一個謂詞公式都可以化為與之對應的skolem標準形。但是，skolem標準形不唯一。

前束范式：a是一個前束范式，如果a中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。

skolem標準形的轉化過程為，依據約束變量換名規則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式g轉換成為前束范式

前束范式的形式為：

(q1x1)(q2x2)…(qnxn)m(x1,x2,…,xn)

即： 把所有的量詞都提到前面去。

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達式中的所有同名變量。所以將量詞提到公式最前端時存在約束變量換名問題。要嚴守規則。

約束變量換名規則：

(qx)m（x）

(qx)m（x,z）

（qy）m（y）

（qy）m（y,z）

量詞否定等值式：

～(x)m（x）

～(x)m（x）

量詞分配等值式：

(x)(p（x）∧q（x）)

(x)(p（x）∨ q（x）)

(x)p（x）∧(x)q（x）(x)p（x）∨(x)q（x）

（y）～ m（y）

（y）～ m（y）

消去量詞等值式：設個體域為有窮集合（a1, a2, …an）

(x)p（x）

(x)p（x）

p（a1）∧ p（a2）∧ …∧ p（an）p（a1）∨ p（a2）∨ … ∨ p（an）

量詞轄域收縮與擴張等值式：

(x)(p（x）∨ q)

(x)(p（x）∧ q)

(x)(p（x）→ q)

(x)(q → p（x）)

(x)p（x）∨ q(x)p（x）∧ q(x)p（x）→ q q →(x)p（x）

(x)(p（x）∨ q)

(x)(p（x）∧ q)

(x)(p（x）→ q)

(x)(q → p（x）)

消去量詞

量詞消去原則：

(x)p（x）∨ q(x)p（x）∧ q(x)p（x）→ q q →(x)p（x）

1)消去存在量詞“"，即，將該量詞約束的變量用任意常量（a, b等）、或全稱變量的函數(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數。

2)略去全程量詞”“，簡單地省略掉該量詞。

skolem 定理：

謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。

注意：公式g的skolem標準形同g并不等值。例題2-2

將下式化為skolem標準形：

～(x)(y)p(a, x, y)→(x)(～(y)q(y, b)→r(x))

解：

第一步，消去→號，得：

～(～(x)(y)p(a, x, y))∨(x)(～～(y)q(y, b)∨r(x))

第二步，～深入到量詞內部，得：

(x)(y)p(a, x, y)∧～(x)((y)q(y, b)∨r(x))

＝(x)(y)p(a, x, y)∧(x)((y)～q(y, b)∧～r(x))

第三步，全稱量詞左移，（利用分配律），得

(x)((y)p(a, x, y)∧(y)(～q(y, b)∧～r(x)))

第四步，變元易名，存在量詞左移，直至所有的量詞移到前面，得：

(x)((y)p(a, x, y)∧(y)(～q(y, b)∧～r(x)))

＝(x)((y)p(a, x, y)∧(z)(～q(z, b)∧～r(x)))

=(x)(y)(z)(p(a, x, y)∧～q(z, b)∧～r(x))

由此得到前述范式

第五步，消去”“（存在量詞），略去”“全稱量詞

消去(y)，因為它左邊只有(”x)，所以使用x的函數f(x)代替之，這樣得到：

(x)(z)(p(a, x, f(x))∧～q(z, b)∧～r(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(p(a, x, f(x))∧～q(g(x), b)∧～r(x))

則，略去全稱變量，原式的skolem標準形為：

p(a, x, f(x))∧～q(g(x), b)∧～r(x)

2.3.2子句集

文字：不含任何連接詞的謂詞公式。

子句：一些文字的析取（謂詞的和）。

子句集：所有子句的集合

對于任一個公式g，都可以通過skolem標準形，標準化建立起一個子句集與之相對應。因為子句不過是一些文字的析取，是一種比較簡單的形式，所以對g的討論就用對子句集s的討論來代替，以便容易處理。

子句集s可由下面的步驟求取：

1.謂詞公式g轉換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成skolem標準形

3.將skolem標準形中的各個子句提出，表示為集合形式

教師提示：為了簡單起見，子句集生成可以理解為是用“，”取代skolem標準形中的“λ”，并表示為集合形式。

注意：skolem標準形必須滿足合取范式的條件。即，在生成子句集之前邏輯表達式必須是各“謂詞表達式”或“謂詞或表達式”的與。

定理

謂詞表達式g是不可滿足的當且僅當 其子句集s是不可滿足的

公式g與其子句集s并不等值，但它們在不可滿足的意義下是一致的。因此如果要證明a1∧a2∧a3→b，只需證明g＝ a1∧a2∧a3∧～b的子句集是不可滿足的，這也正是引入子句集的目的。

注意：公式g和子句集s雖然不等值，但是它們的之間一般邏輯關系可以簡單的說明為：g真不一定s真，而s真必有g真，即，s g。在生成skolem標準形時將存在量詞用常量或其他變量的函數代替，使得變量討論的論域發生了變化，即論域變小了。所以g不能保證s真。

定理的推廣

對于形如g = g1λ g2λ g3λ …λ gn 的謂詞公式，g的子句集的求取過程可以分解成幾個部分單獨處理。如果gi的子句集為si，則

有 s' = s1 ∪ s2 ∪ s3 ∪ …∪ sn，雖然g的子句集不為s'，但是可以證明：

sg 與s1 ∪ s2 ∪ s3 ∪ …∪sn在不可滿足的意義上是一致的。

即sg 不可滿足

由上面的定理，我們對sg的討論，可以用較為簡單的s1 ∪ s2 ∪ s3 ∪ …∪ sn來代替。為方便起見，也稱s1 ∪ s2 ∪ s3 ∪ …∪ sn為g的子句形，即：

s1 ∪ s2 ∪s3 ∪ …∪ sn不可滿足

sg＝s1 ∪ s2 ∪ s3 ∪ …∪ sn。根據以上定理可對一個謂詞表達式分而治之，化整為零，大大減少了計算復雜度。

例2－3

對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？

用一階邏輯表示這個問題，并建立子句集。

解：

這里我們首先引入謂詞：

p(x, y)表示x是y的父親

q(x, y)表示x是y的祖父

ans(x)表示問題的解答

于是有：

對于第一個條件，“如果y是x的父親，z又是y的父親，則z是x的祖父”，一階邏輯表達式如下：

a1：(x)(y)(z)(p(x, y)∧p(y, z)→q(x, z))

則把a1化為合取范式，進而化為skolem標準形，表示如下：

s a1：～p(x ,y)∨～p(y, z)∨q(x, z)

對于第二個條件：“每個人都有父親”，一階邏輯表達式如下：

a2：(y)(x)p(x, y)

化為skolem標準形，表示如下：

s a2：p(f(y), x)

結論：某個人是它的祖父

b：(x)(y)q(x, y)

否定后得到子句：

s～b：～q(x, y)∨ans(x)

則得到的相應的子句集為：{ s a1，s a2，s～b }

解畢。

謂詞邏輯公式篇四

2.3 謂詞邏輯歸結法基礎

由于謂詞邏輯與命題邏輯不同，有量詞、變量和函數，所以在生成子句集之前要對邏輯公式做處理，具體的說就是要將其轉化為skolem標準形，然后在子句集的基礎上再進行歸結，雖然基本的歸結的基本方法都相同，但是其過程較之命題公式的歸結過程要復雜得多。

本節針對謂詞邏輯歸結法介紹了skolem標準形、子句集等一些必要的概念和定理。

2．3．1 skolem 標準形 skolem標準形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為skolem標準形，任何一個謂詞公式都可以化為與之對應的skolem標準形。但是，skolem標準形不唯一。

前束范式：a是一個前束范式，如果a中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。

skolem標準形的轉化過程為，依據約束變量換名規則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式g轉換成為前束范式

前束范式的形式為：

(q1x1)(q2x2)…(qnxn)m(x1,x2,…,xn)

即： 把所有的量詞都提到前面去。

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達式中的所有同名變量。所以將量詞提到公式最前端時存在約束變量換名問題。要嚴守規則。

約束變量換名規則：

(qx)m（x）（qy）m（y）

(qx)m（x,z）（qy）m（y,z）

量詞否定等值式：

～(x)m（x）（y）～ m（y）

～(x)m（x）（y）～ m（y）

量詞分配等值式：

(x)(p（x）∧q（x）)(x)p（x）∧(x)q（x）

(x)(p（x）∨ q（x）)(x)p（x）∨(x)q（x）

消去量詞等值式：設個體域為有窮集合（a1, a2, …an）

(x)p（x）p（a1）∧ p（a2）∧ …∧ p（an）

(x)p（x）p（a1）∨ p（a2）∨ … ∨ p（an）

量詞轄域收縮與擴張等值式：

(x)(p（x）∨ q)(x)p（x）∨ q

(x)(p（x）∧ q)(x)p（x）∧ q

(x)(p（x）→ q)(x)p（x）→ q

(x)(q → p（x）)q →(x)p（x）

(x)(p（x）∨ q)(x)p（x）∨ q

(x)(p（x）∧ q)(x)p（x）∧ q

(x)(p（x）→ q)(x)p（x）→ q

(x)(q → p（x）)q →(x)p（x）消去量詞

量詞消去原則：

1)消去存在量詞“"，即，將該量詞約束的變量用任意常量（a, b等）、或全稱變量的函數(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數。

2)略去全程量詞”“，簡單地省略掉該量詞。

skolem 定理：

謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。

注意：公式g的skolem標準形同g并不等值。例題2-2

將下式化為skolem標準形：

～(x)(y)p(a, x, y)→(x)(～(y)q(y, b)→r(x))

解：

第一步，消去→號，得：

～(～(x)(y)p(a, x, y))∨(x)(～～(y)q(y, b)∨r(x))

第二步，～深入到量詞內部，得：

(x)(y)p(a, x, y)∧～(x)((y)q(y, b)∨r(x))

＝(x)(y)p(a, x, y)∧(x)((y)～q(y, b)∧～r(x))

第三步，全稱量詞左移，（利用分配律），得

(x)((y)p(a, x, y)∧(y)(～q(y, b)∧～r(x)))

第四步，變元易名，存在量詞左移，直至所有的量詞移到前面，得：

(x)((y)p(a, x, y)∧(y)(～q(y, b)∧～r(x)))

＝(x)((y)p(a, x, y)∧(z)(～q(z, b)∧～r(x)))

=(x)(y)(z)(p(a, x, y)∧～q(z, b)∧～r(x))

由此得到前述范式

第五步，消去”“（存在量詞），略去”“全稱量詞

消去(y)，因為它左邊只有(”x)，所以使用x的函數f(x)代替之，這樣得到：

(x)(z)(p(a, x, f(x))∧～q(z, b)∧～r(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(p(a, x, f(x))∧～q(g(x), b)∧～r(x))

則，略去全稱變量，原式的skolem標準形為：

p(a, x, f(x))∧～q(g(x), b)∧～r(x)2.3.2子句集

文字：不含任何連接詞的謂詞公式。

子句：一些文字的析取（謂詞的和）。

子句集：所有子句的集合

對于任一個公式g，都可以通過skolem標準形，標準化建立起一個子句集與之相對應。因為子句不過是一些文字的析取，是一種比較簡單的形式，所以對g的討論就用對子句集s的討論來代替，以便容易處理。

子句集s可由下面的步驟求取：

1.謂詞公式g轉換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成skolem標準形

3.將skolem標準形中的各個子句提出，表示為集合形式

教師提示：為了簡單起見，子句集生成可以理解為是用“，”取代skolem標準形中的“λ”，并表示為集合形式。

注意：skolem標準形必須滿足合取范式的條件。即，在生成子句集之前邏輯表達式必須是各“謂詞表達式”或“謂詞或表達式”的與。定理

謂詞表達式g是不可滿足的當且僅當 其子句集s是不可滿足的

公式g與其子句集s并不等值，但它們在不可滿足的意義下是一致的。因此如果要證明a1∧a2∧a3→b，只需證明g＝ a1∧a2∧a3∧～b的子句集是不可滿足的，這也正是引入子句集的目的。

注意：公式g和子句集s雖然不等值，但是它們的之間一般邏輯關系可以簡單的說明為：g真不一定s真，而s真必有g真，即，s g。在生成skolem標準形時將存在量詞用常量或其他變量的函數代替，使得變量討論的論域發生了變化，即論域變小了。所以g不能保證s真。定理的推廣

對于形如g = g1λ g2λ g3λ …λ gn 的謂詞公式，g的子句集的求取過程可以分解成幾個部分單獨處理。如果gi的子句集為si，則

有 s' = s1 ∪ s2 ∪ s3 ∪ …∪ sn，雖然g的子句集不為s'，但是可以證明：

sg 與s1 ∪ s2 ∪ s3 ∪ …∪sn在不可滿足的意義上是一致的。

即sg 不可滿足 s1 ∪ s2 ∪s3 ∪ …∪ sn不可滿足

謂詞邏輯公式篇五

習題二

(參考答案)2.1 在謂詞邏輯中將下面命題符號化，（1）高斯是數學家，但不是文學家。

p(x):x是數學家.s(x):x是文學家.a:高斯 p(a)??s(a)（2）如果小張比小李高，小李比小趙高，則小張比小趙高。

p(x,y):x比y高.a:小張.b:小李.c:小趙

(p(a,b)?p(b,c))?p(a,c)（3）魚都會在水里游。

p(x)::x是魚

r(x)x都會在水里游.?x(p(x)? r(x))（4）情商比智商更重要。

p(x,y):x比y更重要.a:情商.b:智商 p(a,b)（5）并不是所有的人都愛看電影。

p(x):x是人.g(x):愛看電影.??x(p(x)? g(x))或

?x(p(x)?? g(x))（6）有的人愛吃醋，并且沒有不愛美的人。

p(x):x是人.g(x):x愛吃醋.r(x):x愛美.?x(p(x)?g(x))??x(p(x)? r(x))2.2 利用二元謂詞將下面命題符號化。（1）每列火車都比某些汽車快。

p(x,y):x比y快.m(x):x是火車.g(y):y是汽車 ?x(m(x)??y(g(y)?p(x,y))（2）某些汽車比所有火車慢。

p(x,y):x比y慢.m(x):x是汽車.g(y):y是火車 ?x(m(x)??y(g(y)?p(x,y)))2.3 在謂詞邏輯中將下面命題符號化，要求使用全稱量詞與存在量詞兩種方法。（1）有的江西人沒去過廬山。p(x):x是江西人.m(x):x去過廬山.?x(p(x)?? m(x))或

??x(p(x)? m(x))（2）沒有人不愛自己的祖國。

p(x):x是人.m(x):x愛自己的祖國 ??x(p(x)?? m(x))或

?x(p(x)? m(x))（3）并非每個清華大學的學生都是優等生。

p(x):x是清華大學的學生.m(x):x是優等生 ?x(p(x)?? m(x))

或

??x(p(x)? m(x))（4）沒有不努力的大學生。

m(x):x是大學生

p(x):x是努力的.??x(m(x)?? p(x)).或

?x(m(x)? p(x))2.4 指出下列謂詞公式中的量詞及其轄域，指出各自由變元和約束變元。如果有同名而引起混淆的情況，要求使用換名規則或代替規則改寫。

（1）?x(p(x)??yq(y))；

?x的轄域為p(x)??yq(y).其中：x是約束出現 ?y的轄域為q(y).其中：y是約束出現

（2）?x(f(x)? h(x,y))?? h(x)；

?x的轄域為f(x)? h(x,y).其中：x是約束出現.y是自由出現 而原式中? h(x)中x是自由出現 更改后的為：?x(f(x)? h(x,y))??h(z)（3）?x(p(x)??xq(x,z)??yr(x, y))?q(x, y)；

?x的轄域為p(x)??xq(x,z)??yr(x, y).其中：z是自由出現.x ,y是約束出現.?x的轄域為q(x,z).其中：x是約束出現.z是自由出現 ?y的轄域為r(x, y).其中：y是約束出現.x是自由出現 q(x, y)中x、y是自由出現

更改后的為：?x(p(x)??u q(u,z)??yr(v, y))?q(s, t)（4）p(x)?(?y?x(p(x)?b(x,y))?p(x))；

?y與?x的轄域為(p(x)?b(x,y)).其中：x、y是約束出現 更改后的為：p(u)?(?y?x(p(x)?b(x,y))? p(u)2.5 設個體域d={1,2,3}，消去下列各公式中的量詞。（1）?xp(x)??yq(y)；(p(1)? p(2)? p(3))?(q(1)? q(2)? q(3))（2）?xp(x)??yq(y)；(p(1)? p(2)? p(3))?(q(1)? q(2)? q(3))（3）?x?y p(x,y)。(p(1,1)? p(1,2)? p(1,3))?(p(2,1)? p(2,2)? p(2,3))?(p(3,1)? p(3,2)? p(3,3))2.6 設一元謂詞f(x):x?3,g(x):x?5,r(x);x?7，解釋i為：個體域d={0,2,6 }，在i下求下列各式的真值。

（1）?x(f(x)?g(x));(f(0)?g(0))?(f(2)?g(2))?(f(6)?g(6))?f（2）?x(r(x)?f(x))?g(5);((r(0)? f(0))?(r(2)? f(2))?(r(6)? f(6)))?g(5)?f（3）?x(f(x)?g(x))。

(f(0)?g(0))?(f(2)?g(2))?(f(6)?g(6))?t 2.7 取個體域為整數集，給定下列各公式，判定命題的真值。（1）?x?y(x?y?1)

假（2）?x(x?y?x);

不是命題

（3）?x?y?z(x?y?z)；

真（4）?x?y?z(x + y = z)；

真（5）?y?x(x?y?2)；

真（6）?x?y(x?y?2y)。

假 2.8 求下列各式的前束范式：（1）?(?xp(x)??yp(y))； ?x?y(p(x)??p(y))（2）?(?xp(x)??y?zq(y,z))； ?x?y?z(p(x)?? q(y,z))（3）(??xf(x)??yg(y))?(f(u)??zh(z))； ?x?y?z((?f(x)?g(y))?(f(u)?h(z)))（4）?xf(y,x)??yg(y)； ?x?y(f(u,x)?g(y))

（5）?x(f(x,y)??yg(x,y))。?x?y(f(x,u)? g(y))

2.9 構造下列推理的證明：

（1）前提：?x(f(x)? h(x))，? h(y)

結論：?x(?f(x))

證明：①?x[f(x)?h(x)]

前提引入

②f(y)?h(y)

①ui

③?h(y)

前提引入

④?f(y)

②③拒取式

⑤?x[?f(x)]

④ug（2）前提：?x(f(x)?g(x)?h(x))，?x(f(x)?r(x))

結論：?x(f(x)?r(x)?g(x))

證明：①?x(f(x)?r(x))

前提引入

②f(c)? r(c)

①ei

③f(c)

②化簡規則

④?x(f(x)?g(x)?h(x))

前提引入 ⑤f(c)? g(c)?h(c)

④ui

⑥g(c)?h(c)

③⑤假言推理

⑦g(c)

⑥化簡規則

⑧f(y)?r(y)? g(y)

②⑦合取規則

⑨?x[f(x)?r(x)? g(x)]

⑧eg（3）前提：??x(f(x)?h(x))，?x(g(x)?h(x))結論：g(y)??f(y)

證明：①??x(f(x)?h(x))

前提引入

②?x(?f(x)??h(x))

①置換規則 ③?x(h(x)??f(x))

②置換規則 ④h(y)??f(y)

③ui ⑤?x(g(x)?h(x))

前提引入 ⑥g(y)?h(y)

⑤ui ⑦g(y)??f(y)

④⑥假言三段論

（4）前提：?x(w(x)??b(x))，?x(b(x)?r(x))，?x(?r(x))結論：?x(?w(x))證明：①?x?r(x)

前提引入

②?r(c)

①ei ③?x(b(x)?r(x))

前提引入 ④b(c)?r(c)

③ui ⑤b(c)

②④析取三段論 ⑥?x(w(x)??b(x))

前提引入 ⑦w(c)??b(c)

⑥ui ⑧? w(c)

⑤⑦拒取式 ⑨?x(?w(x))

⑧eg 2.10 在謂詞邏輯中，構造下面推理的證明。個體域是人的集合。

（1）每個科學工作者都是勤奮的，每個既勤奮又聰明的人在他的事業中都將獲得成功，劉濤是科學工作者并且是聰明的，所以劉濤在他的事業中將獲得成功。

f(x):x是科學工作者

g(x):x是勤奮的人

h(x):x是聰明的人

r(x):x在他的事業中都將獲得成功

a: 劉濤

前提：?x(f(x)?g(x))?x((g(x)?h(x))?r(x))

f(a)?h(a)結論：r(a)證明：①?x(f(x)?g(x))

前提引入

②f(a)?g(a)

①ui

③f(a)?h(a)

前提引入

④f(a)

③化簡規則

⑤g(a)

②④假言推理

⑥h(a)

③化簡規則

⑦g(a)?h(a)

⑤⑥合取規則

⑧?x((g(x)?h(x))?r(x))

前提引入

⑨(g(a)? h(a))?r(a)

⑧ui

⑩r(a)

⑧⑨假言推理

（2）每個學術會的成員都是工人并且是專家，有些成員是青年人，所以有的成員是青年專家

f(x):x是學術會的成員

g(x):x是工人

h(x):x是專家 r(x):x是青年人

前提：?x(f(x)?(g(x)?h(x)))

?x(f(x)?r(x))結論：?x(f(x)?h(x)?r(x))證明：①?x(f(x)?r(x))

前提引入

②f(c)?r(c)

①ei ③f(c)

②化簡規則

④?x(f(x)?(g(x)?h(x)))

前提引入

⑤f(c)?(g(c)?h(c))

④ui

⑥g(c)?h(c)

③⑤假言推理

⑦h(c)

⑥化簡規則

⑧f(c)? r(c)?h(c)

②⑦合取規則

⑨?x(f(x)?h(x)?r(x))

⑧eg（3）每一個大學生不是文科生就是理科生；有的大學生是優等生；小張不是文科生但他是優等生。因此，如果小張是大學生，他就是理科生。

p(x):x是大學生

g(x):x是文科生

h(x):x是理科生

r(x):x是優等生

a:是小張

前提：?x(p(x)?(g(x)?h(x)))

結論：p(a)?h(a)證明：①?x(p(x)? r(x))

②p(a)? r(a)

③p(a)

④?g(a)? r(a)

⑤?g(a)

⑥?x(p(x)?(g(x)?h(x)))

⑦p(a)?(g(a)?h(a))

⑧g(a)?h(a)

⑨h(a)

⑩h(a)??p(a)

⑾p(a)?h(a)

?x(p(x)? r(x))

?g(a)? r(a)

前提引入

①ei ②化簡規則

前提引入

④化簡規則

前提引入

⑥ui

③⑦假言推理

⑤⑧析取三段論

⑨附加規則

⑩置換規則