離散數(shù)學(第4講)

1、馮偉森馮偉森Email：2021年年12月月23日星期四日星期四2021-12-232021-12-23計算機學院計算機學院2 2主要內容主要內容 1 1、聯(lián)結詞的完備集、聯(lián)結詞的完備集 2 2、命題公式的蘊涵、命題公式的蘊涵 1 1）九類蘊涵關系）九類蘊涵關系 2 2）蘊涵關系的基本性質）蘊涵關系的基本性質1.4 1.4 聯(lián)結詞的完備集聯(lián)結詞的完備集2021-12-232021-12-23計算機學院計算機學院3 3 前面我們已經(jīng)介紹了最常見的前面我們已經(jīng)介紹了最常見的6 6種邏輯聯(lián)結種邏輯聯(lián)結詞。他們都和自然語言中使用的聯(lián)結詞緊密相關，詞。他們都和自然語言中使用的聯(lián)結詞緊密相關，易于理解。不

2、同聯(lián)結詞產(chǎn)生的真值表是互不相同易于理解。不同聯(lián)結詞產(chǎn)生的真值表是互不相同的，的，根據(jù)對含兩個命題變元的公式的解釋方式看，根據(jù)對含兩個命題變元的公式的解釋方式看，共有共有2 2* *2=42=4種不同的解釋種不同的解釋，因而，因而公式的真值表相公式的真值表相應有應有2 2* *2 2* *2 2* *2=162=16種可能結果。種可能結果。對其中每一種真值對其中每一種真值表都應該存在相應的聯(lián)結詞。下面從真值表取值表都應該存在相應的聯(lián)結詞。下面從真值表取值情況的角度定義幾個新的聯(lián)結詞。情況的角度定義幾個新的聯(lián)結詞。2021-12-232021-12-23計算機學院計算機學院4 4P P Q Q1

3、1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 13 14 15 13 14 15 16161 1 1 11 1 0 00 0 1 10 0 0 01 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 0 1 1 1 0 0

4、 1 0 1 1 1 0 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0QPQPPQPQP P Q QP PQ QP P Q Q Q QP PPQPQQ QT T F F 下面是含兩個命題變元的所有公式的真值表所能取下面是含兩個命題變元的所有公式的真值表所能取得的情況：得的情況：2021-12-232021-12-23計算機學院計算機學院5 5P QP QPQPQ1 11 11 01 00 10 10 00 00 01 11 11 1定義定義 1.141.14 設設P P和和Q Q是命題公式，分別稱是命題公式，分別稱PQPQ和和PQPQ為為“與非與非”和和“或非或非”命題

5、公式。其相應的命題公式。其相應的真值表如下所示：真值表如下所示： 2021-12-232021-12-23計算機學院計算機學院6 6P QP QPQPQ1 11 11 01 00 10 10 00 00 00 00 01 1由真值表可以看出由真值表可以看出P PQ Q（P PQ Q）, , P PQ Q （P PQ Q）2021-12-232021-12-23計算機學院計算機學院7 7 根據(jù)聯(lián)結詞根據(jù)聯(lián)結詞和和的定義，不難證明下面的的定義，不難證明下面的等價式。等價式。 PPPP（PPPP）P P ( PQ)( PQ) ( PQ)( PQ) ( PQ) ( PQ) P PQQ ( PP)(QQ

6、) ( PP)(QQ) PPQ Q （PPQ Q）P PQQ PP PP（PPPP）P P ( PQ) ( PQ) ( PQ) ( PQ) ( PQ) ( PQ) P PQQ ( PP) (QQ) ( PP) (QQ) PPQ Q （PPQ Q）P PQQ2021-12-232021-12-23計算機學院計算機學院8 8這些等價式告訴我們，這些等價式告訴我們，可由可由和表和表示出來，示出來，可由可由和表示出來，反過和表示出來，反過來，來，和和都可以單獨表示出所有已知都可以單獨表示出所有已知聯(lián)結詞，它們的這一性質使得聯(lián)結詞，它們的這一性質使得在邏輯電在邏輯電路設計中只用一種門式電路元件就能實路設

7、計中只用一種門式電路元件就能實現(xiàn)任何電路功能，現(xiàn)任何電路功能，當然，元件的數(shù)量通當然，元件的數(shù)量通常也顯得更多。常也顯得更多。2021-12-232021-12-23計算機學院計算機學院9 9還有一個二元聯(lián)結詞還有一個二元聯(lián)結詞“ “ ”, ,稱為稱為條件否定條件否定，可以用下面的真值表定義：可以用下面的真值表定義：P QP QP P Q Q1 11 11 01 00 10 10 00 0 0 0 1 1 0 0 0 0顯然，顯然，P P Q Q(PQ)(PQ)2021-12-232021-12-23計算機學院計算機學院1010P P Q Q1 2 3 4 5 6 7 8 9 10 11 12

