離散數(shù)學(xué)第二章一階邏輯知識點(diǎn)總結(jié)

1、數(shù)理邏輯部分第2章一階邏輯2.1 一階邏輯基本概念個體詞(個體)：所研究對象中可以獨(dú)立存在的具體或抽象的客體個體常頂：具體的事物，用a,b,c表示個體變項(xiàng)：抽象的事物，用x,y,z表示個體域：個體變項(xiàng)的取值范圍有限個體域，如9,瓦1,2無限個體域，如N,Z, R,.全總個體域：宇宙間一切事物組成謂詞：表示個體詞性質(zhì)或相互之間關(guān)系的詞謂詞常項(xiàng)：F(a)：。是人謂詞變項(xiàng)：F(x)： x具有性質(zhì)F一元謂詞：表示事物的性質(zhì)多元謂詞(元謂詞,2):表示事物之間的關(guān)系如 L(x,y)： x 與 y 有關(guān)系L(x,y)： x y,.0元謂詞：不含個體變項(xiàng)的謂詞，即命題常項(xiàng)或命題變項(xiàng)量詞：表示數(shù)量的詞全稱量詞

2、：表示任意的，所有的，一切的等如 x表示對個體域中所有的x存在量詞：表示存在，有的，至少有一個等如 X表示在個體域中存在X一階邏輯中命題符號化例1用0元謂詞將命題符號化要求：先將它們在命題邏輯中符號化，再在一階邏輯中符號化(1)墨西哥位于南美洲在命題邏輯中，設(shè)p:墨西哥位于南美洲符號化為P,這是真命題在一階邏輯中，設(shè)6墨西哥，F(xiàn)(x)： X位于南美洲符號化為F(a)(2) JI是無理數(shù)僅當(dāng)儂有理數(shù)在命題邏輯也設(shè)O儂無蹴，外博:有理教符號化為pf姓這是假命題在一階邏輯也設(shè)年)：塌無郵,G住):塌有簸符號化為F居tG(耶)如果2A3,則3(4在命題邏鏡中，設(shè)/23,依3V4符號化為2裊必應(yīng)是真命題

3、在一階邏輯中，設(shè)尸(0xy, G(x)z x例2在一階邏輯中將下面命題符號化人都愛美；(2)有人用左手寫字分別取。為人類集合，(b)D為全總個體域.解：(a)(1)設(shè)G(x)： x愛美,符號化為 xG(x)(2)設(shè)G(x)： x用左手寫字，符號化為xG(x)(b)設(shè) F(x)： x 為人,G(x)：同(a)中(1) x (F(x) G(x)(2) x (F(x) G(x)這是兩個基本公式，注意這兩個基本公式的使用.例3在一階邏輯中將下面命題符號化(1)正數(shù)都大于負(fù)數(shù)(2)有的無理數(shù)大于有的有理數(shù)解注意：題目中沒給個體域，一律用全總個體域(1)令 F(x): x 為正數(shù),G(y): y 為負(fù)數(shù),

4、L(x,y): xyx(F(x) y(G(y) L(x,y) 或X y(FM G(y) L(xfy)兩者等值(2)令F(x): x是無理數(shù),G(y): y是有理數(shù), L(x,y)： xyx(F(x) y(G(y) L(xfy)兩者等值或x y(F(x) G(y) L(x,y)幾點(diǎn)注意：1元謂詞與多元謂詞的區(qū)分無特別要求，用全總個體域量詞順序一般不能隨便顛倒否定式的使用思考：沒有不呼吸的人不是所有的人都喜歡吃糖不是所有的火車都比所有的汽車快 以上命題應(yīng)如何符號化？(3) 一階邏輯合式公式及解釋字母表定義字母表包含下述符號：(1)個體常項(xiàng):a, b, c,ai, bi, a,i 1個體變項(xiàng):x,

5、y, z,Xi, yif zhi1(3)函數(shù)符號：f, g, h, git hhi1(4)謂詞符號:F, G, H,Fh Gh Hh / 1(5)量詞符號：,(6)聯(lián)結(jié)詞符號：，(7)括號與逗號：(,)，定義項(xiàng)的定義如下:(1)個體常項(xiàng)和個體變項(xiàng)是項(xiàng).(2)若(XI, X2,Xc)是任意的元函數(shù)，tl,t2,.,tn是任意的個項(xiàng)，則(tl, t2t tn)是項(xiàng).(3)所有的項(xiàng)都是有限次使用(1),(2)得到的.個體常項(xiàng)、變項(xiàng)是項(xiàng)，由它們構(gòu)成的。元函數(shù)和復(fù) 合函數(shù)還是項(xiàng)定義設(shè)R(xi, X2,Xn)是任意的n元謂詞,tn是任意的n個項(xiàng)，則稱R(tlt t2l0)是原子公式. 原子公式是由項(xiàng)組成的

6、n元謂詞.例如,F(x,y), F(/(xi,X2),g(X3,X4)等均為原子公式定義合式公式(簡稱公式)定義如下：(1)原子公式是合式公式.(2)若八是合式公式，則(A)也是合式公式(3)若4,8是合式公式，則(A B), (A B), (A B), (A B)也是合式公式(4)若4是合式公式，則xA, xA也是合式公式(5)只有有限次地應(yīng)用(1廣形成的符號串是合 式公式.請舉出幾個合式公式的例子.定義 在公式xA和xA中，稱x為指導(dǎo)變元，4為相 應(yīng)量詞的轄域.在x和x的轄域中，x的所有出現(xiàn)都 稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱 為是自由出現(xiàn)的.例如，在公式 x(F(x,y) G

7、(x,z)中，A=(F(x,y) G(x,z)為 x 的轄域，X為指導(dǎo)變元,a中X的兩次出現(xiàn)均為約束出現(xiàn), y與z均為自由出現(xiàn).閉式：不含自由出現(xiàn)的個體變項(xiàng)的公式.給定公式 4= x(F(x) G(x)成真解釋：個體域N, F(x): x2, G(x):xl代入得4= x(x2 xl) 真命題成假解釋：個體域N, F(x): xl, G(x): x2代入得A= x(xl x2) 假命題問：xF(x) x F(x)有成真解釋嗎？ xF(x) x F(x)有成假解釋嗎？解釋定義解釋岫下面4部分組成非空個體域“。沖一些特定元素萬等(c)上一些特定函數(shù)f等馬上一些特定謂詞F等說明，被解釋的公式4中的個

8、體變項(xiàng)均取值于心若，中含個體常頂、函數(shù)T、謂詞工就分g懈程 成屋？被解釋的公式不一定全部包含解釋中的4部分.閉式在任何解釋下都是命題，注意不是閉式的公式在某些解釋下也可能是命題.永真式(邏輯有效式)：無成假賦值 矛盾式(永假式)：無成真賦值 可滿足式：至少有一個成真賦值 幾點(diǎn)說明：永真式為可滿足式，但反之不真謂詞公式的可滿足性(永真性，永假性)是不可判定的利用代換實(shí)例可判某些公式的類型定義 設(shè)4是含命題變項(xiàng)Pl, P2, ,Pn的命題公式，是個謂詞公式，用4處處代替4中的P,(1 /川，所得公式4稱為4的代換實(shí)例.例如：F(x) G(x), xF(x) yG(y)等都是 p q 的換實(shí)例， x

9、(F(x) G(x)等不是p q的代換實(shí)例.定理重言式的代換實(shí)例都是永真式，矛盾式的代 換實(shí)例都是矛盾式.例1給定解釋如下：S)個體域S) a=2 /(x,J2_=*+H f(x?v)=x1謂詞聲(4)：*=?說明下列公式在I下的涵義，并討論真值(1)jc(2x=x) 假命題(2) YxVM尸饗力ViVjG+2號f葉2=*)假命題v*，石/第)/)VjfVjSz真命題(4) 3x產(chǎn)兆力s(x力)3x(2x=xr) 真命遨(5) 3x6V*的K)口c 的Vz (y+zr)假命題兩點(diǎn)說明:(6) 、題齷閉式在邛毓領(lǐng)(7) 說明，量詞順序不能隨意改變(8) 明下面公式既不是永真式，也不是矛盾式(1)

10、 Vx(F(x) 7版)(2)本(F(x)aG(x)(3)中xVy (F住)八G(y)rH(x：s)不難對每一個公群&出一個成假解釋和一個成真 解釋，從而證明它們既不是永真式，也不是矛盾 式.2.3 一階邏輯等值式等值式定義若A B為邏輯有效式，則稱4與B是等值的，記作4 8,并稱A B為等值式.基本等值式：命題邏輯中16組基本等值式的代換實(shí)例如，xF(x) yG(y) xF(x) yG(y)(xF(x) yG(y) xF(x) yG(y)等消去量詞等值式設(shè)。=。1,。2,.,。力xA(x) A(ai) 4(72) . A(an) xA(x) A(ai) A(a2) . A(an)量詞轄域收縮

11、與擴(kuò)張等值式設(shè)/(T)是含信由故見的公式”中不含曲曲見關(guān)于領(lǐng)量詞的二Va:(x)v)cVx4Cv)vB，GW(m)a5)o/總 )aB力(5f關(guān)于存在量詞的；玉族(加3xC4(H)ABkHt*A：)AiB3je0(QtiUw今i 玉(Bf 4G)Q8f+4(量詞否定等值式設(shè)4M是含x自由出現(xiàn)的公式xA(x)x A(x)xA(x)x A(x)量詞分配等值式x(A(x) 8(x)xA(x)xB(x)x(A(x) 8(x)xA(x)xB(x)注意：對無分配律，對無分配律 例 將下面命題用兩種形式符號化(1)沒有不犯錯誤的人(2)不是所有的人都愛看電影解 令F(x)： x是人，G(x)： x犯錯誤.x

12、(F(x) G(x)x(F(x) G(x)請給出演算過程，并說明理由.(2)令F(x)： x是人，G(x)：愛看電影.x(F(x) G(x)x(F(x) G(x)給出演算過程，并說明理由.前束范式定義 設(shè)八為一個一階邏輯公式,若4具有如下形式Q1X1Q2X2QkXkB,則稱人為前束范式,其中Q,(l / k)為或，8為不含量詞的公式.例如，x y(F(x) (G(y) H(x,y)x (F(x) G(x)是前束范式，而x(F(x) y(G(y)x(F(x) G(x)不是前束范式.定理(前束范式存在定理)一階邏輯中的任何公 式都存在與之等值的前束范式注意：公式的前束范式不惟一求公式的前束范式的方

13、法：利用重要等值式、置換規(guī)則、換名規(guī)則、代替規(guī)則進(jìn)行等值演算.換名規(guī)則：將量詞轄域中出現(xiàn)的某個約束出現(xiàn)的 個體變項(xiàng)及對應(yīng)的指導(dǎo)變項(xiàng)，改成其他轄域中未 曾出現(xiàn)過的個體變項(xiàng)符號，公式中其余部分不變， 則所得公式與原來的公式等值.代替規(guī)則：對某自111出現(xiàn)的個體變項(xiàng)用與原公式 中所有個體變項(xiàng)符號不同的符號去代替，則所得公 式與原來的公式等值.例求下列公式的前束范式(1) x(M(x) F(x)解x(M(x) F(x)x( M(x) F(x)(量詞否定等值式)兩步結(jié)果都是前束范式，說明前束范式不惟一.(2)xF(x)xG(xxF(x)xG(x)xF(x)x G(x（量詞否定等值式）x(F(x)G(x)（量詞分配等值式）另有一種形式xF(x)xG(x)G(x)xF(x)xF(x)G(y)（換名規(guī)則）x y(F(x)G(y)（量詞轄域擴(kuò)張）兩種形式是等值的xF(x)xG(x)xF(x)xG(x)G(x)xF(x)x(F(x)G(x)（為什么？）x y(F(x)G(y)（為什么？）xF(x) y(G(x/y) H(y)xF(x