數(shù)理邏輯第十五節(jié)課06

1、復(fù)習(xí)基礎(chǔ) 85分左右進階 15分左右1復(fù)習(xí).基礎(chǔ)1.演繹與歸納有何區(qū)別？2復(fù)習(xí).基礎(chǔ)1.演繹與歸納有何區(qū)別？演繹推理有必然性，前件真，后件必然真3復(fù)習(xí).基礎(chǔ)1.演繹與歸納有何區(qū)別？0304 24-36（初步）4復(fù)習(xí).基礎(chǔ)2.什么是推理？5復(fù)習(xí).基礎(chǔ)2.什么是推理？一系列命題(proposition)或者陳述句(declarative sentence)的序列，其中一部分組成前提(premises)集，序列的最后一個是結(jié)論(conclusion)，用以表明前提集合理地得出或者支持結(jié)論6復(fù)習(xí).基礎(chǔ)2.什么是推理？0304 43邢第5-6面徐第2面，分得更細論說推理7復(fù)習(xí).基礎(chǔ)3.陳述句與命題的關(guān)系

2、？8復(fù)習(xí).基礎(chǔ)3.陳述句與命題的關(guān)系？陳述句是表達命題的句子除了表達命題以外，還有其它的豐富的意思只關(guān)注陳述句表達有真假的命題9復(fù)習(xí).基礎(chǔ)3.陳述句與命題的關(guān)系？0304 44-59邢 4-510復(fù)習(xí).基礎(chǔ)4.根據(jù)不同的“邏輯部件”進行相應(yīng)的形式化、符號化11復(fù)習(xí).基礎(chǔ)4.根據(jù)不同的“邏輯部件”進行相應(yīng)的形式化、符號化不同的邏輯“部件” 不同“粗細地”外延化情景 不同的形式化12復(fù)習(xí).基礎(chǔ)4.根據(jù)不同的“邏輯部件”進行相應(yīng)的形式化、符號化不同的邏輯“部件” 不同“粗細地”外延化情景 不同的形式化例子康德不是女人 康德是女人或者柏拉圖是男人 柏拉圖是男人 男人是戰(zhàn)士 柏拉圖是男人 柏拉圖是戰(zhàn)士1

3、3復(fù)習(xí).基礎(chǔ)4.根據(jù)不同的“邏輯部件”進行相應(yīng)的形式化、符號化不同的邏輯“部件” 不同“粗細地”外延化情景 不同的形式化真值聯(lián)結(jié)詞 量詞14復(fù)習(xí).基礎(chǔ)4.根據(jù)不同的“邏輯部件”進行相應(yīng)的形式化、符號化0311 14-24徐命題邏輯 符號化 34-38；60-61 習(xí)題2.1-2.3徐謂詞邏輯 符號化 248-266；（我們沒有詳細講，7.1-7.6）15復(fù)習(xí).基礎(chǔ)5.元語言與對象語言可以是同一種語言嗎？16復(fù)習(xí).基礎(chǔ)5.元語言與對象語言可以是同一種語言嗎？元語言與對象語言可以是同一種17復(fù)習(xí).基礎(chǔ)5.元語言與對象語言可以是同一種語言嗎？元語言與對象語言可以是同一種相應(yīng)的漢語+部分英語+一些符號

4、 元語言18復(fù)習(xí).基礎(chǔ)5.元語言與對象語言可以是同一種語言嗎？元語言與對象語言可以是同一種相應(yīng)的漢語+部分英語+一些符號 元語言元語言里可以有推理、使用數(shù)學(xué)概念、方法19復(fù)習(xí).基礎(chǔ)5.元語言與對象語言可以是同一種語言嗎？0311 53-60邢92-93徐39-4020復(fù)習(xí).基礎(chǔ)6.命題公式的主聯(lián)結(jié)詞21復(fù)習(xí).基礎(chǔ)6.命題公式的主聯(lián)結(jié)詞有五類聯(lián)結(jié)詞（1） 否定（并非，不，） （2） 合?。ú⑶?，但是， ） （3） 析?。ɑ蛘撸皇?就是， ） （4） 蘊涵（如果-那么，只要， ） （5） 雙蘊涵（當(dāng)且僅當(dāng)，等價于， ） 22復(fù)習(xí).基礎(chǔ)6.命題公式的主聯(lián)結(jié)詞命題公式的形成0命題變號都是0公式；若是

