離散數(shù)學(xué)第1章-命題邏輯

.

重慶文理學(xué)院計算機(jī)學(xué)院

離散數(shù)學(xué).

離散數(shù)學(xué)第一篇數(shù)理邏輯.

數(shù)理邏輯邏輯學(xué)是一門研究人的思維形式和規(guī)律的學(xué)科。邏輯學(xué)可分為形式邏輯、辯證邏輯和數(shù)理邏輯三大類。數(shù)理邏輯是數(shù)學(xué)的一個分支，它用數(shù)學(xué)的方法研究推理的過程。推理是從一種判斷推出另一種判斷的思維過程。.

數(shù)理邏輯數(shù)學(xué)方法：采用一套符號、公式表示體系，使用已有的數(shù)學(xué)成果和方法，尤其是形式化的公理方法，對具體事物進(jìn)行抽象的形式化研究。數(shù)理邏輯的優(yōu)點(diǎn)：表達(dá)簡潔、推理方便、概括性好、易于分析。.

離散數(shù)學(xué)第一章命題邏輯.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其他連接詞與最小連接詞組1.6范式1.7公式的主范式1.8

推理理論.1.1

命題與連接詞

1.1.1命題的概念

1.1.2邏輯連接詞

.1.1.1命題的概念

定義1.1.1命題是具有真假意義的陳述句。

命題總是具有一個“值”，稱為真值。真值只有“真”和“假”兩種，“真”用符號T或1表示，“假”用符號F或0表示。只有能夠確定或能夠分辨其真假的陳述句才能稱為命題。一切沒有判斷內(nèi)容的句子、無所謂是非的句子，如感嘆句、疑問句、祈使句等不是命題。.1.1.1命題的概念例1.1.1判斷下列各語句是否為命題。(1).神州七號的成功發(fā)射是中國航天業(yè)的又一個壯舉。(2).地震是地球各大板塊相互擠壓造成的。(3).北京舉辦了2008年奧林匹克運(yùn)動會。(4).游客止步！(5).明天是否要下雨？(6).校園的景色真美！(7).如果功課不多，那么放學(xué)后我去打籃球。(8).我選修數(shù)學(xué)專業(yè)，或者我選修英語專業(yè)。(9).

x＋y＞5。.1.1.1命題的概念

有兩點(diǎn)需要注意：

■

命題是可分辨真假的陳述句，但不一定必須知道它的真假。

■悖論的陳述句不是命題，因為悖論往往產(chǎn)生自相矛盾的結(jié)論。..1.1.1命題的概念

命題分為原子命題和復(fù)合命題兩種類型。復(fù)合命題是由原子命題和連接詞復(fù)合而成。判斷一個命題是否為復(fù)合命題，其關(guān)鍵是連接詞是否出現(xiàn)。若出現(xiàn)，則是復(fù)合命題；若不出現(xiàn)，則是原子命題。一個原子命題通常用大寫字母或帶下標(biāo)的大寫字母表示，如P，Q，…或Pi，Qi，…。表示原子命題的符號稱為命題標(biāo)識符。一個命題標(biāo)識符如果表示確定的命題，稱為命題常量。如果命題標(biāo)識符只表示命題的位置標(biāo)志，稱為命題變元。命題變元不能確定真值，只有當(dāng)命題變元用一個特定命題取代時，命題變元才有真值。例如：用P和Q分別表示原子命題“我是中國人”和“我為中國的進(jìn)步感到驕傲”，那么復(fù)合命題“我是中國人而且我為中國的進(jìn)步感到驕傲”，則可表示為“P而且Q”。自然語言中“而且”這樣的連接詞是可用邏輯符號表示的。.1.1命題與連接詞1.1.1命題的概念

1.1.2邏輯連接詞

.1.1.2邏輯連接詞

自然語言中，常使用“或”、“與”、“如果…，那么…”等一些連接詞。連接詞是復(fù)合命題的重要組成部分，為了便于書寫和推理，必須對連接詞作出明確規(guī)定和符號化。下面介紹常用的五種連接詞：

1.否定

2.合取

3.析取

4.條件

5.

雙條件

.1.否定

定義1.1.2

設(shè)P是一個命題，P的否定是一個新的命題，記作?P，讀作“非P”。連接詞“?”表示命題的否定。若P為T，則?P為F；若P為F，則?P為T。命題P與其否定?P的關(guān)系如表1.1.1所示。

表1.1.1

連接詞“?”的真值表連接詞“?”表示自然語言中“非”、“不”、“沒有”的邏輯抽象。

.2.合取

定義1.1.3

設(shè)P和Q是兩個命題，由連接詞∧將P、Q聯(lián)接成復(fù)合命題，記作P∧Q

，讀作“P和Q的合取

”，或“P合取Q”。

