《離散數(shù)學(xué)》課件第二章

《《離散數(shù)學(xué)》課件第二章》由會員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》課件第二章（80頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,*,,“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的?！?,,,蘇格拉底三段論,,第二講 謂詞邏輯,（,Predicate,Qogic,）,,,1.,個體、謂詞和量詞,,,2.,謂詞公式,,,3.,等值演算,,,4.,范式,,,5.,推理理論,,,6.,謂詞邏輯在計算機科學(xué)中的應(yīng)用,,,,考慮如下,3,個命題或推理：,,1 “,有一個整數(shù)大于其他每個整數(shù)”,,2 “,任給,?,,> 0,，存在,?,,> 0,，如果,|x-a|<,?,，則,|f(x)-b|<,?,”,,3,,蘇格拉底三段論

2、：“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的?！?,,有一個整數(shù)大于其他每個整數(shù),個體,Individuah,？,謂詞,Predicate,？,量詞,Quantification,？,個體常,元,(a,b,…),、個體變元,(x,y,…),表示性質(zhì)、關(guān)系。,謂詞常元、謂詞變元(P,Q,…)，,,n元謂詞,n元命題函數(shù)，如G(x,y),論域？個體域，全總個體域,?,Existentiah,~,,?,Universah,~,2.1,個體,、謂詞和量詞,,2.1,個體,、謂詞和量詞,,有一個整數(shù)大于其他每個整數(shù),論域為整數(shù)集合：?,x,(,?,yG(x,y),),,,論域為全總域：,,?,x

3、,(,Z(x),??,y,(,Z(y),?,(x>y),),),,,,?,x,(,Z(x),??,y,(,(,Z(y),?N(x,y),),,?,(x>y),),),,2.1,個體,、謂詞和量詞,,2 “,任給,?,>0,，存在,?,>0,，如果,|x-a|<,?,，則,|f(x)-b|<,?,”,,（實數(shù)域）,,,(,?,?,),(,(,?,,>0),?,(,?,?,),(,(,?,>0),?,((|,x,-,a,|<,?,),?,(,f,(,x,)-,b,|<,?,)),),),,,3,蘇格拉底三段論：“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的?！?,(,全總個體域,),,,令,

4、F(x),：,x,是人，,G(x),：,x,是要死的，,a:,蘇格拉底，則可以形式化為：,,前提：,?,x(F(x),?,G(x)), F(a),,,結(jié)論：,G(a),,2.1,個體,、謂詞和量詞,,練習(xí),,1,在我們班同學(xué)中，并非所有同學(xué)都來自湖北。,,2 4,班有的同學(xué)準備周末去郊游。,,3,凡是有理數(shù)都可寫成分數(shù)。,,4,對于任意的,x, y,，都存在唯一的,z,，使得,x+y=z,。,,1.,個體、謂詞和量詞,,練習(xí),,1,在我們班同學(xué)中，并非所有同學(xué)都來自湖北。,,,令,S(x),：,x,是同學(xué)，,C(x),：,x,在我們班中，,E(x),：,x,來自湖北，則命題可符號化為：,??,

5、x((S(x),?,C(x)),?,E(x)),。,?,x(S(x),?,C(x),??,E(x)),。,,,2 4,班有的同學(xué)準備周末去郊游。,,?,x(R (x),?,S(x),?,T(x)),,,3,凡是有理數(shù)都可寫成分數(shù)。,,,?,x,(Q(,x,),?,F(,x,)),,,4,對于任意的,x, y,，都存在唯一的,z,，使得,x+y=z,。,,,?,x(,?,y(,?,z,((,x,+,y,=,z,),??,u,((,u,=,x,+,y,),?,(,u,=,z,))))),,,,定義2.4,表示單個個體的性質(zhì)或兩個以上個體關(guān)系的詞叫謂詞。,,定義2.5,表示具體性質(zhì)或關(guān)系的謂詞稱為謂

6、詞常元，表示抽象的或泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變元。,,,無論是謂詞常元或變元都用大寫英文字母,P,Q,R…,或帶下標的,Pi,Qi,Ri,…,表示，要根據(jù)上下文區(qū)分。,2.1,個體,、謂詞和量詞,,,,定義2.6,由一個謂詞(如,P),和,n,個個體變元(如,x1，x2，…，,xn,),組成的,P(x1，x2，…，,xn,)，,稱它為,n,元原子謂詞或,n,元命題函數(shù)，簡稱,n,元謂詞。,,當,n=1,時，稱一元謂詞；當,n=2,時，稱為二元謂詞，…。特別地，當,n=0，,稱為零元謂詞，即不帶個體變元的謂詞為零元謂詞。零元謂詞是命題，這樣命題與謂詞就得到了統(tǒng)一，因而可將命題看成特殊的謂詞

7、。,2.1,個體,、謂詞和量詞,,,,例2.1,分析下列命題的個體與謂詞。,,（1）5是質(zhì)數(shù)。,,,解,,“,5,”,是個體常元，,“,…,是質(zhì)數(shù),”,是謂詞，記為,P,。這里的謂詞是一元謂詞，屬于謂詞常元。,2.1.2 謂詞,,（2）張三與李四是同學(xué)。,,,解,,“,張三,”,與,“,李四,”,是個體常元，分別記為,a,，,b,，,“,…,與,…,是同學(xué),”,是謂詞，記為,Q,。這里的謂詞是二元謂詞，屬于謂詞常元。,,,（3）,x,與,y,具有關(guān)系,R。,,,解,,“,x,”,與,“,y,”,是個體變元，謂詞為,R,。這里的謂詞是二元謂詞，屬于謂詞變元。,,2.1.2 謂詞,,,例2.2,用

