《離散數(shù)學(xué)課件》謂詞邏輯2

1、1,上節(jié)課內(nèi)容,,謂詞公式的符號化謂詞演算的合式公式自由出現(xiàn)和約束出現(xiàn)約束變元的換名規(guī)則自由變元的代入規(guī)則,2,第3講 永真性和可滿足性,謂詞公式的賦值可滿足性代換實例等價式,3/66,3.4.1 真假性,四個因素(1) 個體域(2) 自由變元(3) 謂詞變元(4) 命題變元,?xA(x) ?A(y) ?P,4/66,(1) 個體域,例 設(shè)A(e)表示e為偶數(shù)，考察 ?x

2、A(x),當(dāng)個體域I為{1,2,3}時，公式的值為假； 當(dāng)個體域I為{2,4,6}時，公式的值為真。,5/66,(2) 自由變元,例 設(shè)A(e)表示e為偶數(shù)，考察 A(y),當(dāng)y取1時，其值為F； 當(dāng)y取2時，其值為T。,6/66,(3) 謂詞變元,例 個體域I={2，4}. 考察 ?xA(x),當(dāng)A(e)表示e為偶數(shù)時，?xA(x)=T；

3、當(dāng)A(e)表示e為奇數(shù)時，?xA(x)=F；,7/66,(4) 命題變元,例 個體域I={2，4}，A(e)表示e為偶數(shù). 考察 ?xA(x)?P,當(dāng)P=T 時，公式的值為真；當(dāng)P=F 時，公式的值為假。,8/66,謂詞演算公式,設(shè)?為任何一個謂詞演算公式，其中自由變元為x1，x2，…，xn； 謂詞變元為X1，X2，…，Xm； 命題變元為P1，

4、P2，…，Pk。 此時?可表示為： ?(x1，…，xn；X1，…，Xm；P1，…，Pk),9/66,謂詞演算公式的解釋,◇ 設(shè)個體域I解釋為常個體域I0；◇ 自由變元x1，…，xn解釋為： I0中的個體a1，…，an；◇ 謂詞變元X1，…，Xm解釋為： I0上的謂詞A1，…，Am；◇ 命題變元P1，…，Pk解釋為： P10，…，Pk0，

5、 其中Pi0=T或F(i=1，2，…，k)。,10/66,成真解釋、成假解釋,給定公式?一個解釋： (I0；a1，…，an；A1，…，Am；P10，…，Pk0)公式?在該解釋下的值記為： ?(a，A，P0)= ?(a1,…,an；A1,…,Am；P10,…,Pk0)若?(a，A，P0)=T，則稱(I0；a；A；P0)為成真解釋；若?(a，A，P0)=F，則稱(I0；a；A；P0)為成假解釋。,,11/66,含有

6、量詞的謂詞演算公式,設(shè)個體域I中所有實體變元為a1，a2，…，an，則有： ?x?(x)=?(a1)??(a2)?…??(an) ?x?(x)=?(a1)??(a2)?…??(an),12/66,含有量詞的謂詞演算公式的真假性,?x?(x)為真 ? 個體域I中的每一個個體均使得?取為真?x?(x)為真 ? 個體域I中有一個個體使得?取為真,13,例１ 求(?x)（P(x)→Q

7、(x)）的真值，其中Ｐ(x)：x等于1；Ｑ(x)：x等于2；且個體域Ｅ＝{1,2}。,解：(?x)(P(x)→Q(x)) ?(P(1)→Q(1))∧(P(2)→Q(2)) ?(Ｔ→Ｆ)∧(Ｆ→Ｔ) ?Ｆ∧Ｔ ? Ｆ,代換實例(續(xù)),例2 給定解釋I 如下: (a) 個體域 D=N (b) (c) (d) 謂詞說明下列公式在 I 下的涵義,并討論真值 (

8、1) ?xF(g(x,a),x),?x(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),15,兩點說明:5個小題都是閉式,在I下全是命題(3)與(5)說明，量詞順序不能隨意改變,(5) ?x?y?zF(f(y,z),x),?x?y?z (y+z=x) 假

9、命題,(4) ?xF(f(x,x),g(x,x)),?x(2x=x2) 真命題,?x?y?z (x+y=z) 真命題,個體域 D=N； ； ；,16/66,例3(p41)已知 ?x?y((X(x，y)?Y(z))?Z(x，y)) 試求公式在解釋 (I；z；X(e1，e2)，Y(e)，Z(e1，e2))