當(dāng)且僅當(dāng)P、Q同時為T時，P∧Q為T。在其它情況下，P∧Q的真值為F。連接詞∧的真值如表1.1.2所示。表1.1.2

連接詞“∧”的真值表

連接詞“∧”表示自然語言中“而且”、“并且”、“既…，又…”等的邏輯抽象。.3.析取

定義1.1.4

設(shè)P和Q是兩個命題，由連接詞∨將P、Q聯(lián)接成復(fù)合命題，記作P∨Q

，讀作“P和Q的析取

”，或“P析取Q”。當(dāng)且僅當(dāng)P、Q同時為F時，P∨Q為F。在其它情況下，P∨Q的真值為T。連接詞∨的真值如表1.1.3所示。表1.1.3

連接詞“∨”的真值表連接詞“∨”表示自然語言中“或”、“或者”等邏輯抽象。在自然語言中的“或”是多義的，可表示“排斥或”，也可表示“可兼或”。析取連接詞表示的是“可兼或”。.3.析取“排斥或”也是一種連接詞，用表示。連接詞的真值如表1.1.4所示。.4.條件

定義1.1.5

設(shè)P和Q是兩個命題，由連接詞→將P、Q聯(lián)接成復(fù)合命題，記作P→Q，讀作“如果P，那么Q”，或“若P則Q”。在P→Q中，P稱為前件，Q稱為后件。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時，P→Q的真值為F，否則P→Q的真值為T。連接詞→的真值如表1.1.5所示。表1.1.5連接詞“→”的真值表

.4.條件在自然語言中，“如果…，則…”常常表示一種因果關(guān)系，否則無意義。但對數(shù)理邏輯中的條件命題P→Q來說，只要P、Q能夠分別確定真值，P→Q即成為命題。在自然語言中，“如果…”為假時，則往往無法判斷“如果…，則…”的真假。但在數(shù)理邏輯的條件命題中，該情況規(guī)定為“善意的推定”，即當(dāng)前提為F時，結(jié)論不論真假，條件命題的真值都為T。.5.雙條件

定義1.1.6

設(shè)P和Q是兩個命題，由連接詞?將P、Q聯(lián)接成復(fù)合命題，記作P?Q

，讀作“P當(dāng)且僅當(dāng)Q”。當(dāng)且僅當(dāng)P、Q的真值相同時，P?Q為T，在其它情況下，P?Q的真值為F。連接詞?的真值如表1.1.6所示。表1.1.6

連接詞“?”的真值表雙條件運(yùn)算符“?”表示自然語言中的“充分必要條件”、“當(dāng)且僅當(dāng)”等邏輯抽象。.邏輯連接詞小結(jié)

從上述對五個基本聯(lián)接詞的介紹，可得到以下幾個結(jié)論：復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，而與它們的內(nèi)容、意義無關(guān)，并且與連接詞所連接的兩個原子命題之間是否有關(guān)系無關(guān)?！?∨和?具有可交換性，而?,→不具有交換性。連接詞具有操作或運(yùn)算的意義。五個連接詞的優(yōu)先次序依次為?，∧,∨，→，?.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式1.5其他連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.2命題公式及命題公式的翻譯

1.2.1命題公式

1.2.2命題的翻譯

1.2.3命題公式的解釋

.1.2.1命題公式命題公式（也稱合式公式）的構(gòu)成必須遵循一定的規(guī)則，下面用歸納法定義合式公式。定義1.2.1合式公式是由下列規(guī)則形成的字符串：①原子命題變元是一個合式公式。②若A是合式公式，則(?A)是合式公式。③若A和B是合式公式，則(A∧B)、(A∨B)、(A→B)和(A?B)都是合式公式。④經(jīng)過有限次地使用①、②、③所得到的結(jié)果，都是合式公式。以上定義中，①稱為基礎(chǔ)，②、③稱為歸納，④稱為界限或結(jié)論。以下幾點(diǎn)需要注意：（1）命題公式是沒有真值的，只有對其變元進(jìn)行真值指派后，才具有真值；（2）命題公式無限多。

.1.2命題公式及命題公式的翻譯

1.2.1命題公式

1.2.2命題的翻譯

1.2.3命題公式的解釋

.1.2.2命題的翻譯

命題的翻譯在數(shù)理邏輯中很重要，進(jìn)行邏輯推理的第一步就是將自然語言中表述的命題翻譯成命題公式，然后再進(jìn)行推理求解或證明。定義1.2.2

把一個文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識符、連接詞和圓括號表示的合式公式，稱為命題的翻譯，或命題的符號化。命題符號化的步驟如下：（1）確定給定的句子是否為命題。若是命題，分解出原子命題，分別用不同的符號表示不同的原子命題。（2）判斷句子的連接詞是否為命題連接詞。若是，分解出連接詞，將其用相應(yīng)邏輯連接詞符號表示。（3）將表示各原子命題的符號、連接詞符號以及圓括號形成符號串，正確地表示命題。.1.2命題公式及命題公式的翻譯

