1、陳瑜,Email： 2020年9月4日星期五,離散數(shù)學(xué),計(jì)算機(jī)學(xué)院,2020/9/4,計(jì)算機(jī)學(xué)院,2/39,主要內(nèi)容,1.謂詞公式的蘊(yùn)涵,2020/9/4,計(jì)算機(jī)學(xué)院,3/39,2.4 謂詞公式的蘊(yùn)涵,一.謂詞公式的蘊(yùn)涵 定義2.16：設(shè)A和B是以為D論域的兩個(gè)謂詞公式,如果在任一解釋下,當(dāng)公式A取值真(1)時(shí),公式B也取值真(1),則稱(chēng)A蘊(yùn)涵B,記作AB。 例4-1：設(shè)P(x)是以D為論域的謂詞公式，證明: 證明：因?yàn)樵谀骋唤忉屜?，?dāng)x=a，P(a)=1時(shí)，公式1右邊在該解釋下也取值1。同理，當(dāng)在某解釋下公式2的左邊取值1時(shí)，則對(duì)任何xD，P(x)也在這個(gè)解釋下取值1。,2020/9/4,計(jì)

2、算機(jī)學(xué)院,4/39,2.4 謂詞公式的蘊(yùn)涵,一.謂詞公式的蘊(yùn)涵 定義2.16：設(shè)A和B是以為D論域的兩個(gè)謂詞公式,如果在任一解釋下,當(dāng)公式A取值真(1)時(shí),公式B也取值真(1),則稱(chēng)A蘊(yùn)涵B,記作AB。 例4-1：設(shè)P(x)是以D為論域的謂詞公式，證明: 證明：因?yàn)樵谀骋唤忉屜?，?dāng)x=a，P(a)=1時(shí)，公式1右邊在該解釋下也取值1。同理，當(dāng)在某解釋下公式2的左邊取值1時(shí)，則對(duì)任何xD，P(x)也在這個(gè)解釋下取值1。,2020/9/4,計(jì)算機(jī)學(xué)院,5/39,2.4 謂詞公式的蘊(yùn)涵,定理2.8： A B iif A B是永真式。(略) 例4-2：證明P(x)（x）P(x)和（x）P(x)P(x)

3、是永真式。 證明： 由前面例子可知P(x) （x）P(x)，由定理2.8知P(x)（x）P(x)是永真式；實(shí)際上，當(dāng)在某解釋下P(x)取值1時(shí)，（x）P(x)也取值 1；若P(x)取值0時(shí)，無(wú)論（x）P(x)取什么值， P(x)（x）P(x)都取值1，所以是永真式。同理，（x）P(x)P(x)也是永真式。,2020/9/4,計(jì)算機(jī)學(xué)院,6/39,2.4 謂詞公式的蘊(yùn)涵,定理2.8： A B iif A B是永真式。 例4-2：證明P(x)（x）P(x)和（x）P(x)P(x)是永真式。 證明： 由前面例子可知P(x) （x）P(x)，由定理2.8知P(x)（x）P(x)是永真式；實(shí)際上，當(dāng)在某

4、解釋下P(x)取值1時(shí)，（x）P(x)也取值 1；若P(x)取值0時(shí)，無(wú)論（x）P(x)取什么值， P(x)（x）P(x)都取值1，所以是永真式。同理，（x）P(x)P(x)也是永真式。,2020/9/4,計(jì)算機(jī)學(xué)院,7/39,2.4 謂詞公式的蘊(yùn)涵,定理2.8： A B iif A B是永真式。 例4-2：證明P(x)（x）P(x)和（x）P(x)P(x)是永真式。 證明： 由前面例子可知P(x) （x）P(x)，由定理2.8知P(x)（x）P(x)是永真式；實(shí)際上，當(dāng)在某解釋下P(x)取值1時(shí)，（x）P(x)也取值 1；若P(x)取值0時(shí)，無(wú)論（x）P(x)取什么值， P(x)（x）P(x

5、)都取值1，所以是永真式。同理，（x）P(x)P(x)也是永真式。,2020/9/4,計(jì)算機(jī)學(xué)院,8/39,2.4 謂詞公式的蘊(yùn)涵,定理2.8： A B iif A B是永真式。 例4-2：證明P(x)（x）P(x)和（x）P(x)P(x)是永真式。 證明： 由前面例子可知P(x) （x）P(x)，由定理2.8知P(x)（x）P(x)是永真式；實(shí)際上，當(dāng)在某解釋下P(x)取值1時(shí)，（x）P(x)也取值 1；若P(x)取值0時(shí)，無(wú)論（x）P(x)取什么值， P(x)（x）P(x)都取值1，所以是永真式。同理，（x）P(x)P(x)也是永真式。,2020/9/4,計(jì)算機(jī)學(xué)院,9/39,2.4 謂詞

