離散數(shù)學(xué)第1章重言式與蘊含式和其它連接詞

1、1Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院2為什么要學(xué)習(xí)離散數(shù)學(xué)？李開復(fù)：給中國學(xué)生的第四封信給中國學(xué)生的第四封信大學(xué)四年應(yīng)該這么度過大學(xué)四年應(yīng)該這么度過數(shù)學(xué)是理工科學(xué)生必備的基礎(chǔ)。很多學(xué)生在高中時認為數(shù)學(xué)是最難學(xué)的，到了大學(xué)里，一旦發(fā)現(xiàn)本專業(yè)對數(shù)學(xué)的要求不高，就會徹底放松對數(shù)學(xué)知識的學(xué)習(xí)，而且他們看不出數(shù)學(xué)知識有什么現(xiàn)實的應(yīng)用或就業(yè)前景。但大家不要忘記，絕大多數(shù)理工科專業(yè)的知識體系都建立在數(shù)學(xué)的基石之上。例如，要例如，要想學(xué)好計算機工程專業(yè)，那至少要把離散數(shù)學(xué)（包括集合論、想學(xué)好計算機工程專業(yè)，那至少要把離散數(shù)學(xué)（包括集合論、圖論、

2、數(shù)理邏輯等）、圖論、數(shù)理邏輯等）、線性代數(shù)、概率統(tǒng)計和數(shù)學(xué)分析學(xué)好；要想進一步攻讀計算機科學(xué)專業(yè)的碩士或博士學(xué)位，可能還需要更高的數(shù)學(xué)素養(yǎng)。3課程回顧第1次課：命題；5個聯(lián)結(jié)詞第2次課：合式公式命題的翻譯命題公式等價的兩種證明方法真值表利用命題定律推導(dǎo)第一章 命題邏輯 第3講15 重言式與蘊含式 16 其他連結(jié)詞重點：重言式、蘊含式難點：用推理方法證明蘊含式。5回顧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表1-4.46回顧 表 1-4.2 P Q PQ P(PQ）PT T T F

3、FT F F F FF T F T FF F F T F7一、重言式和矛盾式一、重言式和矛盾式 定義定義1-5.1 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式重言式或永真公式永真公式。定義定義1-5.2 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式矛盾式或永假公式永假公式。對于矛盾式也有類似于定理1-5.1和定理1-5.2的結(jié)果。證明 由于重言式的真值與分量的指派無關(guān)，故對同一分量以任何合式公式置換后，重言式的真值仍永為T。 口定理定理1-5.2 一個重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。

4、證明 設(shè)A和B為兩個重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故ABT，ABT。 口 定理定理1-5.1 任何兩個重言式的合取或析取，仍然是一個重言式。因為重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了，后面將重點研究重言式。重言式最有用，因為它有以下特點：兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。 由重言式使用公認的規(guī)則可以產(chǎn)生許多有用等價式和蘊涵式。10證明重言式的方法證明重言式的方法v給定一命題公式，至少存在一個指派，公式相應(yīng)確定真值為真，稱為可滿足式。v重言式必是可滿足式，反之一般不真。v判

5、定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。v在命題邏輯中，由于任何一個命題公式的指派數(shù)目總是有限的，所以命題邏輯的判定問題是可解的。其判定方法有真值表法和公式推演法。例題1 證明(PS)R)V(PS)R)為重言式。證明 因為PVPT， 如以(PS)R)置換P即得 (PS)R)V(PS)R) T 定理定理1-5.3 設(shè)A、B為兩個命題公式，A B當(dāng)且僅當(dāng)A B為一個重言式。 證明 若AB，則A、B有相同真值，即A B永為T。 若A B為重言式，則A B永為T，故A、B的真值相同，即AB。 定理定理1-5.3的作用：為的作用：為A B又提供了一種方法。又提供了一種方法