1.2.1命題公式

1.2.2命題的翻譯

1.2.3命題公式的解釋

.1.2.3命題公式的翻譯

定義1.2.3對于命題公式A中的每個命題變元Pi

，任給一個指派S(Pi)或解釋I(Pi)，得到一種真值的組合S(P1),S(P2),…,S(Pn)或I(P1),I(P2),…,I(Pn)，稱為A的一個真值指派，或稱為A的一種解釋，記為S(A)或I(A)。例1.2.7設(shè)公式A為(?P∨Q)→R，若將P、Q、R分別用(0,0,0)替換，得到公式A的一種解釋，在這種解釋下，A的真值為假。同理還可用(0,0,1)、(0,1,0)、(0,1,1)、(1,0,0)、(1,0,1)、(1,1,0)、(1,1,1)其它7種不同的指派來對公式進(jìn)行解釋。由于公式中有P、Q、R三個不同的命題變元，每個命題變元只有0或1兩種方式的替換，因此公式A的不同指派有23＝8種。

.1.2.3命題公式的翻譯

定理1.2.1

若公式A中有n個不同的命題變元，則公式A具有2n種不同的真值指派。定義1.2.4

設(shè)A為一命題公式，對其中出現(xiàn)的命題變元做所有可能的真值指派S，連同在其解釋下A的取真值情況S(A)組成一個表，稱為A的真值表。為了真值表的書寫規(guī)范和方便，規(guī)定如下：（1）命題變元按英文字母字典序進(jìn)行排列，如A,B,C,…；帶有下標(biāo)的命題變元，則按下標(biāo)由小到大的數(shù)序排列，如P1,P2,…。（2）對公式的每種解釋，以二進(jìn)制從小到大或從大到小的順序列出。（3）若公式較為復(fù)雜，遵循從簡單到復(fù)雜，由括號里面到外面的原則。.計算機(jī)題目1、已知命題p和q的真值，求它們的合取、析取、條件和雙條件語句的真值。2、已知長度為n的兩個位串，求他們按位的AND、OR和XOR*3、給定m、n，交互玩曲奇餅游戲。.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其他連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.等價公式及公式的分類

有上一節(jié)例1.2.11可知，存在一些形式不相同的公式但它們的真值表是相同的，即一個真值表可表示多種形式不同的公式。若兩個公式的真值表完全相同，則這兩個公式等價。本節(jié)主要學(xué)習(xí)等價公式的定義和性質(zhì)、基本等價公式、置換規(guī)則及公式的分類等內(nèi)容。.1.3等價公式及公式的分類

1.3.1等價公式的定義和性質(zhì)

1.3.2基本等價公式

1.3.3置換規(guī)則

1.4.3公式的分類.1.3.1等價公式的定義和性質(zhì)

定義1.3.1

設(shè)A和B是兩個公式，設(shè)P1,P2,…,Pn為所有出現(xiàn)于A和B中的原子變元，若給P1,P2,…,Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等，記為A?B。

例1.3.1證明P?Q?(P∧Q)∨(?P∧?Q)

表1.3.1P?Q?(P∧Q)∨(?P∧?Q)

P?Q與(P∧Q)∨(?P∧?Q)的真值表相同，所以得證兩命題等價。.1.3.1等價公式的定義和性質(zhì)

等價式具有如下性質(zhì)：（1）自反性：對任意公式A，都有A?A。（2）對稱性：對任意公式A和B，若A?B

，則B?A

。（3）傳遞性：對任意公式A，B和C，若A?B且B?C

，則A?C。注意不要將符號“?”和符號“?”混淆?！?”是一個邏輯連接詞，表示當(dāng)且僅當(dāng)?shù)倪壿嫼x?！?”不是邏輯連接詞，它表示兩個公式之間的一種等價關(guān)系?！?”可連接任意兩個公式A、B，即A?B，表示A當(dāng)且僅當(dāng)B。但任意兩個公式之間不一定具有等價關(guān)系。.1.3等價公式及公式的分類

1.3.1等價公式的定義和性質(zhì)

1.3.2基本等價公式

1.3.3置換規(guī)則

1.4.3公式的分類.1.3.2基本等價公式

下表列出了一些基本的等價式，利用這些基本的等價式可進(jìn)行復(fù)雜公式的證明和推理。它們可由真值表予以驗證。

.分配律在抽象代數(shù)中，分配律是二元運(yùn)算的一個性質(zhì)，它是基本代數(shù)中的分配律的推廣。例如：2·(1+3)=(2·1)+(2·3).由于以上的等式對于任何實(shí)數(shù)都是成立的，我們稱實(shí)數(shù)的乘法對實(shí)數(shù)的加法滿足分配律。.1.3等價公式及公式的分類

