第九章命題邏輯分析課件

數(shù)理邏輯又稱符號邏輯、理論邏輯。它既是數(shù)學(xué)的一個(gè)分支，也是邏輯學(xué)的一個(gè)分支；是用數(shù)學(xué)的方法研究邏輯或形式邏輯的學(xué)科。數(shù)理邏輯就是精確化、數(shù)學(xué)化的形式邏輯。數(shù)理邏輯包括命題邏輯和謂詞邏輯。它是現(xiàn)代計(jì)算機(jī)技術(shù)的基礎(chǔ)。它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用提供必要的理論基礎(chǔ)。第9章命題邏輯數(shù)理邏輯又稱符號邏輯、理論邏輯。它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、例1張三說李四在說謊,李四說王五在說謊,

王五說張三和李四都在說謊.

問:誰說的是真話?

例2有一倉庫被盜,經(jīng)偵察確定甲,乙,丙,丁

四人中的兩人作案,且可靠的線索有:

(1)甲,乙兩人中有且只有一個(gè)人去過倉庫;

(2)乙和丁不會(huì)同時(shí)去倉庫;

(3)丙若去倉庫,丁必定同去;

(4)丁若沒去倉庫,則甲也沒去.

判斷四人中哪兩人作案?解答:(1)李四說真話;(2)作案者為甲和丁.例1張三說李四在說謊,李四說王五在說謊,9.1命題和命題聯(lián)結(jié)詞

一、命題的概念二、命題聯(lián)結(jié)詞和真值表三、命題的符號化四、命題公式9.1命題和命題聯(lián)結(jié)詞一、命題的概念

1.命題的定義

能夠確定或分辨其真假的陳述句,

且真與假必居其一。

簡言之,命題是非真即假的陳述句。

2.命題的真值

命題是真就說其真值為真,用“1”表示，

命題是假就說其真值為假,用“0”表示。真值為真的命題稱為真命題,真值為假的命題稱假命題。一、命題的概念1.命題的定義一、命題的概念

3.說明：判斷命題應(yīng)注意以下幾點(diǎn)

(1)那些“自稱謂”的陳述句可能產(chǎn)生自相矛盾的

結(jié)論(悖論),故不在討論之列.例如：我現(xiàn)在說真話.

(2)“很難”,“相當(dāng)年輕”等這些概念

沒有清晰的界限,屬于模糊概念,故不在討論之列.例如：這個(gè)題目很難.(3)某些命題尚未確定其真值.例如：火星上存在有生命的物種.

(4)某些命題可能無法查明其真值.

例如:公元1014年元旦北京下過雨.

(5)命題真假會(huì)因時(shí)因地而異.

例如:現(xiàn)在是上午.3.說明：判斷命題應(yīng)注意以下幾點(diǎn)

例1判斷下列句子是否是命題

(1)4是素?cái)?shù).

(2)π是無理數(shù).

(3)月球上有水.

(4)π大于2嗎

(5)請不要吸煙！

(6)這朵花真美麗啊！

(7)x大于y.

-------------是假命題---------是真命題---------是真命題---------不是命題--------不是命題----不是命題-------------不是命題例1判斷下列句子是否是命題-------------是4.命題的表示一般用大寫的英文字母表示一個(gè)最簡單命題。例如：P：我是學(xué)生。Q：我明天要上學(xué)。4.命題的表示一般用大寫的英文字母表示一個(gè)最簡單命題。例如：

1.原子命題再細(xì)分不成為句子的命題稱為原子命題。

例如:“明天下雪”和“7是素?cái)?shù)”

都是原子命題。

2.復(fù)合命題

原子命題?？赏ㄟ^一些命題聯(lián)結(jié)詞構(gòu)成新命題,這種命題稱為復(fù)合命題。例如:“明天下雪或下雨”；“明天下雨并且下雪”;“如果明天下雨,我就不去游泳”等，

都是復(fù)合命題。

二、命題的類型1.原子命題二、命題的類型

1.命題聯(lián)結(jié)詞:

又稱邏輯運(yùn)算符號，

是通常語言里的連接詞的邏輯抽象。

常用的命題聯(lián)結(jié)詞有五種:

否定、合取、析取、蘊(yùn)涵、等值三、命題聯(lián)結(jié)詞1.命題聯(lián)結(jié)詞:三、命題聯(lián)結(jié)詞

注:?P為真當(dāng)且僅當(dāng)P為假。

?P的真值表：P?P假真真假P

