離散數(shù)學(xué)-謂詞邏輯

1、第二章 謂詞邏輯 （Predicate Logic）,歷史使人聰明，詩歌使人機智，數(shù)學(xué)使人精細，哲學(xué)使人深邃，道德使人嚴(yán)肅，邏輯與修辭使人善辯。 Bacon Francis,第二章 謂詞邏輯,2.1謂詞的概念與表示(Predicate and it

2、s expression)2.2謂詞公式與翻譯(Predicate formulae)2.3約束變元與自由變元(Free and Bound variable)2.4 謂詞的解釋與類型(Interpretation & types of predicate calculus) 2.5謂詞演算的等價式與蘊含式(Equivalences & implications of predicat

3、e calculus)2.6前束范式(Prenex normal form)2.7謂詞演算的推理理論(Inference theory of predicate calculus),2.1 謂詞的概念與表示(Predicate and Its Expression),在Ls中，把命題分解到原子命題為止，認(rèn)為原子命題是不能再分解的，僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。命題邏輯的局限性： （

4、1） 它不能揭示某些有效的論證； （2） 無法將具有某種共同屬性的命題顯示出來，甚至對于含有變量的判斷都無法用命題來描述。,例如，下列推理： 所有的人都是要死的。 蘇格拉底是人。 所以，蘇格拉底是要死的。 這是有效論證。但在命題邏輯中,如果用P,Q,R表示以上三個命題，則上述推理

5、過程為：（P∧Q）?R。借助命題演算的推理理論不能證明其為重言式。（P真Q真R假為成假賦值）,2.1 謂詞的概念與表示(Predicate and Its Expression),【例】設(shè) P 表示命題：張輝是工人。 Q 表示命題：李明是工人。 僅僅從命題符號 P 和 Q 看不出張輝和李明都是工人這一特性?！纠?x=3 ? x+y=z ? f(

6、x)=0 ?,2.1 謂詞的概念與表示(Predicate and Its Expression),第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來。解決辦法：將命題進行分解，分析出個體詞，謂詞和量詞，以期達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系。,2.1 謂詞的概念與表示(

7、Predicate and Its Expression),2.1.1 個體和謂詞 在謂詞邏輯中，可將原子命題劃分為個體和謂詞兩部分。個體：可以獨立存在的具體事物的或抽象的概念。例如，電子計算機、李明、玫瑰花、黑板、實數(shù)、中國、思想、唯物主義等，個體也可稱之為主語。,2.1 謂詞的概念與表示(Predicate and Its Expression),謂詞：用來刻劃個體的性質(zhì)或個體之間的相互關(guān)系的詞。例如在

8、下面命題中： （1）張明是個勞動模范。 （2）李華是個勞動模范。 刻劃客體的性質(zhì) （3）王紅是個大學(xué)生。 （4）小李比小趙高2cm。 （5）點a在b與c之間。 刻劃客體之間的相互關(guān)系 （6）阿杜與阿寺同歲。 （7） x與y具有關(guān)系L。 “是個勞動模范”、“是個大學(xué)生”、“…比…高2cm”、 “… 在…與…之間”、“…

9、與…具有關(guān)系L”都是謂詞。,2.1 謂詞的概念與表示(Predicate and Its Expression),刻劃一個個體性質(zhì)的詞稱之為一元謂詞,刻劃n個個體之間關(guān)系的詞稱之為n元謂詞.一般我們用大寫英文字母表示謂詞，用小寫英文字母表示個體名稱，例如，將上述謂詞分別記作大寫字母F、G、H、R，S，則上述命題可表示為： (1) F(a) a：張明 (2) F(b) b：李華 (3) G

10、(c) c：王紅 (4) H(s,t) s：小李 t：小趙 (5) R(a,b,c) (6) S(a,b) a:阿杜。b:阿寺。稱為命題的謂詞形式。,2.1 謂詞的概念與表示(Predicate and Its Expression),表示具體性質(zhì)或關(guān)系的謂詞稱為謂詞常元；表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變元。 一般的，用F(a)表示個體常元a具

