離散數(shù)學(xué)ch2

1、第二章 謂詞邏輯,,命題邏輯的特點(diǎn)和局限性,命題是命題演算的基本單位不再對簡單命題進(jìn)行分解無法研究命題的內(nèi)部結(jié)構(gòu)及命題之間內(nèi)在的聯(lián)系在推理方面存在局限性著名的＂蘇格拉底三段論＂凡人都是要死的.蘇格拉底是人.所以蘇格拉底是要死的.若用P,Q,R表示上述三個(gè)命題(P∧Q)?R表示上述推理,但它不是有效推理.無法判斷＂蘇格拉底三段論＂的正確性其原因在于P,Q,R沒有反映它們內(nèi)在的聯(lián)系.,需將簡單命題做進(jìn)一步的分析,分析

2、出其中的個(gè)體詞,謂詞,量詞等,研究它們的形式結(jié)構(gòu)及邏輯關(guān)系,總結(jié)出正確的推理形式和規(guī)則.這也就是謂詞邏輯(一階邏輯)所研究的內(nèi)容本章學(xué)習(xí)謂詞邏輯的基本概念謂詞邏輯合式公式及其解釋謂詞邏輯等值式謂詞邏輯推理理論,2-1謂詞的概念與表示,簡單命題分解成客體(個(gè)體詞、主詞) 和謂詞客體:可以是具體的事物,也可是抽象的概念例, 李明,黑板,自然數(shù),思想,定理等都是個(gè)體詞謂詞:用來刻劃客體的性質(zhì)或客體之間關(guān)系的詞語例:在下面

3、三個(gè)簡單命題中:3是無理數(shù).王宏是程序員.小李比小王高2厘米．客體：３, 王宏, 小李,小王謂詞: ＂…是無理數(shù)＂， ＂…是程序員＂，＂…比…高2厘米＂ ＂…是無理數(shù)＂， ＂…是程序員＂刻劃個(gè)體的性質(zhì)＂…比…高2厘米＂表示客體與客體之間的關(guān)系,與客體相關(guān)的概念,客體常元：表示具體的或特定的客體用小寫英文字母a,b,c,…表示客體變元：表示抽象的或泛指的客體用小寫英文字母x,y,z,…表示個(gè)體域(論域)：客體變元的取

4、值范圍論域可為有限集，可為無限集全總個(gè)體域,與謂詞相關(guān)的概念,謂詞常元：表示具體性質(zhì)或關(guān)系的謂詞謂詞變元：表示抽象的或泛指的謂詞用大寫的英文字母表示例:F: …比…高2厘米3比2高2厘米記作: F(3,2)謂詞填式：謂詞字母后填以個(gè)體所得的式子．常稱為謂詞.注謂詞中所含個(gè)體的數(shù)目稱為該謂詞的元數(shù)一元謂詞,二元謂詞,…n元謂詞一元謂詞刻劃個(gè)體的性質(zhì)，n元謂詞刻劃個(gè)體間的關(guān)系0元謂詞看成是命題多元謂詞個(gè)體填

5、入的順序有關(guān),2-2命題函數(shù)與量詞,簡單命題函數(shù): n元謂詞P(x1,x2,…,xn)是以個(gè)體變元x1,x2,…,xn的個(gè)體域?yàn)槎x域，以{0,1}為值域的n元函數(shù).復(fù)合命題函數(shù)謂詞與命題的關(guān)系一般P(x1,x2,…,xn)不是命題例:R(x):x是大學(xué)生.R(x)的真假與討論范圍密切相關(guān)例:(P(x,y)∧P(y,z))→P(x,z)P(x,y)解釋為:x小于yP(x,y)解釋為:x是y的兒子P(x,y)解釋為:x距

