離散數(shù)學(xué)1-5,1-6

1、離散數(shù)學(xué)離散數(shù)學(xué)Discrete Mathematics陳明陳明Email:mingchen_信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院二零一三年九月二零一三年九月離散數(shù)學(xué)離散數(shù)學(xué)課程回顧第第1次課：次課：命題；命題；5個聯(lián)結(jié)詞個聯(lián)結(jié)詞第第2次課：次課：命題的翻譯命題的翻譯命題公式等價的兩種證明方法命題公式等價的兩種證明方法真值表真值表利用命題定律推導(dǎo)利用命題定律推導(dǎo)離散數(shù)學(xué)離散數(shù)學(xué)合式公式合式公式：命題演算的合式公式：命題演算的合式公式(wff) 規(guī)定為：規(guī)定為： (1)單個命題變元本身是一個合式公式。單個命題變元本身是一個合式公式。 (2)如果如果A是合式公式，那么是合式公式，那么A是合式公式。

2、是合式公式。 (3)如果如果A和和B是合式公式，那么是合式公式，那么(AB)，(AB)，(AB）和和(A B)都是合式公式。都是合式公式。 (4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)、(2)、(3)所得到的包含命所得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。 翻譯翻譯 把自然語言中的有些語句，翻譯成數(shù)理邏輯中的把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式。符號形式。 優(yōu)先次序優(yōu)先次序 規(guī)定聯(lián)結(jié)詞運算的優(yōu)先次序為：規(guī)定聯(lián)結(jié)詞運算的優(yōu)先次序為：、離散數(shù)學(xué)離散數(shù)學(xué) 真值表真值表 在命題公式中，對于分量指派真值的各種可能組合，就確

3、定在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。 邏輯相等邏輯相等 給定兩個命題公式給定兩個命題公式A和和B，設(shè)，設(shè)P1，P2，Pn為所有出現(xiàn)為所有出現(xiàn)于于A和和B中的原子變元，若給中的原子變元，若給P1，P2，Pn任一組真值指派，任一組真值指派，A和和B的真的真值都相同，則稱值都相同，則稱A和和B是等價的或邏輯相等。記作是等價的或邏輯相等。記作A B。 子公式子公式如果如果X是合式公式是合式公式A的一部分，且的一部分，且X本身也是一個合式公式，則本身也是一

4、個合式公式，則稱稱X為公式為公式A的子公式。的子公式。 定理定理1-4.1 設(shè)設(shè)X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果將，如果將A中的中的X用用Y來置換，所得到公式來置換，所得到公式B與公式與公式A等價，即等價，即A B。 10個命題定律。個命題定律。離散數(shù)學(xué)離散數(shù)學(xué)對合律P P1冪等律PP P，PP P2結(jié)合律(PQ）R P（QR）(PQ）R P（QR）3交換律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT P8零律PT T，PF F9否

5、定律PP T，PP F10PQ PQ表表1-4.8離散數(shù)學(xué)離散數(shù)學(xué)化簡如下語句：化簡如下語句：“情況并非如此：若他不來，則我不去情況并非如此：若他不來，則我不去”。 離散數(shù)學(xué)離散數(shù)學(xué)解：首先符號化上述語句。解：首先符號化上述語句。 設(shè)設(shè)P：他來。：他來。Q：我去：我去 則原句：則原句：（PQ） 然后化簡上述命題公式然后化簡上述命題公式 （PQ） （ P Q ） P Q即：我去了，但他未來。即：我去了，但他未來。 離散數(shù)學(xué)離散數(shù)學(xué) P：上午下雨，：上午下雨，Q：我去看電影，：我去看電影，R：我在家看書；：我在家看書；S：我在家看報：我在家看報。（P Q） （P （R S ）P12：（：（7）a）

6、離散數(shù)學(xué)離散數(shù)學(xué) 1-5 重言式與蘊含式重言式與蘊含式 1-6 其他聯(lián)結(jié)詞其他聯(lián)結(jié)詞離散數(shù)學(xué)離散數(shù)學(xué)一、重言式和矛盾式一、重言式和矛盾式 從上節(jié)真值表和命題的等價公式推證中可以看到，有從上節(jié)真值表和命題的等價公式推證中可以看到，有些命題公式，無論對分量作何種指派，其對應(yīng)的真值些命題公式，無論對分量作何種指派，其對應(yīng)的真值都為都為T （見（見14頁表頁表1-4.4）或都為）或都為F（見（見13頁表頁表1-4.2）。）。PQPQ(PQ)PQPQ(PQ） PQTT T F F F F TTF F T F TT TFT F T T FT TFF F T T TT T表表1-4.4離散數(shù)學(xué)離散數(shù)學(xué) 表表

7、 1-4.2 PQ PQP(PQ）PTT T F FTF F F FFT F T FFF F T F離散數(shù)學(xué)離散數(shù)學(xué) 重言式和矛盾式這兩類特殊的命題公式在今后重言式和矛盾式這兩類特殊的命題公式在今后的命題演算中極為有用。的命題演算中極為有用。 定義定義1-5.1 給定一命題公式，若無論對分量作怎樣給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為的指派，其對應(yīng)的真值永為T，則稱該命題公式為，則稱該命題公式為重言式或永真公式重言式或永真公式。定義定義1-5.2 給定一命題公式，若無論對分量作怎樣給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為的指派，其對應(yīng)的真值永為F，則稱該命

8、題公式為，則稱該命題公式為矛盾式或永假公式矛盾式或永假公式。離散數(shù)學(xué)離散數(shù)學(xué)證明證明 由于重言式的真值與分量的指派無關(guān)，故對同一分由于重言式的真值與分量的指派無關(guān)，故對同一分量以任何合式公式置換后，重言式的真值仍永為量以任何合式公式置換后，重言式的真值仍永為T。 定理定理1-5.2 一個重言式，對同一分量都用一個重言式，對同一分量都用任何合式公式置任何合式公式置換換，其結(jié)果仍為一重言式。，其結(jié)果仍為一重言式。 證明證明 設(shè)設(shè)A和和B為兩個重言式，則不論為兩個重言式，則不論A和和B的分量指派任的分量指派任何真值，總有何真值，總有A為為T，B為為T，故，故ABT，ABT。 定理定理1-5.1 任何

9、兩個重言式的合取或析取，仍然是一個重任何兩個重言式的合取或析取，仍然是一個重言式。言式。對于矛盾式也有類似于定理對于矛盾式也有類似于定理1-5.1和定理和定理1-5.2的結(jié)果。的結(jié)果。離散數(shù)學(xué)離散數(shù)學(xué)例題例題1 證明證明(PS)R)V(PS)R)為重言式。為重言式。證明證明 因為因為PVPT， 如以如以(PS)R)置換置換P即得即得 (PS)R)V(PS)R) T離散數(shù)學(xué)離散數(shù)學(xué) 重點將研究重言式重點將研究重言式，因為重言式的否定是矛盾式，因為重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。矛盾式的否定是重言式，這樣只研究其一就可以了。 重言式最有用，它有以下特點：重言式最