5、0公式，則()也是0公式；若與是0公式，則()也是0公式；若與是0公式，則()也是0公式；若與是0公式，()也是0公式；若與是0公式， ()也是0公式；只有適合以上七條的是0公式。23復(fù)習(xí).基礎(chǔ)6.命題公式的主聯(lián)結(jié)詞命題公式的形成0命題變號都是0公式；若是0公式，則()也是0公式；若與是0公式，則()也是0公式；若與是0公式，則()也是0公式；若與是0公式，()也是0公式；若與是0公式， ()也是0公式；只有適合以上七條的是0公式。24最后一步用到第2-6條，相應(yīng)的真值聯(lián)結(jié)詞是主聯(lián)結(jié)詞復(fù)習(xí).基礎(chǔ)6.命題公式的主聯(lián)結(jié)詞命題公式的形成0命題變號都是0公式；若是0公式，則()也是0公式；若與是0公式

6、，則()也是0公式；若與是0公式，則()也是0公式；若與是0公式，()也是0公式；若與是0公式， ()也是0公式；只有適合以上七條的是0公式。25最后一步用到第2-6條，相應(yīng)的真值聯(lián)結(jié)詞是主聯(lián)結(jié)詞可推廣到一階公式復(fù)習(xí).基礎(chǔ)7.命題公式的語形樹26復(fù)習(xí).基礎(chǔ)7.命題公式的語形樹0311 68-75由結(jié)構(gòu)歸納法可證明每個命題公式都有唯一一棵語形樹。27復(fù)習(xí).基礎(chǔ)7.命題公式的語形樹0311 68-75由結(jié)構(gòu)歸納法可證明每個命題公式都有唯一一棵語形樹。直觀上保證“無歧義性”28復(fù)習(xí).基礎(chǔ)8.命題公式的子公式集29復(fù)習(xí).基礎(chǔ)8.命題公式的子公式集0311 76-79借助語形樹的概念30復(fù)習(xí).基礎(chǔ)8.命

7、題公式的子公式集0311 76-79借助語形樹的概念請試著用遞歸定義定義命題公式的子公式31復(fù)習(xí).基礎(chǔ)9.歸納法、歸納定義32復(fù)習(xí).基礎(chǔ)9.歸納法、歸納定義數(shù)學(xué)歸納法設(shè)P(x)是一個性質(zhì)，若它滿足P(0)對任意的自然數(shù)n(P(n)P(n+1)那么，對任意的自然數(shù)n(P(n)33復(fù)習(xí).基礎(chǔ)9.歸納法、歸納定義邢58-63 歸納定義 68-70 項的歸納證明 76-78 公式的歸納證明0513 101-12034復(fù)習(xí).基礎(chǔ)9.歸納法、歸納定義邢58-63 歸納定義 68-70 項的歸納證明 76-78 公式的歸納證明0513 101-120在用歸納定義方法得到的集合上實施歸納證明，以證明集合中的每

8、個元素都有某性質(zhì)35復(fù)習(xí).基礎(chǔ)10.真值函數(shù)聯(lián)結(jié)詞的真值表36復(fù)習(xí).基礎(chǔ)10.真值函數(shù)聯(lián)結(jié)詞的真值表基本真值表-真值函數(shù)聯(lián)結(jié)詞的“意義”37復(fù)習(xí).基礎(chǔ)10.真值函數(shù)聯(lián)結(jié)詞的真值表0318 33-64徐 43特別要注意“實質(zhì)蘊涵”的真值表38復(fù)習(xí).基礎(chǔ)11.真值指派與命題公式真值的計算39復(fù)習(xí).基礎(chǔ)11.真值指派與命題公式真值的計算公式在情景下的真值40復(fù)習(xí).基礎(chǔ)11.真值指派與命題公式真值的計算公式在情景下的真值外延化情景 真值指派41復(fù)習(xí).基礎(chǔ)11.真值指派與命題公式真值的計算0318 65-79徐44-48由“每個0公式都有唯一一棵語形樹。”以及真值指派、真值函數(shù)聯(lián)結(jié)詞的“意義”都為函數(shù)

9、保證復(fù)合命題的真假完全由構(gòu)成它的簡單命題的真假所決定。每個0公式在每個“情景”下有唯一的真值42復(fù)習(xí).基礎(chǔ)12.重言蘊涵、可滿足與重言式43復(fù)習(xí).基礎(chǔ)12.重言蘊涵、可滿足與重言式重言后承（重言蘊涵）-有效的推理形式44復(fù)習(xí).基礎(chǔ)12.重言蘊涵、可滿足與重言式重言后承（重言蘊涵）-有效的推理形式稱公式集可滿足，若存在真值指派，使得 45復(fù)習(xí).基礎(chǔ)12.重言蘊涵、可滿足與重言式重言后承（重言蘊涵）-有效的推理形式稱公式集可滿足，若存在真值指派，使得 若對每個真值指派，都有，則稱為重言式我們有另一個定義，46復(fù)習(xí).基礎(chǔ)12.重言蘊涵、可滿足與重言式0318 80-90；0325 8-11；徐49-

10、5747復(fù)習(xí).基礎(chǔ)13.真值表法48復(fù)習(xí).基礎(chǔ)13.真值表法0325 54-64；徐47-4849復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)50復(fù)習(xí).基礎(chǔ)51復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)0415 17-136徐113-143一個自然推演系統(tǒng)N52復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)為什么要講演算系統(tǒng)？53復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)邏輯學(xué)的根 正確的推理形式（與重言式）54復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)邏輯學(xué)的根 正確的推理形式（與重言式）處理成 55復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）

