第四章命題邏輯

因而命題邏輯具有局限性，甚至無法判斷一些簡單而常見的推理。如：命題演算的基本單位是命題不再對簡單命題進(jìn)行分解不考慮命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系命題邏輯p:凡人必死。q:蘇格拉底是人。r:所以蘇格拉底必死。顯然是一個(gè)有效推理，但按命題邏輯中的推理：

pq∴r

r不是一個(gè)重言式，是一個(gè)非有效的推理。問題出在命題中所包含的成分，若改成：所有A是BC是A所以C是B從而符合了有效推理。這在命題邏輯中是無法描述的。鑒于此，德國的數(shù)學(xué)家弗雷格引入了謂詞，量詞，個(gè)體詞，對命題邏輯進(jìn)行了擴(kuò)充。研究它們的形式結(jié)構(gòu)及邏輯關(guān)系。總結(jié)出正確的推理形式和規(guī)則，即一階邏輯，又稱謂詞邏輯。4.1一階邏輯的符號化

個(gè)體詞謂詞獨(dú)立存在的客體刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間關(guān)系的詞。簡單命題分解成如：李明是個(gè)大學(xué)生。個(gè)體詞謂詞張明與李亮是兄弟。個(gè)體詞

是指所研究對象中可以獨(dú)立存在的具體的或抽象的客體。例如，小王，桌子，中國，√3

，3等本書在論述或推理中如沒有指明所采用的個(gè)體域，都是使用全總個(gè)體域。個(gè)體常項(xiàng)

表示具體或特定的客體的個(gè)體詞。一般用小寫英文字母a，b，c…，ai，bi，ci…表示個(gè)體變項(xiàng)

表示抽象或泛指的個(gè)體詞。常用x，y，z…，xi，yi，zi…表示。個(gè)體域(或稱論域)個(gè)體變項(xiàng)的取值范圍。個(gè)體域可以是有窮集合，例如，{1，2，3}，{a，b，c，d}，{a，b，c，…，x，y，z}，…；也可以是無窮集合，例如，自然數(shù)集合N={0，1，2，…}，實(shí)數(shù)集合R={x|x是實(shí)數(shù)}…。全總個(gè)體域是由宇宙間一切事物組成的。謂詞

刻畫個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞。(1)√2

是無理數(shù)。

(2)x是有理數(shù)。

(3)小王與小李同歲。

(4)x與y具有關(guān)系L。謂詞常項(xiàng)

表示具體性質(zhì)或關(guān)系的謂詞謂詞變項(xiàng)

表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞無論是謂詞常項(xiàng)或變項(xiàng)都用大寫英文字母F，G，H，…表示，可根據(jù)上下文區(qū)分一般的，用F(a)表示個(gè)體常項(xiàng)a具有性質(zhì)F，用F(x)表示個(gè)體變項(xiàng)x具有性質(zhì)F.而用F(a，b)表示個(gè)體常項(xiàng)a，b具有關(guān)系F，用F(x,y)表示個(gè)體變項(xiàng)x，y具有關(guān)系F.(F是謂詞常項(xiàng)或謂詞變項(xiàng))實(shí)質(zhì)上，n元謂詞P(x1,x2,…,xn)可以看成以個(gè)體域?yàn)槎x域，以{0,1}為值域的n元函數(shù)或關(guān)系。它不是命題。要想使它成為命題，必須用謂詞常項(xiàng)取代P，用個(gè)體常項(xiàng)a1,a2,…,an取代x1,x2,…,xn，得P(a1,a2,…,an)是命題。更一般的用P(x1,x2,…,xn)表示含n(n≥1)個(gè)命題變項(xiàng)的n元謂詞。n=1時(shí)，P(x1)表示x1具有性質(zhì)P；n≥2時(shí)，P(x1,x2,…,xn)表示x1,x2,…,xn具有關(guān)系P。0元謂詞不帶個(gè)體變項(xiàng)的謂詞。例如，F(xiàn)(a)，G(a,b)，P(a1,a2,…,an)等都是0元謂詞。當(dāng)F，G，P為謂詞常項(xiàng)時(shí)，0元謂詞為命題。命題邏輯中的命題均可以表示成0元謂詞，因而可以將命題看成特殊的謂詞。

判斷：0元謂詞都是命題?！晾?.1

將下列命題在一階邏輯中用0元謂詞符號化，并討論它們的真值:

(1)只有2是素?cái)?shù)，4才是素?cái)?shù)。

