引入陳述句=主語+謂語例：張三是好學(xué)生。

李四是好學(xué)生。

王五是好學(xué)生。

趙六是好學(xué)生。什么是抽象？[1]抽象就是去除事物的細節(jié)，找到事物的本質(zhì)屬性

。[2]籠統(tǒng)的，不具體的。簡單的說，就是把現(xiàn)實生活中的東西用計算機語言描述，使計算機能夠明白！抽象能力是程序設(shè)計、科學(xué)研究的基本能力。在命題邏輯中，對下述的“蘇格拉底三段論”都無法用命題邏輯予以推證。

凡人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。類似的例子還有許多。例如：所有的人都要呼吸,所有的正整數(shù)都大于0,

李莉是人,3是正整數(shù),所以李莉要呼吸。所以3大于0。在命題邏輯中，命題被當作一個基本的，不可分割的單位，只研究由原子命題和聯(lián)接詞所組成的復(fù)合命題；因而無法研究命題的內(nèi)部結(jié)構(gòu)及命題之間內(nèi)在的聯(lián)系。本章介紹的謂詞邏輯，對原子命題的成份、結(jié)構(gòu)和原子命題間的共同特性等作了進一步分析。引入了個體詞、謂詞、量詞、謂詞公式等概念，在此基礎(chǔ)上研究謂詞公式間的等值關(guān)系和蘊含關(guān)系，并且對命題邏輯中的推理規(guī)則進行擴充和進行謂詞演繹。主要內(nèi)容如下：

4.1謂詞、個體詞和量詞

4.2謂詞公式

5.1謂詞等價關(guān)系

5.2范式

5.3蘊含關(guān)系謂詞邏輯

一、個體詞和謂詞在謂詞演算中，可將原子命題分解為謂詞與個體詞兩部分。

定義

客（個）體是指可以獨立存在的客體。

注個體可以是抽象的，也可是具體的。個體通常在一個命題里表示思維對象(研究對象)。

定義用來刻劃個體的性質(zhì)或個體之間關(guān)系的詞稱為謂詞，刻劃一個個體性質(zhì)的詞稱為一元謂詞；刻劃n個個體之間關(guān)系的詞稱為n元謂詞。

謂詞、個體詞和量詞在這三個命題中，李明、張亮、陳華都是個體；（1）“…是學(xué)生”是一元謂詞，（2）“…比…高”是二元謂詞，（3）“…坐…與…之間”是三元謂詞。例1

（1）李明是學(xué)生；（2）張亮比陳華高；（3）陳華坐在張亮與李明之間。n元謂詞——n個個體？——n個個體變元？課本0元謂詞不準確！二、個體變元

個體常元

表示具體或特定的個體的個體詞稱為個體常元。

個體變元

表示抽象的，或泛指的（或者說取值不確定的）個體稱為個體變元。例2

L（x,y,z）表示“x+y=z”,其中x,y,z為個體變元。L（3，2，5）表示真命題“3+2=5”，（3，2，5）為個體常元而L（1，2，4）表示假命題“1+2=4”，（1，2，4）為個體常元。我們用大寫字母表示謂詞，小寫字母u,v,w,

x,y,z……表示個體變元。小寫字母阿a,b,c,

d,e,f……表示個體常元。（顯然個體的順序與謂詞有關(guān)）形式化

例3

設(shè)H是表示謂詞“…能夠到達山頂”，若個體a王紅；b：老虎；c：汽車，則H（a），H（b），H（c）分別表示“王紅能夠到達山頂。”“老虎能夠到達山頂。”“汽車能夠到達山頂。”這里w、t、s均是個體常元。H（x）：x能夠到達山頂。這里的x是泛指的，不確定的，x可在一定的范圍內(nèi)取值。故x是個體變元。三、量詞和全總個體域1.量詞在命題里表示數(shù)量的詞。

使用前面介紹的概念，還不足以表達日常生活中的各種命題。例如：命題“所有的正整數(shù)都是素數(shù)”和“有些正整數(shù)是素數(shù)”僅用個體詞和謂詞是很難表達的。

（1）全稱量詞

“

x”

如“所有人都是要死的。”可表示為

xD（x），x的個體域為全體人的集合。（2）存在量詞“

