離散數(shù)學(xué)第二章(第2講)課件

1、4 謂詞演算的等價(jià)式與蘊(yùn)含式1、謂詞公式的等價(jià)定義A，B為二個(gè)謂詞公式，E為它們共同個(gè)體域，若對(duì)A和B的任一組變?cè)M(jìn)行賦值，使得A和B的值相同，則稱A和B在個(gè)體域E上是互為等價(jià)的，記為AB EB或 A定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變?cè)概蒃中的每一個(gè)客體所得命題的值均為真，則稱A在E中是永真的。若E為任意域則稱A是永真的。2、謂詞公式的分類定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變?cè)概蒃中的每一個(gè)客體所得命題的值均為假，則稱A在E中是永假的。若E為任意域則稱A是永假的。定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變?cè)概蒃中每一個(gè)客體，在E中存在一些客體，使得指

2、派后的真值為真，則A稱是可滿足的。3.不含量詞的謂詞公式的等價(jià)公式和永真蘊(yùn)含式 只要用原子謂詞公式去代替命題邏輯中等價(jià)公式和永真蘊(yùn)含式中的原子命題變?cè)瑒t可獲得謂詞演算中的等價(jià)公式和永真蘊(yùn)含式。 命題邏輯 謂詞邏輯 (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. 含有量詞的一般謂詞公式的等價(jià)公式和永真蘊(yùn)含式5.含有量詞的特殊的謂詞公式的等價(jià)式和永真蘊(yùn)含式(

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

4、是一個(gè)小城鎮(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) )每一個(gè)自然數(shù)都是偶數(shù) x( N(x)E(x) )結(jié)論：對(duì)于非量化命題的否定只需將動(dòng)詞否定，而對(duì)于量化命題的否定不但對(duì)動(dòng)詞進(jìn)行否定而且對(duì)量詞同時(shí)進(jìn)行否定，其方法是： x的否定變?yōu)閤 ， x的否定變?yōu)閤 。量詞轉(zhuǎn)換律的推廣應(yīng)用: xyP(x,y,z) xyP(x,y,z) 解釋：xyP(x,y,z) x yP(x,y,z) xyP(x,y,z) (3) 量詞轄域的擴(kuò)張及其收縮律 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為不含有變?cè)獂的任何謂詞公式。證明： xA(x) P x(A(x) P)設(shè)個(gè)體域?yàn)椋?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 ) 下面的等價(jià)公式也是成立的：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、有變?cè)獂的任何謂詞公式證明：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)設(shè)個(gè)體域?yàn)椋?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) 量詞的轉(zhuǎn)換xP(x) xP(x)(6) 含有多個(gè)量詞的謂詞公式的等價(jià)式 在含有多個(gè)量詞的謂詞公式中, 相同量詞間的次序是可以任意調(diào)動(dòng)的，不會(huì)影響命題的真值。 xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y)不同量詞間的次序則不能隨意調(diào)動(dòng)。所以若謂詞公式中出現(xiàn)多個(gè)不同量詞，則按照從左到右的次序讀出，不能顛倒次序。 例： yx(xy-2)表示: 任何y均存在x，使得xy-2。 例

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