離散數(shù)學(xué)虞慧群1-redicatelogic

1、1,虞慧群 ,謂詞邏輯 Predicative Logic,2,謂詞與量詞 項(xiàng)與公式 公式語義 前束范式 推理理論,內(nèi)容提要,1、謂詞與量詞,概念： 謂詞，個(gè)體詞，論域，全稱量詞，存在量詞,考慮以下推理（蘇格拉底三段論）： 所有的人都會(huì)死的。 蘇格拉底是人。 蘇格拉底會(huì)死的。 直觀上是有效的論證，但命題語言表示為： p q r 不是有效推論。,命題的局限性,原因：“蘇格拉底三段論”有效性不是取決于前提、結(jié)論之間的作為簡單的命題的關(guān)系，而是依賴于命題的成分之間的聯(lián)系。有必要將命題分解得更細(xì)。,+ 量詞,命題的成分：,例: (1) 蘇格拉底是人 (2) 所有的人都會(huì)死的。 注意：邏輯中主、謂成分劃

2、分與漢語有區(qū)別。,謂詞 表示命題的謂語部分的符號(hào)或符號(hào)串 常用表示：大寫字母，A,B,C, 帶有下標(biāo)的大寫字母，A1,A2,A3, 以大寫字母為首的字符串，Human, 謂詞的元數(shù): 謂詞中包含個(gè)體的數(shù)目。 1元謂詞描述個(gè)體的性質(zhì)，2元或多元謂詞描述兩個(gè)或多個(gè)個(gè)體間的關(guān)系。 0元謂詞中無個(gè)體，理解為就是命題,6,個(gè)體詞 用于表示命題中主語部分的符號(hào)或符號(hào)串。 通常用小寫字母，或帶小標(biāo)的小寫字母表示。 個(gè)體常元 表示確指?jìng)€(gè)體。 例：Human(s)中s指蘇格拉底，是個(gè)體常元。 個(gè)體變?cè)?表示不確指?jìng)€(gè)體。 例：Human(x)中的x。 個(gè)體域(domain): 個(gè)體變?cè)娜≈捣秶?，常用D表示。,7