10、有用，它有以下特點：兩重言式的合取式、析取式、條件式和雙條件式等兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。雜的重言式。 由重言式使用公認的規(guī)則可以產(chǎn)生許多有用由重言式使用公認的規(guī)則可以產(chǎn)生許多有用等價式等價式和和蘊涵式蘊涵式。離散數(shù)學(xué)離散數(shù)學(xué)給定一命題公式，至少存在一個指派，公式相應(yīng)確定給定一命題公式，至少存在一個指派，公式相應(yīng)確定真值為真，稱為真值為真，稱為可滿足式可滿足式。重言式必是可滿足式，反之一般不真。重言式必是可滿足式，反之一般不真。判定給定公式是否為永真式、永假式或可滿足式的問判定

11、給定公式是否為永真式、永假式或可滿足式的問題，稱為題，稱為給定公式的判定問題給定公式的判定問題。在命題邏輯中，由于任何一個命題公式的指派數(shù)目總在命題邏輯中，由于任何一個命題公式的指派數(shù)目總是有限的，所以命題邏輯的判定問題是可解的。其判是有限的，所以命題邏輯的判定問題是可解的。其判定方法有定方法有真值表法真值表法和和公式推演法公式推演法。證明重言式的方法證明重言式的方法離散數(shù)學(xué)離散數(shù)學(xué) 定理定理1-5.3 設(shè)設(shè)A、B為兩個命題公式，為兩個命題公式，A B當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)A B為一個重言式。為一個重言式。 證明證明 若若AB，則，則A、B有相同真值，即有相同真值，即A B永為永為T。 若若A B為