?P1001設(shè)P為命題,那么“對P的否定”為另一命題。

表示為?P,叫做P的否定,讀做“非P”。2.五種聯(lián)結(jié)詞例2

設(shè)P:3是素?cái)?shù);則?P:3不是素?cái)?shù)。

1)否定（

?）設(shè)Q:這些都是男生;則?Q:這些都不是男生。注:?P為真當(dāng)且僅當(dāng)P為假。P?P假真P?P設(shè)P,Q為命題,那么“P并且Q”為一復(fù)合命題,表示為P∧Q,叫做P和Q的合取,讀做“P且Q”。注:P∧Q為真當(dāng)且僅當(dāng)P和Q同為真。

P∧Q的真值表：PQP∧Q000110110001例3設(shè)P:2是素?cái)?shù),Q:2是偶數(shù);

則P∧Q:2是素?cái)?shù),并且是偶數(shù)

2)合取（∧）設(shè)P,Q為命題,那么“P并且Q”為一復(fù)合命題,PQP3）

析?。ā牛┰O(shè)P,Q為命題,那么“P或者Q”為一復(fù)合命題,

表示為P∨Q,叫做P和Q的析取,讀做“P或Q”。

注:P∨Q為真當(dāng)且僅當(dāng)P和Q至少一個(gè)為真。

P∨Q的真值表：PQP∨Q000110110111例4

設(shè)P:張三愛唱歌,Q:張三愛聽音樂;

則P∨Q:張三愛唱歌或愛聽音樂。3）析?。ā牛㏄QP∨Q000例4設(shè)P思考:

張明下午在寢室或在圖書館。“或”:可兼或和排斥或（不可兼或）。

(P∧?Q)∨(?P∧Q)表示排斥或,

表示P和Q不能同時(shí)發(fā)生。思考:張明下午在寢室或在圖書館。

4)蘊(yùn)含（條件）（→）

設(shè)P,Q為命題,則“如果P就Q”為一復(fù)合命題,

表示為P→Q,讀做“若P則Q”。

這里,P叫做前提,假設(shè)或前件;

Q叫做結(jié)論或后件。注:P→Q為假當(dāng)且僅當(dāng)P為真而Q為假。

P→Q的真值表：PQP

Q0001101111014)蘊(yùn)含（條件）（→）PQPQ001

P→Q的邏輯關(guān)系:

Q是P的必要條件,P是Q的充分條件。

若P,則Q；如果P,那么Q；因?yàn)镻,所以Q。例:如果(因?yàn)?我有課,那么(所以)我去教室。

Q每當(dāng)P；P僅當(dāng)Q。例:每當(dāng)有課我去教室。我去教室僅當(dāng)我有課。

只要P,就Q；

只有P才Q。例:只要(只有)我有課,我就(才)去教室。

除非Q才P；

除非Q,否則非P。例:除非我有課,我才(否則我不)去教室。說明：P→Q的邏輯關(guān)系:說明：注1

在數(shù)理邏輯中,“如果P,那么Q”中的

前件P與后件Q可以無任何內(nèi)在聯(lián)系。例如：“若6是偶數(shù)，則明天下雨”。注2

在數(shù)理邏輯中,作為一種規(guī)定,

當(dāng)P為假時(shí),無論Q是真是假,P→Q均為真。例5張三對李四說:“我去書店一定幫你買那本書”。設(shè)P:張三去書店;Q:張三買那本書;

則可以將這句話表示為命題:P→Q.

注1在數(shù)理邏輯中,“如果P,那么Q”中的5)等值（雙條件）（

）

設(shè)P,Q為命題,則“P當(dāng)且僅當(dāng)Q”為復(fù)合命題,表示為P

Q,讀做“P當(dāng)且僅當(dāng)Q”。

P

Q也可讀做“P是Q的充要條件”。

注:P

Q為真當(dāng)且僅當(dāng)P和Q同為真或同為假?；虍?dāng)且僅當(dāng)P→Q和Q→P都為真,5)等值（雙條件）（）P

Q的真值表:

PQP

Q000110111001例6:設(shè)P:我去游泳,Q:天下雨;

則P

?Q:我去游泳當(dāng)且僅當(dāng)天不下雨。PQ的真值表:PQPQ001例6:3.命題的符號化

符號化應(yīng)注意以下幾點(diǎn):

(1)確定語句是否為命題,不是就不必翻譯。

(2)確定語句中的連接詞是否能對應(yīng)于并且

