離散數(shù)學(xué)第一章

1、,,緒論 Preface,,,,,一、什么是離散數(shù)學(xué),二、離散數(shù)學(xué)與計(jì)算機(jī)科學(xué),三、離散數(shù)學(xué)研究的范圍,四、離散數(shù)學(xué)課程的任務(wù),現(xiàn)代數(shù)學(xué)的重要分支。,緒論P(yáng)RAFACE,兩個(gè)特征,,一、什么是離散數(shù)學(xué),,,,,,可計(jì)算性（能行性）,離散性,,研究離散量的結(jié)構(gòu)及離散量之間關(guān)系。,典型問題：蘇格拉底三段論、信息檢索周游世界問題、最短路徑。。。,緒論P(yáng)RAFACE,計(jì)算機(jī)只能處理離散性問題 用計(jì)算機(jī)求解任何問題不僅要知道 解的存在，更

2、要知道解的能行性。 計(jì)算機(jī)科學(xué)的理論基礎(chǔ)和工具。 信息時(shí)代的數(shù)學(xué)基礎(chǔ)。,二、離散數(shù)學(xué)與計(jì)算機(jī)科學(xué),,,,,,,數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論、　 概率論、可計(jì)算性理論、組合數(shù)學(xué)、　 自動(dòng)機(jī)理論、擬陣論等等。,三、離散數(shù)學(xué)研究的范圍,,,,,,緒論P(yáng)RAFACE,,,,,,緒論P(yáng)RAFACE,四、離散數(shù)學(xué)課程的任務(wù),２、提高邏輯推理能力、抽象思維能力 和歸納構(gòu)造能力。,１、掌握離散數(shù)學(xué)的基本理論和方法,

3、 為后繼課程準(zhǔn)備 必要的數(shù)學(xué)工具。,是計(jì)算機(jī)專業(yè)的核心主干課程,后繼課程：數(shù)據(jù)結(jié)構(gòu)、數(shù)字邏輯、算法 編譯原理、數(shù)據(jù)庫、人工智能等。,,,,,,緒論P(yáng)RAFACE,,,,,,緒論P(yáng)RAFACE,離散數(shù)學(xué)學(xué)習(xí)秘訣,1、堅(jiān)持聽課 聽君一席話勝讀十年書,2、獨(dú)立思考 人類一思考，上帝就發(fā)笑,3、完成作業(yè) 入寶山空手而歸,,,,,,,,平時(shí)成績20％(考勤,作業(yè),測驗(yàn))

4、 期末閉卷考試 80 ％,,教學(xué)安排,五教1109 周一下午 2: 00,,作業(yè)和測驗(yàn)：每周第一次上課時(shí)交作業(yè). 每章均有習(xí)題課和測驗(yàn). 期中考試第9周.,,,考核辦法:,答疑地點(diǎn):,“離散數(shù)學(xué)”耿素云,屈婉玲,北京大學(xué)出版社 “離散數(shù)學(xué)及其應(yīng)用” (美) kenneth H.Rosen 機(jī)械工業(yè)出版社,參考書目,,,,,,緒論P(yáng)RAFACE,第四篇

5、 圖論,1.命題邏輯,2.謂詞邏輯,3.集合與關(guān)系,4.函數(shù),6.布爾代數(shù),5.代數(shù)結(jié)構(gòu),目 錄,,,,７.圖論,第一篇 數(shù)理邏輯,第二篇 集合論,第三篇 代數(shù)結(jié)構(gòu),,,,,,緒 論,第一篇 數(shù) 理 邏 輯Mathematics Logic,,,,,又稱符號(hào)邏輯,是用數(shù)學(xué)方法研究形式邏輯（演繹和推理）的一門學(xué)問。,數(shù)理邏輯,13,,,,,,,邏輯LOGIC—是研究思維規(guī)律的科學(xué)。 1.辯

6、證邏輯：屬哲學(xué)范疇，以認(rèn)識(shí)論的世界觀為基 礎(chǔ)，是辯證法研究的對(duì)象。 例如：用全面的和發(fā)展的觀點(diǎn)觀察事物； 具體問題具體分析； 實(shí)踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。 2.形式邏輯：研究思維形式和初步規(guī)律(推理)的科學(xué) 例如：人總是要死的， 蘇格拉

7、底是人， 所以，蘇格拉底是要死的,數(shù)理邏輯,14,,,,,,,人的思維過程: 概念 ? 判斷 ? 推理 推理：是由若干個(gè)已知的判斷(前提)，推出新的判斷 (結(jié)論)的思維過程。,數(shù)理邏輯,,類比推理：由個(gè)別事實(shí)推出個(gè)別結(jié)論。 如：地球上有空氣、水，地球上有生物。 火星上有空氣、水。 ? 火星上有生物。歸

8、納推理：由若干個(gè)別事實(shí)推出一般結(jié)論。 如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電… ? 一切金屬都導(dǎo)電。演繹推理：由一般規(guī)律推出個(gè)別事實(shí)。 如：所有金屬都導(dǎo)電。 銅是金屬。 ?銅能導(dǎo)電,形式邏輯主要是研究演繹推理的,,,,,,,蘇格拉底三段論：,已知判斷,推出的判斷,,,推理,所以，蘇格拉底是要死的。,又如：,前提,結(jié)論,自然數(shù)是整數(shù)，２是自然數(shù)，,所以，２是整數(shù)。,蘇格拉底是人，,人總是要死的

