離散數(shù)學(xué)第2講

1、第二講 一階/謂詞邏輯,在Ls中，把命題分解到原子命題為止，認(rèn)為原子命題是不能再分解的，僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。這樣，有些推理用命題邏輯就難以確切地表示出來。例如，著名的亞里士多德三段論蘇格拉底推理：,退出,所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。根據(jù)常識，認(rèn)為這個推理是正確的。但是，若用Ls來表示，設(shè)P、Q和R分別表示這三個原子命題，則有P，Q?R,然而，(P∧Q)→R

2、并不是永真式，故上述推理形式又是錯誤的。一個推理，得出矛盾的結(jié)論，問題在哪里呢? 問題就在于這類推理中，各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間，即體現(xiàn)在命題結(jié)構(gòu)的更深層次上。對此，Ls是無能為力的。所以，在研究某些推理時，有必要對原子命題作進(jìn)一步分析，分析出其中的個體詞，謂詞和量詞，研究它們的形式結(jié)構(gòu)的邏輯關(guān)系、正確的推理形式和規(guī)則，這些正是謂詞邏輯（簡稱為Lp）的基本內(nèi)容。,2.1 個體、謂

3、詞和量詞2.2 謂詞公式與翻譯2.3 約束變元與自由變元2.4 公式解釋與類型2.5 等價式與蘊涵式2.6 謂詞公式范式2.7 謂詞邏輯的推理理論,2.1 個體、謂詞和量詞,張三喜歡唱歌李四喜歡唱歌所有人都喜歡唱歌有人喜歡唱歌,2.1 個體、謂詞和量詞,在Lp中，命題是具有真假意義的陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。在Lp中，為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按照這兩

4、部分對命題進(jìn)行分析，并且把主語稱為個體或客體，把謂語稱為謂詞。,１.個體、謂詞和命題的謂詞形式定義2.1.1 在原子命題中，所描述的對象稱為個體；用以描述個體的性質(zhì)或個體間關(guān)系的部分，稱為謂詞。個體，是指可以獨立存在的事物，它可以是具體的，也可以是抽象的，如張明，計算機，精神等。表示特定的個體，稱為個體常元，以a，b，c…或帶下標(biāo)的ai，bi，ci…表示；表示不確定的個體，稱為個體變元，以x，y，z…或xi，yi，zi…表示。,謂

5、詞，當(dāng)與一個個體相聯(lián)系時，它刻劃了個體性質(zhì)；當(dāng)與兩個或兩個以上個體相聯(lián)系時，它刻劃了個體之間的關(guān)系。表示特定謂詞，稱為謂詞常元，表示不確定的謂詞，稱為謂詞變元，都用大寫英文字母，如P，Q，R，…，或其帶上、下標(biāo)來表示。,例：命題“張明是位大學(xué)生”“張明”是個體，“是位大學(xué)生”是謂詞設(shè)S：是位大學(xué)生，c：張明，則S(c)：張明是位大學(xué)生。如，命題“武漢位于北京和廣州之間” 武漢、北京和廣州是三個個體，而“…位于…和…之間”是謂

6、詞，它刻劃了武漢、北京和廣州之間的關(guān)系。設(shè)P：…位于…和…之間，a：武漢，b：北京，c：廣州，則P(a，b，c)：武漢位于北京和廣州之間。,定義2.1.2 一個原子命題用一個謂詞(如P)和n個有次序的個體常元(如a1，a2，…，an)表示成P(a1，a2，…，an)，稱它為該原子命題的謂詞形式或命題的謂詞形式。應(yīng)注意的是，命題的謂詞形式中的個體出現(xiàn)的次序影響命題的真值，不是隨意變動，否則真值會有變化。如上述例子中，P(b,a,c

7、)是假。,２.原子謂詞公式原子命題的謂詞形式還可以進(jìn)一步加以抽象，比如在謂詞右側(cè)的圓括號內(nèi)的n個個體常元被替換成個體變元，如x1,x2,···,xn，這樣便得了一種關(guān)于命題結(jié)構(gòu)的新表達(dá)形式，稱之為n元原子謂詞。定義2.1.3 由一個謂詞(如P)和n個體變元(如x1，x2，…，xn)組成的P(x1，x2，…，xn)，稱它為n元原子謂詞或n元命題函數(shù)，簡稱n元謂詞。而個體變元的論述范圍，稱為個體域或論域。