3、,量詞：限定個(gè)體數(shù)量特性的詞。,全稱量詞(Universal quantifier) 對(duì)所有的，for All,例： 所有的整數(shù)都有質(zhì)因子。 理解成“對(duì)所有x，若x是整數(shù)，那么x有質(zhì)因子” ( x)(I(x) P(x),xA(x)表示個(gè)體域中的任意個(gè)體x均具有性質(zhì)A。,存在量詞(Existential quantifer) ，有些，there Exist,xA(x)表示存在著個(gè)體域中的個(gè)體x具有性質(zhì)A。,例：有些豬有翅膀。 理解為“至少有一個(gè)物體x，x是豬并且x有翅膀?！?( x)(P(x) W(x),例：將下列語句符號(hào)化： （1）不是所有的鳥都能飛。 ( x)(B(x) F(x) （2）所有

4、的人都能做那件事。 ( x)(M(x) D(x) （3）有些人是笨的。 ( x)(M(x) S(x) （4）有一個(gè)整數(shù)比其它任何整數(shù)都大。 ( x)(I(x) ( y)(E(y) D(x,y) G(x,y),10,考慮例（1）“不是所有的鳥都能飛” 可理解為“至少有一只鳥不能飛”。 ( x)(B(x) F(x) ( x)(B(x) F(x) ( x) 等價(jià)于 。 即只要有一個(gè)量詞就夠了。,11,2、項(xiàng)與合式公式,概念： 項(xiàng)，原子公式，合式公式，自由變?cè)?，約束變?cè)?，轄域，換名，代入,謂詞語言：用符號(hào)串表示個(gè)體、謂詞、量詞和命題,邏輯符號(hào)：在任何情況下都作用相同的符號(hào)。,非邏輯符號(hào)：其他符號(hào)，即個(gè)

5、體常元符號(hào)、函數(shù)符號(hào)、 謂詞符號(hào)。,(1)個(gè)體常元和變?cè)琼?xiàng)； (2) 若f是n元函數(shù)符號(hào)，t1, , tn是項(xiàng)，則f(t1, , tn)是項(xiàng)； (3) 僅僅有限次使用(1)，(2)產(chǎn)生的符號(hào)串是項(xiàng)。,項(xiàng)（Term）,注：項(xiàng)將解釋成個(gè)體對(duì)象。,合式公式 (Well-Formed Formulas) 遞歸定義如下： (1) 原子公式是公式； (2) 若A是合式公式，則( A)是合式公式； (3) 若A，B是公式，則(AB)，(AB)，AB)，(AB)是公式； (4) 若A是公式，x是變?cè)?，則xA，xA是公式； (5)僅僅有限次使用得到的符號(hào)串才是合式公式。,原子公式 (Atomic formul

6、as) 若P是一個(gè)元謂詞符號(hào)，t1,tn是項(xiàng), 則P(t1,tn)是原子公式。,變?cè)募s束 設(shè)公式 的一個(gè)子公式為 x A或 x A。則稱： 指導(dǎo)變?cè)簒是或的指導(dǎo)變?cè)?轄域(Scope)：A是相應(yīng)量詞的轄域。 約束出現(xiàn)(bounded)：轄域中x的一切出現(xiàn)，以及( x)中的x稱為x在中的約束出現(xiàn)。 自由出現(xiàn)(free)：變?cè)姆羌s束出現(xiàn)。 約束變?cè)杭s束出現(xiàn)的變?cè)?自由變?cè)鹤杂沙霈F(xiàn)的變?cè)?封閉的 (Closed) 一個(gè)公式A是封閉的，若其中不含自由變?cè)?例： x y (P(x,y) Q(y,z) x P(x,y),17,變?cè)獡Q名 (Replacement) 目的是避免變?cè)募s束與自

7、由同時(shí)出現(xiàn)，引起混淆,可對(duì)約束變?cè)獡Q名。 規(guī)則：（1） 換名的范圍是量詞的指導(dǎo)變?cè)?及其相應(yīng)轄域中的變?cè)?，其余部分不變?（2） 換名時(shí)最好選用轄域中未出現(xiàn)的變?cè)?例： x (P(x) R(x,y) Q(x,y) 可換為： z (P(z) R(z,y) Q(x,y) 不能： y (P(y) R(y,y) Q(x,y) 變?cè)?Substitution) 代入對(duì)自由變?cè)M(jìn)行。不能改變約束關(guān)系。,18,3、謂詞公式語義,概念： 解釋，賦值，有效的，可滿足的，不可滿足的,解釋 (Interpretation) 謂詞語言的一個(gè)解釋 I= (D, )包括： (1) 非空集合D，稱之為論域； (2)

8、 對(duì)應(yīng)于每一個(gè)個(gè)體常元a， (a)D； (3) 對(duì)應(yīng)于每一個(gè)n元函數(shù)符號(hào)f都有一個(gè)函數(shù) (f):Dn D； (4) 對(duì)應(yīng)于每一個(gè)n元謂詞符號(hào)A都有一個(gè)n元關(guān)系(A) Dn。 注：解釋也稱為結(jié)構(gòu)，通常簡單地用 表示。,20,賦值 (Assignment) 解釋I中的賦值v為每一個(gè)個(gè)體變?cè)獂指定一個(gè)值v(x ） D，即設(shè) V為所個(gè)體變?cè)募希瑒t賦值v是函數(shù) v:V D. 若v是賦值，則v的a-equivalent 賦值記為vxa（其中a D表示一個(gè)由,定義的賦值。,注：給定解釋I和I中的賦值v后，任何項(xiàng)和公式的含義就明確了。 vI:TERM D vI:WFF 1,0,項(xiàng)的語義,項(xiàng)t在結(jié)構(gòu)I=(D

9、，)和賦值v下的值，記為vI(t),(1) 若t 是常元a，則vI(t) = (a),(2) 若t 是變?cè)獂，則vI(t) = (x),(3) 若t 是f(t1,t2,tn)，則vI(t) = (f)(vI (t1), vI ( t2), , vI ( tn) ),例、 =a, f，f(x,a)是一個(gè)項(xiàng) 解釋、 、： 1(a)=1， 1(f)=+； I1=(Z,) 2(a)=0， (f)=-； I=(Z,) 3(a)=-2， 3(f)=；I=(Z,),x的賦值v1、v2、v3 v1(x)=7、v2(x)=0、v3(x)=-5,公式的語義,公式A在結(jié)構(gòu)I=(D，)和賦值v下的值，記為vI(A),