x”如“有些有理數(shù)是整數(shù)。”令Ｉ(x）：x是整數(shù)；于是命題可表示為

xＩ(x）其中x的個體域為有理數(shù)集合。（3）存在唯一量詞“!x”

如“方程x+1=0存在唯一的整數(shù)解。” 令P（x）：x是x+1=0的整數(shù)解。則命題可表示為!xP（x），其中x的個體域為整數(shù)集。個體變元的取值范圍稱為個體域（論域）。例4

P（x,y）表示“2x+y=1”，若x,y的個體域為正整數(shù)集，則總是假；

若x，y的個體域為有理數(shù)集，則y=1―2x，對任意的有理數(shù)k，在x=k，y=1―2k時，P（k，1―2k）為真。

2．全總個體域

含有量詞的命題的表達式的形式，與個體域有關(guān)。含有量詞的命題的真值與個體域也有關(guān)。因此，為了方便，我們引入全總個體域的概念。

定義宇宙間所有的個體聚集在一起所構(gòu)成的集合稱為全總個體域。后面的討論中，除特殊說明外，均使用全總個體域。而對個體變化的真正取值范圍，用特性謂詞加以限制。例5

(1)“所有的人都是要死的。”(2)“有的人活百歲以上。”當x的個體域E為全體人組成的集合時，符號化上述命題。令D（x）：x是要死的。則（1）可表示為xD（x）。令G（x）：x活百歲以上。則（2）可表示為xG（x）。

當取x的個體域為全總個體域時，必須引入一個特性謂詞將人從全宇宙的一切事物中分離出來。P60

（1）對所有個體而言，如果它是人，則它是要死的。(2）存在著個體，它是人并且它活百歲以上。于是令M（x）：x是人。（1）x（M（x）D（x））（2）x（M（x）∧G（x））

一般地，對全稱量詞，此特性謂詞作蘊含的前件；對存在量詞，此特性謂詞常作合取項。有些問題用特性謂詞并不能表達語意。例：孩子是由奶奶照顧。P（x，y）x照顧y

P（f(y)，y）函數(shù)f(y)表示y的奶奶.個體域可以是函數(shù)也可以表示為F（x，y）x是y的奶奶

P（x，y）∧

F（x，y）？P（F（x，y），y）僅謂詞個體變元被量化的謂詞稱為一階謂詞。如果函數(shù)符號和謂詞符號也被量化，則那樣的謂詞為二階謂詞。

1）若沒事先給出個體域，都認為是全總個體域。2）在不同個體域中，命題符號化形式可能不一樣。

四．命題符號化例凡是實數(shù)均能比較大小。

則該命題可表示為

或者令Q（x,y）:x≥y;解

令R（x）：x是實數(shù)；G（x,y)：x與y可比較大小.注意：謂詞不是唯一的。3）引入特性謂詞后，使用全稱量詞與存在在量詞符號化的形式不同。（前者單條件、后者合取）

例發(fā)光的不都是金子

解

令P（x）：x發(fā)光；G（x）：x是金子。

則可表示為

或注意：否定的對象是量詞、謂詞?理解全稱特性謂詞和存在特性謂詞的區(qū)別了嗎？4）多個量詞出現(xiàn)時，不能隨意改變它們的順序，否則可能會改變原命題含意。P62

例：“對任意x,存在y,使x+y=5。”取個體域為實數(shù)集。

符號化為：xyH(x,y)

其中H（x,y）：x+y=5：這是真命題。

但若寫成：yxH(x,y)

則其含意為“存在著y,使對任意x，都有x+y=5”這就是一個假命題，且與原意不符。（2）所有運動員都欽佩某些教練。解

令P（x）：x是運動員；T（x）：x是教練；

Q（x，y）：x欽佩y。

則該命題可表示為

注意：量詞不一定前置！（2`）所有運動員和教練都欽佩某些教練。

則該命題可表示為

例

將下列命題符號化（練習(xí)）

（1）會叫的狗未必咬人。

解

令D（x）：x是狗；P（x）：x會叫；Q（x）：x咬人。

則可表示為

或表示為

（2）一切人不是一樣高。

解

M(x)：x是人；G(x,y):x與y一樣高;H(x,y):x與y是不同的人。可表示為

或者

xy（M(x)M(y)H(x,y)L(x,y)）例6

“某些人對某些藥物過敏”令H(x)：x是人;M(y):y是藥;S(x，y)：x對y過敏。符號化表示為：

定義（謂詞公式的遞歸定義。）

(1）命題常元、命題變元和簡單謂詞都是謂詞公式。（2）如果A是謂詞公式，則

┐A也是謂詞公式。（3）如果A和B是謂詞公式，則（A∨B）,(A∧B）,(A→B),

(A

B)也是謂詞公式。（4）如果A是謂詞公式，x是A中的個體變元，則

和

也是謂詞公式。（5）只有由使用上述四條規(guī)則有限次而得到的才是謂詞公式。一、謂詞公式

謂詞公式

二、約束變元和自由變元

個體變元有自由變元和約束變元之分.

在謂詞公式中，形如或的那一部分稱為公式的x約束部分。而A（x）稱為量詞x或x的轄域。x在公式的x約束部分的任一出現(xiàn)都稱為x的約束出現(xiàn)。

公式中約束出現(xiàn)的變元是約束變元

當x的出現(xiàn)不是約束出現(xiàn)時，稱x的出現(xiàn)是自由出現(xiàn)。自由出現(xiàn)的變元是自由變元。

x,y,z在公式中的所有出現(xiàn)均是約束出現(xiàn)，故它們均是約束變元。

例

指出下列各公式中的量詞轄域及自由變元和約束變元。

解

是的轄域。是的轄域.

R(z）是z的轄域。解

P（x，y）→

yQ（x，y，z）是x的轄域，在這一部分中，x是約束出現(xiàn)，故x是約束變元，在P（x，y）中的y是自由出現(xiàn)，故y為自由變元。但Q（x，y，z）是y的轄域，因而在Q（x，y，z）中y卻是約束出現(xiàn)，故此時y是約束變元，z是自由變元。在S（x，z）中x，z是自由變元。三、換名規(guī)則和代入規(guī)則

避免個體變量名一樣而意義不同:

1.換名規(guī)則

對約束變元進行換名，使得一個變元在一個公式中只呈一種形式出現(xiàn)。

（1）約束變元換名時，該變元在量詞及其轄域中的所有出現(xiàn)均須同時更改，公式的其余部分不變；（2）換名時，一定要更改為該量詞轄域中沒有出現(xiàn)過的符號，最好是公式中未出現(xiàn)過的符號。

解

需對x，y換名

錯誤：

例8

對公式進行換名，使各變元只呈一種形式出現(xiàn)。

2.代入規(guī)則對于公式中自由變元的更改叫做代入。

的x,y的自由出現(xiàn)分別用w,t代入得（1）對于謂詞公式中的自由變元可以代入，代入時須對該自由變元的所有自由出現(xiàn)同時進行代入；（2）代入時所選用的變元符號與原公式中所有變元的符號不相同。例如對例8中公式

四.謂詞公式的解釋定義1.30一個公式A的解釋I由下面四部分組成：1）非空個體域D。2）D中一部分特定元。

3）D上一些特定函數(shù)。（個體＋函數(shù)＝項P63）4）D上一些特定謂詞。

定義指派(解釋)

一組代入到謂詞公式中，并使得謂詞公式成為命題的確定的個體和命題稱為公式的一組指派。一個謂詞公式一般含有個體變元、命題變元和謂詞，只有當公式中的自由變元用某個體域中確定的個體代入，命題變元用確定的命題代入后，原公式才變成為一個命題。當個體域為有限集時，如D={a1,an}由量詞意義可見，對任謂詞A(x)，有

①xA(x)A(a1)A(a2)A(an)

②xA(x)A(a1)A(a2)A(an)

在集合S={2，3，5，7，11}上，表示x都是素數(shù)：xA(x)。在集合S={2，3，5，6，7}上，表示有x是素數(shù)：xA(x)例：給定解釋I如下：1）D={2，3}；2）D中特定元a=2；3）函數(shù)f(2)=3,f(3)=2；

4）謂詞F(2)=0,F(3)=1；G(i,j)=1,i,j=2,3；

L(2,2)=L(3,3)=1；L(2,3)=L(3,2)=0。求下列各式真值。1）x（F(x)）

G(x，a)）；2）x（F(f(x))

G(x,f(x))）；3）xyL（x,y）。解：

（1）原命題(F(2)

G(2，2))(F(3)

G(3，2)）

（01）（11）

0

（2）原命題

F(f(2))

G(2，f(2)))

F(f(3)G(3，f(3)))

（F（3）

G（2，3））

(F(2)G（3，2）)

（11）（01）

1（3）原命題((L(2，2)

L(2，3))(L(3，2)

L(3，3))

111

五、公式的類型定義1.31

給定謂詞公式A，其個體域為E，如果對于任一組指派，公式A的值總是為真，則稱A在E上式永真的。如果對于公式A的任一組指派，公式A的值總是為假，則稱A在E上是永假的。如果至少存在著一組指派，使公式A的值為真，則稱A在E上是可滿足的。

例1

試說明下列各公式的類型（個體域取為全總個體域）（1）（2）（3）F(x)

（其中F(x):x+6=5）（4）

解

(1)永真公式(2)可滿足公式(3)可滿足公式(4)永假公式解

（1）可滿足公式。

（2）永假公式。

（3）永真公式。

（4）可滿足公式。

例2

試說明下列各公式的類型。（1）（2）（3）（4）P（x，y）其中x，y的個體域為R；謂詞P（x，y）：x=y；Q是命題變元.定義1.32代換實例A0是命題公式，x1,x2,

…,

xn是命題變項，用n個謂詞公式A1,A2,…,An分別代換x1,x2,

…,

xn

，所得公式A稱為A0的代換實例。如：P(y)→Q(y)都是p→q的代換實例。定理:命題公式中的重言式的代換實例在謂詞公式中可仍稱為重言式，這樣的重言式都是邏輯有效式。定理:命題公式的等價式如有PQP∨Q

P(y)→Q(y)

P(y)∨Q(y)

例11)P∧Q

P

永真式的代換實例2)PVQ

P

可滿足式的代換實例P(y)∧

Q(y)

→P(y)P(y)V

Q(y)

→P(y)可滿足式永真式

定義

設(shè)A、B是兩個公式，它們有共同的個體域E，若對于A和B的任意一組指派，兩公式都具有相同的真值，則稱公式A和B在E上等值，記作A

B。定義

對于公式A和B，若A→B

1，則稱公式A蘊含公式B，記作A

B。

公式的等值與蘊含

謂詞演算中的等值式和蘊涵式在命題演算中，任一等值式或蘊涵式，其中同一命題變元，當用同一命題公式取代時，其結(jié)果仍是等值式或蘊涵式。1.命題公式的推廣(P72)

將此情況推廣到謂詞公式中，用謂詞公式去取代命題演算中等值式或蘊涵式的命題變元時，便得到謂詞演算的等值式或蘊涵式。例如又例如

例如2.全稱量詞和存在量詞間轉(zhuǎn)化的等值式（P73）

（其中A(x)是任意的公式）對個體域是有限時，給出其證明。

證明

設(shè)個體域,則

3.量詞轄域擴展與收縮的等值式（P73）

證明

設(shè)個體域,則（2）①②③④

證明

證明

（1）①

“個體域中每一個體x，使得A(x)與B(x)均為真”與“個體域中每一個體x，使得A(x)為真且每一個體x使得B(x)為真”具有相同的含義.

4.量詞分配等值式與蘊涵式（1）①②證明

由①得注意：P55①②請舉例?A（x）x是偶數(shù)，B（x）x是奇數(shù)，x是整數(shù)。①從左到右不成立②從右到左不成立P59定理1.10

證明

（2）②由（2）①得（2）①②即

即故P80證明

（1）5.量詞與聯(lián)結(jié)詞的關(guān)系P806.量詞的交換

P55定理1.9

全稱量詞之間可交換存在量詞之間可交換全稱量詞與存在量詞之間不可交換

七范式P77前束范式:將所有的量詞都放在謂詞公式的前面。如xy(P(x,y)∧Q(a)∧R(z))就是前束范式。定理:存在性求前束范式的方法：1）將“非”聯(lián)接詞后置2）可用提取律3）不可用提取律時，換名或代入例5.6

-5.8在謂詞演算中，推理的形式結(jié)構(gòu)仍為

若是永真式，則稱由前提邏輯的推出結(jié)論C，在此,C均為謂詞公式。

謂詞演算的推理理論一、推理規(guī)則P80A命題演算中的推理規(guī)則，可在謂詞推理理論中應(yīng)用。C與量詞有關(guān)的推理規(guī)則1.US(全稱特定化規(guī)則)或2. ES（存在特定化規(guī)則）B謂詞等值公式、謂詞蘊涵公式3.UG（全稱一般化規(guī)則）4、EG（存在一般化規(guī)則）二、推理規(guī)則的應(yīng)用

例1

證明蘇格拉底的三段論。

解

令M(x):x是人;D(x):x是要死的;c:蘇格拉底。于是蘇格拉底三段論可表示為：證明（1）M(c)前提（2） 前提（3）（1）；US（4）D(c) (1),(3);例2

（3） C(a)∧

Q(a)

（2）；ES

證明

（1） 前提

（2） 前提

（4） （1）；US

（5）C(a) （3）；I1

（6）W(a)∧

R(a)（4）,（5）；I11

（7）Q(a) （3）；I2

（8）R(a) （6）；I2

（9）Q(a)∧R(a)（7）,（8）；I9

（10）

（9）；EG例3

證明證明

（1） 附加前提

（2） （1）；E

（6）Q(c)

（3）,（5）；I10

（7）

（6）；EG

（3）

（2）；ES

（4）

前提

(5)（4）；US例4

證明

（1） 附加前提

（2） （1）；E10

證法一

:(間接證明法)

（3） （2）；I1

（4） （2）；I2

（5） （4）；I19

（6） （3）；E18

（7） （6）；ES

（8） （5）；US

（9） （7）（8）；I9

（10） （9）；E10

（11） 前提

（12） （11）；US

（13） （10）（12）;I9

證法二（1） 附加前提

（2） （1）；E18

（3） 前提

（4） （2）；ES

（5） （3）；US

（6） （4）（5）；I10

（7） （6）；EG

（8）