離散數(shù)學(xué)數(shù)理邏輯

離散數(shù)學(xué)數(shù)理邏輯第一頁，共八十六頁，2022年，8月28日1教材與參考資料教材：《離散數(shù)學(xué)》（第2版），屈婉玲、耿素云、張立昂編，清華大學(xué)出版社參考資料：《離散數(shù)學(xué)》，劉玉珍、劉詠梅編，武漢大學(xué)出版社《DiscreteMathematicalStructures》(SixthEdition)，

BernardKolman,FobertC.BusbyandSharonRoss，高等教育出版社有影印版、譯本《DiscreteMathematicsandItsApplications》(SixthEdition)，[美]KennethH.Rosen，機械工業(yè)出版社影印版、譯本第二頁，共八十六頁，2022年，8月28日2課程主要內(nèi)容數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)*第三頁，共八十六頁，2022年，8月28日3目的、意義和要求研究內(nèi)容：離散量的結(jié)構(gòu)及其相互間的關(guān)系。意義：計算機科學(xué)的理論基礎(chǔ)。目的：打基礎(chǔ)必備的數(shù)學(xué)知識培養(yǎng)抽象思維能力、邏輯推理能力教學(xué)內(nèi)容：第1-7章重點第9、14章備選第8、11章自學(xué)第10、12、13章不要求

第四頁，共八十六頁，2022年，8月28日4學(xué)習(xí)要求1、課堂要求：按時上課認真聽講2、課外要求：復(fù)習(xí)(每次課后，安排半個小時)

認真、按時完成作業(yè)(每次課后，安排1個小時)第五頁，共八十六頁，2022年，8月28日5學(xué)習(xí)考查方法1、出勤率：10%不定期檢查出勤情況2、作業(yè)完成情況：10%對作業(yè)完成情況進行登記3、課堂測驗+期中考試：20%共5次4、期末考試（閉卷）：60%第六頁，共八十六頁，2022年，8月28日6第一篇數(shù)理邏輯

第1章導(dǎo)論數(shù)理邏輯的概念數(shù)理邏輯的發(fā)展簡史數(shù)理邏輯的地位和作用第七頁，共八十六頁，2022年，8月28日7（1）定義§1.1數(shù)理邏輯的概念數(shù)理邏輯是采用數(shù)學(xué)方法研究抽象思維推理規(guī)律（形式推理）的一門科學(xué)。命題邏輯是數(shù)理邏輯的基本組成部分之一推理的基本要素是命題把命題作為基本單位來分析符號化研究公式間的關(guān)系

推導(dǎo)、演算

第八頁，共八十六頁，2022年，8月28日8（2）方法

引入一套數(shù)學(xué)符號系統(tǒng)來進行研究，強調(diào)推理過程中前提和結(jié)論之間的形式關(guān)系。例：A、B、C、D4人做百米競賽，觀眾甲、乙、丙預(yù)報比賽結(jié)果的名次為： 甲：C第一，B第二 乙：C第二，D第三 丙：A第二，D第四比賽結(jié)束后發(fā)現(xiàn)甲乙丙每人報告的情況都各對一半，試問實際名次如何？1.引入pi,qi,ri,si分別表示“A排名第i，B排名第i，C排名第i，D排名第i”2.給出個命題之間的關(guān)系

（1）(r1∧┐q2)∨(┐r1

∧q2)1

（2）(r2∧┐s3)∨(┐r2

∧s3)1（3）(p2∧┐s4)∨(┐p2

∧s4)13.通過演算規(guī)則，得出結(jié)果第九頁，共八十六頁，2022年，8月28日9（3）內(nèi)容謂詞邏輯命題邏輯第十頁，共八十六頁，2022年，8月28日10（4）分支模型論證明論公理集合論遞歸論第十一頁，共八十六頁，2022年，8月28日11§1.2數(shù)理邏輯的發(fā)展簡史創(chuàng)立階段起源階段完善階段

發(fā)展歷史第十二頁，共八十六頁，2022年，8月28日12起源階段

