離散命題邏輯

離散數(shù)學第二章

命題邏輯離散命題邏輯第1頁第2章

命題邏輯2.1命題邏輯基本概念2.2命題邏輯等值演算2.3范式2.4推理離散命題邏輯第2頁命題邏輯基本概念一、命題

定義：能判斷真假而不是可真可假陳說句，被稱為命題。

說明：命題真值：作為命題所表示判斷只有兩個結(jié)果：正確和錯誤，此結(jié)果稱為命題真值。命題是正確，稱此命題真值為真；命題是錯誤，稱此命題真值為假。真值為真命題稱為真命題

；真值為假命題稱為假命題。任何命題真值都是唯一。離散命題邏輯第3頁命題邏輯基本概念說明：其它類型句子，如疑問句、祈使句、感嘆

句均沒有真假意義，所以，均不是命題。

在數(shù)理邏輯中，命題真值真和假，有時

分別用1和0來表示，也有時分別用T和F來表示。

命題是含有唯一真值陳說句。離散命題邏輯第4頁命題邏輯基本概念怎樣判斷命題？首先判斷其是否為陳說句其次判斷其是否有唯一真值例1：判斷以下句子是否為命題，真值怎樣？

（1）10是整數(shù)。（2）北京是我們祖國首都。真命題

真命題

（3）雪是黑。（4）x大于y。（5）向右看齊?。?）你吃飯了嗎？疑問句非命題

祈使句非命題

真值不唯一非命題

假命題離散命題邏輯第5頁命題邏輯基本概念例1：判斷以下句子是否為命題，真值怎樣？

（7）本命題是假。（8）我正在說謊。悖論非命題

悖論非命題

（9）元旦是晴天。是命題真假未定“他在說謊?！笔敲}還是悖論？離散命題邏輯第6頁命題與聯(lián)結(jié)詞三、原子命題（簡單命題）

不能被分解為更簡單命題命題，稱為原子命題。

四、復合命題

由若干個原子命題用命題聯(lián)結(jié)詞聯(lián)結(jié)而成命題稱為復合命題。二、命題符號化

用小寫字母

p，q，r，來表示命題。

例2:

p:10是整數(shù)。q：北京是我們祖國首都。r:雪是黑。離散命題邏輯第7頁命題與聯(lián)結(jié)詞例3：判斷以下命題是否為復合命題，并將以下命題符號化。（1）5能被2整除。（2）2是素數(shù)當且僅當三角形有三條邊。原子命題

復合命題

（3）4是2倍數(shù)或是3倍數(shù)。復合命題（4）李明與王華是同學。原子命題（5）藍色和黃色能夠調(diào)配成綠色。原子命題（6）3不是偶數(shù)。復合命題（7）林芳學過英語或日語。復合命題書本24頁例2.2離散命題邏輯第8頁命題與聯(lián)結(jié)詞命題聯(lián)結(jié)詞

說明：否定

符號：

pp0110真值表：定義2.1：設(shè)p為命題，復合命題“非p”（或“p否定”）稱為p否定式，記作p

，符號

稱為否定聯(lián)結(jié)詞。要求p為真當且僅當為假。

p是一元聯(lián)結(jié)詞

離散命題邏輯第9頁命題與聯(lián)結(jié)詞真值表：合取

符號

定義2.2：設(shè)p，q為兩個命題，復合命題“p而且q”（或

p與q）稱為p與q合取式，記作pq，符號稱為合取聯(lián)結(jié)詞。并要求pq為真當且僅當p與q同時為真時為真。

注意：PQPQ000010100111自然語言中“既…，又…”，“不但…，而且…”，“即使…，不過…”，“一面…，一面…”等聯(lián)結(jié)詞可符號化為。但不要見到“與”、“和”就符號化為合取離散命題邏輯第10頁命題與聯(lián)結(jié)詞例4：將以下命題符號化。

（1）吳穎既用功又聰明。（2）吳穎不但用功而且聰明。（3）吳穎即使聰明，但不用功。（4）張輝與王麗都是三好學生。（5）張輝與王麗是同學。p:吳穎用功。q:吳穎聰明。r:張輝是三好學生。s:王麗是三好學生。t:張輝與王麗是同學。pq