11、有性質(zhì)F(F是謂詞常項或謂詞變項)，用F(x)表示個體變元x具有性質(zhì)F，而用F(a，b)表示個體常元a，b具有關(guān)系F，用F(x,y)表示個體變元x，y具有關(guān)系F。,2.1 謂詞的概念與表示(Predicate and Its Expression),注：(1)單獨一個謂詞并不是命題，在謂詞字母后填上個體所得到的式子稱之為謂詞填式。(2)在謂詞填式中，若個體確定，則A(a1，a2...an)就變成了命題。 (3)在多元謂詞表達式中

12、，個體字母出現(xiàn)的先后次序與事先約定有關(guān)，一般不可以隨意交換位置(如，上例中H(s,t) 與H(t, s)代表兩個不同的命題) 。,2.1 謂詞的概念與表示(Predicate and Its Expression),定義2.1.3:由一個謂詞H和n個個體變元組成的表達式H(x1, x2 , …, xn)稱為n元原子謂詞或n元簡單命題函數(shù)，簡稱n元謂詞。在命題函數(shù)中，個體變元的取值范圍稱為個體域，又稱之為論域。個體域可以是有限事物的集

13、合，也可以是無限事物的集合。全總個體域：宇宙間一切事物組成的個體域稱為全總個體域。,2.1 謂詞的概念與表示(Predicate and Its Expression,有時候?qū)⒉粠€體變項的謂詞稱為0元謂詞，例如，F(xiàn)(a)，G(a,b)，P(a1,a2,…,an)等都是0元謂詞。當(dāng)F，G，P為謂詞常項時，0元謂詞為命題。這樣一來，命題邏輯中的命題均可以表示成0元謂詞，因而可以將命題看成特殊的謂詞。,2.1 謂詞的概念與表示(Pred

14、icate and Its Expression),命題的謂詞形式舉例。例1:若小明的學(xué)習(xí)好，則小明的工作好。 設(shè) S(x):x學(xué)習(xí)好；W(x):x工作好；a:小明。 則有 S(a) ? W(a),,例2:將下列命題用0元謂詞符號化，并討論它們的真值。(1) 2是素數(shù)且是偶數(shù)。(2) 如果2大于3,則2大于4。(3) 如果張明比李民高, 李民比趙亮高,則張明比趙亮高。,2.1 謂詞的概念與表示(Predic

15、ate and Its Expression),解:(1) 設(shè)F(x): x是素數(shù). G(x): x是偶數(shù). 則命題符號化為： F(2)∧G(2) （真） (2) 設(shè)L(x,y) ：x大于y. 則命題符號化為： L(2,3) ? L(2,4) （真） (3) 設(shè) H(x,y): x比y高. a:張明 b:李民 c：趙亮 則命題符號化為： H(a,

16、b)∧H(b ,c)?H(a,c) （真）,,實質(zhì)上，n元謂詞 H(x1, x2 , …, xn) 可以看成以個體域為定義域，以{0,1}為值域的n元函數(shù)或關(guān)系。它不是命題。要想使它成為命題，必須用個體常項a1, a2 , …, an取代x1, x2 , …, xn ，得H(a1, a2 , …, an)是命題。注意:命題函數(shù)中，個體域選擇的不同對命題的真值極有影響。,例：若 R (x) 表示 “a 是大學(xué)生”，

17、如果 x 的討論范圍為某大學(xué)里的所有在校學(xué)生， 則 R(x) 是永真式。若 x 的討論范圍為某中學(xué)里的所有在校學(xué)生， 則 R(x) 是永假式。若 x 的討論范圍為一個劇場中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么，對某些觀眾而言，

18、R(x) 為真，對另一些觀眾而言，R(x) 為假。,例：試將 “所有的人都是要死的” 這一命題符號化。 在此例中，怎么表達“所有的”這一概念呢？顯然，僅僅用目前所討論的知識是不行的，在此引入量詞來刻劃 “所有的” 這一概念。,2.1 謂詞的概念與表示(Predicate and Its Expression),2.1.2 量詞(Quantifiers)量詞：有了個體詞和謂詞之后，有些命題還是不能準(zhǔn)確的符號化，原

