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

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

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

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

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

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

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

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

8、,當(dāng)n=1時(shí)，稱一元謂詞；當(dāng)n=2時(shí)，稱為二元謂詞，…。特別地，當(dāng)n=0，稱為零元謂詞。零元謂詞是命題，這樣命題與謂詞就得到了統(tǒng)一。,n元謂詞不是命題，只有其中的個(gè)體變?cè)锰囟▊€(gè)體或個(gè)體常元替代時(shí)，才能成為一個(gè)命題。但個(gè)體變?cè)谀男┱撚蛉√囟ǖ闹担瑢?duì)命題的真值極有影響。例如，令S(x)：x是大學(xué)生。若x的論域?yàn)槟炒髮W(xué)的計(jì)算機(jī)系中的全體同學(xué)，則S(x)是真的；若x的論域是某中學(xué)的全體學(xué)生，則S(x)是假的；若x的論域是某劇場(chǎng)中的觀

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

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

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

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

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

14、為謂詞的量化。若一個(gè)謂詞中所有個(gè)體變?cè)剂炕?，則該謂詞就變成了命題。這是因?yàn)樵谥^詞被量化后，可以在整個(gè)個(gè)體域中考慮命題的真值了。,量詞(舉例)設(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)),個(gè)體變項(xiàng)(varible)表示不確定的泛指對(duì)象用小寫(xiě)英文字母x,y,z,…來(lái)表示例如： F(x): x是人。G(x): x是數(shù)?！按嬖谥恕? ?xF(x)“僅有一人”: ?!xF(x)“萬(wàn)物皆數(shù)”: ?xG(x),個(gè)體常項(xiàng)(constant)表示具體的特定對(duì)象用小寫(xiě)英文字母a,b,c,…來(lái)表示例如： a:王大明，b:王小明， G(x,y): x與y是兄弟,“王大明與王小明是兄弟”: G(a,b

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

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

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

19、,例3 在一階邏輯中將下面命題符號(hào)化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無(wú)理數(shù)大于有的有理數(shù)解 注意: 題目中沒(méi)給個(gè)體域, 一律用全總個(gè)體域  (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是無(wú)理數(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)) 兩者等值,幾點(diǎn)注意： 1元謂詞與多元謂詞的區(qū)分無(wú)特別要求 用全總個(gè)體域量詞順序一般不要隨便顛倒 否定式的使用思考： ①

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

22、用來(lái)表示個(gè)體常元和個(gè)體變?cè)?。例如，令f(x,y)表示x+y，謂詞N(x)表示x是自然數(shù)，那么f(2,3)表示個(gè)體自然數(shù)5，而N(f(2,3))表示5是自然數(shù)。這里函數(shù)是就廣義而言的。例如P(x):x是教授，f(x):x的父親，c:張強(qiáng)，那么P(f(c))便是表示“張強(qiáng)的父親是教授”這一命題。,函數(shù)的使用給謂詞表示帶來(lái)很大方便。例如，用謂詞表示命題：“對(duì)任意整數(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是項(xiàng)，則稱P(t1，t2，…，tn)為L(zhǎng)s中原子謂詞公式，簡(jiǎn)稱原子公式。下面，由原子公式出發(fā)，給出Lp中的合式謂詞公式的歸納定義。,定義2.2.3 合式謂詞公式當(dāng)且僅當(dāng)由下列規(guī)則形成的符號(hào)串① 原子公式是合式謂

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

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

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

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

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

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

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

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

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

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

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

35、.,例3 在一階邏輯中將下面命題符號(hào)化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無(wú)理數(shù)大于有的有理數(shù)解 注意: 題目中沒(méi)給個(gè)體域, 一律用全總個(gè)體域  (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是無(wú)理數(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 約束變?cè)c自由變?cè)?定義2.3.1 給定一個(gè)謂詞公式A，其中有一部分公式形如(?x)B(x)或(?x)B(x)，則稱

37、它為A的x約束部分，稱B(x)為相應(yīng)量詞的作用域或轄域。在轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變?cè)?；B中不是約束出現(xiàn)的其它個(gè)體變?cè)某霈F(xiàn)稱為自由出現(xiàn)，這些個(gè)體變?cè)Q自由變?cè)?對(duì)于給定的謂詞公式，能夠準(zhǔn)確地判定它的轄域、約束變?cè)妥杂勺冊(cè)呛苤匾?。通常，一個(gè)量詞的轄域是某公式A的一部分，稱為A的子公式。因此，確定一個(gè)量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講：,①若量詞后有括號(hào)，則括號(hào)內(nèi)的子公式就是該量詞的轄

