1第二章謂詞邏輯2本章學習目標

命題邏輯中原子命題是最小的單位，不能夠再進行分解，這給推理帶來了很大局限性，本章引入謂詞邏輯。學習關于謂詞邏輯的相關概念和定理，解決實際問題。3主要內容

2.1謂詞邏輯命題的符號化

2.2謂詞邏輯公式與解釋2.3謂詞邏輯約束公式的等價與蘊涵2.4前束范式2.5謂詞演算的推理理論42.1謂詞邏輯命題的符號化2.1.1個體詞與謂詞2.1.2量詞2.1.3謂詞邏輯中命題的符號化5命題邏輯的局限性limitation不能描述性質因集合的個體不同而不同例:人總是要死的蘇格拉底是人蘇格拉底是要死的用命題邏輯無法描述62.1謂詞邏輯命題的符號化2．謂詞：用來刻畫個體詞的性質或個體詞之間關系的詞

一般來說，“x是A”類型的命題可以用A（x）表達。對于

“x大于y”這種兩個個體之間關系的命題，可表達為B（x，y），這里B表示“…大于…”謂詞。我們把A（x）稱為一元謂詞，

B（x，y）稱為二元謂詞，M（a，b，c）稱為三元謂詞，依次類推，通常把二元以上謂詞稱作多元謂詞。

2.1.1個體詞與謂詞1．個體詞：個體詞是指研究對象中不依賴于人的主觀而獨立存在的具體的或抽象的客觀實體

個體常項或個體常元：個體變項或個體變元：個體域或論域：72.1謂詞邏輯命題的符號化解（1）設謂詞G（x）：x是素數，a：4，b：8；（1）中的題符號化為謂詞的蘊涵式：G（a）→G（b）由于此蘊涵式的前件為假，所以（1）中的命題為真。（2）設謂詞H（x，y）：x小于y，a：1，b：2，c：5，d：4（2）中的命題符號化為謂詞的蘊涵式：H（a，b）→H（c，d）由于此蘊涵式的前件為真，后件為假，所以（2）中的命題為假。例2.1將下列命題在謂詞邏輯中符號化，并討論它們的真值：（1）只有4是素數，8才是素數。（2）如果1小于2，則5小于4。2.1.1個體詞與謂詞82.1謂詞邏輯命題的符號化全稱量詞對于日常生活和數學中出現的“一切的”、“任意的”、“所有的”、“每一個”、“都”、“凡”等詞統稱為全稱量詞，用符號“”表示。并用x，y表示個體域中的所有個體，用（x）F（x），（y）F（y）等表示個體域中的所有個體具有性質F。

存在量詞對日常生活和數學中常用的“存在”、“存在一個”、“有一個”、“至少有一個”、“有些”、“有的”等詞統稱為存在量詞，用符號“”表示。并用x，y表示個體域中有的個體，用（x）F（x），（y）F（y）等表示個體域中有的個體具有性質F。

2.1.2量詞92.1謂詞邏輯命題的符號化解（a）令F（x）：x要死的；G（x）：x天生就近視。（1）在個體域D1中除人外，沒有其他的事物，因而（1）可符號化為：xF（x）（2）在個體域D1中有些人是天生就近視，因而（2）可符號化為例2.1.2在個體域分別限制為（a）和（b）條件時，將下面的命題符號化：（1）所有人都是要死的。（2）有的人天生就近視。其中：（a）個體域D1為人類集合。（b）個體域D2為全總個體域。2.1.3謂詞邏輯中命題的符號化

102.1謂詞邏輯命題的符號化謂詞的蘊涵式：xG（x）（b）在個體域D2中除人外，還有其他的事物，因而在將（1）、（2）符號化時，必須考慮先將人分離出來，令M（x）：x是人。在D2中，（1）、（2）可分別描述如下：（1）對于宇宙間的一切事物，如果事物是人，則他是要死的。（2）在宇宙間存在著天生就近視的人。將（1）、（2）分別符號化為：（1）

x（M（x）F（x））（2）

x（M（x）G（x））在個體域D1、D2中命題（1）、（2）都是真命題。2.1.3謂詞邏輯中命題的符號化

112.1謂詞邏輯命題的符號化例2.1.3在個體域分別限制為（a）和（b）條件時，將下面的命題符號化：（1）對任意的x，都有x2-5x+6

=（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）個體域D1為自然數集合。（b）個體域D2為實數集合。2.1.3謂詞邏輯中命題的符號化

