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

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

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

3、 為后繼課程準(zhǔn)備 必要的數(shù)學(xué)工具。,是計算機(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è) 入寶山空手而歸,,,,,,,,平時成績20％(考勤,作業(yè),測驗(yàn))

4、 期末閉卷考試 80 ％,,教學(xué)安排,五教1109 周一下午 2: 00,,作業(yè)和測驗(yàn)：每周第一次上課時交作業(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,,,,,又稱符號邏輯,是用數(shù)學(xué)方法研究形式邏輯（演繹和推理）的一門學(xué)問。,數(shù)理邏輯,13,,,,,,,邏輯LOGIC—是研究思維規(guī)律的科學(xué)。 1.辯

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

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

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

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

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

11、et theory),證明論(poof theory）,遞歸論(recursive theory）,數(shù)理邏輯包括五個部分：,模型論( 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,第一章,,,以命題為研究對象，研究命題的邏輯結(jié)構(gòu)及命題間的推理關(guān)系。,1-1 命題及其表示,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集,1-7 對偶與范式,1-8 推理理論,,,,,,1-4 等價公式,1-1 命題及其表示,命題邏輯,,,,,,本節(jié)主要討論四個問題：命題如何定義？命題如何取值

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

14、升起。,命題邏輯 >命題及其表示,,,,,,(3) 1+101=110.,(4) 別的星球上有生物.,(5) 全體立正!,(6) 明天是否開會?,(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)識符。,(9) 我學(xué)英語或者我學(xué)日語.,(10) 如果天氣好,我去散步.,(復(fù)合命題),(復(fù)合命題),,,,,復(fù)合命題的真值由各原子命題的真值及連接詞的含義確定。,,,,,,命題常量: 命題標(biāo)識符代表某一確定的命題。命題變

16、元:命題標(biāo)識符代表任意一個命題.變元的取值范圍(T,F).變元的指派:當(dāng)命題變元被特定命題代入,成為具有確定真值的命題時。稱對命題變元的指派。原子變元：命題變元代表原子命題時。,命題邏輯 >命題及其表示,名詞術(shù)語,27,1-1 命題及其表示,命題邏輯,,,,,,回答問題：命題如何定義？命題如何取值？命題如何分類？命題如何表示？,28,1-1 命題及其表示,命題邏輯,,,,,,判斷：X+y<52+2=4張華

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

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

19、其否命題?P為:,例如,塑料是金屬.,(Q),(?Q),塑料不是金屬.,塑料是金屬.,(?Q),(Q),否定是個相對概念.,,,塑料不是金屬.,2.所有的自然數(shù)都不是偶數(shù).?,是對整個命題的否定,而不是對句子成份的否定.,,,,,,命題邏輯 > 邏輯連接詞,定義 1-2.2 兩個命題P和Q的合取是一個復(fù)合命題,記作P∧Q。 當(dāng)且僅當(dāng)P、Q同時為T時,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 兩個命題P和Q的析取是一個復(fù)合命題,記作P∨Q。當(dāng)且僅當(dāng)P、Q同時為F時,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.４ 給定兩個命題P和Q,其條件命題是一個復(fù)合命題,記作P→Q,讀作“若P則Q”。當(dāng)且僅當(dāng)P的真值為T, Q的真值為F時, P→Q的真值為F。否則P→Q的真值為T。我們稱P為前件，Q為后件。,,,,,,(4) 條件（Implication） →,與日常用語中的 ‘如果…則’,‘必須…以便’,等含義相當(dāng)。,P→Q為F, if

23、f P為T、Q為F。,命題邏輯 > 邏輯連接詞,,,,,,例1 如果某動物是哺乳動物,則它必胎生.,解:,設(shè) P: 某動物是哺乳動物 Q: 某動物是胎生,符號化為: P? Q,例2 如果太陽從東方升起,你就可以長生不老.,解:,設(shè) P: 太陽從東方升起 Q: 你可以長生不老.,符號化為: 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的真值相同時,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 兩個三角形

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

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

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

28、）我留下（ q）?！狈柣癁椋?）A. p? q B. q?p C. p ?q D. p?q5.設(shè) p:天下雨, q: 他有時間, r: 他進(jìn)城, 則命題 “如果天不下雨且他有時間,他就進(jìn)城”符號化為 ( ) 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)掌握的方法: 命題符號化.,,,1-3 命題公式與賦值,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-5 重言式,1-6 連接詞的全功能集

30、,1-7 對偶與范式,1-8 推理理論,,,,,,1-4 等價公式,1-3 命題公式與賦值,定義1-3.1 命題演算的合式公式(wff),規(guī)定為:(1) 單個命題變元本身是wff。(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é)詞和括號的符號串是wff.,命題邏輯 > 命題公式與賦值,1. 命題公式,合式公式是對命題形式的抽象描述，反映了復(fù)合命題的結(jié)構(gòu)特征，故可將對復(fù)合命題的研究化為對合式公式的研究。,公式中的命題變元稱為分量,含n個分量的公式稱為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),例如:,二元公式,二元公式,(多括號),(非法字符),1.公式最外層的括號可省略.2.規(guī)定運(yùn)算優(yōu)先級為?,?,?,?,? ,則其中的括 號可省略.3.同級的從左至右進(jìn)行時,則其中的括號可省略.,命題公式的簡化規(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指定一組真值稱為對公式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)=,為簡便起見可將這組賦值表示為一個01序列:010,該公式共有多少種不同賦值?,T,(成真賦值),0,(成假賦值),命題邏輯 >命題公式與賦值,真值表:將公式的所有不同賦值及對應(yīng)的取值情況匯列成表.,,,,,,,1.將wff中出現(xiàn)的所有變元按順序一一列出.,3.按所有變元取值的各種組合計算各分子式最后一列 即為原式的取值情況。,例 題,,如果X是wff的一部分

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

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

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

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

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

40、真值表的最后一列.,等價演算:利用基本公式、等價的性質(zhì) 和 置換定理，推演出其他等價式.,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等價,即A?B。,例 題,命題邏輯 >等價公式,等價的性質(zhì),(1).A?A,(

41、2).若A?B,則B?A.,(3).若A?B,且B?C，則A?C,（自反性）,（對稱性）,（傳遞性）,,證明 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,,,,,,命題邏輯 >等價公式,回答問題1 互不等價的n元公式有——個？2 等價的性質(zhì)有哪些？3

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

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

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

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

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

47、) ?T只需證 ?( P?Q ) ? ?P? Q ? ? P? Q,命題邏輯 >等價公式,1.由3個命題變元組成的互不等價的公式有______個.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、的概念: 永真式，永真與等價的關(guān)系。本節(jié)重點(diǎn)掌握的方法: 永真式的各種判定方法,,命題邏輯,1-1 命題及其表示,1-2 邏輯連接詞,1-3 命題公式與賦值,1-4 等價公式,1-5 重言式,1-7 對偶與范式,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)成的公式能等價表示任意公式；2）G中任一連接詞不能被其余下的連接詞等價表示。,例1 已知{?, ?}和{ ?, ?},為極小全功能集, 證明{?, →}也是極小全功能集.,例2 證明{↓}和{↑}也是極小全功能集.,實(shí)際應(yīng)用中多采用{?, ?, ?}為全功能集.,,

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

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

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