8、 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 1 1 11 1 0 00 0 1 10 0 0 01 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 01 0 0

9、 1 1 1 0 0 1 0 1 1 1 0 0 0 至此我們定義了至此我們定義了9 9個聯(lián)結詞，其中個聯(lián)結詞，其中1 1個一元個一元聯(lián)結詞，聯(lián)結詞，8 8個二元聯(lián)結詞。那么，還能不能定個二元聯(lián)結詞。那么，還能不能定義出新的聯(lián)結詞呢？下面是含兩個命題變元的義出新的聯(lián)結詞呢？下面是含兩個命題變元的所有公式的真值表所能取得的情況：所有公式的真值表所能取得的情況：2021-12-232021-12-23計算機學院計算機學院1111 顯然公式顯然公式1 1是永真式，是永真式，2 2代表矛盾式，代表矛盾式，3 3代表代表Q Q，4 4代表代表QP,5QP,5代表代表PQPQ，6 6代表代表PQPQ， 7

10、 7是是P P，8 8是是Q Q，9 9代表代表P PQ Q，1010代表代表P P Q Q，1111代表代表Q Q，1212代表代表P P，1313代表代表PQPQ，1414代表代表Q Q P,15P,15代代表表P P Q Q，1616代表代表PQPQ，可見，已定義的，可見，已定義的9 9個聯(lián)個聯(lián)結詞就是全部可以定義的聯(lián)結詞。結詞就是全部可以定義的聯(lián)結詞。 2021-12-232021-12-23計算機學院計算機學院1212 定義定義 1.15 1.15 設設S S 是由某些聯(lián)結詞構成的集合，是由某些聯(lián)結詞構成的集合，如果每個邏輯聯(lián)結詞的功能都能夠由如果每個邏輯聯(lián)結詞的功能都能夠由S S中

11、的聯(lián)結中的聯(lián)結詞實現(xiàn)，則稱詞實現(xiàn)，則稱S S是聯(lián)結詞的一個是聯(lián)結詞的一個功能完備集功能完備集；進；進一步，如果去掉一步，如果去掉S S中的任何一個聯(lián)結詞后，至少中的任何一個聯(lián)結詞后，至少有一個聯(lián)結詞的功能不能由有一個聯(lián)結詞的功能不能由S S中剩余的聯(lián)結詞實中剩余的聯(lián)結詞實現(xiàn)時，則稱現(xiàn)時，則稱S S是邏輯聯(lián)結詞的一個是邏輯聯(lián)結詞的一個最小功能完備最小功能完備集集。2021-12-232021-12-23計算機學院計算機學院1313 根據(jù)定義根據(jù)定義, ,我們知道我們知道 、 是最小的功是最小的功能完備集能完備集，那么，那么 ， 是不是最小功能是不是最小功能完備集？由于完備集？由于P PQ Q(

12、(P PQ)Q)，可見，可見可可由由 ， 表達；同理表達；同理, P, PQ Q( (P PQ) ,Q) ,因而因而可由可由 ， 表達，這說明表達，這說明 ， 不是最小功能完備集，但是不是最小功能完備集，但是 在實際應用中，在實際應用中，普普遍采用的功能完備集卻是遍采用的功能完備集卻是 , , , , ,這也是邏這也是邏輯系統(tǒng)中最主要的輯系統(tǒng)中最主要的3 3個常用聯(lián)結詞。個常用聯(lián)結詞。2021-12-232021-12-23計算機學院計算機學院14141 16 6 命題公式的蘊涵命題公式的蘊涵 定義定義1.18 1.18 設設A A和和B B是兩個合適公式，如果在是兩個合適公式，如果在任何解釋

13、任何解釋下，下，A A取值取值1 1時時B B也取值也取值1 1，則稱公式，則稱公式A A蘊涵公式蘊涵公式B B，并記，并記A A B B。 定理定理1.111.11 A AB iff ABB iff AB為永真式。為永真式。 注意注意：蘊含和條件聯(lián)結詞：蘊含和條件聯(lián)結詞是完全不同的。是完全不同的。 是命題聯(lián)結詞，是命題聯(lián)結詞，ABAB是一個命題公式；是一個命題公式； 是是公式間關系符公式間關系符，A AB B不是一個命題公式，不是一個命題公式，僅表示僅表示A A，B B間的蘊含關系。間的蘊含關系。2021-12-232021-12-23計算機學院計算機學院1515基本蘊含（關系）式（蘊含定律