12解（a）令F（x）：x2-5x+6

=（x-2）（x-3）；G（x）：x+1=0。（1）可符號化為：xF(x)（2）可符號化為：xG（x）在個體域D1中命題（1）為真命題，命題（2）為假命題。（b）在個體域D2中（1）、（2）符號化分別為（1）xF（x）（2）xG（x）在個體域D2中命題（1）、（2）都是真命題。2.1謂詞邏輯命題的符號化2.1.3謂詞邏輯中命題的符號化

13例2.1.4將下列命題符號化，并指出真值情況。（1）沒有人登上過月球。（2）所有人的頭發未必都是黑色的。解個體域為全總個體域，令M（x）：x是人。（1）令F（x）：x登上過月球。命題（1）符號化為：x（M（x）∧F（x））設a是1969年登上月球完成阿波羅計劃的一名美國人，則M（a）∧F（a）為真，故命題（1）為假。（2）令H（x）：x的頭發是黑色的。命題（2）可符號化為：x（M（x）H（x））我們知道有的人頭發是褐色的，所以x（M（x）H（x））為假，故命題（2）為真。

2.1謂詞邏輯命題的符號化2.1.3謂詞邏輯中命題的符號化

14例2.1.5將下列命題符號化。（1）火車比汽車跑得快。（2）有的火車比所有汽車跑得快。（3）并不是所有的火車比汽車跑得快。（4）不存在完全相同的兩輛汽車。解設個體域為全總個體域。令C（x）：x是火車；G（y）：y是汽車；Q（x，y）：x比y跑得快；S（x，y）：x和y相同。這4個命題分別符號化為：（1）（x）（y）（C（x）∧G（y）Q（x，y））；（2）（x）（C（x）∧（y）（G（y）Q（x，y）））；（3）（x）（y）（C（x）∧G（y）Q（x，y））；（4）（x）（

y）（G（x）∧G（y）∧S（x，y）））。2.1謂詞邏輯命題的符號化2.1.3謂詞邏輯中命題的符號化

152.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

2.2.2謂詞的約束和替換

2.2.3謂詞邏輯公式的解釋

162.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

定義2.2.1謂詞邏輯中項的定義：（1）任何一個個體變元或個體常元是項；（2）若f（x1，x2，…，xn）是任意的n元函數，t1，t2，…，tn是任意的n個項，則f（t1，t2，…，tn）是項；（3）由有限次使用（1），（2）得到的表達式是項；定義2.2.2設P（x1，x2，…，xn）是n元謂詞公式，其中，x1x2，…，xn是個體變項，則稱P（x1，x2，…，xn）為謂詞演算的原子公式。172.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

定義2.2.3謂詞演算的合式公式定義如下：（1）原子公式是合式公式；（2）若A是合式公式，則（﹁A）也是合式公式；（3）若A，B是合式公式，則（A∧B）、（A∨B）、（A→B）、（A?B）是合式公式；（4）若A是合式公式，則xA、xA是合式公式；（5）只有有限次地應用（1）~（4）構成的符號串才是合式公式。18例2.2.1在謂詞邏輯中將下列命題符號化。（1）不存在最大的數。（2）計算機系的學生都要學離散數學。解取個體域為全總個體域。（1）令F（x）：x是數，L（x，y）：x大于y；則命題（1）符號化為﹁x（F（x）∧y（F（y）→L（x，y）））（2）令C（x）：x是計算機系的學生，G（x）：x要學離散數學;則命題（2）可符號化為：x（C（x）→G（x））2.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

19例2.2.2將下列命題符號化。（1）盡管有人聰明，但并非所有人都聰明。（2）這只大紅書柜擺滿了那些古書。解（1）令C（x）：x聰明；M（x）：x是人。則命題（1）可符號化為x（M（x）∧C（x））∧﹁x（M（x）→C（x））（2）令F（x，y）：x擺滿了y；R（x）：x是大紅書柜；Q（x）:x是古書；a：這只；b：那些。則命題（2）可符號化為R（a）∧Q（b）∧F（a，b）2.2.1謂詞邏輯的合式公式