6、離y10米,量詞,有些命題除了表示個(gè)體詞和謂詞外,還有表示數(shù)量的詞,稱為量詞例:任何人都能做哪件事.有些人活百歲以上.量詞的種類:全稱量詞 用符號＂?＂對應(yīng)日常語言中＂一切＂,＂所有的＂,＂任意的＂?x表示對個(gè)體域里的所有個(gè)體存在量詞 用符號＂?＂對應(yīng)于日常語言中＂存在著＂,＂有一個(gè)＂,＂至少有一個(gè)＂?x表示存在個(gè)體域里的個(gè)體,帶量詞命題的符號化,例:(1)任何人都能做哪件事.(2)有些人活百歲以上

7、.解: D(x): x能做哪件事G(x): x活百歲以上假設(shè)個(gè)體域是人類的集合(1)符號化為?xD(x)(2)符號化為?xG(x)若個(gè)體域是全總個(gè)體域需引進(jìn)新的謂詞 M(x):x是人.(1)符號化為?x(M(x)→D(x))(2)符號化為?x(M(x)∧G(x)),使用量詞時(shí)的注意點(diǎn),在不同的個(gè)體域中,命題符號化的形式不一樣.若事先沒給出個(gè)體域,應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域.當(dāng)個(gè)體域是有限集時(shí),如D={a1,a2,…,

8、an},對任意謂詞A(x),有:?xA(x) ? A(a1)∧A(a2)∧…∧A(an)?xA(x) ? A(a1)∨A(a2)∨…∨A(an)多個(gè)量詞同時(shí)出現(xiàn)時(shí),不可隨意顛倒它們的次序.?x?yH(x,y)?y?xH(x,y)H(x,y): x+y=5,例1:將下列命題符號化,1.凡是有理數(shù)都可寫成分?jǐn)?shù)令謂詞Q(x):x是有理數(shù)F(x):x可寫成分?jǐn)?shù)則命題符號化為：(?x)(Q(x)?F(x))2.教室里有同學(xué)在講

9、話S(x):x在教室里T(x):x在講話，則符號化為：(?x)(S(x)∧T(x))3.并非每個(gè)實(shí)數(shù)都是有理數(shù).令:R(x):x是實(shí)數(shù). Q(x):x是有理數(shù).則命題可符號化為:??x(R(x)→Q(x))?x(R(x)∧?Q(x)),4.盡管有些人聰明,但不是所有人聰明.令:M(x):x是人. P(x):x聰明.則命題可符號化為:?x(M(x)∧P(x))∧??x(M(x)→P(x))5.沒