1.3.1等價公式的定義和性質(zhì)

1.3.2基本等價公式

1.3.3置換規(guī)則

1.4.3公式的分類.1.3.3置換規(guī)則定義1.3.2若X是公式A的一部分，且X本身也是一個公式，則稱X為公式A的子公式。例1.3.3若公式A為Q→(P∨R)，則Q、P、R、P∨R均為公式A的子公式，而Q→、P∨、∨R均不為公式A的子公式。定理1.3.1設(shè)X是合式公式A的子公式，若X?Y，如果將A中的X用Y來置換，所得到的公式B與公式A等價，即A?B。證明：因為X?Y，所以在相同變元的任一種指派下，X與Y真值相同。以Y取代X后，公式B與公式A在相應(yīng)的指派情況下，其真值必相同，故A?B。

.1.3等價公式及公式的分類

1.3.1等價公式的定義和性質(zhì)

1.3.2基本等價公式

1.3.3置換規(guī)則

1.3.4公式的分類.1.3.4公式的分類

定義1.3.3

設(shè)A是一個公式，對A做所有可能的解釋I，對于這些解釋I：（1）若所有I(A)皆為真，則A為永真式或重言式。（2）若所有I(A)皆為假，則A為永假式。（3）若至少存在一個I(A)為真，則A為可滿足式。由定義1.3.3可知，永真式一定是可滿足式，但可滿足式不一定是永真式。永假式一定是不可滿足式，非永假式一定是可滿足式。利用等價推導(dǎo)可判斷公式A的類型，規(guī)則如下：（1）若A?T，則是永真式。（2）若A?F，則是永假式。（3）若A?B，B是可滿足式，則A是可滿足式，反之亦然。.1.3.4公式的分類

定理1.3.2

任何兩個永真式的合取或析取，仍是一個永真式。證明：設(shè)和為兩個永真式，則不論對A、B作何真值指派，總有A為T，B為T，因此(A∧B)?T，(A∨B)?T

。定理1.3.3

一個永真式A

，在任何一個原子命題變元R出現(xiàn)的每一處，用另一個公式代入，所得公式B仍為永真式。本定理稱為代入規(guī)則。證明：公式是A永真式，不論R做何種真值指派，A的真值永遠(yuǎn)是T。因此，用一個命題公式代入到原子變元R出現(xiàn)的每一處后，所得的命題公式的真值仍為真。

.1.3.4公式的分類

從上述定理可看出代入和置換的三點(diǎn)區(qū)別：（1）代入規(guī)則只能對永真式適用，置換規(guī)則可對任何公式適用。（2）代入是對原子命題而言，置換可對命題公式實(shí)行。（3）代入必須是處處代入，置換則可部分置換，也可全部置換。定理1.3.4

設(shè)A、B是公式，則A?B等價于A?B是永真式。證明：若A?B

，則A、B具有相同的真值，即A?B為永真式。若A?B為永真式，則A、B具有相同的真值，即A?B。.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其他連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.4蘊(yùn)含式與對偶式

1.4.1蘊(yùn)含式

1.4.2對偶式.1.4蘊(yùn)含式與對偶式1．蘊(yùn)含式的定義定義1.4.1

設(shè)A和B是兩個公式，如果A→B是永真式，則稱A蘊(yùn)含B，記作A?B。

注意符號‘→’和‘?’的區(qū)別：

‘→’是邏輯連接詞，代表“如果…那么”的邏輯關(guān)系；‘?’不是連接詞，它表示兩個公式之間的一種蘊(yùn)含關(guān)系。A?B成立，當(dāng)且僅當(dāng)A→B是永真式。.1.4蘊(yùn)含式與對偶式

蘊(yùn)含式具有如下性質(zhì)：（1）自反性：即對任意公式A，有A?A。（2）傳遞性：即對任意公式A、B和C，若A?B，B?C，則A?C。（3）對任意公式A、B和C，若A?B，A?C，則A?(B∧C)。（4）對任意公式A、B和C，若A?C，B?C，則A∨B?C。

常用蘊(yùn)含式：.1.4蘊(yùn)含式與對偶式2.

蘊(yùn)含式的證明（1）對P→Q來說，Q→P稱作它的逆換式；?P→?Q稱為它的反換式；?Q→?P稱為它的逆反式。含條件連接詞的公式與其逆反式等價，即P→Q??Q→?P。因此要證明P?Q，只需證明?Q??P，反之亦然。（2）要證P?Q，即證P→Q是永真式。.1.4蘊(yùn)含式與對偶式

常用的蘊(yùn)含式證明有三種方法。（1）真值表法。用真值表證明P→Q是永真式，即真值表中的最后一列都是1。該方法的優(yōu)點(diǎn)是直觀明了，缺點(diǎn)是當(dāng)命題變元較多時，構(gòu)造真值表的工作量較大。（2）通過等價式的推導(dǎo)。例1.4.2求證?Q∧(P→Q)??P證明：?Q∧(P→Q)→?P??(?Q∧(P→Q))∨?P條件轉(zhuǎn)化律

