離散數(shù)學課堂(左孝凌版)課件

第一章命題邏輯1－1命題及其表示法1.什么是命題命題：能判斷真假的陳述句。命題的值叫它的真值。真值：“真”：表示判斷正確。記作True，用T表示。 “假”：表示判斷錯誤。記作False，用F表示。1第一章命題邏輯1例1判斷下列句子中哪些是命題？（1）2是素數(shù)。（2）雪是黑色的。（3）2+3=5

（4）明年10月1日是晴天。（5）3能被2整除。（6）這朵花真好看呀！（7）明天下午有會嗎？（8）請關(guān)上門?。?）X+Y>5

（10）地球外的星球上也有人。（11）我正在說謊。2例1判斷下列句子中哪些是命題？22．命題的符號化表示命題的符號化就是用符號表示命題。 簡單命題（或原子命題）：簡單陳述句表示的命題。用P，Q，R,…,Pi,Qi,Ri,…表示。例P:2是偶數(shù)。

Q:雪是黑色的。 命題常量（或命題常元）：簡單命題。 命題變項（或命題變元）：真值可以變化的簡單陳述句。不是命題。例：x+y>5

32．命題的符號化表示3命題變項也用P，Q，R,…,

Pi,Qi,Ri,…表示。復合命題：由簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。4命題變項也用P，Q，R,…,Pi,Qi,Ri,…表示。4例2將下列命題符號化。 （1）3不是偶數(shù)。 （2）2是素數(shù)和偶數(shù)。 （3）林芳學過英語或日語。 （4）如果角A和角B是對頂角，則角A等于角B。解：（1）設(shè)P：3是偶數(shù)。?P （?：表示并非） （2）設(shè)P：2是素數(shù)；Q：2是偶數(shù)。

P∧Q (∧:表示和)

（3）設(shè)P：林芳學過英語；Q：林芳學過日語。

P∨Q (∨:表示或)

（4）設(shè)P：角A和角B是對頂角；Q：角A等于角B。

P→Q （→個表示如果……則……）5例2將下列命題符號化。5 1－2.聯(lián)結(jié)詞定義1－2.1

設(shè)P為任一命題，P的否定是一個新的命題，稱為P的否定式，記作?P。?為否定聯(lián)結(jié)詞。P?PTFFT例p：3是偶數(shù)。

?p：3不是偶數(shù)。

6 1－2.聯(lián)結(jié)詞P?PTFFT例定義1－2.2

設(shè)P、Q為兩命題，復合命題“P并且Q”（或“P和Q”）稱為P與Q的合取式，記作P∧Q，∧為合取聯(lián)結(jié)詞。 ∧表示自然語言中的“既……又……”，“不僅……而且……”，“雖然……但是”PQP∧QTTTTFFFTFFFF7定義1－2.2設(shè)P、Q為兩命題，復合命題“P并且Q”（或“例3將下列命題符號化。（1）李平既聰明又用功。（2）李平雖然聰明，但不用功。（3）李平不但聰明，而且用功。（3）李平不是不聰明，而是不用功。解：設(shè)P：李平聰明；Q：李平用功。（1）P∧Q（2）P∧?Q（3）P∧Q（4）?（?P）∧?Q注意：不是見到“和”、“與”就用∧。例：“李文和李武是兄弟”，“王芳和陳蘭是好朋友”是簡單命題。8例3將下列命題符號化。8定義1－2.3

設(shè)P、Q為兩命題，復合命題“P或Q”稱為P與Q的析取式，記作P∨Q，∨為析取聯(lián)結(jié)詞。PQP∨QTTTTFTFTTFFF9定義1－2.3設(shè)P、Q為兩命題，復合命題“P或Q”稱為P

析取式P∨Q表示的是一種相容性或，即允許P和Q同時為真。例：“王燕學過英語或日語”P∨Q

自然語言中的“或”具有二義性，有時表示不相容的或。例：“派小王或小李中的一人去開會”。為排斥性的或。P：派小王去開會；Q：派小李去開會。 （P∧?Q）∨（?P∧Q），（P∨Q）∧?（P∧Q）10析取式P∨Q表示的是一種相容性或，即允許P和Q同時為定義1－2.4

設(shè)P、Q為兩命題，復合命題“如果P，則Q”稱作P與Q的蘊涵式，記作P→Q，→為蘊涵聯(lián)結(jié)詞。PQP→QTTTTFFFTTFFT11定義1－2.4設(shè)P、Q為兩命題，復合命題“如果P，則Q”稱

在P→Q中，Q是P的必要條件，P是Q的充分條件。表示自然語言“只要P就Q”，“P僅當Q”，“只有Q，才P”注意：1.在自然語言中，“如果P，則Q”中的P與Q往往有某種內(nèi)在的聯(lián)系，但在數(shù)理邏輯中，P→Q中的P與Q不一定有內(nèi)在的聯(lián)系。2.在數(shù)學中，“如果P，則Q”表示P為真，Q為真的邏輯關(guān)系，但在數(shù)理邏輯中，當P為假時P→Q為真。12在P→Q中，Q是P的必要條件，P是Q的充分條件。表示例4將下列命題符號化。(1)只要不下雨，我就騎自行車上班。(2)只有不下雨，我才騎自行車上班。(3)若2+2＝4，則太陽從東方升起。(3)若2+2≠4，則太陽從東方升起。(4)若2+2＝4，則太陽從西方升起。(5)若2+2≠4，則太陽從西方升起。解：在（1）、（2）中，設(shè)P：天下雨；Q：我騎自行車上班。 （1）?P→Q （2）Q→?P在（3）－（6）中，設(shè)P：2+2＝4；Q：太陽從東方升起；R:太陽從西方升起。（1）P→Q，真值為T（2）?P→Q，真值為T（3）P→R，真值為F（4）?P→R真值為T13例4將下列命題符號化。13定義1-2.5