9、，,推理形式： 凡A是X, a是A, 所以, a是 X。,數(shù)理邏輯,,,,,,例如：,如果今天出太陽,我就進(jìn)城,今天出了太陽，,如果狗有翅膀,狗會(huì)飛上天,狗有了翅膀,,又例如：,,所以我進(jìn)城了.,推理正確，結(jié)論有效,所以狗飛上了天.,,推理正確，結(jié)論有效,,(T),(T),(F),(推理錯(cuò)誤，結(jié)論無效),若n是素?cái)?shù),則n是整數(shù), 6是整數(shù), 所以, 6是素?cái)?shù).,數(shù)理邏輯,17,,數(shù)理邏輯是用數(shù)學(xué)

10、方法研究形式邏輯（演繹和推理）的一門學(xué)問。通過引入一套符號(hào)系統(tǒng),將形式邏輯中用自然語言描述的概念、判斷及判斷之間的聯(lián)系等符號(hào)化，并借助數(shù)學(xué)方法把判斷之間的邏輯關(guān)系及推理過程轉(zhuǎn)換成符號(hào)運(yùn)算，從而將形式邏輯的推理系統(tǒng)變成了嚴(yán)密精確、形式化、公理化的數(shù)學(xué)系統(tǒng)?！　?shù)理邏輯在計(jì)算機(jī)方面的直接應(yīng)用主要有程序設(shè)計(jì)、定理的機(jī)器證明,人工智能等。,,,,,,數(shù)理邏輯,18,邏輯演算(logical calculus）,,,,,,公理化集合論 (S

11、et theory),證明論(poof theory）,遞歸論(recursive theory）,數(shù)理邏輯包括五個(gè)部分：,模型論( model theoy ）,又稱數(shù)理邏輯基礎(chǔ)包括命題演算、謂詞演算和應(yīng)用運(yùn)算討論邏輯概念和一般性的推理規(guī)律。,數(shù)理邏輯,第四篇 圖論,1.命題邏輯,2.謂詞邏輯,3.集合與關(guān)系,4.函數(shù),6.布爾代數(shù),5.代數(shù)結(jié)構(gòu),目 錄,,,,７.圖論,第一篇 數(shù)理邏輯,第二篇 集合論,第三篇 代數(shù)結(jié)構(gòu),,,,,,緒

12、論,命 題 邏 輯,,,,,Propositional Logic,第一章,,,以命題為研究對(duì)象，研究命題的邏輯結(jié)構(gòu)及命題間的推理關(guān)系。,1-1 命題及其表示,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,1-4 等價(jià)公式,1-1 命題及其表示,命題邏輯,,,,,,本節(jié)主要討論四個(gè)問題：命題如何定義？命題如何取值

13、？命題如何分類？命題如何符號(hào)化？,命題：,命題邏輯 >命題及其表示,1-1命題及其表示,,,,,,真命題:命題含義為真,記作T.亦稱其真值為T;,命題是具有唯一確定真值的陳述句.,假命題:命題含義為假,記作F.亦稱其真值為F;,{T, F }統(tǒng)稱為命題的真值。,1. 命題（Proposition）,每個(gè)能表達(dá)判斷的陳述句稱之。,,一切沒有判斷內(nèi)容的句子均非命題.,,,“100是個(gè)很大的數(shù)”是命題嗎？,例 天是藍(lán)的。太陽從西方

14、升起。,命題邏輯 >命題及其表示,,,,,,(3) 1+101=110.,(4) 別的星球上有生物.,(5) 全體立正!,(6) 明天是否開會(huì)?,(7) 天氣多好啊!,(8) 我正在說謊.,(命題,T),(命題,F),(陳述句,但不是命題),(是命題),(感嘆句,不是命題),(悖論,不是命題),(疑問句,不是命題),(祈使句,不是命題),(1) 中國人民是偉大的.,(2) 雪是黑的.,補(bǔ)例：今天早上又刮風(fēng)又下雨.,(復(fù)合命題),命

15、題邏輯 >命題及其表示,,,,,,原子命題:,復(fù)合命題:,簡單陳述句表達(dá)的判斷。,復(fù)合陳述句表達(dá)的判斷。即由連接詞、標(biāo)點(diǎn)及原子命題復(fù)合而成的命題。,2.命題的分類,用A，B，...P，Q...表示,稱為命題標(biāo)識(shí)符。,(9) 我學(xué)英語或者我學(xué)日語.,(10) 如果天氣好,我去散步.,(復(fù)合命題),(復(fù)合命題),,,,,復(fù)合命題的真值由各原子命題的真值及連接詞的含義確定。,,,,,,命題常量: 命題標(biāo)識(shí)符代表某一確定的命題。命題變

16、元:命題標(biāo)識(shí)符代表任意一個(gè)命題.變?cè)娜≈捣秶?T,F).變?cè)闹概?當(dāng)命題變?cè)惶囟}代入,成為具有確定真值的命題時(shí)。稱對(duì)命題變?cè)闹概?。原子變?cè)好}變?cè)碓用}時(shí)。,命題邏輯 >命題及其表示,名詞術(shù)語,27,1-1 命題及其表示,命題邏輯,,,,,,回答問題：命題如何定義？命題如何取值？命題如何分類？命題如何表示？,28,1-1 命題及其表示,命題邏輯,,,,,,判斷：X+y<52+2=4張華

