第二章謂詞邏輯(6學(xué)時(shí))

1第二章謂詞邏輯2本章學(xué)習(xí)目標(biāo)

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

2.1謂詞邏輯命題的符號(hào)化

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

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

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

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

2.1.1個(gè)體詞與謂詞1．個(gè)體詞：個(gè)體詞是指研究對(duì)象中不依賴于人的主觀而獨(dú)立存在的具體的或抽象的客觀實(shí)體

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

存在量詞對(duì)日常生活和數(shù)學(xué)中常用的“存在”、“存在一個(gè)”、“有一個(gè)”、“至少有一個(gè)”、“有些”、“有的”等詞統(tǒng)稱為存在量詞，用符號(hào)“”表示。并用x，y表示個(gè)體域中有的個(gè)體，用（x）F（x），（y）F（y）等表示個(gè)體域中有的個(gè)體具有性質(zhì)F。

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

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

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

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

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

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

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

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

13例2.1.4將下列命題符號(hào)化，并指出真值情況。（1）沒有人登上過月球。（2）所有人的頭發(fā)未必都是黑色的。解個(gè)體域?yàn)槿倐€(gè)體域，令M（x）：x是人。（1）令F（x）：x登上過月球。命題（1）符號(hào)化為：x（M（x）∧F（x））設(shè)a是1969年登上月球完成阿波羅計(jì)劃的一名美國人，則M（a）∧F（a）為真，故命題（1）為假。（2）令H（x）：x的頭發(fā)是黑色的。命題（2）可符號(hào)化為：x（M（x）H（x））我們知道有的人頭發(fā)是褐色的，所以x（M（x）H（x））為假，故命題（2）為真。

2.1謂詞邏輯命題的符號(hào)化2.1.3謂詞邏輯中命題的符號(hào)化

14例2.1.5將下列命題符號(hào)化。（1）火車比汽車跑得快。（2）有的火車比所有汽車跑得快。（3）并不是所有的火車比汽車跑得快。（4）不存在完全相同的兩輛汽車。解設(shè)個(gè)體域?yàn)槿倐€(gè)體域。令C（x）：x是火車；G（y）：y是汽車；Q（x，y）：x比y跑得快；S（x，y）：x和y相同。這4個(gè)命題分別符號(hào)化為：（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謂詞邏輯命題的符號(hào)化2.1.3謂詞邏輯中命題的符號(hào)化

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

2.2.2謂詞的約束和替換

2.2.3謂詞邏輯公式的解釋

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

定義2.2.1謂詞邏輯中項(xiàng)的定義：（1）任何一個(gè)個(gè)體變?cè)騻€(gè)體常元是項(xiàng)；（2）若f（x1，x2，…，xn）是任意的n元函數(shù)，t1，t2，…，tn是任意的n個(gè)項(xiàng)，則f（t1，t2，…，tn）是項(xiàng)；（3）由有限次使用（1），（2）得到的表達(dá)式是項(xiàng)；定義2.2.2設(shè)P（x1，x2，…，xn）是n元謂詞公式，其中，x1x2，…，xn是個(gè)體變項(xiàng)，則稱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）只有有限次地應(yīng)用（1）~（4）構(gòu)成的符號(hào)串才是合式公式。18例2.2.1在謂詞邏輯中將下列命題符號(hào)化。（1）不存在最大的數(shù)。（2）計(jì)算機(jī)系的學(xué)生都要學(xué)離散數(shù)學(xué)。解取個(gè)體域?yàn)槿倐€(gè)體域。（1）令F（x）：x是數(shù)，L（x，y）：x大于y；則命題（1）符號(hào)化為﹁x（F（x）∧y（F（y）→L（x，y）））（2）令C（x）：x是計(jì)算機(jī)系的學(xué)生，G（x）：x要學(xué)離散數(shù)學(xué);則命題（2）可符號(hào)化為：x（C（x）→G（x））2.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