??(?Q∧(?P∨Q))∨?P德?摩根律?(Q∨(P∧?Q))∨?P分配律?(Q∨P)∧(Q∨?Q))∨?P否定律

?(Q∨P)∧T)∨?P同一律

?Q∨(P∨?P)否定律?Q∨T零律?T.1.4蘊(yùn)含式與對偶式（3）條件假定推演法

對于式P→Q，除P的真值取T、Q的真值取F這種指派的情況下P→Q的真值為F，其余情況P→Q的真值為T。因此，要證明P?Q，只需對條件命題P→Q的前件P指定真值為T時，能推出后件Q的真值也為T。該證明方法為肯定前件推導(dǎo)后件為真的方法。同理，由于P→Q??Q→?P，還存在否定后件推導(dǎo)前件為假的方法。①肯定前件推導(dǎo)后件為真的方法假定條件式的前件為真，若能推導(dǎo)出后件也為真，則條件式是永真式，即蘊(yùn)含式成立。下面用肯定前件推導(dǎo)后件為真的方法證明例1.4.2。證明方法3：假定﹁Q∧(P→Q)為T，則﹁Q為T，且P→Q為T。因此Q為F，要使P→Q為T，則必須P為F，故﹁P為T。②否定后件推導(dǎo)前件為假的方法

假定條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)含式成立。.1.4蘊(yùn)含式與對偶式

1.4.1蘊(yùn)含式

1.4.2對偶式.1.4.2對偶式

通過觀察可以發(fā)現(xiàn)，很多基本等價式都是成對出現(xiàn)的。這些成對出現(xiàn)的基本等價式就是對偶式。定義1.4.2

在給定的僅使用﹁、∧和∨的命題公式A中，若把

∧和∨互換，F(xiàn)和T互換而得到一個命題公式A*，則稱A*為A的對偶式。顯然，A也是A*的對偶式，即A與A*互為對偶式。例1.4.3

寫出下列公式的對偶式：

①(P∨Q)∧R②﹁(P∧Q)∧S

解：①的對偶式為(P∧Q)∨R

②的對偶式為﹁(P∨Q)∨S

定理1.4.1

設(shè)A和A*互為對偶式，P1,P2,…,Pn是出現(xiàn)在A和A*中的原子變元，則

①﹁A(P1,P2,…,Pn)?A*(﹁P1,﹁P2,…,﹁Pn)；

②A(﹁P1,﹁P2,…,﹁Pn)?﹁A*(P1,P2,…,Pn)。

.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其它連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.5其它連接詞與最小連接詞組

1.5.1其它連接詞

1.5.2最小連接詞組.1.5.1其它連接詞定義1.5.1設(shè)P和Q是兩個命題公式，復(fù)合命題P↑Q稱作P和Q的“與非”。當(dāng)且僅當(dāng)P和Q的真值均為T時，P↑Q為F，否則P↑Q的真值為T。

P↑Q的真值表

從上表可知P↑Q?﹁(P∧Q)。連接詞“↑”具有如下性質(zhì)：（1）P↑P?﹁(P∧P)?﹁P

（2）(P↑Q)↑(P↑Q)??(P↑Q)?P∧Q（3）(P↑P)↑(Q↑Q)??P↑?Q??(?P∧?Q)?P∨Q.1.5.1其它連接詞定義1.5.2

設(shè)P和Q是兩個命題公式，復(fù)合命題P↓Q稱作P和

Q的“或非”。當(dāng)且僅當(dāng)P和Q的真值均為F時，P↓Q的真值為T，否則P↓Q的真值為F。

P↓Q的真值表從上表可知P↓Q?﹁(P∨Q)。連接詞“↓”或具有如下性質(zhì)：

（1）P↓P??(P∨P)??P（2）(P↓Q)↓(P↓Q)??(P↓Q)?P∨Q（3）(P↓P)↓(Q↓Q)??P↓?Q??(?P∨?Q)?P∧Q.1.5.1其它連接詞

定義1.5.3

設(shè)P和Q是兩個命題公式，復(fù)合命題稱作命題P和Q的條件否定，的真值為T，當(dāng)且僅當(dāng)P真值為T，Q真值為F，否則的真值為F。的真值表

由定理1.2.1可知，含有2個命題變元的公式具有4種不同的真值指派。在每種指派下，公式的真值只能取真、假兩種情況。因此，2個命題變元可構(gòu)成24個不等價的命題公式。如表1.5.4所示。

.1.5.1其它連接詞表1.5.42個變元構(gòu)成的不等價命題公式由表1.5.4可看出：F0