19、因是還缺少表示個體常項或變項之間數(shù)量關(guān)系的詞。稱表示個體常項或變項之間數(shù)量關(guān)系的詞為量詞。分為全稱量詞(?)和存在量詞(?),2.1 謂詞的概念與表示(Predicate and Its Expression),1.全稱量詞(The Universal Quantifiers)對日常語言中的“一切”、“所有”、“凡”、“每一個”、“任意”等詞，用符號“?” 表示， ?ｘ表示對個體域里的所有個體， （?ｘ）Ｆ(ｘ)表示個體域里

20、的所有個體具有性質(zhì)F。符號“?”稱為全稱量詞。,2.1 謂詞的概念與表示(Predicate and Its Expression),例3：在謂詞邏輯中將下列命題符號化.（1）凡是人都呼吸。 （2）每個學(xué)生都要參加考試。（3）任何整數(shù)或是正的或是負(fù)的。解: (1) 當(dāng)個體域為人類集合時： 令F(x): x呼吸。則（1）符號化為（?x）F(x) 當(dāng)個體域為全總個體域時： 令M(x): x

21、是人。則（1）符號化為 （?x）(M(x) ?F(x)).,2.1 謂詞的概念與表示(Predicate and Its Expression),(2) 當(dāng)個體域為全體學(xué)生的集合時： 令P(x): x要參加考試。則（2）符號化為 （?x）P(x) 當(dāng)個體域為全總個體域時： 令S(x): x是學(xué)生。則（2

22、）符號化為 （?x）(S(x) ?P(x)).,2.1 謂詞的概念與表示(Predicate and Its Expression),(3) 當(dāng)個體域為全體整數(shù)的集合時： 令P(x): x是正的。N(x): x是負(fù)的。則（3）符號化為 （?x）(P(x)∨N(x)) 當(dāng)個體域為全總個體域時：

23、 令I(lǐng)(x): x是整數(shù)。則（3）符號化為 （?x）(I(x)?(P(x)∨N(x))).,,全稱量詞的一些重要性質(zhì)：設(shè)P是任意的命題，F(xiàn)(x)與A(x,y)均為謂詞，則有：,2.1 謂詞的概念與表示(Predicate and Its Expression),2.存在量詞(The Existential Quantifiers)對日常語言中的“有一個”、“有的”、“存在著”、“

24、至少有一個”、 “存在一些”等詞，用符號“?” 表示， ?ｘ表示存在個體域里的個體， （?ｘ）Ｆ(ｘ)表示存在個體域里的個體具有性質(zhì)F。符號“?”稱為存在量詞.,2.1 謂詞的概念與表示(Predicate and Its Expression),例4：在謂詞邏輯中將下列命題符號化. （1）一些數(shù)是有理數(shù)。 （2）有些人活百歲以上。,2.1 謂詞的概念與表示(Predicate and Its

25、Expression),解: (1)當(dāng)個體域為實數(shù)集合時： 令Q(x): x是有理數(shù)。則（1）符號化為 （ ?ｘ）Q(x) 當(dāng)個體域為全總個體域時： 令P(x): x是數(shù)， Q(x): x是有理數(shù)。 則（1）符號化為 （ ?x） (P(x) ∧ Q(x)),2.1 謂詞的概念與表示(Predicate and Its

26、Expression),（2）當(dāng)個體域為人類集合時： 令G(x): x活百歲以上。則（2）符號化為 （ ?x）G(x) 當(dāng)個體域為全總個體域時： 令M(x): x是人。則（2）符號化為 （?x） (M(x) ∧ G(x)),,存在量詞的一些重要性質(zhì)：設(shè)P是任意的命題，F(xiàn)(x)與A(x,y)均為謂詞，則

27、有：,2.1 謂詞的概念與表示(Predicate and Its Expression),有時需要同時使用多個量詞。例5. 命題“對任意的x,存在y, 使得x+y=5”, 取個體域為實數(shù)集合,則該命題符號化為: （?x） （?y） H (x, y).其中H(x,y): x+y=5. 這是個真命題.,,例6.在個體域限制為(a)和(b)條件時，將下列命題符號化:  