6、。其他方法：其他方法：（1）真值表法）真值表法（2）利用命題定律推導(dǎo)證明）利用命題定律推導(dǎo)證明13例題2 證明(PQ）（PQ）證明：據(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二、蘊含式二、蘊含式 聯(lián)結(jié)詞 可用來表達。由第4節(jié)例題5可知：A B (AB)(BA) 下面討論AB的重言式。1.定義定義定義1-5.3 當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱“P蘊含Q”，并記作P Q。符號和的區(qū)別與聯(lián)系類似于和的關(guān)系。區(qū)別：是邏輯聯(lián)結(jié)詞，屬于

7、對象語言中的符號，是公式中的符號；不是聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個公式之間的關(guān)系，不是兩公式中符號。2. 蘊含式的證明方法：(1)列真值表法：根據(jù)定義， 只需證PQ是重言式(2)邏輯推論前真看后真后假看前假(3)等價置換 例題3 證明P PQ 證明 列出真值表： 從表中看出PPQ是一個重言式，故P PQ成立。P Q PQPPQT T T TT F T TF T T TF F T T 證明 列出真值表： 從表中看出PQP 不是一個重言式，故 PQ P不成立。 P Q PQPQPT T T TT F T TF T T FF F F T例題4 考察PQ P是否成立。由例題3和例題4可知，PQ

8、和QP不等價。對PQ來說，vQP稱作它的逆換式逆換式；vPQ稱為它的反換式反換式；vQP稱為它的逆反式逆反式。它們之間的關(guān)系如表所示。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從表1-5.1中看出：(PQ）（QP） (QP）（PQ）因此要證明P Q，只需證明Q P，反之亦然。v要證明P Q，即證PQ是重言式。v對于PQ來說，除P的真值取T，Q的真值取F這樣一種指派時，PQ的真值為F外，其余情況，PQ的真值為T。v要證PQ是重言式：（1）只要

9、對條件命題PQ的前件P，指定真值為T，若由此推出Q的真值也為T，則PQ是重言式，即P Q成立()；（2）同理，如條件命題PQ中，假定后件Q的真值取F，若由此推出P的真值為F，即推證了Q P 故P Q成立()。 例題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 常用的蘊含重言式 PQ P1 PQ Q2 P PQ3 P PQ4 Q PQ5

10、 (PQ） P6 (PQ） Q7 P(PQ） Q8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13 (P Q)(Q R) (P R)14三、等價式和蘊含式的關(guān)系三、等價式和蘊含式的關(guān)系 就象聯(lián)結(jié)詞 和的關(guān)系一樣，等價式與蘊含式之間也有緊密的聯(lián)系。 定理1-5.4 設(shè)P、Q為任意兩個命題公式，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是

11、重言式，即PQ。 這個定理也可作為兩個公式等價的定義。蘊含有下面幾個常用的性質(zhì)： (1)設(shè)設(shè)A、B、C為合式公式，若為合式公式，若A B且且A是重言是重言式，則式，則B必是重言式。必是重言式。 證明 因為AB永為T，所以，當(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ì)(1)，AC為重言式，即A C。 (3)若若A B，且，且A C，則，則A (BC)。 證明 由假設(shè)AB，AC為重言式。設(shè)A為T

12、，則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四、小結(jié)四、小結(jié) 本節(jié)主要內(nèi)容本節(jié)主要內(nèi)容1. 深刻理解以下概念深刻理解以下概念 重言式重言式 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式重言式或永真公式永真公式。 矛盾式矛盾式 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式矛盾式或永假公式

13、永假公式。 蘊含式蘊含式 當(dāng)且僅當(dāng)PQ是一個重言式時，稱P蘊含Q，并記作P Q。 逆換式逆換式 對PQ來說，QP稱作它的逆換式逆換式。 反換式反換式 對PQ來說， PQ稱為它的反換式反換式。 逆反式逆反式 對PQ來說， QP稱為它的逆反式逆反式。2. 掌握以下定理掌握以下定理 定理定理1-5.1 任何兩個重言式的合取或析取，仍然是一個重言式。 定理定理1-5.2 一個重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。 定理定理1-5.3 設(shè)A、B為兩個命題公式，A B當(dāng)且僅當(dāng)A B為一個重言式。 定理定理1-5.4 設(shè)P、Q為任意兩個命題公式，P Q的充分必要條件是P Q且Q P。3

14、. 會證明重言式、蘊含式會證明重言式、蘊含式28 前面已經(jīng)定義了5種聯(lián)結(jié)詞：，和 ，但這些聯(lián)結(jié)詞還不能廣泛地直接表達命題間的聯(lián)系，下面再定義4種命題聯(lián)結(jié)詞：16 其他連結(jié)詞其他連結(jié)詞29 P QTT FTF TFT TFF F一、不可兼析?。ó愇鋈。┮?、不可兼析取（異析取） 表1-6.1QP30(1)P QQ P(2)()()P QRPQ R(3)()() ()PQ RPQPR(4)()()()P QPQPQ 6P PFF PPT PP （ ），(5)(P Q) (P Q) 314. 定理P RP P QF QQ Q RQ P QF PP P Q RR RF 證明則 如果PQ 32二、條件否定

15、定義定義1-6.2 設(shè)P和Q是兩個命題公式，復(fù)合命題P Q稱作命題P和Q的條件否定，P Q的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的P Q的真值為F。 PQP Q TT FTF TFT FFF F表1-6.22. 真值表聯(lián)結(jié)詞 的定義如表1-6.2所示。從定義可知cPQPQ （）33三、與非定義 PQTT FTF TFT TFF T表1-6.32. 真值表從表1-6.3 可以看出PQPQ （）PQ2、真值表343. 性質(zhì)聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a) PQQP(b) PP P(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ 35 PQTT FTF FFT FFF T表1-

16、6.4從表1-6.4可以看出2. 真值表1. 定義四、或非PQ()PQPQ 363. 性質(zhì)聯(lián)結(jié)詞“”有如下幾個性質(zhì)：(a) PQQP(b) PPP(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ3738五、聯(lián)結(jié)詞完備集五、聯(lián)結(jié)詞完備集定義定義 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備聯(lián)結(jié)詞完備集集。 根據(jù)需要，人們還可構(gòu)造形式上更為簡單的聯(lián)結(jié)詞完備集。例如，在計算機硬件設(shè)計中，用與非門或者或非門來設(shè)計邏輯線路時，就需要構(gòu)造新聯(lián)結(jié)詞完備集。 39定理：定理： ，都是聯(lián)結(jié)詞完備集。證證 已知,為聯(lián)結(jié)詞完備集，因而只需證明其

17、中的每個聯(lián)結(jié)詞都可以由定義即可。 而 p pq (pp) ( pq) pp (1) (pq) pq （定義） (pp)(qq)由(1) (3) pq ( pq) ( pq) （定義） (pq)(pq) 由(1) (2) 由（1）(3)可知是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備集。 40五、最小聯(lián)結(jié)詞組五、最小聯(lián)結(jié)詞組 我們一共給出了九個聯(lián)結(jié)詞的定義，是否還需要定義其他聯(lián)結(jié)詞呢？下面列出兩個命題變元可構(gòu)成的所有不等價的命題公式（共有16個）。41PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTT

18、FTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取與非析取或非若P則Q逆條件雙條件不可兼析取若Q則P逆條件由上述分析，除常量及命題變元本身外，命題聯(lián)結(jié)詞一共有九個就夠了。42實際上這九個聯(lián)結(jié)詞并非都是必要的。因為包含某些聯(lián)結(jié)詞的公式可以用另外一些聯(lián)結(jié)詞的公式等價代換。下面考慮最小聯(lián)結(jié)詞組，對于任何一個命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價代換。 43P Q （）(PQ)()cPQPQ ()PQPQ ()PQPQ 所以44 六、小結(jié) 本節(jié)所講內(nèi)容如下： 不可兼析取 設(shè)P和Q是兩個命題公式，復(fù)合命題 稱作P和Q的不可兼析取。 的真值為T，當(dāng)且僅當(dāng)P與Q的真值不同時

19、為T，否則 的真值為F。 逆條件 設(shè)P和Q是兩個命題公式，復(fù)合命題P Q 稱作命題P和Q的條件否定，P Q的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的P Q的真值為F。 與非 設(shè)P和Q是兩個命題公式，復(fù)合命題 稱作命題P和Q的“與非”，當(dāng)且僅當(dāng)P和Q真值都是T時， 為F，否則 的真值都為T。 或非 設(shè)P和Q是兩個命題公式，復(fù)合命題 稱作命題P和Q的“或非”，當(dāng)且僅當(dāng)P和Q的真值都為F時， 的真值為T，否則 的真值都為F。QPQPQPPQPQPQPQPQPQ45作業(yè)P23：2.a)(3種方法)，8P29：346Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工

20、程學(xué)院信息科學(xué)與工程學(xué)院第一章 命題邏輯第4講17 對偶與范式 要求：掌握對偶與范式，會求命題公式的主析取范式和主合取范式。 重點和難點：求命題公式的主析取范式和主合取范式。一、對偶式一、對偶式1. 復(fù)習(xí)命題定律。見15頁表1-4.8對合律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否定律PP T，PP F10 我們從表1-4.8可以看到命題定律除對合律外都是成對出現(xiàn)的，其不同的只是和互換。我們把這樣的公式稱作具有對偶規(guī)律。 定義1-7.1 在給定的命題公式中，將聯(lián)結(jié)詞換成，將換成 ，若有特殊變元F和T亦相互取代，所得公式A*稱作A的對偶式。 顯然A也是A*的對偶式。2. 對偶式的定義例題1 寫出下列表達式的對偶式。(P Q) R(P Q) F(P Q) (P (Q S)（a）(PQ) R（b）(PQ) T（c）(P