2.2謂詞邏輯公式與解釋201．約束變元與自由變元的概念定義2.2.4在公式xF（x）和xF（x）中，稱x為指導變元，F（x）為相應量詞的轄域或作用域。在x和x的轄域中，x的所有出現都稱為約束出現，F（x）中不是約束出現的其他變元均稱為自由出現。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋21例2.2.3指出下列各式量詞的轄域及變元的約束情況：（1）x（F（x，y）→G（x，z））（2）x（P（x）→yR（x，y））（3）x（F（x）→G（y））→y（H（x）∧M（x，y，z））2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋22解（1）對于x的轄域是A=（F（x，y）→G（x，z）），在A中，x是約束出現的，而且約束出現兩次，y，z均為自由出現，而且各自由出現一次。（2）對于x的轄域是（P（x）→yR（x，y）），y的轄域是R（x，y），x，y均是約束出現的。（3）對于x的轄域是（F（x）→G（y）），其中x是約束出現的，而y是自由出現的。對y的轄域是（H（x）∧M（x，y，z）），其中y是約束出現的，而x，z是自由出現的。在整個公式中，x約束出現一次，自由出現兩次，y約束出現一次，自由出現一次，z僅自由出現一次。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋232．約束變元的換名與自由變元的代入約束變元換名的規則：

（1）將量詞的作用變元及其轄域中所有相同符號的變元用一個新的變元符號代替，公式的其余部分不變。（2）新的變元符號是原公式中沒有出現的。（3）用（1）、（2）得到的新公式與原公式等值。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋24例2.2.4對公式x（P（x）→R（x，y））∧Q（x，y）進行換名。解對約束變元x換名為t后為t（P（t）→R（t，y））∧Q（x，y）同理，對公式中的自由變元也可以更改，這種更改稱作代入。自由變元的代入規則是：（1）對于謂詞公式中的自由變元，可以代入，此時需要對公式中出現該自由變元的每一處進行代入。（2）用以代入的變元與原公式中所有變元的名稱都不能相同。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋25例2.2.5對公式x（F（x）→G（x，y））∧yH（y）代入。解對y實施代入，經過代入后原公式為x（F（x）→G（x，t））∧yH（y）另外，量詞作用域中的約束變元，當論域的元素是有限時，個體變元的所有可能的取代是可以枚舉的。設論域元素為a1，a2，…，an，則xA（x）

A（a1）∧A（a2）∧…∧A（an）

xA（x）

A（a1）∨A（a2）∨…∨A（an）。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋26定義2.2.5沒有自由變元的公式稱為閉式。例如：（x）（

y）（P（x）→R（x，y））∧（x）（y）Q（x，y）是閉式。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋272.2.3謂詞邏輯公式的解釋定義2.2.6謂詞邏輯公式的一個解釋I，是由非空區域D和對G中常項符號、函數符號、謂詞符號以下列規則進行的一組指定組成：（1）對每一個常項符號指定D中一個元素。（2）對每一個n元函數符號，指定一個函數。（3）對每一個n元謂詞符號，指定一個謂詞。顯然，對任意公式G，如果給定G的一個解釋I，則G在I的解釋下有一個真值，記作TI（G）。2.2謂詞邏輯公式與解釋28例2.2.6設有公式：（x）（y）（F（x，y）→G（x，y））。在如下給出的解釋下，判斷該公式的真值。解

（1）解釋I為：D：整數集合。F（x，y）：x+y＝0G（x，y）：x>y因為對任意的x，任意yD，有x+y＝0為“假”，所以無論G（x，y）為“真”或“假”，都有F（x，y）→G（x，y）為“真”所以（x）（y）（F（x，y）→G（x，y））為“真”。2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋29（2）解釋I為：D：整數集合，F（x，y）：xy＝0,G（x，y）：x＝y。因為對任意的x0，當y＝0時，有F（x，y）→G（x，y）為“假”，即有（y）（F（x，y）→G（x，y））為“假”。對x＝0，當y0時，有F（x，y）→G（x，y）為“假”，即有（y）（F（x，y）→G（x，y））為“假”。所以，對任意的xD，都有（y）（F（x，y）→G（x，y））為“假”。即有：（x）（y）（F（x，y）→G（x，y））為“假”。2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋30例例2.2.7指出下面公式在解釋I下的真值。（1）G=x（P（f（x））∧Q（x，f（a）））；（2）H=x（P（x）∧Q（x，a））。給出如下的解釋I：D={2，3}；a：2；f（2）：3、f（3）：2；P（2）：0、P（3）：1；Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋312.2謂詞邏輯公式與解釋2.2.3謂詞邏輯公式的解釋解（1）TI（G）=TI（（P（f（2））∧Q（2，f（2）））∨（P（f（3））∧Q（3，f（2））））