8、,當(dāng)n=1時，稱一元謂詞；當(dāng)n=2時，稱為二元謂詞，…。特別地，當(dāng)n=0，稱為零元謂詞。零元謂詞是命題，這樣命題與謂詞就得到了統(tǒng)一。,n元謂詞不是命題，只有其中的個體變元用特定個體或個體常元替代時，才能成為一個命題。但個體變元在哪些論域取特定的值，對命題的真值極有影響。例如，令S(x)：x是大學(xué)生。若x的論域為某大學(xué)的計算機系中的全體同學(xué)，則S(x)是真的；若x的論域是某中學(xué)的全體學(xué)生，則S(x)是假的；若x的論域是某劇場中的觀

9、眾，且觀眾中有大學(xué)生也有非大學(xué)生的其它觀眾，則S(x)是真值是不確定的。,通常，把一個n元謂詞中的每個個體的論域綜合在一起作為它的論域，稱為n元謂詞的全總論域。定義了全總論域，為深入研究命題提供了方便。當(dāng)一個命題沒有指明論域時，一般都從全總論域作為其論域。而這時又常常要采用一個謂詞如P(x)來限制個體變元x的取值范圍，并把P(x)稱為特性謂詞。,３.量詞利用n元謂詞和它的論域概念，有時還是不能用符號來很準(zhǔn)確地表達(dá)某些命題，例如S(x)

10、表示x是大學(xué)生，而x的個體域為某單位的職工，那么S(x)可表示某單位職工都是大學(xué)生，也可表示某單位有一些職工是大學(xué)生，為了避免理解上的歧義，在Lp中，需要引入用以刻劃“所有的”、“存在一些”等表示不同數(shù)量的詞，即量詞，其定義如下：,定義2.1.4 ①符號?稱為全稱量詞符，用來表達(dá)“對所有的”、“每一個”、“對任何一個”、“一切”等詞語；?x稱為全稱量詞，稱x為指導(dǎo)變元。②符號?稱為存在量詞符，用來表達(dá)“存在一些”、“至少有一個”、“

11、對于一些”、“某個”等詞語；?x稱為存在量詞，x稱為指導(dǎo)變元。,*③符號?!稱為存在唯一量詞符，用來表達(dá)“恰有一個”、“存在唯一”等詞語；?!x稱為存在唯一量詞，稱x為指導(dǎo)變元。全稱量詞、存在量詞、存在唯一量詞統(tǒng)稱量詞。量詞記號是由邏輯學(xué)家Fray引入的，有了量詞之后，用邏輯符號表示命題的能力大大加強了。,例 試用量詞、謂詞表示下列命題：① 所有大學(xué)生都熱愛祖國；② 每個自然數(shù)都是實數(shù)；③ 一些大學(xué)生有遠(yuǎn)大理想；④ 有的

12、自然數(shù)是素數(shù)。,解 令S(x)：x是大學(xué)生，L(x)：x熱愛祖國，N(x)：x是自然數(shù)，R(x)：x是實數(shù)，I(x)：x有遠(yuǎn)大理想，P(x)：x是素數(shù)。則例中各命題分別表示為：①(?x)(S(x)?L(x)) ②(?x)(N(x)?R(x))③(?x)(S(x)?I(x)) ④(?x)(N(x)?P(x)),在該例的解答中，由于命題中沒有指明個體域，這便意味著各命題是在全總論域中討論，因而都使用了特

13、性謂詞，如S(x)、N(x)。而且還可以看出，量詞與特性謂詞的搭配還有一定規(guī)律，即全稱量詞后跟一個條件式，而特性謂詞作為其前件出現(xiàn)；存在量詞后跟一個合取式，特性謂詞作為一個合取項出現(xiàn)。,如果在解答時，指明了個體域，便不用特性謂詞，例如在①、③中令個體域為全體大學(xué)生，②和④中的個體域為全部自然數(shù)，則可符號化為：①(?x)L(x) ②(?x)R(x)③(?x)I(x) ④(?x)P(x),謂詞前加上了量詞，稱