17、不是計(jì)算機(jī)系學(xué)生張三和李四都是大學(xué)生如果太陽從西方升起，則 人總是要死的燕子飛回北方，春天來了,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,1-4 等價(jià)公式,30,1-1 命題及其表示,命題邏輯,,,,,,本節(jié)將討論問題：什么是邏輯連接詞？有哪些基本邏輯連接詞？如何使用原子命題和連接詞

18、 將命題符號(hào)化？,,定義1-2.1 設(shè)P為一命題,P的否定是一個(gè)新的命題,記作?P。若P為T,?P為F,若P為F,?P為T.,(1) 否定(Negation) ?,即：,1-2 邏輯連接詞,,,,,,把幾個(gè)命題連接起來構(gòu)成復(fù)合命題的詞.,與日常用語中的‘不…’, ‘非…’,否…‘等含義相當(dāng).,?P為T iff P為F,命題邏輯 > 邏輯連接詞,,,,,,1.并非所有的自然數(shù)是偶數(shù).?,例如 設(shè)P:所有的自然數(shù)是偶數(shù).,

19、其否命題?P為:,例如,塑料是金屬.,(Q),(?Q),塑料不是金屬.,塑料是金屬.,(?Q),(Q),否定是個(gè)相對(duì)概念.,,,塑料不是金屬.,2.所有的自然數(shù)都不是偶數(shù).?,是對(duì)整個(gè)命題的否定,而不是對(duì)句子成份的否定.,,,,,,命題邏輯 > 邏輯連接詞,定義 1-2.2 兩個(gè)命題P和Q的合取是一個(gè)復(fù)合命題,記作P∧Q。 當(dāng)且僅當(dāng)P、Q同時(shí)為T時(shí),P∧Q為T,在其他情況下,P∧Q的真值都是F。,(2) 合取(Conjunc

20、tion) ∧,即,,,,,,與日常用語中的 ‘并且’, ‘以及’,‘和’,‘不僅...而且’‘雖然…但是’等含義相當(dāng).,P∧Q為T,iff P與Q均為T.,命題邏輯 > 邏輯連接詞,,,,,,新命題 P?Q,P: 我們?nèi)タ措娪癚: 房間里有十張桌子,,命題,,,例1,P: 張明與張亮是兄弟,原子命題,例2,不是連接詞,,只考慮命題與命題之間的形式關(guān)系,不顧及句子的含義.,我們?nèi)タ措娪扒曳块g里有十張桌子.,命題邏輯 >

21、; 邏輯連接詞,,定義 1-2.3 兩個(gè)命題P和Q的析取是一個(gè)復(fù)合命題,記作P∨Q。當(dāng)且僅當(dāng)P、Q同時(shí)為F時(shí),P∨Q的真值為F,否則P∨Q的真值為T。,(3) 析取(Disjunction)∨,即：,,,,,,與日常用語中的 ‘可兼或’含義相當(dāng)。,P∨Q為F, iff P、Q均F,命題邏輯 > 邏輯連接詞,,,,,,今晚我在家看電視,或去劇場看電影.,,例1,例2,他可能是100米或200米跑的冠軍.,例3,他昨

22、天作了20道或30道習(xí)題.,異或,可兼或?,不是連接詞,,,,命題邏輯 > 邏輯連接詞,,即:,定義 1-2.４ 給定兩個(gè)命題P和Q,其條件命題是一個(gè)復(fù)合命題,記作P→Q,讀作“若P則Q”。當(dāng)且僅當(dāng)P的真值為T, Q的真值為F時(shí), P→Q的真值為F。否則P→Q的真值為T。我們稱P為前件，Q為后件。,,,,,,(4) 條件（Implication） →,與日常用語中的 ‘如果…則’,‘必須…以便’,等含義相當(dāng)。,P→Q為F, if

23、f P為T、Q為F。,命題邏輯 > 邏輯連接詞,,,,,,例1 如果某動(dòng)物是哺乳動(dòng)物,則它必胎生.,解:,設(shè) P: 某動(dòng)物是哺乳動(dòng)物 Q: 某動(dòng)物是胎生,符號(hào)化為: P? Q,例2 如果太陽從東方升起,你就可以長生不老.,解:,設(shè) P: 太陽從東方升起 Q: 你可以長生不老.,符號(hào)化為: P? Q,,有因果關(guān)系(T),,無因果關(guān)系(F),前件是后件成立的充分條件;,后件是前件成立的必要條件.,,西方

24、?,命題邏輯 > 邏輯連接詞,,定義 1-2.5 給定命題P和Q,其復(fù)合命題P?Q稱作雙條件命題,讀作“P當(dāng)且僅當(dāng)Q”,當(dāng)P和Q的真值相同時(shí),P?Q的真值為T,否則P?Q的真值為F。,(5) 雙條件(Equivalence) ?,即：,,,,,,與日常用語中的‘當(dāng)且僅當(dāng)’,‘充分必要’,‘只有且僅有…才能’,‘除非’等含義相當(dāng)。,P ?Q為T, iff P與Q同T或同F(xiàn)。,命題邏輯 > 邏輯連接詞,,例1 兩個(gè)三角形