德國數(shù)學(xué)家、哲學(xué)家G.Leibniz（1646~1716），提出建立一種普遍的符號語言，利用符號語言進行思維演算的設(shè)想。第十三頁，共八十六頁，2022年，8月28日13創(chuàng)立階段英國數(shù)學(xué)家G.Bool于1847年發(fā)表《邏輯的數(shù)學(xué)分析》，創(chuàng)建一套表示邏輯推理的基本符號以及符號的運算規(guī)律，建立了布爾代數(shù)。德國數(shù)學(xué)家G.Frege于1879年在《概念的演算》一書中引進謂詞符號和量詞符號，創(chuàng)建第一個比較嚴格的邏輯演算系統(tǒng)。第十四頁，共八十六頁，2022年，8月28日14完善階段英國邏輯學(xué)家和B.Russel于1910將當(dāng)時的數(shù)理邏輯寫入了《數(shù)學(xué)原理》中，使數(shù)理邏輯成為了一門專門的學(xué)科。

20世紀30年代，由于眾多科學(xué)家的努力，衍生出許多新的分支，如：直覺主義邏輯、多值邏輯、組合邏輯等。第十五頁，共八十六頁，2022年，8月28日15§1.3數(shù)理邏輯的地位和作用1、計算機科學(xué)的重要的理論基礎(chǔ)之一；2、對數(shù)學(xué)、計算機科學(xué)、人工智能、語言學(xué)、控制論等諸多學(xué)科產(chǎn)生深遠的影響。3、在計算機科學(xué)中的應(yīng)用：軟件、硬件設(shè)計第十六頁，共八十六頁，2022年，8月28日16第2章命題邏輯2.1命題邏輯基本概念

2.2命題邏輯等值演算

2.3范式2.4命題邏輯推理理論

第十七頁，共八十六頁，2022年，8月28日172.1

命題邏輯基本概念

2.1.1命題與聯(lián)結(jié)詞命題與真值(簡單命題,復(fù)合命題)聯(lián)結(jié)詞(?,,,,)

命題公式及其分類命題公式及其賦值真值表命題公式的分類

第十八頁，共八十六頁，2022年，8月28日18§2.1.1命題與聯(lián)結(jié)詞1、命題及相關(guān)概念（1）命題的定義兩者必居其一且只居其一——二值邏輯命題定義的理解：從兩個方面把握這個概念（1）陳述句；（2）真值唯一性（注意：真值可能目前還不知道答案）。命題：一個具有真假意義的陳述句。什么是真值：只包含真/假兩個值的量。T/1—真F/0—假第十九頁，共八十六頁，2022年，8月28日19注意：（1）感嘆句、祈使句、疑問句都不是命題（2）陳述句中的悖論以及判斷結(jié)果不唯一確定的也不是命題第二十頁，共八十六頁，2022年，8月28日20中國的首都在北京。1+1=10請開門！x+y=1明年10月1日是晴天。本命題是假的。李紅既學(xué)英語又學(xué)日語。例1判斷下列個自然語言是否是命題第二十一頁，共八十六頁，2022年，8月28日21（2）幾個基本概念真命題與假命題命題變元與命題常元真命題:真值為真的命題假命題:真值為假的命題若p即可以表示真命題，又可以表示假命題，則稱p為命題變元。T永遠表示真命題，F(xiàn)表示假命題，稱T和F為命題常元。第二十二頁，共八十六頁，2022年，8月28日22例2真命題假命題真值不確定疑問句感嘆句祈使句悖論(1),(2),(5)是命題,(3),(4),(6)~(8)都不是命題真值確定,但未知