28、;  (1) 對于任意的x，均有x2-3x+2=(x-1)(x-2).   (2) 存在x，使得x+5=3. 其中: (a)個體域D1=N(N為自然數(shù)集合)        (b)個體域D2=R(R為實數(shù)集合),,解： (a)令F(x): x2-3x+2=(x-1)(x-2)，

29、 G(x): x+5=3。 命題(1)的符號化形式為 （? x）F(x)               命題(2)的符號化形式為（? x）G(x)         &#

30、160;   顯然(1)為真命題；而(2)為假命題，因為N不含負(fù)數(shù)。  (b) 在D2內(nèi)，(1)和(2)的符號化形式還是上兩式，(1)依然是真命題，而此時(2)也是真命題。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),3. 使用量詞時應(yīng)注意的問題（1）在不同的個體域，同一命題的符號化形

31、式可能相同也可能不同。（2）在不同的個體域，同一命題的真值可能相同也可能不同。（3）以后如不指定個體域，默認(rèn)為全總個體域。對每個個體變元的變化范圍，用特性謂詞加以限制。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),特性謂詞:限定個體變元變化范圍的謂詞(如例3中的M（x）)。一般而言，對全稱量詞，特性謂詞常作蘊含的前件，如（?x）

32、(M(x) ?F(x))；對存在量詞，特性謂詞常作合取項，如（? x）(M(x)∧ G(x))。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),(4)一般來說，當(dāng)多個量詞同時出現(xiàn)時，它們的順序不能隨意調(diào)換。如：在實數(shù)域上用H(x,y)表示x+y=5,則命題“對于任意的x,都存在y使得x+y=5”可符號化為： （?x）（?y）H(x,y)

33、 ,其真值為1.若調(diào)換量詞順序后為：（?y）（?x）H(x,y) , 其真值為0。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),(5) 當(dāng)個體域為有限集合時,如D={a1, a2 …, an},對任意謂詞A(x),有 (?x) A(x)?A(a1)∧A(a2)∧…∧A(an ) （?x）A(x)?A(a1)∨A(a2)∨…∨A

34、(an ),,例7：在謂詞邏輯中將下列命題符號化.（1）所有的人都長頭發(fā)。（2）有的人吸煙。（3）沒有人登上過木星。（4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。解：令　M(x): x是人。（特性謂詞）（1） 令F(x): x長頭發(fā)。則符號化為：　　?。?x）(M(x) ?F(x)),第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression

35、),（2） 令S(x): x吸煙。則符號化為：　　　 （?x）(M(x)∧S(x))（3） 令D(x): x登上過木星。則符號化為：　　　 ┐(?x)(M(x)∧D(x))（4）令Q(x):x是清華大學(xué)的學(xué)生。H(x):x是高素質(zhì)的。則符號化為： 　 ┐(?x)(Q(x) ?H(x)),,例8. 將下列命題符號化:     (1) 兔子比烏龜跑得快。  &

36、#160;  (2) 有的兔子比所有的烏龜跑得快。     (3) 并不是所有的兔子都比烏龜跑得快。     (4) 不存在跑得同樣快的兩只兔子。,,解: 本題沒有指明個體域，因而采用全總個體域。因為本例中出現(xiàn)二元謂詞，因而引入兩個個體變項x與y。 令F(x):x是兔子，G(y):y是烏龜，H(x,y):x比y跑得快，L(x

37、,y):x與y跑得一樣快。這4個命題分別符號化為         (?x)(?y)(F(x)∧G(y)→H(x,y))           (?x)(F(x)∧(? y)(G(y)→H(x,y)))      &

38、#160; ┐(?x)(?y)(F(x)∧G(y)→H(x,y))           ┐(?x)(?y)(F(x)∧F(y)∧L(x,y)),2.2 謂詞公式與翻譯(Predicate formulae),定義2.2.1 項由下列規(guī)則形成：（1）個體常元和個體變元是項；（2）若f是n元函數(shù)，且t1,t2,…,tn是項，則