對應(yīng)于哪一個(gè)命題聯(lián)結(jié)詞;

(3)正確表示原子命題和選擇命題聯(lián)結(jié)詞;

(5)原子命題一般表示成肯定。

(4)要按邏輯關(guān)系翻譯而不能憑字面翻譯。3.命題的符號化例7將下列命題符號化:

(1)他有理論知識但無實(shí)踐經(jīng)驗(yàn)。

(2)小張是計(jì)算機(jī)學(xué)院的學(xué)生，

他住在8號樓202室或203室。

(3)又大又紅的蘋果我才會(huì)買。

(4)如果小王和小張都不去,則小李去。

(5)如果小王和小張不都去,則小李去。

P∧?Q(P∧Q)→R(?P∧?Q)→R?(P∧Q)→RP∧((Q∧?R)∨(?Q∧R))例7將下列命題符號化:P∧?Q(P∧Q)→R(?P∧?Q)9.2命題公式1.命題變元:

如果P代表真值未指定的任意命題,

就稱P為命題變元

2.

命題常元:

如果P代表真值已指定的命題,

就稱P為命題常元.(1和0稱為命題常元)

3.

原子公式:單個(gè)命題變元和命題常元.一、命題變元(常元）9.2命題公式1.命題變元:一、命題變元(常元）

定義遞歸定義命題公式:

(1)0和1是命題公式;

(2)命題變元是命題公式;

(3)如果A是命題公式,則?A是命題公式;

(4)如果A和B是命題公式,

則A∧B,A∨B,A→B,A

B是命題公式;

(5)只有有限次利用上述(1)(2)(3)(4)

而產(chǎn)生的符號串才是命題公式。二、命題公式定義遞歸定義命題公式:二、命題公式

例1下面的符號串不是公式

P→QP,∨R→P,P→P∨,(P∧Q∨R))Q∧R).

下面的符號串是公式

(P∨Q)→(?P∧R),(P∧(Q∨R))(Q∧R).例1下面的符號串不是公式

定義設(shè)P1,P2,…,Pn是出現(xiàn)在命題公式

F中的全部命題變元,

給P1,P2,…,Pn各指定一個(gè)真值(真或假),稱為對F的一個(gè)真值指派(賦值或解釋)。

思考:含有n個(gè)命題變元的命題公式F

有多少種真值指派?

三、公式的真值指派（賦值）定義設(shè)P1,P2,…,Pn是出現(xiàn)在命題公式三、公式四、公式的真值表用表格的形式來反映公式在所有不同的真值指派下與其命題變元之間的真值關(guān)系，這樣的表格稱為公式的真值表。四、公式的真值表用表格的形式來反映公式在所有不同的定義

設(shè)A為任一命題公式:

(1)若公式A在它的各種賦值下取值均為真,

則稱公式A是重言式或永真式;

(2)若公式A在它的各種賦值下取值均為假,則稱公式是矛盾式或永假式;

(3)若至少有一組真值指派使公式

A的值為真，則稱公式A是可滿足式。五、公式的類型定義設(shè)A為任一命題公式:五、公式的類型9.3命題公式的等值關(guān)系和蘊(yùn)含關(guān)系1.定義

設(shè)A和B是兩個(gè)命題公式,若公式AB為重言式,

則稱公式A和B是等值的公式,記為AB。注:(1)

當(dāng)且僅當(dāng)在所有真值指派下，

公式A和B的真值完全相同時(shí),

公式A和B才是兩個(gè)等值的公式。

(2)

AB是表示一個(gè)公式，

而AB是表示兩公式A和B的關(guān)系是等值。一、命題公式的等值關(guān)系9.3命題公式的等值關(guān)系和蘊(yùn)含關(guān)系1.定義一、命

1）自反性：

AA。

2）對稱性：若AB則BA。

3)傳遞性：若AB,BC,則AC。

2.等值關(guān)系的性質(zhì)等值關(guān)系是一個(gè)等價(jià)關(guān)系。2.等值關(guān)系的性質(zhì)等值關(guān)系是一個(gè)等價(jià)關(guān)系。

3.證明邏輯恒等式A

B的方法:

(1)利用真值表:證明公式AB為重言式。

例1證明：德.摩根定律?(P∨Q)

?P∧?Q證明:公式(?(P∨Q))

(?P∧?Q)真值表：PQP∨Q?(P∨Q)?P∧?Q(?(P∨Q))

(?P∧?Q)000110110111100010001111從真值表可得：?(P∨Q)

