數(shù)理邏輯總復(fù)習(xí)2013

1、1,數(shù)理邏輯總復(fù)習(xí),,2,第一章 主要內(nèi)容,命題、真值、簡單命題與復(fù)合命題、命題符號化聯(lián)結(jié)詞?, ?, ?, ?, ?及復(fù)合命題符號化命題公式及層次公式的類型真值表及應(yīng)用,3,第一章 基本要求,深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號化會求復(fù)合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型,4,第二章 主要內(nèi)容,等值式與等值演算基本等值

2、式（16組，24個公式）主析取范式與主合取范式聯(lián)結(jié)詞完備集消解法,5,第二章 基本要求,深刻理解等值式的概念牢記基本等值式的名稱及它們的內(nèi)容熟練地應(yīng)用基本等值式及置換規(guī)則進行等值演算理解文字、簡單析取式、簡單合取式、析取范式、合取范式的概念深刻理解極小項、極大項的概念、名稱及下角標(biāo)與成真、成假賦值的關(guān)系，并理解簡單析取式與極小項的關(guān)系,6,第二章 基本要求,熟練掌握求主范式的方法（等值演算、真值表等）會用主范式求公式的成

3、真賦值、成假賦值、判斷公式的類型、判斷兩個公式是否等值會將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式會用命題邏輯的概念及運算解決簡單的應(yīng)用問題掌握消解規(guī)則及其性質(zhì)會用消解算法判斷公式的可滿足性,7,第三章 主要內(nèi)容,推理的形式結(jié)構(gòu)判斷推理是否正確的方法真值表法 等值演算法主析取范式法推理定律自然推理系統(tǒng)P構(gòu)造推理證明的方法直接證明法附加前提證明法歸謬法(反證法),8,第三章 基本要求,理解并記住推理形式結(jié)構(gòu)的兩

4、種形式： 1. (A1?A2?…?Ak)?B 2. 前提：A1, A2, … , Ak 結(jié)論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記 P 系統(tǒng)中各條推理規(guī)則熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬法會解決實際中的簡單推理問題,9,第四章 主要內(nèi)容,個體詞、謂詞、量詞一階邏輯命題符號化一階語言L：項、原子公式、合式公式公式的解釋

5、量詞的轄域、指導(dǎo)變元、個體變項的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型永真式(邏輯有效式)、矛盾式(永假式)、可滿足式,10,第四章 基本要求,準(zhǔn)確地將給定命題符號化理解一階語言的概念深刻理解一階語言的解釋熟練地給出公式的解釋記住閉式的性質(zhì)并能應(yīng)用它深刻理解永真式、矛盾式、可滿足式的概念, 會判斷簡單公式的類型,11,第五章 主要內(nèi)容,一階邏輯等值式基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式推理的形式結(jié)構(gòu)自

6、然推理系統(tǒng)NL推理定律、推理規(guī)則,12,第五章 基本要求,深刻理解并牢記一階邏輯中的重要等值式, 并能準(zhǔn)確而熟練地應(yīng)用它們．熟練正確地使用置換規(guī)則、換名規(guī)則、代替規(guī)則．熟練地求出給定公式的前束范式．深刻理解自然推理系統(tǒng)NL 的定義，牢記NL 中的各條推理規(guī)則，特別是注意使用??、?+、?+、?? 4條推理規(guī)則的條件．能正確地給出有效推理的證明．,13 of 8,練習(xí)1：符號化練習(xí)（紅色為p，藍(lán)色為q）,這個工作要求有C++或J

7、ava的開發(fā)經(jīng)驗。本飯店午餐免費贈送湯或沙拉?？荚囅胍酶叻郑堰@本習(xí)題集做完就夠了。必須走500米才能登上香山山頂。只有你購買的手機沒有超過一年，你的包修單才有效。在電腦上登陸必須有一個有效的口令。如果你經(jīng)常玩電子游戲，你的視力會衰退，反之亦然。,p ? q,(?p ? q) ? (p ? ?q),q ? p,q ? p,q ? p,p ? q,q ? p,14 of 8,練習(xí)1（續(xù)）,a) 假如上午不下雨，我去看電影；否

