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

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

2、石之上。例如，要想學(xué)好計(jì)算機(jī)工程專業(yè)，那至少要把離散數(shù)學(xué)（包括集合論、圖論、數(shù)理邏輯等）、線性代數(shù)、概率統(tǒng)計(jì)和數(shù)學(xué)分析學(xué)好；要想進(jìn)一步攻讀計(jì)算機(jī)科學(xué)專業(yè)的碩士或博士學(xué)位，可能還需要更高的數(shù)學(xué)素養(yǎng)。,3,課程回顧,第1次課：命題；5個(gè)聯(lián)結(jié)詞第2次課：合式公式命題的翻譯命題公式等價(jià)的兩種證明方法真值表利用命題定律推導(dǎo),第一章 命題邏輯 第3講§1—5 重言式與蘊(yùn)含式 §1—6 其他連結(jié)詞,重點(diǎn)：重言式、

3、蘊(yùn)含式難點(diǎn)：用推理方法證明蘊(yùn)含式。,5,回顧,,表1-4.4,6,回顧,,表 1-4.2,7,一、重言式和矛盾式 定義1-5.1 給定一命題公式，若無論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。,定義1-5.2 給定一命題公式，若無論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。,對(duì)于矛盾式也有類似于定理1-5.1和定理1-5.2的結(jié)果。,證明 由于重言式

4、的真值與分量的指派無關(guān)，故對(duì)同一分量以任何合式公式置換后，重言式的真值仍永為T。 口,定理1-5.2 一個(gè)重言式，對(duì)同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。,證明 設(shè)A和B為兩個(gè)重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故A∧B?T，A∨B?T。 口,定理1-5.1 任何兩個(gè)重言式的合取

5、或析取，仍然是一個(gè)重言式。,因?yàn)橹匮允降姆穸ㄊ敲苁剑苁降姆穸ㄊ侵匮允?，這樣只研究其一就可以了，后面將重點(diǎn)研究重言式。重言式最有用，因?yàn)樗幸韵绿攸c(diǎn)：①兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。 ②由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。,10,證明重言式的方法,給定一命題公式，至少存在一個(gè)指派，公式相應(yīng)確定真值為真，稱為可滿足式。重言式必是可滿足式，反之

6、一般不真。判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。在命題邏輯中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以命題邏輯的判定問題是可解的。其判定方法有真值表法和公式推演法。,例題1 證明((P∨S)∧R)V┐((P∨S)∧R)為重言式。,證明 因?yàn)镻V┐P?T， 如以((P∨S)∧R)置換P即得 ((P∨S)∧R)V┐((P∨S)∧R) ?T,定理1-5.3 設(shè)A、B為兩個(gè)命