14、為謂詞的量化。若一個謂詞中所有個體變元都量化了，則該謂詞就變成了命題。這是因為在謂詞被量化后，可以在整個個體域中考慮命題的真值了。,量詞(舉例)設(shè)：F(x)：x是自然數(shù)。G(x)：x是偶數(shù)。H(x) ： x是奇數(shù)。I(x,y)：x=y?！坝行┳匀粩?shù)是偶數(shù)”。?x(F(x)∧G(x))“既有奇數(shù)又有偶數(shù)” 。?xH(x)∧?yG(y)“存在既奇又偶的數(shù)” 。?x(H(x)∧G(x))“存在唯一的自然數(shù)0”。?!x(F(x)∧

15、I(x,0)),個體變項(varible)表示不確定的泛指對象用小寫英文字母x,y,z,…來表示例如： F(x): x是人。G(x): x是數(shù)?！按嬖谥恕? ?xF(x)“僅有一人”: ?!xF(x)“萬物皆數(shù)”: ?xG(x),個體常項(constant)表示具體的特定對象用小寫英文字母a,b,c,…來表示例如： a:王大明，b:王小明， G(x,y): x與y是兄弟,“王大明與王小明是兄弟”: G(a,b

16、),例1 用0元謂詞將命題符號化 要求：先將它們在命題邏輯中符號化，再在謂詞 邏輯中符號化 (1) 墨西哥位于南美洲 在命題邏輯中, 設(shè) p: 墨西哥位于南美洲 符號化為 p, 這是真命題 在一階邏輯中, 設(shè)a：墨西哥，F(xiàn)(x)：x位于南美洲 符號化為F(a),例1(續(xù)),,(2)   是無理數(shù)僅當(dāng) 是有理數(shù) 在命題邏輯中, 設(shè) p： 是無

17、理數(shù)，q： 是有理數(shù). 符號化為 p ? q, 這是假命題 在一階邏輯中, 設(shè)F(x): x是無理數(shù), G(x): x是有理 數(shù)符號化為 (3) 如果2>3，則33，q：3y，G(x,y)：x<y, 符號化為 F(2,3)?G(3,4),例2 在一階邏輯中將下面命題符號化 (1) 人都愛美; (2) 有人用左手寫字 分別取(a) D為人類集

18、合, (b) D為全總個體域 .解：(a) (1) 設(shè)G(x)：x愛美, 符號化為 ?x G(x) (2) 設(shè)G(x)：x用左手寫字, 符號化為 ?x G(x) (b) 設(shè)F(x)：x為人，G(x)：同(a)中 (1) ?x (F(x)?G(x)) (2) ? x (F(x)?G(x))這是兩個基本公式, 注意這兩個基本公式的使用.

19、,例3 在一階邏輯中將下面命題符號化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無理數(shù)大于有的有理數(shù)解 注意: 題目中沒給個體域, 一律用全總個體域  (1) 令F(x): x為正數(shù), G(y): y為負(fù)數(shù), L(x,y): x>y ?x(F(x)??y(G(y)?L(x,y))) 或 ?x?y(F(x)?G(y)?L(x,y)) 兩

20、者等值 (2) 令F(x): x是無理數(shù), G(y): y是有理數(shù), L(x,y)：x>y ?x(F(x)??y(G(y)?L(x,y))) 或 ?x?y(F(x)?G(y)?L(x,y)) 兩者等值,幾點注意： 1元謂詞與多元謂詞的區(qū)分無特別要求 用全總個體域量詞順序一般不要隨便顛倒 否定式的使用思考： ①

21、沒有不呼吸的人 ② 不是所有的人都喜歡吃糖 ③ 不是所有的火車都比所有的汽車快以上命題應(yīng)如何符號化？,2.2 謂詞公式與翻譯,１.謂詞公式為了方便處理數(shù)學(xué)和計算機科學(xué)的邏輯問題及謂詞表示的直覺清晰性，將引進(jìn)項的概念。定義2.2.1 項由下列規(guī)則形成：① 個體常元和個體變元是項；② 若f是n元函數(shù)，且t1，t2，…，tn是項，則f(t1，t2，…，tn)是項；③ 所有項都由①和②生成。,有了項的定義，函數(shù)的概念就可

22、用來表示個體常元和個體變元。例如，令f(x,y)表示x+y，謂詞N(x)表示x是自然數(shù)，那么f(2,3)表示個體自然數(shù)5，而N(f(2,3))表示5是自然數(shù)。這里函數(shù)是就廣義而言的。例如P(x):x是教授，f(x):x的父親，c:張強，那么P(f(c))便是表示“張強的父親是教授”這一命題。,函數(shù)的使用給謂詞表示帶來很大方便。例如，用謂詞表示命題：“對任意整數(shù)x，x2-1=(x+1)(x-1)是恒等式”。解：令I(lǐng)(x):x是整

23、數(shù)，f(x)=x2-1，g(x)=(x+1)(x-1)，E(x,y):x=y，則該命題可表示成：(?x)(I(x)?E(f(x),g(x)))。,定義2.2.2 若P(x1，x2，…，xn)是n元謂詞，t1，t2，…，tn是項，則稱P(t1，t2，…，tn)為Ls中原子謂詞公式，簡稱原子公式。下面，由原子公式出發(fā)，給出Lp中的合式謂詞公式的歸納定義。,定義2.2.3 合式謂詞公式當(dāng)且僅當(dāng)由下列規(guī)則形成的符號串① 原子公式是合式謂