8、個體，謂詞表示下列命題。,,（1）張華是大學(xué)生。,,,解,令,a,：張華；,S(x,),：,x,是大學(xué)生。整個命題可表示為：,S(a,),。,,,說明,：,,①若,x,的個體域為某大學(xué)計算機系的全體學(xué)生，則,S(a,),為真；,,②若,x,的個體域為某中學(xué)的全體學(xué)生，則,S(a,),為假；,,③若,x,的個體域為某電影院中的觀眾，則,S(a,),真值不確定。所以個體變元在哪些個體域取特定的值，對命題的真值極有影響。,2.1.2 謂詞,,,（2）武漢位于重慶和上海之間。,,,,解,令,a,：武漢；,b,：重慶；,c,：上海；,P(x,y,z,),：,x,位于,y,和,z,之間。整個命題可表示為,

9、P(a,b,c,),。,,,,,說明,：顯然,P(a,b,c,),為真，但,P(b,a,c,),為假。所以個體變元的順序影響命題真值，不能隨意改動。,,2.1.2 謂詞,,,定義2.7,表示個體常元或變元之間數(shù)量關(guān)系的詞叫量詞；表示,“,全部,”,，,“,所有的,”,，,“,一切的,”,，,“,每一個,”,，,“,任意的,”,等數(shù)量關(guān)系的詞叫,全稱量詞,，用符號,“,?,”,表示；表示,“,存在一些,”,，,“,有一些,”,，,“,至少有一個,”,等數(shù)量關(guān)系的詞叫,存在量詞,，用符號,“,?,”,表示；表示,“,存在惟一,”,，,“,恰有一個,”,等數(shù)量關(guān)系的詞叫,存在惟一量詞,，用符號,“,

10、?,！,”,表示。,2.1.3 量詞,,,注意,：,量詞的優(yōu)先級高于任何聯(lián)結(jié)詞，所以,(,?,x)P(x,1,,x,2,,,…,,x,n,)、(,?,x)P(x,1,,x,2,,,…,,,x,n,)、,可分別寫成,?,xP(x,1,,x,2,,,…,,x,n,)、,?,xP(x,1,,x,2,,,…,,,x,n,)，,但要注意明確量詞的轄域（轄域?qū)⒃谙乱还?jié)討論）。,2.1.3 量詞,,,例2.3,符號化下列命題（設(shè)個體域為整數(shù)集合）。,,（1）所有的整數(shù)都是有理數(shù)。,,（2）有些整數(shù)是奇數(shù)。,,（3）存在著惟一的偶素數(shù)。,,,解,（,1,）令,P(x,),：,x,是有理數(shù)，則命題可表示為：,?

11、,xP(x,),。,,（,2,）令,Q(x,),：,x,是奇數(shù)，則命題可表示為：,?,xQ(x,),。,,（,3,）令,R(x,),：,x,是偶數(shù)，,S(x,),：,x,是素數(shù)，則命題可表示為,?,！,x(R(x),?,S(x,)),。,,,2.1.3 量詞,,定義2.9,由,n,元謂詞,P,和,n,個個體變元,x,1,，x,2,，,…,，,x,n,所構(gòu)成的不含命題聯(lián)結(jié)詞和量詞的謂詞表達式,P(x,1,，x,2,，,…,，,x,n,),稱為謂詞邏輯中的,原子謂詞公式,，簡稱,原子公式,。,,由定義可知，一個命題或一個命題變元也稱為原子公式，也就是說，當,n=0,時，,P(x,1,，x,2,，,

12、…,，,x,n,),為原子命題,P。,,2.2.1 謂詞公式與翻譯,,定義2.10,謂詞公式歸納定義如下：,,（1）原子公式是謂詞公式；,,（2）,如果,α,是謂詞公式，則,?,α,也是謂詞公式；,,（3）如果,α,和,β,是謂詞公式，則,α,?,β,，,α,?,β,，,β→α,和,α,?,β,也都是謂詞公式；,,（4）如果,α,是謂詞公式，,x,是個體變元，則,?,x,α,(x)，,?,x,α,(x,),和,?,！,x,α,(x,),也都是謂詞公式；,,（5）只有有限次地應(yīng)用（1）,～,（4）構(gòu)成的符號串才是謂詞公式。,,2.2.1 謂詞公式與翻譯,,由定義可知，謂詞公式是由原子公式、命題聯(lián)

13、結(jié)詞、量詞以及圓括號按照上述規(guī)則組成的一個符號串。因此，命題邏輯中的命題公式是謂詞公式的一個特例。,,為敘述方便，我們下面討論只含,“,?,x,”,和,“,?,x,”,的謂詞公式，事實上，量詞,“,?,！,x,”,可以通過量詞,“,?,x,”,和,“,?,x,”,來表示。,2.2.1 謂詞公式與翻譯,,,一般來說，將自然語言翻譯成謂詞公式主要有以下幾個,步驟,：,,,（1）確定個體域，如無特別說明，一般使用全總個體域；,,（2）根據(jù)個體域，分析命題中的個體、個體性質(zhì)以及各個個體間的關(guān)系，確定謂詞；,,（3）根據(jù)表示數(shù)量的詞確定量詞；,,（4）利用聯(lián)結(jié)詞將整個命題符號化。,2.2.1 謂詞公式與

14、翻譯,,,例2.,5,,將下列命題符號化。,,（1）,教室里有同學(xué)在講話。,,,解,因為題中沒有特別指明個體域，所以這里采用全總個體域。,,令,S(x,),：,x,是同學(xué)，,R(x,),：,x,在教室里，,T(x,),：,x,在講話，則命題可符號化為：,?,x(S(x),?,R(x),?,T(x,)),。,2.2.1 謂詞公式與翻譯,,,（2）,在我們班中，并非所有同學(xué)都能取得優(yōu)秀成績。,,,解,,令,S(x,),：,x,是同學(xué)，,C(x,),：,x,在我們班中，,E(x,),：,x,能取得優(yōu)秀成績，,,則命題可符號化為：,??,x((S(x),?,C(x)),?,E(x,)),。,,或者，此