8、則就在家里讀書或看報。p:上午下雨。 q: 我去看電影。r:我在家讀書。 r: 我在家看報。b)我今天去打球，除非下雨。p:我今天去打球。 q: 今天下雨。c)僅當(dāng)你走，我將留下。p:你走。 q: 我留下。,(?p?q)?(p?(r?s)),?q?p,q?p,15,練習(xí)1（續(xù)）,符號化下列命題1）每一個人的外祖父都是他母親的父親.P(x):x是人，O(x,y):x是y的外祖父F(x,y):x

9、是y的父親，M(x,y):x是y的母親2）不管白貓黑貓，抓住老鼠就是好貓.C(x):x是貓，W(x):x是白色的，B(x):x是黑色的G(x):x是好的，M(x):x是老鼠，K(x,y):x抓住y,?x?y (P(x) ? O(y,x)??z(M(z,x) ? F(y,z))),?x?y(C(x)?(W(x)?B(x))?M(y)?K(x,y)?G(x)),16,練習(xí)1（續(xù)）,3）在實數(shù)集中，任給一正實數(shù)，都存在大于該實數(shù)的實數(shù)

10、。 R(x):x是實數(shù)，G(x,y):x大于y，4）對平面上任意兩點，有且僅有一條直線通過這兩點。 P(x):x是一個點；L(x):x是一條直線 R(x,y,z):z通過x,y；E(x,y):x等于y.,?x(R(x)?G(x,0)??y(R(y)?G(y,x))),?x?y(P(x)?P(y)??z(L(z)?R(x,y,z))? ?u(L(u)?R(x,y,u)?E(u,z))),17,練

11、習(xí)2：實際應(yīng)用題,A, B, C, D 四個人中要派兩個人出差，按下述三個條件有幾種派法？如何派。（1）若 A 去，則 C 和 D 中要去一人。（2）B 和 C 不能都去。（3）C 去則 D 要留下。,解：設(shè)a: A 去出差。 b: B 去出差。 c: C 去出差。 d: D 去出差。按題意應(yīng)有：a?(c??d)?(?c?d), ?(b?c), c??d同時成立,18,練習(xí)2（續(xù)）,解：F=(a?(

12、c??d)?(?c?d))??(b?c)?(c??d)設(shè)B1=a?(c??d)?(?c?d) ? ?a?(c??d)?(?c?d) B2= ?(b?c)?(c??d) ? (?b??c)?(?c??d) ? (?b??c)?(?b??d)??c?(?c??d)F=B1?B2 ?(?a??b??c)?(?a??b??d)?(?a??c)?(?a??c??d)?(c??b??d)?(?c??b?d)?(?c

13、?d)所以有三種派法：B和D, A和C, A和D,19,練習(xí)3：實際應(yīng)用題,設(shè)有一個在Internet上下載新聞的程序，為避免程序產(chǎn)生死循環(huán)和重復(fù)下載同一條新聞條目，程序必須根據(jù)下述4個條件對給定的一個新聞條目判斷是否執(zhí)行下載任務(wù)：條件1：該新聞條目在程序的前一次執(zhí)行中已下載，用命題符號e表示；條件2：該新聞條目在程序的本次執(zhí)行中已下載，用命題符號n表示；條件3：該新聞條目是一個動態(tài)更新的新聞條目，用命題符號d表示；條件4：該

14、新聞條目已過期，程序需要重新下載，用命題符號o表示。,20,練習(xí)3：實際應(yīng)用題,執(zhí)行下載任務(wù)的規(guī)劃是：該新聞條目在程序的前一次執(zhí)行中未下載，則不論其他條件如何，一定執(zhí)行下載；如果是一條動態(tài)新聞，并且該新聞條目在程序的本次執(zhí)行中沒有下載，則執(zhí)行下載，否則不執(zhí)行下載；如果新聞條目在程序的前一次執(zhí)行中已下載，并且該新聞條目在程序的本次執(zhí)行中沒有下載，則如果是一個過期的新聞條目，則執(zhí)行下載，否則不執(zhí)行下載。請根據(jù)上述條件，寫出是否執(zhí)行下