24、詞公式；② 若A是合式謂詞公式，則(?A)是合式謂詞公式；③ 若A，B是合式謂詞公式，則(A∧B)，(A∨B)，(A→B)和(A?B)都是合式謂詞公式；④ 若A是合式謂詞公式，x是個體變元，則(?x)A、(?x)A都是合式謂詞公式；⑤ 僅有有限項次使用①、②、③和④形成的才是合式謂詞公式。,２.謂詞邏輯的翻譯把一個文字?jǐn)⑹龅拿}，用謂詞公式表示出來，稱為謂詞邏輯的翻譯或符號化；反之亦然。一般說來，符號化的步驟如下：①正確理解

25、給定命題。必要時把命題改敘（換句話說），使其中每個原子命題、原子命題之間的關(guān)系能明顯表達(dá)出來。,②把每個原子命題分解成個體、謂詞和量詞；在全總論域討論時，要給出特性謂詞。③找出恰當(dāng)量詞。應(yīng)注意全稱量詞(?x)后跟條件式，存在量詞(?x)后跟合取式。④用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來。兩種模式:?x(M(x)→G(x)) ?x(M(x)∧G(x)),命題符號化(舉例)例: “有些人是要死的”.解1:

26、采用全總個體域.設(shè): F(x): x是人; G(x):x是要死的.原命題符號化成: ?x(F(x)∧G(x))解2: 采用全體人作為個體域.設(shè): G(x): x是要死的.原命題符號化成: ?xG(x),命題符號化(舉例、續(xù))例: “凡人都是要死的”.解1: 采用全總個體域.設(shè): F(x): x是人; G(x):x是要死的.原命題符號化成: ?x(F(x)→G(x))解2: 采用全體人作為個體域.設(shè): G(x):

27、 x是要死的.原命題符號化成: ?xG(x),命題符號化(舉例、續(xù))例: “存在最小的自然數(shù)”。解1: 設(shè): F(x): x是自然數(shù); G(x,y): x≤y;原命題符號化成:?x(F(x)∧?y(F(y)→G(x,y)))解2: 采用全體自然數(shù)作為個體域.設(shè): G(x,y): x<y;原命題符號化成: ?x?yG(x,y)注意量詞順序:?y?xG(x,y): “沒有最小的自然數(shù)”.,例 將命題“沒有最大

28、的自然數(shù)”符號化。解： 命題中“沒有最大的”顯然是對所有的自然數(shù)而言，所以可理解為“對所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”；再具體點，即“對所有的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)))。,例 將命題“沒有最大的自然數(shù)”符號化。解：令N(x): x是自然數(shù)，G(

29、x,y): x大于y，則原命題表示為：(?x)(N(x)?(?y)(N(y)?G(y,x)))。提問:給定論域為全體自然數(shù),符號化的結(jié)果?,例 將語句“今天有雨雪，有些人會跌跤”符號化。解： 本語句可理解為“若今天下雨又下雪，則存在x，x是人且x會跌跤”。令R: 今天下雨，S: 今天下雪，M(x): x是人，F(xiàn)(x): x會跌跤，則本語句可表示為：R?S?(?x)(M(x)?F(x))。由于人們對命題的文字?jǐn)⑹龊饫斫獾?/p>

30、不同，強調(diào)的重點不同，會影響到命題符號化的形式不同。,命題符號化(舉例、續(xù))例: “火車比汽車快”。解: 設(shè): F(x): x是火車; G(x): x是汽車; H(x,y): x比y快原命題符號化成: ?x(F(x)→?y(G(y)→H(x,y)))或: ?x?y((F(x)∧G(y))→H(x,y)),命題符號化(舉例、續(xù))例: “有的汽車比火車快”。解: 設(shè): F(x): x是汽車; G(

31、x): x是火車; H(x,y): x比y快原命題符號化成: ?x(F(x)∧?y(G(y)∧H(x,y)))或: ?x?y(F(x)∧G(y)∧H(x,y)),命題符號化(舉例、續(xù))例: “有些病人相信所有的醫(yī)生”。解: 設(shè): F(x): x是病人; G(x): x是醫(yī)生; H(x,y): x相信y原命題符號化成: ?x(F(x)∧?y(G(y)→H(x,y)

32、)),例1 用0元謂詞將命題符號化 要求：先將它們在命題邏輯中符號化，再在謂詞 邏輯中符號化 (1) 墨西哥位于南美洲 在命題邏輯中, 設(shè) p: 墨西哥位于南美洲 符號化為 p, 這是真命題 在一階邏輯中, 設(shè)a：墨西哥，F(xiàn)(x)：x位于南美洲 符號化為F(a),例1(續(xù)),,(2)   是無理數(shù)僅當(dāng) 是有理數(shù) 在命題邏輯中, 設(shè) p： 是