(2)如果5大于4，則4大于6.。解：

(1)設(shè)一元謂詞F(x):x是素?cái)?shù)，a:2，b:4。

(1)中命題符號化為0元謂詞的蘊(yùn)涵式:F(b)→F(a)由于此蘊(yùn)涵前件為假，所以(1)中命題為真。

（2）設(shè)二元謂詞G(x，y):x大于y，a:4，b:5，c:6。G(b,a)，G(a,c)是兩個(gè)0元謂詞，把(2)中命題符號化為G(b,a)→G(a,c)由于G(b,a)為真，而G(a,c)為假，所以(2)中命題為假。有了個(gè)體詞和謂詞之后，有些命題還是不能準(zhǔn)確的符號化，原因是還缺少表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。稱表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞為量詞量詞可分兩種:(1)全稱量詞表示個(gè)體域里所有個(gè)體

(2)存在量詞日常生活和數(shù)學(xué)中所用的“一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都”等詞可統(tǒng)稱為全稱量詞，將它們符號化為“

”。并用

x，y等表示個(gè)體域里的所有個(gè)體。表示個(gè)體域里有的個(gè)體日常生活和數(shù)學(xué)中所用的“存在”，“有一個(gè)”，“有的”，“至少有一個(gè)”等詞統(tǒng)稱為存在量詞，將它們都符號化為“

”。并用x，y等表示個(gè)體域里有的個(gè)體例4.2

在個(gè)體域分別限制為(a)和(b)條件時(shí)，將下面兩個(gè)命題符號化:

(1)凡人都呼吸。

(2)有的人用左手寫字。

其中:(a)個(gè)體域D1為人類集合；

(b)個(gè)體域D2為全總個(gè)體域。解：(a)令F(x):x呼吸。G(x):x用左手寫字。(1)在D1中除了人外，再無別的東西，因而符號化為

xF(x)

(2)在D1中的有些個(gè)體(人)用左手寫字，因而符號化為xG(x)

(b)D2中除了有人外，還有萬物，因而在(1)，(2)符號化時(shí)，必須考慮將人分離出來。令M(x):x是人。在D2中，(1)，(2)可以分別重述如下:(1)對于宇宙間一切事物而言，如果事物是人，則他要呼吸。

(2)在宇宙間存在著用左手寫字的人。于是(1)，(2)的符號化形式分別為（1）x(M(x)→F(x))

（2）x(M(x)∧G(x))

可知，命題(1)，(2)在不同的個(gè)體域D1和D2中符號化的形式不一樣。主要區(qū)別在于，在使用個(gè)體域D2時(shí)，要將人與其他事物區(qū)分開來。為此引進(jìn)了謂詞M(x)，像這樣的謂詞稱為特性謂詞。在命題符號化時(shí)一定要正確使用特性謂詞。問:(a)能否將(1)符號化為

x(M(x)∧F(x))？

(b)能否將(2)符號化為

x(M(x)→G(x))？例4.3

在個(gè)體域限制為(a)和(b)條件時(shí)，將下列命題符號化:

(1)對于任意的x，均有x2-3x+2=(x-1)(x-2).

(2)存在x，使得x+5=3。

其中:(a)個(gè)體域D1=N(N為自然數(shù)集合)

(b)個(gè)體域D2=R(R為實(shí)數(shù)集合)解：

(a)令F(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。命題(1)的符號化形式為xF(x)命題(2)的符號化形式為xG(x)顯然(1)為真命題；而(2)為假命題，因?yàn)镹不含負(fù)數(shù)。(b)在D2內(nèi)，(1)和(2)的符號化形式同在D1中的形式，(1)依然是真命題，而此時(shí)(2)也是真命題。在不同個(gè)體域內(nèi)，同一個(gè)命題的符號化形式可能不同，也可能相同。

由上例我們可以看出：2.同一個(gè)命題，在不同個(gè)體域中的真值也可能不同。例4.4

將下列命題符號化，并討論真值。

(1)所有的人都長著黑頭發(fā)。

(2)有的人登上過月球。

(3)沒有人登上過木星。

(4)在美國留學(xué)的學(xué)生未必都是亞洲人。解：由于本題沒有提出個(gè)體域，因而應(yīng)該采用全總個(gè)體域，令M(x):x為人。1)令F(x):x長著黑頭發(fā)。命題符號化為x(M(x)→F(x))2)令G(x):x登上過月球。命題符號為

