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

馮偉森Email：fws365@05二月2023離散數(shù)學(xué)計算機學(xué)院2023/2/5計算機學(xué)院2主要內(nèi)容1、聯(lián)結(jié)詞的完備集2、命題公式的蘊涵

1）九類蘊涵關(guān)系

2）蘊涵關(guān)系的基本性質(zhì)1.4聯(lián)結(jié)詞的完備集2023/2/5計算機學(xué)院3前面我們已經(jīng)介紹了最常見的6種邏輯聯(lián)結(jié)詞。他們都和自然語言中使用的聯(lián)結(jié)詞緊密相關(guān)，易于理解。不同聯(lián)結(jié)詞產(chǎn)生的真值表是互不相同的，根據(jù)對含兩個命題變元的公式的解釋方式看，共有2*2=4種不同的解釋，因而公式的真值表相應(yīng)有2*2*2*2=16種可能結(jié)果。對其中每一種真值表都應(yīng)該存在相應(yīng)的聯(lián)結(jié)詞。下面從真值表取值情況的角度定義幾個新的聯(lián)結(jié)詞。2023/2/5計算機學(xué)院4PQ1

2

3

4

567

8

9

10

11

12131415161

1100

10

01011101110000001101101100110001010101101010101001001110010111000Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTF下面是含兩個命題變元的所有公式的真值表所能取得的情況：2023/2/5計算機學(xué)院5PQP↑Q111001000111定義

1.14

設(shè)P和Q是命題公式，分別稱P↑Q和P↓Q為“與非”和“或非”命題公式。其相應(yīng)的真值表如下所示：

2023/2/5計算機學(xué)院6PQP↓Q111001000001由真值表可以看出P↑Q～（P∧Q）,P↓Q～（P∨Q）2023/2/5計算機學(xué)院7

根據(jù)聯(lián)結(jié)詞↑和↓的定義，不難證明下面的等價式。①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q

～（～P∧～Q）P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q

～（～P∨～Q）P∧Q2023/2/5計算機學(xué)院8這些等價式告訴我們，↑可由∧和～表示出來，↓可由∨和～表示出來，反過來，↑和↓都可以單獨表示出所有已知聯(lián)結(jié)詞，它們的這一性質(zhì)使得在邏輯電路設(shè)計中只用一種門式電路元件就能實現(xiàn)任何電路功能，當(dāng)然，元件的數(shù)量通常也顯得更多。2023/2/5計算機學(xué)院9還有一個二元聯(lián)結(jié)詞“

”,稱為條件否定，可以用下面的真值表定義：PQP

Q11100100

0

1

0

0顯然，P

Q～(P→Q)2023/2/5計算機學(xué)院10PQ123456789101112131415161

1100

10

01011101110000001101101100110001010101101010101001001110010111000至此我們定義了9個聯(lián)結(jié)詞，其中1個一元聯(lián)結(jié)詞，8個二元聯(lián)結(jié)詞。那么，還能不能定義出新的聯(lián)結(jié)詞呢？下面是含兩個命題變元的所有公式的真值表所能取得的情況：2023/2/5計算機學(xué)院11顯然公式1是永真式，2代表矛盾式，3代表Ｐ∨Q，4代表Q→P,5代表P→Q，6代表P↑Q，7是P，8是Q，9代表PQ，10代表PQ，11代表～Q，12代表～P，13代表P↓Q，14代表Q

P,15代表P

Q，16代表P∧Q，可見，已定義的9個聯(lián)結(jié)詞就是全部可以定義的聯(lián)結(jié)詞。2023/2/5計算機學(xué)院12

定義

1.15設(shè)S是由某些聯(lián)結(jié)詞構(gòu)成的集合，如果每個邏輯聯(lián)結(jié)詞的功能都能夠由S中的聯(lián)結(jié)詞實現(xiàn)，則稱S是聯(lián)結(jié)詞的一個功能完備集；進一步，如果去掉S中的任何一個聯(lián)結(jié)詞后，至少有一個聯(lián)結(jié)詞的功能不能由S中剩余的聯(lián)結(jié)詞實現(xiàn)時，則稱S是邏輯聯(lián)結(jié)詞的一個最小功能完備集。2023/2/5計算機學(xué)院13根據(jù)定義,我們知道{↑}、{↓}是最小的功能完備集，那么{～，∨，∧}是不是最小功能完備集？由于P∨Q～(～P∧～Q)，可見∨可由{～，∧}表達；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表達，這說明{～，∨，∧}不是最小功能完備集，但是在實際應(yīng)用中，普遍采用的功能完備集卻是{～,∨,∧},這也是邏輯系統(tǒng)中最主要的3個常用聯(lián)結(jié)詞。2023/2/5計算機學(xué)院14§1．6

