1、4 謂詞演算的等價式與蘊含式1、謂詞公式的等價定義A，B為二個謂詞公式，E為它們共同個體域，若對A和B的任一組變元進行賦值，使得A和B的值相同，則稱A和B在個體域E上是互為等價的，記為AB EB或 A定義給定謂詞公式A，E是A的個體域。若給A中客體變元指派E中的每一個客體所得命題的值均為真，則稱A在E中是永真的。若E為任意域則稱A是永真的。2、謂詞公式的分類定義給定謂詞公式A，E是A的個體域。若給A中客體變元指派E中的每一個客體所得命題的值均為假，則稱A在E中是永假的。若E為任意域則稱A是永假的。定義給定謂詞公式A，E是A的個體域。若給A中客體變元指派E中每一個客體，在E中存在一些客體，使得指

2、派后的真值為真，則A稱是可滿足的。3.不含量詞的謂詞公式的等價公式和永真蘊含式 只要用原子謂詞公式去代替命題邏輯中等價公式和永真蘊含式中的原子命題變元，則可獲得謂詞演算中的等價公式和永真蘊含式。 命題邏輯 謂詞邏輯 (x)(x)(x) (x)(x) (x) (x) . . . . (x)(x)(x) (x) (x) (x) . . . . 命題邏輯 謂詞邏輯 x(x)(x) x P(x) Q(x)() (x) x(x) (x) x(x) x(x) x(x) (x) x(x) x(x) x(x) 4. 含有量詞的一般謂詞公式的等價公式和永真蘊含式5.含有量詞的特殊的謂詞公式的等價式和永真蘊含式(

3、1) 消去量詞定律設個體域為：S= a1, a2 , , an ，則： xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) (2) 量詞轉換律 xP(x) xP(x) xP(x) xP(x) 證明：xP(x) xP(x) 設個體域為： S= a1 , a2 , , an xP(x) ( P(a1) P(a2) P(an) ) P(a1) P(a2) P(an) xP(x)量化命題與非量化命題的的否定形式例： 否定下列命題： (a) 上海是一個小城鎮(zhèn) A(s) (b) 每一個自然數(shù)都是偶數(shù) x( N(x)E(x) )上述二命題的否定為： (a) 上海不

4、是一個小城鎮(zhèn) A(s) (b) 有一些自然數(shù)不是偶數(shù) x ( N(x) E(x) )其否定為：x( N(x)E(x) ) x( N(x)E(x) ) x( N(x)E(x) ) x ( N(x) E(x) )每一個自然數(shù)都是偶數(shù) x( N(x)E(x) )結論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定不但對動詞進行否定而且對量詞同時進行否定，其方法是： x的否定變?yōu)閤 ， x的否定變?yōu)閤 。量詞轉換律的推廣應用: xyP(x,y,z) xyP(x,y,z) 解釋：xyP(x,y,z) x yP(x,y,z) xyP(x,y,z) (3) 量詞轄域的擴張及其收縮律 xA(x) P

5、 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的任何謂詞公式。證明： xA(x) P x(A(x) P)設個體域為： S = a1 , a2 , , an xA(x) P ( A(a1) A(a2) A(an) ) P ( A(a1) P ) ( A(a2)P ) ( A(an) P ) x( A(x) P ) 下面的等價公式也是成立的：xA(x)B x(A(x)B) xA(x)B x(A(x)B)AxB(x) x(AB (x)A x B(x) x(AB (x)注：A,B為不含

6、有變元x的任何謂詞公式證明：xA(x)B x(A(x)B) xA(x)B xA(x) B x A(x) B x ( A(x) B ) x( A(x)B )(4) 量詞分配律x( A(x) B(x) ) xA(x) xB(x)x ( A(x) B(x) ) xA(x) xB(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) ) xA(x) xB(x) x( A(x) B(x) )證明: x( A(x) B(x) ) xA(x) xB(x)設個體域為： S = a1 , a2 , ,

7、 an x( A(x)B(x) ) ( A(a1) B(a1) ) . ( A(an) B(an) ) ( A(a1) A(an) ) ( B(a1) B(an) ) xA(x) x B(x)(5) 量詞的轉換xP(x) xP(x)(6) 含有多個量詞的謂詞公式的等價式 在含有多個量詞的謂詞公式中, 相同量詞間的次序是可以任意調(diào)動的，不會影響命題的真值。 xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y)不同量詞間的次序則不能隨意調(diào)動。所以若謂詞公式中出現(xiàn)多個不同量詞，則按照從左到右的次序讀出，不能顛倒次序。 例： yx(xy-2)表示: 任何y均存在x，使得xy-2。 例

8、：設A(x,y)表示x和y同姓，個體域x是甲組的人，個體域y是乙組的人。則：xyA(x,y)表示對于甲組所有的人，乙組都有人和他同姓。yx A(x,y)表示存在一個乙組的人，甲組所有的人和他同姓。 注：量詞出現(xiàn)的次序直接關系到命題的含義。例：設個體域是整數(shù)集，則下列命題的真值為真的是:A y x(xy=1) B x y (xy0)C x y (xy=y2)( C )5 前束范式定義一個公式，如果量詞均非否定地位于全式的開頭，它們的作用域延伸到整個公式的末尾，則稱此公式為前束范式。例： xyz( Q(x,y) R(z) (前束范式) x(x)(x) (不是前束范式) x(x)(x) (不是前束范式) 定理 任何一個謂詞公式都存在和它等價的前束范式。如何將謂詞公式轉換為前束范式轉換方法： 利用量詞轉換把深入到原子謂詞公式前 利用量詞轄域的擴張收縮定律,把量詞移到全式的最前面，這樣一定可得到等價的前束范式。利用約束變元的改名