33、無理數(shù)，q： 是有理數(shù). 符號化為 p ? q, 這是假命題 在一階邏輯中, 設(shè)F(x): x是無理數(shù), G(x): x是有理 數(shù)符號化為 (3) 如果2>3，則33，q：3y，G(x,y)：x<y, 符號化為 F(2,3)?G(3,4),例2 在一階邏輯中將下面命題符號化 (1) 人都愛美; (2) 有人用左手寫字 分別取(a) D為人類

34、集合, (b) D為全總個體域 .解：(a) (1) 設(shè)G(x)：x愛美, 符號化為 ?x G(x) (2) 設(shè)G(x)：x用左手寫字, 符號化為 ?x G(x) (b) 設(shè)F(x)：x為人，G(x)：同(a)中 (1) ?x (F(x)?G(x)) (2) ? x (F(x)?G(x))這是兩個基本公式, 注意這兩個基本公式的使用

35、.,例3 在一階邏輯中將下面命題符號化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無理數(shù)大于有的有理數(shù)解 注意: 題目中沒給個體域, 一律用全總個體域  (1) 令F(x): x為正數(shù), G(y): y為負(fù)數(shù), L(x,y): x>y ?x(F(x)??y(G(y)?L(x,y))) 或 ?x?y(F(x)?G(y)?L(x,y))

36、兩者等值 (2) 令F(x): x是無理數(shù), G(y): y是有理數(shù), L(x,y)：x>y ?x(F(x)??y(G(y)?L(x,y))) 或 ?x?y(F(x)?G(y)?L(x,y)) 兩者等值,2.3 約束變元與自由變元,定義2.3.1 給定一個謂詞公式A，其中有一部分公式形如(?x)B(x)或(?x)B(x)，則稱

37、它為A的x約束部分，稱B(x)為相應(yīng)量詞的作用域或轄域。在轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變元；B中不是約束出現(xiàn)的其它個體變元的出現(xiàn)稱為自由出現(xiàn)，這些個體變元稱自由變元。,對于給定的謂詞公式，能夠準(zhǔn)確地判定它的轄域、約束變元和自由變元是很重要的。通常，一個量詞的轄域是某公式A的一部分，稱為A的子公式。因此，確定一個量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講：,①若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄

38、域；②若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域。判定給定公式A中個體變元是約束變元還是自由變元，關(guān)鍵是要看它在A中是約束出現(xiàn)，還是自由出現(xiàn)。,,在公式 ?x(F(x,y)?G(x,z)) 中, A=(F(x,y)?G(x,z))為?x的轄域， x為指導(dǎo)變元, A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn). ?x(F(x)∧?y(G(y)→H(x,y)))?x

39、F(x)∧?y(G(y)→H(x,y)),今后常用元語言符號A(x)表示x是其中的一個個體變元自由出現(xiàn)的任意公式，如A(x)可為P(x)?Q(x)，P(x)?(?y)Q(x,y)等。一旦在A(x)前加上量詞(?x)或(?x)，即得公式(?x)A(x),或(?x)A(x)。這時，x即是約束出現(xiàn)了。類似地，用A(x,y)表示x和y是自由出現(xiàn)的公式。,定義2.3.2 設(shè)A為任意一個公式，若A中無自由出現(xiàn)的個體變元，則稱A為封閉的合式公式，簡

40、稱閉式。由閉式定義可知，閉式中所有個體變元均為約束出現(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)不是閉式。,從下面討論可以看出，在一公式中，有的個體變元既可以是約束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，采用下面兩個規(guī)則：①約束變元換名規(guī)則，將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成本轄

41、域中未曾出現(xiàn)過的個體變元，其余不變。②自由變元代替規(guī)則，對某自由出現(xiàn)的個體變元可用個體常元或與原子公式中所有個體變元不同的個體變元去代替，且處處代替。,例： ?x ?y ( R(x,y) ? L(y,z) ) ??xH(x,y)換名和代替為： ?x ?y ( R(x,y) ? L(y,z) ) ??tH(t,w),換名規(guī)則與代替規(guī)則的共同點都是不能改變約束關(guān)系，而不同點是：① 施行的對象不同。換名是對約束變元施行，代替是對自由變元