25、全等,Iff 它們的三組對(duì)應(yīng)邊相等.,,,,,,例3 2+2=4,當(dāng)且僅當(dāng)雪是白的.,例2 燕子飛回北方,春天來了.,,P,,Q,符號(hào)化為:,,P,,,P,,Q,Q,,命題邏輯 > 邏輯連接詞,“P當(dāng)且僅當(dāng)Q” 等價(jià)于“P當(dāng) Q“ 且 “P僅當(dāng)Q ”,P ? Q,,,,,,命題邏輯 > 邏輯連接詞,基本連接詞的真值表,任意兩個(gè)命題均可用邏輯連接詞連接起來。,復(fù)合命題的真值必須按照邏輯連接詞的定義判定，不能按照自然連接詞的語

26、義去理解。,,,,,,命題符號(hào)化 用原子命題符號(hào)及連接詞組成的符號(hào)串表示復(fù)合命題.,命題邏輯 > 邏輯連接詞,例 題,1.判斷是否復(fù)合命題(看有幾個(gè)主謂結(jié)構(gòu)或連接詞).2.對(duì)復(fù)合命題找出每個(gè)原子命題,分別用不同符號(hào)表示.3.分析原子命題之間的關(guān)系,確定連接詞.,命題符號(hào)化的一般策略:,1.他雖有理論知識(shí),但無實(shí)踐知識(shí).,2. 鐵和氧化合, 但 鐵和氮不化合.,3.他是三好學(xué)生,當(dāng)且僅當(dāng)他學(xué)習(xí)好、工作好、身體好。,4 上海到北

27、京的14列車是下午五點(diǎn)半或六點(diǎn)半開。,5.張三或李四都可以作這件事。,43,1-1 命題及其表示,命題邏輯,,,,,,回答問題：什么是邏輯連接詞？有哪些基本邏輯連接詞？如何使用原子命題和連接詞 將命題符號(hào)化？,,,,,,命題邏輯 > 邏輯連接詞,課堂練習(xí),1. X<4 是命題.( )2. “如果太陽從西方升起,則雪是白的“ 是假命題.( )3. “明天我去看電影”不是命題。（ ）4. “僅當(dāng)你走（ p

28、）我留下（ q）?！狈?hào)化為（ ）A. p? q B. q?p C. p ?q D. p?q5.設(shè) p:天下雨, q: 他有時(shí)間, r: 他進(jìn)城, 則命題 “如果天不下雨且他有時(shí)間,他就進(jìn)城”符號(hào)化為 ( ) A. ?p?q?r B. ?p?q?r C. ?p?q?r D. ?p?q?r

29、 6. x:=1 If 2+2=4 then x:=x+1,,,,,,,命題邏輯 > 邏輯連接詞,作 業(yè),1-1， 1-2 （1），（3），（5）1-3 （5），（7）,本節(jié)重點(diǎn)掌握的概念: 命題，連接詞。本節(jié)重點(diǎn)掌握的方法: 命題符號(hào)化.,,,1-3 命題公式與賦值,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集

30、,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,1-4 等價(jià)公式,1-3 命題公式與賦值,定義1-3.1 命題演算的合式公式(wff),規(guī)定為:(1) 單個(gè)命題變?cè)旧硎莣ff。(2) 如果A是wff,那么?A是wff。(3) 如果A和B是wff,那么(A∧B),(A∨B),(A→B) 和(A?B)都是wff 。(4) 當(dāng)且僅當(dāng)有限次應(yīng)用(1),(2),(3)所得到的包 含命題變

31、元,聯(lián)結(jié)詞和括號(hào)的符號(hào)串是wff.,命題邏輯 > 命題公式與賦值,1. 命題公式,合式公式是對(duì)命題形式的抽象描述，反映了復(fù)合命題的結(jié)構(gòu)特征，故可將對(duì)復(fù)合命題的研究化為對(duì)合式公式的研究。,公式中的命題變?cè)Q為分量,含n個(gè)分量的公式稱為n元公式.,,,,,,命題邏輯 >命題公式與賦值,(2). (P?(P?Q )),(3). ( P),(4). (P?Q ), (P?Q)?Q),(5). P?Q,(1). ?( P?

32、Q ),(1),×,×,?,--(2),--(3),(1),--(3),--(3),例如:,二元公式,二元公式,(多括號(hào)),(非法字符),1.公式最外層的括號(hào)可省略.2.規(guī)定運(yùn)算優(yōu)先級(jí)為?,?,?,?,? ,則其中的括 號(hào)可省略.3.同級(jí)的從左至右進(jìn)行時(shí),則其中的括號(hào)可省略.,命題公式的簡化規(guī)則:,命題邏輯 >命題公式與賦值,(P?(P?Q )),((( P? Q )? R)?Q),化簡為:,P?(P?

33、Q ) 再化簡：P?P?Q,例如:,化簡為:,(( P? Q) ? R)?Q,(P? Q ? R)?Q,化簡為:,,,,,,設(shè)P1,P2,...Pn是命題公式A中出現(xiàn)的所有分量，為P1,P2,...Pn指定一組真值稱為對(duì)公式A的賦值，若指定一組真值使A成為真命題，則這組真值稱為A的成真賦值；否則為A的成假賦值。,2.命題公式的賦值,P?( Q ? R )為三元公式,例:,若取 P= F, Q= T, R= F,,則P?(Q?R)= F

34、?(T?F)=,若取賦值為110,則P?(Q?R)=1?(1?0)=,為簡便起見可將這組賦值表示為一個(gè)01序列:010,該公式共有多少種不同賦值?,T,(成真賦值),0,(成假賦值),命題邏輯 >命題公式與賦值,真值表:將公式的所有不同賦值及對(duì)應(yīng)的取值情況匯列成表.,,,,,,,1.將wff中出現(xiàn)的所有變?cè)错樞蛞灰涣谐?,3.按所有變?cè)≈档母鞣N組合計(jì)算各分子式最后一列 即為原式的取值情況。,例 題,,如果X是wff的一部分