=TI（（P（3）∧Q（2，3））∨（P（2）∧Q（3，3））

=（1∧1）∨（0∧1）

=1（2）TI（H）=TI（P（2）∧Q（2，2）∧P（3）∧Q（3，2））

=0∧1∧1∧0=032定義2.2.7若存在解釋I，使得G在解釋I下取值為真，則稱公式G為可滿足的，簡稱I滿足G。若不存在解釋I，使得I滿足G，則稱公式G為永假式（或矛盾式）。若G的所有解釋I都滿足G，則稱公式G為永真式（或重言式）。2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋33例2.2.8討論下面公式的類型：（1）（x）G（x）→（x）G（x）（2）（x）（y）﹁F（x，y）∧（x）（y）F（x，y）（3）（x）（F（x）→G（x））2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋34解（1）公式在任何解釋下的含義是：如果個體域中的每個元素都有性質G，則論域中的某些元素具有性質G。（x）G（x）為真時，（x）G（x）也為真，所以公式（x）G（x）→（x）G（x）為永真式。（2）公式在任何解釋下的含義是：個體域I中的每個x，y都不具備關系F，但存在某些元素具有關系F。這兩個命題矛盾，所以公式（x）（y）﹁F（x，y）∧（x）（y）F（x，y）為永假式。3）取解釋I1：個體域為實數集合，F（x）：x是整數，G（x）：x是有理數。在解釋I1下公式（x）（F（x）→G（x））為真，因而公式不為矛盾式。2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋352.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式1．命題公式的推廣

2．量詞的轉換

3．量詞轄域的擴張與收縮

4．量詞的分配律

2.3.2謂詞邏輯的蘊涵公式2.3.3多個量詞的使用362.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定義2.3.1設A、B是命題邏輯中的任意兩個公式，設它們有共同的個體域E，若對任意的解釋I都有TI（A）=TI（B），則稱公式A、B在E上是等價的，記作AB。37

1．命題公式的推廣

在命題邏輯中，任意一個永真式，其中同一命題變元用同一命題公式代換，所得到的公式仍為永真式，把這個情況推廣到謂詞邏輯之中，命題邏輯中的永真公式所有相同的變元用謂詞邏輯中的同一公式代替，所得到的謂詞公式為永真式，所以命題演算中的等價公式都可以推廣到謂詞邏輯中使用。例如（x）G（x）

﹁﹁（x）G（x）（x）（A（x）→B（x））（x）（﹁A（x）∨B（x））（x）﹁（F（x）∨G（x））（x）（﹁F（x）∧﹁G（x））2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式382．量詞的轉換

定理2.3.1設G（x）是謂詞公式，有關量詞否定的兩個等價公式：（1）﹁（x）G（x）（x）﹁G（x）（2）﹁（x）G（x）（x）﹁G（x）證明

（1）設個體域是有限的為：D={a1，a2，…，an}，則有

﹁（x）G（x）

﹁（G（a1）∨

G（a2）∨…∨G（an））

﹁G（a1）∧

﹁G（a2）∧…∧﹁G（an）

（x）﹁G（x）2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式39定理2.3.1設G（x）是謂詞公式，有關量詞否定的兩個等價公式：（1）﹁（x）G（x）（x）﹁G（x）（2）﹁（x）G（x）（x）﹁G（x）（2）設個體域是有限的為：D={a1，a2，…，an}，則有

﹁（x）G（x）

﹁（G（a1）∨

G（a2）∨…∨G（an））

﹁G（a1）∧

﹁G（a2）∧…∧﹁G（an）

（x）﹁G（x）2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式403．量詞轄域的擴張與收縮

定理2.3.2設G（x）是任意的含自由出現個體變項x的公式，B是不含x出現的公式，則有（1）（x）（G（x）∨B）（x）G（x）∨B（2）（x）（G（x）∧B）（x）G（x）∧B（3）（x）（G（x）→B）（x）G（x）→B（4）（x）（B→G（x））

