第3章一階邏輯教育研究

1、第第2 2章章 命題邏輯命題邏輯( (復(fù)習(xí)復(fù)習(xí)) )2.3 2.3 范式范式2.4 2.4 命題邏輯推理理論命題邏輯推理理論第第3 3章章 一階邏輯一階邏輯( (新課新課) )3.1 3.1 一階邏輯基本概念一階邏輯基本概念3.2 3.2 一階邏輯等值演算一階邏輯等值演算p范式與數(shù)字邏輯中化簡(jiǎn)邏輯函數(shù)的關(guān)聯(lián)范式與數(shù)字邏輯中化簡(jiǎn)邏輯函數(shù)的關(guān)聯(lián)p命題邏輯推理如何用計(jì)算機(jī)實(shí)現(xiàn)命題邏輯推理如何用計(jì)算機(jī)實(shí)現(xiàn)1章節(jié)課堂離散數(shù)學(xué)知識(shí)框架離散數(shù)學(xué)知識(shí)框架( (應(yīng)用型應(yīng)用型) )p邏輯：研究思維的邏輯：研究思維的規(guī)律性。規(guī)律性。p學(xué)習(xí)和工作時(shí)時(shí)處學(xué)習(xí)和工作時(shí)時(shí)處處離不開處離不開“邏輯邏輯”。p數(shù)理邏輯：研究推數(shù)

2、理邏輯：研究推理、計(jì)算等邏輯問題。理、計(jì)算等邏輯問題。p在離散數(shù)學(xué)中數(shù)理在離散數(shù)學(xué)中數(shù)理邏輯的內(nèi)容一般包括邏輯的內(nèi)容一般包括命題邏輯和一階邏輯。命題邏輯和一階邏輯。命題邏輯和一階邏輯命題邏輯和一階邏輯2章節(jié)課堂3離散數(shù)學(xué)與其他課程的關(guān)系離散數(shù)學(xué)與其他課程的關(guān)系高等高等代數(shù)代數(shù)數(shù)學(xué)數(shù)學(xué)分析分析概率概率統(tǒng)計(jì)統(tǒng)計(jì)算法設(shè)計(jì)算法設(shè)計(jì)與分析與分析算法與數(shù)算法與數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)編譯技術(shù)編譯技術(shù)網(wǎng)絡(luò)技術(shù)網(wǎng)絡(luò)技術(shù)軟件工程軟件工程人工智能人工智能p基礎(chǔ)數(shù)學(xué)的延伸基礎(chǔ)數(shù)學(xué)的延伸p算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu) 的理論基礎(chǔ)的理論基礎(chǔ)p概率統(tǒng)計(jì)、算法概率統(tǒng)計(jì)、算法 設(shè)計(jì)與分析的理設(shè)計(jì)與分析的理 論基礎(chǔ)論基礎(chǔ)p其他專業(yè)課程的