pq

rs

pq

t注意：若“和”、“與”連接是主語成份，則該陳說句為簡單命題。離散命題邏輯第11頁命題與聯(lián)結(jié)詞真值表：析取

符號

定義2.3：設(shè)p，q為兩命題，復合命題“p或q”

稱為p與q析取式，記作pq

，符號稱為析取聯(lián)結(jié)詞。并要求pq為假當且僅當p與q同時為假。

PQPQ000011101111注意：自然語言中“或”含有二義性，用它做聯(lián)結(jié)命題有時含有相容性，有時含有排斥性，對應聯(lián)結(jié)詞分別稱為相容或和排斥或。離散命題邏輯第12頁命題與聯(lián)結(jié)詞例5：將以下命題符號化。（1）張明正在睡覺或游泳。（2）李強是位排球隊員或是足球隊員。（3）他昨晚做了二十或三十道題。（4）張靜只能挑選202或203房間?；虮硎炯s數(shù)，不能用析取p:張明正在睡覺。q:張明正在游泳pq排斥或p:李強是位排球隊員。q:李強是位足球隊員

pq相容或p:張靜挑選202房間。q:張靜挑選203房間（pq）

（pq）排斥或

離散命題邏輯第13頁命題與聯(lián)結(jié)詞蘊含

符號：

定義2.4：設(shè)p，q為兩命題，復合命題“假如p，則q”稱為p與q蘊含式，記作pq，并稱p是蘊含式前件，q為蘊含式后件，符號稱為蘊含聯(lián)結(jié)詞。并要求pq為假當且僅當p為真q為假。

真值表：PQPQ001011100111pq邏輯關(guān)系為q是p必要條件。離散命題邏輯第14頁命題與聯(lián)結(jié)詞注意：在自然語言和數(shù)學中，有很多方式來描述蘊含，比如：“只要p，就q”，“因為p，所以q”，“p僅當q”，“只有q才p”，“除非q才p”，“除非q，不然非p”，q是p必要條件，因而所用聯(lián)結(jié)詞應符號化為，各種描述方式都應該符號化為pq。在自然語言中，“假如p，則q”中前件p與后件q往往含有某種內(nèi)在聯(lián)絡，而在數(shù)理邏輯中，p與q能夠無任何內(nèi)在聯(lián)絡。在數(shù)學或其它自然科學中，“假如p，則q”往往表示是前件p為真，后件q也為真推理。但在數(shù)理邏輯中，作為一個要求，當p為假時，不論q是真還是假，pq均為真，也就是說，只有p為真q為假這一個情況，使得復合命題pq為假。離散命題邏輯第15頁命題與聯(lián)結(jié)詞例6：將以下命題符號化。（1）只要不下雨，我就騎自行車上班。（2）只有不下雨，我才騎自行車上班。（3）若2+2=4，則太陽從東方升起。p:天下雨。q:我騎自行車上班。s:2+2=4。t:太陽從東方升起r:太陽從西方升起。（4）若2+24，則太陽從東方升起。（5）若2+2=4，則太陽從西方升起。（6）若2+24，則太陽從西方升起。

pqqp

st

sr

sr

st離散命題邏輯第16頁命題與聯(lián)結(jié)詞等價

符號：

定義2.5：設(shè)p，q為兩命題，復合命題“p當且僅當q”稱為p與q等價式，記作pq，符號稱為等價聯(lián)結(jié)詞。并要求pq為真當且僅當p與q同時為真或同時為假。

真值表：PQPQ001010100111pq邏輯關(guān)系為q與p互為充分必要條件。離散命題邏輯第17頁命題與聯(lián)結(jié)詞例7：將以下命題符號化。（1）2+2=4當且僅當3是奇數(shù)。（2）2+2=4當且僅當3不是奇數(shù)。p:2+2=4。

q:3是奇數(shù)。（3）2+24當且僅當3是奇數(shù)。（4）2+24當且僅當3不是奇數(shù)。

pqpq

pqpq離散命題邏輯第18頁命題與聯(lián)結(jié)詞說明：

