1、1,第 3 編 數(shù) 理 邏 輯,第 7 章 命 題 邏 輯,2,在命題邏輯中，原子為基本單位，不能再分，因此具有局限性，使有些簡單命題無法判斷。,例：著名的“蘇格拉底三段論”： P : 凡人都是要死的。 Q : 張三是人。 R : 張三要死的。 PQR 應(yīng)該是永真式，但在命題邏輯中無法證明。 解決方法：命題分解成個體詞、謂詞、量詞。,3,7.1 謂詞概念與表示,個體詞：可以獨立存在的客體?？梢允蔷唧w的事物，也可以是抽象的概念。用小寫字母表示：a, b, c,.,x, y, z. 定義：用以刻劃個體詞的性質(zhì)或關(guān)系的詞(命題函數(shù))稱為謂詞。用大寫字母表示：F( ), G( ). 個體域D：個體詞的

2、取值范圍。 全總個體域D：包含宇宙間所有的事物組成的個體，是研究問題中最大的個體域。 謂詞的取值范圍：0, 1.,4,例： 是無理數(shù)。 小王是程序員。 小李比小王高 2 厘米。,H(x): x 是程序員。 H(小王)。 G(x, y): x 比 y 高 2 厘米。G(小李, 小王)。 F(x)、H(x)是一元聯(lián)結(jié)詞；G(x, y)是二元聯(lián)結(jié)詞。 含n個個體詞的謂詞稱 n元謂詞。P(x1,x2,.,xn). 不含個體詞的謂詞稱 零元謂詞。,符號化：設(shè)F(x): x 是無理數(shù)。F( ) ， F( )。,5,對于個體詞具有數(shù)量的概念。如 所有的人都要死的。 有的人活百歲以上。,定義：“任意x ”稱全

