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

1、1離散數(shù)學(xué)離散數(shù)學(xué)課程學(xué)時(shí)：課程學(xué)時(shí)：4848講講 授：楊紹禹授：楊紹禹一階邏輯n例：蘇格拉底論斷q前提n“所有的人都是要死的”n“蘇格拉底是人”q結(jié)論n“所以蘇格拉底是要死的”n命題邏輯限定原子命題是不能細(xì)分的整體q命題邏輯的局限性PQRPQR不是命題演算不是命題演算的有效推理的有效推理問題的提出：( (為什么要對原子命題進(jìn)一步細(xì)分為什么要對原子命題進(jìn)一步細(xì)分? ?) )？n例q1：小張是大學(xué)生q2：小李是大學(xué)生qQ1：2大于3qQ2：6大于4n不同原子命題之間是有內(nèi)在聯(lián)系的，但命題邏輯無法研究這種內(nèi)在聯(lián)系n解決問題的方法q分析原子命題，分離其主語和謂語q考慮一般和個(gè)別，全稱和存在刻劃個(gè)體的

2、性質(zhì)刻劃兩個(gè)個(gè)體的關(guān)系原子命題不能細(xì)分嗎？(能否能否對原子命題進(jìn)一步細(xì)分對原子命題進(jìn)一步細(xì)分? ?) )謂詞和量詞n4.1 謂詞謂詞q謂詞的概念和表示(如何如何對原子命題進(jìn)一步細(xì)分對原子命題進(jìn)一步細(xì)分? ?) )n在原子命題中，用來刻劃一個(gè)個(gè)體的性質(zhì)或幾個(gè)個(gè)體之間關(guān)系的成分稱為謂詞謂詞。n刻劃一個(gè)個(gè)體性質(zhì)的詞稱為一元謂詞一元謂詞；刻劃n個(gè)個(gè)體之間關(guān)系的詞稱為n元謂詞。元謂詞。謂詞常用大寫英文字母表示。n謂詞與個(gè)體詞一起才能表示命題。用A(a)表示“a具有性質(zhì)A”(或“a屬于A類”)，用B(a1,a2,an)表示“a1,a2,an關(guān)系滿足B”。q個(gè)體n能夠獨(dú)立存在的事物，思維的對象n通常用小寫英

3、文字母a、b、c、.表示個(gè)體常量個(gè)體常量n用小寫英文字母x、y、z.表示任何個(gè)體，則稱這些字母為個(gè)體個(gè)體變元變元三個(gè)要件以命題邏輯為基礎(chǔ)謂詞命名式(謂詞填式)(a) 5是質(zhì)數(shù) (b) 張明生于北京(c) 7=32P(x)：x是質(zhì)數(shù)G(x, y)： x生于y ，a：張明，b：北京H(x, y, z) ：x=yzP(5)G(a,b)H(7,3,2)謂詞 個(gè)體詞謂詞命名式(謂詞填式)N元謂詞填式中變元謂詞填式中變元的次序很重要元的次序很重要例例思考：xyz該怎么表示？練習(xí)練習(xí)1.小張不是工人2.張三和李四是表兄弟3.小莉是非常聰明和美麗的4.實(shí)數(shù)x大于實(shí)數(shù)y5.大灰狼偷吃了小羊羔 W(a)W(x):