10、 =({1，2，3}；1；e1?e2；e為偶數(shù)；e1?e2) 之下的值。,解：將解釋代入公式得： 原式 = ?x?y((x?y? 1為偶數(shù))?x?y) = ?x?y(T) =T,17/66,例3(p41)已知 ?x?y((X(x，y)?Y(z))?Z(x，y)) 試求公式在解釋 (I；z；X(e1，e2)，Y(e)，Z(e1，

11、e2)) =({1，2，3}；2；e1?e2；e為偶數(shù)；e1?e2) 之下的值。,解：將解釋代入公式得： 原式 = ?x?y((x?y? 2為偶數(shù))?x?y) = ?x?y(x?y?x?y),18/66,解(續(xù)) 原式 = ?x?y(x?y?x?y),當(dāng)x=1時, 考察?y的作用域(1?y?1?y)①當(dāng)y=1時，(1?1)?(1?1)=T?T=T②當(dāng)y=2時，(1?2

12、)?(1?2)=F?T=T ③當(dāng)y=3時，(1?3)?(1?3)=F?T=T當(dāng)x=2時，考察?y的作用域(2?y?2?y)①當(dāng)y=1時，(2?1)?(2?1)=T?F=F ②當(dāng)y=2時，(2?2)?(2?2)=T?T=T ③當(dāng)y=3時，(2?3)?(2?3)=F?T=T,19/66,解(續(xù)2) 原式 = ?x?y(x?y?x?y),當(dāng)x=3時, 考察?y的作用域(

13、3?y?3?y)①當(dāng)y=1、2時，(3?y)?(3?y)=T?F=F②當(dāng)y=3時，(3?3)?(3?3)=T?T=T,所以，得到：原式 =(T?T?T) ? (F?*?*) ? (F ?*?*) =T?F?* =F,20/66,永真、永假,定義2：給定一個謂詞演算公式?，其個體域為I，對于I中的任意一個解釋, (1)若?均取為真， 則稱公式?在I上為永真的；

14、 (2)若?均取為假， 則稱公式?在I上為永假的， 也稱為公式在I上不可滿足的。,21/66,例 討論公式類型 ?xF(x)? ?xF(x),,證明 設(shè)E為任意一個解釋，其個體域為I， 1、若對于任意的x?I,F(x)均為真, 則?xF(x)與?xF(x)都為真， 從而該公式也為真。 2、若存在x0?I, 使得F(x0)為假， 則?xF(x)為假，從而該公式為真。

15、故在解釋E下該公式為真。由于E的任意性，所以該公式是永真式。,22/66,可滿足、非永真,定義3：給定一個謂詞演算公式?，其個體域為I, (1)如果在個體域I上存在一個成真解釋, 則稱公式?在I上為可滿足公式； (2)如果在個體域I上存在一個成假解釋， 則稱公式?在I上為非永真公式。,23/66,考察 ?xF(x) ? ?xF(x)=T?,可滿足式,24/66,定理1

16、 (p42),如果I，J是個具有相同個數(shù)的個體域(個體本身可不相同)，則任意一個公式?，若在I中永真當(dāng)且僅當(dāng)其在J中永真；若在I中可滿足當(dāng)且僅當(dāng)其在J中可滿足。,注：有限域上一個公式的永真性和可滿足性依賴于個體域中個體的數(shù)目，與個體的內(nèi)容無關(guān)。,25/66,K 域,定義：把個體域{1，2，3，…，k}稱為K域， 即由k個個體組成的個體域。 當(dāng)k=1時，就稱為1域，依此類推。,定理2：如果一公式在k域上永真