15、載對應(yīng)的主合取范式.,21,練習(xí)3（續(xù)）,?e?(d??n)?(e??n?o)?((?e?d)?(?e??n))?(e??n?o)?(?e?d??n)?(?e?d?o)?(?e??n)?(?e??n?o)(?e?d?o)?(?e??n)(?e?n?d?o)?(?e??n?d?o)?(?e??n?d??o)?(?e??n??d?o) ?(?e??n??d??o),22,練習(xí)4 證明題,某廠方拒絕增加工資，則罷工不會停止，除非罷工

16、超過一年并且工廠經(jīng)理辭職。問：如果廠方拒絕增加工資，而罷工又剛剛開始，罷工是否能停止？,解： 令 p: 廠方拒絕增加工資q: 罷工停止r: 工廠經(jīng)理辭職s: 罷工超過一年則，前提：( p ? ?(r ? s)) → ?q, p, ?s 結(jié)論： ?q,23,練習(xí)4(續(xù)),解： (1) ?s前提引入 (2) ?s ? ? r 1)置換 (3) ?(r ? s)

17、 2)置換 (4) p前提引入 (5) p ? ?(r ? s)3)4)合取引入 (6) ( p ? ?(r ? s)) → ?q前提引入 (7) ?q 5)6)假言推理所以罷工不會停止。,前提：( p ? ?(r ? s)) → ?q, p, ?s結(jié)論： ?q,24,練習(xí)5 證明題,在一階邏輯中推證下列結(jié)論的有效性：每個報考研究生的大學(xué)畢業(yè)生

18、要么參加研究生入學(xué)考試，要么被推薦為免試生；每個報考研究生的大學(xué)畢業(yè)生當(dāng)且僅當(dāng)學(xué)習(xí)成績優(yōu)秀才被推薦為免試生；有些報考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績優(yōu)秀，但并非所有報考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績都優(yōu)秀。因此，有些報考研究生的大學(xué)畢業(yè)生要參加研究生入學(xué)考試。設(shè)P(x)：x是報考研究生的大學(xué)畢業(yè)生，Q(x)：x參加研究生入學(xué)考試，R(x)：x被推薦為免試生，S(x)：x學(xué)習(xí)成績優(yōu)秀。,25,練習(xí)5（續(xù)）,前提：?x(P(x)?Q(x)?R

19、(x)), ?x(P(x)?(S(x)?r(x))), ?x(P(x)?S(x))??x(P(x)??S(x))結(jié)論：?x(P(x)?Q(x)),26,練習(xí)5（續(xù)）,?x(P(x)?S(x))??x(P(x)??S(x))前提引入?x(P(x)??S(x))1)化簡?x(P(x)?(S(x)?R(x)))前提引入P(x)?(S(x)?R(x))3)?-P(x)?(?S(x)??R(x))4)化簡P(x)

20、??S(x)??R(x)5)置換P(x)??S(x)?P(x)化簡(P(x)??S(x)??R(x))?(P(x)??S(x)?P(x)) 6)7)合取?(P(x)??S(x))?(?R(x)?P(x)) 8)置換P(x)??S(x)?P(x)??R(x) 9)置換,27,練習(xí)5（續(xù)）,11) ?x(P(x)?Q(x)?R(x))前提引入12) P(x)?Q(x)?R(x)11) ?-13) P(

21、x)??R(x)?Q(x)12)置換14) P(x)??R(x)?P(x)13)置換15)(P(x)??R(x)?Q(x))?(P(x)??R(x)?P(x)) 13)14)合取16)?(P(x)??R(x))?(Q(x)?P(x)) 15)置換17)P(x)??R(x)?P(x)?Q(x)16)置換18) P(x)??S(x)?P(x)?Q(x)10)17)假言三段論19) P(x)??S(x)? ?