離散數(shù)學(xué)之謂詞邏輯.ppt

1、2.1謂詞的概念與表示,命題邏輯的局限性： 下列推理：凡是人都是要死的。 蘇格拉底是人。 蘇格拉底是要死的。 眾所周知，這是真命題。但在命題邏輯中 ( P Q ) R ，難證其為重言式。,原因：命題邏輯不考慮命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。 辦法：將命題再次細分。,2.1謂詞的概念與表示,謂詞在反映判斷的句子中，用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞。 例：(1)3是有理數(shù)。(2)x是無理數(shù)。 (3)阿杜與阿寺同歲。 (4)x與y有關(guān)系L。 其中，“是有理數(shù)”、“是無理數(shù)”、“與同歲”、“與有關(guān)系L”均為謂詞。前兩個是指明客體性質(zhì)的謂詞，后兩個是指明兩個客體之間關(guān)系的謂詞。,2.1謂詞的概念與表示,

2、將上述謂詞分別記作大寫字母F、G、H、L，用小寫字母表示客體名稱，則上述可表示為： (1)F(3)(2)G(x) (3)H(a,b)a:阿杜b:阿寺 (4)L(x,y) 謂詞填式單獨一個謂詞不是完整的命題，把謂詞字母后填以客體所得的式子稱為謂詞填式。,2.1謂詞的概念與表示,n元謂詞由n個客體插入到固定位置上的謂詞填式。 例如：A(b)稱作一元謂詞，B(a, b)稱作二元謂詞，L(a, b, c)稱作三元謂詞，P(x1 , x2 , , xn)稱作n元謂詞。 注意：代表客體名稱的字母，它在多元謂詞中出現(xiàn)的次序是固定的，與事先約定的次序有關(guān)，如L(a, b, c)和L(b, c, a)代表兩個不

3、同的命題。,2.2命題函數(shù)與量詞,例：H是謂詞“能夠到達山頂”，t表示老虎，c表示汽車，z表示張三，那么H(t), H(c), H(z)表示三個不同的命題，但它們有一個共同的形式H(x)，當(dāng)x分別取t, c, z 時。 L(x, y)表示“x小于y”，那么L(2, 3)表示了一個真命題“2小于3”，而L(5, 1)表示假命題“5小于1”?？梢钥闯?，L(x, y)本身不是一個命題，只有當(dāng)變元x, y取特定的客體時，才是一個命題。,2.2命題函數(shù)與量詞,簡單命題函數(shù)由一個謂詞，一些客體變元組成的表達式稱為簡單命題函數(shù)。 n元謂詞就是有n個客體變元的命題函數(shù)。 不帶任何客體變元的謂詞稱為0元謂詞。

4、復(fù)合命題函數(shù)由一個或n個簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達式稱復(fù)合命題函數(shù)。,2.2命題函數(shù)與量詞,命題函數(shù)不是一個命題，只有客體變元取特定名稱時，才能成為一個命題。 但客體變元在哪些范圍內(nèi)取特定的值，對是否成為命題及命題的真值極有影響。 例：R(x)表示“x是大學(xué)生”，如果x的討論范圍是某大學(xué)里班級中的學(xué)生，則R(x)是永真式。如果x的討論范圍是某中學(xué)里班級中的學(xué)生，則R(x)是永假式。如果x的討論范圍為一劇場中的觀眾，那么對某些觀眾，R(x)為真，對另一些觀眾，R(x)為假。,2.2命題函數(shù)與量詞,個體可以獨立存在的具體的或抽象的客體。 個體常量：具體的或特定的，一般用a,b,c,表