15、命題也可以理解為,“,在我們班中存在不能取得優(yōu)秀成績的同學(xué),”,，,,則該命題也可符號化為：,?,x(S(x),?,C(x),??,E(x,)),。,,2.2.1 謂詞公式與翻譯,,,（3）沒有最大的自然數(shù)。,,,解,,命題中,“,沒有最大的,”,顯然是對所有的自然數(shù)而言，所以可理解為,“,對任意的自然數(shù),x,，存在著比,x,更大的自然數(shù),”,。令,N(x):x,是自然數(shù)，,G(x,y):x,大于,y,，則命題可符號化為：,?,x(N(x),??,y(N(y),?,G(y,x,))),。,,2.2.1 謂詞公式與翻譯,,（4）今天有雨雪，有些人會跌跤。,,,解,,令,R,：今天下雨，,S,：今

16、天下雪，,M(x,),：,x,是人，,F(x,),：,x,會跌跤，則命題可符號化為：,(,R,?,S),??,x(M(x),?,F(x,)),。,,2.2.1 謂詞公式與翻譯,,,定義2.11,,設(shè),α,是謂詞公式，,β,是,α,中連續(xù)的符號串且也是謂詞公式，則稱,β,是,α,的,子公式,。,,例如，,α=,?,x(P(x),??,y(Q(y),?,R(x,y)))，β,=,?,y(Q(y),?,R(x,y,))，,則,β,是,α,的子公式。而,P(x),??,y,不是謂詞公式，因而也不是,α,的子公式。,,2.2.1 謂詞公式與翻譯,,2,謂詞公式,,2.2.2,自由變元與約束變元,,,設(shè),

17、?,是一個謂詞公式，,?,x,?,(x)和,?,x,?,(x)是,?,的,子公式,，則稱,?,x,?,(x)與,?,x,?,(x)是,?,的,約束部分,（Bound Part），x稱為是,約束出現(xiàn),（Bound Occurrence）的。約束出現(xiàn)的變元稱為,約束變元,（Bound Variabhe），不是約束出現(xiàn)的變元稱為,自由變元,（Free Variabhe）。,?,(x)稱為是,?,x在,?,中的,轄域,（Scope）或,作用域,，,?,(x)稱為是,?,x在,?,中的轄域。,,,,2,謂詞公式,,1,量詞后的用,括號,括起來的子公式就是其轄域，如果子公式是原子公式，則括號可以去掉。,,

18、2,當,多個量詞連續(xù),出現(xiàn)，它們之間無括號,分隔時，后面的量詞在前面量詞的轄域之中，且量詞對變元的約束與,量詞的次序,有關(guān)，一般不能隨意改動,。,,2,謂詞公式,,示例,指出下列公式中，各量詞的轄域以及變元的,,自由出現(xiàn)和約束出現(xiàn)：,,1,?,x(F(x, y, z),??,yG(x, y)),,2,?,xF(x, y),?,G(x, y),,3,?,x,?,y(F(x),?,G(y),?,H(x, y)),,4,,?,x,?,y(F(x),?,G(y),?,H(x, y)),,2,謂詞公式,,練習(xí),,指出下列公式中，各量詞的轄域以及變元的,,自由出現(xiàn)和約束出現(xiàn)：,,,（,1,）,?,x(P(

19、x),??,y(Q(y),?,R(x,y))),,（,2,）,?,x(P(x),?,Q(y)),??,yR(x,y),,2,謂詞公式,,2.2,,變元的改名與代入,,為了清晰起見，通常運用,改名,(換名)規(guī)則和,代入,(替換)規(guī)則,,使得公式A滿足下列條件：,,所有變元在公式A中要么自由出現(xiàn)，要么約束出現(xiàn)，不要既有自由出現(xiàn)，又有約束出現(xiàn)。,,所有量詞后面采用的約束變元互不相同。,,,2,謂詞公式,,約束,變元改名規(guī)則和,自由,變元代入規(guī)則,,,改名規(guī)則,：將量詞中的作用變元,x,以及該量詞的轄域中相應(yīng)全部,約束變元,x,都用相同的原公式中不出現(xiàn)的新個體變元,y,替換，得到公式與原公式等價。,,

20、代入規(guī)則,：將公式所有,自由變元,x,改為不在該公式中出現(xiàn)的新變元,y,，得到公式與原公式等價。,,2,謂詞公式,,示例,,對公式,?,x,(,P(x,y),∧,?,yQ(y),∧,M(x,y),),∧,(,?,xR(x),?,Q(x),),中,,的約束變元進行改名。,使每個變元在公式中只以一種形式出,,現(xiàn)（即約束出現(xiàn)或自由出現(xiàn)）。,,解,,在該公式中，將P(x,y)和M(x,y)中的約束變元x改名為z，R(x)中的x改名為s，Q(y)中的y改名為t，改名后為：,,,?,z(P(z,y),??,tQ(t),?,M(z,y)),?,(,?,sR(s),?,Q(x)),,,2,謂詞公式,,練習(xí),,

21、使用換名規(guī)則和代入規(guī)則變換下列公式,,,1,?,x((P(x),?,R(x)),?,S(x)),??,x(P(x),?,Q(x)),,2,?,x(P(x),?,Q(x)),??,xR(x),?,S(x),,3,?,xP(x),??,xQ(x),?,(,?,xP(x),?,Q(x)),,2,謂詞公式,,練習(xí),,1,?,x((P(x),?,R(x)),?,S(x)),??,x(P(x),?,Q(x)),,,?,x((P(x),?,R(x)),?,S(x)),??,y,(P(,y,),?,Q(,y,)),,,2,?,x(P(x),?,Q(x)),??,xR(x),?,S(x),,,?,x(P(x),

22、?,Q(x)),??,y,R(,y,),?,S(,z,),,,3,?,xP(x),?,(,?,x)Q(x),?,(,?,xP(x),?,Q(x)),,,?,xP(x),?,(,?,y,)Q(,y,),?,(,?,z,P(,z,),?,Q(,u,)),,2,謂詞公式,,,給定一個文字敘述的命題，可以符號化為謂詞公式．反之，給定一個謂詞公式，它表達怎樣的意義？這涉及,謂詞邏輯,的,語義,問題．由于謂詞公式僅僅是由一些抽象符號構(gòu)成，只有對它們,解釋,和賦值后，才能討論公式的意義，公式可能真或可能假。,,2,謂詞公式,,2.3,,公式真值,論域,,賦值,,,個體變元,,,命題,變元,,,謂詞,,量化,