6、公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),注意：與E36的差異？ 36： （x）（）(P(x)Q()（x）P(x)（x）Q(x),2020/9/4,計(jì)算機(jī)學(xué)院,10/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x

7、）(P(x)Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),證明: 當(dāng)在某解釋下，上式左邊取值1時(shí)，（x）P(x)取值1或者（x）Q(x)取值 1，即對(duì)所有xD，P(x)恒取值 1或者Q(x)恒取值1。由此可見(jiàn)，對(duì)所有xD， (P(x)Q(x)都取值1，從而（x）(P(x)Q(x)取值1。根據(jù)定義，蘊(yùn)含關(guān)系成立。,2020/9/4,計(jì)算機(jī)學(xué)院,11/39,2.4 謂詞公式的蘊(yùn)涵,

8、二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),注意：與E37的差異？ 37： （x）（）(P(x)Q()（x）P(x)（x）Q(x),2020/9/4,計(jì)算機(jī)學(xué)院,12/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)

9、Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),證明：當(dāng)在某解釋下使（x）(P(x)Q(x)取值1時(shí)，必有客體cD使得(P(c)Q(c)=1，從而（x）P(x)（x）Q(x)取值1， 蘊(yùn)含關(guān)系成立。,2020/9/4,計(jì)算機(jī)學(xué)院,13/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x）

10、(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),2020/9/4,計(jì)算機(jī)學(xué)院,14/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I

11、15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),證明：當(dāng)(x)(P(x)Q(x)取值1時(shí)，對(duì)任何xD，P(x)Q(x)都取值1。 這時(shí)又有兩種情況：其一，有某個(gè)xD使P(x)取值0，于是(x)P(x)取值0，從而(x)P(x)(x)Q(x)取值1；其二，對(duì)每個(gè)xD，P(x)都取值1，這時(shí)Q(x)也必須取值1，從而(x)P(x)和(x)Q(x)都取值1，即： (x)P(x)(x)Q(x)取值1。根據(jù)蘊(yùn)含定義得證。,2020/9/4,計(jì)算機(jī)學(xué)院,15/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I1

12、2: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),證明：當(dāng)(x)(P(x)Q(x)取值1時(shí)，對(duì)任何xD，P(x)Q(x)都取值1。 這時(shí)又有兩種情況：其一，有某個(gè)xD使P(x)取值0，于是(x)P(x)取值0，從而(x)P(x)(x)Q(x)取值1；其二，對(duì)每個(gè)xD，P(x)都取值1，這時(shí)Q(x)也必須取值1，從而(x)P(x)和(x)Q(x)都取值1，即： (x)P(x)(x)Q(x)取值1。

13、根據(jù)蘊(yùn)含定義得證。,2020/9/4,計(jì)算機(jī)學(xué)院,16/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),證明見(jiàn)下頁(yè),2020/9/4,計(jì)算機(jī)學(xué)院,17/39,補(bǔ)充：,I14 的證明1: （x）P(x)（x）Q(x) (（ x）P(x)（x）Q(x) （x）P(x

14、)（x）Q(x) （x）(P(x)Q(x) （I11） （x）( P(x)Q(x) I14 的證明2（按定義證明）: 設(shè)（x）P(x)（x）Q(x)在某個(gè)解釋下面取值為1，分二種情況： 1） （x）P(x)=1必有（x）Q(x)=1，即對(duì)xD， Q(x)=1 所以對(duì)xD， 無(wú)論P(yáng)(x)=1（=0），都有P(x)Q(x)的值為1， 即（x）( P(x)Q(x)在此解釋下面取值為1； 2） （x）P(x)=0，即對(duì)xD， P(x)=0 所以對(duì)xD， 無(wú)論Q(x)=1（=0），都有P(x)Q(x)的值為1， 即（x）( P(x)Q(x)在此解釋下面取值為1；,2020/9/4,計(jì)算機(jī)學(xué)院,18/39

15、,補(bǔ)充：,I14 的證明1: （x）P(x)（x）Q(x) （x）P(x)（x）Q(x) （x）P(x)（x）Q(x) （x）(P(x)Q(x) （x）( P(x)Q(x) I14 的證明2（按定義證明）: 設(shè)（x）P(x)（x）Q(x)在某個(gè)解釋下面取值為1，分二種情況： 1） （x）P(x)=1必有（x）Q(x)=1，即對(duì)xD， Q(x)=1 所以對(duì)xD， 無(wú)論P(yáng)(x)=1（=0），都有P(x)Q(x)的值為1， 即（x）( P(x)Q(x)在此解釋下面取值為1； 2） （x）P(x)=0，即對(duì)xD， P(x)=0 所以對(duì)xD， 無(wú)論Q(x)=1（=0），都有P(x)Q(x)的值為1， 即

16、（x）( P(x)Q(x)在此解釋下面取值為1；,P Q PQ 0 0 1 0 1 1 1 0 0 1 1 1,2020/9/4,計(jì)算機(jī)學(xué)院,19/39,補(bǔ)充：,I14 的證明1: （x）P(x)（x）Q(x) （x）P(x)（x）Q(x) （x）P(x)（x）Q(x) （x）(P(x)Q(x) （x）( P(x)Q(x) I14 的證明2（按定義證明）: 設(shè)（x）P(x)（x）Q(x)在某個(gè)解釋下面取值為1，分二種情況： 1） （x）P(x)=1必有（x）Q(x)=1，即對(duì)xD， Q(x)=1 所以對(duì)xD， 無(wú)論P(yáng)(x)=1（=0），都有P(x)Q(x)的值為1， 即（x）( P(x)Q(x

17、)在此解釋下面取值為1； 2） （x）P(x)=0，即存在一些xD使得P(x)=0，此時(shí)無(wú)論Q(x)取何值， P(x)Q(x)的值為1。又根據(jù)1）的證明可知，如果x的取值使得P(x)為1，那么P(x)Q(x)的值仍為1（因?yàn)榇藭r(shí)必有Q(x)=1）。 因此，綜上述，對(duì)xD， 都有P(x)Q(x)的值為1， 即（x）( P(x)Q(x)在此解釋下面取值為1；,P Q PQ 0 0 1 0 1 1 1 0 0 1 1 1,2020/9/4,計(jì)算機(jī)學(xué)院,20/39,2.4 謂詞公式的蘊(yùn)涵,二.謂詞演算中的蘊(yùn)涵式(蘊(yùn)涵定律) I11: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I12: （x

18、）(P(x)Q(x)（x）P(x)（x）Q(x) I13: (x)(P(x)Q(x)(x)P(x)(x)Q(x) I14: （x）P(x)（x）Q(x)（x）(P(x)Q(x) I15: (x)(P(x)Q(x)(x)P(x)(x)Q(x),2020/9/4,計(jì)算機(jī)學(xué)院,21/39,例4-3,1）設(shè)G(x)：x是高才生； H(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生 則： (x)G(x)(x)H(x)表示：“該班的所有學(xué)生是高才生或該班的所有學(xué)生是運(yùn)動(dòng)健將”； (x)(G(x)H(x)表示：“該班的所有學(xué)生是高才生或是運(yùn)動(dòng)健將”。 顯然，前者可推出后者，但反之則不然。 即有 I11:(x

19、)G(x)(x)H(x)(x)(G(x)H(x)。,2020/9/4,計(jì)算機(jī)學(xué)院,22/39,例4-3,1）設(shè)G(x)：x是高才生； H(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生 則： (x)G(x)(x)H(x)表示：“該班的所有學(xué)生是高才生或該班的所有學(xué)生是運(yùn)動(dòng)健將”； (x)(G(x)H(x)表示：“該班的所有學(xué)生是高才生或是運(yùn)動(dòng)健將”。 顯然，前者可推出后者，但反之則不然。 即有 I11:(x)G(x)(x)H(x)(x)(G(x)H(x)。,2020/9/4,計(jì)算機(jī)學(xué)院,23/39,例4-3,1）設(shè)G(x)：x是高才生； H(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生 則：

20、 (x)G(x)(x)H(x)表示：“該班的所有學(xué)生是高才生或該班的所有學(xué)生是運(yùn)動(dòng)健將”； (x)(G(x)H(x)表示：“該班的所有學(xué)生是高才生或是運(yùn)動(dòng)健將”。 顯然，前者可推出后者，但反之則不然。 即有： I11:(x)G(x)(x)H(x)(x)(G(x)H(x)。,2020/9/4,計(jì)算機(jī)學(xué)院,24/39,例4-3（續(xù)）,2)設(shè)G(x)：x是高才生； H(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生。 則： (x)(G(x)H(x)表示：“該班的一些學(xué)生既是高才生又是運(yùn)動(dòng)健將”； (x)G(x)(x)H(x)表示：“該班的一些學(xué)生是高才生且該班的一些學(xué)生是運(yùn)動(dòng)健將”。 顯然，前者可推

21、出后者，但反之則不然。 即有 I12:(x)(G(x)H(x)(x)G(x)(x)H(x),2020/9/4,計(jì)算機(jī)學(xué)院,25/39,例4-3（續(xù)）,2)設(shè)G(x)：x是高才生； H(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生。 則： (x)(G(x)H(x)表示：“該班的一些學(xué)生既是高才生又是運(yùn)動(dòng)健將”； (x)G(x)(x)H(x)表示：“該班的一些學(xué)生是高才生且該班的一些學(xué)生是運(yùn)動(dòng)健將”。 顯然，前者可推出后者，但反之則不然。 即有 I12:(x)(G(x)H(x)(x)G(x)(x)H(x),2020/9/4,計(jì)算機(jī)學(xué)院,26/39,例4-3（續(xù)）,2)設(shè)G(x)：x是高才生； H

22、(x)：x是運(yùn)動(dòng)健將。 其中：個(gè)體域是某班的學(xué)生。 則： (x)(G(x)H(x)表示：“該班的一些學(xué)生既是高才生又是運(yùn)動(dòng)健將”； (x)G(x)(x)H(x)表示：“該班的一些學(xué)生是高才生且該班的一些學(xué)生是運(yùn)動(dòng)健將”。 顯然，前者可推出后者，但反之則不然。 即有 I12:(x)(G(x)H(x)(x)G(x)(x)H(x),2020/9/4,計(jì)算機(jī)學(xué)院,27/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP

23、(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),2020/9/4,計(jì)算機(jī)學(xué)院,28/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),證明：如果xyP(x,y)取真值1，則對(duì)

24、所有x、yD，P(x，y)都取值1。特別對(duì)所有xD和某個(gè)確定客體y=cD，P(x，c)都取值1，也就是說(shuō)，存在客體y=cD使每個(gè)xD，P(x，c)均取值1。因此得證。,2020/9/4,計(jì)算機(jī)學(xué)院,29/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),（證明：由I16

25、可知）,2020/9/4,計(jì)算機(jī)學(xué)院,30/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),2020/9/4,計(jì)算機(jī)學(xué)院,31/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y

26、)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),證明：如果yxP(x,y)取真值1，則必有某個(gè)確定客體y=cD使對(duì)所有xD，P(x，c)均取值1。這就是說(shuō)，對(duì)任何xD都存在同一個(gè)cD使P(x，y)取值1，因此此蘊(yùn)含式成立。,2020/9/4,計(jì)算機(jī)學(xué)院,32/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP

27、(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),（證明：由I19可知）,2020/9/4,計(jì)算機(jī)學(xué)院,33/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,y)xyP(x,y) I23 :yxP(x,y)yxP(x,y),2020/9/4,計(jì)算機(jī)學(xué)院,34/39,三.兩個(gè)量詞的蘊(yùn)涵式 I16 :xyP(x,y)yxP(x,y) I17 :yxP(x,y)xyP(x,y) I18 :yxP(x,y)xyP(x,y) I19 :xyP(x,y)yxP(x,y) I20 :xyP(x,y)yxP(x,y) I21 :yxP(x,y)xyP(x,y) I22 :xyP(x,