離散數(shù)學(xué)DiscreteMathematics,陳明Email:mingchen_gang,信息科學(xué)與工程學(xué)院,二零一三年九月,課程回顧,第1次課：命題；5個聯(lián)結(jié)詞第2次課：命題的翻譯命題公式等價的兩種證明方法真值表利用命題定律推導(dǎo),合式公式：命題演算的合式公式(wff)規(guī)定為：(1)單個命題變元本身是一個合式公式。(2)如果A是合式公式，那么A是合式公式。(3)如果A和B是合式公式，那么(AB)，(AB)，(AB）和(AB)都是合式公式。(4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)、(2)、(3)所得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。翻譯把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式。優(yōu)先次序規(guī)定聯(lián)結(jié)詞運算的優(yōu)先次序為：、,真值表在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。邏輯相等給定兩個命題公式A和B，設(shè)P1，P2，Pn為所有出現(xiàn)于A和B中的原子變元，若給P1，P2，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等。記作AB。子公式如果X是合式公式A的一部分，且X本身也是一個合式公式，則稱X為公式A的子公式。定理1-4.1設(shè)X是合式公式A的子公式，若XY，如果將A中的X用Y來置換，所得到公式B與公式A等價，即AB。10個命題定律。,PQPQ,表1-4.8,化簡如下語句：“情況并非如此：若他不來，則我不去”。,解：首先符號化上述語句。設(shè)P：他來。Q：我去則原句：（PQ）然后化簡上述命題公式（PQ）（PQ）PQ即：我去了，但他未來。,P：上午下雨，Q：我去看電影，R：我在家看書；S：我在家看報。（PQ）（P（RS）,P12：（7）a）,1-5重言式與蘊含式1-6其他聯(lián)結(jié)詞,一、重言式和矛盾式從上節(jié)真值表和命題的等價公式推證中可以看到，有些命題公式，無論對分量作何種指派，其對應(yīng)的真值都為T（見14頁表1-4.4）或都為F（見13頁表1-4.2）。,表1-4.4,表1-4.2,重言式和矛盾式這兩類特殊的命題公式在今后的命題演算中極為有用。定義1-5.1給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。,定義1-5.2給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。,證明由于重言式的真值與分量的指派無關(guān)，故對同一分量以任何合式公式置換后，重言式的真值仍永為T。,定理1-5.2一個重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。,證明設(shè)A和B為兩個重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故ABT，ABT。,定理1-5.1任何兩個重言式的合取或析取，仍然是一個重言式。,對于矛盾式也有類似于定理1-5.1和定理1-5.2的結(jié)果。,例題1證明(PS)R)V(PS)R)為重言式。,證明因為PVPT，如以(PS)R)置換P即得(PS)R)V(PS)R)T,重點將研究重言式，因為重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。重言式最有用，它有以下特點：兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。由重言式使用公認的規(guī)則可以產(chǎn)生許多有用等價式和蘊涵式。,給定一命題公式，至少存在一個指派，公式相應(yīng)確定真值為真，稱為可滿足式。重言式必是可滿足式，反之一般不真。判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。在命題邏輯中，由于任何一個命題公式的指派數(shù)目總是有限的，所以命題邏輯的判定問題是可解的。其判定方法有真值表法和公式推演法。,證明重言式的方法,定理1-5.3設(shè)A、B為兩個命題公式，AB當(dāng)且僅當(dāng)AB為一個重言式。證明若AB，則A、B有相同真值，即AB永為T。若AB為重言式，則AB永為T，故A、B的真值相同，即AB。,定理1-5.3的作用：為AB又提供了一種方法。其他方法：（1）真值表法（2）利用命題定律推導(dǎo)證明,定理1-5.3設(shè)A、B為兩個命題公式，AB當(dāng)且僅當(dāng)AB為一個重言式。證明若AB，則A、B有相同真值，即AB永為T。若AB為重言式，則AB永為T，故A、B的真值相同，即AB。,例題2證明(PQ）（PQ）,證明：據(jù)定理1-5.3，只需證：(PQ）（PQ）為重言式。,聯(lián)結(jié)詞可用來表達。由第4節(jié)例題5可知：AB(AB)(BA)下面討論AB的重言式。1.定義定義1-5.3當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱“P蘊含Q”，并記作PQ。,二、蘊含式,2.蘊含式的證明方法：(1)列真值表法：根據(jù)定義，只需證PQ是重言式(2)邏輯推論前真看后真后假看前假(3)等價置換,例題3證明PPQ證明列出真值表：從表中看出PPQ是一個重言式，故PPQ成立。,證明列出真值表：從表中看出PQP不是一個重言式，故PQP不成立。,例題4考察PQP是否成立。,由例題3和例題4可知，PQ和QP不等價。對PQ來說，QP稱作它的逆換式；PQ稱為它的反換式；QP稱為它的逆反式。,它們之間的關(guān)系如表所示。,表1-5.1,從表1-5.1中看出：(PQ）（QP）(QP）（PQ）因此要證明PQ，只需證明QP，反之亦然。要證明PQ，即證PQ是重言式。對于PQ來說，除P的真值取T，Q的真值取F這樣一種指派時，PQ的真值為F外，其余情況，PQ的真值為T。要證PQ是重言式：（1）只要對條件命題PQ的前件P，指定真值為T，若由此推出Q的真值也為T，則PQ是重言式，即PQ成立(前真看后真)；（2）同理，如條件命題PQ中，假定后件Q的真值取F，若由此推出P的真值為F，即推證了QP故PQ成立(后假看前假)。,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為F，則必須P為F，故P為T。,表1-5.2常用的蘊含式,就象聯(lián)結(jié)詞和的關(guān)系一樣，等價式與蘊含式之間也有緊密的聯(lián)系。定理1-5.4設(shè)P、Q為任意兩個命題公式，PQ的充分必要條件是PQ且QP。,證明若PQ，則PQ為重言式，因為PQ(PQ)(QP)，故PQ為T且QP為T，即PQ，QP成立。反之，若PQ且QP，則PQ為T且QP為T，因此PQ為T，PQ是重言式，即PQ。這個定理也可作為兩個公式等價的定義。,三、等價式和蘊含式的關(guān)系,蘊含有下面幾個常用的性質(zhì)：(1)設(shè)A、B、C為合式公式，若AB且A是重言式，則B必是重言式。證明因為AB永為T，所以，當(dāng)A為T時，B必永為T。(2)若AB，且BC則AC，即蘊含關(guān)系是傳遞的。證明由AB，BC，即AB，BC為重言式。所以(AB)(BC)為重言式。由表l-5.2的(11)式，(AB)(BC)AC，故由性質(zhì)(1)，AC為重言式，即AC。,(3)若AB，且AC，則A(BC)。證明由假設(shè)AB，AC為重言式。設(shè)A為T，則B、C為T，故BC為T。因此，A(BC)為T。若A為F，則BC不論有怎樣的真值，A(BC)為T。所以，A(BC)(4)若AB，且CB，則ACB。證明因為AB為T，CB為T，故(AB)(CB)為T。即(AC)B)為T或ACB為T。所以ACB,重點掌握1、重言式、蘊含式定義2、蘊含式的證明3、常用的蘊含式,前面已經(jīng)定義了5種聯(lián)結(jié)詞：，和，但這些聯(lián)結(jié)詞還不能廣泛地直接表達命題間的聯(lián)系，下面再定義4種命題聯(lián)結(jié)詞：,1-6其他聯(lián)結(jié)詞,一、不可兼析?。ó愇鋈。?表1-6.1,從真值表看與雙條件的關(guān)系,4.定理,證明,則,定義定義1-6.2設(shè)P和Q是兩個命題公式，復(fù)合命題PQ稱作命題P和Q的條件否定，PQ的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的PQ的真值為F。,表1-6.2,2.真值表聯(lián)結(jié)詞的定義如表1-6.2所示。,從定義可知,二、條件否定,定義,表1-6.3,2.真值表,從表1-6.3可以看出,2、真值表,三、與非,3.性質(zhì),聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ,表1-6.4,從表1-6.4可以看出,2.真值表,1.定義,四、或非,3.性質(zhì),聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ,五、聯(lián)結(jié)詞完備集定義設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。,定理：，都是聯(lián)結(jié)詞完備集。,證已知,為聯(lián)結(jié)詞完備集，因而只需證明其中的每個聯(lián)結(jié)詞都可以由定義即可。,而ppq(pp)(pq)pp(1)(pq)(2)pq（定義）(pp)(qq)由(1)pq(pq)(pq)（定義）(3)(pq)(pq)由(1),由（1）(3)可知是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備集。,六、最小聯(lián)結(jié)詞組我們一共給出了九個聯(lián)結(jié)詞的定義，是否還需要定義其他聯(lián)結(jié)詞呢？下面列出兩個命題變元可構(gòu)成的所有不等價的命題公式（共有16個）。,由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。,實際上這九個聯(lián)結(jié)詞并非都是必要的。因為包含某些聯(lián)結(jié)詞的公式可以用另外一些聯(lián)結(jié)詞的公式等價代換。下面考慮最小聯(lián)結(jié)詞組，對于任何一個命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價代換。,所以,常用聯(lián)結(jié)詞組，,作業(yè),P23：2.a),b)(3種方法：真值表法，前真看后真，后假看前假)P29：5,回顧重言式給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。矛盾式給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。蘊含式當(dāng)且僅當(dāng)PQ是一個重言式時，稱P蘊含Q，并記作PQ。逆換式對PQ來說，QP稱作它的逆換式。反換式對PQ來說，PQ稱為它的反換式。逆反式對PQ來說，QP稱為它的逆反式。,不可兼析取設(shè)P和Q是兩個命題公式，復(fù)合命題稱作P和Q的不可兼析取。的真值為T，當(dāng)且僅當(dāng)P與Q的真值不同時為T，否則的真值為F。條件否定設(shè)P和Q是兩個命題公式，復(fù)合命題PQ稱作命題P和Q的條件否定，PQ的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的PQ的真值為F。與非設(shè)P和Q是兩個命題公式，復(fù)合命題稱作命題P和Q的“與非”，當(dāng)且僅當(dāng)P和Q真值都是T時，為F，否則的真值都為T?；蚍窃O(shè)P和Q是兩個命題公式，復(fù)合命題稱作命題P和Q的“或非”，當(dāng)且僅當(dāng)P和Q的真值都為F時，的真值為T，否則的真值都為F。,回顧,表1-5.2常用的蘊含式,由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。,回顧重言式給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。矛盾式給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。蘊含式當(dāng)且僅當(dāng)PQ是一個重言式時，稱P蘊含Q，并記作PQ。逆換式對PQ來說，QP稱作它的逆換式。反換式對PQ來說，PQ稱為它的反換式。逆反式對PQ來說，QP稱為它的逆反式。,不可兼析取設(shè)P和Q是兩個命題公式，復(fù)合命題稱作P和Q的不可兼析取。的真值為T，當(dāng)且僅當(dāng)P與Q的真值不同時為T，否則的真值為F。條件否定設(shè)P和Q是兩個命題公式，復(fù)合命題PQ稱作命題P和Q的條件否定，PQ的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的PQ的真值為F。與非設(shè)P和Q是