23、,量詞,量化,謂詞,,2,謂詞公式,,{,論域,， 個體變元/常元取值，,命題,變元,、,謂詞,取值},解釋,指 派,個體變元取值，命題,變元取值,,,定義2.12,設(shè)有一謂詞公式,α，,其自由個體變元為,x,1,,x,2,,,…,,,x,h,；,命題變元為,P,1,,P,2,,,…,,,P,k,，,則我們把,α,表示為：,,,α,(x,1,,x,2,,,…,,x,h,；P,1,,P,2,,,…,,,P,k,),,如果對個體域指定以,D，,對,x,1,,x,2,,,…,,,x,h,在個體域上分別指派以個體,a,1,,a,2,,,…,,a,h,；,對,P,1,,P,2,,,…,,,P,k,分

24、別指派以,P,1,*,,P,2,*,,,…,,,P,k,*,(,其中,P,i,*,或為0,或為1，,i=1,2,,…,,k)，,則稱對,α,作了一個個體域,D,上的,指派,，記為,α(a,1,,a,2,,,…,,a,h,； P,1,*,,P,2,*,,,…,,,P,k,*,)。,如果該值為真，則該指派為,α,的,成真指派,；如果該值為假，則該指派稱為,α,的,成假指派,。,2.2.3 謂詞公式的分類,,例2.,9,,求公式,α,=,?,x(P(x),?,Q(x,y)),?,R,的成真指派和成假指派，其中,P(x,),表示,“,x,是偶數(shù),”,，,Q(x,y,),表示,“,y,能整除,x,”,,

25、,α,的個體域,D={3,4}，R,是命題變元。,,解,,2.2.3 謂詞公式的分類,y R,?,x(P(x),?,Q(x,y,)),?,3 0,,3 1,,4 0,,4 1,0,,0,,1,,1,0,,1,,1,,1,,定義2.13,如果公式,α,對個體域,D,中任何指派均取得真值，則稱,α,為,D,中的,永真式,；如果均取得假值，則稱,α,為,D,中的,永假式,；如果至少有一個指派取得真值，則稱,α,為,D,中的,可滿足式,。,2.2.3 謂詞公式的分類,,,例2.1,0,,判斷下列公式的類型。,,（1）,?,x,?,yG(x-y,x+y),?,(Q,??,Q,),,（

26、2）G(x-y,x+y),,（3）,?,x,?,y(G(x,y),??,G(x,y)),?,Q,,其中,x,y,的個體域為整數(shù)集,I，Q,為命題變元，,G(x,y,),表示,x,?,y,。,,,2.2.3 謂詞公式的分類,,定義2.14,設(shè),α，β,為任意兩個謂詞公式，它們有共同的個體域,D，,若在,D,中,α,?,β,為永真式，則稱公式,α,和,β,在,D,上等值，記為,α,?,β,，,稱,α,?,β,為,等值式,。,2.3.1 等值式的基本概念,,2.3,等值演算,,謂詞邏輯中特有的等值式,,,[1].,在,有限,個體域,D = {,a,1,,a,2,,…,a,n,},中,消除量詞,：,,

27、,(1).,?,xA(x),?A(a,1,)?A(a,2,)?,…,?A(a,n,),,,(2).,?xA(x)?A(a,1,)?A(a,2,)?,…,?A(a,n,),,,[2].,量詞否定,等值式：,,,(1).,?,(,?,x,A(,x,)),?,,?,x,(,?,A(,x,)),,(2).,?,(,?,x,A(,x,)),?,,?,x,(,?,A(,x,)),,,2.3,等值演算,,[3].,量詞分配,等值式：,,(1).,?,x(A(x),?,B(x)),?,(,?,xA(x)),?,(,?,xB(x)),,(2).,?,x(A(x),?,B(x)),?,(,?,xA(x)),?,(

28、,?,xB(x)),,,[4].,量詞順序變換,等值式：,,(1).,?,x,?,y(A(x, y)),?,,?,y,?,x(A(x, y)),,(2).,?,x,?,y(A(x, y)),?,,?,y,?,x(A(x, y)),,2.3,等值演算,,[5].,量詞轄域的收縮與擴張,等值式：,下述等值式中，變元,x,不在,B,中出現(xiàn),,(1).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(2).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(3).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(4

29、).,?,x,(B,?,A(,x,)),?,B,?,(,?,x,A(,x,)),,(5).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(6).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(7).,?,x,(A(,x,),?,B),?,(,?,x,A(,x,)),?,B,,(8).,?,x,(B,?,A(,x,)),?,B,?,(,?,x,A(,x,)),注意，,應(yīng)用這些公式時,，,公式中，合?。ㄎ鋈。┑膬蓚€分支，和蘊涵的前件與后件選取的約束變元不同，當約束變元相同時，且又不能運用,?,對,?,的分配律和,?,對,?,的分配律時

30、則可使用換名規(guī)則，使得約束變元不同。,,,2.3,等值演算,,,示例,證明,,?,x(A(x),?,B(x)),??,xA(x),??,xB(x),,,證明,,,,令個體域為D，設(shè)在,任一,指派,?,下，,若,左式,?,T，則在D中存在,一個,個體,c使得A(c),?,B(c),?,T，從而A(c),?,T或B(c),?,T，因此有,?,xA(x),?,T或,?,xB(x),?,T，所以,?,xA(x),??,xB(x),?,T。,,,,反之，設(shè)在,任一,指派,?,下，,若,右式,?,T，則,?,xA(x),?,T或,?,xB(x),?,T，即在D中存在,兩個個體,c，d使得A(c),?,T或