下列句子中哪些是命題？并指出命題的真值。(1)北京是中華人民共和國的首都.(2)2+5＝8.(3)x+5＞3.(4)你會開車嗎？(5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請關(guān)上門！(8)我正在說謊話.第二十三頁，共八十六頁，2022年，8月28日23（1）簡單命題與復(fù)合命題（2）聯(lián)結(jié)詞的定義（3）聯(lián)結(jié)詞的優(yōu)先級2.聯(lián)接詞第二十四頁，共八十六頁，2022年，8月28日24（1）簡單命題與復(fù)合命題簡單命題(原子命題):簡單陳述句構(gòu)成的命題。簡單命題的符號化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假復(fù)合命題:由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。

例如如果明天天氣好,我們就出去郊游設(shè)p:明天天氣好,q:我們出去郊游,如果p,則q

又如張三一面喝茶一面看報設(shè)p:張三喝茶,q:張三看報,p并且q第二十五頁，共八十六頁，2022年，8月28日25（2）聯(lián)結(jié)詞的定義否定詞（┐）定義2.1設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞,并規(guī)定p為真當(dāng)且僅當(dāng)p為假。例如p:2是合數(shù),p:2不是合數(shù)。p為假,p為真。第二十六頁，共八十六頁，2022年，8月28日26合取詞（∧

）定義2.2設(shè)p,q為二命題,復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式,記作p∧q,∧稱作合取聯(lián)結(jié)詞,并規(guī)定

p∧q為真當(dāng)且僅當(dāng)p與q同時為真.例如p:2是偶數(shù),q:2是素數(shù),p∧q:表示的含義是2是偶素數(shù)。

因為p為真,q也為真，所以p∧q為真。第二十七頁，共八十六頁，2022年，8月28日27例3

將下列命題符號化.解：記p:王曉用功,q:王曉聰明(1)p∧q(2)p∧q(3)q∧p(4)記r:張輝是三好生,s:王麗是三好生,r∧s(5)簡單命題,記

t:張輝與王麗是同學(xué)(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).第二十八頁，共八十六頁，2022年，8月28日28析取詞（∨）定義2.3設(shè)p、q為命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q,∨稱作析取聯(lián)結(jié)詞,并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假。例如張三和李四至少有一人會英語設(shè)p:張三會英語,q:李四會英語,符號化為p∨q。第二十九頁，共八十六頁，2022年，8月28日29相容或與排斥或析取詞表示的是相容或，即p

和q

均為真時(p∨q)亦為真，而與之對應(yīng)的還有一個是排斥或，它表示的含義是p

和q

不能同時為真。例如這件事由張三和李四中的一人去做設(shè)p:張三做這件事,q:李四做這件事應(yīng)符號化為(p∧

q)∨(p∧q)第三十頁，共八十六頁，2022年，8月28日30例4

將下列命題符號化，并指出其真值解：記p:2是素數(shù),q:3是素數(shù),r:4是素數(shù),s:6是素數(shù)(1)p∨r,(2)

p∨q,(3)r∨s,(4)記t:元元拿一個蘋果,u:元元拿一個梨真值:1真值:1真值:0(t∧u)∨(t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年(v∧w)∨(v∧w)又可形式化為v∨w(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.第三十一頁，共八十六頁，2022年，8月28日31蘊涵詞（）定義2.4設(shè)p,q為二命題,復(fù)合命題“如果p,則q”稱作p與q的蘊涵式,記作pq,并稱p是蘊涵式的前件,q為蘊涵式的后件.稱作蘊涵聯(lián)結(jié)詞,并規(guī)定,pq為假當(dāng)且僅當(dāng)p為真且q為假.例如如果明天天氣好,我們就出去郊游設(shè)p:明天天氣好,q:我們出去郊游,形式化為pq第三十二頁，共八十六頁，2022年，8月28日32蘊涵詞的其它表述方式pq的邏輯關(guān)系:q為p的必要條件,p為q的充分條件?！叭绻鹥,則q”的多種表述方式：若p,就q

只要p,就qp僅當(dāng)q

只有q

才p除非q,才p

除非q,否則非p當(dāng)p為假時，pq為真(不管q為真,還是為假)第三十三頁，共八十六頁，2022年，8月28日33例5

設(shè)p:天冷,q:小王穿羽絨服，將下列命題符號化

注意：

pq與qp

等值（真值相同）pqpqqp或pqpqqp

qppq或qpqp(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.第三十四頁，共八十六頁，2022年，8月28日34等價詞（）定義2.5設(shè)p,q為命題,復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式,記作pq,稱作等價聯(lián)結(jié)詞.并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假。

pq的邏輯關(guān)系:p與q互為充分必要條件例如這件事張三能做好,且只有張三能做好設(shè)p:張三做這件事,q:這件事做好了形式化為:pq第三十五頁，共八十六頁，2022年，8月28日35例6

求下列復(fù)合命題的真值：1011(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽從東方升起.(4)2+2＝5當(dāng)且僅當(dāng)美國位于非洲.第三十六頁，共八十六頁，2022年，8月28日36分析找出簡單命題用字母表示簡單命題用聯(lián)接詞聯(lián)接命題符號命題符號化的一般規(guī)則第三十七頁，共八十六頁，2022年，8月28日37分析找出簡單命題用字母表示簡單命題用聯(lián)接詞聯(lián)接命題符號解令p:我上街

q:我累

r:我去書店看看則可符號化為：（pq)r例7

將下列命題符號化：如果我上街并且我不累，我就去書店看看。簡單命題：我上街。我累。我去書店看看。第三十八頁，共八十六頁，2022年，8月28日38例8試將下列命題符號化：如果你不看電影，那么我也不看電影小王一邊吃飯，一邊看書解:（1）設(shè)p：你看電影，q：我看電影，則：

p

q（2）設(shè)p：小王吃飯，q：小王看書，則：

pq第三十九頁，共八十六頁，2022年，8月28日39（3）聯(lián)結(jié)詞的優(yōu)先級聯(lián)結(jié)詞優(yōu)先級:(),,,,,同級按從左到右的順序進行第四十頁，共八十六頁，2022年，8月28日401、分析下列各命題的真值（1）2+2=4當(dāng)且僅當(dāng)3是奇數(shù)（2）2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)（3）2+2≠4當(dāng)且僅當(dāng)3是奇數(shù)（4）2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù)2、將下列命題符號化（1）小王是游泳冠軍或者百米賽跑冠軍（2）小王現(xiàn)在在宿舍或者在圖書館（3）選小王或者小李中的一人當(dāng)班長（4）如果我上街，我就去書店看看，除非我很累課堂練習(xí)（1）第四十一頁，共八十六頁，2022年，8月28日41課堂練習(xí)（2）3、將下列命題符號化（1）李平既聰明又用功（2）李平雖然聰明，但不用功（3）李平不但聰明，而且用功（4）李平不是不聰明，而是不用功4、將下列命題符號化（1）只要不下雨，我就騎自行車上班（2）只有不下雨，我才騎自行車上班（3）若2+2=4，則太陽從東方升起（4）若2+2≠4,則太陽從東方升起第四十二頁，共八十六頁，2022年，8月28日42§2.1.2合式公式及其分類1.命題語言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分類第四十三頁，共八十六頁，2022年，8月28日431.命題語言的字母表命題語言的字母表：命題常元：T,F(或1，0)命題變元：p1,p2,…,pn聯(lián)接詞：┐，∧，∨，→，輔助符號：（）第四十四頁，共八十六頁，2022年，8月28日44（1）合式公式(命題公式,公式)的定義定義2.6

合式公式遞歸定義如下：(1)單個命題常項或變項是合式公式，并稱作原子合式公式；(2)若A是合式公式,則(A)也是合式公式；(3)若A,B是合式公式,則(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地應(yīng)用(1)~(3)形成的符號串才是合式公式。2、合式公式的基本概念說明:(1)元語言符號與對象語言符號(2)在不影響運算順序時,括號可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r第四十五頁，共八十六頁，2022年，8月28日45（2）合式公式的層次定義2.7(1)單個命題變項或命題常項是0層公式(2)稱A是n+1(n≥0)層公式是指下面情況之一：(a)A=B,B是n層公式(b)A=BC,其中B,C分別為i層和j層公式,且

n=max(i,j)(c)A=BC,其中B,C的層次及n同(b)(d)A=BC,其中B,C的層次及n同(b)(e)A=BC,其中B,C的層次及n同(b)例如

p0層

p1層

pq2層(pq)r3層

((pq)r)(rs)4層第四十六頁，共八十六頁，2022年，8月28日46（3）公式的賦值定義2.8設(shè)p1,p2,…,pn是出現(xiàn)在公式A中全部的命題變項，給p1,p2,…,pn指定一組真值，稱為對A的一個賦值或解釋。使公式為真的賦值稱作成真賦值,使公式為假的賦值稱作成假賦值。說明:(1)賦值記作=12…n，其中i=0或1，諸i之間不加標(biāo)點符號；(2)通常賦值與命題變項之間按下標(biāo)或字母順序?qū)?yīng),即：當(dāng)A的全部命題變項為p1,p2,…,pn時,給A賦值12…n是指p1=1,p2=2,…,pn=n;當(dāng)A的全部命題變項為p,q,r,…時,給A賦值123…是指p=1,q=2,r=3,…第四十七頁，共八十六頁，2022年，8月28日47實例例8

公式A=(

p1

p2p3)(p1

p2)000是成真賦值,001是成假賦值公式B=(pq)r000是成假賦值,001是成真賦值第四十八頁，共八十六頁，2022年，8月28日483、真值表真值表:命題公式在所有可能的賦值下的取值的列表。含n個變項的公式有2n個賦值用0或1表示公式中命題變元的取值，并依據(jù)聯(lián)結(jié)詞的邏輯規(guī)則計算出復(fù)合命題（公式）的真值，用一個對應(yīng)表表示的一種方法。第四十九頁，共八十六頁，2022年，8月28日49基本復(fù)合命題真值表匯總

pq

pp∧qp∨qpqpq0010011011011010001001101111第五十頁，共八十六頁，2022年，8月28日50pqqp

(qp)q

(qp)qp

00011011

1011

0001

1111例9

給出公式的真值表(1)

(qp)qp；(2)(pq)q；

(3)(pq)r.例9第五十一頁，共八十六頁，2022年，8月28日51pqppq(pq)(pq)q00011011

1100110100100000(2)(pq)q第五十二頁，共八十六頁，2022年，8月28日52pqrpq

r

(pq)r

000001010011100101110111

00111111

10101010

11101010(3)(pq)r第五十三頁，共八十六頁，2022年，8月28日534、命題公式的分類重言式(永真式):無成假賦值的命題公式矛盾式(永假式):無成真賦值的命題公式可滿足式:非矛盾式的命題公式注意:重言式是可滿足式，但反之不真.例如上例中(1)(qp)qp為重言式(2)(pq)q為矛盾式(3)(pq)r為非重言式的可滿足式第五十四頁，共八十六頁，2022年，8月28日542、判斷下列命題公式的類型（1）（2）課堂練習(xí)1、構(gòu)造下列命題公式的真值表（1）（2）第五十五頁，共八十六頁，2022年，8月28日552.2命題邏輯等值演算2.2.1等值式與等值演算等值式基本等值式等值演算2.2.2聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞第五十六頁，共八十六頁，2022年，8月28日56§2.2.1等值式與等值演算1、等值式的定義定義2.11

若等價式AB是永真式,則稱A與B等值,記作AB,并稱AB是等值式。第五十七頁，共八十六頁，2022年，8月28日57(1)是元語言符號,不要混同于和=。(2)A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同,即A與B有相同的真值表。(3)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項稱作B的啞元.啞元的值不影響命題公式的真值。說明第五十八頁，共八十六頁，2022年，8月28日582、性質(zhì)(1)AA(2)若AB，則B

A(3)若AB且B

C，則A

C第五十九頁，共八十六頁，2022年，8月28日593、真值表法判斷公式是否等值結(jié)論:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)00110111011010011001100111001001例1

