【正文】 2022/8/17 27 （ 11） 例：設(shè)個(gè)體域 D＝ {1,2},求公式 A＝ ? x ? yP（ x， y）在 D上的解釋?zhuān)⒅赋鲈诿恳环N解釋下公式 A的真值。 解：公式里沒(méi)有個(gè)體常量和函數(shù)，所以直接為 謂詞指派真值 ，設(shè)為 P（ 1， 1）＝ T P（ 1， 2）＝ F P（ 2， 1）＝ T P（ 2， 2）＝ F 這就是 A在 D上的一個(gè)解釋。 在此解釋下： 當(dāng) x＝ 1時(shí)有 y＝ 1使 P（ x， y）的真值為 T； 當(dāng) x＝ 2時(shí)有 y＝ 1使 P（ x， y）的真值為 T； 即對(duì)于 D中的所有 X都有 y＝ 1使 P（ x， y）的真值為 T， 所以在此解釋下公式 A的真值為 T。 2022/8/17 28 （ 12） 例：設(shè)個(gè)體域 D＝ {1,2}, 求公式 A＝ ? x P（ x） ?Q（ f(x),b） 在 D上的解釋?zhuān)⒅赋鲈诿恳环N解釋下公式 A的真值。 解： 為 個(gè)體常量 b指派 D中的值： b=1 為 函數(shù) f(x)指派 D中的值 f(1)=2,f(2)=1 對(duì) 謂詞 指派真值為： P(1)=F, P(2)=T,Q(1,1)=T, Q(2,1)=F 2022/8/17 29 （ 13） 在此解釋下， 當(dāng) x＝ 1時(shí)有： P(1)=F, Q(f(1),1)=Q(2,1)=F 所以 P（ x） ?Q（ f(x),b）為 T。 當(dāng) x＝ 2時(shí)有 P(2)=T, Q(f(2),1)=Q(1,1)=T 所以 P（ x） ?Q（ f(x),b）為 T。 即對(duì)個(gè)體域 D中的所有 x均有 P（ x） ?Q（ f(x),b），所以公式 B在此解釋下的真值為 T。 2022/8/17 30 （ 14） 定義 6：謂詞公式在個(gè)體域上的永真、永假、可滿(mǎn)足 設(shè) P為謂詞公式， D為其個(gè)體域，對(duì)于 D中的任一解釋 I： （ 1）若 P恒為真，則稱(chēng) P在 D上永真或是 D上的永真式。 （ 2）若 P恒為假，則稱(chēng) P在 D上永假或是 D上的永假式。 （ 3）若至少有一個(gè)解釋?zhuān)墒?P為真，則稱(chēng) P在 D上是 可滿(mǎn)足式 。 2022/8/17 31 （ 15） 定義 7：謂詞公式全個(gè)體域上的永真、永假、可滿(mǎn)足 設(shè) P為謂詞公式，對(duì)于任何個(gè)體域： （ 1）若 P都永真，則稱(chēng) P為永真式。 （ 2）若 P都永假，則稱(chēng) P為永假式。 （ 3）若 P都可滿(mǎn)足，則稱(chēng) P為可滿(mǎn)足式。 謂詞公式的真值與個(gè)體域及真值有關(guān)，考慮到個(gè)體域的 數(shù)目和個(gè)體域中元素?cái)?shù)目無(wú)限的情形，所以要通過(guò)算法 判斷一個(gè)謂詞公式永真是不可能的，所以稱(chēng)一階謂詞邏 輯是不可判定的。 2022/8/17 32 （ 1） ? 自然演繹推理 利用一階謂詞推理規(guī)則的符號(hào)表示形式，可以把關(guān)于自然語(yǔ)言的邏輯推理問(wèn)題，轉(zhuǎn)化為符號(hào)表達(dá)式的推演變換。這種推理十分類(lèi)似于人們用自然語(yǔ)言推理的思維過(guò)程，因而稱(chēng)為自然演繹推理。 ? 常用邏輯等價(jià)式 ? 常用邏輯蘊(yùn)含式 2022/8/17 33 常用邏輯等價(jià)式（ 1） 2022/8/17 34 常用邏輯等價(jià)式（ 2） 2022/8/17 35 常用邏輯等價(jià)式（ 3） 2022/8/17 36 常用邏輯等價(jià)式（ 4） 2022/8/17 37 常用邏輯蘊(yùn)含式（ 1) 2022/8/17 38 常用邏輯蘊(yùn)含式 (2) 2022/8/17 39 （ 2） 例 設(shè)有前提： （ 1）凡是大學(xué)生都學(xué)過(guò)計(jì)算機(jī)； （ 2）小王是大學(xué)生。 試問(wèn)：小王學(xué)過(guò)計(jì)算機(jī)嗎？ ))x(M)x(S(x)( ??1)a(S)( 2)a(M)a(S)( ?2)a(S)(3)a(M)( 4解：令 S（ x） ： x是大學(xué)生 M（ x） ： x學(xué)過(guò)計(jì)算機(jī)； a： 小王 上面命題用謂詞公式表示為： ))x(M)x(S(x)( ??1 [前提 ] [(1),US] [前提 ] [(2),(3),I3] 我們進(jìn)行形式推理： M(a)，即小王學(xué)過(guò)計(jì)算機(jī)。 ?xA(x)=A(y) y是個(gè)體域中任一確定元素 (A ? B) ? A = B 2022/8/17 40 （ 3） 例 證明 是 和 邏輯 結(jié)果。 )b,a(P? ))y,x(W)y,x(P(yx ??? )b,a(W?))y,a(W)y,a(P(y)( ??2))b,a(W)b,a(P)( ?3)b,a(P)( ?5證： ))y,x(W)y,x(P(yx)( ???1 [前提 ] [(1),US] [(2),US] )b,a(W)( ?4[前提 ] [(3),(4),I4] (A ? B) ? 172。 B = 172。 A 拒取式 2022/8/17 41 （ 4） 例 證明 ))x(P)x(R(x))x(Q)x(R(x))x(Q)x(P(x ??????????證： ))x(Q)x(P(x)( ??1 [前提 ] [(1),US] [(2),E24] [(3),(5),I6] )y(Q)y(P)( ?2)()()3( yPyQ ???)y(Q)y(R)( ??5)y(P)y(R)( ??6))x(P)x(R(x)( ???7))x(Q)x(R(x)( ???4 [前提 ] [(4),US] [(1),UG] A?B = 172。B ? 172。 A 逆反律 (A?B) ? (B?C) = A ? B 假言三段論 A(y) = ?xA(x) 全稱(chēng)推廣規(guī)則 2022/8/17 42 子句集 命題邏輯中的歸結(jié)原理 替換與合一 謂詞邏輯中的歸結(jié)原理 2022/8/17 43 (1) 定義 1：原子謂詞公式及其否定稱(chēng)為 文字 若干個(gè)文字的一個(gè)析取式稱(chēng)為一個(gè) 子句 由 r個(gè)文字組成的子句叫 r文字子句 1文字子句叫 單元子句 不含任何文字的子句稱(chēng)為 空子句 ，記為 或 NIL。 例如： 172。D(y) I(a) P ?Q ?172。R 172。I(z)?R(z) 2022/8/17 44 (2) 定義 2：對(duì)一個(gè)謂詞公式 G，通過(guò)以下步驟所得的子句集 S，稱(chēng)為 G的 子句集（ clauses） 。 例 ： ?x {? y P(x， y) ? 172。 ?y[Q(x,y) ?R(x,y)]} 由第一步可得： ?x {172。 ? y P(x， y) ? 172。?y[172。 Q(x,y) ?R(x,y)]} 消蘊(yùn)含詞和等值詞 理論根據(jù)： A?B 172。A ?B A B (172。A ?B) ?( 172。B ?A) ???蘊(yùn)含表達(dá)式 2022/8/17 45 (3) ?x {172。 ? y P(x， y) ? 172。?y[172。 Q(x,y) ?R(x,y)]} ?x {? y 172。 P(x， y) ? ? z[Q(x,z) ? 172。 R(x,z)]} 適當(dāng)改名，使變量標(biāo)準(zhǔn)化 即：對(duì)于不同的約束，對(duì)應(yīng)于不同的變量 移動(dòng)否定詞作用范圍，使其僅作用于原子公式 理論根據(jù)： 172。 (172。A) A 172。(A ?B) 172。A ?172。B 172。(A ?B) 172。A ?172。B 172。?xP(x) ?x172。P(x) 172。?xP(x) ?x172。P (x) ?????雙重否定律 摩根定律 量詞轉(zhuǎn)換定律 = ?x {? y 172。 P(x， y) ? ? y [Q(x,y) ? 172。 R(x,y)]} 2022/8/17 46 (4) 消去存在量詞 (Skolem化） ,同時(shí)進(jìn)行變?cè)鎿Q 原則：對(duì)于一個(gè)受存在量詞約束的變量，如果它 不受全稱(chēng)量詞約束 ，則該變量用一個(gè) 常量代替 （這 個(gè)常量叫 Skolem常量 ），如果它 受全稱(chēng)量詞約束 ， 則該變量用一個(gè)全稱(chēng)量詞指導(dǎo)變?cè)?函數(shù)代替 （這 個(gè)函數(shù)叫 Skolem函數(shù) ） 。 ?x {? y 172。 P(x， y) ? ? z[Q(x， z) ? 172。 R(x， z)]} = ?x {172。 P(x， f(x)) ? [Q(x， g(x)) ? 172。 R(x， g(x))]} 172。 P(x， f(x)) ? [Q(x,g(x)) ? 172。 R(x,g(x))] 消去所有全稱(chēng)量詞。 2022/8/17 47 (5) [172。 P(x， f(x)) ? Q(x,g(x))] ? [172。 P(x， f(x)) ? 172。 R(x,g(x))] [172。 P(x， f(x)) ? Q(x,g(x))] ? [172。 P(y， f(y)) ? 172。 R(y,g(y))] 適當(dāng)改名，使子句間無(wú)同名變?cè)? {172。 P(x， f(x)) ? Q(x,g(x)) , 172。 P(y， f(y)) ? 172。 R(y,g(y))} 消去合取詞，以子句為元素組成一個(gè)集合 S 化公式為合取范式 理論依據(jù)： A?（ B ? C） （ A ? B） ? （ A ?C） （ A ? B ） ? C （ A ? C） ? （ B ?C） ??172。 P(x， f(x)) ? [Q(x,g(x)) ? 172。 R(x,g(x))] 2022/8/17 48 (6) 子句集 ： 無(wú)量詞約束；（ 3， 4， 5） 元素只是文字的析?。唬?1） 否定符只作用于單個(gè)文字；（ 2） 元素間默認(rèn)為合取。（ 6， 7， 8） 化子句集的步驟： 消去蘊(yùn)含詞和等值詞。 使否定詞僅作用于原子公式。 適當(dāng)改名使量詞間不含同名指導(dǎo)變?cè)? 消去存在量詞。 消去全稱(chēng)量詞。 化公式為合取范式。 適當(dāng)改名，使子句間無(wú)同名變?cè)? 消去合取詞，以子句為元素組成一個(gè)集合 S。 2022/8/17 49 (7) 練習(xí)：用謂詞公式表示下述命題。 已知前提： （ 1）自然數(shù)都是大于零的整數(shù)。 （ 2）所有整數(shù)不是偶數(shù)就是奇數(shù)。 （ 3）偶數(shù)除以 2是整數(shù)。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 化 F1 ? F2 ? F3 ? 172。G的 子句集。 F1: ?x (N(x)?GZ(x) ? I(x)) F2: ?x (I(x)?(E(x) ?O(x))) F3: ? x (E(x) ? I(s(x))) G: ?x (N(x)?(I(s(x)) ?O(x))) 2022/8/17 50 (8) 解： F1 ? F2 ? F3 ? 172。G的子句集為 （ 1） 172。N(x) ? GZ(x) （ 2） 172。N(y) ? I(y) （ 3） 172。I(z) ? E(z) ?O(z) （ 4） 172。E(u) ? I(s(u)) （ 5） N(a) （ 6） 172。O(a) （ 7） 172。I(s(a)) 2022/8/17 51 (9) Skolem標(biāo)準(zhǔn)型 在求子句集的過(guò)程中，消去存在量詞 之后，把所有 全稱(chēng)量詞 都依次移到式子的最左邊（或者 把所有的量詞都依次移到式子最右邊，再消去存在量 詞），再將右部的式子化為合取范式，這樣得到的式 子就是 Skolem標(biāo)準(zhǔn)型。 ?x {