31、B(d),?,T，從而在D中存在一個個體c或d（不妨設(shè),為,c）使得A(c),?,B(c),?,T，,,所以,?,x(A(x),?,B(x)),?,T。,,由以上兩方面知等值式成立。,,2.3,等值演算,,,示例,證明等值式。,,?,x(A(x),?,B(x)),??,xA(x),?,?,xB(x),,,證明,,?,x(A(x),?,B(x)),,,??,x(,?,A(x),?,B(x)),,,??,x,?,A(x),??,xB(x),,,???,xA(x),??,xB(x),,,??,xA(x),??,xB(x),,2.3,等值演算,,示例,,?,x,?,y(P(x)→Q(y)),??,xP

32、(x)→,?,yQ(y),,證明 ?,x,?,y(P(x),?,Q(y,)),,??,x,?,y(,?,P(x),?,Q(y,)),,??,x(,?,P(x),??,yQ(y,)),,??,x,?,P(x),??,yQ(y,),,???,xP(x),??,yQ(y,),,??,xP(x),??,yQ(y,),,,2.3,等值演算,,練習(xí),判斷以下式子是否成立？,,(1),?,xA(x),∧,?,xB(x),??,x(A(x),∧,B(x)),,(2),?,xA(x),∨,?,xB(x),??,x(A(x),∨,B(x)),,（3）?,x,?,yP(x,y),??,y,?,xP(x,y),,2

33、.3,等值演算,,?,x,(A(,x,),?,B(,x,)),?,(A(,a,),?,B(,a,)),?,(A(,b,),?,B(,b,)),?,(A(,c,),?,B(,c,)),,?,(A(,a,),?,A(,b,),?,A(,c,)),?,(B(,a,),?,A(,b,),?,A(,c,)),?,(A(,a,),?,B(,b,),?,A(,c,)),?,(B(,a,),?,B(,b,),?,A(,c,)),?,(A(,a,),?,A(,b,),?,B(,c,)),?,(B(,a,),?,A(,b,),?,B(,c,)),?,(A(,a,),?,B(,b,),?,B(,c,)),?,(B(

34、,a,),?,B(,b,),?,B(,c,)),,,,而,,(,?,x,A(,x,)),?,(,?,x,B(,x,)),?,(A(,a,),?,A(,b,),?,A(,c,)),?,(B(,a,),?,B(,b,),?,B(,c,)),,2.3,等值演算,,設(shè),D = {,a,,,b,,,c,},，則：,,(i).,,?,x,?,y,A(,x,,,y,),?,,?,y,A(,a,,,y,),?,,?,y,A(,b,,,y,),?,,?,y,A(,c,,,y,),,?,(A(,a,,,a,),?,A(,a,,,b,),?,A(,a,,,c,)),?,(A(,b,,,a,),?,A(,b,,,b,

35、),?,A(,b,,,c,)),?,(A(,c,,,a,),?,A(,c,,,b,),?,A(,c,,,c,)),,,(ii).,,?,x,?,y,A(,x,,,y,),,?,,?,y,A(,a,,,y,),?,,?,y,A(,b,,,y,),?,,?,y,A(,c,,,y,),,?,(A(,a,,,a,),?,A(,a,,,b,),?,A(,a,,,c,)),?,(A(,b,,,a,),?,A(,b,,,b,),?,A(,b,,,c,)),?,(A(,c,,,a,),?,A(,c,,,b,),?,A(,c,,,c,)),,(iii).,,?,x,?,y,A(,x,,,y,),?,,?,y,A

36、(,a,,,y,),?,,?,y,A(,b,,,y,),?,,?,y,A(,c,,,y,),,?,(A(,a,,,a,),?,A(,a,,,b,),?,A(,a,,,c,)),?,(A(,b,,,a,),?,A(,b,,,b,),?,A(,b,,,c,)),?,(A(,c,,,a,),?,A(,c,,,b,),?,A(,c,,,c,)),,,(iv).,,?,x,?,y,A(,x,,,y,),?,,?,y,A(,a,,,y,),?,,?,y,A(,b,,,y,),?,,?,y,A(,c,,,y,),,?,(A(,a,,,a,),?,A(,a,,,b,),?,A(,a,,,c,)),?,(A(,

37、b,,,a,),?,A(,b,,,b,),?,A(,b,,,c,)),?,(A(,c,,,a,),?,A(,c,,,b,),?,A(,c,,,c,)),,4,范式,,前束范式,,,設(shè),A,為謂詞邏輯公式，若,A,具有如下形式：,,,Q,1,x,1,Q,2,x,2,…Q,n,x,n,B,,則稱,A,為前束范式,(Prenex,Normah,Form),。其中,Q,i,(1,?,,i,?,n),,是,?,或,?,，,B,為不含量詞,的謂詞公式,。,,,,前束合取范式、前束析取范式,,,示例,,?,y,?,u,?,v(A(x,y),?,B(u,y),→,R(u,v)),,4,范式,,如何求解前束范式

38、？,,,(1),消,去聯(lián)結(jié)詞,→,，,?,及多余的量詞；,,,(2),將聯(lián)結(jié)詞,?,向內(nèi)深入，使之只作用于原子謂詞公式；,,,(3),利用,改名或代入,規(guī)則使所有約束變元的符號均不同，并且自由變元與約束變元的符號也不同；,,,(4),利用,量詞轄域,的擴張與收縮律，擴大量詞的轄域至整個公式。,,,前束范式一定存在嗎？,,,定理,1.3,,任意,一個謂詞公式,都存在著與之等值的,前束范式。,,4,范式,,示例,,將公式,?,x,?,y(,?,z(P(x,z),?,P(y,z))→,?,zQ(x,y,z)),化為前束范式。,,,,解,,?,x,?,y(,?,z(P(x,z),?,P(y,z)),?

39、?,zQ(x,y,z)),,,??,x,?,y(,??,z(P(x,z),?,P(y,z)),??,zQ(x,y,z)),（消去,?,）,,,??,x,?,y(,?,z(,?,P(x,z),??,P(y,z)),??,zQ(x,y,z)),（,?,深入）,,,??,x,?,y(,?,z(,?,P(x,z),??,P(y,z)),??,uQ(x,y,u)),（改名）,,,??,x,?,y,?,z,?,u(,?,P(x,z),??,P(y,z),?,Q(x,y,u)),（量詞前移）,,,4,范式,,定義2.17,一個公式,α,，,如果具有形式：,,Q1x1Q2x2,…,Qnxn((,α,11,?,

40、α,12,?,…,?,α,1h1),?,(,α,21,?,α,22,?,…,?,α,2h2),?,…,?,(,α,m1,?,α,m2,?,…,?,α,mhm,)),,則稱該式為,前束合取范式,。,,一個公式,α,，,如果具有形式：,,Q1x1Q2x2,…,Qnxn((,α,11,?,α,12,?,…,?,α,1h1),?,(,α,21,?,α,22,?,…,?,α,2h2),?,…,?,(,α,m1,?,α,m2,?,…,?,α,mhm,)),,則稱該式為,前束析取范式,。,,其中：,Qi(i,=1,2,,…,,n),為,?,或,?,，,xi,為,,個體變元，,α,ij,為原子謂詞公式或其否定