3、其他專業(yè)課程的 描述和建模工具描述和建模工具離散離散數(shù)學(xué)數(shù)學(xué)3章節(jié)課堂pqr0001000111010100111110001101001101011111主析取范式主析取范式( (由真值為由真值為1 1對(duì)應(yīng)的最小項(xiàng)析取組成對(duì)應(yīng)的最小項(xiàng)析取組成) )：m001 m011 m100 m111=( p ( p (p (p ) ), , , ,( (74313 m4章節(jié)課堂p與數(shù)字邏輯的關(guān)聯(lián)與數(shù)字邏輯的關(guān)聯(lián)-邏輯函數(shù)的邏輯函數(shù)的 “與或與或”式化簡(jiǎn)式化簡(jiǎn)cbadcacbcdbf)13,12,11,10, 8 , 5 , 3 , 2(4mbadc00110110001101100 0 1 1 1 0

4、0 0 1 1 0 0 01 1 1 cbadbabccbadbacbf數(shù)字邏輯：用二進(jìn)制為基礎(chǔ)的數(shù)字化技術(shù)解決邏輯問題數(shù)字邏輯：用二進(jìn)制為基礎(chǔ)的數(shù)字化技術(shù)解決邏輯問題5章節(jié)課堂下列命題推理如何用計(jì)算機(jī)進(jìn)行驗(yàn)證下列命題推理如何用計(jì)算機(jī)進(jìn)行驗(yàn)證前提前提: p q, qr, ps, s結(jié)論結(jié)論: r(p q) )證明證明 ： ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取則：則：推理正確，推理正確， r(pq)是有效結(jié)論是有效結(jié)論6章節(jié)課堂定理定理2.8 由

5、前提由前提a1, a2, , ak 推出推出b 的推理正確當(dāng)且僅的推理正確當(dāng)且僅當(dāng)當(dāng) a1 a2 akb 為重言式為重言式.定義定義2.9 真值表真值表: 命題公式在所有可能的賦值下的取值的列命題公式在所有可能的賦值下的取值的列表含表含n個(gè)變項(xiàng)的公式有個(gè)變項(xiàng)的公式有2n個(gè)賦值。個(gè)賦值。定義定義2.10 重言式重言式(永真式永真式): 無成假賦值的命題公式無成假賦值的命題公式定義定義2.8 設(shè)設(shè)p1, p2, , pn是出現(xiàn)在公式是出現(xiàn)在公式a中全部的命題中全部的命題變項(xiàng)變項(xiàng), 給給 p1, p2, , pn指定一組真值指定一組真值, 稱為對(duì)稱為對(duì)a的一個(gè)的一個(gè)賦值賦值或或解釋解釋.使公式為真的

6、賦值稱作使公式為真的賦值稱作成真賦值成真賦值, 使公式為假使公式為假的賦值稱作的賦值稱作成假賦值。成假賦值。p相關(guān)知識(shí)點(diǎn)相關(guān)知識(shí)點(diǎn)7章節(jié)課堂p q r sep q r se0 0 0 011 0 0 010 0 0 111 0 0 110 0 1 011 0 1 010 0 1 111 0 1 110 1 0 011 1 0 010 1 0 111 1 0 110 1 1 011 1 1 010 1 1 111 1 1 11 b)( )()()(4321qprssprqqpeaaaa p若要證明若要證明e是永真式，只需編寫程序?qū)崿F(xiàn)如下功能：是永真式，只需編寫程序?qū)崿F(xiàn)如下功能：對(duì)于變?cè)獙?duì)于變?cè)?

7、p,q,r,s的所有賦值，驗(yàn)證的所有賦值，驗(yàn)證e的取值是否均為的取值是否均為1即可。即可。8章節(jié)課堂#include stdio.hmain() int p,q,r,s,a1,a2,a3,a4,b,e;/p,q,r,s是命題變?cè)敲}變?cè)?a1,.,a4是前提，是前提，b是結(jié)論是結(jié)論,e是是a1a2 a3 a4 b int yh(int p,int q)/計(jì)算蘊(yùn)涵命題計(jì)算蘊(yùn)涵命題pq的值的值return !p|q;/應(yīng)用蘊(yùn)涵等值式：應(yīng)用蘊(yùn)涵等值式：pqp qfor(p=0;p=1;p+) /p,q,r,s四重循環(huán)實(shí)現(xiàn)所有賦值情況四重循環(huán)實(shí)現(xiàn)所有賦值情況 for (q=0;q=1;q+) for

8、(r=0;r=1;r+) for(s=0;s=1;s+) int result=1; /result作為標(biāo)志，取值為作為標(biāo)志，取值為1推理有效，取值為推理有效，取值為0推理無效推理無效 a1=p|q;a2=yh(q,r); a3=yh(p,s);a4=!s;/a1,.a4是前提是前提 b=r&(p|q);/b是結(jié)論是結(jié)論 e=yh(a1&a2&a3&a4,b) if (result=1) printf(所給推理有效所給推理有效!); else printf(所給推理無效所給推理無效!);if (e=0) /成假賦值出現(xiàn)成假賦值出現(xiàn) result=0;break;