7、題公式，A ? B當(dāng)且僅當(dāng)A B為一個(gè)重言式。 證明 若A?B，則A、B有相同真值，即A B永為T。 若A B為重言式，則A B永為T，故A、B的真值相同，即A?B。,,定理1-5.3的作用：為A ? B又提供了一種方法。其他方法：（1）真值表法（2）利用命題定律推導(dǎo)證明,13,例題2 證明┐(P∧Q）?（┐P∨┐Q）,證明：據(jù)定理1-5.3 ，只需證：┐(P∧Q） （

8、┐P∨┐Q）為重言式。,二、蘊(yùn)含式 聯(lián)結(jié)詞 可用→來表達(dá)。由第4節(jié)例題5可知：A B? (A→B)∧(B→A) 下面討論A→B的重言式。1.定義定義1-5.3 當(dāng)且僅當(dāng)P→Q是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P ? Q。,符號(hào)→和?的區(qū)別與聯(lián)系類似于?和?的關(guān)系。區(qū)別：→是邏輯聯(lián)結(jié)詞，屬于對(duì)象語言中的符號(hào)，是公式中的符號(hào)；?不是聯(lián)結(jié)詞，屬于元語言中的符號(hào)，表示兩個(gè)公式之間的關(guān)系，不

9、是兩公式中符號(hào)。,2. 蘊(yùn)含式的證明方法：(1)列真值表法：根據(jù)定義， 只需證P→Q是重言式(2)邏輯推論前真看后真后假看前假(3)等價(jià)置換,例題3 證明P ? P∨Q 證明 列出真值表： 從表中看出P→P∨Q是一個(gè)重言式，故P ? P∨Q成立。,證明 列出真值表： 從表中看出P∨Q→P 不是一個(gè)重言式，故 P∨Q ? P不成立。,例題4 考察P∨Q ? P是否成立。,由例題3和例

10、題4可知，P→Q和Q→P不等價(jià)。對(duì)P→Q來說，Q→P稱作它的逆換式；┐P→┐Q稱為它的反換式；┐Q→┐P稱為它的逆反式。它們之間的關(guān)系如表所示。,從表1-5.1中看出：(P→Q）?（┐Q→┐P） (Q→P）?（┐P→┐Q）因此要證明P ? Q，只需證明┐Q ? ┐P，反之亦然。要證明P ? Q，即證P→Q是重言式。對(duì)于P→Q來說，除P的真值取T，Q的真值取F這樣

11、一種指派時(shí)，P→Q的真值為F外，其余情況，P→Q的真值為T。要證P→Q是重言式：（1）只要對(duì)條件命題P→Q的前件P，指定真值為T，若由此推出Q的真值也為T，則P→Q是重言式，即P ? Q成立(前真看后真)；（2）同理，如條件命題P→Q中，假定后件Q的真值取F，若由此推出P的真值為F，即推證了┐Q ? ┐P 故P ? Q成立(后假看前假)。,例題1 推證┐Q∧(P→Q） ? ┐P,證法2 (后假看前假) 假定┐P為F，則

12、P為T。 (a）：若Q為F，則P→Q為F，┐Q∧(P→Q）為F。 (b）：若Q為T，則┐Q為F，┐Q∧(P→Q）為F。所以┐Q∧(P→Q) ? ┐P成立。,證法1 (前真看后真) 假定┐Q∧(P→Q）為T，則┐Q為T，且(P→Q）為T。由Q為F，則必須P為F，故┐P為T。,表 1-5.2 常用的蘊(yùn)含重言式,三、等價(jià)式和蘊(yùn)含式的關(guān)系 就象聯(lián)結(jié)詞 和→的關(guān)系一樣，等價(jià)式與蘊(yùn)含式之間也有緊密的聯(lián)

13、系。 定理1-5.4 設(shè)P、Q為任意兩個(gè)命題公式，P?Q的充分必要條件是P ? Q且Q ? P。,證明 若P?Q，則P Q為重言式，因?yàn)镻 Q? (P→Q)∧(Q→P)，故P→Q為T且Q→P為T，即P ? Q，Q ? P成立。反之，若P ? Q且Q ? P，則，P→Q為T且Q→P為T，因此P Q為T，P Q是重言式，即P?Q。 這個(gè)定理也可作為兩個(gè)公式等價(jià)的定義。,蘊(yùn)含有下面幾個(gè)常用的性質(zhì)

14、： (1)設(shè)A、B、C為合式公式，若A ? B且A是重言式，則B必是重言式。 證明 因?yàn)锳→B永為T，所以，當(dāng)A為T時(shí)，B必永為T。 (2)若A ? B，且B ? C則A ? C，即蘊(yùn)含關(guān)系是傳遞的。 證明 由A ? B，B ? C，即A→B，B→C為重言式。所以(A→B)∧(B→C)為重言式。 由表l-5.2的(11)式，(A→B)∧(B→C) ? A→C，故由性質(zhì)(1)，A→C為重言式，即

15、A ? C。,(3)若A ? B，且A ? C，則A ?(B∧C)。 證明 由假設(shè)A→B，A→C為重言式。設(shè)A為T，則B、C為T，故B∧C為T。因此，A→(B∧C)為T。 若A為F，則B∧C不論有怎樣的真值，A→(B∧C)為T。所以， A ?(B∧C) (4)若A ? B，且C ? B，則A∨C ? B。 證明 因?yàn)锳→B為T，C→B為T，故(┐A∨B)∧(┐C∨B)為

16、T。 即(┐A∧┐C)∨B)為T或A∨C→B為T。 所以 A∨C ? B,四、小結(jié) 本節(jié)主要內(nèi)容1. 深刻理解以下概念 重言式 給定一命題公式，若無論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。 矛盾式 給定一命題公式，若無論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。

17、 蘊(yùn)含式 當(dāng)且僅當(dāng)P→Q是一個(gè)重言式時(shí)，稱P蘊(yùn)含Q，并記作P ? Q。 逆換式 對(duì)P→Q來說，Q→P稱作它的逆換式。 反換式 對(duì)P→Q來說， ┐P→┐Q稱為它的反換式。 逆反式 對(duì)P→Q來說， ┐Q→┐P稱為它的逆反式。,2. 掌握以下定理 定理1-5.1 任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。

18、 定理1-5.2 一個(gè)重言式，對(duì)同一分量都用任何合式公式置換，其結(jié)果仍為一重言式。 定理1-5.3 設(shè)A、B為兩個(gè)命題公式，A B當(dāng)且僅當(dāng)A B為一個(gè)重言式。 定理1-5.4 設(shè)P、Q為任意兩個(gè)命題公式，P Q的充分必要條件是P ? Q且Q ? P。3. 會(huì)證明重言式、蘊(yùn)含式,28,,前面已經(jīng)定義了5種聯(lián)結(jié)詞：┐，∧，∨，→和 ，但這些聯(lián)結(jié)詞還不能廣泛地

19、直接表達(dá)命題間的聯(lián)系，下面再定義4種命題聯(lián)結(jié)詞：,§1—6 其他連結(jié)詞,29,,一、不可兼析取（異析?。?表1-6.1,,30,31,4. 定理,證明,則,32,二、條件否定定義定義1-6.2 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題P Q稱作命題P和Q的條件否定，P Q的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的P Q的真值為F。,表1-6.2,2. 真值表聯(lián)結(jié)詞 的定

20、義如表1-6.2所示。,從定義可知,33,三、與非定義,表1-6.3,2. 真值表,從表1-6.3 可以看出,2、真值表,34,3. 性質(zhì),聯(lián)結(jié)詞“↑”有如下幾個(gè)性質(zhì)：(a) P↑Q?Q↑P(b) P↑P?? P(c) (P↑Q)↑(P↑Q)?P∧Q(d) (P↑P)↑(Q↑Q)?P∨Q,35,表1-6.4,,從表1-6.4可以看出,2. 真值表,1. 定義,四、或非,36,3. 性質(zhì),聯(lián)結(jié)詞“↓”有如下幾個(gè)性質(zhì)

21、：(a) P↓Q?Q↓P(b) P↓P??P(c) (P↓Q)↓(P↓Q)?P∨Q(d) (P↓P)↓(Q↓Q)?P∧Q,37,38,五、聯(lián)結(jié)詞完備集定義 設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n(n≥1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。 根據(jù)需要，人們還可構(gòu)造形式上更為簡(jiǎn)單的聯(lián)結(jié)詞完備集。例如，在計(jì)算機(jī)硬件設(shè)計(jì)中，用與非門或者或非門來設(shè)計(jì)邏輯線路時(shí)，就需要構(gòu)造新聯(lián)結(jié)詞完備集。,

22、39,定理： {↑}，{↓}都是聯(lián)結(jié)詞完備集。,證 已知{┐,∧,∨}為聯(lián)結(jié)詞完備集，因而只需證明其中的每個(gè)聯(lián)結(jié)詞都可以由↑定義即可。,而 ┐p p∨q     ? ┐(p∧p)   ? ┐┐( p∨q)     ? p↑p  

23、                       (1) ? ┐(┐p∧┐q) ?  ┐p↑┐q  

24、;      （定義） ? (p↑p)↑(q↑q)由(1) (3)   p∧q    ? ┐┐( p∧q)     ? ┐( p↑q) &

25、#160;     （定義）    ? (p↑q)↑(p↑q) 由(1)    (2),由（1）～(3)可知{↑}是聯(lián)結(jié)詞完備集，類似可證{↓}是聯(lián)結(jié)詞完備集。,40,五、最小聯(lián)結(jié)詞組 我們一共給出了九個(gè)聯(lián)結(jié)詞的定義，是否還需要定義其他聯(lián)結(jié)詞呢？下面列出兩個(gè)命題變?cè)蓸?gòu)成的所有不等價(jià)的命題公式（共

26、有16個(gè)）。,41,由上述分析，除常量及命題變?cè)旧硗?，命題聯(lián)結(jié)詞一共有九個(gè)就夠了。,42,實(shí)際上這九個(gè)聯(lián)結(jié)詞并非都是必要的。因?yàn)榘承┞?lián)結(jié)詞的公式可以用另外一些聯(lián)結(jié)詞的公式等價(jià)代換。下面考慮最小聯(lián)結(jié)詞組，對(duì)于任何一個(gè)命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價(jià)代換。,43,所以,44,六、小結(jié) 本節(jié)所講內(nèi)容如下： 不可兼析取 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題 稱作P和Q的不可兼析取。 的真值為T，當(dāng)

27、且僅當(dāng)P與Q的真值不同時(shí)為T，否則 的真值為F。 逆條件 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題P Q 稱作命題P和Q的條件否定，P Q的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則的P Q的真值為F。 與非 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題 稱作命題P和Q的“與非”，當(dāng)且僅當(dāng)P和Q真值都是T時(shí)， 為F，否則 的真

28、值都為T。 或非 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題 稱作命題P和Q的“或非”，當(dāng)且僅當(dāng)P和Q的真值都為F時(shí)， 的真值為T，否則 的真值都為F。,45,作業(yè),P23：2.a)(3種方法)，8P29：3,46,離 散 數(shù) 學(xué)Discrete Mathematics,山東科技大學(xué)信息科學(xué)與工程學(xué)院,第一章 命題邏輯第4講§1—7 對(duì)偶與范式,要求：掌握對(duì)偶與

29、范式，會(huì)求命題公式的主析取范式和主合取范式。 重點(diǎn)和難點(diǎn)：求命題公式的主析取范式和主合取范式。,一、對(duì)偶式1. 復(fù)習(xí)命題定律。見15頁表1-4.8,我們從表1-4.8可以看到命題定律除對(duì)合律外都是成對(duì)出現(xiàn)的，其不同的只是∨和∧互換。我們把這樣的公式稱作具有對(duì)偶規(guī)律。 定義1-7.1 在給定的命題公式中，將聯(lián)結(jié)詞∨換成∧，將∧換成 ∨，若有特殊變?cè)狥和T亦相互取代，所得公式A*稱作A的對(duì)偶式。

30、 顯然A也是A*的對(duì)偶式。,2. 對(duì)偶式的定義,,,,例題1 寫出下列表達(dá)式的對(duì)偶式。,(P ∧ Q) ∨ R(P ∨ Q) ∧ F┐(P ∧ Q) ∨ (P ∧ ┐(Q ∨ ┐S)),（a）(P∨Q) ∧R（b）(P∧Q) ∨T（c）┐(P ∨Q) ∧ (P∨ ┐(Q ∧ ┐S)),A,A*,,定理1-7.1 設(shè)A和A*是對(duì)偶式，P1， P2 ，…，Pn是出現(xiàn)在A和A*中的原子變?cè)瑒t┐A（ P1， P2 ，…，Pn

31、 ） ? A*（┐ P1，┐ P2 ，…，┐Pn ）A（┐ P1，┐ P2 ，…，┐Pn ） ? ┐A*（ P1， P2 ，…，Pn ）,證明 由德?摩根定律 (P∧Q) ? ┐(┐P ∨┐Q)， P ∨Q ? ┐(┐P ∧┐Q) 故 ┐A（ P1， P2 ，…，Pn ） ? A*（┐ P1，┐ P2 ，…，┐Pn ）同理 ┐A*（ P1， P2 ，…，Pn ） ? A（┐

32、 P1，┐ P2 ，…，┐Pn ）,例題3 設(shè)A*（S，W，R）是 ┐S∧ (┐W ∨ R) ，證明 A*（┐S， ┐W， ┐R） ? ┐A（S，W，R）,.所以 A*（┐S， ┐W， ┐R） ? ┐A（S，W，R）,證明 由于A*（S，W，R）是 ┐S∧ (┐W ∨ R) ，,則 A*（┐S， ┐W， ┐R）是 S∧ (W ∨

33、 ┐ R)，,但 A（S，W，R）是 ┐S ∨ (┐W ∧ R) ，,故 ┐A（S，W，R）是 ┐(┐S ∨ (┐W ∧ R),? S∧ (W ∨ ┐ R),定理1-7.2 設(shè)P1， P2 ，…，Pn是出現(xiàn)在公式A和B中的所有原子變?cè)绻鸄 ? B，則A* ? B*。,證明 因?yàn)锳 ? B，即,,,,,,是一個(gè)重言式，故,也是一個(gè)重言式。即,由定理1-