41、。,,,4,范式,,定理,2.4,,任意一個謂詞公式,都存在著與之等值的,前束合?。ㄎ鋈。┓妒?。,,,將一個謂詞公式化為前束,合取范式或前束析取范式時，只需在前面求前束范式的（1）,--,（4）四個步驟基礎(chǔ)上再增加一個步驟：,,（5）利用分配律將公式化為前束合取范式或前束析取范式。,,,4,范式,,示例,將公式,??,x(,?,yA(x,y),→?,x,?,y(B(x,y),??,y(A(y,x),→,B(x,y)))),化為前束合取范式和前束析取范式。,,,解,,??,x(,?,yA(x,y),?,?,x,?,y(B(x,y),??,y(A(y,x),?,B(x,y)))),,?,??,x,

42、(,??,yA(x,y),?,(?,x,?,y(B(x,y),?,?,u,(,?,A(,u,,x),?,B(x,,u,))))),,?,?,x,(,?,yA(x,y),?,?,(?,x,?,y(B(x,y),?,?,u,(,?,A(u,x),?,B(x,u))))),,??,x(,?,yA(x,y),?,?,(?,x,?,y,?,u,(B(x,y),?,(,?,A(u,x),?,B(x,u))))),,??,x(,?,yA(x,y),??,v,?,w,?,u(,?,B(v,w),?,(A(u,v),?,?,B(v,u)))),,,?,?,x,?,y,?,v,?,w,?,u,(A(x,y),?,

43、?,B(v,w)),?,(A(x,y),?,A(u,v),?,?,B(v,u))),,,4,范式,,示例,求下列公式的前束范式,：,,[1].,?,x,F(,x,,,y,),?,,?,y,F(,x,,,y,),,[2].,?,x,?,y,F(,x,,,y,),?,,?,x,?,y,F(,x,,,y,),,[3].,?,x,F(,x,,,y,),?,(,?,x,G(,x,),?,,?,y,F(,y,,,z,)),,解,,[1].,?,x,F(,x,,,y,),??,y,F(,x,,,y,),?,,?,x,F(,x,,,u,),?,,?,y,F(,v,,,y,),?,,?,x,?,y,(F(,x,

44、,,u,),?,F(,v,,,y,)),，顯然不能變換為：,?,x,?,y,(F(,x,,,y,),?,F(,x,,,y,)),。,,,[2].,?,x,?,y,F(,x,,,y,),?,,?,x,?,y,F(,x,,,y,),?,,?,x,?,y,F(,x,,,y,),?,,?,u,?,v,F(,u,,,v,),,,?,,?,x,(,?,y,F(,x,,,y,),?,,?,u,?,v,F(,u,,,v,)),?,,?,x,?,y,(F(,x,,,y,),?,,?,u,?,v,F(,u,,,v,)),,,?,,?,x,?,y,?,u,?,v,(F(,x,,,y,),?,F(,u,,,v,)),

45、?,…,,[3].,?,x,F(,x,,,y,),?,(,?,x,G(,x,),?,,?,y,F(,y,,,z,)),?,,?,x,F(,x,,,u,),?,(,?,v,G(,v,),?,,?,y,F(,y,,,z,)),?,,?,x,F(,x,,,u,),?,(,?,v,?,y,(G(,v,),?,F(,y,,,z,))),?,,?,x,?,v,?,y,(F(,x,,,u,),?,(G(,v,),?,F(,y,,,z,))),?,…,,4,范式,,前束范式的,優(yōu)點,是全部量詞集中在公式前面，其,缺點,是全稱量詞與存在量詞的排列無一定規(guī)則，這樣當把一個公式化為前束范式時，其表達形式會顯現(xiàn)多種情

46、形，不便應(yīng)用。,,1920年,司柯倫,(,Skolem,),提出對前束范式中量詞出現(xiàn)的次序給出規(guī)定：每個存在量詞均在全稱量詞之前。按此規(guī)定得到的范式形式，稱為司柯倫范式。顯然，任意一個謂詞公式均可化為,司柯倫范式,。它的優(yōu)點是：全公式按順序可分為三部分，公式的所有存在量詞、所有全稱量詞和轄域。這給謂詞邏輯的研究提供了一定的方便。,,例如，,?,x,?,y,?,z(P(x,y),?,(Q(y,z),?,R(x,))),是司柯倫范式。,,5,推理理論,,推理定律,,1,命題邏輯中的,蘊涵推理式，通過代入,得到的謂詞邏輯推理定律；由謂詞邏輯中的,等值式,得到的,推理定律。,,如在命題邏輯中有公式：,