10、2、若A為原子公式P(t1,tn) ，則,1、若A為命題常元符號(hào)p，則,4、若A為析取式(BC) ，則,5、若A為合取式(B C) ，則,3、若A為否定式(B) ，則,7、若A為等價(jià)式(B C) ，則,6、若A為蘊(yùn)含式(BC) ，則,9、若A為(xB)，則,8、若A為(xB) ，則,給出如下兩個(gè)公式：1) G=x(P(f(x)Q(x，f(a)2) H=x(P(x)Q(x，a) 給出如下的解釋I：D=2，3 a =2 f(2) f(3) 3 2 P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 2) Q(3, 3) 0 1 1 1 0 1,練習(xí),TI(G)= TI(P(f(2)Q(2

11、，f(2)(P(f(3)Q(3，f(2)= TI(P(3)Q(2，3)(P(2)Q(3，3)=(11)(00)=1 TI(H)= TI(P(2)Q(2，2)P(3)Q(3，2)=0110=0,有效公式 當(dāng)一個(gè)解釋I的所有賦值v都使公式A的真值為1，則稱A在解釋I下有效的(valid in the interpretation I);當(dāng)公式A在所有的解釋下都有效時(shí)，稱A是(邏輯)有效的(Logically valid)。 可滿足的 給定公式A，若在某一解釋中至少有一種賦值使A取值為1，則稱A為可滿足的。否則稱A是不可滿足的。 等值式 A B ：若AB是有效的。,30,A=x（P(x，y) P(x

12、，y)）不可滿足公式,A=（P(x，y) P(x，y)）有效公式,例、,A=xP(x，y)可滿足公式,幾類等值式 （1） 命題公式的推廣 e.g. P(x) Q(x) P(x) Q(x) （2）否定深入 x P(x) x( P(x) xP(x) x ( P(x),32,（3）量詞作用域的擴(kuò)張與收縮 設(shè)B中不含x的自由出現(xiàn)，則 x(A(x) B) x A(x) B x(A(x) B) x A(x) B x(A(x) B) x A(x) B x(A(x) B) x A(x) B,33,（4） x(A(x) B(x) x A(x) x B(x) x(A(x) B(x) x A(x) x B(x) （

13、5）多個(gè)量詞的使用 x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y),34,置換規(guī)則 設(shè)(A)是含A的公式, 那么, 若AB, 則(A)(B). 換名規(guī)則 設(shè)A為一公式，將A中某量詞轄域中個(gè)體變項(xiàng)的所有約束 出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)獡Q成該量詞轄域中未曾出現(xiàn)過的個(gè) 體變項(xiàng)符號(hào)，其余部分不變，設(shè)所得公式為A，則AA.,35,4、前束范式,概念： 前束范式,前束范式：如果謂詞公式A有如下形狀：Q1x1QnxnM 其中 Qixi或者是xi，或者是xi，i=1，n，M是不含量詞的公式， Q1x1Qnxn稱為首標(biāo)，M稱為母式。,對(duì)于任意謂詞公式，都存在與它邏輯等價(jià)的前束范

14、式。,例、xyz(P(x，y)Q(x，z)；xyzP(x，y，z) 均為前束范式。,步3. 將量詞符號(hào)移至公式最外層。,步1. 對(duì)約束出現(xiàn)的變?cè)M(jìn)行必要的換名，使得約束出現(xiàn) 的變?cè)ゲ幌嗤也慌c任何自由變?cè)?步2. 將所有的否定號(hào)深入到量詞后面。,x A= x A x A= x A,前束范式的算法：,x AB= x(AB ) x AB= x(AB ) x AB= x(AB ) x AB= x(AB ),x AB= x(A B ) x A B= x(A B ),A xB= x(A B ) A x B= x(A B ),x不在B中自由出現(xiàn),x不在A中自由出現(xiàn),例、,(xP(x) x y Q(

15、x,y)x yR(x,y),=(xP(x) wy Q(w,y)u vR(u,v),=(x P(x) wy Q(w,y)u vR(u,v),=x ( P(x) wy Q(w,y)u vR(u,v),換名,深入,量詞符號(hào)前移,=(x wy ( P(x) Q(w,y)u vR(u,v),= u v (x wy ( P(x) Q(w,y) R(u,v) ),= u v x w y ( P(x) Q(w,y) R(u,v) ),例、,xy(z(P(x,z)P(y,z)uQ(x,y,u),=xy(z(P(x,z)P(y,z)uQ(x,y,u),=xy(z(P(x,z)P(y,z)uQ(x,y,u),=xy

16、z(P(x,z)P(y,z)uQ(x,y,u),=xyzu(P(x,z)P(y,z)Q(x,y,u),5、謂詞邏輯推理理論,概念： 邏輯蘊(yùn)含式，有效結(jié)論，-規(guī)則（US），+規(guī)則（UG）， -規(guī)則(ES)，+規(guī)則(EG), 推理,邏輯蘊(yùn)含式 A C：當(dāng)且僅當(dāng)AC是有效的。 有效結(jié)論 設(shè)A、C是兩個(gè)謂詞公式，若A C，稱C是A的有效結(jié)論。 推廣:若H1 Hn C, 稱C是一組前題H1,Hn的有效結(jié)論。,42,43,幾類邏輯蘊(yùn)涵式,第一組 命題邏輯推理定理的代換實(shí)例 如, xF(x)yG(y) xF(x) 第二組 基本等值式生成的推理定理 如, xF(x) xF(x), xF(x) xF(x) xF

17、(x)xF(x), xF(x) xF(x) 第三組 其它常用推理定律 (1) xA(x)xB(x) x(A(x)B(x) (2) x(A(x)B(x)xA(x)xB(x) (3) x(A(x)B(x) xA(x)xB(x) (4) x(A(x)B(x) xA(x)xB(x),+規(guī)則(UG)：,- 規(guī)則(US)：,- 規(guī)則(ES)：,+ 規(guī)則(EG)：,推理規(guī)則,x A(x) A(c),45,自然推理系統(tǒng)NL,自然推理系統(tǒng)NL 定義如下: 1. 字母表. 同一階語言L 的字母表 2. 合式公式. 同L 的合式公式 3. 推理規(guī)則: (1) 前提引入規(guī)則 (2) 結(jié)論引入規(guī)則 (3) 置換規(guī)則 (4) 假言推理規(guī)則 (5) 附加規(guī)則 (6) 化簡規(guī)則 (7) 拒取式 (8) 假言三段論規(guī)則,(9) 析取三段論規(guī)則 (10) 構(gòu)造性二難推理規(guī)則 (11) 合取引入規(guī)則 (12) -規(guī)則 (13) +規(guī)則 (14) -規(guī)則 (15) +規(guī)則,推理（證明） 從前提A1, A2, Ak到結(jié)論B的推理是一個(gè)公式序列C1, C2, Cl. 其中Ci(1il)是某個(gè)Aj, 或者可由序列中前面的公式應(yīng)用推理 規(guī)則得到, 并且Cl =B。,46,例：用推理理論證明 (1) x (H(x) M(x),H(s) |- M(s) (2) x (C(x) W(x) R(x), x(C(x)