35、且X本身也是一個(gè)wff, 稱之.,含有n個(gè)不同變?cè)墓接?個(gè)不同賦值.,命題邏輯 >命題公式與賦值,列真值表步驟,1.構(gòu)造? P ? Q 真值表.,2.構(gòu)造( P? Q ) ? ? P 真值表.,4.構(gòu)造P?( Q ? R )真值表.,2.按運(yùn)算優(yōu)先級(jí)的次序,列出各子公式,最后一列即為原式,3.構(gòu)造?(P? Q )?(? P ? ? Q) 真值表.,(3).含有n個(gè)命題變?cè)拿}公式共有 種賦值.,(1).有些公式在某些

36、賦值下為真,某些賦值下為假,這些 公式稱為可滿足的.,由真值表得命題公式的一些性質(zhì):,,,,,,(2).有些公式,無論命題變?cè)骱畏N指派其值永真(或永 假),這些公式稱為永真(或永假)式.記作T(或F).,(4).兩個(gè)不同的命題公式可有相同的真值,稱其為等價(jià).,命題邏輯 >命題公式與賦值,,判定一個(gè)命題公式是永真、永假還是可滿足的稱為判定公式的類型。,永真式和永假式與賦值無關(guān)，僅與命題公式的形式結(jié)構(gòu)有關(guān)。是命題邏

37、輯研究的目標(biāo)。,什么是命題公式？什么是命題公式的賦值？含有n個(gè)命題變?cè)拿}公式共有 種賦值？如何求出命題公式的所有取值？命題公式有哪幾種類型？命題公式的類型如何判斷？如何判斷兩個(gè)命題公式等價(jià)？,,,,,,回答問題：,命題邏輯 >命題公式與賦值,,,,,,命題邏輯 >命題公式與賦值,1-3 （1）（a），（c） （5），（7）,作 業(yè),本節(jié)重點(diǎn)掌握的概念: 命題公式本節(jié)重點(diǎn)掌

38、握的方法: 列真值表,,,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-4 等價(jià)公式,1-5 重言式,1-6 連接詞的全功能集,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,,,,,,1-4 等價(jià)公式,定義1-4.2 設(shè)兩個(gè)命題公式A和B有相同的原子變?cè)狿1,P2,…,Pn,若對(duì)P1,P2,…,Pn任一組真值指派A和B的真值都相同,則稱A和B是等價(jià)的或邏輯相等。記作A?B。,命題邏輯 >等價(jià)

39、公式,?不是連接詞。,含有n個(gè)分量P1,P2,…,Pn的命題公式可有無窮多個(gè), 但互不等價(jià)的公式只有_____個(gè).,22n,如何判定兩公式等價(jià)?,A?B??(?A??B),連接詞的化歸公式,A?B??A?B,A?B?(A?B)?(B?A),?(?A?B)?(?B?A),?(A?B)?(?A??B),A?B??(?A??B),命題邏輯 >等價(jià)公式,常用命題基本公式 表1-4.8,,命題公式A和B 等價(jià)的判定:,真值表法:比較A,B

40、真值表的最后一列.,等價(jià)演算:利用基本公式、等價(jià)的性質(zhì) 和 置換定理，推演出其他等價(jià)式.,P15 例 題5,,P15 例 題6,證明 P?Q ?(P?Q)?(Q?P),驗(yàn)證吸收律 P? (P ?Q ) ?P, P? (P?Q )?P,,,,,,定理1-4.1（置換定理）設(shè)X是合式公式A的子公式,且X?Y,如果將A中的X用Y來置換,所得到的公式B與A等價(jià),即A?B。,例 題,命題邏輯 >等價(jià)公式,等價(jià)的性質(zhì),(1).A?A,(

41、2).若A?B,則B?A.,(3).若A?B,且B?C，則A?C,（自反性）,（對(duì)稱性）,（傳遞性）,,證明 1. ( P? Q ) ?(P ?? Q) ? P,2. P?(Q?R)?Q?(P?R) ??R?(Q ??P),3.P? (P ?Q ) ?P, P? (P?Q )?P,,,,,,命題邏輯 >等價(jià)公式,回答問題1 互不等價(jià)的n元公式有——個(gè)？2 等價(jià)的性質(zhì)有哪些？3

42、 什么是邏輯演算？4 判定兩公式等價(jià)有哪幾種方法？,,,,,,命題邏輯 >等價(jià)公式,1. p?q??r 的不同賦值有______個(gè)。2.命題公式p?q??r 的成假賦值是__________.3.命題公式p?(p?q)的類型是____________.,,課堂練習(xí),,,,,,命題邏輯 >等價(jià)公式,作 業(yè),1-4 （1）（a），（c） （7） （a），（c），（g） （8）

43、 （9）,本節(jié)重點(diǎn)掌握的概念: 等價(jià)式本節(jié)重點(diǎn)掌握的方法: 等價(jià)演算,,,1-5 重言式,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,1-4 等價(jià)公式,定義1-5.1、定義1-5.2　 給定一命題公式,若無論對(duì)分量作怎樣的指派(賦值),其對(duì)應(yīng)的真值永為T(永為F),則稱該命題公式為永真式(永假式)