11、系統(tǒng)邏輯學(xué)的根 正確的推理形式（與重言式）處理成 語形上演算系統(tǒng)H （可靠性與完全性）56復(fù)習(xí).基礎(chǔ)14.命題邏輯的演算（公理、自然推演）系統(tǒng)邏輯學(xué)的根 正確的推理形式（與重言式）處理成 語形上演算系統(tǒng)H （可靠性與完全性）如果考內(nèi)定理的證明，會給出公理、規(guī)則57復(fù)習(xí).基礎(chǔ)15.命題邏輯中的代入58復(fù)習(xí).基礎(chǔ)15.命題邏輯中的代入用在代入規(guī)則59復(fù)習(xí).基礎(chǔ)15.命題邏輯中的代入用在代入規(guī)則0401 39-44徐81-8560復(fù)習(xí).基礎(chǔ)16.演算系統(tǒng)的可靠性61復(fù)習(xí).基礎(chǔ)16.演算系統(tǒng)的可靠性據(jù)系統(tǒng)證明的都是對的62復(fù)習(xí).基礎(chǔ)16.演算系統(tǒng)的可靠性據(jù)系統(tǒng)證明的都是對的命題演算系統(tǒng)、謂詞演算系統(tǒng)用

12、一種形式的歸納法證63復(fù)習(xí).基礎(chǔ)16.演算系統(tǒng)的可靠性據(jù)系統(tǒng)證明的都是對的命題演算系統(tǒng)、謂詞演算系統(tǒng)用一種形式的歸納法證64復(fù)習(xí).基礎(chǔ)65復(fù)習(xí).基礎(chǔ)66復(fù)習(xí).基礎(chǔ)17.會用演繹定理67復(fù)習(xí).基礎(chǔ)68復(fù)習(xí).基礎(chǔ)17.會用演繹定理0401 107；0408 42-64徐176-17769復(fù)習(xí).基礎(chǔ)18.會用反證法與歸謬法70復(fù)習(xí).基礎(chǔ)71復(fù)習(xí).基礎(chǔ)18.會用反證法與歸謬法0408 67-8472復(fù)習(xí).基礎(chǔ)19-21.集合論初步73復(fù)習(xí).基礎(chǔ)19-21.集合論初步子集、冪集、并、差映射、單射、滿射、雙射集合的等勢74復(fù)習(xí).基礎(chǔ)19-21.集合論初步子集、冪集、并、差映射、單射、滿射、雙射集合的等勢重