19例2.2.2將下列命題符號(hào)化。（1）盡管有人聰明，但并非所有人都聰明。（2）這只大紅書柜擺滿了那些古書。解（1）令C（x）：x聰明；M（x）：x是人。則命題（1）可符號(hào)化為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）可符號(hào)化為R（a）∧Q（b）∧F（a，b）2.2.1謂詞邏輯的合式公式

2.2謂詞邏輯公式與解釋201．約束變?cè)c自由變?cè)母拍疃x2.2.4在公式xF（x）和xF（x）中，稱x為指導(dǎo)變?cè)?，F(xiàn)（x）為相應(yīng)量詞的轄域或作用域。在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，F(xiàn)（x）中不是約束出現(xiàn)的其他變?cè)Q為自由出現(xiàn)。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋21例2.2.3指出下列各式量詞的轄域及變?cè)募s束情況：（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）對(duì)于x的轄域是A=（F（x，y）→G（x，z）），在A中，x是約束出現(xiàn)的，而且約束出現(xiàn)兩次，y，z均為自由出現(xiàn)，而且各自由出現(xiàn)一次。（2）對(duì)于x的轄域是（P（x）→yR（x，y）），y的轄域是R（x，y），x，y均是約束出現(xiàn)的。（3）對(duì)于x的轄域是（F（x）→G（y）），其中x是約束出現(xiàn)的，而y是自由出現(xiàn)的。對(duì)y的轄域是（H（x）∧M（x，y，z）），其中y是約束出現(xiàn)的，而x，z是自由出現(xiàn)的。在整個(gè)公式中，x約束出現(xiàn)一次，自由出現(xiàn)兩次，y約束出現(xiàn)一次，自由出現(xiàn)一次，z僅自由出現(xiàn)一次。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋232．約束變?cè)膿Q名與自由變?cè)拇爰s束變?cè)獡Q名的規(guī)則：

（1）將量詞的作用變?cè)捌漭犛蛑兴邢嗤?hào)的變?cè)靡粋€(gè)新的變?cè)?hào)代替，公式的其余部分不變。（2）新的變?cè)?hào)是原公式中沒有出現(xiàn)的。（3）用（1）、（2）得到的新公式與原公式等值。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋24例2.2.4對(duì)公式x（P（x）→R（x，y））∧Q（x，y）進(jìn)行換名。解對(duì)約束變?cè)獂換名為t后為t（P（t）→R（t，y））∧Q（x，y）同理，對(duì)公式中的自由變?cè)部梢愿?，這種更改稱作代入。自由變?cè)拇胍?guī)則是：（1）對(duì)于謂詞公式中的自由變?cè)梢源?，此時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行代入。（2）用以代入的變?cè)c原公式中所有變?cè)拿Q都不能相同。2.2.2謂詞的約束和替換2.2謂詞邏輯公式與解釋25例2.2.5對(duì)公式x（F（x）→G（x，y））∧yH（y）代入。解對(duì)y實(shí)施代入，經(jīng)過代入后原公式為x（F（x）→G（x，t））∧yH（y）另外，量詞作用域中的約束變?cè)?，?dāng)論域的元素是有限時(shí)，個(gè)體變?cè)乃锌赡艿娜〈强梢悦杜e的。設(shè)論域元素為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沒有自由變?cè)墓椒Q為閉式。例如：（x）（

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

（1）解釋I為：D：整數(shù)集合。F（x，y）：x+y＝0G（x，y）：x>y因?yàn)閷?duì)任意的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：整數(shù)集合，F(xiàn)（x，y）：xy＝0,G（x，y）：x＝y(tǒng)。因?yàn)閷?duì)任意的x0，當(dāng)y＝0時(shí)，有F（x，y）→G（x，y）為“假”，即有（y）（F（x，y）→G（x，y））為“假”。對(duì)x＝0，當(dāng)y0時(shí)，有F（x，y）→G（x，y）為“假”，即有（y）（F（x，y）→G（x，y））為“假”。所以，對(duì)任意的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è)元素都有性質(zhì)G，則論域中的某些元素具有性質(zhì)G。（x）G（x）為真時(shí)，（x）G（x）也為真，所以公式（x）G（x）→（x）G（x）為永真式。（2）公式在任何解釋下的含義是：個(gè)體域I中的每個(gè)x，y都不具備關(guān)系F，但存在某些元素具有關(guān)系F。這兩個(gè)命題矛盾，所以公式（x）（y）﹁F（x，y）∧（x）（y）F（x，y）為永假式。3）取解釋I1：個(gè)體域?yàn)閷?shí)數(shù)集合，F(xiàn)（x）：x是整數(shù)，G（x）：x是有理數(shù)。在解釋I1下公式（x）（F（x）→G（x））為真，因而公式不為矛盾式。2.2.3謂詞邏輯公式的解釋2.2謂詞邏輯公式與解釋352.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式1．命題公式的推廣

