1、謂詞公式是由原子謂詞公式通過聯(lián)結(jié)詞、量詞、 小括號組成的字符串。 而原子謂詞公式(x1，x2，.，xn)中可含有 個體常元、個體變元(約束變元和自由變元)、 謂詞常元、謂詞變元。 顯然，對謂詞公式A，只有當(dāng)把其中的自由個體 變元、謂詞變元都賦予確定的含義以后，A才成為 具有確定內(nèi)容的命題，同時也具有確定的真假值。,1.7 謂詞演算的永真公式,將謂詞公式中個體變元由確定的個體來取代，謂詞變元 由確定的謂詞來取代，稱為對謂詞公式的賦值或解釋。 公式A的每一個指派或解釋I由以下三部分組成： 1 非空個體域； 2 D中一部分特定元素 (用來解釋個體常元) 3 D上一些特定的謂詞 (用來解釋謂詞變元)

2、例如：對 x(P(x)Q(x) 指定：1.個體域D為全總個體域 2.(x)：x是人；(x)：x是黃種人。 則x(P(x)Q(x)：所有的人都是黃種人。 F 思考：若 個體域D為實數(shù)集 (x)：x是自然數(shù)；(x)：x是有理數(shù)。,一、謂詞公式的賦值,例1-7-1 給定一個解釋I： D=2，3； D中的特定元素 a=2 D上的特定謂詞 F(x)為：F(2)=0，F(xiàn)(3)=1 L(x,y)為：L(2,2)= L(3,3)=1; L(2,3)=L(3,2)=0. 在這個解釋下，求下列各式的值。 1 x(F(x)L(x,a) (F(2)L(2,2)(F(3)L(3,2) (01)(11) 0 2 xy L

3、(x,y) x(L(x,2)L(x,3) (L(2,2)L(2,3)(L(3,2)L(3,3) (10)(01) 1,A在個體域E上的分類 給定謂詞公式A及個體域E，如果在個體域E中無論怎樣構(gòu)成A的一種指派： 1 A都取值為真，則稱A在E上永真或A在E上上邏輯有效。 2 A都取值為假，則稱A在E上永假或A在E上矛盾。 3 A至少在一種指派下取值為真，則稱A在E上可滿足。 A的分類 1 如果A在任意個體域上永真，則稱A為永真式(或邏輯有效式)。 2 如果A在任意個體域永假，則稱A為永假式(或矛盾式)。 3 如果A至少在一個個體域上可滿足，則稱A為可滿足式。,謂詞公式的類型,方法一：真值表法 當(dāng)謂

4、詞公式A的個體域E是有限的，謂詞變元的解釋也 是有限的時，原則上可以用真值表來判斷。 方法二：指派分析法 當(dāng)謂詞公式A的個體域E是無限的，或謂詞變元的解釋是無限的時，謂詞公式A的指派就是無限多個，無法實現(xiàn)用真值表來判斷，一般根據(jù)聯(lián)結(jié)詞、量詞的意義，直接用自然語言來敘述進(jìn)行證明。,謂詞公式類型的判斷,例1-7-2 在給定條件下判定謂詞公式的類型。 1 設(shè)謂詞P(x)的含義僅為：A(x)：x是奇數(shù)。或 B(x)：x是偶數(shù)。 個體域E=3，4， 判定謂詞公式P(x)xP(x)的類型。,P(x)xP(x)在E上可滿足， xP(x)在E上永真。,2 xP(x)xP(x) 解： 未指明個體域與謂詞P(x)

5、的含義 -任意多組解釋 設(shè)D為任意一個個體域，I為任意一個指派。 若xP(x)為真， 即對于D中任意x，P(x)均為真。 此時在D中當(dāng)然至少有一個x，使P(x)為真。 則xP(x)為真。 所以在指派I下，xP(x)xP(x)取值為真。 由I的任意性，xP(x) xP(x)為永真式。,遍及個體域E等價（永真蘊含） 給定個體域E上的兩個謂詞公式A和B，若對E中的任意指派I， 1 A、B 都具有相同的真值（即謂詞公式AB為永真式）， 則稱謂詞公式A和B在E上等價，記作：在E上AB。 2 當(dāng)A為真時，B也為真（即謂詞公式AB為永真式）， 則稱謂詞公式A在E上永真蘊含B，記作：在E上AB。 等價（永真蘊

6、含） 1 若A和B在任意個體域上都是等價的，則稱謂詞公式A和B 等價，記作：AB。 2 若A和B在任意個體域上都有A永真蘊含B，則稱謂詞公式A 永真蘊含B，記作：AB。,二、謂詞演算中的邏輯等價式和永真蘊含式,謂詞邏輯中常用的邏輯等價式和永真蘊含式，其來源可分為兩類： 一、永真命題公式的推廣 用原子謂詞公式取代命題演算等價公式中的各命題變元，命題演算的等價式就轉(zhuǎn)化為謂詞演算的等價式。 依據(jù)：永真式的任何代入實例也必永真。 例如：1 由 P P 得： A(x) A(x) 2 由 PQ PQ 得：xA(x)xB(x) (xA(x)(xB(x) 二、由于引入量詞而產(chǎn)生的謂詞演算中特有的邏輯等價式、

7、永真蘊含式。,常用的邏輯等價式和永真蘊含式,1量詞的消去律 (1)設(shè)個體域為有限集D=a1, a2, ,an時，則有 x P(x) P(a1)P(a2)P(an) （1） x P(x) P(a1) P(a2) P(an) （2） (2) 設(shè)A是不含自由變元x的謂詞公式，則有 xA A （3） xA A （4） (因為A的真值與自由變元x無關(guān)),與量詞有關(guān)的邏輯等價式,2量詞的否定律( 量詞轉(zhuǎn)換律 ) xP(x) x P(x) （5） xP(x) x P(x) （6） 量詞前面的否定詞可深入到量詞轄域內(nèi)。 注：出現(xiàn)在量詞之前的否定不是否定該量詞，而是否定被量化了的整個命題。 xP(x) (xP(

8、x)。 例如： 設(shè)個體域D為大學(xué)生集合，P(x)：x今天來上課。 P(x)：x今天沒來校上課。 1 xP(x)：不是所有的大學(xué)生今天都來上課。 與 xP(x)：存在一些大學(xué)生今天沒來上課。（含義相同） 2 xP(x)：今天沒有(不存在)來上課的大學(xué)生。 與 xP(x)：所有的大學(xué)生今天都沒來上課。（含義相同）,3量詞轄域的擴張與收縮律 設(shè)P是不含自由變元x的任一謂詞公式(包括命題公式)， 則有： xA(x)Px（A(x)P） （7） xA(x)Px（A(x)P） （8） xA(x)Px（A(x)P） （9） xA(x)Px（A(x)P） （10） 證明：當(dāng)個體域為有限集a1, a2,., an

9、時， xA(x)P(A(a1)A(a2).A(an)P (A(a1)P)(A(a2)P).(A(an)P) x(A(x)P) 當(dāng)個體域為無限集時，指派分析證明： 左右同真假。,3量詞轄域的擴張與收縮律 設(shè)P是不含自由變元x的任一謂詞公式(包括命題公式)， 則有： PxA(x) x( PA(x) ) （11） PxA(x) x( PA(x) ) （12） xA(x)P x( A(x)P ) （13） xA(x)P x( A(x)P ) （14） 前不變后變 證明：(13) x(A(x)P) x(A(x)P) 蘊含等價式 xA(x)P 量詞轄域的擴張與收縮律 xA(x)P 量詞否定律 xA(x)P

10、 蘊含等價式,4量詞的分配律 x(A(x)B(x) xA(x) xB(x) （15） x(A(x)B(x) xA(x) xB(x) （16） x(A(x)B(x) xA(x) xB(x) （17） 例如：設(shè)個體域D為聯(lián)歡會上所有的人組成的集合， A(x)：x唱歌。 B(x)：x跳舞。 1 x(A(x)B(x)： 聯(lián)歡會上所有的人既唱歌又跳舞。 與 xA(x)xB(x)： 聯(lián)歡會上所有的人唱歌且所有的人 跳舞。（含義相同） 2 x(A(x)B(x)： 聯(lián)歡會上有人唱歌或跳舞。 與 xA(x)xB(x)： 聯(lián)歡會上有人唱歌，或聯(lián)歡會上有 人跳舞。（含義相同）,證明：設(shè)D為任意一個個體域，I為任意一

11、個指派。 x(A(x)B(x)：對于D中所有的，A(x)和B(x)都是真的。 xA(x)xB(x)：對于D中所有的，A(x)是真的；同時對 于D中所有的，B(x)也是真的。-兩個命題是等價的。 x(A(x)B(x)：D中存在，能使()或者()為真。 xA(x)xB(x)：D中存在能使()為真，或者D中存在 能使()為真。 -兩個命題是等價的。 (17) x( A(x)B(x) ) x(A(x)B(x) 蘊含等價式 xA(x) xB(x) 量詞分配的等價式 (xA(x) xB(x) 量詞否定律 xA(x) xB(x) 蘊含等價式,5量詞交換律 xyP(x,y) yxP(x,y) （18） xyP

12、(x,y) yxP(x,y) （19） 證明：當(dāng)個體域為有限集時，為討論方便不妨取D=1,2 則 xyP(x,y) x( yP(x,y) ) x( P(x,1)P(x,2) ) ( P(1,1)P(1,2) )( P(2,1) P(2,2) ) yxP(x,y) y( P(1,y) P(2,y) ) ( P(1,1)P(2,1) )( P(1,2) P(2,2) ) 當(dāng)個體域為無限集時，指派分析證明： 左右同真假。,1量詞消去的蘊含式 xP(x) P(a) (1) 或 xP(x) P(y)、 xP(x) P(x) P(a) xP(x) (2) 或 P(y) xP(x)、 P(x) xP(x)

13、xP(x) xP(x) (3),與量詞有關(guān)的永真蘊含式,2量詞分配的蘊含式 xA(x) xB(x) x(A(x)B(x) （4） x(A(x)B(x) xA(x) xB(x) （5） xA(x) xB(x) x(A(x)B(x) （6） 注意：全稱量詞x對、 不能等價分配 存在量詞對不能等價分配 對(4)式，“每一個人都唱歌或者每一個人都跳舞”，那么可以說“每一個人都唱歌或跳舞”。但反之不真（不能保證每個人都是在唱歌，或者每個人都是在跳舞）。 對(5)式，“有人既唱歌又跳舞”，那么可以說 “有人唱歌且有人跳舞”。反之不真（不能保證是同一個人既唱歌又跳舞）。,量詞交換的蘊含式 xyP(x,y)

14、yxP(x,y) （7） yxP(x,y) xyP(x,y) （8） xyP(x,y) yxP(x,y) （9） 其中 xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) xyP(x,y) yxP(x,y) (8)反之xyP(x,y) yxP(x,y) 不成立，同4。 交換量詞中x,y的次序，類似可得： yxP(x,y) xyP(x,y) （10） xyP(x,y) yxP(x,y) （11） yxP(x,y) xyP(x,y) （12）,1 代入規(guī)則 (1) 自由個體變元的代入 對公式A中所有的同名自由個體變元都用另一個自由個體變元來代替，且新變元在原來的公式中沒有出現(xiàn)過

15、。 例如：xF(x)G(x,y) - xF(x)G(u,y) - xF(x)G(y,y) (2) 謂詞變元的代入 對公式A中的謂詞也可用公式未曾出現(xiàn)過的新的謂詞來代替，只要求新的謂詞中的變元沒有在原來的公式中出現(xiàn)過。 例如：x(A(x)A(x) - x( F(x,y)F(x,y) ) 代入定理： 永真式的任何代入實例仍為永真式。,三、謂詞公式的等值演算,2 置換規(guī)則 設(shè)C是含子公式A的謂詞公式，D是用公式B置換了C中的A（不必每一處）之后得到的謂詞公式， A、B都僅含有n個自由個體變元。 如果AB，則CD。 例如： 公式C： P(x)( Q(x,t) R(x,t) 其中子公式A：Q(x,t)

16、R(x,t) Q(x,t)R(x,t) 代入規(guī)則 故C P(x)(Q(x,t) R(x,t) ),3 對偶原理 A的對偶公式A*：設(shè)謂詞公式A中僅含有聯(lián)結(jié)詞 、。 將A中、 、 分別換成、 后 所得到的謂詞公式。 對偶原理：設(shè)A*、B*分別是命題公式、的對偶式。 若 A B， 則 A* B* 。 若 A B， 則 B* A* 。,例1-7-3 1 將 xyzP(x,y,z)中的否定詞移到量詞的轄域中。 解： xyzP(x,y,z) x( yzP(x,y,z) ) 多個量詞轄域的定義 x ( yzP(x,y,z) ) 量詞的否定律 x ( y( zP(x,y,z) ) ) 多個量詞轄域的定義 x

17、y( zP(x,y,z) ) 量詞的否定律 xyz P(x,y,z) 同上 2 設(shè)個體域D=a,b,c， 將下列公式中的量詞消去。 (1) x(F(x)G(x) (2) x(F(x)G(x) (3) x(F(x) yG(y),等值演算實例,3 證明：xy(P(x)Q(y) xP(x)yQ(y) 證明： xy( P(x)Q(y) x( y(P(x)Q(y) ) 多個量詞轄域的定義 x( y( P(x) Q(y) ) ) 蘊含等價式 x( P(x) yQ(y) ) 量詞轄域的擴張與收縮律 xP(x) yQ(y) 同上 ( xP(x) ) yQ(y) 量詞的否定律 xP(x)yQ(y) 蘊含等價式,

18、前束范式：量詞均非否定地放在在全式的開頭，沒有括 號將它們彼此隔開，而它們的轄域延伸到整 個公式末尾的謂詞公式。 前束范式的形式： v1v2.vn A 其中“”表示量詞或，v1，v2，.，vn是個體變元， A是不帶量詞的謂詞公式。 前束范式的母式：前束范式中位于所有量詞后面的部分，即A。 例如： 1 xyz(Q(x,y)R(z) 2 xyQ(x,y) zR(z) 3 Q(x,y) 其中1、3是前束范式，2不是前束范式 1的母式：Q(x,y)R(z)， 1-前束析取范式,四、前束范式,前束范式存在性定理： 任意一個謂詞公式，均和一個前束 范式等價。 證明：構(gòu)造性算法進(jìn)行證明，步驟如下： 1 消去對、冗余的聯(lián)結(jié)詞。 2 利用量詞否定律和德摩根律將否定詞向內(nèi)深入，使之 只作用于原子公式。 3 利用改名規(guī)則或代入規(guī)則使所有的約