3、稱量詞，記x。 “存在一個x ”稱存在量詞，記x。,對上面的例子，可設(shè) F(x): x 要死的。xF(x). G(x): x 活百歲以上。xG(x). 這兩個命題的真值都為T.,7.2 命題函數(shù)與量詞,6,注意：, x 的定義域D不同，符號可能不一樣。 如：D = 人類，符號同上； 如：D 為全總個體域，加特性謂詞：M(x): x是人。,x (M(x)F(x) .(1) x (M(x)G(x) .(2), 沒有給定定義域，則為全總個體域。 全稱量詞和存在量詞的符號化形式不同： 見(1), (2)式。,7, 但定義域有限時，設(shè)D = a1,a2,.,an,x F(x) F(a1)F(a2)F(a

4、n). x G(x) G(a1)G(a2)G(an)., 不能隨意顛倒量詞的順序。 例：“對任意的x，存在y，使x + y = 5”。 D = R, H(x, y): x + y = 5. 則 xy H(x, y) T 。但 yx H(x, y) F 。,8,7.3 謂詞公式的翻譯與解釋,定義1 字母表如下： (1) 個體常項：a,b,c, (2) 個體變項：x,y,z, (3) 函數(shù)符號：f ( ),g( ), (4) 謂詞符號：P( ),Q( ), (5) 量詞符號：, (6) 邏輯符號：, (7) 括號與逗號：(, ), ，,個體詞D,注意函數(shù)與謂詞的區(qū)別,9,定義2：謂詞邏輯中的項，被

5、遞歸定義為：(1) 任意的個體常項或個體變項是項；(2) 若f (x1,x2,xn,)是n元函數(shù)符號, t1,t2,tn是項, 則f (t1,t2,tn)是項；(3) 所有項都是有限次使用(1) (2) 生成的符號串。,例：a是項，x是項，g(x)是項，f (x, y)是項，f (g(x), a)是項.,定義3: 若P(x1,x2,xn,)是n元謂詞, t1,t2,tn 是項, 則P(t1,t2,tn)是原子公式。,10,定義4 合式公式是如下定義的一個符號串(1) 原子公式是合式公式；(2) 若A, B是合式公式，則如下符號串(A), (AB), (AB), (AB), (AB), (A B

6、)也是 合式公式；(3) 若A是合式公式，則xA, xA是合式公式；(4) 所有合式公式(謂詞公式)都是有限次使用(1)(2)(3)得到的符號串。,例：(1) x (P(f (x)Q(x, f (a); (2) x (P(x)Q(x, a). 兩個符號串都是公式。,11,命題符號化：,確定謂詞確定個體詞及量詞依量詞確定邏輯關(guān)系。,x (M(x)F(x) .(1) x (M(x)G(x) .(2),12,例1：每一個有理數(shù)都是實數(shù)。某些實數(shù)是有理數(shù)。不是每一個實數(shù)都是有理數(shù)。,解：設(shè)P(x): x 是有理數(shù)。Q(x): x 是實數(shù)。 x(P(x)Q(x). x(Q(x)P(x). x(Q(x)P

7、(x). ,13,例2:(1)所有的正數(shù)均可開平方；(2)沒有最大的自然數(shù)。,解：(1) 設(shè) R(x): x 是實數(shù)。 G(x,y): x y。 S(x): x 可以開平方。 x(R(x)G(x,0)S(x). (2) 設(shè) N(x): x 是自然數(shù)。 G(x,y): x y。 x(N(x)y(N(y)G(y,x). ,14,例3 不管黑貓白貓，抓住老鼠就是好貓。,解：設(shè)B(x): x 是黑貓； W(x): x 是白貓； M(x): x 抓住老鼠； G(x): x 是好貓。,x (B(x)W(x)M(x) G(x).,15,定義5：公式x A(x, y) 或x A(x, y) 中， x為指導(dǎo)變元

8、，A為 x的作用域或轄域. x 作用域內(nèi)的 x 稱為約束變元，非約束的 y 稱為自由變元。,例1：(1) x (P(x)yQ(x, y); x 和 y 都是約束變元。 (2) x F(x)G(x, y); 第一個 x 是約束變元，第二個 x 是自由變元， y 是自由變元。 (3) xy(R(x, y)L(y, z)x H(x, y). x 是約束變元，第一個y和第二個y是約束變元，第三個y是 自由變元，z 是自由變元。,7.4 變元的約束,16,n元謂詞：若謂詞公式P(x1, x2,., xm)中有n個自由變元，稱n元謂詞。,若謂詞公式P(x1, x2,., xm)中有k個約束變元，則為m-k

9、元謂詞。如 x yQ(x, y) 為零元謂詞； x Q(x, y) 為1元謂詞； Q(x, y) 為2元謂詞.,17,有些量詞既是約束的又是自由的，為避免混淆，可采用如下規(guī)則：,換名規(guī)則：對約束變元進行換名，即將量詞作用域中出現(xiàn)的某個約束變元換成另外作用域中未曾出現(xiàn)變元符號，公式中的其余部分不變。 代入規(guī)則：對自由變元進行代入，即對自由變元用與原公式中所有變元符號不同的符號去代替。,18,如上面例1(2) x F(x)G(x, y);可換名為: z F(z)G(x, y).,(3) xy(R(x, y)L(y, z)x H(x, y). 可換名為: xu(R(x, u)L(u, z)t H(t

10、, y).,19,7.5 謂詞演算的等價式與蘊含式,對一個解釋 I，公式就有一個確定的真值。,定義6：設(shè)謂詞公式A的個體域為D。 (1) 對每個常項指定D中一個元素；(2) 對每個n元函數(shù)指定Dn到D的一個函數(shù)；(3) 對每個n元謂詞指定Dn到0, 1的一個謂詞. 按這樣規(guī)則作出的一組指派稱為A的一個解釋 或賦值 I 。,20,例1 (1) x (P(f (x)Q(x, f (a)的一個解釋 I：,于是 x (P(f (x)Q(x, f (a) (P(f (2)Q(2, f (2)(P(f (3)Q(3, f (2) (P(3)Q(2, 3)(P(2)Q(3, 3) (11)(01) 10 1

11、.,D = 2, 3,21,(2) x (P(x)Q(x, a)的一個解釋 I：,D = 2, 3,x (P(x)Q(x, a) (P(2)Q(2, 2)(P(3)Q(3, 2) (01)(10) 0. ,22,例2 已知解釋N如下：1) 個體域為自然數(shù)集合Dn;2) Dn中特定元素 a = 0 ;3) Dn上的特定函數(shù) f(x,y) = x+y, g(x,y) = x y;4) Dn上的特定謂詞 F(x,y) 為 x = y 。在解釋N下，試說明下列公式的真假：(1) x F(g(x, a), x)(2) xy(F(f(x, a), y)F(f(y, a), x),解：在解釋N下，公式分別為

12、 (1) x F(g(x, a), x) x (x 0 = x) x (0 = x) 0,23,(2) xy(F(f(x, a), y)F(f(y, a), x), xy( x + 0 = y y + 0 = x) xy( x = y y = x) 11 1,24,定義7：設(shè)A是謂詞公式, 如果A在任何解釋下都為真，則稱A為邏輯有效式(永真式)；如果A在任何解釋下都為假，則稱A為矛盾式(永假式)；若至少存在一個解釋使A為真，則稱A為可滿足式。,例：P(x)P(x) 邏輯有效式； P(x)P(x) 矛盾式。 謂詞公式的真值表不存在。,定義8 設(shè)命題公式A0，命題變項為P1,P2,.,Pn，A1,

13、A2,.,An為謂詞公式，用Ai代替Pi(i=1,2,.,n)所得公式A稱為A0的代換實例。,25,等值式與重言蘊含式,1. 命題公式仍可用(16個等值式)。 2. 量詞否定等值式 (1) xA(x) x(A(x) (2) xA(x) x(A(x) 3. 量詞轄區(qū)擴張與收縮等值式 (1) x(A(x)B) xA(x)B (2) x(A(x)B) xA(x)B (3) x(A(x)B) xA(x)B (4) x(BA(x) BxA(x),26,(5) x(A(x)B) xA(x)B (6) x(A(x)B) xA(x)B (7) x(A(x)B) xA(x)B (8) x(BA(x) BxA(x

14、),4. 一般等值式 (9) xA(x)xB(x) x(A(x)B(x) (10) xA(x)xB(x) x(A(x)B(x) (11) xA(x)xB(x) xy(A(x)B(y) (12) xA(x)xB(x) xy(A(x)B(y) (13) x(A(x)B(x) xA(x)xB(x),27,5. 一般重言蘊含式 (14) xA(x)xB(x) x(A(x)B(x) (15) x(A(x)B(x) xA(x)xB(x) (16) x(A(x)B(x) xA(x)xB(x) (17) xA(x)xB(x) x(A(x)B(x) (18) x(A(x)B(x) xA(x)xB(x),6. 兩

15、個量詞的等值式與重言蘊含式 交換量詞位置，自己看。,28,利用上面公式可進行等值推演和形式演繹。,例：證三段論x(H(x)M(x), H(a) M(a). 其中H(x): x是人; M(x): x要死的; a: 張三。 證：(1) H(a) P (2) x(H(x)M(x) P (3) H(a)M(a) US(2) 全稱指定 (4) M(a) Q (1)(3) x(H(x)M(x), H(a) M(a). ,29,7.6 前束范式,定義9：一個公式，如果量詞均在公式的開頭，它們的作用域延伸到整個公式的末尾，則稱該公式為前束范式。 謂詞公式A具有如下形式 Q1x1Q2x2QnxnB 其中Qi x

16、i或者是xi，或者是xi，i =1,n, B是不含量詞的謂詞公式，則稱A為前束范式。,一種較簡單的范式。,例：xyz(P(x, y)Q(x, z)就是前束范式。,30,求前束范式要用到兩個性質(zhì)。性質(zhì)1: (1) x(G(x)H) xG(x)H(1)/ x(G(x)H) xG(x)H (2) x(G(x)H) xG(x)H(2)/ x(G(x)H) xG(x)H (3) (xG(x) x(G(x)(3)/ (xG(x) x(G(x),為前3(1)式,為前3(5)式,為前3(2)式,為前3(6)式,為前2(1)式,為前2(2)式,實際上以上等值式都不是新的公式，它們在前面已經(jīng)出現(xiàn)過或者是它們的特殊

17、情況。,31,性質(zhì)2: (1) xG(x)xH(x) x(G(x)H(x)(2) xG(x)xH(x) x(G(x)H(x)(3) xG(x)xH(x) xy(G(x)H(y)(4) xG(x)xH(x) x y(G(x)H(y),前4(9)式,前4(10)式,前4(11)式,前4(12)式,32,定理：對任意公式G，都存在一個與其等值的前束范式。,證: 通過以下步驟可將G化為等值的前束范式。 第一步：使用基本等值式，將聯(lián)結(jié)詞, 化為, , ； 第二步：將所有否定 放到原子前； 第三步：根據(jù)需要將約束變量改名； 第四步：使用性質(zhì)1, 2, 將所有量詞都提到公式的最左邊。 于是將公式G在等值意義

18、下，化成了一個前束范式。 ,33,例1：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)xG(x) xF(x)xG(x) xF(x)yG(y) xy(F(x)G(y) ,例2：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) x(F(x)G(x) ,34,例3：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) ,例4：求公式xF(x)xG(x)的前束范式。,解：xF(x)xG(x) xF(x)yG(y) x(F(x)yG(y) xy(F(x)G(y) ,35,附：幾個謂

19、詞公式的證明,設(shè)D = a1, a2,an. 4(10) xA(x)xB(x) x(A(x)B(x) 證：x(A(x)B(x) (A(a1)B(a1)(A(an)B(an) (A(a1)A(an)(B(a1)B(an) xA(x)xB(x)。 ,36,5(14) xA(x)xB(x) x(A(x)B(x),證：xA(x)xB(x) (A(a1)A(an)(B(a1)B(an) (A(a1)B(a1)(A(an)B(an) (A(a1)B(a2)(A(a1)B(a3) (A(an-1)B(an) x(A(x)B(x) (A(a1)B(a2) x(A(x)B(x). ,37,2(2) xA(x)

20、x(A(x),證：xA(x) (A(a1)A(an) A(a1)A(an) x(A(x). 3(1) x(A(x)B) xA(x)B 證：x(A(x)B) (A(a1)B)(A(an)B) (A(a1)A(an)B xA(x)B. ,38,3(3) (xA(x)B) x(A(x)B),證：(xA(x)B) xA(x)B xA(x)B x(A(x)B) x(A(x)B)。 3(4) BxA(x) x(BA(x) 證：BxA(x) BxA(x) x(BA(x) x(BA(x)。 ,39,7.7 謂詞邏輯的推理理論,A1,A2,.,Am C 可用公式： 命題邏輯: 等值式(16個), 蘊含式(14個) 謂詞邏輯: 等值式(13個),