由聯(lián)結(jié)詞集｛}中一個聯(lián)結(jié)詞聯(lián)結(jié)一個或兩個原子命題組成復合命題是簡單復合命題，能夠稱他們?yōu)榛緩秃厦}。屢次使用聯(lián)結(jié)詞集中聯(lián)結(jié)詞，能夠組成更為復雜復合命題。求復雜復合命題真值時，還要要求聯(lián)結(jié)詞先后次序。將括號也算在內(nèi)，這個次序為，

對同一優(yōu)先級聯(lián)結(jié)詞，先出現(xiàn)者先運算。我們只關(guān)心復合命題中命題之間真值關(guān)系，而不關(guān)心命題內(nèi)容。離散命題邏輯第19頁命題與聯(lián)結(jié)詞例8：求以下復合命題真值。（1）

pqr

00000

1001001

010100011101100

010101

01

1

110

00

011100

1離散命題邏輯第20頁命題與聯(lián)結(jié)詞例9：求以下復合命題真值。（2）

pqr

00001

1001111

010111011100100

011101

11

1

110

11

111110

0離散命題邏輯第21頁命題公式及分類一、命題常項

定義：簡單命題被稱為命題常項。

二、命題變項 定義：真值能夠改變陳說句為命題變項或命題變元。可以用p，q，r，……表示命題變項。

注意：命題變項不是命題。

離散命題邏輯第22頁命題公式（合式公式）

定義2.6：（1）單個命題常項或變項p,q,r,…,pi,qi,ri,…,0,1是合式公式;

（2）若A是合式公式，則（A）也是合式公式。

（4）只有有限次地應用（1）～（3）形成符

號串才是合式公式。

合式公式也稱為命題公式，并簡稱為公式。

命題公式及分類（3）若A,B是合式公式，則（AB），（AB），（AB），（AB）也是合式公式。離散命題邏輯第23頁例：依據(jù)上述定義，判定下面符號串是不是命題公式。(p∨q)p(q

r)p∨q∨rpq

r

p∨r命題公式及分類?????離散命題邏輯第24頁公式層次

定義2.7：（1）若公式A是單個命題變項，則稱A為0層公式。

（2）稱A是n+1（n0）層公式是指下面情況之一：

（a）A=B，B是n層公式；

命題公式及分類

（b）A=BC,A＝BC,A=BC,A=BC中一個，

其中B，C分別為i層和j層公式，而且n=max（i,j）；

離散命題邏輯第25頁例：求以下命題公式層次。

0層

3層

4層命題公式及分類

2層

4層

2層離散命題邏輯第26頁賦值（解釋）

定義2.8：

設(shè)A為一命題公式，是出現(xiàn)在公式A中全部命題變項，給各指定一個真值，稱為對A一個賦值或解釋，若指定一組值使A真值為1，則稱這組值為A成真賦值，若使A真值為0，則稱這組值為A成假賦值。

注意：含n個命題變項公式含有個不一樣賦值。

命題公式及分類離散命題邏輯第27頁真值表

定義2.9：將命題公式A在全部賦值下取值情況列成表，稱作A真值表。

結(jié)構(gòu)真值表步驟（1）找出公式中所含全體命題變項（若無下腳標就按字典次序排列），列出

個賦值。賦值從000……0開始，然后按二進制加法依次寫出各賦值，直到111……1為止。

（2）按從低到高次序?qū)懗龉礁鱾€層次。

（3）對應各個賦值計算出各個層次真值，知道最終計算出公式真值。命題公式及分類離散命題邏輯第28頁命題公式及其賦值例10：求以下公式真值表。（1）

pqr

00011

1001101

010111011101100

011101

00

0

11001111100

0

10101111離散命題邏輯第29頁例10：求以下公式真值表。（2）

pqr

00011

1001100

010111011100100

010101

00

0

11011111110

0命題公式及分類離散命題邏輯第30頁例10：求以下公式真值表。（3）

11111111

pqr

00011

1001111

010111011111100

000101

00

0

11001111101

1命題公式及分類離散命題邏輯第31頁（4）

pqr

00010

0001100

010100011100100

010101

01

0110

10011110

0例10：求以下公式真值表。命題公式及分類離散命題邏輯第32頁命題公式及其賦值重言式（永真式）、矛盾式（永假式）