12、重言式，則為重言式，則A B永為永為T，故，故A、B的真的真值相同，即值相同，即AB。 定理定理1-5.3的作用：為的作用：為A B又提供了一種方法。又提供了一種方法。其他方法：其他方法：（1）真值表法）真值表法（2）利用命題定律推導(dǎo)證明）利用命題定律推導(dǎo)證明 定理定理1-5.3 設(shè)設(shè)A、B為兩個命題公式，為兩個命題公式，A B當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)A B為一個重言式。為一個重言式。 證明證明 若若AB，則，則A、B有相同真值，即有相同真值，即A B永為永為T。 若若A B為重言式，則為重言式，則A B永為永為T，故，故A、B的真的真值相同，即值相同，即AB。 離散數(shù)學(xué)離散數(shù)學(xué)例題例題2 證明證明(

13、PQ）（PQ）證明：據(jù)定理證明：據(jù)定理1-5.3 ，只需證：，只需證：(PQ） （PQ）為重言式。為重言式。PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T離散數(shù)學(xué)離散數(shù)學(xué)聯(lián)結(jié)詞聯(lián)結(jié)詞 可用可用來表達。由第來表達。由第4節(jié)例題節(jié)例題5可知：可知：A B (AB)(BA) 下面討論下面討論AB的重言式。的重言式。1.定義定義定義定義1-5.3 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱是一個重言式時，我們稱“P蘊含蘊含Q”，并記作，并記作P Q。二、蘊含式二、蘊含式離散數(shù)學(xué)離散數(shù)學(xué)2. 蘊含

14、式的證明方法：蘊含式的證明方法：(1)列真值表法：列真值表法：根據(jù)定義，根據(jù)定義， 只需證只需證PQ是重言式是重言式(2)邏輯推論邏輯推論前真看后真前真看后真后假看前假后假看前假(3)等價置換等價置換離散數(shù)學(xué)離散數(shù)學(xué) 例題例題3 證明證明P PQ 證明證明 列出真值表：列出真值表： 從表中看出從表中看出PPQ是一是一個重言式，故個重言式，故P PQ成立。成立。P Q PQPPQT T T TT F T TF T T TF F F T離散數(shù)學(xué)離散數(shù)學(xué) 證明證明 列出真值表：列出真值表： 從表中看出從表中看出PQP 不是一個重言式，故不是一個重言式，故 PQ P不成立。不成立。 P Q PQPQP

15、T T T TT F T TF T T FF F F T例題例題4 考察考察PQ P是否成立。是否成立。離散數(shù)學(xué)離散數(shù)學(xué)由例題由例題3和例題和例題4可知，可知，PQ和和QP不等價。不等價。對對PQ來說，來說，vQP稱作它的逆換式；稱作它的逆換式；vPQ稱為它的反換式；稱為它的反換式；vQP稱為它的逆反式。稱為它的逆反式。離散數(shù)學(xué)離散數(shù)學(xué)P Q PQPQ原式原式Q P 逆反式逆反式QP逆換式逆換式PQ 反換式反換式T T F F T T T TT F F T F F T TF T T F T T F FF F T T T T T T它們之間的關(guān)系如表所示。它們之間的關(guān)系如表所示。表表1-5.1離

16、散數(shù)學(xué)離散數(shù)學(xué)從表從表1-5.1中看出：中看出：(PQ）（QP） (QP）（PQ）因此要證明因此要證明P Q，只需證明，只需證明Q P，反之亦然。，反之亦然。要證明要證明P Q，即證，即證PQ是重言式。是重言式。對于對于PQ來說，除來說，除P的真值取的真值取T，Q的真值取的真值取F這樣一種指派時，這樣一種指派時，PQ的真值為的真值為F外，其余情況，外，其余情況，PQ的真值為的真值為T。要證要證PQ是重言式：是重言式：（1）只要對條件命題）只要對條件命題PQ的前件的前件P，指定真值為，指定真值為T，若由此推，若由此推出出Q的真值也為的真值也為T，則，則PQ是重言式，即是重言式，即P Q成立成立(

17、)；（2）同理，如條件命題）同理，如條件命題PQ中，假定后件中，假定后件Q的真值取的真值取F，若，若由此推出由此推出P的真值為的真值為F，即推證了，即推證了Q P 故故P Q成立成立()。離散數(shù)學(xué)離散數(shù)學(xué) P21頁例題頁例題1 推證推證Q(PQ） P 證法證法2 (后假看前假后假看前假) 假定假定P為為F，則，則P為為T。 (a）：若）：若Q為為F，則，則PQ為為F，Q(PQ）為）為F。 (b）：若）：若Q為為T，則，則Q為為F，Q(PQ）為）為F。所以所以Q(PQ) P成立。成立。證法證法1 (前真看后真前真看后真) 假定假定Q(PQ）為）為T，則，則Q為為T，且，且(PQ）為）為T。由由Q

18、為為F，則必須，則必須P為為F，故，故P為為T。離散數(shù)學(xué)離散數(shù)學(xué) 表 1-5.2 常用的蘊含式 PQ P（化簡律）1 PQ Q2 P PQ（附加律）3 P PQ4 Q PQ5 (PQ） P6 (PQ） Q7 P(PQ） Q（假言律）8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR（傳遞律）11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13 (P Q)(Q R) (P R)14離散數(shù)學(xué)離散數(shù)學(xué)就象聯(lián)結(jié)詞就象聯(lián)結(jié)詞 和和的關(guān)系一樣，等價式與蘊含式之的關(guān)系一樣，等價式與蘊含式之間也有緊密的聯(lián)系。間也有緊密的聯(lián)系。 定理定理1-5.4 設(shè)設(shè)P、Q為任意兩個命

19、題公式，為任意兩個命題公式，PQ的的充分必要條件是充分必要條件是P Q且且Q P。 證明證明 若若PQ，則，則P Q為重言式，因為為重言式，因為P Q (PQ)(QP)，故，故PQ為為T且且QP為為T，即即P Q，Q P成立。成立。 反之，若反之，若P Q且且Q P，則，則PQ為為T且且QP為為T，因此，因此P Q為為T，P Q是重言式，即是重言式，即PQ。 這個這個定理也可作為兩個公式等價的定義。定理也可作為兩個公式等價的定義。三、等價式和蘊含式的關(guān)系三、等價式和蘊含式的關(guān)系離散數(shù)學(xué)離散數(shù)學(xué)蘊含有下面幾個常用的性質(zhì)：蘊含有下面幾個常用的性質(zhì)： (1)設(shè)設(shè)A、B、C為合式公式，若為合式公式，若

20、A B且且A是重言式，是重言式，則則B必是重言式。必是重言式。 證明證明 因為因為AB永為永為T，所以，當(dāng)，所以，當(dāng)A為為T時，時，B必永必永為為T。 (2)若若A B，且，且B C則則A C，即，即蘊含關(guān)系是傳蘊含關(guān)系是傳遞的。遞的。 證明證明 由由A B，B C，即，即AB，BC為重言式。為重言式。所以所以(AB)(BC)為重言式。為重言式。 由表由表l-5.2的的(11)式，式，(AB)(BC) AC，故，故由性質(zhì)由性質(zhì)(1)，AC為重言式，即為重言式，即A C。離散數(shù)學(xué)離散數(shù)學(xué) (3)若若A B，且，且A C，則，則A (BC)。 證明證明 由假設(shè)由假設(shè)AB，AC為重言式。設(shè)為重言式。

21、設(shè)A為為T，則，則B、C為為T，故，故BC為為T。因此，。因此，A(BC)為為T。 若若A為為F，則，則BC不論有怎樣的真值，不論有怎樣的真值，A(BC)為為T。所以，所以， A (BC) (4)若若A B，且，且C B，則，則AC B。 證明證明 因為因為AB為為T，CB為為T，故，故(AB)(CB)為為T。 即即(AC)B)為為T或或ACB為為T。 所以所以 AC B離散數(shù)學(xué)離散數(shù)學(xué)重點掌握重點掌握1、重言式、蘊含式定義、重言式、蘊含式定義2、蘊含式的證明、蘊含式的證明3、常用的蘊含式、常用的蘊含式離散數(shù)學(xué)離散數(shù)學(xué) 前面已經(jīng)定義了前面已經(jīng)定義了5種聯(lián)結(jié)詞：種聯(lián)結(jié)詞：，和和 ，但這些聯(lián)結(jié)詞還

22、不能但這些聯(lián)結(jié)詞還不能廣泛地直接廣泛地直接表達命題間的聯(lián)系，表達命題間的聯(lián)系，下面再定義下面再定義4種命題聯(lián)結(jié)詞：種命題聯(lián)結(jié)詞：1-6 其他聯(lián)結(jié)詞其他聯(lián)結(jié)詞離散數(shù)學(xué)離散數(shù)學(xué) P QTT FTF TFT TFF F一、不可兼析?。ó愇鋈。┮弧⒉豢杉嫖鋈。ó愇鋈。?表表1-6.1QP從真值表看與雙條件的關(guān)系從真值表看與雙條件的關(guān)系離散數(shù)學(xué)離散數(shù)學(xué)(1)P QQ P(2)()()P QRPQ R(3)()() ()PQ RPQPR(4)()()()P QPQPQ 6P PFF PPT PP （ ），(5)(P Q) (P Q) 離散數(shù)學(xué)離散數(shù)學(xué)4. 定理定理P RP P QF QQ Q RQ P Q

23、F PP P Q RR RF 證明則 如果PQ 離散數(shù)學(xué)離散數(shù)學(xué)1. 定義定義2. 定義定義1-6.2 設(shè)設(shè)P和和Q是兩個命題公式，復(fù)合命題是兩個命題公式，復(fù)合命題P Q稱作命題稱作命題P和和Q的條件否定，的條件否定，P Q的真值為的真值為T，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P的真值為的真值為T，Q的真值為的真值為F，否則的，否則的P Q的真值為的真值為F。 PQP Q TT FTF TFT FFF F表表1-6.22. 真值表真值表聯(lián)結(jié)詞聯(lián)結(jié)詞 的定義如表的定義如表1-6.2所示。所示。從定義可知從定義可知cPQPQ （）二、條件否定二、條件否定離散數(shù)學(xué)離散數(shù)學(xué)1. 定義定義 PQTT FTF TFT TF

24、F T表表1-6.32. 真值表從表1-6.3 可以看出PQPQ （）PQ2、真值表、真值表三、與非三、與非離散數(shù)學(xué)離散數(shù)學(xué)3. 性質(zhì)聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a) PQQP(b) PP P(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ 離散數(shù)學(xué)離散數(shù)學(xué) PQTT FTF FFT FFF T表表1-6.4從表1-6.4可以看出2. 真值表真值表1. 定義定義四、或非四、或非PQ()PQPQ 離散數(shù)學(xué)離散數(shù)學(xué)3. 性質(zhì)性質(zhì)聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a) PQQP(b) PP P(c)(PQ)(PQ)PQ(d) (PP)(QQ)PQ離散數(shù)學(xué)離散數(shù)學(xué)離散數(shù)學(xué)離散數(shù)學(xué)五、聯(lián)結(jié)詞完備集五、

25、聯(lián)結(jié)詞完備集定義定義 設(shè)設(shè)S S是一個聯(lián)結(jié)詞集合，如果任何是一個聯(lián)結(jié)詞集合，如果任何n(n1)n(n1)元真值函數(shù)都可以由僅含元真值函數(shù)都可以由僅含S S中的聯(lián)結(jié)詞構(gòu)成的公中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱式表示，則稱S S是是聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集。 離散數(shù)學(xué)離散數(shù)學(xué)定理：定理： ，都是聯(lián)結(jié)詞完備集。都是聯(lián)結(jié)詞完備集。證證 已知已知,為聯(lián)結(jié)詞完備集為聯(lián)結(jié)詞完備集，因而只需證明其中的每，因而只需證明其中的每個聯(lián)結(jié)詞都可以由個聯(lián)結(jié)詞都可以由定義即可。定義即可。 而而 p pq p pq (pp) (pp) ( pq) ( pq) pp (1) pp (1) (pq (pq) ) (2)(2) pq

26、 pq （定義）（定義） (pp)(qq) (pp)(qq)由由(1) (1) pq pq ( pq) ( pq) ( pq) ( pq) （定義）（定義） (3)(3) (pq)(pq) (pq)(pq) 由由(1) (1) 由（由（1）(3)可知可知是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備是聯(lián)結(jié)詞完備集。集。 離散數(shù)學(xué)離散數(shù)學(xué)六、最小聯(lián)結(jié)詞組六、最小聯(lián)結(jié)詞組 我們一共給出了九個聯(lián)結(jié)詞的定義，是否還需要我們一共給出了九個聯(lián)結(jié)詞的定義，是否還需要定義其他聯(lián)結(jié)詞呢？下面列出兩個命題變元可構(gòu)成的定義其他聯(lián)結(jié)詞呢？下面列出兩個命題變元可構(gòu)成的所有不等價的命題公式（共有所有不等價的

27、命題公式（共有16個）。個）。離散數(shù)學(xué)離散數(shù)學(xué)PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTTFTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取與非析取或非若P則Q逆條件雙條件不可兼析取若Q則P逆條件由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。離散數(shù)學(xué)離散數(shù)學(xué)實際上這九個聯(lián)結(jié)詞并非都是必要的。因為包含某實際上這九個聯(lián)結(jié)詞并非都是必要的。因為包含某些聯(lián)結(jié)詞的公式可以用另外一些聯(lián)結(jié)詞

28、的公式等價些聯(lián)結(jié)詞的公式可以用另外一些聯(lián)結(jié)詞的公式等價代換。代換。下面考慮最小聯(lián)結(jié)詞組，對于任何一個命題公式，下面考慮最小聯(lián)結(jié)詞組，對于任何一個命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價代換。都能由僅含這些聯(lián)結(jié)詞的命題公式等價代換。 離散數(shù)學(xué)離散數(shù)學(xué)離散數(shù)學(xué)離散數(shù)學(xué)P Q （）(P Q)()cPQPQ ()PQPQ ()PQPQ 所以常用聯(lián)結(jié)詞組常用聯(lián)結(jié)詞組，離散數(shù)學(xué)離散數(shù)學(xué)作業(yè)作業(yè)P23：2.a), b)(3種方法：真值表法，前真看后真，種方法：真值表法，前真看后真，后假看前假后假看前假)P29：5離散數(shù)學(xué)離散數(shù)學(xué)回顧回顧 重言式重言式 給定一命題公式，若無論對分量作怎樣的指派，給定一命題

29、公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。，則稱該命題公式為重言式或永真公式。 矛盾式矛盾式 給定一命題公式，若無論對分量作怎樣的指派，給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。，則稱該命題公式為矛盾式或永假公式。 蘊含式蘊含式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)PQ是一個重言式時，稱是一個重言式時，稱P蘊含蘊含Q，并記作并記作P Q。 逆換式逆換式 對對PQ來說，來說，QP稱作它的逆換式。稱作它的逆換式。 反換式反換式 對對PQ來說，來說， PQ稱為它的反換式。稱為它的反換式。 逆

30、反式逆反式 對對PQ來說，來說， QP稱為它的逆反式。稱為它的逆反式。離散數(shù)學(xué)離散數(shù)學(xué) 不可兼析取不可兼析取 設(shè)設(shè)P和和Q是兩個命題公式，復(fù)合命題是兩個命題公式，復(fù)合命題 稱作稱作P和和Q的不可兼析取。的不可兼析取。 的真值為的真值為T，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)P與與Q的真值不同時為的真值不同時為T，否則，否則 的真值為的真值為F。 條件否定條件否定 設(shè)設(shè)P和和Q是兩個命題公式，復(fù)合命題是兩個命題公式，復(fù)合命題P Q 稱作命題稱作命題P和和Q的條件否定，的條件否定，P Q的真值為的真值為T，當(dāng)且僅，當(dāng)且僅當(dāng)當(dāng)P的真值為的真值為T，Q的真值為的真值為F，否則的，否則的P Q的真值為的真值為F。 與非與

31、非 設(shè)設(shè)P和和Q是兩個命題公式，復(fù)合命題是兩個命題公式，復(fù)合命題 稱作命稱作命題題P和和Q的的“與非與非”，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)P和和Q真值都是真值都是T時，時， 為為F，否則，否則 的真值都為的真值都為T。 或非或非 設(shè)設(shè)P和和Q是兩個命題公式，復(fù)合命題是兩個命題公式，復(fù)合命題 稱作命稱作命題題P和和Q的的“或非或非”，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)P和和Q的真值都為的真值都為F時，時， 的真值為的真值為T，否則，否則 的真值都為的真值都為F。QPQPQPPQPQPQPQPQPQ回顧回顧離散數(shù)學(xué)離散數(shù)學(xué) 表表 1-5.2 常用的蘊含式常用的蘊含式 PQ P（化簡律）1 PQ Q2 P PQ（附加律）3 P

32、 PQ4 Q PQ5 (PQ） P6 (PQ） Q7 P(PQ） Q（假言律）8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR（傳遞律）11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13 (P Q)(Q R) (P R)14離散數(shù)學(xué)離散數(shù)學(xué)PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTTFTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取與非析取或非若P則Q逆條件雙條件不可兼析取若Q則P逆條件由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。離散數(shù)學(xué)離散數(shù)學(xué)回顧回顧 重言式重言式 給定一命題公式，若無論對分量作怎樣的指派，給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。，則稱該命題公式為重言式或永真公式。 矛盾式矛盾式 給定一命題公式，若無論對分量作怎樣的指派，給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。，則稱該命題公式為矛盾式或永假公式。 蘊含式蘊含式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)PQ是一個重言式時