44、,記作T (F).,1-5 永真式(重言式),命題邏輯 >重言式與蘊(yùn)含式,真值表法 : 公式A的真值表最后一列均為T(F). 利用等價(jià)演算: 公式 A為永真式, 即 A?T . 公式 A 為永假式, 即 A?F.,永真式(永假式)的判定,證明: ?P?( P ? Q ) 是永真式.,例 題,判定一命題公式是永真（永假），還是可滿足的稱為命題公式的判定問題。,證明: ( P ?

45、( P ? Q ) )?Q 是永真式.,利用代入定理可判定某些永真或永假式.,,,,,,定理1-5.2 (代入定理) 一個(gè)重言式,對(duì)同一分量都用任何合式公式置換,結(jié)果仍為一重言式。,代入定理與置換定理(定理1-4.1)的區(qū)別:,(2)代入必須取代該命題變?cè)乃谐霈F(xiàn),置換則不一定 取代分子公式的所有出現(xiàn).,(3)可用任意公式取代變?cè)?而只能用等價(jià)的公式置換分 子公式.,(1)代入是對(duì)變?cè)M(jìn)行取代,置換是對(duì)分子公式

46、進(jìn)行取代;,P20 例題1,命題邏輯 >重言式與蘊(yùn)含式,定理1-5.1 重言式的合取或析取,仍是重言式。,證明((P?S)?R)??((P?S)?R)為重言式,,,,,,定理1-5.3 設(shè)A、B為兩個(gè)命題公式,A?B 當(dāng)且僅當(dāng) A?B 為一個(gè)重言式。,命題邏輯 >重言式與蘊(yùn)含式,要證 (?( P?Q )? ?P? Q)?(?P?Q) 為重言式,例,即證明 (?( P?Q ) ? ? P? Q )? (? P? Q

47、) ?T只需證 ?( P?Q ) ? ?P? Q ? ? P? Q,命題邏輯 >等價(jià)公式,1.由3個(gè)命題變?cè)M成的互不等價(jià)的公式有______個(gè).2.求(P?R)?(Q?R ) 的真值表.該公式的類型是______.3.利用等值演算證明(p?r)?(q?r ) ?p?q?r .,,課堂練習(xí),,,,,,命題邏輯 >重言式,作 業(yè),1-5 （1）（a），（c） （2） （a），（b）,本節(jié)重點(diǎn)掌握

48、的概念: 永真式，永真與等價(jià)的關(guān)系。本節(jié)重點(diǎn)掌握的方法: 永真式的各種判定方法,,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-4 等價(jià)公式,1-5 重言式,1-7 對(duì)偶與范式,1-8 推理理論,,,,,,1-6 連接詞的全功能集,1-6 聯(lián)結(jié)詞的全功能集,,,,,,T,Q?P,P?Q,?,P,P?Q,?P,?Q,?,?,?,?,F,?,?,?,,,,,,?,Q,命題邏輯 >聯(lián)結(jié)詞的全功能集,

49、1.其他連接詞,70,,,,,,(1).P Q ? ?(P?Q),連接詞的化歸,(4).P?Q ? ?P?Q,(7).P ? Q ? ?(P?Q),? ?(P?Q),(5).P ? Q ? ?(?P??Q),(2).P?Q ? (P?Q)?(Q?P),(6).P ? Q ? ?(?P??Q),(8).P ? Q ? ?(P?Q),(3).,{?,?}和{ ?,?}稱為最小連接詞組(極小全功能集),命題邏輯 >聯(lián)結(jié)詞的全功能集,,

50、,,,,2.極小全功能集,命題邏輯 >聯(lián)結(jié)詞的全功能集,定義1-6.G是連接詞的集合,稱G是連接詞的極小全功能集, 若滿足如下條件:1）由G中的連接詞構(gòu)成的公式能等價(jià)表示任意公式；2）G中任一連接詞不能被其余下的連接詞等價(jià)表示。,例1 已知{?, ?}和{ ?, ?},為極小全功能集, 證明{?, →}也是極小全功能集.,例2 證明{↓}和{↑}也是極小全功能集.,實(shí)際應(yīng)用中多采用{?, ?, ?}為全功能集.,,

51、,,,,IF... THEN ...ELSE,三元聯(lián)結(jié)詞,命題邏輯 >其它聯(lián)結(jié)詞,假如上午不下雨,我去看電影;否則就在家里讀書或看報(bào).,( P? Q ) ? ( ?P ? R ),補(bǔ)例,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-4 真值表與等價(jià)公式,1-5 重言式,1-6 連接詞的全功能集,1-8 推理理論,,,,,,1-7 對(duì)偶與范式,本節(jié)討論命題公式的規(guī)范形式。包括主析取范式和主合

52、取范式，給出求主析和主合取方式的方法并通過范式獲得其性質(zhì)。1)便于計(jì)算機(jī)處理命題和推理2)通過化標(biāo)準(zhǔn)形便于判斷公式等價(jià)及公式的類型3)通過真值表可寫出的公式。,基本內(nèi)容,范式：normal formular,命題邏輯 >對(duì)偶與范式,本節(jié)只討論包含{?, ?, ?}的公式.,定義1-7.1 在給定的命題公式A中,將聯(lián)結(jié)詞∨換成∧,將∧換成∨,若有特殊變?cè)狥和T亦相互取代,所得公式A*稱為A的對(duì)偶式。,1-7 對(duì)偶與范式,