?P∧?Q。3.證明邏輯恒等式AB的方法:例1證明1)代入規(guī)則:

重言式中某命題變元出現(xiàn)的每一處

均代以同一命題公式后所得命題公式

(代入實(shí)例)仍為重言式。如：

在P∨(P∧Q)

P中以(R→P)代P得

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

在P∨Q

Q∨P中以?C代P,同時(shí)以(?A∧B)代Q得

?C∨(?A∧B)

(?A∧B)∨?C

(2)等值演算：

a)常用的等值式

b)兩個(gè)規(guī)則1)代入規(guī)則:(2)等值演算：a)常用的等值2)定義

若C是公式A中的一部分且C為公式,則稱C為A的子公式。例:P∨Q和P∧R是公式P∨Q→P∧R

的子公式。

3)替換規(guī)則:

若C是A的子公式,且C

D。

如果將公式A中的子公式C，

置換成公式D之后,得到公式B,

則AB。2)定義

1.定義

設(shè)A和B是兩個(gè)公式,若公式A→B是重言式,即A→B1,則稱公式A蘊(yùn)含公式B,記作AB。

2.蘊(yùn)含關(guān)系的性質(zhì)

二、命題公式的蘊(yùn)含關(guān)系自反性：

AA.反對稱性：若AB,BA,則AB.

傳遞性：若AB,BC,則AC.蘊(yùn)含關(guān)系是一個(gè)偏序關(guān)系。1.定義二、命題公式的蘊(yùn)含關(guān)系自反性：A

(2)演繹推理：

a）證明A為真時(shí)B為真.

b)證明B為假時(shí)A為假。

3.證明永真蘊(yùn)涵式A

B的方法:(1)利用真值表:證明公式A→B為重言式。3.證明永真蘊(yùn)涵式AB的方法:(1)利用真值

例1證明(P→Q)∧?Q

?P。證明:設(shè)(P→Q)∧?Q為真,

則P→Q和?Q同為真;

因此Q為假;從而P為假;

所以?P為真。

例2證明(P→Q)∧(Q→R)

P→R。證明:設(shè)P→R為假,

則P為真而R為假;對Q分兩種情況討論:

(a)若Q為真,則因R為假,故Q→R為假;

(b)若Q為假,則因P為真,故P→Q為假;

則(P→Q)∧(Q→R)為假。例1證明(P→Q)∧?Q?P。9.4范式

一、質(zhì)合取式與質(zhì)析取式

二、析取范式與合取范式

三、最小項(xiàng)與最大項(xiàng)

四、主析取范式與主合取范式9.4范式一、質(zhì)合取式與質(zhì)析取式

定義1一個(gè)由命題變元或命題變元的否定所組成的合取式稱為質(zhì)合取式。

定義2

一個(gè)由命題變元或命題變元的否定所組成的析取式稱為質(zhì)析取式。

如：設(shè)P和Q是兩個(gè)命題變元,則P,P∧Q,?P∧Q,?P∧?Q都是質(zhì)合取式,

而

Q,P∨Q,?P∨Q,?P∨?Q都是質(zhì)析取式。

一、質(zhì)合（析）取式1.質(zhì)合（析）取式的定義定義1一個(gè)由命題變元或命題變元的否定一、質(zhì)合（析）(1)質(zhì)合取式為矛盾式的充分必要條件是,

它同時(shí)包含某個(gè)命題變元P及其否定?P。

(2)

質(zhì)析取式為重言式的充分必要條件是,

它同時(shí)包含某個(gè)命題變元P及其否定?P。2.定理(1)質(zhì)合取式為矛盾式的充分必要條件是,2.定

定義3一個(gè)由質(zhì)合取式的析取所組成的公式,

稱為析取范式,即該公式具有形式:

A1∨A2∨…∨An(n≥1)

其中A1,A2,…,An都是質(zhì)合取式。

定義4一個(gè)由質(zhì)析取式的合取所組成的公式,

稱為合取范式,即該公式具有形式:

A1∧A2

∧…∧An(n≥1)

其中A1,A2,…,An都是質(zhì)析取式。

如：

?P∨(P∧Q)∨(Q∧R)為析取范式。

(?P∨Q∨R)∧(?Q∨?R)∧Q為合取范式。二、析（合）取范式1.析（合）取范式的定義定義3一個(gè)由質(zhì)合取式的析取所組成的公式,二、析（合

3.定理:對于任何命題公式A都存在