判斷(pq)與

pq

是否等值解第六十頁，共八十六頁，2022年，8月28日60

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)與(pq)r等值,但與(pq)r不等值例2判斷下述3個公式之間的等值關(guān)系:

p(qr),(pq)r,(pq)r解第六十一頁，共八十六頁，2022年，8月28日614、基本等值式（1）雙重否定律：（2）等冪律：第六十二頁，共八十六頁，2022年，8月28日62（3）交換律：（4）結(jié)合律：（5）分配律：（6）德·摩根定律：第六十三頁，共八十六頁，2022年，8月28日63（7）吸收律：（8）蘊含等值式：（9）等價等值式：第六十四頁，共八十六頁，2022年，8月28日64（10）零律：（11）同一律：（12）排中律：第六十五頁，共八十六頁，2022年，8月28日65（13）矛盾律：（14）等價否定等值式：（15）歸謬律：（16）假言易位：第六十六頁，共八十六頁，2022年，8月28日66

(1)代入規(guī)則

代入規(guī)則：對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。例如F=（pq）?（qp）是重言式，若用公式r∧s代換命題變元p得公式

F1=（（r∧s）q）?（q（r∧s）），F(xiàn)1仍是重言式。注意：因為AB當(dāng)且僅當(dāng)A?B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。5、等值演算第六十七頁，共八十六頁，2022年，8月28日67(2)