10、有一個(gè)耗子比任何象重.令H(x):x是耗子; E(x):x是象; P(x,y):x比y重.則命題可符號化為:??x(H(x)∧?y(E(y)→P(x,y)))?x?y(H(x)∧E(y)→?P(x,y))??x?y(H(x)∧H(y)∧P(x,y)),6.極限定義的符號表示.Kimx→af(x)=b?ε?δ((ε>0→δ>0)∧?x(|x-a|>0∧|x-a|<δ→|f(x)-b|&

11、lt;ε)7.每個(gè)自然數(shù)n都有后繼數(shù)n+1.令F(x):x是自然數(shù). H(x,y):y是x的后繼數(shù).則命題可符號化為：?x(F(x)→?y(F(y)∧H(x,y)))8.對于任意的x, y，都存在唯一的z，使得x+y=z .符號化為：(?x)(?y)(?z)((x+y = z)∧(?u)((u = x + y) ? (u = z)) ),2-3謂詞公式的定義,1.符號表(1)客體常元:a,b,c,…,ai,bi,

12、ci,…,i≥1;(2)客體變元:x,y,z,…,xi,yi,zi,…,i≥1;(3)函數(shù)符號:f,g,h,…,fi,gi,hi,…,i≥1;(4)謂詞符號:F,G,H,…,Fi,Gi,Hi,…,i≥1;(5)量詞符號:?, ?(6)聯(lián)結(jié)詞:?,∧,∨,→, ?(7)括號和逗號:(, ), 注:在一階邏輯中還可描述對個(gè)體所進(jìn)行的某種變換，即引入所謂函詞例如命題：?的平方是非負(fù)數(shù).a: ?, f(x)=x2, R

13、(x):x>0.符號化為:R(f(a))a: ?, R(x):x>0, P(x,y):x是y的平方. 符號化為: ?y(P(y,a)∧R(y))函詞與謂詞不同函詞作用在個(gè)體上，而產(chǎn)生另一個(gè)個(gè)體而謂詞作用在個(gè)體上之后產(chǎn)生的是一個(gè)命題,2.項(xiàng)的遞歸定義如下:(1)客體常元、客體變元是項(xiàng);(2)若f是n元函數(shù),t1,t2,…,tn是項(xiàng),則f(t1,t2,…,tn)是項(xiàng);(3)只有有限次使用(1)和(2)生成

14、的符號串才是項(xiàng).3.原子公式設(shè)R是n元謂詞, t1,t2,…,tn是項(xiàng),則R(t1,t2,…,tn)是原子公式.4.合式公式(簡稱為公式)(1)原子公式是合式公式;(2)若A是合式公式,則(?A)也是合式公式;(3)若A,B是合式公式,則(A∧B),(A∨B),(A→B),(A?B)也是合式公式;(4)若A是合式公式,則(?xA(x)), (?xA(x))也是合式公式;(5)只有有限次地使用(1)至(4)構(gòu)成的符號串是合

15、式公式.所謂一階邏輯的“一階”的含義就是指其中的量詞只能作用在個(gè)體上,給定下述謂詞,將下列公式翻譯成自然語言,P(x): x是素?cái)?shù)E(x): x是偶數(shù)Q(x): x是奇數(shù)N(x, y): x可以整除y(1) P(5)(2)(?x)(N(2, x)?E(x))(3)(?x)(?E(x) ? ?N(2, x))(4)(?x)(P(x)?(?y)(Q(y)?N(y, x))),2-4變元的約束,1.轄域 自由出現(xiàn)