39、 f(t1,t2,…,tn)是項；（3）所有項由（1）和（2）生成。定義2.2.2 若P(x1,x2,…,xn)是n元謂詞， t1,t2,…,tn是項，則稱P(t1,t2,…,tn)是Lp中原子謂詞公式，簡稱原子公式。,有了項的定義，函數(shù)的概念就可用來表示個體常元和個體變元。例如，令f(x,y)表示x+y，謂詞N(x)表示x是自然數(shù)，那么f(2,3)表示個體自然數(shù)5，而N(f(2,3))表示5是自然數(shù)。這里函數(shù)是就廣義而言

40、的，例如P(x):x是教授，f(x):x的父親，c:張強，那么P(f(c))便是表示“張強的父親是教授”這一命題。,2.2 謂詞公式與翻譯(Predicate formulae),定義2.2.3謂詞演算的合式公式,可由下述各條組成:（1）原子公式是合式公式。（2）若A 是合式公式，則(┐A)也是合式公式。（3）若A，B是合式公式，則(A ∧ B)，(A ∨ B)， (A ? B)，(A ? B)也是合式公式。

41、（4）若A是合式公式，x是A中出現(xiàn)的任何變元,則(?x)A , (?x)A，也是合式公式。 (5)只有有限次應(yīng)用(1)~(4)得到的公式是合式公式。,2.2 謂詞公式與翻譯(Predicate formulae),合式謂詞公式是按上述規(guī)則由原子公式、聯(lián)結(jié)詞、量詞、圓括號和逗號所組成的符號串，而且命題公式是它的特例。為使用方便，稱合式謂詞公式為謂詞公式，在不引起混淆時，可以將公式中有的括號進行省略。,一般說來，謂詞邏輯的翻譯或符號

42、化的步驟如下： ①正確理解給定命題。必要時把命題改敘，使其中每個原子命題、原子命題之間的關(guān)系能明顯表達出來。,2.2 謂詞公式與翻譯(Predicate formulae),②把每個原子命題分解成個體、謂詞和量詞；在全總論域討論時，要給出特性謂詞。③找出恰當(dāng)量詞。應(yīng)注意全稱量詞(?x)后跟條件式，存在量詞(?x)后跟合取式。④用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來。,2.2 謂詞公式與翻譯(Predicate formulae),2.

43、2 謂詞公式與翻譯(Predicate formulae),例1：在謂詞邏輯中將下列命題符號化.（1）凡正數(shù)都大于零。（2）存在小于2的素數(shù)。（3）沒有不能表示成分?jǐn)?shù)的有理數(shù)。（4）并不是所有參加考試的人都能取得好成績。解：（1） 令F(x): x是正數(shù)。M(x):x大于零。則符號化為：　（?x）(F(x)?M(x)),第二章 謂詞邏輯（Predicate Logic） 2.2 謂詞公式與翻譯(Predicate

44、formulae),（2）令E(x): x小于2。S(x):x是素數(shù)。則符號化為：　　　 （?x)(E(x)∧S(x))　　　真值為0。 （3）令D(x): x是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。則符號化為： (?x)(D(x) ?F(x)) 或 ┐(?x)(D(x)∧ ┐F(x))　　真值為１。 （4）令M(x)：x是人.Q(x):x參加考試。H(x):x取得好成績。則符號化為：

45、 　 ┐(?x)(M(x)∧Q(x)?H(x)) 或 (?x)(M(x)∧Q(x)∧┐H(x)),2.2 謂詞公式與翻譯(Predicate formulae),例2：在謂詞邏輯中將下列命題符號化. （1）所有運動員都欽佩某些教練.（2）有些運動員不欽佩教練.設(shè)：L(x):x是運動員 J(y):y是教練 A(x,y):x欽佩y(1) (?x)(L(x) ?（?y)(J(

46、y)∧A(x,y)))(2)（?x)(L(x) ∧(?y)(J(y)? ┐A(x,y))),例3: 沒有不犯錯誤的人。,設(shè) M(x)：x 是人。 F(x)：x犯錯誤。命題符號化為 ：,此命題等價于“任何人都要犯錯誤”或“所有人都要犯錯誤”。所以此命題也可符號化為：,解：本語句即為“不存在不犯錯誤的人。”,例2.2.2 將命題“沒有最大的自然數(shù)”符號化。解：命題可理解為“對所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”，