與其等值的析取范式和合取范式。

4.求與A邏輯等價(jià)的析取范式和合取范式的方法:

(1)用蘊(yùn)涵表達(dá)式和等值表達(dá)式消去公式A中的→和

聯(lián)結(jié)詞;

(2)用雙重否定律和德

摩根律將A中的?都消去

或移到命題變元之前;

(3)用結(jié)合律和分配律將公式化成析取范式

或合取范式。3.定理:對于任何命題公式A都存在

例1求公式：(P→Q)→P的析取范式

與合取范式。解:公式

?(?P∨Q)∨P

(P∧?Q)∨P(析取范式)

(P∨P)∧(?Q∨P)(合取范式)

P∧(P∨?Q)(合取范式)例1求公式：(P→Q)→P的析取范式

三、最?。ù螅╉?xiàng)

定義5

思考:含n個(gè)變元的最小項(xiàng)和最大項(xiàng)的個(gè)數(shù)？設(shè)有個(gè)n命題變元P1,P2,…,Pn,形如P1,P2,…,Pn所產(chǎn)生的最大項(xiàng)。的命題公式稱為由命題變元而形如的命題公式稱由命題變元P1,P2,…,Pn所產(chǎn)生的最小項(xiàng)。其中每個(gè)或?yàn)镻i,或?yàn)?Pi

，即Pi、?Pi

必出現(xiàn)一個(gè)，且只能出現(xiàn)一個(gè)。三、最?。ù螅╉?xiàng)定義5思考:含n個(gè)最小項(xiàng)最大項(xiàng)公式成真賦值編號公式成假賦值編號?P∧?Q?P∧QP∧?QP∧Q00011011m00m01m10m11P∨QP∨?Q?P∨Q?P∨?Q00011011M00M01M10M11

含2個(gè)命題變元P,Q的最小項(xiàng)和最大項(xiàng)最小項(xiàng)最大項(xiàng)公式成真賦值編號公式成假賦值編號?P∧?Q00最小項(xiàng)最大項(xiàng)公式成真賦值編號公式成假賦值編號?P∧?Q∧?R?P∧?Q∧R?P∧Q∧?R?P∧Q∧RP∧?Q∧?RP∧?Q∧RP∧Q∧?RP∧Q∧R000001010011100101110111m000m001m010m011m100m101m110m111P∨Q∨RP∨Q∨?RP∨?Q∨RP∨?Q∨?R?P∨Q∨R?P∨Q∨?R?P∨?Q∨R?P∨?Q∨?R000001010011100101110111M000M001M010M011M100M101M110M111

含3個(gè)命題變元P,Q,R的最小項(xiàng)和最大項(xiàng)最小項(xiàng)最大項(xiàng)公式成真編號公式成假編號?P∧?Q∧?R000

1.定義

由不同的最小項(xiàng)所組成的析取式,

稱為主析取范式。

由不同的最大項(xiàng)所組成的合取式,

稱為主合取范式。

四、主析（合）取范式1.定義四、主析（合）取范式任何非重言式都有唯一的主合取范式。

重言式無主合取范式，定義為“1”。2.定理3.定理任何非矛盾式都有唯一的主析取范式。

矛盾式無主析取范式，定義為“0”。

矛盾式主合取范式必是所有最大項(xiàng)的合取。

重言式主析取范式必是所有最小項(xiàng)的析取。任何非重言式都有唯一的主合取范式。2.定理3.

a.利用真值表法求主析(合)取范式:

(1)求主析取范式考慮真值表中對應(yīng)1的行

所有最小項(xiàng)的析取。

(2)求主合取范式考慮真值表中對應(yīng)0的行

所有最大項(xiàng)的合取。

4.求命題公式主析(合)取范式的方法a.利用真值表法求主析(合)取范式:4.求命題公式主

例2用真值表求公式(P→Q)∧Q的主析(合)取范式。

PQP→Q(P→Q)∧Q0001101111010101考慮真值表為真的行,得公式的主析取范式：(?P∧Q)∨(P∧Q)考慮真值表為假的行,得公式的主合取范式：

(P∨Q)∧(?P∨Q)。例2用真值表求公式(P→Q)∧Q的主析(合)取范式。Pb.利用等值演算求主析(合)取范式步驟:(1)把給定命題公式化成析(合)取范式;(2)刪除析(合)取范式中所有為永假(真)的