16、 約束出現(xiàn)設(shè)α是公式,含有子公式?xP(x)則?x中x的稱為指導(dǎo)變元P(x)稱為量詞?x的轄域P(x)中出現(xiàn)的變元x稱為約束出現(xiàn)若x的出現(xiàn)不是約束的稱為自由出現(xiàn)例:指出下列各公式中的指導(dǎo)變元,量詞的轄域,變元的自由出現(xiàn)和約束出現(xiàn).?x(P(x)→Q(x))?x(P(x)→?yR(x,y))?x?y(P(x,y)∧Q(y,z))∧?xP(x,y)?x(P(x)∧?xQ(x,z)→?y(R(x,y))∨Q(x,y)

17、(3)中的y變元既自由出現(xiàn),又約束出現(xiàn)(4)中的x和y變元既自由出現(xiàn),又約束出現(xiàn),2.約束變元改名換名規(guī)則:將量詞轄域中某個(gè)約束出現(xiàn)的變元及相應(yīng)的指導(dǎo)變元改成轄域中末曾出出過的變元,公式中其余部分不變.?x?y(P(x,y)∧Q(y,z))∧?xP(x,y)改名為?x?t(P(x,t)∧Q(t,z))∧?xP(x,y)3.自由變元的代入替換規(guī)則:自由變元的代入用公式中未曾出現(xiàn)的變元去代入該自由出現(xiàn)的變元且處處代入.

18、?x?y(P(x,y)∧Q(y,z))∧?xP(x,y)代入后?x?y(P(x,y)∧Q(y,z))∧?xP(x,t)換名規(guī)則與替換規(guī)則均可達(dá)到將同一公式中變元調(diào)整為不會既自由出現(xiàn)又約束出現(xiàn).不同點(diǎn)是: 實(shí)施的對象不同,范圍不同,結(jié)果的形式不同,2-5謂詞演算的等價(jià)式與蘊(yùn)涵式,1.解釋(賦值)一個(gè)解釋I由下面四部分組成:(1)非空的個(gè)體域D(2)D中特異的元素(3)D上函數(shù)(4)D上謂詞當(dāng)用一個(gè)解釋去解釋一個(gè)A公式

19、時(shí),將A中的客體常元用D中的特異元素,函數(shù)符號和謂詞用D上的函數(shù)和謂詞代.,例:考察公式?x?y??z(?A(f(x,z),y)) (*),定義解釋N:DN={1,2,3,…}DN上的加法是f的解釋DN上的相等關(guān)系是A的解釋(*)的含義:對所有x,y∈DN,并非對所有z有x+z≠y．即對所有x,y∈DN,存在z有x+z=y．在此解釋下,(*)是假命題.,定義解釋I:DI是正有理數(shù)集DI上的乘法是f的解釋DI上的相

20、等關(guān)系是A的解釋(*)的含義:對所有x,y∈DN,并非對所有z有x.z≠y．即對所有x,y∈DN,存在z有x.z=y．在此解釋下,(*)是真命題.,2.永真 可滿足 等價(jià),定義2-5.1~2-5.4設(shè)A是一公式,如果A在任可解釋下都是真的,則稱A為永真的(邏輯有效的).設(shè)A是一公式,如果A在任可解釋下都是假的,則稱A為永假的(矛盾的).若存在一解釋使A為真,則稱A為可滿足的.設(shè)A,B為公式,若A?B為永真的,則

21、稱A與B是等價(jià)的.記為A?B.設(shè)A,B為公式,若A→B為永真的,則稱A蘊(yùn)涵B.記為A?B.例：(*)是可滿足的; ?xA(x)→?xA(x)永真; ?xA(x)→B???xA(x)∨B,3.常用的等價(jià)和蘊(yùn)涵式,命題公式的推廣量詞與?之間的關(guān)系量詞作用域的擴(kuò)張和收縮量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)式量詞與命題聯(lián)結(jié)詞之間的一些蘊(yùn)涵式多個(gè)量詞的使用,(1)命題公式的推廣,代換實(shí)例 設(shè)A0是含命題變元P1,P2,…,Pn

22、的命題公式, A1,A2,…,An是謂詞公式.用Ai(1≤i≤n) 處處代換Pi,所得公式A稱為A0的代換實(shí)例.命題公式中的重言式代換實(shí)例在謂詞邏輯中是邏輯有效的,仍稱為重言式.命題公式中的矛盾式代換實(shí)例在謂詞邏輯中是永假的,仍稱為矛盾式.命題演算中的等價(jià)公式表和蘊(yùn)涵公式表可推廣在謂詞演算中.,(2)量詞與?之間的關(guān)系,對于任意公式A(x):??xA(x) ??x?A(x)??xA(x) ??x?A(x)?xA(x) ??

23、?x?A(x)?xA(x) ???x?A(x),(3)量詞作用域的擴(kuò)張和收縮,對于含變元自由出現(xiàn)的公式A(x)和不含x的公式B(a) ?x(A(x)∨B) ?(?xA(x)∨B)(b) ?x(A(x)∧B) ?(?xA(x)∧B)(c) ?x(A(x)∨B) ?(?xA(x)∨B)(d) ?x(A(x)∧B) ?(?xA(x)∧B)(a) ?x(B→A(x)) ?(B→?xA(x))(b) ?x(A(x)→B) ?(?x

24、A(x)→B)(c) ?x(B→A(x)) ?(B→?xA(x))(d) ?x(A(x)→B) ?(?xA(x)→B),(4)量詞與命題聯(lián)結(jié)詞間的等價(jià)式,?x(A(x)∧B(x)) ?(?xA(x)∧?xB(x))?x(A(x)∨B(x)) ?(?xA(x)∨?xB(x))下列兩個(gè)不成立?x(A(x)∨B(x)) ?(?

25、xA(x)∨?xB(x))?x(A(x)∧B(x)) ?(?xA(x)∧?xB(x))有下列蘊(yùn)涵式?xA(x)∨?xB(x) ??x(A(x)∨B(x)) ?x(A(x)∧B(x)) ? ?xA(x)∧?xB(x),(6)多個(gè)量詞的使用,對于任意含有x,y自由出現(xiàn)的公式A(x,y)?x?yA(x,y) ??y?xA(x,y) ?x?yA(x,y) ??y?xA(x,y) ?x?yA(x,y) ??y?xA(x,y)?x