B→（x）G（x）（5）（x）（G（x）∨B）（x）G（x）∨B（6）（x）（G（x）∧B）（x）G（x）∧B（7）（x）（G（x）→B）（x）G（x）→B(8）（x）（B→G（x））

B→（x）G（x）2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式41證明（1）設D是個體域，I為任意解釋，即用確定的命題及確定的個體代替出現在x（A（x）∨B）和xA（x）∨B中的命題變元和個體變元，于是得到兩個命題，若對x（A（x）∨B）代替之后所得命題的真值為真，此時必有A（x）∨B的真值為真；因而A（x）真值為真或B的真值為真，若B的真值為真，則xA（x）∨B的真值為真；若B的真值為假，則必有對D中任意x都使得A（x）的真值為真，所以x（A（x）∨B）為真，從而xA（x）∨B為真。2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式42證明若對x（A（x）∨B）代替之后所得命題的真值為假，則A（x）和B的真值必為假，因此xA（x）∨B的真值為假；所以x（A（x）∨B）為假，有xA（x）∨B為假。（2）、（5）和（6）證明與（1）類似，證明過程略。（3）x（A（x）→B）

x（

A（x）∨B）

xA（x）∨B

xA（x）∨B

xA（x）→B（4）、（7）、（8）證明與（3）類似，證明過程略。2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式434．量詞的分配律

定理2.3.3設G（x）、H（x）是任意包含約束出現個體變元x的公式，則有：(1)（x）（G（x）∧H（x））（x）G（x）∧（x）H（x）(2)（x）（G（x）∨H（x））（x）G（x）∨（x）H（x）2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式44證明

（1）設D是任一個體域，若（x）（G（x）∧H（x））的真值為真，則對任意aD，有G（a）和H（a）同時為真，即（x）G（x）為真、（x）H（x）為真，從而（x）

G（x）∧（x）H（x）為真。若（x）G（x）∧H（x））的真值為假，則對任意aD，有G（a）和H（a）不能同時為真，即（x）G（x）和

（x）H（x）的真值不能同時為真，從而（x）G（x）∧（x）H（x）的真值為假。綜上所述（x）（G（x）∧H（x））（x）G（x）∧（x）H（x）。2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式45證明（2）設D是任一個體域，若（x）（G（x）∨H（x））的真值為真，則存在aD，使得G（a）∨H（a）為真，即G（a）為真或H（a）為真，即（x）G（x）為真或（x）H（x）為真，從而（x）G（x）∨（x）H（x）為真。若（x）（G（x）∨H（x））的真值為假，則存在aD，使得G（a）∨H（a）為假，此時，G（a）為假，H（a）為假，從而（x）G（x）∨（x）H（x）的真值為假。綜上所述（x）（G（x）∨H（x））（x）G（x）∨（x）H（x）。2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式46要進行等價演算，除了以上重要的等值式外，還要記住下面三條規則：（1）置換規則（2）換名規則（3）代替規則2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式47例2.3.1證明下列各等價式（1）﹁（x）（F（x）∧G（x））（x）（F（x）→﹁G（x））（2）﹁（x）（F（x）→G（x））（x）（F（x）∧﹁G（x））證明

（1）﹁（x）（F（x）∧G（x））

（x）﹁（F（x）∧G（x））

（x）（﹁F（x）∨﹁G（x））

（x）（F（x）→﹁G（x））2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式48例2.3.1證明下列各等價式（1）﹁（x）（F（x）∧G（x））（x）（F（x）→﹁G（x））（2）﹁（x）（F（x）→G（x））（x）（F（x）∧﹁G（x））證明

（2）

﹁（x）（F（x）→G（x））

（x）﹁（F（x）→G（x））

（x）﹁（﹁F（x）∨G（x））

（x）（F（x）∧﹁G（x））2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式49定義2.3.2設A、B是謂詞邏輯中的任意兩個公式，若A→B是永真式，則稱公式A蘊涵公式B，記作AB。定理2.3.4下列蘊涵式成立（1）（x）A（x）∨（x）B（x）（x）（A（x）∨B（x））（2）（x）（A（x）∧B（x））（x）A（x）∧（x）B（x）（3）（x）（A（x）→B（x））（x）A（x）→（x）B（x）（4）（x）（A（x）→B（x））（x）A（x）→（x）B（x）（5）（x）A（x）→（x）B（x）（x）（A（x）→B（x））2.3謂詞邏輯約束公式的等價與蘊涵2.3.2謂詞邏輯的蘊涵公式50證明

（1）設xA（x）

xB（x）在任意解釋下的真值為真，即對個體域中的每一個x。都能使A（x）的真值為真或者對個體域中的每一個x都能使B（x）的真值為真，無論哪種情況，對于個體域中的每一個x都能使A（x）∨B（x）的真值為真。因此，蘊涵式xA（x）∨xB（x）