38、域；②若量詞后無(wú)括號(hào)，則與量詞鄰接的子公式為該量詞的轄域。判定給定公式A中個(gè)體變?cè)羌s束變?cè)€是自由變?cè)?，關(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)變?cè)? 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)),今后常用元語(yǔ)言符號(hào)A(x)表示x是其中的一個(gè)個(gè)體變?cè)杂沙霈F(xiàn)的任意公式，如A(x)可為P(x)?Q(x)，P(x)?(?y)Q(x,y)等。一旦在A(x)前加上量詞(?x)或(?x)，即得公式(?x)A(x),或(?x)A(x)。這時(shí)，x即是約束出現(xiàn)了。類(lèi)似地，用A(x,y)表示x和y是自由出現(xiàn)的公式。,定義2.3.2 設(shè)A為任意一個(gè)公式，若A中無(wú)自由出現(xiàn)的個(gè)體變?cè)?，則稱A為封閉的合式公式，簡(jiǎn)

40、稱閉式。由閉式定義可知，閉式中所有個(gè)體變?cè)鶠榧s束出現(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)不是閉式。,從下面討論可以看出，在一公式中，有的個(gè)體變?cè)瓤梢允羌s束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，采用下面兩個(gè)規(guī)則：①約束變?cè)獡Q名規(guī)則，將量詞轄域中某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)?，改成本?/p>

41、域中未曾出現(xiàn)過(guò)的個(gè)體變?cè)?，其余不變。②自由變?cè)嬉?guī)則，對(duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ?，且處處代替?例： ?x ?y ( R(x,y) ? L(y,z) ) ??xH(x,y)換名和代替為： ?x ?y ( R(x,y) ? L(y,z) ) ??tH(t,w),換名規(guī)則與代替規(guī)則的共同點(diǎn)都是不能改變約束關(guān)系，而不同點(diǎn)是：① 施行的對(duì)象不同。換名是對(duì)約束變?cè)┬?，代替是?duì)自由變?cè)?/p>

42、施行。② 施行的范圍不同。換名可以只對(duì)公式中一個(gè)量詞及其轄域內(nèi)施行，即只對(duì)公式的一個(gè)子公式施行；而代替必須對(duì)整個(gè)公式同一個(gè)自由變?cè)乃凶杂沙霈F(xiàn)同時(shí)施行，即必須對(duì)整個(gè)公式施行。,③ 施行后的結(jié)果不同。換名后，公式含義不變，因?yàn)榧s束變?cè)桓拿麨榱硪粋€(gè)個(gè)體變?cè)?，約束關(guān)系不改變。約束變?cè)荒芨拿麨閭€(gè)體常元；代替，不僅可用另一個(gè)個(gè)體變?cè)M(jìn)行代替，并且也可用個(gè)體常元去代替，從而使公式由具有普遍意義變?yōu)閮H對(duì)該個(gè)體常元有意義，即公式的含義改變了。,

43、2.4 公式解釋與類(lèi)型,1．公式解釋一般情況下，Lp中的公式含有：個(gè)體常元、個(gè)體變?cè)s束變?cè)蜃杂勺冊(cè)?、函?shù)變?cè)?、為謂詞變?cè)?，?duì)各種變?cè)弥付ǖ奶厥獬Ｔゴ?，就?gòu)成了一個(gè)公式的解釋。當(dāng)然在給定的解釋下，可以對(duì)多個(gè)公式進(jìn)行解釋。下面給出解釋的一般定義。,定義2.4.1 一個(gè)解釋I由下面4部分組成：① 非空個(gè)體域DI。② DI中部分特定元素a’，b’，…。③ DI上的特定一些函數(shù)f’，g’，…。④ DI上特定謂詞：P’