17、， 則其在h(h<k)域上永真。,定理3：如果一公式在h域上可滿足， 則其在k(k>h)域上可滿足。,26/66,定理(補充) 如下公式在k域上永真： ?x(A(x)?B(x))?(?xA(x)??xB(x)),證明：在k域 I={1，2，… ，k}上，,原式= ((A(1)∧B(1))∧(A(2)∧B(2)) ∧…∧((A(k

18、)∧B(k) )) ? (((A(1)∧A(2)∧…∧A(k)) ∧(B(1)∧B(2)∧…∧B(k))) = T所以原式在k域上永真。,代換實例（補充）,定義 設(shè)A0是含命題變項p1, p2, …,pn的命題公式， A1,A2,…,An是n個謂詞公式，用Ai處處代替A0中的pi (1?i?n) ，所得公式A稱為A0的代換實例. 例如: F(x)?G(x

19、), ?xF(x)??yG(y) 等都是p?q的換實例， ?x(F(x)?G(x)) 等不是 p?q 的代換實例.,27,定理 重言式的代換實例都是永真式，矛盾式的代 換實例都是矛盾式.,28/66,例 判斷下列公式的類型:,(1) ?xF(x)→(?x?yG(x，y)→?xF(x))  (2) ?(?xF(x)→?yG(y))∧?yG(y),p→(q→p) ?(p→q)

20、∧q,重言式矛盾式,29/66,3.4.2 同真假性、等價式,定義1：設(shè)有兩公式?和?, 如果對于個體域 I 上任何解釋，公式 ?和?均取得相同的真假值， 則稱?和?在 I 上同真假。 如果?和?在每一個非空個體域上均同真假，則稱?和?同真假。,在任何解釋I和I中的任意賦值下的兩個謂詞公式Ａ和Ｂ，若對Ａ和Ｂ中的變項作同樣的賦值，所得命題的真值都相同，則稱謂詞公式Ａ和Ｂ在I上是等價的，記作：Ａ?Ｂ（A

21、=B）。,30/66,（1）關(guān)于否定的等價公式,??x?(x)= ?x??(x) ??x?(x)= ?x??(x),,例如，設(shè)P(x)表示“x今天來校上課”，則?P(x)表示“x今天沒來校上課”。那麼， 對第一個式子,“不是所有的人今天都來上課?(?x)P(x) ”與“有(存在)一些人今天沒來上課(?x)?P(x)”在意義上是相同的。 對第二個式子,“今天沒有(不存在)來上課的人?(?x)P(

22、x) ”與“所有的人今天都沒來上課(?x)?P(x)”在意義上是相同的。,31/66,設(shè)個體域I中所有實體變元為a1，a2，…，an，則有： ??x?(x)=?(?(a1)??(a2)?…??(an)) =??(a1)???(a2)?…???(an)) =?x??(x) ??x?(x)=?(?(a1)??(a2)?…??(an))

23、 =??(a1)???(a2)?…???(an)) =?x??(x),32/66,（2）量詞作用域的收縮與擴張,設(shè)公式?中不含有自由的x，則: ?x(?(x)? ?)= ?x?(x)? ? ?x(?(x)? ?)= ?x?(x)? ? ?x(?(x)? ?)= ?x?(x)? ? ?x(?(x)? ?)= ?x

24、?(x)? ?,析取式/合取式的量詞作用域中的閉式可分離出來,33/66,量詞作用域的收縮與擴張(續(xù)),設(shè)公式?中不含有自由的x，則下面的公式成立: ?x(?(x) → ?)= (? x?(x) → ?) ?x(? →?(x)) = (?→?x?(x)) ?x(?(x)→ ?)= (?x?(x) →?) ?x(?→?(x))= (?→?x?(x)),蘊含式的量詞作用域中的閉式前件可分離出來,34/66,例1 試判斷下

25、面兩公式是否等價 ?x(???(x)) 和 ???x ?(x),解： ?x(???(x)) =?x(? ? ∨ ?(x) = ? ? ∨ ?x ?(x) = ???x ?(x) 　　所以兩公式等價。,35/66,例2 (p42) 試判斷下面兩公式是否等價 ?x?(x)??

26、和 ?x(?(x)??),解： ?x?(x)?? = (??x?(x)) ? ? = (?x??(x)) ? ? = ?x(??(x)? ? ) = ?x(?(x)?? ) ? ?x(?(x)

27、??)　　所以兩公式不等價。,36/66,（3）量詞分配等值式,?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x)?B(x))??xA(x)??xB(x),注意：?對?無分配律，?對?無分配律,例如，“聯(lián)歡會上所有的人既唱歌又跳舞”和“聯(lián)歡會上所有的人唱歌且所有的人跳舞”的意義相同。例如，“聯(lián)歡會上有人唱歌或跳舞”和“聯(lián)歡會上有人唱歌，或有人跳舞”的意義相同。,37,證：(?x)(P(x)→Q(x))

28、 ?(?x)(?P(x)∨Q(x)) ?(?x)?P(x)∨(?x)Q(x) ??(?x)P(x)∨(?x)Q(x) ?(?x)P(x)→(?x)Q(x),例1 證明(?x)（P(x)→Q(x)）? (?x)P(x)→(?x)Q(x),38,證： 左式?(?x)(?y)(?P(x)∨Q(y))

