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

離散數(shù)學(xué)_命題邏輯第一頁，共八十一頁，2022年，8月28日第一章

命題邏輯

數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律。因此,數(shù)理邏輯又稱為符號邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系,并給出推理規(guī)則,進(jìn)行命題演繹。主要內(nèi)容如下：命題和命題聯(lián)結(jié)詞命題公式與翻譯命題公式的等值關(guān)系和蘊(yùn)含關(guān)系對偶與范式命題演算的推理理論第二頁，共八十一頁，2022年，8月28日命題和命題聯(lián)結(jié)詞

一、

命題的概念

命題：是能分辨真假的陳述句。

例1

判斷下列語句是否是命題。（1）空氣是人生存所必需的。（2）請把門關(guān)上。（3）南京是中國的首都。（4）你吃飯了嗎？（5）x=3。（6）啊，真美呀！(7)明年春節(jié)是個(gè)大晴天。

解語句（1）,（3）,（5），(7)是陳述句

（1）、（3）、(7)是命題

用真值來描述命題是“真”還是“假”。分別用“1”和“0”表示

命題用大寫的拉丁字母A、B、C、……P、Q、……或者帶下標(biāo)的大寫的字母來表示。

例2

判斷下列陳述句是否是命題。

P：地球外的星球上也有人；Q：小王是我的好朋友；

解

P、Q是命題

第三頁，共八十一頁，2022年，8月28日二、命題聯(lián)結(jié)詞

原子命題：由簡單句形成的命題。

復(fù)合命題：由一個(gè)或幾個(gè)原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。

例3

A：李明既是三好學(xué)生又是足球隊(duì)員。

B：張平或者正在釣魚或者正在睡覺。

C：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會。第四頁，共八十一頁，2022年，8月28日定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。

1.否定“?”

定義1-1

設(shè)P是一個(gè)命題，利用“?”和P組成的復(fù)合命題稱為P的否命題，記作“?P”(讀作“非P”)。命題P取值為真時(shí)，命題?P取值為假；命題P取值為假時(shí)，命題?P取值為真。

例4

設(shè)P：上海是一個(gè)城市；Q：每個(gè)自然數(shù)都是偶數(shù)。則有?P：上海不是一個(gè)城市;?Q：并非每個(gè)自然數(shù)都是偶數(shù)。

P

?P

1001第五頁，共八十一頁，2022年，8月28日

2．合取“∧”

定義1-2

設(shè)P和Q是兩個(gè)命題，由P、Q利用“∧”組成的復(fù)合命題，稱為合取式復(fù)合命題，記作“P∧Q”（讀作“P且Q”）。

當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，P∧Q才取值為真。

例5

設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?/p>

PQP∧Q000010100111第六頁，共八十一頁，2022年，8月28日3.析取“∨”

定義1-3

由命題P和Q利用“∨”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí)，P∨Q取值為真。

PQP∨Q000011101111例6

將命題“他可能是100米或400米賽跑的冠軍。”符號化。

解令P：他可能是100米賽跑冠軍；

Q：他可能是400米賽跑冠軍。

則命題可表示為P∨Q。第七頁，共八十一頁，2022年，8月28日設(shè)P、Q是兩個(gè)命題，P異或Q是一個(gè)復(fù)合命題，記作P∨Q。

例7今天晚上我在家看電視或去劇場看戲。令P：今天晚上我在家看電視。

Q：今天晚上我去劇場看戲例7中的命題可表示為P∨Q，或者表示為（P∧?Q∨(?P∧Q)。由于“∨”可用“∨”，“∧”和“?”表示，故我們不把它當(dāng)作基本聯(lián)結(jié)詞。

PQP∨Q000011101110第八頁，共八十一頁，2022年，8月28日

4.蘊(yùn)含“→”

定義1-4

由命題P和Q利用“→”組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。

當(dāng)P為真，Q為假時(shí)，P→Q為假，否則P→Q為真。

PQP→Q001011100111

例8

將命題“如果我得到這本小說，那么我今夜就讀完它?！狈柣?。

解令P：我得到這本小說；Q：我今夜就讀完它。于是上述命題可表示為P→Q。

例9

若P：雪是黑色的；Q：太陽從西邊升起；R：太陽從東邊升起。則P→Q和P→R所表示的命題都是真的.

第九頁，共八十一頁，2022年，8月28日5．等值“?”

定義1-5

由命題P和Q，利用“?”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“P?Q”（讀作“P當(dāng)且僅當(dāng)Q”）。