9、 /推理無效，結(jié)束賦值結(jié)果的檢查即結(jié)束循環(huán)推理無效，結(jié)束賦值結(jié)果的檢查即結(jié)束循環(huán) b)( )()()(4321qprssprqqpeaaaa 9章節(jié)課堂一階邏輯的內(nèi)容要點(diǎn)：謂詞和個(gè)體謂詞和個(gè)體量詞量詞一階邏輯公式一階邏輯公式置換規(guī)則置換規(guī)則一階邏輯等值式一階邏輯等值式推理理論推理理論一階邏輯前束范式一階邏輯前束范式11章節(jié)課堂3.1.1 命題邏輯的局限性命題邏輯的局限性3.1.2 個(gè)體詞、謂詞與量詞個(gè)體詞、謂詞與量詞n個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、個(gè)體域、全總個(gè)體域個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、個(gè)體域、全總個(gè)體域n謂詞常項(xiàng)、謂詞變項(xiàng)謂詞常項(xiàng)、謂詞變項(xiàng)n全稱量詞、存在量詞全稱量詞、存在量詞3.1.3 一階邏輯命題符

10、號(hào)化一階邏輯命題符號(hào)化3.1.4 一階邏輯一階邏輯公式與分類公式與分類3.1 3.1 一階邏輯基本概念一階邏輯基本概念(*)(* #)(*)12章節(jié)課堂3.1.1 3.1.1 命題邏輯的局限性命題邏輯的局限性考慮下述數(shù)學(xué)中公認(rèn)的正確推理考慮下述數(shù)學(xué)中公認(rèn)的正確推理:凡偶數(shù)都能被凡偶數(shù)都能被2整除整除, 6是偶數(shù)是偶數(shù), 所以所以6能被能被2整除整除.令令 p: 凡偶數(shù)都能被凡偶數(shù)都能被2整除，整除， q: 6是偶數(shù)是偶數(shù) r: 6能被能被2整除整除命題的符號(hào)化：命題的符號(hào)化：p q r 根據(jù)定理根據(jù)定理2.8 p q r 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (p q) r是永真式是永真式因?yàn)橐驗(yàn)?p q) r不

11、是永真式不是永真式所以不能得出所以不能得出p q r推理是有效的。推理是有效的。13章節(jié)課堂。14章節(jié)課堂 15章節(jié)課堂例如例如 “若若x是偶數(shù)是偶數(shù), 則則x能被能被2整除整除.” p個(gè)體常項(xiàng)：個(gè)體常項(xiàng)：p個(gè)體變項(xiàng)：個(gè)體變項(xiàng)：p個(gè)體詞：個(gè)體詞：p個(gè)體域：個(gè)體域：3.1.2 3.1.2 個(gè)體詞與個(gè)體域個(gè)體詞與個(gè)體域1 1、個(gè)體詞、個(gè)體詞p個(gè)體詞個(gè)體詞: :所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體p個(gè)體常項(xiàng)個(gè)體常項(xiàng): : 表示具體事物的個(gè)體詞表示具體事物的個(gè)體詞, , 用用a a, , b b, , c c等表示等表示p個(gè)體變項(xiàng)個(gè)體變項(xiàng): : 表示抽象

12、事物的個(gè)體詞表示抽象事物的個(gè)體詞, , 用用x x, , y y, , z z等表示等表示p個(gè)體域個(gè)體域: : 個(gè)體變項(xiàng)的取值范圍個(gè)體變項(xiàng)的取值范圍p : :宇宙間一切事物宇宙間一切事物x x、偶數(shù)和、偶數(shù)和2 2x可以是自然數(shù)集可以是自然數(shù)集n, n, , ,也可以是全總個(gè)體域也可以是全總個(gè)體域偶數(shù)和偶數(shù)和2 2全總個(gè)體域全總個(gè)體域16章節(jié)課堂2 2、謂詞、謂詞p謂詞謂詞: : 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞，謂詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞，謂詞用用f,g,h,pf,g,h,p等表示等表示n謂詞常項(xiàng)謂詞常項(xiàng): : 表示表示具體具體性質(zhì)或相互之間關(guān)系的謂詞性質(zhì)或相互之間關(guān)系的謂詞n謂詞

13、變項(xiàng)謂詞變項(xiàng): : 表示表示抽象抽象性質(zhì)或相互之間關(guān)系的謂詞性質(zhì)或相互之間關(guān)系的謂詞pn n元謂詞元謂詞p p( (x x1 1, , x x2 2, , , x xn n) ): : 含含n n個(gè)命題變項(xiàng)的謂詞個(gè)命題變項(xiàng)的謂詞p0 0元謂詞元謂詞: :p一元謂詞一元謂詞: :p多元謂詞多元謂詞( (n n 2)2): :是定義在個(gè)體域上是定義在個(gè)體域上, , 值域?yàn)橹涤驗(yàn)?,10,1的的n n元函數(shù)元函數(shù)不含個(gè)體變項(xiàng)的謂詞不含個(gè)體變項(xiàng)的謂詞表示事物的性質(zhì)表示事物的性質(zhì)表示事物之間的關(guān)系表示事物之間的關(guān)系17章節(jié)課堂p實(shí)例實(shí)例(1) 4是偶數(shù)是偶數(shù) 4是個(gè)體常項(xiàng)是個(gè)體常項(xiàng), f: 是偶數(shù)是偶數(shù)

14、 符號(hào)化為符號(hào)化為: f(4)(2) x是合數(shù)是合數(shù) x是個(gè)體變項(xiàng)是個(gè)體變項(xiàng), g: 是合數(shù)是合數(shù) 符號(hào)化為符號(hào)化為: g(x)(3) x y x,y是個(gè)體變項(xiàng)是個(gè)體變項(xiàng),h: 10, g(x): x0 -假命題假命題-真命題真命題33章節(jié)課堂p實(shí)例實(shí)例例例 給定解釋給定解釋i i 如下如下: : (a) 個(gè)體域個(gè)體域 d=n (b) (c) (d) 謂詞謂詞說明下列公式在說明下列公式在 i 下的含義下的含義, 并討論其真值并討論其真值 2 axyyxgyxyxf ),(,),(yxyxf :),( 在在i下，公式解釋為：下，公式解釋為： x(2x=x)(2) x y(f(f(x,a),y)f

15、(f(y,a),x) x y(x+2=yy+2=x) (1) xf(g(x,a),x)-假命題假命題-假命題假命題34章節(jié)課堂p閉式的性質(zhì)閉式的性質(zhì)定理定理3.1 閉式在任何解釋下都變成命題閉式在任何解釋下都變成命題. ( (閉式閉式: : 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式) ) (1) xf(g(x,a),x) -閉式閉式(2) x y(f(f(x,a),y)f(f(y,a),x) - -閉式閉式(3) x y zf(f(x,y),z) -閉式閉式(5) f(f(x,a), g(x,a) -不是閉式，不是命題不是閉式，不是命題(6) x (f(x,y)f(f(x,a)

16、, f(y,a) -不是閉式不是閉式,是命題是命題(4) xf(f(x,x),g(x,x) -閉式閉式xyyxgyxyxf ),(,),(yxyxf :),(35章節(jié)課堂p一階邏輯公式的分類一階邏輯公式的分類設(shè)設(shè)a是一個(gè)謂詞公式，若是一個(gè)謂詞公式，若a在在 下下均為真，則稱均為真，則稱a為永真式為永真式(有效式有效式)。若。若a在任何解在任何解釋下均為假，則稱釋下均為假，則稱a為永假式為永假式(矛盾式矛盾式)。若至少存。若至少存在一個(gè)解釋使在一個(gè)解釋使a為真，則稱為真，則稱a是可滿足式。是可滿足式。p在一階邏輯中在一階邏輯中, , 公式的可滿足性公式的可滿足性( (永真性永真性, ,永假性永假

17、性) )是是 的的, ,即不存在算法能在有限步內(nèi)判斷即不存在算法能在有限步內(nèi)判斷任給的公式是否是可滿足式任給的公式是否是可滿足式( (永真式永真式, ,矛盾式矛盾式) )任何解釋任何解釋不可判定不可判定36章節(jié)課堂p代換實(shí)例代換實(shí)例定義定義3.9 設(shè)設(shè)a0是含命題變項(xiàng)是含命題變項(xiàng)p1, p2, ,pn的命題公式的命題公式, a1,a2,an是是n個(gè)謂詞公式個(gè)謂詞公式, 用用ai處處代替處處代替a0中中的的pi(1 i n), 所得公式所得公式a稱為稱為a0的的代換實(shí)例代換實(shí)例.例例: 命題公式命題公式a0：a1 : a2 :a1 ： a2：a: 是是 的代換實(shí)例的代換實(shí)例pq xf(x) yg

18、(y)代替代替p代替代替qpq xf(x)yg(y)定理定理3.2 永真式的代換實(shí)例都是永真式，永真式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式矛盾式的代換實(shí)例都是矛盾式. 37章節(jié)課堂p實(shí)例實(shí)例例例 判斷下列公式的類型判斷下列公式的類型:(1) x(f(x)g(x) -非永真式的可滿足式非永真式的可滿足式(2) ( xf(x) ( xf(x) -永真式永真式這是這是 p p 的代換實(shí)例的代換實(shí)例, p p是永真式是永真式, 取解釋取解釋i1, d1=r, :x是整數(shù)是整數(shù), :x是有理數(shù)是有理數(shù), 真命題真命題)(xf)(xg(3) ( xf(x)yg(y) yg(y) -矛盾式矛盾式

19、這是這是 (pq) q的代換實(shí)例的代換實(shí)例, (pq) q是矛盾式是矛盾式取解釋取解釋i2, d2=r, :x是整數(shù)是整數(shù), :x是自然數(shù)是自然數(shù), 假命題假命題)(xf)(xg38章節(jié)課堂3.2 3.2 一階邏輯等值演算一階邏輯等值演算3.2.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則n基本等值式基本等值式n置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則、換名規(guī)則、代替規(guī)則3.2.2 一階邏輯前束范式一階邏輯前束范式39章節(jié)課堂3.2.1 3.2.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則定義定義3.10 若若ab是永真式是永真式, 則稱則稱a與與b是是等值等值的的, 記作記作ab

20、, 并稱并稱ab為為等值式等值式基本等值式：基本等值式：p命題邏輯中基本等值式的代換實(shí)例命題邏輯中基本等值式的代換實(shí)例如如: xf(x)yg(y) 蘊(yùn)涵等值式蘊(yùn)涵等值式 aba bxf(x)yg(y)p消去量詞等值式消去量詞等值式 設(shè)設(shè)d=a1,a2,an xa(x)a(a1) a(a2) a(an) xa(x)a(a1) a(a2) a(an)40章節(jié)課堂p基本等值式基本等值式( (續(xù)續(xù)) )量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 設(shè)設(shè)a(x)是含是含x自由出現(xiàn)的公式，自由出現(xiàn)的公式，b中不含中不含x的出現(xiàn)的出現(xiàn)關(guān)于全稱量詞的：關(guān)于全稱量詞的： x(a(x) b)xa(x) b x

21、(a(x) b)xa(x) b x(ba(x)bxa(x) 在公式在公式 xa和和 xa中中, 稱稱x為指導(dǎo)變?cè)獮橹笇?dǎo)變?cè)? a為相應(yīng)量詞的轄域?yàn)橄鄳?yīng)量詞的轄域 x(a(x)b)xa(x)b41章節(jié)課堂設(shè)個(gè)體域設(shè)個(gè)體域d=1,2，則：，則： x(a(x)b) (a(1)b) (a(2)b)( a(1) b ) ( a(2) b)(a(1)b) (a(2)b)( a(1) a(2) b (a(1) a(2) b(a(1) a(2)b xa(x)bp 如何理解如何理解 x(a(x)b)xa(x)b42章節(jié)課堂p基本等值式基本等值式( (續(xù)續(xù)) )量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 設(shè)

22、設(shè)a(x)是含是含x自由出現(xiàn)的公式，自由出現(xiàn)的公式，b中不含中不含x的出現(xiàn)的出現(xiàn)關(guān)于存在量詞的關(guān)于存在量詞的: x(a(x) b)xa(x) b x(a(x) b)xa(x) b x(ba(x)bxa(x) x(a(x)b)xa(x)b43章節(jié)課堂p基本等值式基本等值式( (續(xù)續(xù)) )量詞否定等值式量詞否定等值式設(shè)設(shè)a(x)是含是含x自由出現(xiàn)的公式自由出現(xiàn)的公式 xa(x) x a(x) xa(x) x a(x)量詞分配等值式量詞分配等值式 x(a(x) b(x)xa(x)xb(x) x(a(x) b(x)xa(x)xb(x)注意：注意： 對(duì)對(duì) 無分配律，無分配律， 對(duì)對(duì) 無分配律無分配律 4

23、4章節(jié)課堂p 對(duì)對(duì) 無分配律，無分配律， 對(duì)對(duì) 無分配律無分配律 x(a(x) b(x)xa(x) xb(x)例：例：a(x)： b(x)： d：n x(a(x) b(x)xa(x) xb(x)例：例：a(x)： b(x)： d：n xa(x)xb(x) x(a(x) b(x) x(a(x) b(x) xa(x) xb(x)x是奇數(shù)是奇數(shù)x是偶數(shù)是偶數(shù)左邊左邊=1 右邊右邊=0左邊左邊=0 右邊右邊=1x是素?cái)?shù)是素?cái)?shù)x是合數(shù)是合數(shù)45章節(jié)課堂p等值演算的等值演算的3條規(guī)則條規(guī)則置換規(guī)則置換規(guī)則 設(shè)設(shè) (a)是含公式是含公式a的公式的公式, (b)是用公式是用公式b取代取代 (a)中的所有中的所

24、有a得到得到的公式的公式, 若若ab則則 (a) (b) 例：例： 設(shè)設(shè) (a): xa(x) ( xa(x) 因?yàn)橐驗(yàn)?xa(x) x a(x) 所以所以 ( xa(x) ( x a(x)46章節(jié)課堂p等值演算的等值演算的3條規(guī)則條規(guī)則換名規(guī)則換名規(guī)則 將公式將公式a中某量詞的指導(dǎo)變?cè)爸心沉吭~的指導(dǎo)變?cè)捌湓谳犛騼?nèi)的所有約束出現(xiàn)改成該量詞轄域其在轄域內(nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng)內(nèi)未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng), 其余部分不變其余部分不變, 記所得公式為記所得公式為a , 則則aa .例：例： uf(u,y,z) yg(x,y,z) uf(u,y,z) vg(x,v,z)

25、說明：說明： yg(x,y,z)中的約束變項(xiàng)中的約束變項(xiàng)y換名為換名為v47章節(jié)課堂p等值演算的等值演算的3條規(guī)則條規(guī)則代替規(guī)則代替規(guī)則 將公式將公式a中某個(gè)自由出現(xiàn)的個(gè)體中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有自由出現(xiàn)改成變項(xiàng)的所有自由出現(xiàn)改成a中未曾出現(xiàn)的某中未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng)個(gè)個(gè)體變項(xiàng), 其余部分不變其余部分不變, 記所得公式為記所得公式為a , 則則aa。例：例： xf(x,u,z) yg(x,y,z) xf(x,u,z) yg(v,y,z) 說明：說明：g(x,y,z) 中的自由變項(xiàng)中的自由變項(xiàng)x用用v代替代替48章節(jié)課堂p實(shí)例實(shí)例例例 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)消去公式中

26、既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)(1) xf(x,y,z) yg(x,y,z) uf(u,y,z) yg(x,y,z) 換名規(guī)則換名規(guī)則 uf(u,y,z) vg(x,v,z) 換名規(guī)則換名規(guī)則或者或者 xf(x,u,z) yg(x,y,z) 代替規(guī)則代替規(guī)則 xf(x,u,z) yg(v,y,z) 代替規(guī)則代替規(guī)則(2) x(f(x,y) yg(x,y,z) x(f(x,y) tg(x,t,z) 換名規(guī)則換名規(guī)則或者或者 x(f(x,t) yg(x,y,z) 代替規(guī)則代替規(guī)則49章節(jié)課堂p實(shí)例實(shí)例例例 設(shè)個(gè)體域設(shè)個(gè)體域d=a,b,c, 消去下面公式中的量詞消去下面公式中的量詞:(1) x(f

27、(x)g(x) (f(a)g(a) (f(b)g(b) (f(c)g(c)(2) x(f(x)yg(y) xf(x)yg(y) 量詞轄域收縮量詞轄域收縮(f(a) f(b) f(c) (g(a) g(b) g(c) x(f(x,a) f(x,b) f(x,c)(3) x yf(x,y) (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)50章節(jié)課堂p實(shí)例實(shí)例解解 (f(f(2) g(2, f(2) (f(f(3) g(3, f(3)例例 給定解釋給定解釋i: (a) d=2,3, (b) (c) :x是奇數(shù)是奇數(shù),

28、 : x=2 y=2, : x=y.在在i下求下列各式的真值下求下列各式的真值:(1) x(f(f(x) g(x, f(x) , 2)3(, 3)2(:fff),(yxg),(yxl)(xf(2) x yl(x,y) (1 1) (0 1) 1解解 yl(2,y) yl(3,y) (l(2,2) l(2,3) (l(3,2) l(3,3) (1 0) (0 1) 051章節(jié)課堂p實(shí)例實(shí)例例例 證明下列等值式證明下列等值式: x(m(x) f(x) x(m(x) f(x)證證: x(m(x) f(x) x( m(x)f(x) 蘊(yùn)涵等值式蘊(yùn)涵等值式 x(m(x) f(x) x (m(x) f(x)

29、 量詞否定等值式量詞否定等值式52章節(jié)課堂3.2.2 3.2.2 一階邏輯前束范式一階邏輯前束范式定義定義3.11 設(shè)設(shè)a為一個(gè)一階邏輯公式為一個(gè)一階邏輯公式, 若若a具有如下具有如下形式形式 q1x1q2x2qkxk b，則稱則稱a為為前束范式前束范式, 其中其中qi 為為 或或 , 1 i k, b為不含量詞的公式為不含量詞的公式.例：例： x y(f(x)(g(y) h(x,y) x (f(x) g(x) x(f(x)y(g(y) h(x,y)x(f(x) g(x)-前束范式前束范式-非前束范式非前束范式53章節(jié)課堂p公式的前束范式公式的前束范式定理定理3.3(前束范式存在定理前束范式存

30、在定理) ) 一階邏輯中的任何公一階邏輯中的任何公式都存在與之等值的前束范式式都存在與之等值的前束范式例例 求公式的前束范式求公式的前束范式(1) xf(x)xg(x)解解1 xf(x) x g(x) 量詞否定等值式量詞否定等值式 x(f(x)g(x) 量詞分配等值式量詞分配等值式解解2 xf(x)yg(y) 換名規(guī)則換名規(guī)則 xf(x) y g(y) 量詞否定等值式量詞否定等值式 x(f(x) y g(y) 量詞轄域擴(kuò)張量詞轄域擴(kuò)張 x y(f(x)g(y) 量詞轄域擴(kuò)張量詞轄域擴(kuò)張54章節(jié)課堂 x(f(x)g(x) x y(f(x)g(y) )2()2() 1 () 1 ()2()2()1

31、 ()2()2() 1 ()1 () 1 ()2()()1 ()()()()2()2() 1 () 1 ()2()2()1 () 1 ()()(gfgfgfgfgfgfgxfgxfxygxfyxgfgfgfgfxgxfxd=1,2？55章節(jié)課堂56章節(jié)課堂(1)us規(guī)則規(guī)則(全稱量詞消去規(guī)則全稱量詞消去規(guī)則) 要求：要求： y不在不在a(x)中以約束變?cè)男问匠霈F(xiàn)。中以約束變?cè)男问匠霈F(xiàn)。(2)es規(guī)則規(guī)則(存在量詞消去規(guī)則存在量詞消去規(guī)則) 要求要求:（1）a是使是使a(x)為真的特定的個(gè)體常元為真的特定的個(gè)體常元.（2）個(gè)體常元）個(gè)體常元a不在不在a(x)和已經(jīng)推導(dǎo)出的公式出和已經(jīng)推導(dǎo)出的

32、公式出現(xiàn)，除現(xiàn)，除x外，外，a(x)中無其他自由變?cè)?。中無其他自由變?cè)?xa(x)a(a)或或 xa(x)a(y) xa(x)a(a)57章節(jié)課堂要求要求:（1）個(gè)體變?cè)”檎麄€(gè)個(gè)體域時(shí)，）個(gè)體變?cè)”檎麄€(gè)個(gè)體域時(shí)，a(y)均為真均為真（2）x不在不在a(y)中以約束變?cè)男问匠霈F(xiàn)。中以約束變?cè)男问匠霈F(xiàn)。要求要求:（1）x不在不在a(y)中以約束變?cè)男问匠霈F(xiàn)中以約束變?cè)男问匠霈F(xiàn)（2）x不在不在a(a)中以約束變?cè)男问匠霈F(xiàn)中以約束變?cè)男问匠霈F(xiàn)58章節(jié)課堂59章節(jié)課堂 60章節(jié)課堂pp p、e e、t t規(guī)則規(guī)則61章節(jié)課堂(1)us (2)p (1)p規(guī)則規(guī)則規(guī)則規(guī)則誤：誤：分析下面

33、推導(dǎo)過程的錯(cuò)分析下面推導(dǎo)過程的錯(cuò)，例：設(shè)個(gè)體域是實(shí)數(shù)集例：設(shè)個(gè)體域是實(shí)數(shù)集) ), ,( () ), ,( (, ,: :) ), ,( (yyypyxypxyxyx 162章節(jié)課堂(2)(4)t (5)(3)es (4)p (3)(1)es (2)p (1)q(p規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則誤：誤：分析下面推導(dǎo)過程的錯(cuò)分析下面推導(dǎo)過程的錯(cuò)是負(fù)數(shù)，是負(fù)數(shù)，是正數(shù)，是正數(shù)，例：設(shè)個(gè)體域是實(shí)數(shù)集例：設(shè)個(gè)體域是實(shí)數(shù)集) )( () )( () )( () )( () )( () )( (: :) ): :) )( (aqapaqxxqapxxpxxxx 63章節(jié)課堂(1)ug x(2)p

34、 (1)p規(guī)則規(guī)則規(guī)則規(guī)則誤：誤：分析下面推導(dǎo)過程的錯(cuò)分析下面推導(dǎo)過程的錯(cuò)，例：設(shè)個(gè)體域是實(shí)數(shù)集例：設(shè)個(gè)體域是實(shí)數(shù)集) ), ,( () ), ,( (, ,: :) ), ,( (xxxpyxxpyxyx 64章節(jié)課堂假命題假命題，都有，都有對(duì)于任何實(shí)數(shù)對(duì)于任何實(shí)數(shù)規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則規(guī)則誤：誤：分析下面推導(dǎo)過程的錯(cuò)分析下面推導(dǎo)過程的錯(cuò)，例：設(shè)個(gè)體域是實(shí)數(shù)集例：設(shè)個(gè)體域是實(shí)數(shù)集 (3)e (4)eg (3)(1)es (2)p (1)p0202 xxxxxpxxxpxxxpxaxxpyxxpyyxyx: :) ), ,( () ), ,( () )( () ), ,( () ), ,

35、( () ), ,( (: :) ), ,( (65章節(jié)課堂r(x)x(q(x)y)s(x,r(y)y(p(x)xy),s(x,y(q(y)x(p(x)yx:y)s(x, q 推理可表示為：相信是騙子，是教師是學(xué)生，體域，解：設(shè)個(gè)體域是全總個(gè)以教師都不是騙子?！睂W(xué)生都不相信騙子，所所有的老師，任何一個(gè)確性：“有些學(xué)生相信例：證明下列診斷的正xxrxxxxp:)(:)(:)(66章節(jié)課堂 p y)s(x,r(y)y(p(x)x(6)(4)us x)s(a,(5)q(x)(2)t y)s(a,y(q(y)(4)(2)t (3)p(a)(1)es y)s(a,y(q(y)(2)p(a)p y)s(x,y(q(y)x(p(x)(1)r(x)x(q(x)y)s(x,r(y)y(p(x)xy),s(x,y(q(y)x(p(x)規(guī)規(guī)則則規(guī)規(guī)則則：規(guī)規(guī)則則：規(guī)規(guī)則則：規(guī)規(guī)則