29、 ?(?x)((?y)( ?P(x)∨Q(y))) ?(?x)(?P(x)∨(?y)Q(y)) ?(?x) ?P(x)∨(?y)Q(y) ?? (?x)P(x)∨(?y)Q(y) ? (?x)P(x)→(?y)Q(y),例2 證明：(?x)(?y)(P(x)→Q(y))?

30、 (?x)P(x)→(?y)Q(y),等價式與基本等價式,基本等值式:命題邏輯中16組基本等值式的代換實例如，?xF(x)??yG(y) ? ??xF(x)??yG(y) ?(?xF(x)??yG(y)) ? ??xF(x)???yG(y) 等 消去量詞等值式 設(shè)D={a1,a2,…,an} ?

31、xA(x)?A(a1)?A(a2)?…?A(an) ?xA(x)?A(a1)?A(a2)?…?A(an),39,定義 若A?B為邏輯有效式（永真），則稱A 與B是等值（等價）的， 記作 A?B，并稱A?B為等值式（等價式）.,量詞轄域收縮與擴張等值式 設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)關(guān)于全稱量詞的： ?x(A(x)?B)??xA(x)?B ?x(A(x)?

32、B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x),40,關(guān)于存在量詞的: ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x),量詞分配等值式 ?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x

33、)?B(x))??xA(x)??xB(x)注意：?對?無分配律，?對?無分配律,41,小結(jié),謂詞公式的賦值可滿足性代換實例等價式,第4講 范式（4.3）,前束范式SKOLEM標(biāo)準(zhǔn)形,42,43/66,3.4.3 范式,定義：如果一謂詞演算公式?中的一切量詞均在公式的最前面(量詞前不含否定詞)且其作用域一直延伸到公式的末端，則稱公式?為前束形公式。前束形公式的一般形式為： Q1x1Q2x2…QnxnM

34、(x1，x2，…，xn)其中，Qi為?或?，M稱為公式?的母式且其中不含有量詞。,,44/66,例如，?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))不是前束范式,45/66,定理,任意一個謂詞演算公式均有一前束范式與之等價。,

35、求前束范式的一般步驟:,,（1）消去除 ? 、∧、∨之外的聯(lián)結(jié)詞；（2）將否定符 ?移到量詞符后；（3）換名使各變元不同名；（4）擴大轄域使所有量詞處在最前面。,注：公式的前束范式不惟一,例1 求下列公式的前束范式 (1) ??x(M(x)?F(x))解 ??x(M(x)?F(x)) ? ?x(?M(x)??F(x)) （量詞否定等值式） ? ?x(M(x)??F(x))

36、 兩步結(jié)果都是前束范式，說明前束范式不惟一.,46,例(續(xù)),(2) ?xF(x)???xG(x)解 ?xF(x)???xG(x) ??xF(x)??x?G(x) （量詞否定等值式） ??x(F(x)??G(x)) （量詞分配等值式）另有一種形式 ?xF(x)???xG(x) ??xF(x)??x?G(x)

37、 ??xF(x)??y?G(y) ( 代替規(guī)則 ) ??x?y(F(x)??G(y)) ( 量詞轄域擴張 )兩種形式是等值的,47,例(續(xù)),(3) ?xF(x)???xG(x) 解 ?xF(x)???xG(x) ??xF(x)??x?G(x) ??x(F(x)??G(x)) （為什么？） 或 ??x?y(F(x)??

38、G(y)) （為什么？） ?xF(x)??x?G(x) ??xF(x)??y?G(y),48,49,(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))) （為什么？

