數(shù)學(xué)離散數(shù)學(xué)PPT課件

1、上節(jié)課的內(nèi)容 謂詞 一元謂詞n元謂詞 量詞 全稱量詞 存在量詞 量詞的轄域 自由變元與約束變元 約束變元的改名規(guī)則第1頁/共41頁謂詞演算的永真公式第2頁/共41頁謂詞謂詞等價等價的的定義定義 定義定義 1: 兩個任意謂詞公式謂詞公式A和和B, E是它們公有的論述域公有的論述域, 若 (1) 對公式A和和B中的謂詞變元謂詞變元, 指派以任一在任一在E上有定義上有定義的的確定的謂詞謂詞。 (2) 對謂詞命名式謂詞命名式中的個體變元個體變元, 指派以E中中的任一任一確定的個體個體。所得的命題命題都具有同樣的有同樣的真值真值, 則稱公式A和B遍及遍及E等價等價, 記為： 在在 E 上上 AB。 定義

2、定義 2: 如果兩謂詞公式A和B, 在任意論述域任意論述域上上都等價等價, 則稱A和和B等價等價, 記為 AB。第3頁/共41頁 定義定義3: 給定任一謂詞公式謂詞公式 A, 如果在 論述域論述域E 上, 對公式A中的謂詞謂詞和個體個體變元進(jìn)行 定義定義1中的兩種指派兩種指派, 所得命題命題 (1) 都真都真，則稱A在在E上上有效有效或在E上永真永真。 (2) 至少有一個至少有一個是真, 則稱A在在E上上 可滿足可滿足。 (3) 都假都假, 則稱A在在E上上永假永假或在E上不可滿足不可滿足。 謂詞謂詞公式公式的的分類分類 第4頁/共41頁 定義定義 4： 給定任一謂詞公式謂詞公式A, 如果在任

3、意論述域任意論述域上上, 對上述兩種指派, (1) A永真永真, 則稱A永真永真或有效有效。 (2) A至少至少在一個域一個域上可滿足可滿足, 則稱A可滿足可滿足。 (3) A永假永假, 則稱A永假永假或不可滿足不可滿足。 若謂詞公式A的個體域個體域是有限有限的, 謂詞的解釋謂詞的解釋也有限有限, 則可用可用真值表真值表判定判定謂詞公式A是否永真是否永真。謂詞謂詞公式的公式的分類分類 第5頁/共41頁 例例： 設(shè)P(x)僅可解釋為: A(x): x是質(zhì)數(shù), B(x): x是合數(shù)。論述域論述域是3, 4, 判定謂詞公式P(x)xP(x)是否永真是否永真。 解解: (見右表) 所以, P(x)xP

4、(x)非永真式。 第6頁/共41頁 但是，當(dāng)謂詞的解釋和個體變元的數(shù)量稍大, 用真值表判定是否永真就難以實現(xiàn)。 這時，一般利用推導(dǎo)方法, 因此, 如同命題演算一樣, 首先要求出基本的永真公式, 以作為推導(dǎo)的根據(jù)。 第7頁/共41頁謂詞演算的基本永真公式謂詞演算的基本永真公式 1、首先，命題演算命題演算的永真公式永真公式也是謂詞演算謂詞演算的永真公式永真公式, 基本的就是前面介紹的表 1.2-1(2)的邏輯恒等式邏輯恒等式和永真蘊含式永真蘊含式。 第8頁/共41頁 2. 含有量詞含有量詞的謂詞演算的的謂詞演算的基本永真公式基本永真公式。 (i) xAA xAA 這里A是不含自由變元不含自由變元x