4、x是工人a: 小張 P(a,b)P(a)Q(a)R(x):x是實(shí)數(shù)G(x,y): xy G(R(x),R(y)?R(x)R(y)G(x,y)否定命題P(x)Q(y)E(x,y)P1(x)P2(x)P3(x) Q1(y)Q2 (y)E(x,y)問題：R(x,y):x和y是實(shí)數(shù)？分解到詞n謂詞常元q一個(gè)字母代表一特定謂詞, 則稱此字母為謂詞常元(量)。例如P(x)表示“x是質(zhì)數(shù)”這種模式的判斷,P就是謂詞常元。n謂詞變元q若字母代表任意謂詞, 則稱此字母為謂詞變元n論域q謂詞命名式中個(gè)體變元的取值范圍q個(gè)體域與全總域q空集不能作為論域謂詞謂詞命題函數(shù)n謂詞命名式不是不是命題q若謂詞是常元q個(gè)體詞是

5、常元q謂詞命名式才成為一個(gè)命題n命題函數(shù)q由一個(gè)謂詞和若干個(gè)個(gè)體變元組成的命題形式稱為簡單命題函數(shù)簡單命題函數(shù)，表示為P(x1,x2,xn)。由一個(gè)或若干個(gè)簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組成的命題形式稱為復(fù)合命題函數(shù)復(fù)合命題函數(shù)qn=0時(shí)n命題變元命題變元n例q A(x)：x身體好 B(x)：x學(xué)習(xí)好 C(x)：x工作好q表示“如果x身體不好，則x的學(xué)習(xí)與工作都不會(huì)好”的復(fù)合命題函數(shù)qA(x)(B(x)C(x)n命題函數(shù)不是命題，沒有確定真值，但其中謂詞是謂詞常量時(shí)，可通過個(gè)體指派使其成為命題。如：若簡單命題函數(shù)P(X)表示“x是質(zhì)數(shù)”，則P(1)為F，P(2)為T。n除個(gè)體指派外，還常用“量”作

6、出判斷，如：“所有的人都是要死的”、“有的數(shù)是質(zhì)數(shù)”。這種表述在數(shù)理邏輯目標(biāo)語言中需要引入量詞，當(dāng)然量化與個(gè)體指派之間是有聯(lián)系的，數(shù)理邏輯中常用量詞有兩個(gè)全稱量詞和存在量詞。4.2 量詞n例q “所有的正整數(shù)都是素?cái)?shù)” q “有些正整數(shù)是素?cái)?shù)”n假設(shè)q只有兩個(gè)正整數(shù)a和bq個(gè)體域?yàn)閍,bqP(x)：x是素?cái)?shù)P(a) P(b)P(a) P(b)全稱量詞n記作n表示“每個(gè)”、“任何一個(gè)”、“一切”、“所有的”、“凡是”、“任意的”等nx讀作“任意x”， “所有x”， “對一切x ”n量詞后邊的個(gè)體變元，指明對哪個(gè)個(gè)體變元量化，稱為量詞后的指導(dǎo)變元指導(dǎo)變元n例q所有人都是要死的qD(x)：x是要死的

7、q個(gè)體域：所有人構(gòu)成的集合qx D(x)存在量詞n記作 n表示“有些”、“一些”、“某些”、“至少一個(gè)”等n x讀作“存在x”，“對某些x”或“至少有一x”n指導(dǎo)變元指導(dǎo)變元n例q有些有理數(shù)是整數(shù)q(x)：x是整數(shù)q個(gè)體域：有理數(shù)集合qx(x)全總個(gè)體域（全總域）n含有量詞的命題的真值與論域有關(guān)n含有量詞的命題的表達(dá)式的形式與論域有關(guān)n全總個(gè)體域全總個(gè)體域q宇宙間所有的個(gè)體聚集在一起所構(gòu)成的集合q約定約定n除特殊說明外，均使用全總個(gè)體域n對個(gè)體變化的真正取值范圍，用特性謂詞特性謂詞加以限制例1)所有的人都是要死的2)有的人活百歲以上D(x)：x是要死的G(x) ：x活百歲以上n個(gè)體域E為全體人