42、施行。② 施行的范圍不同。換名可以只對公式中一個量詞及其轄域內(nèi)施行，即只對公式的一個子公式施行；而代替必須對整個公式同一個自由變元的所有自由出現(xiàn)同時施行，即必須對整個公式施行。,③ 施行后的結(jié)果不同。換名后，公式含義不變，因為約束變元只改名為另一個個體變元，約束關(guān)系不改變。約束變元不能改名為個體常元；代替，不僅可用另一個個體變元進(jìn)行代替，并且也可用個體常元去代替，從而使公式由具有普遍意義變?yōu)閮H對該個體常元有意義，即公式的含義改變了。,

43、2.4 公式解釋與類型,1．公式解釋一般情況下，Lp中的公式含有：個體常元、個體變元（約束變元或自由變元）、函數(shù)變元、為謂詞變元等，對各種變元用指定的特殊常元去代替，就構(gòu)成了一個公式的解釋。當(dāng)然在給定的解釋下，可以對多個公式進(jìn)行解釋。下面給出解釋的一般定義。,定義2.4.1 一個解釋I由下面4部分組成：① 非空個體域DI。② DI中部分特定元素a’，b’，…。③ DI上的特定一些函數(shù)f’，g’，…。④ DI上特定謂詞：P’

44、，Q’，…。在一個具體解釋中，個體常元、函數(shù)符號、謂詞符號的數(shù)量一般是有限的，并且其解釋一旦確定下來就不再改變，只是個體變元的值在個體域DI內(nèi)變化，量詞符?或?僅作用于DI中的元素。,設(shè)個體域為有限集D={a1, a2,…, an}, 則 ?xA(x)?A(a1)∧A(a2)∧…∧A(an) ?xA(x)?A(a1)∨A(a2)∨…∨A(an)例: 個體域D={a,b,c}, 則?x?yF(x,y)??x (F(

45、x,a)∧F(x,b)∧F(x,c))? (F(a,a)∧F(a,b)∧F(a,c))∨ (F(b,a)∧F(b,b)∧F(b,c))∨ (F(c,a)∧F(c,b)∧F(c,c)),,例1 給定解釋I 如下: (a) 個體域 D=N (b) (c) (d) 謂詞說明下列公式在 I 下的涵義,并討論真值 (1) ?xF(g(x,a),x),?x(

46、2x=x) 假命題,(2) ?x?y(F(f(x,a),y)?F(f(y,a),x)),?x?y(x+2=y?y+2=x) 假命題,例1(續(xù)),(3) ?x?y?zF(f(x,y),z),兩點說明:5個小題都是閉式,在I下全是命題(3)與(5)說明，量詞順序不能隨意改變,(5) ?x?y?zF(f(y,z),x),?x?y?z (y+z=x) 假命題,(4) ?xF(f(x,x),g(x,x

47、)),?x(2x=x2) 真命題,?x?y?z (x+y=z) 真命題,2．公式類型定義2.4.2 ① 若一公式在任何解釋下都是真的，稱該公式為邏輯有效的，或永真的。② 若一公式在任何解釋下都是假的，稱該公式為矛盾式，或永假式。③ 若一公式至少存在一個解釋使其為真，稱該公式為可滿足式。,從定義可知，邏輯有效式為可滿足式，反之未必成立。與命題公式中分類一樣，謂詞公式也分為三種類型，即邏輯有效式（或重

48、言式）、矛盾式（或永假式）和可滿足式。,由于謂詞公式的復(fù)雜性和解釋的多樣性，至今還沒有一個可行的算法判定任何公式的類型。早在1936年，Churen和Turing各自獨立地證明了：對于Lp，其判定問題是不可解的。但是，Lp是個半個可判定的，即若Lp中公式是重言式，則存在算法在有限步驟內(nèi)能驗證它。當(dāng)然，對于一些較為簡單的公式，或某些特殊公式，還是可以判定其類型的。例如，如果一個謂詞公式是命題公式中的重言式的代換實例，則這個謂詞公式是邏輯

49、有效式（或重言式）。見教材P42 例2.4.3,,例 證明下面公式既不是永真式，也不是矛盾式 (1) ?x(F(x) ?G(x)) (2) ?x(F(x)?G(x)) (3) ?x?y(F(x)?G(y)?H(x,y))不難對每一個公式給出一個成假解釋和一個成真解釋, 從而證明它們既不是永真式，也不是矛盾式.,2.5 等價式與蘊涵式,1．等價式定義2.5.1 設(shè)A、B為任意兩個公式，若A?B為邏輯有效的，