47、,,α,?,β,?,α，α,?,α,?,β,，,,可推廣而得：,,?,xA(x),??,yB(y),??,xA(x,)，,,?,xA(x),??,xA(x),??,yB(y,),等等。,,5,推理理論,,2. 由基本等值式生成的推理定律,,2.3節(jié)給出的等值式中的每個等值式可生成兩個推理定律。例如，,,?,xA(x),????,xA(x)，,???,xA(x),??,xA(x,),,和,??,xA(x),??,x,?,A(x,),,?,x,?,A(x),???,xA(x,),,等等。,,5,推理理論,,2,謂詞邏輯特有的推理定律,,,(1) (,?,x,A(,x,)),?,(,?,x,B(,

48、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,推理理論,,多個量詞的謂詞公式的推理？,,,(1).,?,x,?,yA(x, y),?,,?,y,?,xA(x, y),,(2).,?,x,?,yA(x, y),?,,?

49、,y,?,xA(x, y),,(3).,?,y,?,xA(x, y),?,,?,x,?,yA(x, y),,(4).,?,x,?,yA(x, y),?,,?,y,?,xA(x, y),,(5).,?y?x,A(x, y),?,,?x?y,A(x, y),,(6).,?,x,?,yA(x, y),?,,?,y,?,xA(x, y),,(7).,?,y,?,xA(x, y),?,,?x?y,A(x, y),,(8).,?,x,?,yA(x, y),?,,?,y,?,xA(x, y),,,5,推理理論,,推理規(guī)則,,命題邏輯中的推理規(guī)則,,謂詞邏輯中特有的規(guī)則,,1.,全稱量詞消去規(guī)則,（,US,）

50、,,（,i,）,?,xA(x),?,A(y),或,,（,ii,）,?,xA(x),?,A(c),,2.,全稱量詞引入規(guī)則,（,UG,）,,,A(y),??,xA(x),,3.,存在量詞消去規(guī)則,（,ES,）,,?,xA(x),?,A(c),,,4.,存在量詞引入規(guī)則,（,EG,）,,,A(c),??,xA(x),,,5,推理理論,,1.,全稱量詞消除規(guī)則（,US,規(guī)則）,,,(i).,?,x,A(,x,),?,A(,y,),,(ii).,?,x,A(,x,),?,A(,c,),,,成立的條件是：,,,(1).,x,是,A(,x,),的自由變元；,,,(2).,在,(i),中，,y,為不在,A(

51、,x,),中約束出現(xiàn)的變元，,y,可以在,A(,x,),中自由出現(xiàn)，也可在證明序列中前面的公式中出現(xiàn)。,,,(3).,在,(ii),中，,c,任意的個體常量，可以是證明序列中前面公式所指定的個體常量。,,不存在最大的實數(shù)：,,?,x,?,y(y,>,x,),,?,y(,y,>y),,5,推理理論,,2 全稱量詞引入規(guī)則（UG規(guī)則）,,,A(y),?,,?,xA(x),,成立的條件是：,,(1). y在A(y)中自由出現(xiàn),，且任意,y,，,A(y,),為真,；,,(2). 替換y的x要選擇在A(y)中不出現(xiàn)的變元符號；,?,z(z,>,y,),,,,?,z,?,z(,z,>,z,),,,5,推理

52、理論,,3,存在量詞引入規(guī)則（,EG,規(guī)則）,,,A(c),?,,?,xA(x),,,成立的條件是：,,,(1).c,是特定的個體常量；,,,(2).,替換,c,的,x,要選擇在,A(c),中不出現(xiàn)的變元符號；,(1). P(,x,),?,Q(,c,),,,(2). (,?,x,)(P(,x,),?,Q(,x,)),,,,在使用存在量詞引入規(guī)則時，替換個體,c,的變元應(yīng)選擇在公式中沒有出現(xiàn)的變元符號，正確的推理是：,,,(1). P(,x,),?,Q(,c,),,(2). (,?,y,)(P(,x,),?,Q(,y,)),,5,推理理論,,4,存在量詞消除規(guī)則（,ES,規(guī)則）,,,?,xA(x

53、),?,A(c),,,成立的條件是：,,,(1).c,是特定的個體常量，,c,不能在前面的公式序列中出現(xiàn)；,,,(2).c,不在,A(x),中出現(xiàn)；,,,(3).A(x),中自由出現(xiàn)的個體變元只有,x,。,(1),(,?,x,)(,?,y,)(,x,>,y,) //,P,,(2).(,?,y,)(,z,>,y,),,// US,,(3).(,z,>,c,) // ES,,(4).(,?,x,)(,x,>,c,),,// UG,,(5).,c,>,c,// US,,,,由(2)得到(3)不能使用存在量詞消除規(guī)則，因為(2)中含有除,y,以外的自由變元,z,。,,,5,推理理論,,推理方法,,

54、,直接法,,,間接法（反證法、,CP,規(guī)則）,,5,推理理論,,示例,,,,證明,(,?,x)(C(x)→W(x)∧R(x))∧(,?,x,) (,C(x)∧Q(x,))=> (,?,x) (Q (,x)∧R(x,)),,【,分析,】,謂詞邏輯的推理演算不能用真值表法，所以證明方法有直接證法、反正法和,CP,規(guī)則法。當要推理的結(jié)論是蘊含式時才能用,CP,規(guī)則法，能用,CP,規(guī)則法的盡量用,CP,規(guī)則法，因為此方法增加了一個前提條件。該題只能用直接證法、反正法。,,5,推理理論,,證明方法一（直接證法）：,,1) (,?,x)(C(x)→W(x)∧R(x,)) P,,2) (,

55、?,x) (,C(x)∧Q(x,)) P,,3) (,C(a)∧Q(a,)) ES, 2),,4),C(a)→W(a)∧R(a,) US,1),,5),C(a,) T,I,3),,6),W(a)∧R(a,) T,I,4),、,5),,7),Q(a,) T,I,3)

56、,,8),R(a,) T,I,6),,9),Q(a)∧R(a,) T,I,7),、,8),,10) (,?,x) (Q (,x)∧R(x,)) EG,9),3),C(a)→W(a)∧R(a,) US,1),,,4) (,C(a)∧Q(a,)) ES, 2),,(3),、,4),次序不能顛倒,),,5,推理理論,,示例,,將下列推理符號化并給出形式證

