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

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

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

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

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

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

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

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

8、個元素都有某性質35復習.基礎10.真值函數聯結詞的真值表36復習.基礎10.真值函數聯結詞的真值表基本真值表-真值函數聯結詞的“意義”37復習.基礎10.真值函數聯結詞的真值表0318 33-64徐 43特別要注意“實質蘊涵”的真值表38復習.基礎11.真值指派與命題公式真值的計算39復習.基礎11.真值指派與命題公式真值的計算公式在情景下的真值40復習.基礎11.真值指派與命題公式真值的計算公式在情景下的真值外延化情景 真值指派41復習.基礎11.真值指派與命題公式真值的計算0318 65-79徐44-48由“每個0公式都有唯一一棵語形樹?！币约罢嬷抵概?、真值函數聯結詞的“意義”都為函數

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

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

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

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

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

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

15、礎24.量化式中量詞的轄域對一個量化式（或），稱其子公式是量詞（或）的轄域。直觀上看，一處量詞的轄域就是緊跟著它的最短公式0520 72-76邢8287一階公式的秩復習.基礎25.變項的自由出現與約束出現88一階公式的秩復習.基礎25.變項的自由出現與約束出現在公式中，一個變項如果出現在某個形如（或）的量詞的某處轄域中，則稱在中的這處出現（以及它在這個量詞中的出現）是約束的。變項的非約束的出現，稱為自由出現。89一階公式的秩復習.基礎25.變項的自由出現與約束出現在公式中，一個變項如果出現在某個形如（或）的量詞的某處轄域中，則稱在中的這處出現（以及它在這個量詞中的出現）是約束的。變項的非約束的

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

17、解釋邏輯符號）?？梢钥闯觯瑢σ粋€給定語言的解釋主要需要兩樣東西：一是語言之外的某個世界（包括個體域及其中的性質、關系、函數等）二是語言的非邏輯符號與這個世界之間的某種對應關系，二者合起來稱為關于這個語言的一個結構。93一階公式的秩復習.基礎26.一階語言的結構、賦值與解釋0520 102-109邢91-9594一階公式的秩復習.基礎26.一階語言的結構、賦值與解釋結構可以確定閉公式的真假，但是還不足以確定開公式的真假95一階公式的秩復習.基礎26.一階語言的結構、賦值與解釋結構可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談論其中使用開公式的推理形式的有效性96一階公式的秩復習

18、.基礎26.一階語言的結構、賦值與解釋結構可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談論其中使用開公式的推理形式的有效性開公式在結構上無法確定真假值的原因在于其中的自由變項不清楚指向什么對象97一階公式的秩復習.基礎26.一階語言的結構、賦值與解釋結構可以確定閉公式的真假，但是還不足以確定開公式的真假但是我們又要談論其中使用開公式的推理形式的有效性開公式在結構上無法確定真假值的原因在于其中的自由變項不清楚指向什么對象引入賦值與解釋98一階公式的秩復習.基礎26.一階語言的結構、賦值與解釋0520 118-119邢95-9799一階公式的秩復習.基礎27.項與公式在解釋上的值

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

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