設(shè)P、Q為兩命題，復合命題“P當且僅當Q”稱作P與Q的等價式，記作P?

Q，?

為等價聯(lián)結(jié)詞。P?Q表示P與Q互為充分必要條件。

PQP?QTTTTFFFTFFFT14定義1-2.5設(shè)P、Q為兩命題，復合命題“P當且僅當例5將下列命題符號化。（1）2+2＝4，當且僅當3是奇數(shù)。（2）2+2＝4，當且僅當3不是奇數(shù)。（3）2+2≠4，當且僅當3是奇數(shù)。（4）2+2≠4，當且僅當3不是奇數(shù)。（5）兩圓的面積相等，當且僅當它們的半徑相同。（6）兩角相等當且僅當它們是對頂角。解：（1）－（4）設(shè)P：2+2＝4；Q：3是奇數(shù)。（1）P?Q 真命題（2）P??Q假命題（3）?P?Q 假命題 （4）?P??Q 真命題（5）設(shè)P：兩圓的面積相等；Q：兩圓的面積相同。

P?Q 真命題（6）設(shè)P：兩角相等；Q：它們是對頂角。

P?Q 假命題15例5將下列命題符號化。154.5種聯(lián)結(jié)詞的優(yōu)先級順序：?，∧，∨，→，?

164.5種聯(lián)結(jié)詞的優(yōu)先級順序：?，∧，∨，→，?16

1-3命題公式與翻譯

1.命題公式命題公式：由命題常量、命題變元、聯(lián)結(jié)詞、括號等組成的符號串。

命題公式中的命題變元稱作命題公式的分量。171-3命題公式與翻譯17定義1－3.1（1）單個命題常量或命題變元,Q,R,…,Pi,Qi,Ri,…，F(xiàn)，T是合式公式。（2）如果A是合式公式，則（?A）也是合式公式。（3）如果A、B是合式公式，則（A∧B）、（A∨B）、（A→B）、（A?B）也是合式公式。（4）只有有限次地應用（1）－（3）組成的符號串才是合式公式。 例：P,?P,(?P)),(0∧P),P→(P→Q),((P∨Q)→R)→(?R)是公式；

PQ→R,,?(P→),?P→Q)不是公式。18定義1－3.1182.翻譯翻譯就是把自然語言中的有些句子符號化。復合命題符號化的基本步驟：（1）分析出各簡單命題，將它們符號化。（2）使用合適的聯(lián)結(jié)詞，把簡單命題逐個聯(lián)結(jié)起來，組成復合命題的符號化表示。192.翻譯19例將下列命題符號化。（1）小王是游泳冠軍或是百米冠軍。P∨Q（2）小王現(xiàn)在在宿舍或在圖書館。P∨Q（排斥性或，不可能同時為真）(3)選小王或小李中的一人當班長。（P∧?Q）∨（?P∧Q）或?（P?Q）（排斥性或，可能同時為真）PQ原命題P?Q?（P?Q）TTFTFTFTFTFTTFTFFFTF20例將下列命題符號化。PQ原命題P?Q?（P?Q）TTFTF(4)如果我上街，我就去書店看看，除非我很累。?R→(P→Q)或（?R∧P）→Q（除非：如果不）(5)王一樂是計算機系的學生，他生于1968年或1969年，他是三好學生。P∧（Q∨R）∧S（6）我們要做到身體好、學習好、工作好，為祖國四化建設(shè)而奮斗。A：我們要做到身體好B：我們要做到學習好C：我們要做到工作好P：我們要為祖國四化建設(shè)面奮斗。命題符號化形式為：（A∧B∧C）?P21(4)如果我上街，我就去書店看看，除非我很累。21

1－4真值表與等價公式1.真值表定義1－4.1含n個（n≥1）個命題變元（分量）的命題公式，共有2n組真值指派。將命題公式A在所有真值指派之下取值的情況列成表，稱為A的真值表。 構(gòu)造真值表的步驟：(1)找出命題公式中所含的所有命題變元P1,P2,…,Pn。列出所有可能的真值指派。(2)對應每種真值指派，計算命題公式的各層次的值，直到最后計算出命題公式的值。221－4真值表與等價公式22例1構(gòu)造求?P∨Q的真值表。PQ?P?P∨QTTFTTFFFFTTTFFTT23例1構(gòu)造求?P∨Q的真值表。PQ?P?P∨QTTFTTFF例2給出（P∧Q）∧?P的真值表。PQP∧Q?P（P∧Q）∧?PTTTFFTFFFFFTFTFFFFTF24例2給出（P∧Q）∧?P的真值表。PQP∧Q?P（P∧Q例3給出（P∧Q）∨（?P∧?Q）的真值表。PQ?P?QP∧Q?P∧?Q（P∧Q）∨（?P∧?Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT25例3給出（P∧Q）∨（?P∧?Q）的真值表。PQ?P?Q例4給出?（P∧Q）?（?P∨?Q）的真值表。PQP∧Q?（P∧Q）?P?Q?P∨?Q?（P∧Q）?（?P∨?Q）TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT

由以上例子可以看出有一類命題公式不論各命題變元作何種批派，其值永為真（假），我們把這類公式記為T（F）。如例4和例226例4給出?（P∧Q）?（?P∨?Q）的真值表。PQP∧Q?

2．等價公式從真值表中可以看到，有些命題公式在分量的各種指派下，其對應的真值都完全相同，如?P∨Q與P→Q的對應真值相同。PQ?P?P∨QP→QTTFTTTFFFFFTTTTFFTTT（P∧Q）∨（?P∧?Q）與P?Q對應的真值相同。27 2．等價公式PQ?P?P∨QP→QTTFTTTFFFFF