當(dāng)P和Q的真值相同時(shí),P?Q取真,否則取假。

PQPQ001010100111

例10

非本倉庫工作人員，一律不得入內(nèi)。

解令P：某人是倉庫工作人員；

Q：某人可以進(jìn)入倉庫。

則上述命題可表示為P?Q。第十頁，共八十一頁，2022年，8月28日

例11

黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù)令P：黃山比喜馬拉雅山高；Q：3是素?cái)?shù)本例可符號化為PQ

從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié)詞的定義來看，因?yàn)镻的真值為假，Q的真值為真，所以PQ的真值為假。

對于上述五種聯(lián)結(jié)詞，應(yīng)注意到：

復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無關(guān)。第十一頁，共八十一頁，2022年，8月28日

三、命題符號化利用聯(lián)結(jié)詞可以把許多日常語句符號化。基本步驟如下：

（1）從語句中分析出各原子命題，將它們符號化；

（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。

例12

用符號形式表示下列命題。（1）如果明天早上下雨或下雪，那么我不去學(xué)校（2）如果明天早上不下雨且不下雪，那么我去學(xué)校。（3）如果明天早上不是雨夾雪，那么我去學(xué)校。（4）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。

解令P：明天早上下雨；

Q：明天早上下雪；

R：我去學(xué)校。

（2）（?P

∧?Q）→R；

（1）（P∨Q）→

?R；（4）R→（?P

∧?Q）