定義2.10：（1）若A在它各種賦值下取值均為真，則稱A是重言式或永真式。

（2）若A在它各種賦值下取值均為假，則稱A是矛盾式或永假式。

（3）若A不是矛盾式，則稱A是可滿足式。

離散命題邏輯第33頁命題公式及其賦值結(jié)論：（1）可滿足式最少存在一個成真賦值。

（2）重言式一定是可滿足式，但反之不成立。

（3）真值表能夠用來判斷公式類型。

（4）真值表結(jié)構(gòu)步驟如書本第30頁所表示。

離散命題邏輯第34頁命題公式及其賦值例11：以下兩個命題公式真值表是否相同。

pqr

00011

1001111

010111011111100

000101

10

0

11001011111

1

11110001離散命題邏輯第35頁課堂練習2.12.42.10離散命題邏輯第36頁2.2命題邏輯等值演算離散命題邏輯第37頁等

值

式等值

注意：

不是聯(lián)結(jié)符，它是用來說明A與B等值，要與區(qū)分清楚。

怎樣判斷兩個命題公式是否等值？方法一：經(jīng)過真值表比較在各相同賦值情況下，真值是否相同。

方法二：將A，B組成AB等價公式，判斷其是否為重言式。

定義2.10:設(shè)A、B是兩個命題公式，若A，B組成等價式

為重言式，則稱A與B是等值，記作

。離散命題邏輯第38頁等

值

式例2.11：判斷下面兩個公式是否等值：PQ

000010100111

01010111離散命題邏輯第39頁等

值

式例：判斷下面公式是否等值：pq

000010100111

00001101離散命題邏輯第40頁等

值

式

pqr

000111001111

010111011111100

001101

001110

00111111

1離散命題邏輯第41頁等值演算16組主要等值式

雙重否定冪等律交換率分配律結(jié)合律離散命題邏輯第42頁等值演算吸收律德摩根律零律同一律排中律離散命題邏輯第43頁等值演算矛盾律蘊涵等值式等價等值式假言易位等價否定等值式歸謬論離散命題邏輯第44頁等值演算注意：

上述公式中，A，B，C能夠代表任意公式，因而以上各等值式都是用元語言符號書寫，稱這么等值式為等值式模式，每個等值式模式都給出了無窮多個同類型詳細等值式。這些詳細等值式被稱為原來等值式模式代入實例。離散命題邏輯第45頁等值演算等值演算

定義：由已知等值式推演出另外一些等值式過程為等值演算。等值演算規(guī)則置換規(guī)則：設(shè)是含公式A命題公式，是用公式B置換了

中全部A后得到命題公式，若則：

離散命題邏輯第46頁等值演算等值演算用途（1）證實等值式

例：用等值演算法驗證等值式：離散命題邏輯第47頁蘊含等值式方法1:德

摩根律分配律蘊含等值式等值演算離散命題邏輯第48頁方法2:蘊含等值式分配律德

摩根律蘊含等值式等值演算離散命題邏輯第49頁等價等值式蘊含等值式德

摩根律德

摩根律分配律排中律德

摩根律等值演算離散命題邏輯第50頁（2）判斷命題公式類型

例4：判斷以下公式類型：等值演算離散命題邏輯第51頁永假式（矛盾式）蘊含等值式德

摩根律結(jié)合律矛盾律零

律等值演算離散命題邏輯第52頁等

值

式等價等值式永真式（重言式）離散命題邏輯第53頁等

值

式可滿足式蘊含等值式蘊含等值式德

摩根律分配律等冪律離散命題邏輯第54頁聯(lián)結(jié)詞完備集n元真值函數(shù)

定義2.12注意：n個命題變項可組成個不一樣n元真值函數(shù)。稱F:｛0，1｝n

｛0，1｝為n元真值函數(shù)。

聯(lián)結(jié)詞完備集