定義1－4.2

給定兩個命題公式A和B，設(shè)P1，P2，…，Pn為所有出現(xiàn)于A和B中的原子變元,若給P1，P2，…，Pn任一組真值指派,A和B的真值都相同,則稱A和B是等價的或邏輯相等。記作A?B。例5證明P?Q?（P→Q）∧（Q→P）證明列出真值表PQP→QQ→P(P→Q）∧(Q→P）P?QTTTTTTTFFTFFFTTFFFFFTTTT28定義1－4.2給定兩個命題公式A和B，設(shè)P1，

24個重要的等價式P???P 雙重否定律P?P∨P 等冪律P?P∧PP∨Q?Q∨P 交換律P∧Q?Q∧P（P∨Q）∨R?P∨（Q∨R） 結(jié)合律（P∧Q）∧R?P∧（Q∧R）P∨（Q∧R）?（P∨Q）∧（P∨R） 分配律P∧（Q∨R）?（P∧Q）∨（P∧R）?（P∨Q）??P∧?Q 德·摩根律?（P∧Q）??P∨?Q29 24個重要的等價式29P∨（P∧Q）?P 吸收律P∧（P∨Q）?PP∨T?T 零律P∧F?FP∨F?P 同一律P∧T?PP∨?P?T 排中律P∧?P?F 矛盾律P→Q??P∨Q 蘊涵等價式P?

Q?（P→Q）∧（Q→P） 等價等價式P→Q??Q→?P 假言易位P?

Q??P??Q 等價否定等價式（P→Q）∧（P→?Q）??P 歸謬論

其中P、Q和R代表任意的命題公式。30P∨（P∧Q）?P 吸收律30例6驗證吸收律 P∨（P∧Q）?P和

P∧（P∨Q）?PPQP∧QP∨（P∧Q）P∨QP∧（P∨Q）TTTTTTTFFTTTFTFFTFFFFFFF31例6驗證吸收律 P∨（P∧Q）?P和PQP∧QP∨（P∧

定義1-4.3

如果X是合式公式A的一部分,且X本身也是一個合式公式,則稱X為公式A的子公式。 定理1－4.1如果X是合式公式A的子公式，若X?Y，如果將A中的X用Y來置換，所得到公式B與公式A等價，即A?B。證明因為在相應變元的任一種指派下，X與Y的真值相同，故以Y取代X后，公式B與公式A在相應的指派下，其真值必相同，故A?B。

滿足定理1－4.1的置換稱為等價置換（等價代換）32 定義1-4.3如果X是合式公式A的一部分,且X本身也是一例7證明P→Q??（P∧?Q）證明P→Q??P∨Q，（根據(jù)蘊涵等價式）

?P∨Q??（P∧?q），（德·摩根律）即P→q??（P∧?q）33例7證明P→Q??（P∧?Q）33

例8證明P→(Q→R)?(P∧Q)→R證明P→(Q→R)

??P∨(Q→R) （蘊涵等價式）??P∨(?Q∨R) （蘊涵等價式）?(?P∨?Q)∨R （結(jié)合律）??(P∧Q)∨R （德·摩根律）?(P∧Q)→R （蘊涵等價式）34例8證明P→(Q→R)?(P∧Q)→R34例9證明P?(P∧Q)∨(P∧?Q)證明P?P∧1 (同一律)

?P∧(Q∨?Q) （排中律）

?(P∧Q)∨(P∧?Q) （分配律）35例9證明P?(P∧Q)∨(P∧?Q)35練習1.證明Q∨?((?P∨Q)∧P)?T;2.證明(P∨?P)→((Q∧?Q)∧R)?F3.證明(P→Q)∧?P??P36練習1.證明Q∨?((?P∨Q)∧P)?T;361,證明Q∨?((?P∨Q)∧P) ?Q∨?((?P∧P)∨(P∧Q)) （分配律） ?Q∨?(F∨(P∧Q)) （矛盾律） ?Q∨?(P∧Q) （同一律）?Q∨(?P∨?Q) （德·摩根律） ?(Q∨?Q)∨?P （結(jié)合律） ?T∨?P （排中律） ?T （零律）371,證明Q∨?((?P∨Q)∧P)372.證明(P∨?P)→((Q∧?Q)∧R)?T→((Q∧?Q)∧R) （排中律）?T→(F∧R) （矛盾律）?T→F （零律）??T∨F （蘊涵等值式）?F∨F?F （等冪律）382.證明(P∨?P)→((Q∧?Q)∧R)383.證明(P→Q)∧?P?(?P∨Q)∧?P （蘊涵等價值式）??P （吸收律）

393.證明(P→Q)∧?P39

1-5重言式與蘊涵式定義1－5.1

給定一命題公式，若無論對分量作什么樣的指派，其對應的真值永為T，則稱該命題公式為重言式或永真式。定義1－5.2

給定一命題公式，若無論對分量作什么樣的指派，其對應的真值永為F，則稱該命題公式為矛盾式或永假式。40 1-5重言式與蘊涵式40

定理1－5.1

任何兩個重言式的合取或析取，仍然是一個重言式。定理1－5.2

一個重言式，對同一分量，都用任何合式公式置換，其結(jié)果仍為一重言式。

證明由于重言式的真值與分量的指派無關(guān)，幫對同一分量以任何合式公式置換后，重言式的真值仍永為真。對于矛盾式也有類似于定理1－5.1和定理5－1.2的結(jié)果。41定理1－5.1任何兩個重言式的合取或析取，仍然是例1證明（（P∨S）∧R）∨?（（P∨S）∧R）為重言式。證明因為P∨?P?T，用（（P∨S）∧R）置換P得（（P∨S）∧R）∨?（（P∨S）∧R）?T42例1證明（（P∨S）∧R）∨?（（P∨S）∧R）為重言式

定理1－5.3

設(shè)A、B為兩命題公式A?B，當且僅當A?B為一個重言式。證明若A?B，則A、B有相同的真值，即有A?B永為T。若A?B為重言式，則A?B永為T，故A、B的真值相同，即A?B。4343例2證明?（P∧Q）?（?P∨?Q）證明做?（P∧Q）?（?P∨?Q）的真值表。PQP∧Q?P?Q?（P∧Q）?P∨?Q?（P∧Q）??P∨?QTTTFFFFTTFFFTTTTFTFTFTTTFFFTTTTT由以上真值表可知，?（P∧Q）??P∨?Q為重言式，根據(jù)定理1－5.3得?（P∧Q）?（?P∨?Q）44例2證明?（P∧Q）?（?P∨?Q）PQP∧Q?P?Q?定義1－5.3

當且僅當P→Q是重言式時，我們稱“P蘊涵Q”，并記作P?Q

。做P→QQ→P，?P→?Q，?Q→?p的真值表PQ?P?QP→Q

?Q→?PQ→P?P→?QTTFFTTTTTFFTFFTTFTTFTTFFFFTTTTTT由此得P→Q??Q→?P，Q→P??P→?Q，因此要P?Q，只要證明?Q??P，反之亦然。45定義1－5.3當且僅當P→Q是重言式時，我們稱“P蘊涵

要證明P?Q，即證P→Q是重言式，對于P→Q來說，除P的真值取T，Q的真值取F這樣一種指派時，P→Q的真值為F外，其余情況P→Q的真值為T，故要征P?Q，只要對條件P→Q的前件P，指定真值為T，若由此指出Q的真值為T，則P→Q為重言式，即P?Q成立；同理，如對條件命題P→Q中，假定后件Q的真值為F，若由此推出P的真值為F，即推證了?Q→?P。故P?Q成立。即

若P為T時，推出Q為T

或若Q為F時，推出P為F

則P?Q。46 要證明P?Q，即證P→Q是重言式，對于P→Q來說，除P例1推證?Q∧（P→Q）??P證法1假定?Q∧（P→Q）為T，則?Q為T，且P→Q為T。所以Q為F，P→Q為T，所以P為F，故?P為T。證法2假定?P為F，則P為T，①若Q為F，則P→Q為F，?Q∧（P→Q）為F，②若Q為T，則?Q為F，?Q∧（P→Q）為F，所以?Q∧（P→Q）??P47例1推證?Q∧（P→Q）??P47

常用的蘊涵式如下：P∧Q?PP∧Q?QP?P∨Q?P?P→QQ?P→Q?（P→Q）?P?（P→Q）??QP∧（P→Q）?Q?Q∧（P→Q）??p?P∧（P∨Q）?Q（P→Q）∧（Q→R）?P→R（P∨Q）∧（P→R）∧（Q→R）?R（P→Q）∧（R→S）?（P∧R）→（Q∧S）（P?Q）∧（Q?R）?（P?R）48常用的蘊涵式如下：48

定理1－5.4

設(shè)P、Q為任意兩個命題公式，P?Q的充分必要條件是P?Q且Q?P證明若P?Q，則P?Q為重言式。因為P?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?（P→Q）∧（Q→P）為T，即P?Q

這個定理也可以作為兩個公式等價的定義。4949蘊涵的幾個常用的性質(zhì)：（1）設(shè)A、B、C為合式公式，若A?B且A為重言式，則B也是重言式。證明因為A→B永為T，所以當A為T時，B必T。（2）若A?B，B?C，則A?C

證明由A?B，B?C得A→B，B→C為重言式所以（A→B）∧（B→C）為重言式，根據(jù)（P→Q）∧（Q→R）?P→R

所以（A→B）∧（B→C）?A→C，由性質(zhì)（1）得：A→C為重言式，即A?C50蘊涵的幾個常用的性質(zhì)：50（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，則A→（B∧C）為T，所以A?（B∧C）51（3）A?B，且A?C，那么A?（B∧C）51（4）若A?B且C?B，則A∨C?B

證明因為A→B為T，C→B為T，故（?A∨B）∧（?C∨B）為T，則（?A∧?C）∨B為T，即?（A∨C）∨B為T，即（A∨C）→B為T，所以（A∨C）?B

52（4）若A?B且C?B，則A∨C?B521－6其他聯(lián)結(jié)詞

定義1－6.3

設(shè)P、Q是兩個命題公式，復合命題P↑Q稱作P和Q的“與非”。P↑Q??（P∧Q）PQP↑QTTFTFTFTTFFT531－6其他聯(lián)結(jié)詞PQ聯(lián)結(jié)詞“↑”的幾個性質(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∨Q54聯(lián)結(jié)詞“↑”的幾個性質(zhì)：54

定義1－6.3

設(shè)P、Q是兩個命題公式，復合命題P↓Q稱作P和Q的“或非”。P↓

Q??（P∨Q）PQP↓QTTFTFFFTFFFT55定義1－6.3設(shè)P、Q是兩個命題公式，復合命題聯(lián)結(jié)詞“↓

”的幾個性質(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

當有n個命題變元時，可構(gòu)成22n種不等價的命題公式，如n＝2時，有16種不等價的命題公式。，見27頁表1－6.5。56聯(lián)結(jié)詞“↓”的幾個性質(zhì)：56最小聯(lián)結(jié)詞組：對于任何一個命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價代換。由于（1）（P?Q）?（P→Q）∧（Q→P）（2）（P→Q）??P∨Q

（3）P∧Q??（?P∨?Q）（4）P∨Q??（?P∧?q）故由“?”、“∧”、“∨”，“→”、“?”這五個聯(lián)結(jié)詞組成的命題公式，必可以由{?，∧}或{?，∨}組成的命題公式所替代。57最小聯(lián)結(jié)詞組：對于任何一個命題公式，都能由僅含這些聯(lián)結(jié)詞的命

1－7對偶與范式定義1－7.1在給定的命題公式A中，將∨換成∧，∧換成∨，若有特殊變元F和T亦相互取代，所得命題公式A*稱為A的對偶式。

A和A*互為對偶式。例1:P∧Q與P∨Q,?(P∧Q)與?(P∨Q)(P∨Q)∧R與(P∧Q)∨R?(P∧T)∨Q與?(P∨F)∧Q均為對偶式.例2：P↑Q、P↓Q的對偶式。解：P↑Q??(P∧Q)，P↑Q的對偶式為?(P∨Q)

P↓Q??（P∨Q），P↓Q的對偶式為?(P∧Q)581－7對

定理1－7.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)例:設(shè)A(P,Q,R)?P∧(?Q∨R) ①

得:A*(P,Q,R)?P∨(?Q∧R) ②(1)由①知: ?A(P,Q,R)??P∨(Q∧?R)

由②知:A*(?P,?Q,?R)??P∨(Q∧?R)

所以:?A(P,Q,R)?A*(?P,?Q,?R)類似地,有A(?P,?Q,?R)??A*(P,Q,R)59定理1－7.1設(shè)A和A*互為對偶式,P1,P2,…

定理1－7.2設(shè)P1,P2,…,Pn

是出現(xiàn)有命題公式A和B中的所有命題變元，若A?B，則A*?B*。證明：因為A?B，即A(P1,P2,…,Pn)?B(P1,P2,…,Pn)是重言式，

A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)是重言式，故A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)

由定理1－7.1得

?A*(P1,P2,…,Pn)??B*(P1,P2,…,Pn)

因此A*?B*60定理1－7.2設(shè)P1,P2,…,Pn是出現(xiàn)有命題公例4如果A(P,Q,R)是P↑（Q∧?（R↓P）），求它的對偶式A*(P,Q,R)。并求與A及A*等價，但僅包含聯(lián)結(jié)詞“?”、“∧”、“∨”的公式。解：因A(P,Q,R)是P↑（Q∧?（R↓P））故A*(P,Q,R)是P↓（Q∨?（R↑P））但P↑（Q∧?（R↓P））?P↑（Q∧（R∨P））??（P∧（Q∧（R∨P）））所以P↓（Q∨?（R↑P））??(P∨（Q∨（R∧P））)

61例4如果A(P,Q,R)是P↑（Q∧?（R↓P）），求它

定義1－7.2

一個命題公式稱為合取范式，當且僅當它具有形式A1∧A2∧…∧An（n≥1）。其中A1，A2，…，An都是命題變元或其否定所組成的析取式。例?P∨∧(P∨Q)∧(P∨?P)∧(?P∨?R)

定義1－7.3

一個命題公式稱為析取范式，當且僅當它具有形式A1∨A2∨…∨An（n≥1）。其中A1，A2，…，An都是命題變元或其否定所組成的合取式。例(P∧?Q∧?R)∨(P∧?Q)∨(P∧?Q∧R)62定義1－7.2一個命題公式稱為合取范式，當且僅當求合取范式或析取范式的步驟：（1）將公式中的聯(lián)結(jié)詞化歸成?、∧、∨。（2）將?消去或內(nèi)移。（3）利用分配律、交換律求合取范式或析取范式。（求合取范式：∨對∧；求析取范式：∧對∨）注意任何命題的析取范式和合取范式都不是唯一的。63求合取范式或析取范式的步驟：63例求下面命題公式的合取范式和析取范式。（（P∨Q）→R）→P解（1）求合取范式（（P∨Q）→R）→P?（?（P∨Q）∨R）→P??(?(P∨Q)∨R)∨P??((?P∧?Q)∨R)∨P?(?(?P∧?Q)∧?R)∨P?((??P∨??Q)∧?R)∨P?((P∨Q)∧?R)∨P?(P∨Q∨P)∧(?R∨P)?（P∨Q）∧(?R∨P)(2)求析取范式((P∨Q)∧?R)∨P?(P∧?R)∨(Q∧?R)∨P?P∨（P∧?R）∨

(Q∧?R)?P∨(Q∧?R)64例求下面命題公式的合取范式和析取范式。64練習：求下面命題公式的合取范式和析取范式。（1）求合取范式(P→Q)?

R?(?P∨Q)?

R?((?P∨Q)→R)∧(R→(?P∨Q))?(?(?P∨Q)∨R)∧(?R∨(?P∨Q))?((P∧?Q)∨R)∧(?R∨?P∨Q)?(P∨R)∧(?Q∨R)∧(?R∨?P∨Q)（2）求析取范式((P∧?Q)∨R)∧(?R∨?P∨Q)?（(P∧?Q)∧(?R∨?P∨Q)）∨(R∧(?R∨?P∨Q))?((P∧?Q)∧?R)∨((P∧?Q)∧?P)∨((P∧?Q)∧Q))∨((R∧?R)∨(R∧?P)∨(R∧Q))?(P∧?Q∧?R)∨(P∧?P∧?Q)∨(P∧?Q∧Q)∨(R∧?R)∨(?P∧R)∨(Q∧R)?(P∧?Q∧?R)∨(?P∧R)∨(Q∧R)65練習：求下面命題公式的合取范式和析取范式。65定義1－7.4n個命題變元的合取式，稱作布爾合取或小項，其中變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。