53、,,,,,例如 (P∧Q)∨T的對(duì)偶式為:,,１.對(duì)偶式(Dual Formula),?(P∨Q )∧(P∨?(Q∧?S))的對(duì)偶式為:,?(P∧Q )∨(P∧?(Q∨?S)),(P∨Q )∧F,命題邏輯 >對(duì)偶與范式,顯然有: (A*)*=A,,,,,,定理1-7.1 設(shè)A和A*是對(duì)偶式，P1,P2,...,Pn是出現(xiàn)在A和A*中的原子變?cè)?則 ?A( P1,,...,Pn ) ? A*(?P1,

54、..., ?Pn) A(?P1...,?Pn) ? ?A*(P1,...,Pn),P30 例 題3,定理1-7.2(對(duì)偶定理) 設(shè)A和B是命題公式，如果A?B，則A* ? B*。,補(bǔ)例,命題邏輯 >對(duì)偶與范式,設(shè) A*(S，W，R）= ? S ∧( ? W∨? R）證明：設(shè)A*(? S, ? W, ? R）? ? A(S，W，R）,證明 : P∨(P∧Q) ?P,; P ∧ (P

55、∨ Q) ?P,,,,,,定義1-7.2 一個(gè)命題公式稱為合取范式,當(dāng)且僅當(dāng)它具有形式：A1∧A2∧... ∧An, (n≥1) 其中A1,A2,...,An都是由命題變?cè)蚱浞穸ㄋM成的析取式(簡單析取式)。,2.范式(Normal Form),例如 (P∨?Q∨R ) ∧(?P∨Q)∧?R,,,,A1,A2,A3,P∨ Q ∨ R，,?(P∨ Q) ∧R，,,,,,命題邏輯 >對(duì)偶與范式,文字,P∨ ?P，,?P,P

56、∨ ( Q∧R ),簡單析取式：將若干文字用∨連接而成。,,,,,,定義1-7.3 一個(gè)命題公式稱為析取范式,當(dāng)且僅當(dāng)它具有形式：A1?A2?…,?An, (n≥1) 其中A1,A2,...,An都是由文字所組成的合取式。,例如 ?P∨(P∧Q)∨(P∧?Q∧R),,,,A3,A2,A1,P∧Q∧R,,?(P∧Q) ∨R,,,,,命題邏輯 >對(duì)偶與范式,P∨ Q ∨ R，,?P,任意命題公式均可通過等價(jià)演算化為

57、合取或析取范式。,(1).將公式中的聯(lián)結(jié)詞化歸成?、?、?。(2).利用德摩根律將?移到各原子變?cè)啊?3).利用分配律、結(jié)合律將公式歸約為合取范式 或析取范式。,范式化歸步驟,P32 例題5-6,命題邏輯 >對(duì)偶與范式,*定義1-7.4 合取式 1 ? 2 ? …,? n 稱為變?cè)MP1,P2,...,Pn 的一個(gè)小項(xiàng),其中 i 為文字，i=1,2,…n.,命題公式的合取或析取范式

58、不唯一.,例如:變?cè)M{ P, Q }的小項(xiàng):P ?Q, ?P ?Q , P??Q , ?P??Q,求 P?(Q?R )?S 的合取范式,求 ?(P?Q )?( P?Q ) 的析取范式,,,,,,兩個(gè)變?cè)捌湫№?xiàng)的真值表,表1-7.1,命題邏輯 >對(duì)偶與范式,n個(gè)命題變?cè)山M成 個(gè)不同的小項(xiàng).,每個(gè)小項(xiàng)和它的成真賦值一一對(duì)應(yīng),因此可以給小項(xiàng)編號(hào),使編號(hào)與小項(xiàng)的成真賦值對(duì)應(yīng).,,,,,,三個(gè)變?cè)捌湫№?xiàng)的真值表,表1-7.1,

59、= P??Q ?? R,=?P?Q?R,= P?Q ? ? R,=?P??Q? R,=?P??Q?? R,= P? ? Q ? R,= P?Q? R,=?P?Q?? R,命題邏輯 >對(duì)偶與范式,,,,,,小項(xiàng)的性質(zhì),(1).每一個(gè)小項(xiàng)當(dāng)其真值指派與其編號(hào)相同時(shí),真 值為T,其余 -1 種指派下均為假.,(2).任二小項(xiàng)的合取永假.,(3).全體小項(xiàng)的析取永真,記作:,命題邏輯 >對(duì)偶與范式,定義1-7.5

60、 對(duì)于給定的命題公式,如果有一個(gè)等價(jià)公式,它僅由小項(xiàng)的析取所組成,則該等價(jià)式稱作原式的主析取范式。,(1).將公式化歸為析取范式。(2).去掉析取范式中永假的小項(xiàng)。(3).合并析取范式中重復(fù)的小項(xiàng)。(4).對(duì)合取項(xiàng)中未出現(xiàn)的變?cè)狿,以P??P加入, 然后用分配律展開.,形式推演主析范式的步驟,,命題邏輯 >對(duì)偶與范式,定理1-7.3 在一個(gè)公式的真值表中,成真賦值對(duì)應(yīng)的小項(xiàng)做析取,即為此公式的主析取范式.,