8、組成的集合1)x D(x)2)x G(x)n全總個(gè)體域q引入特性謂詞qM(x)：x是人1)x(M(x) D(x)2)x (M(x)G(x)特性謂詞添加規(guī)則n對全稱量詞, 特性謂詞作為條件式之前件加入n對存在量詞, 特性謂詞作為合取項(xiàng)而加入n例(a) 沒有不犯錯(cuò)誤的人F(x)：x犯錯(cuò)誤 M(x)：x是人 x (M(x)F(x)(b) 凡實(shí)數(shù), 或大于零，或等于零，或小于零R(x)：x是實(shí)數(shù)L(x, y)：xyE (x, y) ： x = yS(x, y)：x yx(R(x) L(x, 0) E (x, 0) S (x, 0) 4.3 量化斷言和命題的關(guān)系n假設(shè)論域有限,不妨設(shè)論域D=1,2,3q

9、xP(x)？nxP(x) P(1) P(2) P(3)qxP(x)？nxP(x) P(1) P(2) P(3)n若論域無限可數(shù)，概念可以推廣n兩個(gè)量詞共軛qxP(x) xP(x)qxP(x) xP(x)xA(x) xA(x)a1a2anx取遍論域中的所有值T關(guān)于x的命題函數(shù)A(x)取值皆為T全稱命題xA(x)的真值為TTTTxA(x) xA(x)a1a2anFFFF關(guān)于x的命題函數(shù)A(x)取值皆為F存在命題xA(x)的真值為F量化斷言和個(gè)體指派的關(guān)系x取遍論域中的所有值總之：總之： 1.1.全稱命題全稱命題 xAxA(x)(x)為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng) a aDD，A A(a)(a)皆為皆

10、為真真 2.2.全稱命題全稱命題 xAxA(x)(x)為假，當(dāng)且僅當(dāng)為假，當(dāng)且僅當(dāng) a aDD，A A(a)(a)為假。為假。 3.3.存在命題存在命題 xAxA(x)(x)為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng) a aDD，A A(a)(a)為真。為真。 4.4.存在命題存在命題 xAxA(x)(x)為假，當(dāng)且僅當(dāng)為假，當(dāng)且僅當(dāng) a aDD，A A(a)(a)皆為假。皆為假。4.4 謂詞公式n個(gè)體函數(shù)（函詞）q例n小王比他的父親高 H(x，y)：x比y高a：小王b：小王的父親H(a，b)無法顯示個(gè)體之間的依賴關(guān)系q定義函數(shù)nf(x)=x的父親nH(a， f(a)n函詞與謂詞的區(qū)別q函詞中的個(gè)體變元用個(gè)

11、體代入后的結(jié)果依然是個(gè)體nf(a)=小王的父親q謂詞中的個(gè)體變元用確定的個(gè)體帶入后就變成了命題nM(x)：x是人nM(a)：小王是人q函詞是論域到論域的映射nf : DDq謂詞是從論域到T,F的映射nM : D T,F項(xiàng)和原子公式n項(xiàng)(item)q表示個(gè)體q定義(1)個(gè)體常量是項(xiàng)(2)個(gè)體變元是項(xiàng)(3)如果f是一個(gè)n(n1)元函詞，其t1, t2, tn都是項(xiàng)，則f(t1, t2, tn)是項(xiàng)p例na, b, cnx, y, znf (x), g (a, f (y) n原子公式(atom)q定義n若P是一個(gè)n元謂詞，且t1,t2,tn是項(xiàng)，則P(t1,t2,tn)是 原子公式q命題詞也是原子(

12、n=0)q例nP, Q (x), A (x, f (x), B (x, y, a)謂詞演算的合式公式(Wff)n也叫謂詞公式，簡稱公式n定義(1)原子公式是合式公式(2)如果A、B是合式公式，則(A)、(AB)、(AB)、(AB)、(AB)都是合式公式(3)如果A是合式公式，x是個(gè)體變元，則x和x也是合式公式(4)有限次地使用規(guī)則(1)至(3)求得的公式是合式公式（謂詞公式）n括號(hào)省略規(guī)則n例qP，(Q(x)P)，x(A(x)B(x)，xC(x)， xZ(y)命題符號(hào)化n謂詞邏輯中比較復(fù)雜n命題的符號(hào)表達(dá)式與論域有關(guān)系q例：每個(gè)自然數(shù)都是整數(shù)q論域D=NnI(x)：x是整數(shù)nx I (x)q論

13、域?yàn)槿倐€(gè)體域n特性謂詞N(x)：x是自然數(shù)nx(N(x)I(x)例：將下列命題符號(hào)化(1)所有大學(xué)生都喜歡一些歌星。 S(x)：x是大學(xué)生，X(x)：x是歌星，L(x,y)：x喜歡y x(S(x)y(X(y)L(x,y) (2)發(fā)光的不都是金子。P(x)：x發(fā)光，G(x)：x是金子x(P(x)G(x) (3)某些人對食物過敏F(x, y)：x對y過敏，M(x)：x是人， G(x)：x是食物 x (M(x)y(G(y)F(x,y)(4)每個(gè)人都有些缺點(diǎn) H(x, y)：x有y，M(x)：x是人， S(x)：x是缺點(diǎn) x(M(x) y(S(y)H(x,y)(5)盡管有人聰明, 但未必人人聰明 M

14、(x)：x是人， S(x)：x聰明 x(M(x)S(x)x(M(x)S(x)(6)所有老虎都能吃人(7)不管白貓黑貓，凡能逮住耗子的就是好貓(8)無論是步行的、騎馬的、乘車的，凡口渴的皆要喝水練習(xí)：將下列命題符號(hào)化(1)所有教練員都是運(yùn)動(dòng)員；(J(x)，L(x)(2)某些運(yùn)動(dòng)員是大學(xué)生；(S(x)(3)某些教練員是年老的，但是健壯的；(O(x)，V(x)(4)金教練雖不年老，但不健壯；(j)(5)不是所有運(yùn)動(dòng)員都是教練員；(6)某些大學(xué)生運(yùn)動(dòng)員是國家選手；(C(x)(7)沒有一個(gè)國家選手不是健壯的；(8)所有老的國家選手都是運(yùn)動(dòng)員；(9)沒有一位女同志既是國家選手又是家庭婦女；(W(x)，H(

15、x)(10)有些女同志既是教練員又是國家選手；(11)所有運(yùn)動(dòng)員都?xì)J佩某些教練員；(A(x, y)(12)有些大學(xué)生不欽佩運(yùn)動(dòng)員。練習(xí)參考答案(1)x(J(x)L(x)(2)x(L(x)S(x)(3)x(J(x)O(x)V(x) (4) J(j)O(j)V(j) (5)x(L(x)J(x)(6)x(S(x)L(x)C(x) (7)x(C(x)V(x)(8)x(C(x)O(x)L(x) (9)x(W(x)C(x)H(x) (10)x(W(x)J(x)C(x) (11)x(L(x)y(J(y)A(x,y)(12)x(S(x)y(L(y)A(x,y)(1)所有教練員都是運(yùn)動(dòng)員；(J(x)，L(x)(

16、2)某些運(yùn)動(dòng)員是大學(xué)生；(S(x)(3)某些教練員是年老的，但是健壯的； (O(x)，V(x)(4)金教練雖不年老，但不健壯；(j)(5)不是所有運(yùn)動(dòng)員都是教練員；(6)某些大學(xué)生運(yùn)動(dòng)員是國家選手；(C(x)(7)沒有一個(gè)國家選手不是健壯的；(8)所有老的國家選手都是運(yùn)動(dòng)員；(9)沒有一位女同志既是國家選手又是家庭婦女 (W(x)，H(x)(10)有些女同志既是教練員又是國家選手；(11)所有運(yùn)動(dòng)員都?xì)J佩某些教練員；(A(x, y)(12)有些大學(xué)生不欽佩運(yùn)動(dòng)員。幾個(gè)特別的例子(1) 如果明天下雨下雨，則某些人將被淋濕 不是個(gè)體不是個(gè)體定義命題詞P：明天下雨， M(x)：x是人，W(x)：x將

17、被淋濕P x(M(x) W(x)(2) 有且僅有有且僅有一個(gè)偶素?cái)?shù)A(x)：x是偶素?cái)?shù) x(A(x) y(A(y)x=y)或者 x(A(x)y(xyA(y)(3) 頂多只有一臺(tái)頂多只有一臺(tái)機(jī)器是好的 A(x)：x是好機(jī)器用符號(hào) !xA(x) 表示有且僅有一個(gè)個(gè)體滿足Axy(A(x)A(y)x=y)用符號(hào) !xA(x) 表示頂多有一個(gè)個(gè)體滿足A思考：用E(x)表示“x是偶數(shù)”， P(x)表示“x是素?cái)?shù)”，公式會(huì)是怎么樣？ (4) 如果人都愛美，則漂亮衣服有銷路 M(x)：x是人，L(x)：x愛美， C(x)：x是衣服， B(x)：x是漂亮的，S(x)：x有銷路x(M(x)L(x)x(C(x)B(

18、x) S(x)問題一：前后兩個(gè)x是否指同一個(gè)個(gè)體？答：前后兩個(gè)x不是不是同一個(gè)個(gè)體問題二：若寫成如下形式是否正確？x(M(x)L(x) y(C(y)B(y) S(y)答：是正確的正確的，顯然x(M(x)L(x) x(C(x)B(x) S(x) x(M(x)L(x) y(C(y)B(y) S(y)4.5 自由變元與約束變元n量詞的作用域作用域(轄域轄域)q定義定義：在謂詞公式中，量詞的作用范圍稱之為量詞的作用域，也叫量詞的轄域。q例nxA(x)qx的轄域?yàn)锳(x)nx(P(x)Q(x)yR(x,y)qx的轄域是(P(x)Q(x)yR(x,y)qy的轄域?yàn)镽(x,y)nxyz(A(x,y)B(x,

19、y,z)C(t) x x的轄域的轄域 z z的轄域的轄域 y y的轄域的轄域自由變元自由變元一般地，n如果量詞后邊只是一個(gè)原子謂詞公式時(shí)，該量詞的轄域就是此原子謂詞公式。n如果量詞后邊是括號(hào)，則此括號(hào)所表示的區(qū)域就是該量詞的轄域。n如果多個(gè)量詞緊挨著出現(xiàn)，則后邊的量詞及其轄域就是前邊量詞的轄域。n約束變元q如果個(gè)體變元x在x或者x的轄域內(nèi)，則稱x在此轄域內(nèi)約束出現(xiàn)，并稱x在此轄域內(nèi)是約束變元n自由變元q如果個(gè)體變元x不在任何量詞的轄域內(nèi)，則稱x是自由出現(xiàn)，并稱x是自由變元n例 x(F(x,y)yP(y)Q(z) F(x,y)中的x和P(y)中的y是約束變元而F(x,y)中的y和Q(z)中的z是

20、自由變元例：指出下列各公式中的量詞轄域及自由變元和約束變元nxy(P(x)Q(y)zR(z)qx的轄域y(P(x)Q(y)qy的轄域P(x)Q(y)qz的轄域R(z)nx(P(x,y)yQ(x,y,z)S(x,z)qx的轄域P(x,y)yQ(x,y,z)其中x是約束變元y是自由變元qy的轄域Q(x,y,z)其中y是約束變元x, z是自由變元qS(x，z)中x，z是自由變元對約束變元和自由變元的幾點(diǎn)說明n約束變元用什么符號(hào)表示無關(guān)緊要qxA(x)與yA(y)是一樣的 n一個(gè)謂詞公式如果無自由變元，它就表示一個(gè)命題q例：A(x)表示x是個(gè)大學(xué)生qxA(x)或者xA(x)是命題nP(x,y,z)表示

21、x+yzq假設(shè)論域是整數(shù)集，xyP(x,y,z)表示？n“任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+yz” 。q令z=1，則xyP(x,y,1)表示？n“任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+y1”,qxyP(x,y,1)表示？例36封閉的公式定義定義4.6 若公式若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為為封閉封閉的公式的公式，簡稱，簡稱閉式閉式.例如，例如， x y(F(x) G(y)H(x,y) 為閉式，為閉式，而而 x(F(x) G(x,y) 不是閉式不是閉式 37公式的解釋FafF定義定義4.7 設(shè)設(shè)L 是是L生成的一階語言生成的一階語言, L

22、的的解釋解釋I由由4部分組成：部分組成： (a) 非空個(gè)體域非空個(gè)體域 DI . (b) 對每一個(gè)個(gè)體常項(xiàng)符號(hào)對每一個(gè)個(gè)體常項(xiàng)符號(hào)a L, 有一個(gè)有一個(gè) DI, 稱稱 為為a在在I 中的解釋中的解釋. (c) 對每一個(gè)對每一個(gè)n元函數(shù)符號(hào)元函數(shù)符號(hào)f L, 有一個(gè)有一個(gè)DI上的上的n元函數(shù)元函數(shù) , 稱稱 為為f在在I中的解釋中的解釋. (d) 對每一個(gè)對每一個(gè)n元謂詞符號(hào)元謂詞符號(hào)F L, 有一個(gè)有一個(gè)DI上的上的n元謂詞常項(xiàng)元謂詞常項(xiàng) , 稱稱 為為F在在I中的解釋中的解釋.aInIDDf:afF 設(shè)公式設(shè)公式A, 取個(gè)體域取個(gè)體域DI , 把把A中的個(gè)體常項(xiàng)符號(hào)中的個(gè)體常項(xiàng)符號(hào)a、函數(shù)符

23、、函數(shù)符號(hào)號(hào)f、謂詞符號(hào)、謂詞符號(hào)F分別替換成它們在分別替換成它們在I中的解釋中的解釋 、 、 , 稱稱所得到的公式所得到的公式A 為為A在在I下的下的解釋解釋, 或或A在在I下下被解釋成被解釋成A .實(shí)例yxyxF :),(0 ayxyxgyxyxf ),(,),(例例6 給定解釋給定解釋 I 如下：如下： (a) 個(gè)體域個(gè)體域 D=R (b) (c) (d) 寫出下列公式在寫出下列公式在I下的解釋下的解釋, 并指出它的真值并指出它的真值. (1) xF(f(x,a),g(x,a) x(x+0=x 0) 真真(2) x y(F(f(x,y),g(x,y)F(x,y) x y(x+y=x yx

24、=y) 假假(3) xF(g(x,y),a) x(x y=0) 真值不定真值不定, 不是命題不是命題39公式的類型n定理4.1 閉式在任何解釋下都是命題注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. n定義4.8 若公式A在任何解釋下均為真, 則稱A為永真式(邏輯有效式). 若A在任何解釋下均為假, 則稱A為矛盾式(永假式). 若至少有一個(gè)解釋使A為真, 則稱A為可滿足式.n幾點(diǎn)說明： 永真式為可滿足式，但反之不真 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的40代換實(shí)例n定義4.9 設(shè)A0是含命題變項(xiàng) p1, p2, , pn的命題公式，A1, A2, , An是n個(gè)

25、謂詞公式，用Ai (1in) 處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.n例如， F(x)G(x), xF(x)yG(y)等都是pq的代換實(shí)例.n定理4.2 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式. 41實(shí)例n例7 判斷下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x)重言式重言式 p(qp) 的代換實(shí)例，故為永真式的代換實(shí)例，故為永真式. (2) ( xF(x)yG(y)yG(y)矛盾式矛盾式 (pq) q 的代換實(shí)例，故為永假式的代換實(shí)例，故為永假式. (3) x(F(x)G(x)解釋解釋I1: 個(gè)體域個(gè)體域N, F(x):x

26、5, G(x): x4, 公式為真公式為真 解釋解釋I2: 個(gè)體域個(gè)體域N, F(x):x5, G(x):xy), 真真; 而而B被解釋為被解釋為 y(yy), 假假 原因原因: 在在A中中x自由出現(xiàn)自由出現(xiàn)在在 y的轄域的轄域F(x,y)內(nèi)內(nèi)反例反例2. 前提前提: P(x)Q(x), P(x) 結(jié)論結(jié)論: xQ(x) 取解釋取解釋I: 個(gè)體域?yàn)閭€(gè)體域?yàn)閆, 在在I下前提為下前提為真真, 結(jié)論為假結(jié)論為假, 從而推理不正確從而推理不正確整除整除被被是偶數(shù)是偶數(shù)2:)(,:)(xxQxxP69反例2(續(xù))n“證明”: P(x)Q(x) 前提引入 P(x) 前提引入 Q(x) 假言推理 xQ(x

27、) +n錯(cuò)誤原因: 在使用+規(guī)則, 而x在前提的公式中自由出現(xiàn).70第五章 一階邏輯等值演算與推理n主要內(nèi)容q一階邏輯等值式 基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則q前束范式q推理的形式結(jié)構(gòu)q自然推理系統(tǒng)NL 推理定律、推理規(guī)則71基本要求n深刻理解并牢記一階邏輯中的重要等值式, 并能準(zhǔn)確而熟練地應(yīng)用它們n熟練正確地使用置換規(guī)則、換名規(guī)則、代替規(guī)則n熟練地求出給定公式的前束范式n深刻理解自然推理系統(tǒng)NL 的定義，牢記NL 中的各條推理規(guī)則，特別是注意使用、+、+、 4條推理規(guī)則的條件n能正確地給出有效推理的證明 72練習(xí)12 a1. 給定解釋給定解釋I如下如下:(1) 個(gè)體域個(gè)體域D=2,3

28、(2) (3)(4)求下述在求下述在I下的解釋及其真值下的解釋及其真值: x y(F(f(x) G(y,f(a)2)3(, 3)2(:)( ffxf0)3 , 3(, 1)2 , 3()3 , 2()2 , 2(:),(1)3(, 0)2(:)( GGGGyxGFFxF解解 xF(f(x)yG(y,f(a) F(f(2) F(f(3) (G(2,f(2) G(3,f(2) 1 0 (1 0)073練習(xí)2n2.求下述公式的前束范式: xF(x)y(G(x,y)H(x,y)解解 使用換名規(guī)則使用換名規(guī)則, xF(x)y(G(x,y) H(x,y) zF(z)y(G(x,y) H(x,y) 換名規(guī)則換名規(guī)則 z(F(z)y(G(x,y) H(x,y) 轄域擴(kuò)張轄域擴(kuò)張 z y(F(z)(G(x,y) H(x,y) 轄域擴(kuò)張轄域擴(kuò)張 使用代替規(guī)則使用代替規(guī)則 xF(x)y(G(x,y) H(x,y) xF(x)y(G(z,y) H(z,y) 代替規(guī)則代替規(guī)則 x(F(x)y(G(z,y) H(z,y) 轄域擴(kuò)張轄域擴(kuò)張 x y(F(x)(G(z,y) H(z,y) 轄域擴(kuò)張轄域擴(kuò)張74練習(xí)3n3.構(gòu)造下面推理的證明:(1) 前提：x(F(x)G