47、再具體點，即“對所有的x如果x是自然數(shù)，則一定存在y，y也是自然數(shù)，并且y比x大”。 令N(x):x是自然數(shù)，G(x,y):x大于y，則原命題表示為：(?x) (N(x)?(?y)(N(y)?G(y,x)))。,2.2 謂詞公式與翻譯(Predicate formulae),例4：在謂詞邏輯中將下列命題符號化. （1）那位戴眼鏡的用功的大學(xué)生在看這本大而厚的巨著.（2）對于任意給定的ε>0，必存在著δ>0,使得對任

48、意的x,只要解: (1)設(shè)：S(x):x是大學(xué)生. A(x):x戴眼鏡. B(x):x用功. D(x):x是巨著. F(x,y):x看y. E(y):y是大的. G(y):y是厚的. a:那位 b:這本 則(1)符號化為: A(a)∧B(a)∧S(a)∧D(b)∧E(b)∧G(b)∧F(a,b),第二章 謂詞邏輯（Predicate Logic） 2.2 謂詞公式與翻譯(Predicate form

49、ulae),（2）符號化為: (?ε)((ε>0)?(?δ) ((δ>0)∧(?x) (( <δ)? ( <ε)))),例4: 盡管有人聰明，但未必一切人都聰明。,解: 設(shè) M(x)：x是人。 P(x)：x是聰明的。命題符號化為：,由于人們對命題的文字?jǐn)⑹龊饫斫獾牟煌?，強調(diào)的重點不同，會影響到命題符號化的形式不同。見例題5。,例5:

50、這只大紅書柜擺滿了那些古書。,解法1 這只大紅書柜擺滿了那些古書。,x,y,設(shè) F(x,y)：x擺滿了y,再對x和y加以限制,R(x)：x是大紅書柜,Q(y)：y是古書,a：這只 b：哪些,此時可把命題符號化為：,解法2,設(shè) A(x)：x是書柜,B(x)：x是大的,C(x)：x是紅的,D(y)：y是古老的,E(y)：y是圖書,F(x,y)：x擺滿了y,a ：這只 b：那些,此時可把命題符號化為：,解法1中R(x)表示x

51、是大紅書柜,解法2中A(x) ∧B(x) ∧C(x)也可表示大紅書柜,但用A(x) ∧B(x) ∧C(x)將更方便于對書柜的大小顏色進行討論,對個體刻劃深度的不同就可翻譯成不同的謂詞公式.,2.3 變元的約束(Bound of variable),2.3 變元的約束(Bound of variable)2.3.1 變元的約束2.3.2 約束變元的換名與自由變元的代入,2.3 變元的約束(Bound of variable),2.3.

52、1變元的約束 (Bound of variable)定義2.3.1:在謂詞公式中，形如(?x)P(x)和(?x)P(x)的部分，稱為謂詞公式的x約束部分。 (?x)P(x)或(?x)P(x)中的x叫做量詞的指導(dǎo)變元或作用變元，P(x)稱為相應(yīng)量詞的作用域或轄域。,2.3 變元的約束(Bound of variable),在?x和?x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，相應(yīng)的x稱為約束變元; P(x)中除約束變元以外出現(xiàn)的變元稱為

53、是自由變元。,,,量詞,指導(dǎo)變元,轄域,約束變元,自由變元,,,通常，一個量詞的轄域是公式的子公式。因此，確定一個量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講： （1）若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域； （2）若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域。 判定給定公式中個體變元是約束變元還是自由變元，關(guān)鍵是要看它在公式中是約束出現(xiàn)，還是自由出現(xiàn)。,例1. 指出下列各公式中的指導(dǎo)變元，各量

54、詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個體變元:    (1)( x)(F(x,y)→G(x,z))                      (2)( x)(F(x)→G(y))→( y)(

55、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)公式中含有兩個量詞，前件上的量詞? 的指導(dǎo)變元為x， 轄域A=(F(x)→G(y))，其中x是約束出現(xiàn)的，y是自由出現(xiàn)的。后件中的量詞?的指導(dǎo)變元為y， 轄域為(H(x)∧L(x,y,z))，其中y是約束出現(xiàn)的，x，z均為自由出現(xiàn)的