和F1分別表示永真式和永假式；F2和F3分別表示命題變元P、Q；F4和F5分別表示命題變元的否定?P、?Q；F6表示“合取”命題P∧Q；F7表示“與非”命題P↑Q

；F8表示“析取”命題P∨Q

；F9表示“或非”命題P↓Q

；F10、F14分別表示條件命題P→Q、Q→P；F11、F15分別表示條件否定命題、；F12表示雙條件命題P?Q；F13表示“排斥或”命題。

.1.5其它連接詞與最小連接詞組

1.5.1其它連接詞

1.5.2最小聯(lián)接詞組.1.5.2最小連接詞組

定義1.5.4如果連接詞組G滿足下列兩個條件：（1）由G中的連接詞構(gòu)成的公式能等價表示任意命題公式。（2）G中的任一連接詞不能用其余的連接詞表示；則稱G為最小連接詞組。{﹁,∨}，{﹁,∧}，{﹁,→}，{↑}，{↓}都是最小連接詞組。例1.5.1證明{﹁,∨}是一個最小連接詞組。證明：對任意公式P、Q，

{﹁,∨}可等價表示其余7個連接詞構(gòu)成的公式，且{﹁,∨}中任一連接詞不能用該集合中余下的連接詞等價表示。得證{﹁,∨}是一個最小連接詞組。{?,?},{?},{∧},{∨},{∧,∨}和{?,∨,∧}雖然不是最小連接詞組，但為了表示方便，仍經(jīng)常使用聯(lián)接詞組{﹁,∧,∨}。

.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其它連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.6范式

1.6.1簡單合取式與簡單析取式

1.6.2公式的范式.1.6范式

一個公式可以具有多種相互等價的表達(dá)方式，例如：P?Q?(P→Q)∧(Q→P)?(P∧Q)∨(?P∧?Q)。為了減少同一公式的不同表達(dá)形式對解決推理問題所帶來的麻煩，需要將公式標(biāo)準(zhǔn)化。另外，使用真值表、對偶定理可判斷兩個公式是否等價。除此之外，還可以通過比較公式的標(biāo)準(zhǔn)形式的方法來判斷公式的等價性。公式的標(biāo)準(zhǔn)形式就是范式。.1.6.1簡單合取式與簡單析取式

定義1.6.1在一公式中，僅由命題變元及其否定構(gòu)成的合取式，稱為該公式為簡單合取式，其中每個命題變元或者其否定，稱為合取項。例如：P、Q、﹁P、﹁Q、P∧Q、﹁P∧Q、﹁P∧﹁Q、﹁P∧Q∧﹁Q均是簡單合取式。(P∧Q)∨﹁Q、(﹁P∨Q)∧﹁Q均不是簡單合取式。

定義1.6.2在一公式中，僅由命題變元及其否定構(gòu)成的析取式，稱為該公式為簡單析取式，其中每個命題變元或者其否定，稱為析取項。例如：P、Q、﹁P、﹁Q、P∨Q、﹁P∨Q、﹁P∨﹁Q、﹁P∨Q∨﹁Q均是簡單析取式。(P∨Q)∧﹁Q、(﹁P∧Q)∨﹁Q均不是簡單析取式。注意：單獨(dú)一個命題變元或其否定既可以是簡單合取式，也可以是簡單析取式。例如P、﹁P等既是簡單合取式，也是簡單析取式。定理1.6.1設(shè)A是一個公式，那么（1）若A是簡單合取式，則A是永假式等價于A的合取項中同時有某個命題變元及其否定。（2）若A是簡單析取式，則A是永真式（或重言式）等價于A的析取項中同時有某個命題變元及其否定。.1.6范式

1.6.1簡單合取式與簡單析取式

1.6.2公式的范式.1.6.2公式的范式

定義1.6.3一個命題公式A稱為合取范式，當(dāng)且僅當(dāng)A可表示為簡單析取式的合取，即A=A1∧A2∧…∧An，其中A1,A2,…,An為簡單析取式。例如：(P∨Q)∧(﹁P∨R)∧﹁R，P∧Q，﹁Q均是合取范式。定義1.6.4一個命題公式A稱為析取范式，當(dāng)且僅當(dāng)A可表示為簡單合取式的析取，即A=A1∨A2∨…∨An，其中A1,A2,…,An為簡單合取式。例如：(﹁P∧Q)∨﹁R，P∨Q，P∧Q，﹁Q均是析取范式。定理1.6.2任何一個命題公式都存在與其等價的析取范式和合取范式。通過以下三個步驟可對任何命題公式求取等價的析取范式或合取范式。（1）將公式化為只含有∧，∨及﹁連接詞的公式。（2）利用徳·摩根律將否定符號﹁直接轉(zhuǎn)移到各個命題變元之前。（3）利用分配律、結(jié)合律將公式歸為合取范式或析取范式。.1.6.2公式的范式

定理1.6.3