置換規(guī)則

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

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

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

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

第六十八頁，共八十六頁，2022年，8月28日68(3)

等值演算

等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。例3證明p(qr)(pq)r證p(qr)p(qr)（蘊涵等值式）(pq)r（結(jié)合律）(pq)r（德摩根律）(pq)r（蘊涵等值式）第六十九頁，共八十六頁，2022年，8月28日69

例4：證明（┐A→┐B)→(B→A)是永真式。證明:∵(┐A→┐B)→(B→A)蘊涵等值式┐(┐┐A∨┐B)∨(┐B∨A)德·摩根律、雙重否定律(┐A∧B)∨(┐B∨A)分配律(┐A∨┐B∨A)∧(B∨┐B∨A)交換律、結(jié)合律、補余律

T

∴（┐A→┐B)→(B→A)是永真式第七十頁，共八十六頁，2022年，8月28日70（同一律）（排中律）（分配律）證明

例5證：第七十一頁，共八十六頁，2022年，8月28日71例6

用等值演算法判斷下列公式的類型(1)q(pq)

解q(pq)

q(pq)（蘊涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結(jié)合律）

p0（矛盾律）

0（零律）該式為矛盾式.第七十二頁，共八十六頁，2022年，8月28日72例6(續(xù))(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蘊涵等值式）

(pq)(pq)（交換律）

1該式為重言式.第七十三頁，共八十六頁，2022年，8月28日73例6(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié):A為矛盾式當(dāng)且僅當(dāng)A0;A為重言式當(dāng)且僅當(dāng)A1說明:演算步驟不惟一,應(yīng)盡量使演算短些第七十四頁，共八十六頁，2022年，8月28日74例7：應(yīng)用題某勘探隊有3名隊員，有一天取得一塊礦樣，3人的判斷如下：甲說：這不是鐵，也不是銅乙說：這不是鐵，是錫丙說：這不是錫，是鐵經(jīng)過實驗鑒定后發(fā)現(xiàn)，其中一人2個判斷都是正確的，一人判斷對了一半，另外一個人全錯了。根據(jù)以上情況判斷礦樣的種類。第七十五頁，共八十六頁，2022年，8月28日75解：設(shè)p：礦樣為鐵，q：礦樣為銅，r：礦樣為錫，則可得：第七十六頁，共八十六頁，2022年，8月28日76第七十七頁，共八十六頁，2022年，8月28日77第七十八頁，共八十六頁，2022年，8月28日78等值演算不能直接證明兩個公式不等值.證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.例8

證明:p(qr)(pq)r方法一真值表法方法二觀察法.容易看出000使左邊成真,使右邊成假.方法三先用等值演算化簡公式,再觀察.第七十九頁，共八十六頁，2022年，8月28日792、證明3、證明是永真式。課堂練習(xí)1、證明用等值演算證明：第八十頁，共八十六頁，2022年，8月28日80§2.2.2聯(lián)結(jié)詞完備集1、真值函數(shù)n元真值函數(shù)共有個每一個命題公式對應(yīng)于一個真值函數(shù)每一個真值函數(shù)對應(yīng)無窮多個命題公式1元真值函數(shù)

p

000111