5、示。 個體變元：抽象的或泛指的，一般用x,y,z,表示。 個體域個體變元的論述范圍。 全總個體域把各種個體域綜合在一起作為論述范圍的域。,2.2命題函數(shù)與量詞,量詞用來表示個體常量或變元之間數(shù)量關(guān)系的詞。量詞分為兩種： 全稱量詞表示“一切”,“所有”,“凡”,“每一個”,“任意”等意的詞稱為全稱量詞，記作。 如：x 表示個體域內(nèi)所有的x。 存在量詞表示“某個”,“對于一些”,“存在一些”,“至少有一個”等意的詞稱為存在量詞，記作。 如：y 表示個體域內(nèi)存在一些y。,2.2命題函數(shù)與量詞,例：用謂詞表達式寫出下列命題。 (1)凡是人都呼吸。 (2)有的人是左撇子。 解：令F(x)：x 呼吸。G(

6、x)：x 是左撇子。 當(dāng)個體域為人類集合時： (1) xF(x) (2)xG(x) 當(dāng)個體域為全總個體域時： 令M(x)：x 是人。 (1) x(M(x) F(x) (2) x(M(x)G(x),2.2命題函數(shù)與量詞,約定：以后如不指定個體域，默認(rèn)為全總個體域。 特性謂詞在討論帶有量詞的命題函數(shù)時，必須確定其個體域。當(dāng)使用全總個體域時，對客體變元的變化范圍限制的詞，稱作特性謂詞。 如上例中，M(x)為F(x)和G(x)的特性謂詞，它限定了變元x的范圍。 一般，對全稱量詞，特性謂詞常作條件的前件；對存在量詞，特性謂詞常作合取項。,2.2命題函數(shù)與量詞,例：將下列命題符號化，并討論其真值。 (1)

7、所有的人都長頭發(fā)。 解: 令M(x): x是人。F(x): x 長頭發(fā)。則 x(M(x) F(x) 真值為0 (2)有的人吸煙。 解: 令M(x): x是人。S(x): x 吸煙。則 x(M(x)S(x) 真值為1,2.2命題函數(shù)與量詞,(3)沒有人登上過木星。 解: 令M(x): x是人。D(x): x 登上過木星。則 x(M(x)D(x) 真值為1 (4)清華大學(xué)的學(xué)生未必都是高素質(zhì)的。 解: 令Q(x): x 是清華大學(xué)的學(xué)生。H(x): x 是高素質(zhì)的。則 x(Q(x) H(x) 真值為1 或 x(Q(x)H(x) 可見，有些命題的符號化形式不止一種。,2.2命題函數(shù)與量詞,至此，下列

8、推理即可解決： 凡是人都是要死的。 蘇格拉底是人。 蘇格拉底是要死的。 令M(x): x 是人。D(x): x 是要死的。s: 蘇格拉底。則謂詞表達式為： (x)(M(x) D(x) M(s) D(s),2.3 謂詞公式與翻譯,一階語言一階語言F 的字母表定義如下: (1) 個體常項：a,b,c,ai,bi,ci,i1. (2) 個體變項：x,y,z,xi,yi,zi,i1. (3) 函數(shù)符號：f,g,h,fi,gi,hi,i1. (4) 謂詞符號：F,G,H,Fi,Gi,Hi,i1. (5) 量詞符號：，. (6) 聯(lián)結(jié)詞符號：，. (7) 括號與逗號：( , ) , , .,2.3 謂詞公

9、式與翻譯,F 的項： (1)個體常項和個體變項都是項。 (2)若f(x1, x2, , xn)是任意的n元函數(shù)，t1, t2, , tn是任意的n個項，則f(t1, t2, , tn)是項。 (3)所有的項都是有限次使用(1),(2)得到的。 原子公式若A(x1, x2, , xn)是F 的任意n元謂詞，t1, t2, , tn是F 的任意n個項，則稱A(t1, t2, , tn)為謂詞演算的原子公式。,2.3 謂詞公式與翻譯,謂詞演算的合式公式/謂詞公式 (1)原子公式是合式公式。 (2)若A 是合式公式，則 (A) 也是合式公式。 (3)若A和B是合式公式，則(AB)，(AB)，(AB)，

10、(AB)也是合式公式。 (4)若A是合式公式，x是A中出現(xiàn)的任何變元，則xA和xA，也是合式公式。 (5)只有有限次應(yīng)用規(guī)則(1)(4)構(gòu)成的符號串才是合式公式。,2.3 謂詞公式與翻譯,約定：最外層的圓括號可以省略。但量詞后面若有括號則不能省略。 例：將下列命題符號化 。 (1)沒有不能表示為分?jǐn)?shù)的有理數(shù)。 解: 令Q(x):x是有理數(shù)。W(x):x能表示成分?jǐn)?shù)。 則x(Q(x)W(x) 或 x(Q(x)W(x),2.3 謂詞公式與翻譯,(2)在北京買菜的人不全是外地人。 解: 令B(x):x在北京買菜的人。F(x):x是外地人。則 x(B(x)F(x)或 x(B(x)F(x) 例：將下列命

11、題符號化 。 (1)火車都比輪船快。 解: 令T(x):x是火車。S(x):x是輪船。F(x,y):x 比y 跑得快。則 xy(T(x)S(y) F(x,y),2.3 謂詞公式與翻譯,(2)有的火車比有的汽車快。 解: 令T(x):x是火車。C(x):x是汽車。F(x,y):x 比y 跑得快。則 xy(T(x)C(y)F(x,y) (3)不存在比所有火車都快的汽車。 解: 令T(x):x是火車。C(x):x是汽車。F(x,y):x 比y 跑得快。則 x(C(x)y(T(y)F(x,y) 或 x(C(x) y(T(y)F(y,x),2.4 變元的約束,給定A為一謂詞公式，其中有一部分公式形為xP

12、(x)或xP(x)。和后面所跟的x，稱為相應(yīng)量詞的指導(dǎo)變元。P(x)稱為相應(yīng)量詞的作用域/轄域。在x和x的轄域中，x的所有出現(xiàn)都稱為x在公式A中的約束出現(xiàn)，所有約束出現(xiàn)的變元，叫做約束變元。A中不是約束出現(xiàn)的變元均稱作自由變元。,2.4 變元的約束,(1)x(F(x) G(x,y) x是指導(dǎo)變元，量詞的轄域為(F(x)G(x,y)，其中，x是約束出現(xiàn)兩次，y是自由出現(xiàn)一次。 (2)x F(x,y) y G(x,y) x是指導(dǎo)變元，量詞的轄域是F(x,y)，其中，x是約束出現(xiàn)一次，y是自由出現(xiàn)一次；同時，y也是指導(dǎo)變元，量詞 的轄域是G(x,y)，其中，y是約束出現(xiàn)一次，x是自由出現(xiàn)一次。,2.

13、4 變元的約束,(3)x y (F(x,y)G(y,z)x H(x,y,z) x、y是指導(dǎo)變元，對應(yīng)量詞、的轄域為y(F(x,y)G(y,z)和(F(x,y)G(y,z) ，其中x是約束出現(xiàn)一次，y是約束出現(xiàn)兩次，z是自由出現(xiàn)一次；后一個x也是指導(dǎo)變元，量詞的轄域為H(x,y,z)，其中x是約束出現(xiàn)一次，y、z是自由出現(xiàn)一次。,2.4 變元的約束,例: (1) x(H(x,y) y(W(y)L(x,y,z) (2) x(H(x)W(y) y(F(x)L(x,y,z) 為了避免由于變元的約束與自由同時出現(xiàn)，引起概念上的混亂，故可對約束變元進行換名。使得一個變元在一個公式中只呈一種形式出現(xiàn)，即呈自

14、由出現(xiàn)或呈約束出現(xiàn)。 一個公式的約束變元所使用的名稱符號是無關(guān)緊要的，即xP(x)與yP(y)具有相同的意義，xP(x)與yP(y)意義也相同。,2.4 變元的約束,約束變元的換名規(guī)則： 對于約束變元可以換名，其更改的變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞作用域中所出現(xiàn)的該變元，公式的其余部分不變。 換名時一定要更改為作用域中沒有出現(xiàn)的變元名稱。 例: 對x(H(x,y) y(W(y)L(x,y,z)換名。 解: 可換名為x(H(x,y) u(W(u)L(x,u,z),2.4 變元的約束,對于公式中的自由變元，也允許更改，這種更改叫做代入/代替。 自由變元的代入規(guī)則： 對于謂詞公式中的自由

15、變元，可以作代入，代入時需對公式中出現(xiàn)該自由變元的每一處進行。 用以代入的變元與原公式中所有變元的名稱不能相同。,2.4 變元的約束,例:對x(H(x)W(y)y(F(x)L(x,y,z)代入。 解:經(jīng)代入后公式為 x(H(x)W(v) y(F(u)L(u,y,z),2.4 變元的約束,A(x1, x2, , xn)是n元謂詞，它有n個相互獨立的自由變元。若對其中k個變元進行約束則成n - k元謂詞。若謂詞公式中沒有自由變元出現(xiàn)，則該式就成為一個命題。 當(dāng)論域的元素有限時，可以消去公式中的量詞。設(shè)論域元素為a1, a2, , an。則 (x)A(x)A(a1)A(a2)A(an) (x)A(x

16、)A(a1)A(a2)A(an),2.4 變元的約束,量詞對變元的約束，往往與量詞的次序有關(guān)。命題中的多個量詞，我們約定從左到右的次序讀出。注意: 量詞的次序不能顛倒，否則將與原命題不符。,2.5 謂詞演算的等價式與蘊含式,賦值/解釋在謂詞公式中常包含命題變元和客體變元，當(dāng)客體變元由確定的客體所取代，命題變元用確定的命題所取代時，就稱作對謂詞公式賦值。一個謂詞公式經(jīng)過賦值以后，就成為命題。 等價給定任何兩個謂詞公式wff A和wff B，設(shè)它們有共同的個體域E，若對A和B的變元的任一組真值指派，所得真值均相同，則稱謂詞公式A和B在E上是等價的，并記作AB。,永真式/邏輯有效式給定任意謂詞公式w

17、ff A，其個體域為E，對于A的任一組真值指派，wff A皆為1，則稱公式A在E上是有效的/永真的。 不可滿足式/永假式一個謂詞公式wff A，如果在所有賦值下都為0，則稱該wff A是不可滿足的/永假的。 可滿足式一個謂詞公式wff A，如果至少在一種賦值下為T，則稱該wff A是可滿足的。,2.5 謂詞演算的等價式與蘊含式,謂詞演算中的等價式和蘊涵式命題演算中的等價公式表和蘊含公式表都可推廣到謂詞演算中使用。 消去量詞的等價式 量詞否定的等價式（量詞的轉(zhuǎn)化律） (x)P(x)(x)P(x) ， (x)P(x)(x)P(x) 證明：(可在有限個體域上證明),2.5 謂詞演算的等價式與蘊含式,

18、設(shè)個體域中的客體變元為a1, a2, , an，則 (x)A(x)(A(a1)A(a2)A(an) A(a1)A(a2)A(an) (x)A(x) (x)A(x) (A(a1)A(a2)A(an) A(a1)A(a2)A(an) (x)A(x),2.5 謂詞演算的等價式與蘊含式,量詞作用域的擴張與收縮的等價式 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(BA(x) Bx A(x) 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(BA(x) Bx A(x),2.5 謂詞演算的等

19、價式與蘊含式,以上各等價式中的B不含客體變元x ; 或含有與量詞指導(dǎo)變元x 不同的變元 , 如y , z 等。 試證明 x(A(x)B) x A(x)B 證：左x(A(x)B) x A(x)B x A(x)B x A(x)B（右）,2.5 謂詞演算的等價式與蘊含式,量詞分配的等價式 x(A(x)B(x) x A(x)x B(x) x(A(x)B(x) x A(x)x B(x) 量詞與命題聯(lián)結(jié)詞間的一些蘊含式 x A(x)x B(x) x(A(x)B(x) x(A(x)B(x) x A(x)x B(x) x(A(x) B(x) x A(x) x B(x) x(A(x) B(x) x A(x) x

20、 B(x) x A(x) x B(x) x(A(x) B(x),2.5 謂詞演算的等價式與蘊含式,具有兩個量詞的二元謂詞公式（共八種） x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) y x A(x,y) x y A(x,y) 其中：x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) 后四種均不等價，故全稱量詞和存在量詞在公式中出現(xiàn)的次序，不能隨意更換。,2.5 謂詞演算的等價式與蘊含式,2.6 前束范式,前束范式一個公式如果量詞均包含在全式的開頭，它們的作用域延伸到整個公式

21、的末尾，則該公式叫做前束范式。其形式為(v1)(v2)(vn)A ，其中是量詞或，vi (i=1,2,n)是客體變元，A 是沒有量詞的謂詞公式。 如：x y(F(x)G(y)H(x,y) x y(F(x,y)G(y,z)x H(x,y,z) ,2.6 前束范式,Th1(前束范式存在定理)任意一個謂詞公式，均和一個前束范式等價。 本定理說明任何公式的前束范式都是存在的，但一般不是唯一的。 求法： 利用對合律、德摩根律、量詞轉(zhuǎn)化律把否定深入到命題變元和謂詞填式的前面； 利用換名和代入規(guī)則，量詞作用域的擴張和收縮等價式，把量詞提到前面。,2.6 前束范式,例: 求下列公式的前束范式。 (1)x F(

22、x) x G(x) 解：xF(x) xG(x) xF(x)xG(x) (量詞否定等價式) x(F(x)G(x) (量詞分配等價式) 或xF(x) yG(y) (換名規(guī)則) xF(x)yG(y) (量詞否定等價式) x(F(x)yG(y) (量詞轄域擴張等價式) xy(F(x)G(y) (量詞轄域擴張等價式),2.6 前束范式,(2)x F(x) x G(x) 解：原式 xF(x) yG(y) (換名規(guī)則) xF(x)yG(y) (量詞否定等價式) x(F(x)yG(y) (量詞轄域擴張等價式) xy(F(x)G(y) (量詞轄域擴張等價式) (3)x F(x)x G(x) 解：原式 xF(x)

23、yG(y) (換名規(guī)則) xy(F(x)G(y) (量詞轄域擴張等價式),2.6 前束范式,(4)x F(x,y) y G(x,y) 解：xF(x,y)yG(x,y) t F(t,y)w G(x,w) (換名規(guī)則) tw(F(t,y)G(x,w) (量詞轄域擴張等價式) 或x F(x,t)y G(w,y) (代入規(guī)則) xy(F(x,t)G(w,y) (量詞轄域擴張等價式) (5)x F(x) x G(x) 解：原式xF(x)yG(y) (換名規(guī)則) x y(F(x)G(y) (量詞轄域擴張等價式),2.6 前束范式,(6)(x F(x,y)y G(y)x H(x,y,z) 解：原式 (x F

24、(x,y)b G(b)c H(c,y,z) x b(F(x,y)G(b)c H(c,y,z) x b c (F(x,y)G(b)H(c,y,z),2.6 前束范式,前束合取范式一個wff A如果具有如下形式，則稱為前束合取范式。 (v1)(v2)(vn)(A11A12A1k1) (A21A22A2k2)(Am1Am2Amkm) ， 其中是量詞或，vi (i=1,2,n)是客體變元，Ai j是原子公式或其否定。 Th2(前束合取范式存在定理)每一個wff A都可轉(zhuǎn)化為與其等價的前束合取范式。,2.6 前束范式,前束析取范式一個wff A如果具有如下形式，則稱為前束析取范式。 (v1)(v2)(v

25、n)(A11A12A1k1) (A21A22A2k2)(Am1Am2Amkm) ， 其中是量詞或，vi (i=1,2,n)是客體變元，Ai j是原子公式或其否定。 Th3(前束析取范式存在定理)每一個wff A都可轉(zhuǎn)化為與其等價的前束析取范式。,2.6 前束范式,任一個wff A轉(zhuǎn)換為等價的前束合(析)取范式的步驟： 消去公式中出現(xiàn)的多余量詞； 利用換名、代入規(guī)則使所有約束變元均不相同，并且使約束變元和自由變元不同； 將謂詞公式中出現(xiàn)的聯(lián)結(jié)詞均轉(zhuǎn)化成 , , ；,2.6 前束范式,利用對合律，德摩根律及量詞轉(zhuǎn)化律，將謂詞公式中的 深入到命題變元和謂詞填式的前面； 利用量詞作用域的擴張和收縮等價

26、式，將量詞推到左邊，擴大量詞作用域至整個公式。,2.7 謂詞演算的推理理論,命題演算中的推理規(guī)則，如P、T和CP規(guī)則等也可在謂詞演算的推理理論中應(yīng)用。 但在謂詞推理中，某些前提與結(jié)論可能受量詞限制，為了能使用命題演算中的等價式和蘊含式，必須在推理過程中有消去和添加量詞的規(guī)則。,2.7 謂詞演算的推理理論,(1)全稱指定規(guī)則（簡記為US） (x)P(x) P(c) 如果對論域中所有客體x ，P(x)成立，則對論域中某個任意客體c ，P(c)成立。,2.7 謂詞演算的推理理論,(2)全稱推廣規(guī)則（簡記為UG） P(x) (x)P(x) 如果能夠證明對論域中每一個客體c斷言P(c)都成立，則可得到結(jié)

27、論(x)P(x)成立。,2.7 謂詞演算的推理理論,(3)存在指定規(guī)則（簡記為ES） (x) P(x) P(c) 如果對于論域中某些客體P(x)成立，則必有某個特定客體c，使P(c)成立。應(yīng)注意，指定的客體c不是任意的。,2.7 謂詞演算的推理理論,(4)存在推廣規(guī)則（簡記為EG） P(c) x P(x) 如果對論域中某個特定客體c ，有P(c)成立，則在論域中，必存在x 使得P(x)成立。,2.7 謂詞演算的推理理論,例：構(gòu)造下列推理的證明。 前提：x (A(x)B(x)，x A(x) 結(jié)論：x B(x) 證明：(1) x A(x) P (2) A(c) (1)ES (3) x (A(x)B(x) P (4) A(c)B(c) (3)US (5) B(c) (2)(4) 假言推理 (6) x B(x) (5)EG 注意：(1) (3)引入的順序不可更改!,2.7 謂詞演算的推理理論,例：證明凡是人都是要死的。 蘇格拉底是人。 蘇格拉底是要死的。 解: 令M(x): x是人。D(x): x是要死的。a: 蘇格拉底。即要證 x(M(x)D(x) , M(a) D(a) 證明(1) x (M(x)D(x) P (2)