（3）?(P∧Q）→R；第十二頁，共八十一頁，2022年，8月28日例13將下列命題符號化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；（5）假如上午不下雨，我去看電影，否則就在家里看書。解（1）令P：派小王出差；Q：派小李出差。命題符號化為P∨Q。

（2）令P：我們劃船；Q：我們跑步。則命題可表示為?(P∧Q）。

（3）

令P：你來了；Q：他唱歌；R：你伴奏。則命題可表示為P→（Q?R）

（4）

令P：李明是體育愛好者；Q：李明是文藝愛好者。則命題可表示為（P∧?Q）→?（P∧Q）

（5）

令P：上午下雨；Q：我去看電影；R：我在家讀書。則命題可表示為（?P→Q）∧（P→R）。

第十三頁，共八十一頁，2022年，8月28日練習(xí)1-11.

判斷下列語句哪些是命題，若是命題，則指出其真值。（1）只有小孩才愛哭。（2）X+6=Y

（3）銀是白的。（4）起來吧，我的朋友。(是假)

(不是)(是真)

(不是)

2．將下列命題符號化（1）我看見的既不是小張也不是老李。

解

令P：我看見的是小張；Q：我看見的是老李。

則該命題可表示為?P∧?Q

（2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。

解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；

R：他看電視；S：他聽音樂。則該命題可表示為（P∧?Q）→（R∨S）第十四頁，共八十一頁，2022年，8月28日命題公式

一、

命題公式的概念

1.命題常元

一個(gè)表示確定命題的大寫字母或T和F。

2．命題變元一個(gè)沒有指定具體內(nèi)容的命題符號。

一個(gè)命題變元當(dāng)沒有對其賦予內(nèi)容時(shí)，它的真值不能確定，一旦用一個(gè)具體的命題代入，它的真值就確定了。第十五頁，共八十一頁，2022年，8月28日3.命題公式

命題公式(或簡稱公式)是由0(F)、1(T)和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。

定義1-6

(命題公式的遞歸定義。)

①

0(F)，1(T)是命題公式；

②命題變元是命題公式；

③如果A是命題公式，則?A是命題公式；

④如果A和B是命題公式，則(A∨B),

(A∧B),(A→B),(A?B)也是命題公式；有限次地利用上述①—④而產(chǎn)生的符號串是命題公式。例1

下列符號串是否為命題公式。

①

P→(Q∧PR)；

②

(P∨Q)→(?(Q∧R))

解

①不是命題公式。②是命題公式。

第十六頁，共八十一頁，2022年，8月28日二、真值指派

命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變元都用一個(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。

定義1—7

設(shè)F為含有命題變元P1，P2，…,Pn的命題公式，對P1，P2，…,Pn分別指定一個(gè)真值,稱為對公式F的一組真值指派。

公式與其命題變元之間的真值關(guān)系，可以用真值表的方法表示出來。第十七頁，共八十一頁，2022年，8月28日

例2

給出公式F=(（P∨Q）（Q∧R）)(P∧?R）的真值表。

解

公式F的真值表如下：PQR?RP∨QQ∧R(P∨Q)→(Q∧R)P∧?RF000001010011100101110111101010100011111100010001110100010000101000101110第十八頁，共八十一頁，2022年，8月28日

三、公式類型

定義1-8

如果對于命題公式F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式(或永真公式)，常用“1”(T)表示。相反地，若對于F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式(或永假公式)，常用“0”(F)表示。如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式。

例3

構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式

①(?P?Q)??(P?Q)；

②(Q→P)∧(?P∧Q)；③((P∨Q)→(Q∧R))→(P∧?R)。

第十九頁，共八十一頁，2022年，8月28日

解令F1=(?P?Q)??(P?Q)，F(xiàn)2=(Q→P)∧(?P∧Q)

F1和F2的真值表如下：PQ?P?P?QP?Q?(P→Q)F1Q→P?P∧QF20010101100011101101010010111001100101100由上可知：F1是重言式

,F2是矛盾式。

(3)的真值表自己做一下，它是可滿足公式。第二十頁，共八十一頁，2022年，8月28日命題公式的等值關(guān)系和蘊(yùn)含關(guān)系一、命題公式的等值關(guān)系

定義1-9

設(shè)A和B是兩個(gè)命題公式,P1,P2,…,Pn

是所有出現(xiàn)于A和B中的命題變元，如果對于P1,P2,…,Pn

的任一組真值指派，A和B的真值都相同,則稱公式A和B等值，記為AB,稱AB為等值式。注意：（1）符號“”與“?”的區(qū)別與聯(lián)系。

“”不是聯(lián)結(jié)詞，AB不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。

“?”是聯(lián)結(jié)詞，A?B是一個(gè)公式。

AB當(dāng)且僅當(dāng)A?B是永真公式。第二十一頁，共八十一頁，2022年，8月28日

（2）

可以驗(yàn)證等值關(guān)系是等價(jià)關(guān)系。即自反性：對任意公式A，有AA。

對稱性：對任意公式A，B，若AB，則BA。

可傳遞性：對任意公式A、B、C，若AB，BC，則AC。

（3）當(dāng)A是重言式時(shí)，A1；當(dāng)A是矛盾式時(shí)，則A0。第二十二頁，共八十一頁，2022年，8月28日二、基本的等值式設(shè)P、Q、R是命題變元，下表中列出了24個(gè)最基本的等值式:編號

公式E1E1ノE2E2ノE3E3ノE4E4ノE5E5ノE6E6ノE7E7ノ

P∨QQ∨P交換律

P∧QQ∧P

交換律

(P∨Q)∨RP∨(Q∨R)結(jié)合律

(P∧Q)∧RP∧(Q∧R)

結(jié)合律

P∧(Q∨R)(P∧Q)∨(P∧R)分配律

P∨(Q∧R)(P∨Q)∧(P∨R)分配律

P∨0P

同一律

P∧1P

同一律

P∨P1

互否律

P∧P0

互否律

（P）P

雙重否定律

P∨PP

等冪律

P∧PP

等冪律

第二十三頁，共八十一頁，2022年，8月28日編號

公式E8E8ノE9E9ノE10E10ノE11E12E13E14E15P∨11

零一律

P∧00

零一律P∨（P∧Q）P

吸收律P∧（P∨Q）P

吸收律（P∨Q）P∧Q

德.摩根定律（P∧Q）P∨Q

德.摩根定律PQP∨QP?Q(P∧Q)∨(P∧Q)P(QR)(P∧Q)RP?Q(PQ)∧(QP)

PQQP第二十四頁，共八十一頁，2022年，8月28日三、等值式的判別有兩種方法：真值表方法，命題演算方法

1、真值表方法例1

用真值表方法證明E10：

(PQ)PQ

解令：A=(PQ)，B=PQ，構(gòu)造A，B

以及AB的真值表如下：

PQPQ(PQ)PQPQAB000111110110100111100101由于公式AB所標(biāo)記的列全為1，因此AB。

10100001第二十五頁，共八十一頁，2022年，8月28日例2

用真值表方法證明E11：PQPQ解令A(yù)=PQ，B=PQ

構(gòu)造A，B以及AB的真值表如下：PQPPQPQAB001111011111100001由于公式AB所標(biāo)記的列全為1，因此AB.110111第二十六頁，共八十一頁，2022年，8月28日

例3

用真值表方法判斷PQPQ是否成立.

解令A(yù)=PQ，B=PQ

構(gòu)造A，B以及AB的真值表PQPQPQPQAB0011111011001001100

由于公式AB所標(biāo)記的列不全為1，AB不是永真公式，因此AB不成立。101100111第二十七頁，共八十一頁，2022年，8月28日

(1)代入規(guī)則代入規(guī)則對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。2．等值演算方法例如F=(PQ)?(QP)是重言式，若用公式A∧B代換命題變元P得公式

F1=((A∧B)Q)?(Q(A∧B))，F(xiàn)1仍是重言式。注意：因?yàn)锳B當(dāng)且僅當(dāng)A?B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。第二十八頁，共八十一頁，2022年，8月28日(2)置換規(guī)則

定義1-10

設(shè)C是命題公式A的一部分(即C是公式A中連續(xù)的幾個(gè)符號)，且C本身也是一個(gè)命題公式，則稱C為公式A的子公式。

例如設(shè)公式A=(P∨Q)((PQ)∨(R∧S))。

則P∨Q，PQ，(PQ)∨(R∧S)等均是A的子公式，

但P∨，P和Q等均不是A的子公式，

置換規(guī)則設(shè)C是公式A的子公式，CD。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則AB。

第二十九頁，共八十一頁，2022年，8月28日(3)

等值演算等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。

由代入規(guī)則知前述的基本等值式，不僅對任意的命題變元P，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時(shí)，這些等值式也成立例2

證明命題公式的等值關(guān)系：

(PQ)∧(RQ)(P∨R)Q；證明(PQ)∧(RQ)

(P∨Q)∧(R∨Q)E11

(P∧R)∨QE3ˊ(分配律)

(P∨R)∨QE10(德.摩根定律)

(P∨R)QE11

所以(PQ)∧(RQ)(P∨R)Q第三十頁，共八十一頁，2022年，8月28日例3

證明下列命題公式的等值關(guān)系

(PQ)(P(PQ))

PQ證明

(PQ)(P(PQ))

(PQ)((P

P)Q) E2(結(jié)合律)

(PQ)(PQ)E7(等冪律)

(PQ)(PQ)E1(交換律)

P(Q(PQ))E2(結(jié)合律)

PQE1，E9(交換律，吸收律)第三十一頁，共八十一頁，2022年，8月28日例4

判別下列公式的類型。（1）Q∧(P(P∧Q))

（2）(PQ)∧P解（1）Q∧(P(P∧Q))

Q∧(P∨(P∧Q))E11,E6

Q∧((P∨P)∧(P∨Q))E3ノ

Q∧(1∧(P∨Q))E5

Q∧(P∨Q)

E4ノ

Q∧P∧QE10

(Q∧Q)∧PE1ノ,E2

0E5ノ,E8ノ所以Q∧(P(P∧Q))是矛盾式。（2）(PQ)∧P

(P∨Q)∧P

E11

P

E9ノ于是該公式是可滿足式。

第三十二頁，共八十一頁，2022年，8月28日三、命題公式的蘊(yùn)含關(guān)系

定義1-11

設(shè)A，B是兩個(gè)公式，若公式AB是重言式，即AB1，則稱公式A蘊(yùn)含公式B，記作AB。稱“AB”為蘊(yùn)含式。

注意：符號“”和“”的區(qū)別和聯(lián)系與符號“”與“?”的區(qū)別和聯(lián)系類似。

“”不是聯(lián)結(jié)詞，

“AB”不是公式，它表示公式A與B之間存在蘊(yùn)含關(guān)系。

“”是聯(lián)系詞，AB是一個(gè)公式。

AB當(dāng)且僅當(dāng)AB是永真公式。第三十三頁，共八十一頁，2022年，8月28日

AB是偏序關(guān)系即自反性：AA。

反對稱：若AB，BA，則AB。

傳遞性：若AB，BC，則AC。

反對稱性的證明：

設(shè)AB且BA，

由定義7-11AB1且BA1于是AB(AB)(BA) E14

11

1因此AB第三十四頁，共八十一頁，2022年，8月28日傳遞性的證明：設(shè)AB，BC，則AB1，BC1

(ABC)(ABC)

((AB)C)(A(BC))

(1C)(A1)

11

1

因此AC.于是ACAC

(AC)(BB)第三十五頁，共八十一頁，2022年，8月28日

四、基本的蘊(yùn)含式

編號蘊(yùn)含式I1PQPI2PQQI3PPQI4QPQI5PPQI6QPQI7(PQ)PI8(PQ)

Q設(shè)P、Q、R是命題變元，下表中列出了16個(gè)最基本的蘊(yùn)含式。第三十六頁，共八十一頁，2022年，8月28日編號蘊(yùn)含式I9PQPQ

或表示為：P、QPQI10P(PQ)QP、(PQ)QI11P(PQ)QP、PQQI12Q(PQ)PQ、PQPI13(PQ)(QR)PRPQ、QRPRI14(PQ)(PR)(QR)RPQ、PR、QRRI15PQ(PR)(QR)I16PQ(PR)(QR)第三十七頁，共八十一頁，2022年，8月28日五、蘊(yùn)含式的判別判定“AB”是否成立的問題可轉(zhuǎn)化為判定AB是否為重言式，有下述判定方法：

（1）真值表；（2）等值演算；（3）假定前件A為真；（4）假定后件B為假。

1.真值表方法例4

證明I14：((P∨Q)∧(PR)∧(QR))

R

證明令公式

F=((P∨Q)∧(PR)∧(QR))R，其真值表如下：第三十八頁，共八十一頁，2022年，8月28日

公式F對任意的一組真值指派取值均為1，故F是重言式。PQRP∨QP→RQ→R(P∨Q)∧(P→R）∧（Q→R）F0000010100111001011101110011111111110101110111010001010111111111第三十九頁，共八十一頁，2022年，8月28日

2.

等值演算方法

例5

證明I11：P∧（PQ）Q證明

(P∧(PQ))Q

(P∧(P∨Q))∨Q

E11

(P∨(P∨Q))∨Q

E10ノ

(P∨Q)∨(P∨Q)

E2

1代入規(guī)則,E5

因此P∧（PQ）Q第四十頁，共八十一頁，2022年，8月28日

3.

假定前件A真假定前件A為真，檢查在此情況下，其后件B是否也為真。

ABAB001011100111

例6

證明I12:

Q∧（PQ）P

證明令前件Q∧（PQ）為真，則Q為真,且PQ為真。于是Q為假，因而P也為假。由此P為真。故蘊(yùn)含式I12

成立。第四十一頁，共八十一頁，2022年，8月28日

4、假定后件B假假定后件B為假，檢查在此情況下，其前件A是否也為假.

例7

證明蘊(yùn)含式(PQ)(RS)(PR)(QS)

證明令后件(PR)(QS)為假，則PR為真，QS為假,于是P、R均為真，而Q和S至少一個(gè)為假。由此可知PQ與RS中至少一個(gè)為假,

因此(PQ)(RS)為假.故上述蘊(yùn)含式成立。第四十二頁，共八十一頁，2022年，8月28日練習(xí)1-3

1．判斷下列等值式是否成立

（1）(PQ)∧(RQ)(P∨R)Q

（2）(PQ)(P∧Q)∨(P∧Q)解

（1）(PQ)∧(RQ)(P∨Q)∧(R∨Q)

E11(P∧R)∨QE3ノ

(P∨R)∨QE10（2）(P∧Q)∨(P∧Q)((P∨Q)∧(Q∨P))E6，E10ノ((PQ)∧(QP))E11

(PQ)

E14(P∨R)QE11第四十三頁，共八十一頁，2022年，8月28日2．判定蘊(yùn)含式P(QR)(PQ)(PR)是否成立

解假定后件(PQ)(PR)為假，則PQ為真，PR為假。由PR為假,得P為真，R為假。

又PQ為真，故得Q為真。于是P為真，QR為假。從而P(QR)為假。因此蘊(yùn)含式成立。第四十四頁，共八十一頁，2022年，8月28日范式一、析取范式和合取范式

定義1-12

一個(gè)命題公式若它具有P1*∧P2*∧…∧Pn*的形式（n≥1），其中Pi*是命題變元Pi或其否定?Pi，則稱其為質(zhì)合取式(基本積)。

例如,?P∧Q∧R∧S是由命題變元P、Q、R、S組成的一質(zhì)合取式(基本積)。

定義1-13

一個(gè)命題公式若具有P1*∨P2*∨…∨Pn*（n≥1）的形式，其中P*i是命題變元Pi或是其否定?Pi，則稱其為質(zhì)析取式(基本和)。

例如,?

Q∨P∨?R是由命題變元P、Q、R組成的一質(zhì)析取式(基本和)。第四十五頁，共八十一頁，2022年，8月28日

定理1-4(1)一質(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個(gè)命題變元P及其否定?P。

(2)一質(zhì)析取式為永真式的充分必要條件是，它同時(shí)包含某個(gè)命題變元P及其否定?P。

證明（2）必要性：假設(shè)A=P1*∨P2*∨…∨Pn*為一質(zhì)析取式，且A為一永真式。

(反證法)假設(shè)A式中不同時(shí)包含任一命題變元及其否定，則在A中，當(dāng)Pi*為Pi時(shí)指派Pi取0，當(dāng)Pi*為?Pi時(shí)，指派Pi取1。(i=1,2,…n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。例如A=P1∨?P2∨P3.則(P1,P2,P3)=(0,1,0)的指派，使A的真值為0.

充分性：設(shè)A含命題變元Pi和?Pi，而Pi∨?Pi是永真式，由結(jié)合律和零一律，A的真值必為1，故A也是永真式。第四十六頁，共八十一頁，2022年，8月28日

定義1-14質(zhì)合取式的析取稱為析取范式。即具有A1∨A2∨…∨An(n≥1)的形式的公式，其中Ai是質(zhì)合取式。

例如，F(xiàn)1=P∨(P∧Q)∨R∨(P∧Q∧R)是一析取范式。

定義1-15

質(zhì)析取式的合取稱為合取范式。即具有A1∧A2∧…∧An(n≥1)的形式的公式，其中Ai是質(zhì)析取式。

例如，F(xiàn)2=P∧(P∨Q)∧R∧(P∨Q∨R)是一合取范式。

F3=(P∨R∨Q)∧(P∨Q)∧R∧(P∨R)也是一合取范式。第四十七頁，共八十一頁，2022年，8月28日二、求公式的析取范式和合取范式

任何一個(gè)命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進(jìn)行：（1）利用E11，E12和E14消去公式中的運(yùn)算符“”和“”；

(2)利用德?摩根定律將否定符號“”向內(nèi)深入，使之只作用于命題變元；（3）利用雙重否定律E6將

(P)置換成P；（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。第四十八頁，共八十一頁，2022年，8月28日例1

求F1=(P∧(QR))S的合取范式和析取范式

解

F1

(P∧(Q∨R))∨SE11

P∨(Q∨R)∨SE10ノ

P∨(Q∧R)∨S(析取范式)E10,E6又F1P∨(Q∧R)∨S

(P∨S)∨(Q∧R)E1,E2

(P∨S∨Q)∧(P∨S∨R)（合取范式）E3ノ另外由F1

(P∨S∨Q)∧(P∨S∨R)(P∧(P∨S∨R))∨(S∧(P∨S∨R))∨

(Q∧(P∨S∨R))E3P∨S∨(Q∧P)∨(Q∧S)∨(Q∧R)（析取范式）E9,E13第四十九頁，共八十一頁，2022年，8月28日

例2

求F2=(P∨Q)(P∧Q)的析取范式、合取范式。

解

F2

((P∨Q)(P∧Q))∧((P∧Q)(P∨Q))E14

((P∨Q)∨(P∧Q))∧((P∧Q)∨(P∨Q))E11,E6

(P∨(Q∨(P∧Q)))∧(P∨Q∨(P∧Q))E2,E10ノ,E10

(P∨Q)∧(P∨Q)（合取范式）E2,E9(P∧(P∨Q))∨(Q∧(P∨Q))E3(P∧P)∨(P∧Q)∨(P∧Q)∨(Q∧Q)（析取范式）E3第五十頁，共八十一頁，2022年，8月28日

定理1-5（1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項(xiàng)。

三、利用范式判定公式類型

證明（2）必要性（用反證法）：假設(shè)A＝A1∨A2∨…∨An中某個(gè)Ai不包含一對互為否定的合取項(xiàng)，（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(xiàng)。則由定理7-4知，Ai不是矛盾式。于是存在一組真值指派使Ai取值為真。對同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。

充分性：假設(shè)任一Ai(1≤i≤n)中含有形如P∧P合取式，其中P為命題變元。于是由定理7-4知，每一Ai(1≤i≤n)都為矛盾式，因此A1∨A2∨…∨An必為矛盾式，即A為矛盾式。因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(xiàng)。第五十一頁，共八十一頁，2022年，8月28日

例3

判別公式A=P(P∧(QP))是否為重言式或矛盾式。

解

AP∨(P∧(Q∨P))E11

P∨(P∧Q)∨(P∧P)(析取范式)E3根據(jù)定理7-5，A不是矛盾式。又AP∨(P∧(Q∨P))（P∨P）∧（P∨Q∨P)（合取范式）E3ノ由定理1-5知，A是重言式。第五十二頁，共八十一頁，2022年，8月28日

例4

利用范式判斷公式P(PQ)的類型。

解

P(PQ)

(P(PQ))(P(PQ))

E12

(PQ)(P(PQ))

E10

(PQ)P(析取范式)

E9由定理1-5，該公式不是永假公式。(PP)(PQ)（合取范式） E1，E3

由定理7-5，該公式也不是永真公式。由上可知，該公式是一可滿足公式。又P(PQ)

(PQ)P第五十三頁，共八十一頁，2022年，8月28日

四、主析取范式和主合取范式

定義1-16

設(shè)有命題變元P1，P2，…,Pn，形如的命題公式稱為是由命題變元P1，P2，…，Pn所產(chǎn)生的最小項(xiàng)。而形如的命題公式稱為是由命題變元

P1，P2，…，Pn所產(chǎn)生的最大項(xiàng)。其中Pi*為Pi或?yàn)?/p>

Pi(i=1,2,…n).例如,P1∧P2∧P3，P1∧P2∧P3均是由P1，P2，P3所產(chǎn)生的最小項(xiàng)。

P1∨P2∨P3是由P1，P2，P3產(chǎn)生的一個(gè)最大項(xiàng)。第五十四頁，共八十一頁，2022年，8月28日

定義1-17由不同最小項(xiàng)所組成的析取式，稱為主析取范式。定義1-18

由不同最大項(xiàng)所組成的合取式，稱為主合取范式。例如(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主析取范式。

(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主合取范式。第五十五頁，共八十一頁，2022年，8月28日例4

求公式F1=P(P(QP))和公式

F2=(PQ)(PQ)的主析取范式.解

F1P∨(P∧(Q∨P))E11

P∨(P∧Q)∨(P∧P)E3(P∧(Q∨Q))∨(P∧Q)∨(P∧(Q∨Q))E7ノ,E4ノ,E5

(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)E3

(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)E1,E7

五、求公式的主析取范式和主合取范式對任一給定的公式除了用求范式時(shí)的四個(gè)步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。第五十六頁，共八十一頁，2022年，8月28日

F2(PQ)(PQ)

(PQ)(PQ) E11

(PPQ)(QPQ) E3

00E1,E5

0

定理1-6

每一個(gè)不為永假的命題公式F（P1,P2,…,Pn）必與一個(gè)由P1，P2，…，Pn所產(chǎn)生的主析取范式等值。

永真公式的主析取范式包含所有2n個(gè)最小項(xiàng)。

永假公式的主析取范式是一個(gè)空公式。用0表示。第五十七頁，共八十一頁，2022年，8月28日例5

求公式F1=(PQ)(PQ)和

公式F2=P(P(QP))的主合取范式F1(PQ)(PQ) E11

(PQ)(P(QQ))(Q(PP)) E5,E4

(PQ)(PQ)(PQ)(PQ)(PQ)E3

(PQ)(PQ)(PQ)(PQ) E7第五十八頁，共八十一頁，2022年，8月28日

解

F2

P∨(P∧(Q∨P))E11

(P∨P)∧(P∨Q∨P)E3ノ

1∧1E5,E1

1

定理1-7

每一個(gè)不為永真的公式F(P1,P2,…,Pn)必與一個(gè)由P1,P2,…,Pn所產(chǎn)生的主合取范式等值。永假公式的主合取范式包含所有2n個(gè)最大項(xiàng)。永真公式的主合取范式是一空公式，用1表示。第五十九頁，共八十一頁，2022年，8月28日

六、利用主范式判定公式類型

1.利用主析取范式判定

(1)若公式F(P1,P2，…，Pn)的主析取范式包含所有2n個(gè)最小項(xiàng)，則F是永真公式。例如，例4中的F1。

(2)若F的主析取范式是一空公式且為0，則F是永假公式。例如，例4中的F2。(3)否則，F(xiàn)為可滿足的公式。第六十頁，共八十一頁，2022年，8月28日

2利用主合取范式判定

(1)若公式F（P1,P2,…,Pn）的主合取范式包含所有2n個(gè)最大項(xiàng)，則F是永假公式。例如，例5中的F1。

(2)若F的主合取范式是一空公式且為1，則F是永真公式。例如，例5中的F2。

(3)否則，F(xiàn)為可滿足公式第六十一頁，共八十一頁，2022年，8月28日例6

求公式F=(Q(PQ))P的主范式并判定公式的類型.

解

(1)求F的主析取范式F

(Q(PQ))P

Q(PQ)P

(Q(PP))(PQ)(P(QQ))

（PQ)(PQ)(PQ)(PQ)(PQ)

(PQ)(PQ)(PQ)由此可知F是可滿足公式。第六十二頁，共八十一頁，2022年，8月28日(2)求F的主合取范式F（Q(PQ))P

PQ由前分析和舉例可知：僅需求出公式F的任一種主范式即可判定F的類型。第六十三頁，共八十一頁，2022年，8月28日練習(xí)1-4

1．判斷公式F=(P∨Q)→(P?Q)是否為重言式或矛盾式？解

F(P∨Q)∨((P→Q)∧(Q→P))E11

(P∧Q)∨((P∨Q)∧(Q∨P))E10,E6,E11

(P∧Q)∨((P∧(Q∨P))∨(Q∧(Q∨P)))E3

(P∧Q)∨(P∧Q)∨(P∧P)∨(Q∧Q)∨(Q∧P)E3

(P∧Q)∨(P∧Q)∨(Q∧P)E5ノ,E8

F的主析取范式既非空公式，又未包含22=4個(gè)項(xiàng)，故F不是重言式和矛盾式，只是可滿足式。第六十四頁，共八十一頁，2022年，8月28日命題演算的推理理論

一、推理

推理是由已知的命題得到新命題的思維過程。

定義1-19

設(shè)A和B是兩個(gè)命題公式，如果AB，即如果命題公式AB為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，…,Hn和C是一些命題公式,若蘊(yùn)含式H1∧H2∧…∧Hn

C

(*)成立，則稱C是前提集合{H1，H2，…,Hn}的結(jié)論，或稱從前提H1，H2，…,Hn能推出結(jié)論C。有時(shí)也記作H1，H2，…,Hn

C第六十五頁，共八十一頁，2022年，8月28日

1、真值表法

對于命題公式中所有命題變元的每一組真值指派作出該公式的真值表，看是否為永真。PQ00011011解

構(gòu)造其真值表如下：?P?QP→Q（P→Q）∧P(（P→Q）∧P)→Q11101101010100100111例1

考察結(jié)論C是否是下列前提H1，H2的結(jié)論。（1）H1：P→Q，H2：P，C：Q二、如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論第六十六頁，共八十一頁，2022年，8月28日

（2）H1：P→Q，H2：?P，C：?Q解

構(gòu)造其真值表如下：?P?QP→Q（P→Q）∧?P1111101101000010(（P→Q）∧?P)→?Q1011PQ00011011在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定的前提是否能推出這個(gè)結(jié)論來。第六十七頁，共八十一頁，2022年，8月28日

2、等值演算方法

例證明

分析根據(jù)題意，需證明證明第六十八頁，共八十一頁，2022年，8月28日

3、“形式證明”方法

（1）基本述語

形式證明：一個(gè)描述推理過程的命題序列，其中每個(gè)命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，序列中最后一個(gè)命題就是所要求的結(jié)論，這樣的命題序列稱為形式證明。有效的證明：如果證明過程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。有效的結(jié)論：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。

合理的證明：一個(gè)證明是否有效與前提的真假沒有關(guān)系。如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論也是真的。這樣的證明稱作是合理的。合理的結(jié)論：一個(gè)結(jié)論是否有效與它自身的真假沒有關(guān)系。通過合理證明而得到的結(jié)論稱作合理的結(jié)論。第六十九頁，共八十一頁，2022年，8月28日

(2)推理規(guī)則前提引用規(guī)則：在證明的任何步驟上都可以引用前提。結(jié)論引用規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。代入規(guī)則：在證明的任何步驟上，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。第七十頁，共八十一頁，2022年，8月28日例2

證明R∧（P∨Q）是前提P∨Q，Q→R，P→S，?S的結(jié)論。

所以P∨Q，Q→R，P→S，?S

R∧（P∨Q)編號

公式依據(jù)（1）（2）（3）（4）（5）（6）（7）（8）P→S?S?PP∨QQQ→RRR∧（P∨Q）

前提（前提引入規(guī)則）前提（前提引入規(guī)則）（1），（2）；I12前提（3），（4）；I10前提（5），（6）；I11（4），（7）；I9第七十一頁，共八十一頁，2022年，8月28日例3

證明R→S是前提P→（Q→S），?R∨P和Q的有效結(jié)論。

證明

編號公式依據(jù)

(1)(2)(3)(4)(5)(6)(7)(8)(9)

?R∨PR→PP→（Q→S）

R→（Q→S）

?R∨（?Q∨S）

?

Q∨（?R∨S）

Q?R∨SR→S

前提（1）；E11

前提（2），（3）；I13（4）；E11（5）；E1，E2

前提（6），（7）；I10（8）；E11第七十二頁，共八十一頁，2022年，8月28日利用蘊(yùn)