14、）基本蘊含（關系）式（蘊含定律） I I1 1：PQ PQ P P ， PQPQQ Q I I2 2: : （PQPQ）P P ，（，（PQPQ）Q Q I I3 3：P PPQ PQ ， Q QPQ PQ I I4 4：P PPQ PQ ， Q QPQ PQ II5 5：P P（PQPQ） Q Q 假言推論假言推論II6 6：Q Q（PQPQ） P P 拒取式（否定式假言推論）拒取式（否定式假言推論）II7 7：PP（PQPQ） Q Q 析取三段論析取三段論II8 8：（：（PQPQ）（QRQR） PR PR 假言三段論假言三段論擴充法則擴充法則簡化簡化法則法則2021-12-232021-

15、12-23計算機學院計算機學院1616基本蘊含（關系）式（續(xù)）基本蘊含（關系）式（續(xù)）II9 9：（：（PQPQ）（PRPR）（QRQR） R R 二難推論二難推論 I I1010： （PQPQ）（RSRS）（PRPR）（QSQS）II1111：（：（P PQ Q）（Q QR R） P PR R 等價三段論等價三段論II1212：（PQPQ）（PRPR） QRQR 歸結原理歸結原理 解釋：（解釋：（PQPQ）（PRPR） QR QR 2021-12-232021-12-23計算機學院計算機學院1717蘊含關系的性質蘊含關系的性質 自反性自反性 A A A A 反對稱性反對稱性: : 如果如果A

16、 A B B，B B A A， iff A iff A B B A A B B 且且A A為永真式，則為永真式，則B B必為永真式必為永真式2021-12-232021-12-23計算機學院計算機學院1818 傳遞性，如果傳遞性，如果A A B B，B B C C，則，則A A C C【證明證明】 由已知條件由已知條件A A B B，且，且 B B C C， 根據(jù)根據(jù)定理定理1.111.11 (AB(AB）（BCBC） 是永真式；是永真式； 再由假言三段論，應有再由假言三段論，應有 （ABAB）（BCBC） AC AC ； 再根據(jù)性質再根據(jù)性質3 3， ACAC也必是永真式，也必是永真式， 即

17、即A A C C 。2021-12-232021-12-23計算機學院計算機學院1919。 如如A A B B，A A C C， iffiff A A BC BC【證明】【證明】“” 由由 A AB B 且且 A AC C得到得到A AB B和和A AC C都是永真式，于是都是永真式，于是（A AB B）（A AC C）也是永真式；但是，）也是永真式；但是，（A AB B）（A AC C）（ABAB）( (AC)AC)A(BC)A(BC)A A(BC)(BC)，所以所以A A(B(BC)C)是永真式，即是永真式，即A AB BCC。2021-12-232021-12-23計算機學院計算機學院2

18、020“”從證明過程看，性質從證明過程看，性質5 5反過來也對，即由反過來也對，即由 A AB BCC可以得到可以得到A AB B 且且 A AC C 。 如如A A B B，C C B B，則，則AC AC B B AB AB C C iffiff A A BC BC 該性質是推理演繹中該性質是推理演繹中CPCP規(guī)則的基礎規(guī)則的基礎 A A B B iffiff A AB B是矛盾式是矛盾式 該性質是反證法的基礎該性質是反證法的基礎2021-12-232021-12-23計算機學院計算機學院2121定理定理1.121.12 A AB B iff iff B BA A 該定理提供了逆向思維的基

19、礎該定理提供了逆向思維的基礎2021-12-232021-12-23計算機學院計算機學院2222例例1-6.11-6.1考慮以下語句，并將其前提和結論符號化?？紤]以下語句，并將其前提和結論符號化。 1)1)、前提：、前提： 1. 1. 如果明天天晴，我們準備外出旅游。如果明天天晴，我們準備外出旅游。PQPQ 2 2明天的確天晴。明天的確天晴。P P 結論：我們外出旅游。結論：我們外出旅游。Q Q 上述例子可描述為：上述例子可描述為：PQPQ，P PQ Q( (假言推論假言推論) ) 2)2)、前提：、前提： 1.1.如果一個人是單身漢，則他不幸福。如果一個人是單身漢，則他不幸福。PQPQ 2.2.如果一個人不幸福，則他死得早。如果一個人不幸福，則他死得早。 QRQR 結論：單身漢死得早。結論：單身漢死得早。 PRPR 上述例子可描述為：上述例子可描述為：PQPQ，QRQRPRPR( (假言三段論假言三段論) )2021-12-232021-12-23計算機學院計算機學院2323例例1-6.1(1-6.1(續(xù)續(xù)1)1) 3)3)、某女子在某日晚歸家途中被殺害，據(jù)多方調查確證，、某女子在某日晚歸家途中被殺害，據(jù)多方調查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工兇手必為王某或陳某，但后又查證，作案之