50、則稱A與B是等價的，記為A?B，稱A?B為等價式。由于重言式(永真式)都是邏輯有效的，可見1.3節(jié)中的命題定律（基本等價式）都是Lp 等價式。,此外，還有一置換規(guī)則：設(shè)?(A)是含有A出現(xiàn)的公式，?(B)是用公式B替換若干個公式A的結(jié)果。若A?B，則?(A)? ?(B)。顯然，若?(A)為重言式，則?(B)也是重言式。,下面給出涉及量詞的一些等值式。(1) 量詞否定等值式（量詞可互相轉(zhuǎn)化）：(a)?(?x)A?(?x)?A(

51、b)?(?x)A?(?x)?A,這兩個等值式，可用量詞的定義給予說明。由于“并非對一切x，A為真”等價于“存在一些x，?A為真”，故(a)成立。由于“不存在一些x，A為真”等價于“對一切x，?A為真”，所以(b)成立。這兩個等值式的意義是：否定聯(lián)結(jié)詞可通過量詞深入到轄域中。對比這兩個式子，容易看出，將(?x)與(?x)兩者互換，可從一個式子得到另一個式子，這表明(?x)與(?x)具有對偶性。另外，由于這兩個公式成立也表明了，兩個量

52、詞是不獨立的，可以互相表示，所以只有一個量詞就夠了。,,例 將下面命題用兩種形式符號化 (1) 沒有不犯錯誤的人 (2) 不是所有的人都愛看電影解 (1) 令F(x)：x是人，G(x)：x犯錯誤. ??x(F(x)??G(x)) ??x(F(x)?G(x)) 請給出演算過程，并說明理由. (2) 令F(x)：x是人，G(x)：愛看電影.

53、 ??x(F(x)?G(x)) ??x(F(x)??G(x)) 給出演算過程，并說明理由.,對于多重量詞前置“?”，可反復(fù)應(yīng)用上面結(jié)果，逐次右移?。例如，?(?x)(?y)(?z)P(x,y,z)?(?x)(?y)(?z)?P(x,y,z)（2） 量詞轄域縮小或擴大等值式設(shè)B是不含x自由出現(xiàn)，A(x)為有x自由出現(xiàn)的任意公式，則有：,(a) (?x)(A(x)∧B)?(

54、?x)A(x)∧B (b) (?x)(A(x)∨B)?(?x)A(x)∨B(c) (?x)(A(x)→B)?(?x)A(x)→B(d) (?x)(B→A(x))?B→(?x)A(x)(e) (?x)(A(x)∧B)?(?x)A(x)∧B(f) (?x)(A(x)∨B)?(?x)A(x)∨B (g) (?x)(A(x)→B)?(?x)A(x)→B(h) (?x)(B→A(x))?B→(?x)A(x)。運用(c

55、) 、 (g)時要小心??！,(3) 量詞分配律等值式：(a) (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)(b) (?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)其中，A(x)，B(x)為有x自由出現(xiàn)的任何公式。(4) 多重量詞等值式(a) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)(b) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)其中A(x,y)為

56、含有x， y自由出現(xiàn)的任意公式。,2. 蘊涵式由于Ls中蘊涵式（或永真條件式）在Lp中都是邏輯有效的，而且使用代入規(guī)則得到蘊涵式也都是Lp中邏輯有效的。例如：(?x)P(x)?(?x)P(x)∨(?y)Q(y) 附加((?x)P(x)→Q(x,y))∧(?x)P(x)? Q(x,y) 假言推理,下面將給出Lp中的一些蘊涵式。(1) (a)(?x)A(x)∨(?x)B(

57、x)?(?x)(A(x)∨B(x))(b) (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)(c) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)(d) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)其中，A(x)和B(x)為含有x自由出現(xiàn)的任意公式。,2.6 謂詞公式范式,１.前束范式定義2.9.1 一個合式公式稱為前束范式，如果它有如下形式：(Q1x1)(

58、Q2x2)…(Qkxk)B其中Qi(1≤i≤k)為?或?，B為不含有量詞的公式。稱Q1x1Q2x2…Qkxk為公式的首標(biāo)。特別地，若Ａ中無量詞，則Ａ也看作是前束范式。,可見，前束范式的特點是，所有量詞均非否定地出現(xiàn)在公式最前面，且它的轄域一直延伸到公式之末。例如，(?x)(?y)(P(x,y)?Q(y,z)), R(x,y)等都是前束范式，而(?x)P(x)?(?y)Q(y)，(?x)(P(x)?(?y)Q(x,y))不是前束范

