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

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

2、公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型真賦值與成假賦值及判斷公式類型4第二章第二章 主要內(nèi)容主要內(nèi)容o等值式與等值演算等值式與等值演算o基本等值式（基本等值式（1616組，組，2424個公式）個公式）o主析取范式與主合取范式主析取范式與主合取范式o聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集o消解法消解法5第二章第二章 基本要求基本要求o深刻理解等值式的概念深刻理解等值式的概念o牢記基本等值式的名稱及它們的內(nèi)容牢記基本等值式的名稱及它們的內(nèi)容o熟練地應(yīng)用基本等值式及置換規(guī)則進行等值熟練地應(yīng)用基本等值式及置換規(guī)則進行等值演算演算o理解文字、簡單析取式、簡單合取式、析取理解文字、簡單析取式、簡單

3、合取式、析取范式、合取范式的概念范式、合取范式的概念o深刻理解極小項、極大項的概念、名稱及下深刻理解極小項、極大項的概念、名稱及下角標(biāo)與成真、成假賦值的關(guān)系，并理解簡單角標(biāo)與成真、成假賦值的關(guān)系，并理解簡單析取式與極小項的關(guān)系析取式與極小項的關(guān)系6第二章第二章 基本要求基本要求o熟練掌握求主范式的方法（等值演算、真值熟練掌握求主范式的方法（等值演算、真值表等）表等）o會用主范式求公式的成真賦值、成假賦值、會用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個公式是否等值判斷公式的類型、判斷兩個公式是否等值o會將公式等值地化成指定聯(lián)結(jié)詞完備集中的會將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式

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

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

6、化o一階語言一階語言L：項、原子公式、：項、原子公式、合式公式合式公式o公式的解釋公式的解釋n量詞的轄域、指導(dǎo)變元、個體變項的自由量詞的轄域、指導(dǎo)變元、個體變項的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋出現(xiàn)與約束出現(xiàn)、閉式、解釋o公式的類型公式的類型n永真式永真式(邏輯有效式邏輯有效式)、矛盾式、矛盾式(永假式永假式)、可、可滿足式滿足式10第四章第四章 基本要求基本要求o準(zhǔn)確地將給定命題符號化準(zhǔn)確地將給定命題符號化o理解一階語言的概念理解一階語言的概念o深刻理解一階語言的解釋深刻理解一階語言的解釋o熟練地給出公式的解釋熟練地給出公式的解釋o記住閉式的性質(zhì)并能應(yīng)用它記住閉式的性質(zhì)并能應(yīng)用它o深刻理解永真

7、式、矛盾式、可滿足式的概念深刻理解永真式、矛盾式、可滿足式的概念, 會判斷簡單公式的類型會判斷簡單公式的類型11第五章第五章 主要內(nèi)容主要內(nèi)容o一階邏輯等值式一階邏輯等值式n基本等值式，置換規(guī)則、換名規(guī)則、代替基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則規(guī)則o前束范式前束范式o推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)o自然推理系統(tǒng)自然推理系統(tǒng)NLn推理定律、推理規(guī)則推理定律、推理規(guī)則12第五章第五章 基本要求基本要求o深刻理解并牢記一階邏輯中的重要等值式深刻理解并牢記一階邏輯中的重要等值式, 并并能準(zhǔn)確而熟練地應(yīng)用它們能準(zhǔn)確而熟練地應(yīng)用它們o熟練正確地使用置換規(guī)則、換名規(guī)則、代替熟練正確地使用置換規(guī)則、換名規(guī)

8、則、代替規(guī)則規(guī)則o熟練地求出給定公式的前束范式熟練地求出給定公式的前束范式o深刻理解自然推理系統(tǒng)深刻理解自然推理系統(tǒng)NL 的定義，牢記的定義，牢記NL 中中的各條推理規(guī)則，特別是注意使用的各條推理規(guī)則，特別是注意使用、 +、 +、 4條推理規(guī)則的條件條推理規(guī)則的條件o能正確地給出有效推理的證明能正確地給出有效推理的證明 13練習(xí)練習(xí)1：符號化練習(xí)（紅色為：符號化練習(xí)（紅色為p，藍色為，藍色為q）n這個工作要求有這個工作要求有C+或或Java的開發(fā)經(jīng)驗。的開發(fā)經(jīng)驗。n本飯店午餐免費贈送本飯店午餐免費贈送湯湯或或沙拉沙拉。n考試想要得高分考試想要得高分，把這本習(xí)題集做完把這本習(xí)題集做完就夠了就夠了

9、。n必須必須走走500米米才能才能登上香山山頂?shù)巧舷闵缴巾?。n只有只有你購買的手機沒有超過一年你購買的手機沒有超過一年，你你的包修單才有效的包修單才有效。n在電腦上登陸在電腦上登陸必須必須有一個有效的口令有一個有效的口令。n如果如果你經(jīng)常玩電子游戲你經(jīng)常玩電子游戲，你的視力會你的視力會衰退衰退，反之亦然。，反之亦然。p q( p q) (p q)q pq pq pp qq p14練習(xí)1（續(xù)）a) 假如上午不下雨，我去看電影；否則就在假如上午不下雨，我去看電影；否則就在家里讀書或看報。家里讀書或看報。p:上午下雨。上午下雨。 q: 我去看電影。我去看電影。r:我在家讀書。我在家讀書。 r: 我在