設(shè)A是一個公式，那么（1）A為永假式等價于A的析取范式中每個簡單合取式至少包含一個命題變元及其否定。（2）A為永真式等價于A的合取范式中每個簡單析取式至少包含一個命題變元及其否定。

.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其它連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.7公式的主范式

1.7.1主析取范式

1.7.2主合取范式

1.7.3主析取范式與主合取范式之間的關(guān)系

1.7.4主范式的應(yīng)用.1.7.1主析取范式

1．小項的定義及性質(zhì)定義1.7.1

在含有n個命題變元的簡單合取式中，若每個命題變元與其否定不同時存在，但兩者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單合取式為小項，或布爾積。例如，對兩個命題變元P和Q，其小項為：P∧Q，P∧﹁Q，﹁P∧Q，﹁P∧﹁Q。小項的真值表如下表所示。

.1.7.1主析取范式

在表1.7.2中，如果將命題變元按字典序排列，并把命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)，則可對2n個小項依二進(jìn)制數(shù)編碼，記為mi，下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。即

由n個命題變元生成的小項具有如下性質(zhì)：（1）每個小項具有一個相應(yīng)的編碼，當(dāng)該編碼與其真值指派相同時，該小項真值為T，在其余2n-1種指派情況下為F。任何兩個不同的小項不等價。

（2）任何兩個不同小項的合取為永假式，即。

（3）所有小項的析取為永真式。.1.7.1主析取范式

2.

主析取范式的定義及求法

定義1.7.2

對于給定的命題公式，若有一等價公式僅由小項的析取組成，則該等價式稱作原式的主析取范式。定理1.7.1

在真值表中，一個公式的真值為T的指派所對應(yīng)小項的析取，即為此公式的主析取范式。

定理1.7.2

任意含n個命題變元的非永假命題公式都存在且唯一存在與其等價的主析取范式。

.1.7.1主析取范式求主析取范式的方法有真值表法和基本等價公式化歸法。定理1.7.1已給出真值表求主析取范式法。

基本等價公式化歸法的推演步驟如下：（1）將給定公式化為析取范式。（2）刪除析取范式中永假的析取項。（3）應(yīng)用等冪律將重復(fù)出現(xiàn)的命題變元合并，化簡為一次出現(xiàn)，如P∧P?P。（4）在簡單合取式中補(bǔ)入沒有出現(xiàn)的命題變元，即添加(P∨﹁P)式，然后應(yīng)用分配律展開。

.1.7公式的主范式

1.7.1主析取范式

1.7.2主合取范式

1.7.3主析取范式與主合取范式之間的關(guān)系

1.7.4主范式的應(yīng)用.1.7.2主合取范式

1.大項的定義定義1.7.3

在含有n個命題變元的簡單析取式中，若每個命題變元及其否定不同時存在，但二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單析取式為大項，或布爾和。例如，對于兩個命題變元P和Q，其大項為：P∨Q，P∨﹁Q，﹁P∨Q，﹁P∨﹁Q，共4個。其真值表見表1.7.5。

.1.7.2主合取范式如果將命題變元按字典序排序，并把命題變元與0對應(yīng)，命題變元的否定與1對應(yīng)，則可對2n個大項依二進(jìn)制編碼，記為Mi，下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。例如：當(dāng)有2個命題變元時，M0=P∨Q

M1=P∨﹁QM2=﹁P∨Q

M3

=﹁P∨﹁Q當(dāng)有3個命題變元時，M0=P∨Q∨R

M1=P∨Q∨﹁RM2=P∨﹁Q∨R

M3=P∨﹁Q∨﹁RM4=﹁P∨Q∨R

M5=﹁P∨Q∨﹁RM6=﹁P∨﹁Q∨R

M7=﹁P∨﹁Q∨﹁R.1.7.2主合取范式

大項的性質(zhì)：（1）每個大項具有一個相應(yīng)的編碼，當(dāng)該編碼與其真值指派相同時，該大項真值為F，在其余2n-1種指派下均為T。任何兩個不同的大項不等價。（2）任何2個不同大項的析取為永真式，即Mi∨Mj?T(i≠j

)。（3）所有大項的合取為永假，即.1.7.2主合取范式

2.主合取范式的定義及求法定義1.7.4對于給定的命題公式，若有一等價公式僅由大項的合取所組成，則該等價式稱為原式的主合取范式。定理1.7.3

在真值表中，一個公式的真值為F的指派所對應(yīng)的大項的合取，即為此公式的主合取范式。例1.7.4求(P→Q)∧Q的主合取范式。解：公式(P→Q)∧Q的真值表如表1.7.7所示。因此，(P→Q)∧Q?(P∨Q)∧(﹁P∨Q)。

.1.7.2主合取范式

定理1.7.4