39、）或 ??xF(x)??y(G(z,y)??H(y)) （代替規(guī)則） ??x?y(F(x)?(G(z,y)??H(y))),50,(?x)(?y)((?z)(P(x,z)∧P(y,z))→(?u)Q(x,y,u))解：原式 ?(?x)(?y)(?(?z)(P(x,z)∧P(y,z))∨(?u)Q(x,y,u)) ?(?x)(?y)((?z)?(P(x,z)∧P(y,z))∨(?u)Q(x,y,u)

40、) ?(?x)(?y)((?z)(?P(x,z)∨?P(y,z))∨(?u)Q(x,y,u)) ?(?x)(?y)(?z)(?u)(?P(x,z)∨?P(y,z)∨ Q(x,y,u)),? (?x)(?y)(?z)(?u)((P(x,z)∧P(y,z))→Q(x,y,u)),例2 將謂詞公式化為前束范式：,51,?(?x)((?y)A(x,y)→ (?x)(?y)(B(x,y)∧(?y)(A(y,x)→

41、B(x,y))))解：原式?(?x)?(?(?y)A(x,y)∨ (?x)(?y)(B(x,y)∧(?y)(A(y,x)→B(x,y) )))?(?x)((?y)A(x,y)∧ (?u)(?r)(?B(u,r)∨(?z)?(A(z,u)→B(u,z) )))?(?x)(?y)(?u)(?r)(?z) (A(x,y)∧(?B(u,r)∨?(A(z,u)

42、→B(u,z) ))),例3 將謂詞公式化為前束范式：,例(續(xù)),練習(xí) ?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))) ??x?y(F(x,u)?G(x,y)?H(x,z)))注意：?x與?y不能顛倒,52,如果給定解釋I：個

43、體域為實數(shù)集，F(xiàn)(x,y)：x＞y。 則 ? x?yF（x，y）為真， 而?y ?xF（x，y） 意為“存在著最小實數(shù)”，是假命題.,53/66,二、SKOLEM標(biāo)準(zhǔn)形,定義：僅含有全稱量詞的前束范式稱為SKOLEM標(biāo)準(zhǔn)形。,定理：任一謂詞演算公式?，均可以化成相應(yīng)的SKOLEM標(biāo)準(zhǔn)形, 且?為不可滿足的當(dāng)且僅當(dāng)其SKOLEM標(biāo)準(zhǔn)形是不可滿足的。,54/66,SKOLEM標(biāo)準(zhǔn)形的求解算

44、法,(1)先求謂詞演算公式的前束范式；(2)按如下方法消去存在量詞 ①若存在量詞?x前無全稱量詞，則引入SKOLEM常量a，代替公式中受?x約束的變元，消去存在量詞； ②若存在量詞?x前有n個全稱量詞，則引入n元SKOLEM函數(shù)f，代替公式中受?x約束的變元，消去存在量詞；(3)從左至右重復(fù)上述過程，直至公式中不含有存在量詞。,55/66,例4 (p46)求公式的SKOLEM標(biāo)準(zhǔn)形,?x(X(

45、x)?(?yY(x，y)??xZ(x))),解：①先把公式化為前束范式 原式=?x(X(x)?(??yY(x，y)??xZ(x))) =?x(X(x)?(?y?Y(x，y)??xZ(x))) =?x(X(x)?(?y?Y(x，y)??uZ(u))) =?x?y?u(X(x)?(?Y(x，y)? Z(u))) ②化為SKOLEM

46、標(biāo)準(zhǔn)形 原式=?y?u(X(a)?(?Y(a，y)? Z(u))) =?y(X(a)?(?Y(a，y)? Z(f(y)))),56,例5 求公式的SKOLEM標(biāo)準(zhǔn)形,G=?x?y?z?u?v?wP(x,y,z,u,v,w),解：用a代替x， 用f(y，z)代替u， 用g(y，z，v)代替w， 得公式G的Skolem范式：?y?z?vP(

47、a,y,z,f(y,z),v,g(y,z,v)),3.5.1 唯一性量詞,引進唯一性量詞 ?!xA(x)表示恰好有一個x使得A(x)為真,57,等價為 ?!xA(x)= ?x(A(x) ? ?y(x≠y ??A(y)),例：將下列語句符號化,58,解：1、設(shè)A(x)表示“x是人”， B(x,y)表示“x去過y”， a:他， b：北

48、京 ?!x(A(x) ? ?B(x,b) ?x=a) 2、設(shè)A(x)表示“x是星球”， B(x)表示“x是人” C(x,y)表示“x上有y”， a:地球 ?!x ?y (A(x) ? B(y) ?C(x,y) ? x=a

49、),1、他是唯一沒有去過北京的人。2、地球是唯一有人的星球。,59,解：設(shè)P(x)：x是平面上一點。L(x)：x是一條線。 E(x,y)：x等y。R(x,y,z)：z通過x和y。則本命題符號化為： (?x)(?y) (P(x)∧P(y)→(?z) (L(z)∧R(x,y,z)∧ (?u)（L(u)∧R(x,y,u)→E(u,z))))符號化為： ?x?y?!z