質(zhì)合取式(質(zhì)析取式);(3)用等冪律將重復(fù)出現(xiàn)的變元化為一次出現(xiàn);(4)補(bǔ)進(jìn)析(合)取范式中未出現(xiàn)的所有變元;(5)用等冪律消去重復(fù)出現(xiàn)的最小(大)項(xiàng)。b.利用等值演算求主析(合)取范式步驟:

例3求公式：(P→Q)∧Q的主析取范式與主合取范式。解:(P→Q)∧Q

(?P∨Q)∧Q

(?P∨Q)∧(Q∨(P∧?P))

(?P∨Q)∧(P∨Q)∧(?P∨Q)

(?P∨Q)∧(P∨Q)(主合取范式)

主析取范式:(?P∧Q)∨(P∧Q)

例3求公式：(P→Q)∧Q的主析取范式與主合取范式。9.5命題演算的推理理論

一、推理規(guī)則二、證明方法9.5命題演算的推理理論一

1.定義

設(shè)A和B是兩個(gè)命題公式,如果AB,

即如果命題公式AB為重言式,

則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地,假設(shè)H1,H2,…,Hn和C是一些命題,

如果:H1∧H2∧…∧HnC

則稱從前提H1,H2,…,Hn推出結(jié)論C,

有時(shí)候也記為H1,H2,…,HnC，

并且稱{H1,H2,…,Hn}為C的前提集合。

一、有效推理的概念1.定義一、有效推理的概念

PQPQP∧(PQ)QQ∧(PQ)P0001101111010001010101010011例1判斷結(jié)論C能否可以從前提H1和H2推出

(1)H1:PQ,H2:P,C:Q(2)H1:PQ,H2:Q,C:P解:寫出前提的合取式和結(jié)論的真值表,

看是否出現(xiàn)前提合取式為真,而結(jié)論為假的情形。

由真值表可得：(1)可以，(2)不行PQPQP∧(PQ)QQ∧(PQ)P001

例2判斷下列推理是否正確:

若下午氣溫超過30℃,則小王必去游泳;

若他去游泳,他就不去看電影了.

所以若小王沒去看電影,下午氣溫必超過30℃。解:設(shè)P:下午氣溫超過30℃;Q:小王去游泳;

R:小王去看電影.

則前提:P→Q,Q→?R;結(jié)論:?R→P;

推理的形式結(jié)構(gòu):(P→Q)∧(Q→?R)

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

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

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

非永真,因此推理不正確。例2判斷下列推理是否正確:

1.定義：

形式證明是一個(gè)描述推理過稱的命題序列。

其中每個(gè)命題或是已知的命題，

或是有某些前提所推得的結(jié)論。

序列中最后一個(gè)命題就是所要求的結(jié)論。

二、形式證明的概念1.定義：二、形式證明的概念

2.推理規(guī)則：

(1)

前提引入規(guī)則:

在證明的任何步驟上都可以引用前提。

(2)

結(jié)論引用規(guī)則:

在證明的任何步驟上所得到的結(jié)論，

都可以在其后的證明中引用。

(3)

置換規(guī)則:

在證明的任何步驟上,命題公式的子公式

都可以用與之等值的其他命題公式置換。

(4)

代入規(guī)則:

在證明的任何步驟上,重言式中的任一命題變元

都可以用一命題公式代入,得到的仍是重言式。2.推理規(guī)則：

3.證明的有效性：定義

如果證明過程中的每一步所得到的結(jié)論

都是根據(jù)推理規(guī)則得到的,則這樣的證明稱為是有效的。通過有效的證明而得到的結(jié)論,稱為是有效的結(jié)論。

4.證明方法:

直接證明法和間接證明法。直接證明法有兩種方法：

PT規(guī)則和CP規(guī)則3.證明的有效性：

例3證明：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)PPT(1)(2)PT(3)(4)PT(5)(6)T(4)(7)a)PT規(guī)則例3證明：P∨Q,Q→R,P→S,?SR例4證明下列推理的正確性：若這里有球賽,則通行是困難的;若他們按時(shí)到達(dá),則通行是不困難的;

他們按時(shí)到達(dá)了,所以這里沒有球賽。解：設(shè)P:這里有球賽;Q:通行是困難的;R:他們按時(shí)到達(dá)則要證明:P→Q,R→?Q,R

?P。

編號

公式依據(jù)(1)(2)(3)(4)(5)RR→?Q?QP→Q?PPPT(1)(2)PT(3)(4)例4證明下列推理的正確性：編號公式依據(jù)例5利用有效推理方法破