13、要的是用集合論概念與工具做外延化的工作75復(fù)習(xí).基礎(chǔ)20.集合論初步0422 61-167；0506 9-173；0513 1-26邢第二章76復(fù)習(xí).基礎(chǔ)22.一階語言中的項與公式的定義77復(fù)習(xí).基礎(chǔ)22.一階語言中的項與公式的定義語言里用來代表結(jié)構(gòu)的領(lǐng)域里的個體的要素稱為項78復(fù)習(xí).基礎(chǔ)22.一階語言中的項與公式的定義語言里用來代表結(jié)構(gòu)的領(lǐng)域里的個體的要素稱為項用歸納定義方法定義0513 121-12379復(fù)習(xí).基礎(chǔ)22.一階語言中的項與公式的定義語言里用來代表結(jié)構(gòu)的領(lǐng)域里的個體的要素稱為項用歸納定義方法定義0513 121-123每個項總是從個體變項與個體常項出發(fā)，經(jīng)過有窮步構(gòu)造得到，而且

14、這種構(gòu)造途徑是唯一的80復(fù)習(xí).基礎(chǔ)22.一階語言中的項與公式的定義語言里用來代表結(jié)構(gòu)的領(lǐng)域里的個體的要素稱為項用歸納定義方法定義0513 121-123每個項總是從個體變項與個體常項出發(fā)，經(jīng)過有窮步構(gòu)造得到，而且這種構(gòu)造途徑是唯一的公式類似歸納定義 0520 27-32邢第三章第3、4節(jié)81復(fù)習(xí).基礎(chǔ)23.一階公式的秩82一階公式的秩復(fù)習(xí).基礎(chǔ)23.一階公式的秩公式的復(fù)雜度的度量，可以用于歸納證明83一階公式的秩復(fù)習(xí).基礎(chǔ)84一階公式的秩復(fù)習(xí).基礎(chǔ)24.量化式中量詞的轄域85一階公式的秩復(fù)習(xí).基礎(chǔ)24.量化式中量詞的轄域?qū)σ粋€量化式（或），稱其子公式是量詞（或）的轄域。86一階公式的秩復(fù)習(xí).基

15、礎(chǔ)24.量化式中量詞的轄域?qū)σ粋€量化式（或），稱其子公式是量詞（或）的轄域。直觀上看，一處量詞的轄域就是緊跟著它的最短公式0520 72-76邢8287一階公式的秩復(fù)習(xí).基礎(chǔ)25.變項的自由出現(xiàn)與約束出現(xiàn)88一階公式的秩復(fù)習(xí).基礎(chǔ)25.變項的自由出現(xiàn)與約束出現(xiàn)在公式中，一個變項如果出現(xiàn)在某個形如（或）的量詞的某處轄域中，則稱在中的這處出現(xiàn)（以及它在這個量詞中的出現(xiàn)）是約束的。變項的非約束的出現(xiàn)，稱為自由出現(xiàn)。89一階公式的秩復(fù)習(xí).基礎(chǔ)25.變項的自由出現(xiàn)與約束出現(xiàn)在公式中，一個變項如果出現(xiàn)在某個形如（或）的量詞的某處轄域中，則稱在中的這處出現(xiàn)（以及它在這個量詞中的出現(xiàn)）是約束的。變項的非約束的

16、出現(xiàn)，稱為自由出現(xiàn)。0520 77-79邢8390一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋91一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋單純就語形而言，項與公式都是符號串；如果我們想要確定它們的意義，就需要按照這些符號的類型，把它們與語言之外的個體、關(guān)系、函數(shù)等對應(yīng)起來（用這些符號來代表某些事物）。92一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋要使一個語言中的公式獲得意義，我們首先要劃定一個個體域A，挑出其中的特指個體，確定其中的性質(zhì)、關(guān)系、函數(shù)等，然后把語言中的個體常項、謂詞、函數(shù)符號等與A中的這些東西對應(yīng)起來。這個過程就是對語言的解釋（當(dāng)然，我們也需要