任意含n個命題變元的非永真命題公式都存在且唯一存在與其等價的主合取范式。求主合取范式有真值表法和基本等價化歸法?；镜葍r化歸法的推演步驟：（1）將給定公式化為合取范式。（2）刪除合取范式中所有為永真的合取項。（3）應(yīng)用等冪律合并相同的簡單合取式和相同的變元。（4）對簡單析取式補(bǔ)入沒有出現(xiàn)的命題變元，即添加(P∧?P)式，然后應(yīng)用分配律展開。.1.7公式的主范式

1.7.1主析取范式

1.7.2主合取范式

1.7.3主析取范式與主合取范式之間的關(guān)系

1.7.4主范式的應(yīng)用.1.7.3主析取范式與主合取范式之間的關(guān)系

主析取范式由小項構(gòu)成，主合取范式由大項構(gòu)成。小項與大項的關(guān)系：mi??Mi

Mi??mi

為了使主范式表示得更加簡潔、明了，可用符號∑表示小項的析取，如∑i,j,k表示mi∨mj∨mk，用∏表示大項的合取，如∏i,j,k表示Mi∧Mj∧Mk

。.1.7.3主析取范式與主合取范式之間的關(guān)系

定理1.7.5如果含有n個命題變元的公式A的主析取范式為則的主合取范式為。由定理1.7.5可知，從公式A的主析取范式可求其主合取范式。步驟為：（1）求出A的主析取范式中沒有包含的小項。（2）求出與(1)中小項的下標(biāo)相同的大項。（3）將(2)中大項進(jìn)行合取，即為A的主合取范式。例1.7.8

求的主析取范式和主合取范式。解：主析取范式：

主合取范式：

.1.7公式的主范式

1.7.1主析取范式

1.7.2主合取范式

1.7.3主析取范式與主合取范式之間的關(guān)系

1.7.4主范式的應(yīng)用.1.7.4主范式的應(yīng)用

1.公式類型的判定根據(jù)給定含有n個變元公式A的主范式按下述條件可判定公式的類型。（1）若公式A可化為含2n個不同小項的等價主析取范式，則A為永真式。（2）若公式A可化為含2n個不同大項的等價主合取范式，則A為永假式。（3）若公式A可化為含小項且小項個數(shù)小于2n個的主析取范式，或可化為含大項且大項個數(shù)小于2n個的主合取范式，則A為可滿足式。.1.7.4主范式的應(yīng)用

2.等價式的證明由于任一公式的主范式是唯一的，所以若兩個公式的主范式相同則給定的兩個公式是等價的。例1.7.10證明證明：由于兩公式具有相同的主析取范式，則兩公式等價。.第一章命題邏輯1.1命題與連接詞1.2命題公式及命題公式的翻譯1.3等價公式及公式的分類1.4蘊(yùn)含式與對偶式1.5其他連接詞與最小連接詞組1.6范式1.7公式的主范式1.8推理理論.1.8推理理論

1.8.1有效論證

1.8.2推理方法.1.8.1有效論證

定義1.8.1設(shè)A和B是兩個命題公式，當(dāng)且僅當(dāng)A→B為一永真式(或重言式)，即A?B，稱B是A的有效結(jié)論，或B可由A邏輯推出。上述定義可推廣至n個前提的情況。設(shè)H1,H2,…,Hn,B是命題公式，當(dāng)且僅當(dāng)H1∧H2∧…∧Hn?B才稱B是前提集合{H1,H2,…,Hn}的有效結(jié)論，或由{H1,H2,…,Hn}可邏輯地推出B。.1.8推理理論

1.8.1有效論證

1.8.2推理方法.1.8.2推理方法推理方法有多種，常用的推理方法有真值表法、直接證法和間接證法。

1.真值表法構(gòu)造條件式H1∧H2∧…∧Hm→B的真值表，若它為永真式，則結(jié)論B是有效的。例1.8.1如果張老師來了，這個問題可以得到解答。如果李老師來了，這個問題也可以得到解答?？傊灰獜埨蠋熁蚶罾蠋焷砹?，這個問題可得到解答。解：設(shè)P：張老師來了。Q：李老師來了。R：這個問題可得到解答。題設(shè)的語句可翻譯成

.1.8.2推理方法其真值表如下表所示。

從真值表1.8.1中可得到永真式，故有

.1.8.2推理方法

2.直接證法直接證法是由一組前提條件，利用公認(rèn)的推理規(guī)則，根據(jù)等價公式或蘊(yùn)含式，推導(dǎo)得到有效結(jié)論。常用等價公式如表1.8.2和蘊(yùn)含式如表1.8.3。公認(rèn)的推理規(guī)則如下：

P規(guī)則：前提在推導(dǎo)過程中的任何時候都可以引入使用。

T規(guī)則：在推導(dǎo)中，如果有一個或多個公式永真蘊(yùn)含公式S，則可把S引入到推導(dǎo)過程之中。