57、明,:,,,晚會上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（個體域為參加晚會的人）,,,解,設(shè),P(x),：,x,唱歌了，,Q(x),：,x,跳舞了，則,,前提：,?,x(P(x),?,Q(x)),,結(jié)論,：,?,xP(x),??,xQ(x),,推理形式：,?,x(P(x),?,Q(x)),??,xP(x),??,xQ(x),,5,推理理論,,,,(1),?,(,?,xP(x),??,xQ(x)) P(,附加,),,(2),?,x,?,P(x),??,x,?,Q(x) R,E,(1),,(3),?,x,?,P(x) T,I,

58、(2),,(4),?,P(a) ES,(3),,(5),?,x,?,Q(x) T,I,(2),,(6),?,Q(a) US,(5),,,,(7),?,x(P(x),?,Q(x)) P,,(8) P(a),?,Q(a) US,(7),,(9) Q(a) T,I,(4),(8),,(10) Q(a),??,Q(a),T,I,(6),(9),,矛盾,,因此，假設(shè)不成立，原推理形式正確。,,5,推理理論,,示例,所有的有理數(shù)都是實數(shù)

59、；所有的無理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無理數(shù)。,,解,個體域為全總域，需要引入的謂詞包括：,,,Q(,x,):,x,,是有理數(shù)；,R(,x,):,x,是實數(shù)；,N(,x,):,x,是無理數(shù)；,C(,x,):,x,是虛數(shù)。上述推理可符號化為：,,,前提,：,?,x,(Q(,x,),?,R(,x,)),、,?,x,(N(,x,),?,R(,x,)),、,?,x,(C(,x,),?,,?,R(,x,)),,,結(jié)論,：,?,x,(C(,x,),?,(,?,Q(,x,),?,,?,N(,x,)),，,,驗證該結(jié)論的公式序列如下：,,,5,推理理論,,,(1).,?,x,(Q

60、(,x,),?,R(,x,)) // P,,(2). Q(,y,),?,R(,y,) // US,,(3).,?,x,(N(,x,),?,R(,x,)) // P,,(4). N(,y,),?,R(,y,) // US,,(5).,?,x,(C(,x,),?,,?,R(,x,)) // P,,(6). C(,y,),?,,?,R(,y,) // US,,(7). C(,y,) // P(附加),(8).,?,R(,y,) // 分離規(guī)則，(6)和(7),,(9).,?,Q(,y,)

61、 // 拒取式，(8)和(2),,(10).,?,N(,y,) // 拒取式，(8)和(4),,(11).,?,Q(,y,),?,,?,N(,y),// 合取的引入,,(12). C(,y,),?,(,?,Q(,y,),?,,?,N(,y,) // T, I (7)和(11),,(13).,?,x,(C(,x,),?,(,?,Q(,x,),?,,?,N(,x,)) //UG,,5,推理理論,,示例,每個旅客或者坐頭等艙或者坐二等艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等艙。,,解,個體域為全總域，

62、引入下列謂詞：,P(,x,):,x,是旅客；,Q(,x,):,x,坐頭等艙；,R(,x,):,x,坐二等艙；,S(,x,):,x,是富裕的。,,原推理可符號化為：,,,前提,：,?,x,(P(,x,),?,(Q(,x,),?,R(,x,))),、,?,x,(P(,x,),?,(Q(,x,),?,S(,x,))),、,?,x,(P(,x,),?,S(,x,)),、,?,(,?,x,(P(,x,),?,S(,x,))),,,結(jié)論,：,?,x,(P(,x,),?,R(,x,)),，驗證該結(jié)論的公式序列如下：,,5,推理理論,,(1).,?,(,?,x,(P(,x,),?,S(,x,))) //

63、P,,(2).,?,x,(P(,x,),??,S(,x,)) // T, I (2),,(3). P(,c,),??,S(,c,) // ES,,(4). P(,c,) // T, I (3),,(5).,?,S(,c,) // T, I (3),,(6).,?,x,(P(,x,),?,(Q(,x,),?,R(,x,))) // P,,(7). P(,c,),?,(Q(,c,),?,R(,c,)) // US, (6),,(8). Q(,c,),?,R(,c,) // T, I (4)(7),(9).,?,x,(P(,x,)?,(Q(,x,)

64、?,S(,x,)))//P,,(10).P(,c,)?,(Q(,c,)?,S(,c,))// US(9),,(11).Q(,c,)?,S(,c,) // T, I (4)(11),,(12).Q(,c,)?,S(,c,)// T, I(11),,(13). ?,Q(,c,) // T, I (12)(5),,(14). R(,c,) // T, I (13)(8),,(15). P(,c,) ?,R(,c,)// T, I(4)(14),,(16). ?,x,(P(,x,)?,R(,x,)) // EG,,5,推理理論,,,練習(xí),,每一個大學(xué)生不是文科生就是理科生；有的大學(xué)生愛好文學(xué)；小張不是

65、文科生但他愛好文學(xué)。因此，如果小張是大學(xué)生，他就是理科生；,,,解,：個體域取全總域，要引入的謂詞包括：,,,P(,x,):,x,,是一個大學(xué)生；,Q(,x,):,x,是文科生；,S(,x,):,x,,是理科生；,T(,x,):,x,,愛好文學(xué)。,,要引入的個體常量是：,c,:,小張。,,因此上述推理可符號化為：,,,前提,：,?,x,(P(,x,),?,(Q(,x,),?,S(,x,))),、,?,x,(P(,x,),?,T(,x,)),、,?,Q(,c,),?,T(,c,),,,結(jié)論,：,P(,c,),?,S(,c,),，,,驗證該結(jié)論的公式序列為：,,,5,推理理論,,,(1).,?,Q(,c,),?,T(,c,) // P,,(2).,?,x,(P(,x,),?,(Q(,x,),?,S(,x,))) // P,,(3). P(,c,),?,(Q(,c,),?,S(,c,)) // US (2),,(4). P(,c,) // P,（附加）,,,(5). Q(,c,),?,S(,c,) // T, I (3)(4),,(6).,?,Q(,c,) // T, I (1),,(7). S(,c,) // T, I (5)(6),,