命題公式的蘊涵定義1.18設(shè)A和B是兩個合適公式，如果在任何解釋下，A取值1時B也取值1，則稱公式A蘊涵公式B，并記AB。定理1.11

ABiffA→B為永真式。注意：蘊含和條件聯(lián)結(jié)詞→是完全不同的?！敲}聯(lián)結(jié)詞，A→B是一個命題公式；是公式間關(guān)系符，AB不是一個命題公式，僅表示A，B間的蘊含關(guān)系。2023/2/5計算機學(xué)院15基本蘊含（關(guān)系）式（蘊含定律）I1：P∧QP，P∧QQ

I2:～（P→Q）P，～（P→Q）～Q

I3：PP∨Q，QP∨Q

I4：～PP→Q，QP→Q√I5：P∧（P→Q）

Q

假言推論√I6：～Q∧（P→Q）～P拒取式（否定式假言推論）√I7：～P∧（P∨Q）

Q析取三段論√I8：（P→Q）∧（Q→R）

P→R

假言三段論擴充法則簡化法則2023/2/5計算機學(xué)院16基本蘊含（關(guān)系）式（續(xù)）√I9：（P∨Q）∧（P→R）∧（Q→R）

R

二難推論I10：（P→Q）∧（R→S）（P∧R）→（Q∧S）√I11：（PQ）∧（QR）

PR

等價三段論√I12：（P∨Q）∧（～P∨R）

Q∨R

歸結(jié)原理

[解釋：（～P→Q）∧（P→R）

Q∨R]2023/2/5計算機學(xué)院17蘊含關(guān)系的性質(zhì)①自反性AA②反對稱性:

如果AB，BA，

iffAB③AB且A為永真式，則B必為永真式2023/2/5計算機學(xué)院18

④傳遞性，如果AB，BC，則AC【證明】由已知條件AB，且BC，根據(jù)定理1.11

(A→B）∧（B→C）是永真式；再由假言三段論，應(yīng)有（A→B）∧（B→C）

A→C；再根據(jù)性質(zhì)3，A→C也必是永真式，即AC。■2023/2/5計算機學(xué)院19。⑤

如AB，AC，iffAB∧C【證明】“”由

AB

且

AC得到AB和AC都是永真式，于是（AB）∧（AC）也是永真式；但是，（AB）∧（AC）（～A∨B）∧(～A∨C)～A∨(B∧C)A→(B∧C)，所以A(B∧C)是永真式，即AB∧C。2023/2/5計算機學(xué)院20“”從證明過程看，性質(zhì)5反過來也對，即由

AB∧C可以得到AB

且

AC。

⑥如AB，CB，則A∨CB⑦A∧BCiffAB→C

該性質(zhì)是推理演繹中CP規(guī)則的基礎(chǔ)⑧

A

Biff

A∧～B是矛盾式

該性質(zhì)是反證法的基礎(chǔ)2023/2/5計算機學(xué)院21定理1.12

ABiff

～B～A

該定理提供了逆向思維的基礎(chǔ)2023/2/5計算機學(xué)院22例1-6.1考慮以下語句，并將其前提和結(jié)論符號化。1)、前提：

1.如果明天天晴，我們準(zhǔn)備外出旅游。P→Q

2．明天的確天晴。 P結(jié)論：我們外出旅游。 Q上述例子可描述為：P→Q，PQ(假言推論)2)、前提：1.如果一個人是單身漢，則他不幸福。P→Q2.如果一個人不幸福，則他死得早。

Q→R結(jié)論：單身漢死得早。

P→R上述例子可描述為：

P→Q，Q→RP→R(假言三段論)2023/2/5計算機學(xué)院23例1-6.1(續(xù)1)3)、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒有外出，根據(jù)上述案情可得前提如下：

前提：

1.兇手為王某或陳某。

P∨Q 2.如果王某是兇手，則他在作案當(dāng)晚必外出。

P→R 3.王某案發(fā)之晚并未外出。

～R結(jié)論：陳某是兇手。

Q則上述例子可描述為：

P→R，～R～P

(拒取式)

P∨Q，～PQ

(析取三段論)2023/2/5計算機學(xué)院24例1-6.1(續(xù)2