x(M(x)∧G(x))3)令H(x):x登上過木星。命題符號為

┐x(M(x)∧H(x))4)令F(x):x是在美國留學(xué)的學(xué)生，G(x):x是亞洲人。命題符號化為┐x(F(x)→G(x))

0111例4.5

將下列命題符號化:

(1)兔子比烏龜跑得快。

(2)有的兔子比所有的烏龜跑得快。

(3)并不是所有的兔子都比烏龜跑得快。

(4)不存在跑得同樣快的兩只兔子。解：本題沒有指明個(gè)體域，因而采用全總個(gè)體域。因?yàn)楸纠谐霈F(xiàn)二元謂詞，因而引入兩個(gè)個(gè)體變項(xiàng)x與y.令F(x):x是兔子，G(y):y是烏龜，H(x,y):x比y跑得快，L(x,y):x與y跑得一樣快。這4個(gè)命題分別符號化為4）┐xy(F(x)∧F(y)∧L(x,y))

1）xy(F(x)∧G(y)→H(x,y))2）x(F(x)∧

y(G(y)→H(x,y))

3）┐xy(F(x)∧G(y)→H(x,y))注意：1.多個(gè)量詞出現(xiàn)時(shí)，順序不能隨意調(diào)換。

2.有些命題的符號化形式可不止一種。例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，H(x,y):x+y=10,則xyH(x,y)與yx

H(x,y)不同例如，在例4.5中，

3)還可以符號化為

xy(F(x)∧G(y)∧┐H(x,y))

4)還可以符號化為

xy(F(x)∧F(y)→┐L(x,y))

一、討論下列各式的真值：1）取個(gè)體域?yàn)檎麛?shù)集Z，x

y（x·y=1）

A.0

B.1

C.不定

2）取個(gè)體域?yàn)檎麛?shù)集Z，xyz（x-y=z）

A.0

B.1

C.不定3）取個(gè)體域?yàn)檎麛?shù)集Z，x-y=-y+x

A.0

B.1

C.不定4）取個(gè)體域?yàn)檎麛?shù)集Z，xy(x·y)=y

A.0

B.1

C.不定5）取個(gè)體域?yàn)檎麛?shù)集Z，x(x·y=x)

A.0

B.1

C.不定6）取個(gè)體域?yàn)檎麛?shù)集Z，xy(x+y=2y)

A.0

B.1

C.不定ABBACA二、將下列命題符號化。

(1)每個(gè)人恰有一個(gè)最好的朋友。

(2)如果某人是女性而且有子女，那么此人一定是某人的母親。

(3)有位婦女已搭乘過世界上每一條航線上的航班。

(4)定義是：對每個(gè)實(shí)數(shù)>0，使得對每一個(gè)x，只要

0<|x-a|<，就有|f(x)-L|<

。4）x(0<|x-a|<|f(x)-L|<

）3）令：P(w,f):w搭乘過f。Q(f,a):f是a上的航班。則命題可表示為

waf(P(w,f)Q(f,a))

其中w,a,f代表世界上所有的婦女，所有的空中航班和所有的航線。2）令：M(x):x是女性。P(x):x有子女。M(x,y):x是y的母親。

則命題可表示為x(M(x)P(x))yM(x,y)1）令：B(x,y):x與y是最好的朋友。

則命題可表示為xyz(B(x,y)((zy)B(x,y)))三、把下列語句解釋為文字。1、x(C(x)y(C(y)F(x,y)))，其中

C(x)表示x有臺計(jì)算機(jī)，F(xiàn)(x,y)表示x和y是朋友；論域?yàn)閷W(xué)校全體學(xué)生。2、xyz((F(x,y)F(x,z)(yz))F(y,z))，其中F(x,y)表示x和y是朋友；論域?yàn)閷W(xué)校全體學(xué)生。4.2一階邏輯公式及解釋同命題邏輯一樣，給出謂詞公式定義：定義4.1一階語言L的字母表定義如下:(1)個(gè)體常項(xiàng):a,b,c,…,ai,bi,，ci，…，i≥1(2)個(gè)體變項(xiàng):x,y,z,…，xi,yi,zi，…，i≥1(3)函數(shù)符號:f,g,h,…,fi,gi,hi，…，i≥1(4)謂詞符號:F,G,H,…,Fi,Gi,Hi，…，i≥1(5)量詞符號:

，

(6)聯(lián)結(jié)詞符號:┐,∧,∨,→,