定義2.13設(shè)S是一個聯(lián)結(jié)詞集合，假如任何n（n>=1）元真值函數(shù)都能夠由僅含S中聯(lián)結(jié)詞組成公式表示，則稱S是聯(lián)結(jié)詞完備集。離散命題邏輯第55頁聯(lián)結(jié)詞完備集定理2.1：S={

、、

}是聯(lián)結(jié)詞完備集。推論：以下聯(lián)結(jié)詞集都是完備集：（1）S1＝｛、、、｝（2）S2＝｛、、、、｝（3）S3＝｛、｝（4）S4＝｛、｝（5）S5＝｛、｝離散命題邏輯第56頁聯(lián)結(jié)詞完備集定義2.8定理2.2設(shè)p、q為兩個命題，復合命題“p與q否定式”（“p或q否定式”）稱作p，q與非式（或非式），記作（）。符號（）稱作與非聯(lián)結(jié)詞（或非聯(lián)結(jié)詞）。為真當且僅當p與q不一樣時為真（為真當且僅當p與q同時為假）。｛｝｛

｝都是聯(lián)結(jié)詞完備集：離散命題邏輯第57頁2.3范式離散命題邏輯第58頁簡單析取式與簡單合取式定義2.15：命題變項及其否定統(tǒng)稱做文字。僅由有限個文字組成析取式稱為簡單析取式。僅由有限個文字組成合取式稱為簡單合取式。由上述定義可看出以下兩點：(1)一個簡單析取式是重言式，當且僅當它同時包含一個命題變項及其否定。(2)一個簡單合取式是矛盾式，當且僅當它同時包含一個命題變項及其否定。排中律矛盾律離散命題邏輯第59頁例1：判斷下面公式哪些是簡單析取式，哪些是簡單合取式：

簡單析取式與簡單合取式離散命題邏輯第60頁析取范式與合取范式

定義：（1）由有限個簡單合取式組成析取式被稱為析取范式。

（2）由有限個簡單析取式組成合取式被稱為合取范式。

性質(zhì)：（1）一個析取范式是矛盾式，當且僅當它每個簡單合取式都是矛盾式。

（2）一個合取范式是重言式，當且僅當它每個簡單析取式都是重言式。

離散命題邏輯第61頁例2：判斷下面公式哪些是析取式范式，哪些是合取范式

注意：

（1）簡單析取式既是析取范式，也是合取范式；

（2）簡單合取式既是合取范式，也是析取范式；

析取范式與合取范式任何公式都能夠化成等值析取范式和合取范式離散命題邏輯第62頁定理2.5:任一命題公式都存在著與之等值析取范式與合取范式。范式存在定理離散命題邏輯第63頁析取范式與合取范式怎樣將一個命題公式轉(zhuǎn)換成析取范式或合取范式？（1）首先，消去公式中和聯(lián)結(jié)詞。

（2）其次，范式中不允許出現(xiàn)、、

（3）最終，析取范式中不允許出現(xiàn)

合取范式中不允許出現(xiàn)

知道為何轉(zhuǎn)化為析取范式、合取范式嗎？離散命題邏輯第64頁例3：求下面公式析取范式與合取范式

注意：

命題公式析取范式與合取范式不唯一。

析取范式與合取范式離散命題邏輯第65頁定義：極大項、極小項若每個命題變項和它否定式不一樣時出現(xiàn)而二者之一必須出現(xiàn)且僅出現(xiàn)一次且第i

個命題變項或它否定式出現(xiàn)在從左算起第i位上（若命題變項無角標，就按字典次序排列）稱這么簡單合取式（簡單析取式）為極小項（極大項）。在含有n個命題變項簡單合取式（簡單析取式）中：離散命題邏輯第66頁例4：公式中出現(xiàn)p，q，r三個命題變項，以下公式哪些是極小項，極大項？不是極小項，P，P同時出現(xiàn)

不是極小項，其中沒出現(xiàn)r是極小項是極大項不是極大項，P，P同時出現(xiàn)

不是極大項，其中沒出現(xiàn)r注意：n個命題變項共可產(chǎn)生2n個不一樣極小項，也可產(chǎn)生2n

