2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩105頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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ǔ)稱為謂詞。,1.個(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、)是假。,2.原子謂詞公式原子命題的謂詞形式還可以進(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)稱為特性謂詞。,3.量詞利用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 謂詞公式與翻譯,1.謂詞公式為了方便處理數(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)次使用①、②、③和④形成的才是合式謂詞公式。,2.謂詞邏輯的翻譯把一個(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è)弥付ǖ奶厥獬Tゴ?,就?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 謂詞公式范式,1.前束范式定義2.9.1 一個(gè)合式公式稱為前束范式,如果它有如下形式:(Q1x1)(

58、Q2x2)…(Qkxk)B其中Qi(1≤i≤k)為?或?,B為不含有量詞的公式。稱Q1x1Q2x2…Qkxk為公式的首標(biāo)。特別地,若A中無(wú)量詞,則A也看作是前束范式。,可見(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是自由的。,1.有關(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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論