(7)括號與逗號:(,),，4.2一階邏輯公式及解釋定義4.2L

的項(xiàng)的定義如下:(1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)。

(2)若f(x1,x2,…,xn)是任意的n元函數(shù)，t1,t2,…,tn

是任意的n個(gè)項(xiàng)，則f(t1,t2,…,tn)是項(xiàng)。

(3)所有的項(xiàng)都是有限次使用(1)，(2)得到的。如：a,b,x,y;f(x,y)=x+y,g(x,y)=x-y,h(x,y)=x*y;g(h(x,y),f(a,b))=x*y-(a+b)定義4.3設(shè)R(x1,x2,…,xn)是L

的任意n元謂詞,

t1,t2,…,tn是F

的任意的n個(gè)項(xiàng)，

則稱R(t1,t2,…,tn)是L

的原子公式。例4.5中的1元謂詞F(x)，G(x)，

2元謂詞H(x,y)，L(x,y)等都是原子公式。定義4.4L

的合式公式定義如下:(1)原子公式是合式公式。

(2)若A是合式公式，則(┐A)也是合式公式。

(3)若A，B是合式公式，則(A∧B)，(A∨B)，

(A→B)，(AB)也是合式公式。

(4)若A是合式公式，則xA，

xA也是合式公式

(5)只有有限次的應(yīng)用(1)～(4)構(gòu)成的符號串才是

合式公式。L

的合式公式也稱為謂詞公式，簡稱公式在定義中出現(xiàn)的字母A，B是代表任意公式的元語言符號。為方便起見，公式(┐A)，(A∧B)，…中的最外層括號可以省去。定義4.5在公式xA

和xA中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域。在x和

x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)。A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的。例4.6

指出下列各公式中的指導(dǎo)變元，各量詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng):1)x(F(x,y)→G(x,z))

2)x(F(x)→G(y))→

y(H(x)∧L(x,y,z))解:(1)x是指導(dǎo)變元。量詞的轄域A=(F(x,y)→G(x,z))，在A中，x是約束出現(xiàn)的。而且約束出現(xiàn)兩次，y和z均為自由出現(xiàn)的，而且各自由出現(xiàn)一次。2)公式中含有兩個(gè)量詞，前件上的量詞的指導(dǎo)變元為，的轄域A=(F(x)→G(y))，其中x是約束出現(xiàn)的，y是自由出現(xiàn)的。后件中的量詞的指導(dǎo)變元為y,的轄域?yàn)?H(x)∧L(x,y,z))，其中y是約束出現(xiàn)的，x，z均為自由出現(xiàn)的。在整個(gè)公式中，x約束出現(xiàn)一次，自由出現(xiàn)2次，y自由出現(xiàn)一次，約束出現(xiàn)一次，z只自由出現(xiàn)一次。本書用A(x1,x2,…,xn)表示含x1,x2,…,xn自由

出現(xiàn)的公式，并用Δ表示任意的量詞(或

).

則Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出

現(xiàn)的公式，可記為A1(x2,x3,…,xn)。類似的，

Δx2Δx1A(x1,x2,…,xn)可記為A2(x3,x4,…,xn)，

Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是

自由出現(xiàn)的個(gè)體變項(xiàng)，可以記為An(xn)，而Δxn…Δx1A(x1,x2,…,xn)已經(jīng)沒有自由出現(xiàn)

的個(gè)體變項(xiàng)了。可將例4.6(1)中的公式簡記為A(y,z)，這表明(1)中公式含有自由出現(xiàn)的個(gè)體變項(xiàng)y，z。而yA(y,z)中只含有z為自由出現(xiàn)的公式,zyA(y,z)中已經(jīng)沒有自由出現(xiàn)的個(gè)體變項(xiàng)了，

此時(shí)的公式為zyx(F(x,y)→G(x,y,z))

定義4.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡稱閉式。例4.7

將下列公式中的變項(xiàng)指定成常項(xiàng)使其成為命題:

(1)x(F(x)→G(x))

解:(1)指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法:(a)令個(gè)體域D1為全總個(gè)體域，

F(x)為x是人，G(x)為x是黃種人，則表達(dá)的命題為“所有人都是黃種人”，這是假命題。(b)令個(gè)體域D2為實(shí)數(shù)集合R，