61、P35 例 題7,P35 例 題9,每個(gè)命題公式都有唯一的主范式.,永假式的主析范式記作F.,求 P?((P?Q)??(?Q ??P ))的主析范式,,,,,,定義1-7.6 析取式 1 ? 2 ? ...? n 稱為變?cè)MP1, P2,...,Pn的一個(gè)大項(xiàng),其中 i 為Pi或?Pi , i=1,2,…n,n個(gè)命題變?cè)山M成 個(gè)不同的大項(xiàng).,命題邏輯 >對(duì)偶與范式,兩個(gè)變?cè)捌浯箜?xiàng)的真值表,表1-7.1,,

62、,,,,大項(xiàng)的性質(zhì),(1).每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)真值 為F,其余 -1 種指派下均為T.,(2).任二大項(xiàng)的析取永真.,(3).全體大項(xiàng)的合取永假,記作:,命題邏輯 >對(duì)偶與范式,定義1-7.7 對(duì)于給定的命題公式,如果有一個(gè)等價(jià)公式,它僅由大項(xiàng)的合取所組成,則該等價(jià)式稱作原式的主合取范式。,(1).將公式化歸為合取范式。(2).去掉合取范式中永假的大項(xiàng)。(3).合并合取范式中重復(fù)的大項(xiàng)。

63、(4).對(duì)析取項(xiàng)中未出現(xiàn)的變?cè)狿,以P??P加入, 然后用分配律展開.,形式推演主合范式的步驟,P38 例 題11,命題邏輯 >對(duì)偶與范式,定理1-7.4 在公式真值表中,成假賦值對(duì)應(yīng)的大項(xiàng)做合取,即為此式的主合取范式.,P37 例 題10,如何由主范式判定公式的類型,及公式的等價(jià)?,,永真式的主合范式記作T.,命題公式的主析范式中,未出現(xiàn)的小項(xiàng)編號(hào)即為其主合范式中的大項(xiàng)編號(hào).,,,,,,命題邏輯 >對(duì)偶與

64、范式,1.含有3個(gè)命題變?cè)墓紸，若主合取范式有8個(gè)大項(xiàng)，則A為____式,若主析范式有8個(gè)小項(xiàng)，則A為____式, 若主合取范式有3個(gè)大項(xiàng)組成，則主析取范式由——個(gè)小項(xiàng)組成2.公式A的主析范式為(?P ?Q )?(P??Q),主合范式為__________.3公式p?q??r 的主合取范式是__________.4.命題公式p?(p?q)的主析取范式是________.5.求(P?R)?(Q?R ) 的主析和主合范式.該公式

65、類型是()6.利用范式證明(p?r)?(q?r ) ?p?q?r .,,課堂練習(xí),,,,,,命題邏輯 >對(duì)偶與范式,作 業(yè),1-7 （2）（a） （3） （a） （4）（a），（c） （5）（a），（c） （7）,本節(jié)重點(diǎn)掌握的概念: 主析取范式，主合取范式本節(jié)重點(diǎn)掌握的方法: 求主范式的方法:列真值表法和等價(jià)演算方法,命題邏輯,1-1 命題及其表示,

66、1-2 邏輯連接詞,1-3 命題公式與賦值,1-4 真值表與等價(jià)公式,1-5 重言式,1-6 連接詞的全功能集,1-7 對(duì)偶與范式,,,,,,1-8 推理理論,1-8 推理理論,,,,,,命題邏輯 >推理理論,推理是由一個(gè)或幾個(gè)判斷推出新判斷的思維過程也就是由已知命題推出新命題的過程。已知命題稱為前提，由前提推出的命題稱為結(jié)論。,數(shù)理邏輯研究的是推理的一般形式和規(guī)律,是基于語法學(xué)的論證，一個(gè)推理過程正確與否與前提的真假無關(guān).,

67、推理理論研究如何建立一套嚴(yán)格定義的推理規(guī)則按照這組規(guī)則進(jìn)行推理就能保證推理的正確，由正確推理得到的結(jié)論稱為有效結(jié)論.,真值表法、等價(jià)演算、分析真值、證明法,命題邏輯 >推理理論,A ?B 即 A?B 為重言, 但 A?B ?(A?B)?(B?A)故 A ? B 即 A=>B 且 B => A,補(bǔ)例,定義1-8.1 設(shè)A和C是兩個(gè)命題公式,當(dāng)且僅當(dāng) A?C為一重言式, (記作A ? C) , 稱C是A的有效結(jié)論?；駽可

68、由A邏輯的推出 ( A蘊(yùn)含C )。一般，設(shè)H1,H2…Hn 和 C是命題公式當(dāng)且僅當(dāng)H1?H2?…,?Hn ? C稱C是一組前提H1,H2…Hn的有效結(jié)論.,判定永真式的各種方法都可用于判斷推理的正確性:,前提: P?Q?R 結(jié)論：(P?R)?(Q?R),分析真值法：,要證 A?B, 即證A→B為重言式，由 A→B的真值表知，如能證明當(dāng)前件A為真時(shí),后件B 也只能為真,則A→B必為重言式?；蜃C明其逆反問題: 當(dāng)后件B為假時(shí),前

69、件A 也為假,逆反問題: ¬B→¬A 稱為A→B 的逆反式.,它們之間存在關(guān)系 ：A→B ??B→¬A,命題邏輯 >推理理論,例 1.前提: P?Q, P 結(jié)論：Q,2.前提: P?Q?R 結(jié)論：(P?R)?(Q?R),,,,,,,要證C是一組前提H1,H2…Hn的有效結(jié)論, 需證 : H1?H2?…,?Hn?C 是重言式 即證: H1,H