26、?yA(x,y) ??x?yA(x,y),例:判斷下列公式中哪些是邏輯有效式?哪些是矛盾式?,?xF(x)→?xF(x) 邏輯有效的?xF(x)→(?x?yG(x,y)→?xF(x)) 是P→(Q→P)的代入實(shí)例 重言式?xF(x)→(?xF(x)∨?yG(y)) 是P→(P∨Q)的代入實(shí)例 重言式?(F(x,y)→R(x,y))∧R(x,y) 是?(P→Q)∧Q的代入實(shí)例 矛盾式?x?yF(x,y

27、)→?x?yF(x,y)取解釋N:個(gè)體域?yàn)樽匀粩?shù)集,F(x,y)為N上的相等關(guān)系.取解釋N':個(gè)體域?yàn)樽匀粩?shù)集,F(x,y)為N上的小于等于關(guān)系.非邏輯有效的,非矛盾式,2-6 前束范式,前束范式 設(shè)A為一謂詞公式,如果A具有如下形式: Q1x1Q2x2…QkxkB 則稱A是前束范式. 其中每個(gè)Qi(1≤i≤k)為?或?,B為不含量詞的公式.例:求與公式P(x)→??xQ(x,y)等價(jià)的前

28、束范式．P(x)→??xQ(x,y) ?P(x)→?x?Q(x,y) ?P(x)→?z?Q(z,y) ??z(P(x)→?Q(z,y))定理2-6.1 任意一個(gè)謂詞公式,均和一個(gè)前束范式等價(jià)步1:由A找到B,使A?B,且B中?均在命題變元或謂詞前面出現(xiàn).步2:由B找到C,使B?C,且C中約束變元與自由變元不同名.步3

29、:由C找到D,使C?D,且D中量詞位于最前面.,例:求與公式??x(?yA(x,y)→?x?y(B(x,y)∧?y(A(y,x)→B(x,y))))等價(jià)的前束范式.解: ??x(?yA(x,y)→?x?y(B(x,y)∧?y(A(y,x)→B(x,y)))) ??x?(??yA(x,y)∨?x?y(B(x,y)∧?y(A(y,x)→B(x,y)))) ??x(?yA(x,y)∧??x?y(B(x,y)∧?y(A(y,x)→B(x,

30、y)))) ??x(?yA(x,y)∧?x?y (?B(x,y)∨??y(A(y,x)→B(x,y)))) ??x(?yA(x,y)∧?x?y (?B(x,y)∨?y?(A(y,x)→B(x,y)))) ??x(?zA(x,z)∧?u?y (?B(u,y)∨?y?(A(y,u)→B(u,y)))) ??x(?zA(x,z)∧?u?y (?B(u,y)∨?w?(A(w,u)→B(u,w)))) ??x?z?u?y?w (A(x,

31、z)∧ (?B(u,y)∨?(A(w,u)→B(u,w)))),注意事項(xiàng),公式的前束范式不唯一一個(gè)公式的前束范式的指導(dǎo)變元是各不相同的原公式中自由出現(xiàn)的個(gè)體變元在前束范式中還應(yīng)是自由出現(xiàn)的可進(jìn)一步對前束范式進(jìn)行約束前束合取范式前否析取范式,2-7謂詞演算的推理規(guī)則,(1)全稱指定規(guī)則 US?xP(x) ?P(y)?xP(x) ?P(c)x是P(x)中自由出現(xiàn)的個(gè)體變元y為任意的不在P(x)中約束出現(xiàn)的個(gè)體變元c為個(gè)