17、解釋邏輯符號）?？梢钥闯觯瑢σ粋€給定語言的解釋主要需要兩樣?xùn)|西：一是語言之外的某個世界（包括個體域及其中的性質(zhì)、關(guān)系、函數(shù)等）二是語言的非邏輯符號與這個世界之間的某種對應(yīng)關(guān)系，二者合起來稱為關(guān)于這個語言的一個結(jié)構(gòu)。93一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋0520 102-109邢91-9594一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋結(jié)構(gòu)可以確定閉公式的真假，但是還不足以確定開公式的真假95一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋結(jié)構(gòu)可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談?wù)撈渲惺褂瞄_公式的推理形式的有效性96一階公式的秩復(fù)習(xí)

18、.基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋結(jié)構(gòu)可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談?wù)撈渲惺褂瞄_公式的推理形式的有效性開公式在結(jié)構(gòu)上無法確定真假值的原因在于其中的自由變項不清楚指向什么對象97一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋結(jié)構(gòu)可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談?wù)撈渲惺褂瞄_公式的推理形式的有效性開公式在結(jié)構(gòu)上無法確定真假值的原因在于其中的自由變項不清楚指向什么對象引入賦值與解釋98一階公式的秩復(fù)習(xí).基礎(chǔ)26.一階語言的結(jié)構(gòu)、賦值與解釋0520 118-119邢95-9799一階公式的秩復(fù)習(xí).基礎(chǔ)27.項與公式在解釋上的值

19、100一階公式的秩復(fù)習(xí).基礎(chǔ)27.項與公式在解釋上的值解釋實質(zhì)上是在結(jié)構(gòu)里用個體變項給一些個體起名字（個體變項指稱相應(yīng)的個體）101一階公式的秩復(fù)習(xí).基礎(chǔ)27.項與公式在解釋上的值解釋實質(zhì)上是在結(jié)構(gòu)里用個體變項給一些個體起名字（個體變項指稱相應(yīng)的個體）借助解釋里的賦值，每個項也指稱一個個體，進而，每個公式，無論開閉，都有了真假值102一階公式的秩復(fù)習(xí).基礎(chǔ)27.項與公式在解釋上的值0527 31-38（項）；45-78（公式）邢95（項）；113（公式）103一階公式的秩復(fù)習(xí).基礎(chǔ)28.合同引理104一階公式的秩復(fù)習(xí).基礎(chǔ)28.合同引理如果有相同論域的兩個解釋，對一個項（或者公式）的符號有相同

20、的意義，那么這個項（或者公式）在這兩個解釋上有相同的意義（指向同一個對象，或者有相同的真值）105一階公式的秩復(fù)習(xí).基礎(chǔ)106一階公式的秩復(fù)習(xí).基礎(chǔ)28.合同引理0527 ； 83-116（公式）邢118-120（一般版本）107一階公式的秩復(fù)習(xí).基礎(chǔ)29.語義后承、有效式108一階公式的秩復(fù)習(xí).基礎(chǔ)29.語義后承、有效式對“/”有效與否的形式刻畫109一階公式的秩復(fù)習(xí).基礎(chǔ)29.語義后承、有效式對“/”有效與否的形式刻畫0527 119-131（語義后承）；0603 45-94（有效式）邢123-129（語義后承）；130-133（有效式）110一階公式的秩復(fù)習(xí).基礎(chǔ)30.閉公式描述結(jié)構(gòu)111一階公式的秩復(fù)習(xí).基礎(chǔ)30.閉公式描述結(jié)構(gòu)例子 可以寫出一個閉公式，使得對任意的結(jié)構(gòu)= ,，若，則中至多有2個元素112一階公式的秩復(fù)習(xí).基礎(chǔ)30.閉公式描述結(jié)構(gòu)例子 可以寫出一個閉公式，使得對任意的結(jié)構(gòu)= ,，若，則中至多有2個元素2=113一階公式的秩復(fù)習(xí).基礎(chǔ)30.閉公式描述結(jié)構(gòu)例子 可以寫出一個閉公式，使得對任意的結(jié)構(gòu)= ,，若，則中至多有2個元素2=0527 136-142邢147-149114一階公式的秩復(fù)習(xí).基礎(chǔ)31、32.代換與重言式代換式115一階公式的秩復(fù)習(xí).基礎(chǔ)31、32.代換與重言式代換式命題邏輯中的重言式反映了