5、的謂詞公式謂詞公式, 因為A的真值與x無關(guān), 所以上述等價式成立。第9頁/共41頁 (ii) xP(x) P(y)， 或 xP(x) P(x) P(y) xP(x)，或 P(x) xP(x)前一公式的意義是: 如果斷言“對一切x, P(x) 是真”成立, 那么對任一確定的x, P(x) 是真。后一公式的意義是: 如果對某一確定的x, P(x)是真, 那么斷言“存在一x, 使P(x)是真”成立。根據(jù)前提三段論, 從這兩個公式可推得 xP(x) xP(x) 第10頁/共41頁 (iii) 量詞量詞的的否定否定： ( xP(x) x P(x) ( xP(x) x P(x) 由于“并非對一切x, P(

6、x)是真”等價于“存在一些x, P(x)是真”, 所以前一式成立。由于“并不存在一x, 使P(x)是真”等價于“對一切x, P(x)是真”, 所以后一式成立。第11頁/共41頁對比這兩個式子, 容易看出, 如果把P(x)看作整體, 那么將x和x兩者互換, 可從一個式得出另一個式。這說明 x和和 x具有具有對偶性對偶性。另外, 由于兩個量詞可以互相表達(dá), 所以有一個量詞有一個量詞就夠就夠了了。 ( xP(x) x P(x) ( xP(x) x P(x) 第12頁/共41頁例例 ：x y z(x+z=y) xy z(x+z=y) x yz(x+z=y) x y z (x+z=y) x y z (x

7、+zy) 第13頁/共41頁(iv) 量詞轄域量詞轄域的擴(kuò)張擴(kuò)張和收縮收縮 xA(x)P x(A(x)P) xA(x)P x(A(x)P) xA(x)P x(A(x)P) xA(x)P x(A(x)P) 其中P是不含自由變元是不含自由變元x的謂詞。這里也可以看出 x和和 x具有具有對偶性對偶性。第14頁/共41頁 (v) 量詞量詞的分配分配: x(A(x)B(x) xA(x) xB(x) x(A(x)B(x) xA(x) xB(x)第個等價式的成立是由于對一切x, A(x)B(x)是真, 等價于對一切x, A(x)是真并且對一切x, B(x)是真。 第15頁/共41頁 第個公式可由第個公式推出

8、。因為中的A(x), B(x)是任意的, 所以可用 A(x) , B(x)分別取代取代A(x)和和B(x), 得 否定等價式兩邊否定等價式兩邊得 x( A(x) B(x) x A(x) x B(x) x (A(x)B(x) ( xA(x) ( xB(x) x (A(x)B(x) xA(x) xB(x)第16頁/共41頁第個公式是成立的, 因為存在一x使A(x)B(x)是真, 所以存在一x使A(x)是真, 同時存在一x使B(x)是真。但第個公式不不是是等價等價式式。例例：設(shè)A(x)和B(x)分別解釋為“x是奇數(shù)是奇數(shù)”和“x是偶數(shù)是偶數(shù)”, 論述域論述域是自然數(shù)自然數(shù)N, 則xA(x)是真, x

9、B(x)是真, 所以xA(x)xB(x)是真,但x(A(x)B(x)是假, 所以第個公式不等價不等價。(v) 量詞的分配: x(A(x)B(x) xA(x) xB(x) xA(x) xB(x) x(A(x)B(x) 第17頁/共41頁 第個公式可由第個公式推出。用A(x)和B(x)分別取代取代A(x)和B(x), 得 x(A(x)B(x) xA(x) xB(x) x (A(x) B(x) ( xA(x) ( xB(x)否定等價式兩邊否定等價式兩邊，得： xA(x) xB(x) x(A(x)B(x) 第18頁/共41頁(vi) 量詞對量詞對 及 的處理處理只須應(yīng)用它們對 ， ， 的恒等式恒等式即

10、可推出。例例： x(A(x)B(x) xA(x) xB(x) 證證：x(A(x)B(x) x(A(x)B(x) xA(x)xB(x)xA(x)xB(x) 第19頁/共41頁(vii) 關(guān)于多個量詞多個量詞的永真式永真式: x yP(x, y) y x P(x, y) x yP(x, y) y x P(x, y) y xP(x, y) x y P(x, y) x yP(x, y) y x P(x, y) x yP(x, y) y x P(x, y) 第20頁/共41頁 注意注意： x yP(x, y) y xP(x, y) 不成立不成立！例例: 設(shè)P(x, y)表示 x+y=0, 論述域論述域是

11、有理數(shù)有理數(shù)集合。則 xy (x+y=0) 是真, 但 yx (x+y=0) 是假。 由此可知, 一般情況下，一般情況下，量詞的次序量詞的次序是是不能隨便顛倒不能隨便顛倒的的。 第21頁/共41頁當(dāng)當(dāng)論述域有限時論述域有限時，可將，可將謂詞公式謂詞公式展開為展開為命題公式命題公式證明。證明。例例：設(shè)論述域論述域為a0, a1, a2, , an, 則 xA(x)PA(a0)A(a1)A(a2) A(an)P (A(a0)P)(A(a1)P) (A(an)P)x(A(x)P) 第22頁/共41頁表表 1.7 -1 含有量詞的永真公式概要表含有量詞的永真公式概要表 第23頁/共41頁謂詞演算規(guī)則謂

12、詞演算規(guī)則1、代入規(guī)則、代入規(guī)則2、替換規(guī)則、替換規(guī)則3、對偶原理、對偶原理第24頁/共41頁 1. 代入規(guī)則代入規(guī)則 (i)自由個體變元自由個體變元的代入的代入：在一公式中, 任一自由個體變元任一自由個體變元可代以另一個體變元代以另一個體變元, 只需該個體變元個體變元出現(xiàn)的各處都同樣代入各處都同樣代入, 且代入的變元代入的變元不允許不允許在原來公式中以約束變元出現(xiàn)以約束變元出現(xiàn)。例例: 在公式xP(x, y)Q(w, y)中, 將y代以z, 則得xP(x, z)Q(w, z)，將y代以w, 則得xP(x, w)Q(w, w)。所得公式稱為原公式的代入實例代入實例。 如果原式是如果原式是永真公

13、式永真公式, 則代入后仍得代入后仍得永真公式永真公式, 如果原公式非永真公式非永真公式, 則代入后可能變化可能變化。 第25頁/共41頁 (ii)謂詞變元謂詞變元的代入的代入在一公式中, 一個n元元(n0)謂詞變元謂詞變元F(x1, x2, xn)可代以至少有至少有n個個自由個體變元自由個體變元的公式G(y1, y2, , yn, yn+1, , yn+r), 只須該n元謂詞謂詞出現(xiàn)的各處都同樣代入各處都同樣代入, y1, y2, , yn 代以 x1, x2, xn 。且代入的公式中：1.后邊的r個自由變元個自由變元 不允許不允許在在原公式原公式中以約束變元出現(xiàn)以約束變元出現(xiàn); 2. F(x

14、1,x2, , xn)中中的變元變元也也不允許不允許在代入的公式代入的公式中以約束變元以約束變元出現(xiàn)出現(xiàn)。 第26頁/共41頁例例:(a) 對公式(PQ) (PQ)中的P代以 xP(x), Q代以S(x), 得 ( xP(x)S(x) ( xP(x)S(x) (b) 對公式 A: F(x, y)MF(u, x)中的 F, 欲代以 B: G(x1)H(x2, s)H(t, x2), 則只需x , y , u不是不是B內(nèi)的約內(nèi)的約束變元束變元, 而且s , t不是不是A內(nèi)的約束變元內(nèi)的約束變元。 代入結(jié)果為(G(x)H(y, s)H(t, y)M(G(u)H(x, s)H(t, x) 第27頁/共

15、41頁 2. 替換規(guī)則替換規(guī)則 設(shè)A(x1, x2, xn) B(x1, x2, , xn), 而A是公式是公式C中的子公式中的子公式, 將B替換替換C中中的的A得D (不必每一處不必每一處), 則：CD。 第28頁/共41頁 3. 對偶原理對偶原理 若量詞量詞公式公式 A 僅含運算符僅含運算符 , 和和 , 將上式中的全稱量詞全稱量詞 與與存在量詞存在量詞 互換互換, 與與互換互換, T和和F互換互換, 則互換后所得的公式A* 稱為A的的對偶式對偶式。 若AB，則 A* B *, 若AB，則 B*A*。 第29頁/共41頁謂詞演算實例第30頁/共41頁例例：(a) 證明)()()()(xxQ

16、xxPxQxPx1441114)()()()()()()()()()(ExxQxxPQxxQxxPQxxQxPxExQxPxxQxPx證證:第31頁/共41頁(b) 證明 )()()()()()(xPxRxQxRxxQxPx證證： 根據(jù)根據(jù)CP規(guī)則規(guī)則, 上式等價于 而 )()()()()()(xPxRxQxRxxQxPx)()()()()()()()()()()()()()()()()()(xPxRxPxQxQxRxPxQxQxRxxQxRxQxPxxQxRxxQxPx所以, )()()()()()(xPxRxQxRxxQxPx第32頁/共41頁于是證明: )()()()(xxQxxPxxQ

17、xxP不是永真的即可。 (c) 證明 )()()()(xxQxxPxQxPx是非永真式非永真式。 證：證： )()()()()()()()()()(xxQxxPxxQxxPxxQxPxxQxPxxQxPx第33頁/共41頁 為了證明不是永真證明不是永真的,只需找出只需找出一個論述域一個論述域及域上謂詞的謂詞的一種解釋種解釋, 使使(xP(x) xQ(x)(xP(x)xQ(x)是假是假即可。 現(xiàn)設(shè)論述域是整數(shù)集合論述域是整數(shù)集合, P(x)表示表示x=0, Q(x)表示表示xx。于是 xP(x)是假, 因而 xP(x) xQ(x)是真, 但xP(x)是真, xQ(x)是假, xP(x)xQ(x)

18、 是假。 所以，( xP(x) xQ(x)( xP(x) xQ(x) 是假。第34頁/共41頁第35頁/共41頁附加：謂詞邏輯的前束范式定義：設(shè) A 為一個謂詞邏輯公式，若 A=Q1x1Q2x2Qk xk B, 其中Qi (1 i k)為 或 ，B為不含量詞的公式，則稱A為前束范式。例如， x(F(x)G(x) xy(F(x)(G(y)H(x,y) 是前束范式而 x(F(x)G(x) x(F(x)y(G(y)H(x,y) 不是前束范式 第36頁/共41頁前束范式存在定理定理 謂詞邏輯中的任何公式都存在與之等價的前束范式例 求下列公式的前束范式 (1) x(M(x)F(x)解 x(M(x)F(x) x(M(x)F(x) （量詞否定等值式） x(M(x)F(x) 后兩步結(jié)果都是前束范式，說明公式的前束范式不唯一。第37頁/共41頁求前束范式的實例 (2) xF(x)xG(x)解 xF(x)xG(x) xF(x)xG(x) （量詞否定等值式） x(F(x)G(x) （量詞分配等值式）或 xF(x)xG(x)