32、體常元.(2)全稱推廣規(guī)則 UGP(x) ??xP(x),(3)存在指定規(guī)則 ES?xP(x) ?P(c)c為某些個(gè)體常元(4)存在推廣規(guī)則 EGP(c) ??XP(x)c為某些個(gè)體常元上述四條規(guī)則加上P規(guī)則,T規(guī)則,CP規(guī)則構(gòu)成了謂詞演算的推理規(guī)則.,例1: 證明?x(H(x)→M(x))∧H(s) ?M(s)證明:?x(H(x)→M(x)) PH(s)→M(s) US (1)H(s)

33、 PM(s) T(2)(3) I,例2: 證明?x(C(x)→W(x)∧R(x))∧?x(C(x)∧Q(x)) ? ?x(Q(x)∧R(x)) 證明: ?x(C(x)∧Q(x)) PC(a)∧Q(a) ES(1)?x(C(x)→W(x)∧R(x)) PC(a)→W(a)∧R(a) US(3)C(a)

34、 T (2) IQ(a) T (2) IW(a)∧R(a) T (4)(5) IR(a) T(7) IQ(a)∧R(a) T (6)(8)?x(Q(x)∧R(x)) EG (9),例3: 證明?x(P(x)∨Q(x)) ? ?xP(x)∨?xQ(x)

35、證明: 由于有?xP(x)∨?xQ(x) ? ??xP(x)→?xQ(x) ?x(P(x)∨Q(x)) P??xP(x) P (附加前提)?x?P(x) T (2) E?P(a) ES (3) P(a)∨Q(a) US (1)?P(a)→Q(a) T (5)EQ(a)

36、 T(4)(6) I?xQ(x) EG (7)??xP(x)→?xQ(x) CP,證明　?x(P(x)∨Q(x)) ? ?xP(x)∨?xQ(x) 證明(法二):?(?xP(x)∨?xQ(x))??xP(x)∧??xQ(x)??xP(x)??xQ(x)?x?P(x)?x?Q(x)?P(a)?Q(a)?P(a)∧?Q(a)?(P(a)∨Q(a))

37、?x(P(x)∨Q(x)) P(a)∨Q(a) (?(P(a)∨Q(a))∧(P(a)∨Q(a)),例4:任何人違反交通規(guī)則，則要受到罰款，因此如果沒有罰款，則沒有人違反交通規(guī)則.解: 設(shè)S(x,y)："x違反y." M(y):"y是交通規(guī)則." P(z): "z是罰款." R(x,z):

38、"x受到z"前提H: ?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z))) 結(jié)論C:??zP(z)→?x?y(S(x,y)→?M(y))問H?C?,(1) ?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z))) P(2) ??zP(z) P(附加前提)(3) ?y(S(b,y)∧M(y))→?z(P

39、(z)∧R(b,z)) US(1) (4) ?z?P(z) T(2)(5) ?P(a) US(4)(6) ?P(a)∨?R(b,a) T(5) E(7) ?z(?P(z)∨?R(b,z))

40、 UG (6)(8) ??z(P(z)∧R(b,z)) T(7)(9) ??y(S(b,y)∧M(y)) T(3)(10) ?y?(S(b,y)∧M(y)) T(9)(11) ?(S(b,a)∧M(a)) US

41、(10)(12) S(b,a)→?M(a) T(11)(13) ?x?y(S(x,y)→?M(y)) UG (12) 兩次(14) ??zP(z)→?x?y(S(x,y)→?M(y)) CP(2)(13),第一,二章小結(jié),公式的翻譯符號庫合式公式真值表特殊的公式重言式、予盾式公式間的關(guān)系等價(jià)公式、蘊(yùn)涵公式范式(主)析