56、。在整個公式中，x約束出現(xiàn)一次，自由出現(xiàn)2次，y自由出現(xiàn)一次，約束出現(xiàn)一次，z只自由出現(xiàn)一次。,,2.3 變元的約束(Bound of variable),說明:(1)n元謂詞公式A(x1，x2...xn) 中有n個自由變元,若對其中的k(k≤n)個進行約束,則構(gòu)成了n-k元謂詞;如果一個公式中沒有自由變元出現(xiàn)，則該公式就變成了一個命題。(2)一個公式的約束變元所使用的名稱符號是無關(guān)緊要的，如(?x)M(x)與(?y)M(y)意義相

57、同。,定義2.3.2 設(shè)A為任意一個公式，若A中無自由出現(xiàn)的個體變元，則稱A為封閉的合式公式，簡稱閉式。由閉式定義可知，閉式中所有個體變元均為約束出現(xiàn)。例如，(?x)(P(x)?Q(x))和(?x)(?y)(P(x)?Q(x,y))是閉式，而(?x)(P(x)?Q(x,y))和(?y)(?z)L(x,y,z)不是閉式。,2.3 變元的約束(Bound of variable),2.3.2 約束變元的換名與自由變元的代入規(guī)則 一

58、個變元可能在同一個公式中既是自由出現(xiàn)又是約束出現(xiàn), 這樣在理解上容易發(fā)生混淆。為了避免這種混亂，可采取下面兩個規(guī)則。（1）換名規(guī)則: (對約束變元而言） 對約束變元進行換名，使得一個變元在一個公式中只呈一種形式出現(xiàn)。,第二章 謂詞邏輯（Predicate Logic） 2.3 變元的約束(Bound of variable),例1: (?x)( P(x)?R(x,y))∧ L(x,y)換名為(?t)( P(t)?R(t,

59、y))∧ L(x,y)(?x)( H(x,y)?(?y)(W(y) ∧ L(x,y,z)))換名為(?x)( H(x,y)?(?s)(W(s) ∧ L(x,s,z))),第二章 謂詞邏輯（Predicate Logic） 2.3 變元的約束(Bound of variable),換名原則：(1)約束變元可以換名,其更改的變元名稱范圍是量詞中的指導(dǎo)變元以及該量詞作用域中所出現(xiàn)的該變元，公式的其余部分不變。(2)換名時一定要更

60、改為作用域中沒有出現(xiàn)的變元名稱。,2.3 變元的約束(Bound of variable),（2）代入規(guī)則（對自由變元而言）對公式中自由變元的更改稱為代入。例如，對例1中的公式(?x)( P(x)?R(x,y))∧ L(x,y) 自由變元y用z來代入,得 (?x)( P(x)?R(x,z))∧ L(x,z),2.3 變元的約束(Bound of variable),代入原則：(1)對于謂詞公式中的自

61、由變元可以作代入,代入時需要對公式中出現(xiàn)該自由變元的每一處進行;(2)用以代入的變元與原公式中所有變元的名稱不能相同。,改名規(guī)則與代入規(guī)則的共同點都是不能改變約束關(guān)系，而不同點是：① 施行的對象不同。改名是對約束變元施行，代入是對自由變元施行。② 施行的范圍不同。改名可以只對公式中一個量詞及其轄域內(nèi)施行，即只對公式的一個子公式施行；而代入必須對整個公式同一個自由變元的所有自由出現(xiàn)同時施行，即必須對整個公式施行。,③ 施行后的結(jié)果不

62、同。改名后，公式含義不變，因為約束變元只改名為另一個個體變元，約束關(guān)系不改變，約束變元不能改名為個體常元。代入，不僅可用另一個個體變元進行代入，并且也可用個體常元去代入，從而使公式由具有普遍意義變?yōu)閮H對該個體常元有意義，即公式的含義改變了。,2.4 公式解釋與類型,1．公式解釋 一般情況下，Lp中的公式含有：個體常元、個體變元（約束變元或自由變元）、函數(shù)變元、謂詞變元等，對各種變元用指定的特殊常元去代替，就構(gòu)成了一個公式的解釋。當(dāng)