59、式。定理2.6.1 (前束范式存在定理) Lp中任意公式A都有與之等價的前束范式。本教材轉(zhuǎn)化前束范式原則：能不換名就不換！！,求公式的前束范式,（1）?x(F(x)→G(x)) → ?x H (x, y)（2） ( ?x F(x, y) → ?y G(y) ) → ?x H (x, y),公式的前束范式(續(xù)),例 求下列公式的前束范式 (1) ??x(M(x)?F(x))解 ??x(M(x)?F(x)

60、) ? ?x(?M(x)??F(x)) （量詞否定等值式） ? ?x(M(x)??F(x)) 兩步結(jié)果都是前束范式，說明前束范式不惟一.,例(續(xù)),(2) ?xF(x)???xG(x)解 ?xF(x)???xG(x) ??xF(x)??x?G(x) （量詞否定等值式） ??x(F(x)??G(x)) （量詞分配等值式）

61、另有一種形式 ?xF(x)???xG(x) ??xF(x)??x?G(x) ??xF(x)??y?G(y) ( 代替規(guī)則 ) ??x?y(F(x)??G(y)) ( 量詞轄域擴張 )兩種形式是等值的,例(續(xù)),(3) ?xF(x)???xG(x) 解 ?xF(x)???xG(x) ??xF(x)??x?G(x)

62、 ??x(F(x)??G(x)) （為什么？） 或 ??x?y(F(x)??G(y)) （為什么？） (4) ?xF(x)??y(G(x,y)??H(y)) 解 ?xF(x)??y(G(x,y)??H(y)) ??zF(z)??y(G(x,y)??H(y)) （換名規(guī)則） ??z?y(F(z)?(G(x,y)??H(y)))

63、（為什么？）,例(續(xù)),或 ??xF(x)??y(G(z,y)??H(y)) （代替規(guī)則） ??x?y(F(x)?(G(z,y)??H(y))) (5) ?x(F(x,y)??y(G(x,y)?H(x,z)))解 用換名規(guī)則, 也可用代替規(guī)則, 這里用代替規(guī)則 ?x(F(x,y)??y(G(x,y)?H(x,z))) ??x(F(x,u)??y(G(x,y)?H(x,z))) ?

64、?x?y(F(x,u)?G(x,y)?H(x,z)))注意：?x與?y不能顛倒,2.7 謂詞邏輯的推理理論,Lp是Ls的進(jìn)一步深化和發(fā)展，因此Ls的推理理論在Lp中幾乎可以完全照搬，只不過這時涉及的公式是Lp的公式罷了。在Lp中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運用有關(guān)量詞消去和添加規(guī)則是Lp推理理論中十分重要的關(guān)鍵所在。,在一階邏輯中，推理的形式結(jié)構(gòu)仍為：

65、若(H1∧H2∧…∧Hn)→C是邏輯有效式，則稱C是H1，H2，…，Hn的邏輯結(jié)論，記為 (H1∧H2∧…∧Hn)?C除命題邏輯的11條規(guī)則外，加上前面證明的：(a)(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))(b) (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)(c) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)(d) (?x)(A(x)→B(x))?(?x)A

66、(x)→(?x)B(x),定義2.7.1 在謂詞公式A(x)中，若x不自由出現(xiàn)在量詞?y或?y的轄域，則稱A(x)對于y是自由的。,１.有關(guān)量詞消去和產(chǎn)生規(guī)則還要用到以下4條推理規(guī)則注意：其中A ? B不一定表示A → B是邏輯有效式，而只表示在一定條件下，當(dāng)A為真時，B也為真的推理關(guān)系。,全稱量詞消去規(guī)則(簡稱UI或US規(guī)則， ?-)有兩種形式：(?x)A(x)?A(c) (?x)A(x)?A(y)

67、成立充分條件是： ① c為論域中任意個體常項， y為論域中任一個體 ；② x 在A(x)中是自由出現(xiàn)的； ③ y為任意的不在A(x)中約束出現(xiàn)的個體變項。,(2) 存在量詞消去規(guī)則 (簡稱EI或ES規(guī)則， ?-) (?x)A(x)?A(c) 成立充分條件是：①c是使A為真的特定個體常項；② c不曾在A(x)中出現(xiàn)過； ③若A(x)中有其它自由變項時，不能應(yīng)用本規(guī)

68、則。,(3) 全稱量詞產(chǎn)生規(guī)則 (簡稱UG規(guī)則， ?+)A(y)?(?x)A(x)成立條件：① y在A(y)中自由出現(xiàn)，且y取任何值時A均為真；②取代y的x不能在A(y)中約束出現(xiàn)； ③ A(y)中含有個體常項時，要小心使用。,(4) 存在量詞產(chǎn)生規(guī)則 (簡稱EG規(guī)則， ?+) A(c)?(?x)A(x) 成立充分條件： ①c是特定的個體常項；② 取代c的個體變元x不能已在A(c