44、，Q’，…。在一個(gè)具體解釋中，個(gè)體常元、函數(shù)符號(hào)、謂詞符號(hào)的數(shù)量一般是有限的，并且其解釋一旦確定下來(lái)就不再改變，只是個(gè)體變?cè)闹翟趥€(gè)體域DI內(nèi)變化，量詞符?或?僅作用于DI中的元素。,設(shè)個(gè)體域?yàn)橛邢藜疍={a1, a2,…, an}, 則 ?xA(x)?A(a1)∧A(a2)∧…∧A(an) ?xA(x)?A(a1)∨A(a2)∨…∨A(an)例: 個(gè)體域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) 個(gè)體域 D=N (b) (c) (d) 謂詞說(shuō)明下列公式在 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),兩點(diǎn)說(shuō)明:5個(gè)小題都是閉式,在I下全是命題(3)與(5)說(shuō)明，量詞順序不能隨意改變,(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．公式類(lèi)型定義2.4.2 ① 若一公式在任何解釋下都是真的，稱該公式為邏輯有效的，或永真的。② 若一公式在任何解釋下都是假的，稱該公式為矛盾式，或永假式。③ 若一公式至少存在一個(gè)解釋使其為真，稱該公式為可滿足式。,從定義可知，邏輯有效式為可滿足式，反之未必成立。與命題公式中分類(lèi)一樣，謂詞公式也分為三種類(lèi)型，即邏輯有效式（或重

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

49、有效式（或重言式）。見(jiàn)教材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))不難對(duì)每一個(gè)公式給出一個(gè)成假解釋和一個(gè)成真解釋, 從而證明它們既不是永真式，也不是矛盾式.,2.5 等價(jià)式與蘊(yùn)涵式,1．等價(jià)式定義2.5.1 設(shè)A、B為任意兩個(gè)公式，若A?B為邏輯有效的，

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

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

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

53、 ??x(F(x)?G(x)) ??x(F(x)??G(x)) 給出演算過(guò)程，并說(shuō)明理由.,對(duì)于多重量詞前置“?”，可反復(fù)應(yīng)用上面結(jié)果，逐次右移?。例如，?(?x)(?y)(?z)P(x,y,z)?(?x)(?y)(?z)?P(x,y,z)（2） 量詞轄域縮小或擴(kuò)大等值式設(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)。運(yùn)用(c

55、) 、 (g)時(shí)要小心！！,(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. 蘊(yùn)涵式由于Ls中蘊(yùn)涵式（或永真條件式）在Lp中都是邏輯有效的，而且使用代入規(guī)則得到蘊(yùn)涵式也都是Lp中邏輯有效的。例如：(?x)P(x)?(?x)P(x)∨(?y)Q(y) 附加((?x)P(x)→Q(x,y))∧(?x)P(x)? Q(x,y) 假言推理,下面將給出Lp中的一些蘊(yùn)涵式。(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 一個(gè)合式公式稱為前束范式，如果它有如下形式：(Q1x1)(

58、Q2x2)…(Qkxk)B其中Qi(1≤i≤k)為?或?，B為不含有量詞的公式。稱Q1x1Q2x2…Qkxk為公式的首標(biāo)。特別地，若Ａ中無(wú)量詞，則Ａ也看作是前束范式。,可見(jiàn)，前束范式的特點(diǎn)是，所有量詞均非否定地出現(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都有與之等價(jià)的前束范式。本教材轉(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é)果都是前束范式，說(shuō)明前束范式不惟一.,例(續(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)) ( 量詞轄域擴(kuò)張 )兩種形式是等值的,例(續(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中幾乎可以完全照搬，只不過(guò)這時(shí)涉及的公式是Lp的公式罷了。在Lp中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運(yù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)對(duì)于y是自由的。,１.有關(guān)量詞消去和產(chǎn)生規(guī)則還要用到以下4條推理規(guī)則注意：其中A ? B不一定表示A → B是邏輯有效式，而只表示在一定條件下，當(dāng)A為真時(shí)，B也為真的推理關(guān)系。,全稱量詞消去規(guī)則(簡(jiǎn)稱UI或US規(guī)則， ?-)有兩種形式：(?x)A(x)?A(c) (?x)A(x)?A(y)

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

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