n個命題變元共有2n個小項。例兩個命題變元P和Q，其小項為：P∧Q，P∧?Q，?P∧Q，?P∧?Q66定義1－7.4n個命題變元的合取式，稱作布爾合取或小項，其3個命題變項P、Q、R可形成8個小項：m000

??P∧?Q∧?Rm001??P∧?Q∧Rm010??P∧Q∧?Rm011??P∧Q∧Rm100?P∧?Q∧?RM101?P∧?Q∧Rm110?P∧Q∧?Rm111?P∧Q∧R673個命題變項P、Q、R可形成8個小項：67小項的性質(zhì)：（1）每一個小項當其真值指派與編碼相同時，其真值為T，其余均為F。（2）任意兩個不同小項的合取永為F。（3）m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7?T68小項的性質(zhì)：68

定義1－7.3

對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的主析取范式。

定理1－7.3

在真值表中，一個公式的真值為T的指派所對小項的析取，即為此公式的主析取范式。69定義1－7.3對于給定的命題公式，如果有一個等價公例6給定P→Q，P∨Q和?（P∧Q），求這些公式的主析取范式。解：真值表如下：PQP→QP∨Q?（[P∧Q）TTTTFTFFTTFTTTTFFTFT故P→Q?（?P∧?Q）∨（?P∧Q）∨（P∧Q）

P∨Q?（?P∧Q）∨（P∧?Q）∨（P∧Q）?（P∧Q）?（?P∧?Q）∨（?P∧Q）∨（P∧Q）70例6給定P→Q，P∨Q和?（P∧Q），求這些公式的主析取范例7設(shè)一公式A的真值表如下，求公式A的主析取范式。PQRATTTTTTFFTFTFTFFTFTTFFTFFFFTFFFFT解公式A的主析取范式為：A?（?P∧?Q∧?R）∨（P∧?R∧?R）∨（P∧Q∧R）71例7設(shè)一公式A的真值表如下，求公式A的主析取范式。PQR例8求（P∧Q）∨（?P∧R）∨（Q∧R）的主析取范式。解：原式?（P∧Q∧（R∨?R））∨（?P∧R∧（Q∨?Q））∨（Q∧R∧（P∨?p））

?（P∧Q∧R）∨（P∧Q∧?R）∨（?P∧Q∧R）∨（?P∧?Q∧R）∨

（P∧Q∧R）∨（?P∧Q∧R）?（P∧Q∧R）∨（P∧Q∧?R）∨（?P∧Q∧R）∨（?P∧?Q∧R）72例8求（P∧Q）∨（?P∧R）∨（Q∧R）的主析取范式。7例9求P→（（P→Q）∧?（?Q∨?P））的主析取范式。解：原式??P∨（（?P∨Q）∧（Q∧P））??P∨（（?P∧Q∧P）∨（Q∧Q∧P））??P∨（Q∧P）??P∧（Q∨?Q）∨（P∧Q）?（?P∧Q）∨（?P∧?Q）∨（P∧Q）73例9求P→（（P→Q）∧?（?Q∨?P））的主析取范式。73求主析取范式的步驟：（1）求析取范式。（2）去掉永假的析取項。（3）去掉重復的合取項、合并相同變元。（4）對合取項補入沒出現(xiàn)的命題變元。（P∨?P）74求主析取范式的步驟：74

定義1－7.6n個命題變元的析取式，稱作布爾析取或大項，其中變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。

n個命題變元共有2n個小項。例兩個命題變元P和Q，其小項為：P∨Q，P∨?Q，?P∨Q，?P∨?Q

75定義1－7.6n個命題變元的析取式，稱作布爾析3個命題變項P、Q、R可形成8個大項：M000

?P∨Q∨RM001?P∨Q∨?RM010?P∨?Q∨RM011?P∨?Q∨?RM100??P∨Q∨RM101??P∨Q∨?RM110??P∨?Q∨RM111??P∨?Q∨?R763個命題變項P、Q、R可形成8個大項：76大項的性質(zhì)：（1）每一個大項當其真值指派與編碼相同時，其真值為F，其余均為T。（2）任意兩個不同大項的析取永為T。（3）M0∧M1∧M2∧M3∧M4∧M5∧M6∧M7?F77大項的性質(zhì)：77定義1－7.7對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等價式稱作原式的主合取范式。

定理1－7.4

在真值表中，一個公式的真值為F的指派所對大項的合取，即為此公式的主合取范式。78定義1－7.7對于給定的命題公式，如果有一個等價公式，它僅例10利用真值表求（P∧Q）∨（?P∧R）的主合取范式與主析取范式。PQRP∧Q?P∧R（P∧Q）∨（?P∧R）TTTTFTTTFTFTTFTFFFTFFFFFFTTFTTFTFFFFFFTFTTFFFFFF79例10利用真值表求（P∧Q）∨（?P∧R）的主合取范式與主合取范式：（?P∨Q∨?R）∧（?P∨Q∨R）∧（P∨?Q∨R）∧（P∨Q∨R）主析取范式：（P∧Q∧R）∨（P∧Q∧?R）∨（?P∧Q∧R）∨（?P∧?Q∧R）80主合取范式：（?P∨Q∨?R）∧（?P∨Q∨R）∧（P∨?Q求主合取范式的步驟：（1）求合取范式。（2）去掉所有為T的合取項。（3）合并相同的析取項和變元。（4）補入沒出現(xiàn)的命題變元。（即添加P∧?P）81求主合取范式的步驟：81例11求（P∧Q）∨（?P∧R）的主合取范式。解：原式?（P∧Q）∨?P）∧（（P∧Q）∨R）?（P∨?p）∧（Q∨?p）∧（P∨R）∧（Q∨R）?（Q∨?p）∧（P∨R）∧（Q∨R）?（Q∨?P∨（R∧?R））∧（P∨R∨（Q∧?Q））∧（Q∨R∨（P∧?P））?（Q∨?P∨R）∧（Q∨?P∨?R）∧（P∨R∨Q）∧（P∨R∨?Q）∧（Q∨R∨P）∧（Q∨R∨?P）?（?P∨Q∨R）∧（?P∨Q∨?R）∧（P∨?Q∨R）∧（P∨Q∨R）82例11求（P∧Q）∨（?P∧R）的主合取范式。82用∑表示小項的析取用∏表示大項的合取例如（P∧Q）∨（?P∧R）?（?P∨Q∨R）∧（?P∨Q∨?R）∧（P∨?Q∨R）∧（P∨Q∨R）?M000∧M010∧M100∧M101

?∏0,2,4,5?m001∨m011∨m110∨m111

?∑1,3,6,783用∑表示小項的析取83

1-8推理理論 推理是從前提推出結(jié)論的思維過程,前提是指已知的命題公式,結(jié)論是從前提出發(fā)應用推理規(guī)則推出來的命題公式。前提可以是多個。定義1－8.1設(shè)H1，H2，…，Hn

，C是命題公式，若（H1∧H2∧…∧Hn）→C為重言式,則稱C是一組前提H1,H2,…,Hn的有效結(jié)論。記作：

H1∧H2∧…∧Hn?

C

真值表法推理方法直接證法間接證法841-8推理理論84（1）真值表法若H1，H2，…，Hn都為T的行，C也為真；或若C為假的行，H1，H2，…，Hn

中至少有一個為假則H1∧H2∧…∧Hn?C成立。85（1）真值表法85例1一份統(tǒng)計表格的錯誤或者是由于材料不可靠，或者是由于計算有錯誤；這份統(tǒng)計表格的錯誤不是由于材料不可靠，所以這份統(tǒng)計表格是由于計算有錯誤。解：設(shè)P：統(tǒng)計表格的錯誤是由于材料不可靠。

Q：統(tǒng)計表格的錯誤是由于計算不可靠。前提是：P∨Q，?P，結(jié)論是：Q，即證明（P∨Q）∧?P?QPQP∨Q?PTTTFTFTFFTTTFFFT故（P∨Q）∧?P?Q86例1一份統(tǒng)計表格的錯誤或者是由于材料不可靠，或者是由于計算

例2如果張老師來了，這個問題可以得到解答，如果李老師來了，這個問題也可以得到解答，總之張老師或李老師來了，這個問題就可以得到解答。解：設(shè)P：張老師來了。

Q：李老師來了。

R：這個問題可以得到解答。本題可譯為：（P→R）∧（Q→R）∧（P∨Q）?R87例2如果張老師來了，這個問題可以得到解答，如果李老師來了PQRP→RQ→RP∨QTTTTTTTTFFFTTFTTTTTFFFTTFTTTTTFTFTFTFFTTTFFFFTTF88PQRP→RQ→RP∨QTTTTTTTTFFFTTFTTTT（2）直接證法

就是由一組前提，利用一些公認的推理規(guī)則，根據(jù)已知的等價公式或蘊涵公式，推出有效結(jié)論。

P規(guī)則：前提在推導過程中隨時可以引用。

T規(guī)則：已經(jīng)推出的公式在以后的推導過程中可隨時引用。常用蘊涵式見43頁表1－8.389（2）直接證法89例1證明（P∨Q）∧（P→R）∧（Q→S）?S∨R

證法1（1）P∨QP

（2）?P→QT（1）E

（3）Q→SP

（4）?P→ST（2），（3）I

（5）?S→PT（4）E

（6）P→RP

（7）?S→RT（5），（6）I

（8）S∨RT（7）E

90例1證明（P∨Q）∧（P→R）∧（Q→S）?S∨R90證法2（1）P→RP

（2）P∨Q→R∨QT（1）I

（3）Q→SP

（4）Q∨R→S∨RT（3）I

（5）P∨Q→S∨RT（2），（4）I

（6）P∨QP

（7）S∨RT（5），（6）I91證法2（1）P→R例2證明（W∨R）→V，V→C∨S，S→U，?C∧?U??W證明（1）?C∧?UP

（2）?UT（1）I

（3）S→UP

（4）?ST（2）,（3）I(5)?CT（1）I(6)?C∧?ST(4),(5)I(7)?(C∨S)T(6)E(8)（W∨R）→VP(9)V→(C∨S)P(10)（W∨R）→(C∨S)T(8),(9)I(11)?(（W∨R）T(7),(10)I(12)?W∧?RT(11)E(13)?WT(12)E92例2證明（W∨R）→V，V→C∨S，S→U，?C∧?U(3)間接證法1(歸謬法)

要證H1∧H2∧…∧Hn?C

即要證H1∧H2∧…∧Hn→C為重言式

H1∧H2∧…∧Hn→C

??(H1∧H2∧…∧Hn)∨C??(H1∧H2∧…∧Hn∧?C)因此只要證H1∧H2∧…∧Hn∧?C為矛盾式.

93(3)間接證法1(歸謬法)93例3證明A→B,?(B∨C)可邏輯推出?A證明(1)A→BP(2)AP(附加前提)(3)?(B∨C)P(4)?B∧?CT(3)E(5)BT(1),(2)I(6)?BT(4)I(7)B∧?B(矛盾)T(5),(6)I94例3證明A→B,?(B∨C)可邏輯推出?A94例4證明(P∨Q)∧(P→R)∧(Q→S)?S∨R證明(1)?(S∨R)P(2)?S∧?RT(1)E(3)P∨QP(4)?P→QT(3)E(5)Q→SP(6)?P→ST(4),(5)I(7)?S→PT(6)(8)(?S∧?R)→(P∧?R)T(7)I(9)P∧?RT(2),(8)I(10)P→RP(11)?P∨RT(10)E(12)?(P∧?R)T(11)E(13)(P∧?R)∧?(P∧?R)(矛盾)T(9),(12)I95例4證明(P∨Q)∧(P→R)∧(Q→S)?S∨R(4)間接證法2(附加前提法)要證H1∧H2∧…∧Hn?R→C只要證(H1∧H2∧…∧Hn)→(R→C)為重言式

(H1∧H2∧…∧Hn)→(R→C)??(H1∧H2∧…∧Hn)∨(?R∨C)??(H1∧H2∧…∧Hn∧R)∨C?(H1∧H2∧…∧Hn∧R)→C只要證(H1∧H2∧…∧Hn∧R)?C由(S∧R)?C證得S?(R→C)稱為CP規(guī)則。96(4)間接證法2(附加前提法)96例5證明A→(B→C),?D∨A,B重言蘊涵D→C證明(1)DP(附加前提) (2)?D∨AP(3)AT(1),(2)I(4)A→(B→C)P(5)B→CT(3),(4)I(6)BP(7)CT(5),(6)I(8)D→CCP97例5證明A→(B→C),?D∨A,B重言蘊涵D例6設(shè)有下列情況,結(jié)論是否有效?(a)或者是天晴,或者是下雨。(b)如果是天晴，我去看電影。(c)如果我去看電影，我就不看書。結(jié)論：如果我在看書則天在下雨。解若設(shè)M：天晴。Q：下雨。

S：我看電影。R：我看書。即證：M?Q，M→S，S→?R，推出R→Q其中M?Q??(M?Q）98例6設(shè)有下列情況,結(jié)論是否有效?98

(1)RP（附加前提）

(2)S→?RP(3)R→?ST(2)E(4)?ST(1),(3)I(5)M→SP(6)?MT(4),(5)I(7)?(M?Q）P(8)M??QT(7)E(9)(M→?Q)∧(?Q→M)T(8)E(10)?Q→MT(9)I(11)?M→QT(10)E(12)QT(6),(11)I(13)R→QCP

99(1)R

第二章謂詞邏輯

原子命題是命題邏輯研究的基本單位,沒有對原子的內(nèi)部結(jié)構(gòu)及其相互之間的邏輯關(guān)系進行分析,這樣就無法處理一些簡單而又常見的推理問題。例如:所有的人都是要死的，蘇格拉底是人，所以,蘇格拉底是要死的。P:所有的人是要死的.Q:蘇格拉底是人.R:所以,蘇格拉底是要死的P∧Q→R

不是重言式。

100 第二章謂詞邏輯100

2－1謂詞的概念與表示原子命題由主語和謂語兩部分組成。主語一般是客體?？腕w：可以是一個具體的事物，也可以是一種抽象事物。是命題所研究的對象。謂詞：用以刻劃客體的性質(zhì)或客體之間的性質(zhì)。例李明是一個學生。李明比王杰高。哥白尼指出地球繞著太陽轉(zhuǎn)。1012－1謂詞的概念與表示101謂詞用大寫字母表示?？腕w名稱用小寫字母表示?？腕w常元：表示具體或特定的客體的詞。一般用小寫字母a,b,c,……表示?？腕w變元：表示抽象的或泛指的客體的詞。一般用小寫字母x,y,z,……表示。例如：A表示“是個大學生”，

c表示張三，

e表示李四，則A（c）表示“張三是個大學生”，

A（e）表示“李四是個大學生”，102謂詞用大寫字母表示。102“b是A”類型的命題可用A（b）表示。兩個客體之間關(guān)系的命題可表示為B（a,b）。

A（b）為一元謂詞。

B（a,b）為二元謂詞。依此類推。單獨一個謂詞不是命題，只有將變元x,y,z等取特定客體時，才確定了一個命題。103“b是A”類型的命題可用A（b）表示。103

2－2命題函數(shù)與量詞

定義2－2.1

由一個謂詞，一些客體變元組成的表達式稱為簡單命題函數(shù)。例B（x,y）。

n元謂詞就是有n個客體變元的命題函數(shù)。當n＝0時，它本身就是一個命題。

1042－2命題函數(shù)與量詞104由一個或幾個簡單命題函數(shù)以及聯(lián)結(jié)詞組合而成的表達式稱為復合命題函數(shù)。例1（1）2是素數(shù)且是偶數(shù)。解：設(shè)A（x）：x是素數(shù)；

B（x）：x是偶數(shù)；

a：2

則命題表示為：A（a）∧B（a）

（2）如果2大于3，則2大于4。解：設(shè)L（x,y）：x大于y；

a：2；b：3；c：4

則命題表示為：L（a,b）→L（a,c）。105由一個或幾個簡單命題函數(shù)以及聯(lián)結(jié)詞組合而成的表達式稱為復合命（3）如果張明比李民高，李民比趙亮高，則張明比趙亮高。解：設(shè)H（x,y）：x比y高；

a：張明；b：李民；c：趙亮。則命題符號化為：

H（a,b）∧H（b，c）→H（a,c）。命題函數(shù)不是命題，只有客體變元取特定客體名稱時，才能成為命題。106（3）如果張明比李民高，李民比趙亮高，則張明比趙亮高。106

個體域：客體變元的取值范圍。個體域可以是有限的，也可以是無限的。例學生、工人，實數(shù)，{a,b，c}。

全總個體域：宇宙間的一切事物。107個體域：客體變元的取值范圍。107量詞：表示數(shù)量的詞。全稱量詞“?”用來表達“對所有的”、“每一個”，“對任何一個”。例2（1）所有的人都是要呼吸的。解：設(shè)M（x）：X是人；H（x）：x要呼吸。則符號化為：（?x）（M（x）→

H（x））域為全總域。108量詞：表示數(shù)量的詞。108（2）每個學生都要參加考試。解：設(shè)P（x）：x是學生；Q（x）：x要參加考試。符號化為:

（?x）（P（x）→