63、然在給定的解釋下，也可以對多個公式進行翻譯。,,例：將下列兩個公式中的變項指定成常項使其成為命題: (1) (?x) (F(x)→G(x))                         

64、;        (2) (?x) (?y) (F(x)∧F(y)∧G(x,y) →H(f(x,y),g(x,y))),,解: (1)指定個體變項的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法:   (a)令個體域D1為全總個體域，F(xiàn)(x)為x是人，G(x)為x是黃種人，則(1)表達的命題為“所有人都

65、是黃種人”，這是假命題。 (b)令個體域D2為實數(shù)集合R，F(xiàn)(x)為x是自然數(shù)，G(x)為x是整數(shù)，則(1)表達的命題為“自然數(shù)都是整數(shù)”，這是真命題。 我們還可以給出其他各種不同指定，使(1)表達各種不同形式的命題。,,(2)這里含有兩個2元函數(shù)變項，兩個1元謂詞變項，兩個2元謂詞變項。指定個體域為全總個體域，F(xiàn)(x)為x是實數(shù)，G(x,y)為x≠y，H(x,y)為x>y，f(x,y)=x2+y2，g(x,y)=2xy，則

66、(2)表達的命題為“對于任意的x，y，若x與y都是實數(shù)，且x≠y，則x2+y2 >2xy”，這是真命題。如果H(x,y)改為x<y，則所得命題就為假命題了。,,在上例中所談的對各種變項的指定也可以稱為對它們的解釋。在本例中是給出公式后再對它們進行解釋，也可以先給出解釋，再用這個解釋去研究各種公式。由以上的討論不難看出，一個解釋不外乎指定個體域、個體域中一些特定的元素、特定的函數(shù)和謂詞等部分。,,定義2.4.1 謂詞邏輯中公

67、式的每一個解釋I 由下面四部分組成：① 非空個體域DI。② DI中一些特定元素的集合 ③ DI上特定函數(shù)集合 ④ DI上特定謂詞的集合,對解釋I 的幾點說明:     1. 在解釋的定義中引進了幾個元語言符號，如 。    2. 被解釋的公式A中的個體變項均取值于DI。    

68、3. 若A中含有個體常項ai，就解釋成 。,4. 為第i個n元函數(shù)。例如，i=1，n=2時， 表示第一個二元函數(shù)，它出現(xiàn)在解釋中，可能是 等，一旦公式中出現(xiàn)f1(x,y)就解釋成 ， 出現(xiàn)g1(x,y)就解釋成 。5. 為第i個n元謂詞，如i=2，n=3時， 表示第2個3元謂詞，

69、它可能以 的形式出現(xiàn)在解釋中，公式A若出現(xiàn)F2(x,y,z)就解釋成 。 6. 被解釋的公式不一定全部包含解釋中的四部分。,,,,例1:給定解釋 I 如下： (a) 個體域 D=R (b) (c) (d) 寫出下列公式在I下的解釋, 并指出它的真值。 (1) ?xF(f(x,a),g(x,a)),?x(x+0=x?0)

70、真,(2) ?x?y(F(f(x,y),g(x,y))?F(x,y)),?x?y(x+y=x?y?x=y) 假,(3) ?xF(g(x,y),a),?x(x?y=0) 真值不定, 不是命題,,例2： 給定解釋 I 如下: (a) 個體域D=N (b) =2 (c) (d) 說明下列公式在 I 下的涵義,并討論真值。 (1) F(

71、f(x,y),g(x,y)) x+y=x·y， 不是命題    (2) F(f(x,a),y)→F(g(x,y),z) (x+2=y)→(x·y=z)，  不是命題    (3)┐F(g(x,y),g(y，z)) （x·y≠y·z） ，不是命題,(4) ?x ?y ?z

72、 F (f (x,y), z),,(6) ?x F (f (x,x),g (x,x)),(5) ?x ?y ?z F (f (y,z), x),?x ?y ?z (y+z=x) 假,?x ?y ?z (x+y=z) 真,?x(x+x=x?x) 真,(4), (5)說明?與?不能隨意交換,(7) ?x ?y (F (f (x,a),y)?F (f (y,a),x)),?x ?y (x+