個不一樣極大項。極大項、極小項離散命題邏輯第67頁極小項與極大項記法極小項極大項公式成真賦值名稱公式成假賦值名稱pqr000m0pqr000M0pqr001m1pqr001M1pqr010m2pqr010M2pqr011m3pqr011M3pqr100m4pqr100M4pqr101m5pqr101M5pqr110m6pqr110M6pqr111m7pqr111M7極大項、極小項離散命題邏輯第68頁極大項與極小項定理2.6：設(shè)mi和Mi是命題變項p1，p2….pn形成極小項和極大項，則：注意：是對應名稱極大項與極小項離散命題邏輯第69頁定義2.18：若由n個命題變項組成析取范式（合取范式）中全部簡單合取范式（簡單析取式）都是極小項（極大項），則稱該析取范式（合取范式）為主析取范式（主合取范式）。

主析取范式定理2.7：任何命題公式主析取范式（主合取范式）都是存在，且是唯一。離散命題邏輯第70頁回顧文字簡單析取式、簡單合取式析取范式、合取范式極小項、極大項主析取范式、主合取范式離散命題邏輯第71頁主析取范式怎樣求給定命題公式A主析取范式？ (1)求A析取范式A’(2)若A’中某簡單合取式Bj中既不含命題變項pi，又不含

，則將Bj展開。(3)將重復出現(xiàn)命題變項、矛盾式、重復出現(xiàn)極小項都按冪等律、同一律等“消去”。(4)將極小項按腳標從小到大次序排列，如m1m3m5。離散命題邏輯第72頁例2.17：求主析取范式和主合取范式

主析取范式求析取范式兩個簡單合取式都不是極小項m4,m5m6,m4,m2,m0離散命題邏輯第73頁主析取范式求合取范式離散命題邏輯第74頁（1）求公式成真與成假賦值

若公式A中含有n個命題變項，A主析取范式含s個極小項，

則A有s個成真賦值，他們是所含極小項腳標二進制表示。（2）判斷公式類型

A為重言式當且僅當A主析取范式包含2n

個極小項。

A為矛盾式當且僅當A主析取范式不含任何極小項。

A為可滿足式當且僅當A主析取范式最少含有一個極小項。（3）判斷兩個公式是否等值（4）應用主析取范式分析和處理實際問題。主析取范式用途離散命題邏輯第75頁例2.19：用公式主析取范式判斷公式類型

主析取范式用途離散命題邏輯第76頁主析取范式用途例2.20：判斷以下公式是否等值

離散命題邏輯第77頁主合取范式說明（1）由公式主析取范式求主合取范式

主析取范式中沒有出現(xiàn)極小項下標恰好是主合取范式中

極大項下標。P48，例2.23（2）重言式與矛盾式主合取范式

A為重言式當且僅當A主合取范式不包含任何極大項。

A為矛盾式當且僅當A主合取范式包含2n個極大項。

A為可滿足式當且僅當A主合取范式包含極大項少于2n個。（3）真值表和主析取范式是描述命題公式兩個標準形式

由A主析取范式能夠輕易寫出真值表。離散命題邏輯第78頁知識點回顧1、命題邏輯等值演算（熟記基本等值式）2、連結(jié)詞完備集3、范式相關(guān)概念與計算：簡單析取式、簡單合取式析取范式、合取范式主析取范式、主合取范式由有限個文字組成析取式由簡單合取式組成析取式析取范式，每個簡單合取式都是極小項假如任何n（n>=1）元真值函數(shù)都能夠由僅含S中聯(lián)結(jié)詞組成公式表示，則稱S是聯(lián)結(jié)詞完備集。離散命題邏輯第79頁知識點回顧怎樣求一個公式主析取范式（主合取范式）？（1）消去公式中“蘊含”“等價”連結(jié)詞。方法一：等值演算法（2）否定號內(nèi)移、消去雙重否定。（3）靈活使用分配律、結(jié)合律。（4）將不是極小項（極大項）轉(zhuǎn)換為極小項（極大項）。（5）極小項（極大項）命名、排序。離散命題邏輯第80頁方法二：真值表法知識點回顧怎樣求一個公式主析取范式（主合取范式）？（1）寫出待求公式A真值表。（2）寫出A全部成真賦值（成假賦值）。（3）主析取范式：求出每個成真賦值對應，用名稱

表示極小項，按腳標排序。（4）主合取范式：求出每個成假賦值對應，用名稱