2．量詞的轉(zhuǎn)換

3．量詞轄域的擴(kuò)張與收縮

4．量詞的分配律

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

1．命題公式的推廣

在命題邏輯中，任意一個(gè)永真式，其中同一命題變?cè)猛幻}公式代換，所得到的公式仍為永真式，把這個(gè)情況推廣到謂詞邏輯之中，命題邏輯中的永真公式所有相同的變?cè)弥^詞邏輯中的同一公式代替，所得到的謂詞公式為永真式，所以命題演算中的等價(jià)公式都可以推廣到謂詞邏輯中使用。例如（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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式382．量詞的轉(zhuǎn)換

定理2.3.1設(shè)G（x）是謂詞公式，有關(guān)量詞否定的兩個(gè)等價(jià)公式：（1）﹁（x）G（x）（x）﹁G（x）（2）﹁（x）G（x）（x）﹁G（x）證明

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

﹁（x）G（x）

﹁（G（a1）∨

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

﹁G（a1）∧

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

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

﹁（x）G（x）

﹁（G（a1）∨

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

﹁G（a1）∧

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

（x）﹁G（x）2.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式403．量詞轄域的擴(kuò)張與收縮

定理2.3.2設(shè)G（x）是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式41證明（1）設(shè)D是個(gè)體域，I為任意解釋，即用確定的命題及確定的個(gè)體代替出現(xiàn)在x（A（x）∨B）和xA（x）∨B中的命題變?cè)蛡€(gè)體變?cè)?，于是得到兩個(gè)命題，若對(duì)x（A（x）∨B）代替之后所得命題的真值為真，此時(shí)必有A（x）∨B的真值為真；因而A（x）真值為真或B的真值為真，若B的真值為真，則xA（x）∨B的真值為真；若B的真值為假，則必有對(duì)D中任意x都使得A（x）的真值為真，所以x（A（x）∨B）為真，從而xA（x）∨B為真。2.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式42證明若對(duì)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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式434．量詞的分配律

定理2.3.3設(shè)G（x）、H（x）是任意包含約束出現(xiàn)個(gè)體變?cè)獂的公式，則有：(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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式44證明

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

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

（x）H（x）的真值不能同時(shí)為真，從而（x）G（x）∧（x）H（x）的真值為假。綜上所述（x）（G（x）∧H（x））（x）G（x）∧（x）H（x）。2.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式45證明（2）設(shè)D是任一個(gè)體域，若（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）為假，此時(shí)，G（a）為假，H（a）為假，從而（x）G（x）∨（x）H（x）的真值為假。綜上所述（x）（G（x）∨H（x））（x）G（x）∨（x）H（x）。2.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式46要進(jìn)行等價(jià)演算，除了以上重要的等值式外，還要記住下面三條規(guī)則：（1）置換規(guī)則（2）換名規(guī)則（3）代替規(guī)則2.3謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式47例2.3.1證明下列各等價(jià)式（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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式48例2.3.1證明下列各等價(jià)式（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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1謂詞邏輯的等價(jià)公式49定義2.3.2設(shè)A、B是謂詞邏輯中的任意兩個(gè)公式，若A→B是永真式，則稱公式A蘊(yùn)涵公式B，記作AB。定理2.3.4下列蘊(yùn)涵式成立（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謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.2謂詞邏輯的蘊(yùn)涵公式50證明

（1）設(shè)xA（x）

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