10、家看報。我在家看報。b)我今天去打球，除非下雨。我今天去打球，除非下雨。p:我今天去打球。我今天去打球。 q: 今天下雨。今天下雨。c)僅當(dāng)你走，我將留下。僅當(dāng)你走，我將留下。p:你走。你走。 q: 我留下。我留下。( pq) (p(r s) qpqp15練習(xí)練習(xí)1（續(xù)）（續(xù)）o符號化下列命題符號化下列命題1）每一個人的外祖父都是他母親的父親）每一個人的外祖父都是他母親的父親.P(x):x是人，是人，O(x,y):x是是y的外祖父的外祖父F(x,y):x是是y的父親，的父親，M(x,y):x是是y的母親的母親2）不管白貓黑貓，抓住老鼠就是好貓）不管白貓黑貓，抓住老鼠就是好貓.C(x):x是貓，

11、是貓，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í)練習(xí)1（續(xù)）（續(xù)）3）在實數(shù)集中，任給一正實數(shù)，都存在大于在實數(shù)集中，任給一正實數(shù)，都存在大于該實數(shù)的實數(shù)。該實數(shù)的實數(shù)。 R(x):x是實數(shù)，是實數(shù)，G(x,y):x大于大于y，4）對平面上任意兩點，有且僅有一條直線通）對平面上任意兩點，有且僅有一條直線通過這兩點。過這兩點。 P(x):x是一個點；是一個

12、點；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練習(xí)練習(xí)2：實際應(yīng)用題：實際應(yīng)用題 A, B, C, D 四個人中要派兩個人出差，按四個人中要派兩個人出差，按下述三個條件有幾種派法？如何派。下述三個條件有幾種派法？如何派。（1）若）若 A 去，則去，則 C 和和 D 中要去一人。中要去一人。（2）B 和和 C 不能都去。不能都去。（3）C 去則去則 D 要留下。要留下。解：設(shè)解：設(shè)a

13、: A 去出差。去出差。 b: B 去出差。去出差。 c: C 去出差。去出差。 d: D 去出差。去出差。按題意應(yīng)有：按題意應(yīng)有：a(cd) ( c d), (b c), cd同時成立同時成立18練習(xí)練習(xí)2（續(xù)）（續(xù)）解：解：F=(a(cd) ( c d)(b c) (cd)設(shè)設(shè)B1=a(cd) ( c d) a (cd) ( c d) B2= (b c) (cd) ( bc) ( cd) ( bc) ( bd)c ( cd)F=B1 B2 ( abc) ( abd) ( ac) ( acd) (cbd) ( cb d) ( c d)所以有三種派法：所以有三種派法：B和和D, A和和C, A

14、和和D19練習(xí)練習(xí)3：實際應(yīng)用題：實際應(yīng)用題o設(shè)有一個在設(shè)有一個在Internet上下載新聞的程序，為避免上下載新聞的程序，為避免程序產(chǎn)生死循環(huán)和重復(fù)下載同一條新聞條目，程序產(chǎn)生死循環(huán)和重復(fù)下載同一條新聞條目，程序必須根據(jù)下述程序必須根據(jù)下述4個條件對給定的一個新聞條個條件對給定的一個新聞條目判斷是否執(zhí)行下載任務(wù)：目判斷是否執(zhí)行下載任務(wù)：n條件條件1：該新聞條目在程序的前一次執(zhí)行中：該新聞條目在程序的前一次執(zhí)行中已下載，用命題符號已下載，用命題符號e表示；表示；n條件條件2：該新聞條目在程序的本次執(zhí)行中已：該新聞條目在程序的本次執(zhí)行中已下載，用命題符號下載，用命題符號n表示；表示；n條件條件3

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

16、，則執(zhí)行下載，否則不執(zhí)行下載；則不執(zhí)行下載；n如果新聞條目在程序的前一次執(zhí)行中已下載，如果新聞條目在程序的前一次執(zhí)行中已下載，并且該新聞條目在程序的本次執(zhí)行中沒有下并且該新聞條目在程序的本次執(zhí)行中沒有下載，則如果是一個過期的新聞條目，則執(zhí)行載，則如果是一個過期的新聞條目，則執(zhí)行下載，否則不執(zhí)行下載。下載，否則不執(zhí)行下載。o請根據(jù)上述條件，寫出是否執(zhí)行下載對應(yīng)的主請根據(jù)上述條件，寫出是否執(zhí)行下載對應(yīng)的主合取范式合取范式.21練習(xí)練習(xí)3（續(xù)）（續(xù)） e (dn) (en o)( e d) ( en) (en o)( e dn) ( e d o) ( en) ( en o)( e d o) ( en

17、)( e n d o) ( en d o) ( en do) ( end o) ( endo) 22練習(xí)練習(xí)4 證明題證明題 某廠方拒絕增加工資，則罷工不會停止，除某廠方拒絕增加工資，則罷工不會停止，除非罷工超過一年并且工廠經(jīng)理辭職。問：如非罷工超過一年并且工廠經(jīng)理辭職。問：如果廠方拒絕增加工資，而罷工又剛剛開始，果廠方拒絕增加工資，而罷工又剛剛開始，罷工是否能停止？罷工是否能停止？解：解： 令令 p: 廠方拒絕增加工資廠方拒絕增加工資q: 罷工停止罷工停止r: 工廠經(jīng)理辭職工廠經(jīng)理辭職s: 罷工超過一年罷工超過一年則，前提：則，前提：( p (r s) q, p, s 結(jié)論：結(jié)論： q23練

18、習(xí)練習(xí)4(續(xù)續(xù))解：解： (1) s前提引入前提引入 (2) s r 1)置換置換 (3) (r s) 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é)論：結(jié)論： q24練習(xí)練習(xí)5 證明題證明題o在一階邏輯中推證下列結(jié)論的有效性：在一階邏輯中推證下列結(jié)論的有效性：o每個報考研究生的大學(xué)畢業(yè)生要么參加研究生入每個報考研究生的大學(xué)畢業(yè)生要么參加研究生入學(xué)考試，要么被推薦為免試生；每個報考研究

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