54、..., ?Pn) A(?P1...,?Pn) ? ?A*(P1,...,Pn),P30 例 題3,定理1-7.2(對偶定理) 設(shè)A和B是命題公式，如果A?B，則A* ? B*。,補(bǔ)例,命題邏輯 >對偶與范式,設(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 一個命題公式稱為合取范式,當(dāng)且僅當(dāng)它具有形式：A1∧A2∧... ∧An, (n≥1) 其中A1,A2,...,An都是由命題變元或其否定所組成的析取式(簡單析取式)。,2.范式(Normal Form),例如 (P∨?Q∨R ) ∧(?P∨Q)∧?R,,,,A1,A2,A3,P∨ Q ∨ R，,?(P∨ Q) ∧R，,,,,,命題邏輯 >對偶與范式,文字,P∨ ?P，,?P,P

56、∨ ( Q∧R ),簡單析取式：將若干文字用∨連接而成。,,,,,,定義1-7.3 一個命題公式稱為析取范式,當(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,,,,,命題邏輯 >對偶與范式,P∨ Q ∨ R，,?P,任意命題公式均可通過等價演算化為

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

58、不唯一.,例如:變元組{ P, Q }的小項(xiàng):P ?Q, ?P ?Q , P??Q , ?P??Q,求 P?(Q?R )?S 的合取范式,求 ?(P?Q )?( P?Q ) 的析取范式,,,,,,兩個變元及其小項(xiàng)的真值表,表1-7.1,命題邏輯 >對偶與范式,n個命題變元可組成 個不同的小項(xiàng).,每個小項(xiàng)和它的成真賦值一一對應(yīng),因此可以給小項(xiàng)編號,使編號與小項(xiàng)的成真賦值對應(yīng).,,,,,,三個變元及其小項(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,命題邏輯 >對偶與范式,,,,,,小項(xiàng)的性質(zhì),(1).每一個小項(xiàng)當(dāng)其真值指派與其編號相同時,真 值為T,其余 -1 種指派下均為假.,(2).任二小項(xiàng)的合取永假.,(3).全體小項(xiàng)的析取永真,記作:,命題邏輯 >對偶與范式,定義1-7.5

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

61、P35 例 題7,P35 例 題9,每個命題公式都有唯一的主范式.,永假式的主析范式記作F.,求 P?((P?Q)??(?Q ??P ))的主析范式,,,,,,定義1-7.6 析取式 1 ? 2 ? ...? n 稱為變元組P1, P2,...,Pn的一個大項(xiàng),其中 i 為Pi或?Pi , i=1,2,…n,n個命題變元可組成 個不同的大項(xiàng).,命題邏輯 >對偶與范式,兩個變元及其大項(xiàng)的真值表,表1-7.1,,

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

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

64、范式,1.含有3個命題變元的公式A，若主合取范式有8個大項(xiàng)，則A為____式,若主析范式有8個小項(xiàng)，則A為____式, 若主合取范式有3個大項(xiàng)組成，則主析取范式由——個小項(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í),,,,,,命題邏輯 >對偶與范式,作 業(yè),1-7 （2）（a） （3） （a） （4）（a），（c） （5）（a），（c） （7）,本節(jié)重點(diǎn)掌握的概念: 主析取范式，主合取范式本節(jié)重點(diǎn)掌握的方法: 求主范式的方法:列真值表法和等價演算方法,命題邏輯,1-1 命題及其表示,

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

67、推理理論研究如何建立一套嚴(yán)格定義的推理規(guī)則按照這組規(guī)則進(jìn)行推理就能保證推理的正確，由正確推理得到的結(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是兩個命題公式,當(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為真時,后件B 也只能為真,則A→B必為重言式?；蜃C明其逆反問題: 當(dāng)后件B為假時,前

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