表示極大項，按腳標排序。離散命題邏輯第81頁（1）求公式成真與成假賦值

若公式A中含有n個命題變項，A主析取范式含s個極小項，

則A有s個成真賦值，他們是所含極小項腳標二進制表示。（2）判斷公式類型

A為重言式當且僅當A主析取范式包含2n

個極小項。

A為矛盾式當且僅當A主析取范式不含任何極小項。

A為可滿足式當且僅當A主析取范式最少含有一個極小項。（3）判斷兩個公式是否等值（4）應用主析取范式分析和處理實際問題。知識點回顧主析取范式用途：離散命題邏輯第82頁（1）由公式主析取范式求主合取范式

主析取范式中沒有出現(xiàn)極小項下標恰好是主合取范式中

極大項下標。（2）重言式與矛盾式主合取范式

A為重言式當且僅當A主合取范式不包含任何極大項。

A為矛盾式當且僅當A主合取范式包含2n個極大項。

A為可滿足式當且僅當A主合取范式包含極大項少于2n個。知識點回顧主合取范式說明：離散命題邏輯第83頁學習要求熟記24組等值演算基本公式。熟練掌握公式等值證實方法，會用等值演算判斷公式類型。了解連結(jié)詞完備集含義。熟練掌握公式析取范式（合取范式）、主析取范式求解方法。會用主析取范式判斷公式類型、寫出真值表。會利用公式主析取范式（合取范式）處理簡單實際問題。離散命題邏輯第84頁2.4推

理離散命題邏輯第85頁86內(nèi)容：重點：

(1)了解推理概念；

(2)掌握8條推理定律；

(3)掌握推理規(guī)則；

(4)掌握結(jié)構(gòu)證實法。

了解：

附加前提證實法和歸謬法。

推理規(guī)則，結(jié)構(gòu)證實法。推理概念，推理定律，離散命題邏輯第86頁推

理

理

論1、考慮從一些前提A1、A2、……An出發(fā)，能推導出什么結(jié)論。2、數(shù)理邏輯主要任務是用邏輯方法研究數(shù)學中推理。3、所謂推理是指從前提出發(fā)，應用推理規(guī)則推出結(jié)論思維過程。4、推理都由前提和結(jié)論兩部分組成。前提就是推理所依據(jù)已知命題，結(jié)論則是從前提出發(fā)經(jīng)過推理而得到新命題。5、首先應該明確什么樣推理是有效或正確關(guān)于推理那些事兒離散命題邏輯第87頁推理形式結(jié)構(gòu)定義2.19：設(shè)A1，A2，…Ak,B都是命題公式，若對于A1，A2，…Ak,B任意一組賦值，或者A1∧A2∧…Ak為假，或者當A1∧A2∧…Ak為真時，B也為真，則稱由前提A1，A2，…Ak推出B推理是有效，或者正確。定理2.8：命題公式A1，A2，…Ak,推出B推論正確當且僅當(A1∧A2∧…Ak)→B為重言式。離散命題邏輯第88頁推理形式結(jié)構(gòu)前提：A1，A2…Ak結(jié)論：B(A1∧A2∧…Ak)→B推理兩種形式結(jié)構(gòu)：怎樣判斷一個推理是否有效：(1)將推理中簡單命題符號化。(2)寫出前提和結(jié)論，形式化為(A1∧A2∧…Ak)→B(3)判斷(A1∧A2∧…Ak)→B是否為重言式。還記得判斷重言式方法嗎？真值表法、等值演算法、主析取范式法、觀察法。離散命題邏輯第89頁90例:

判斷下面推理是否正確。

(1)假如天氣涼快，小王就不去游泳，天氣涼快，所以小王沒去游泳。

結(jié)論：

推理形式結(jié)構(gòu)為：

判斷此蘊涵式是否為重言式

前提：，解：設(shè)小王去游泳。：：天氣涼快，離散命題邏輯第90頁91[方法一]用等值演算法。

所以推理正確。

[方法二]用真值表法。

其真值表中最終一列全為1，

所以推理正確。

離散命題邏輯第91頁92[方法三]用主析取范式法。

主析取范式含全部最小項，所以推理正確。

離散命題邏輯第92頁93(