F(x)為x是自然數(shù)，G(x)為x是整數(shù)，則表達(dá)的命題為“自然數(shù)都是整數(shù)”，這是真命題。指定個(gè)體域?yàn)槿倐€(gè)體域，F(xiàn)(x)為x是實(shí)數(shù)，G(x,y)為x≠y，H(x,y)為x>y，f(x,y)=2x+2y，g(x,y)=2xy，則表達(dá)的命題為“對于任意的x，y，若x與y都是實(shí)數(shù)，且x≠y，則2x+2y>2xy”，這是真命題。如果H(x,y)改為x<y，則所得命題就為假命題了。(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))在上例中，對各種變項(xiàng)的指定也可以稱為對它們的解釋。在本例中是給出公式后再對它們進(jìn)行解釋，也可以先給出解釋，再用這個(gè)解釋去解釋各種公式。由以上的討論不難看出，一個(gè)解釋不外乎指定個(gè)體域、個(gè)體域中一些特定的元素、特定的函數(shù)和謂詞等部分。定義4.7F

的解釋I由下面4部分組成:(a)非空個(gè)體域DI(b)DI中一些特定元素的集合

(c)DI上特定函數(shù)集合{

|i,n≥1}(d)DI上特定謂詞的集合{

|i,n≥1}下面對解釋I做幾點(diǎn)說明:2.被解釋的公式A中的個(gè)體變項(xiàng)均取值于DI。1.在解釋的定義中引進(jìn)了幾個(gè)元語言符號，如

,

,

。3.若A中含有個(gè)體常項(xiàng)ai，就解釋成

。

為第i個(gè)n元函數(shù)。例如，i=1，n=2時(shí)，

表示第一個(gè)二元函數(shù)，它出現(xiàn)在解釋中，可能是(x,y)=x2+y2,

(x,y)=2xy等，一旦公式中出現(xiàn)f1(x,y)就解釋成

(x,y)，出現(xiàn)g1(x,y)就解釋成

(x,y)=2xy。

5.

為第i個(gè)n元謂詞，如i=2，n=3時(shí)，

表示第2個(gè)3元謂詞，它可能以

(x,y,z)的形式出現(xiàn)在解釋中，公式A若出現(xiàn)F2(x,y,z)就解釋成

(x,y,z)。6.被解釋的公式不一定全部包含解釋中的四部分。例4.8

給定解釋I如下:

(a)個(gè)體域D=N(N為自然數(shù)集合)

(b)

=0

(c)

(x,y)=x+y,

(x,y)=xy

(d)

(x,y)為x=y

在I下，下列哪些公式為真?哪些為假?哪些的真值還不能確定?(1)F(f(x,y),g(x,y))公式被解釋成“x+y=x·y”，這不是命題。(2)F(f(x,a),y)→F(g(x,y),z)公式被解釋成“(x+0=y)→(x·y=z)”，這也不是命題。(3)┐F(g(x,y),g(y，z))公式被解釋成“x·y≠y·z”，同樣不是命題。(4)

xF(g(x,y),z)公式被解釋成“x(x·y=z)”，不是命題。(5)xF(g(x,a),x)→F(x,y)公式被解釋成“x(x·0=x)→(x=y)”，由于蘊(yùn)涵式的前件為假，所以被解釋的公式為真。(6)

xF(g(x,a),x)公式被解釋成“x(x·0=x)”，為假命題。(7)xy(F(f(x,a),y)→F(f(y,a),x))公式被解釋成“xy((x+0=y)→(y+0=x))”，為真命題。(8)xyzF(f(x,y),z)公式被解釋成“xyz(x+y=z)”，這也為真命題。(9)xF(f(x,x),g(x,x))公式被解釋成“

x(x+x=x·x)”，為真命題。定理4.1

封閉的公式在任何解釋下都變成命題。對閉式來說，由于每個(gè)個(gè)體變項(xiàng)都受量詞的約束，因而具體解釋中總表示一個(gè)意義確定的語句，即一個(gè)真（假）命題。不是閉式的公式在某些解釋下也可能成為命題。定義4.8

設(shè)A為一個(gè)公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。若至少存在一個(gè)解釋使A為真，則稱A為可滿足式。很難判斷任意一公式是否可滿足。定義4.9

設(shè)A0是含有命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2,…,An是n個(gè)謂詞公式，用Ai(1≤i≤n)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例。例如，F(xiàn)(x)→G(x)，

xF(x)→

yG(y)等都是p→q的代換實(shí)例，而x(F(x)→G(x))等不是p→q的代換實(shí)例。定理4.