前言

要考高級數理邏輯了，和舍友整理了一波去年高級數理邏輯的答案，可能有錯誤，僅供參考，被坑了，概不負責，嘿嘿嘿，參考了王元元的《現代邏輯學》，李文生老師的PPT，和BigPan老師的講義，北郵科技酒店的往年試題集合，

修改

修改了簡答題第一題中的問題，有朋友指出 ? □ ? A → ? A \neg \Box \neg A \rightarrow \Diamond A ?□?A→?A是不成立的，因為命題A的可達世界可能不存在，關于必然和可能以及可達世界的問題，我在這篇博客里面稍微講了一下，可以參考一下可能與必然

圖1 題目上

圖2 題目下

一.簡答題

1.原來的歸結程序如下， 是 有 問 題 的 \color{red}是有問題的 是有問題的，

C ? = ? ( ? A → ? B ) ? ∧ ( ? ( A → B ) ) ? = ? ( ? ( ? A ) ? ∧ ( ? B ) ? ) ) ∧ □ ( A → B ) ? = ? ( ? □ A ? ∧ □ B ? ) ∧ □ ( ? A ? ∧ B ? ) = ( □ A ? ∨ ? □ B ? ) ∧ □ ? ( A ? ∨ ? B ? ) ? C ? = ? ( □ A ? ∨ ? □ B ? ) ∨ ? □ ? ( A ? ∨ ? B ? ) = ? ( □ A ? ∨ ? □ B ? ) ∨ ? ( A ? ∨ ? B ? ) = ? ( □ B ? → □ A ? ) ∨ ? ( B ? → A ? ) = ( □ B ? → □ A ? ) → ? ( B ? → A ? ) \begin{aligned} C^* &= \neg(\Diamond A \rightarrow \Diamond B)^* \land (\Diamond(A \rightarrow B))^* \\ &= \neg(\neg(\Diamond A)^* \land (\Diamond B)^*)) \land \Box(A \rightarrow B)^* \\ &= \neg(\neg \Box A^* \land \Box B^*) \land \Box(\neg A^* \land B^*) \\ &= (\Box A^* \lor \neg \Box B^*) \land \Box \neg(A^* \lor \neg B^*) \\ \neg C^* &= \neg (\Box A^* \lor \neg \Box B^*) \lor \neg \Box \neg(A^* \lor \neg B^*) \\ &= \neg (\Box A^* \lor \neg \Box B^*) \lor \Diamond(A^* \lor \neg B^*) \\ &= \neg(\Box B^* \rightarrow \Box A^*) \lor \Diamond(B^* \rightarrow A^*) \\ &= (\Box B^* \rightarrow \Box A^*) \rightarrow \Diamond(B^* \rightarrow A^*) \end{aligned} C??C??=?(?A→?B)?∧(?(A→B))?=?(?(?A)?∧(?B)?))∧□(A→B)?=?(?□A?∧□B?)∧□(?A?∧B?)=(□A?∨?□B?)∧□?(A?∨?B?)=?(□A?∨?□B?)∨?□?(A?∨?B?)=?(□A?∨?□B?)∨?(A?∨?B?)=?(□B?→□A?)∨?(B?→A?)=(□B?→□A?)→?(B?→A?)?

其中 ? C ? \neg C^* ?C?第一步是不成立的，如前所說 ? □ ? A → ? A \neg \Box \neg A \rightarrow \Diamond A ?□?A→?A不成立，所以修改之后的答案是這樣的，

C = ( ? A → ? B ) → ? ( A → B ) C ? = ? ( ? A → ? B ) ? ∧ ( ? ( A → B ) ) ? = ? ( ? ( ? A ) ? ∧ ( ? B ) ? ) ∧ □ ( A → B ) ? = ? ( ? □ A ? ∧ □ B ? ) ∧ □ ( ? A ? ∧ B ? ) = ( □ A ? ∨ ? □ B ? ) ∧ □ ? ( A ? ∨ ? B ? ) ? C ? = ? ( □ A ? ∨ ? □ B ? ) ∨ ? □ ( ? A ? ∧ B ? ) = ? ( □ B ? → □ A ? ) ∨ ? □ ( ? A ? ∧ B ? ) = ( □ B ? → □ A ? ) → ? □ ( ? A ? ∧ B ? ) \begin{aligned} C &= (\Diamond A \rightarrow \Diamond B) \rightarrow \Diamond (A\rightarrow B) \\ \\ C^* &= \neg(\Diamond A \rightarrow \Diamond B)^* \land (\Diamond(A \rightarrow B))^* \\ &= \neg(\neg (\Diamond A)^*\land(\Diamond B)^*)\land \Box(A \rightarrow B)^* \\ &= \neg(\neg \Box A^* \land \Box B^*) \land \Box(\neg A^* \land B^*) \\ &= (\Box A^* \lor \neg \Box B^*) \land \Box\neg(A^* \lor \neg B^*) \\ \\ \neg C^* &= \neg(\Box A^* \lor \neg \Box B^*) \lor \neg\Box(\neg A^* \land B^*) \\ &= \neg(\Box B^* \rightarrow \Box A^*) \lor \neg\Box(\neg A^* \land B^*) \\ &= (\Box B^* \rightarrow \Box A^*) \rightarrow \neg\Box(\neg A^* \land B^*) \end{aligned} CC??C??=(?A→?B)→?(A→B)=?(?A→?B)?∧(?(A→B))?=?(?(?A)?∧(?B)?)∧□(A→B)?=?(?□A?∧□B?)∧□(?A?∧B?)=(□A?∨?□B?)∧□?(A?∨?B?)=?(□A?∨?□B?)∨?□(?A?∧B?)=?(□B?→□A?)∨?□(?A?∧B?)=(□B?→□A?)→?□(?A?∧B?)?

2.FS 合理性（soundness）：稱形式系統 FS 是合理的，FS 的任意公式 A 有：├FS A ，則|=M A ， M 為所有結構； FS 完備性（Completeness）：稱形式系統 FS 是完備的，如果對 FS 的任意公式 A 有：若|=M A ，則├FS A ，這里 M 為 FS 所討論的一類結構；

3.常元：常元表示個體域中的一個確定個體，如：5，Zhang San 等， 變元：變元可以用來表示個體域上的任意個體，是不確定的， 自由變元：自由變元是真正的變元，可以將個體域中的任意個體代入到自由變元中，類似于 數學中的變元， 約束變元：約束變元并不是實際意義的變元（數學意義上的變元），約束變元是為表達某種 想的輔助符號， 自由變元與約束變元的對比：

自由變元 約束變元

可代入 不可代入

不可改名 可改名

4.形式系統 FS 稱為可判定的，如果存在一個演算法，對 FS 對的任一公式 A，可確定├A 是否成立，否則稱 FS 是可判定的；如果上述演算法對定理能作出判斷， 而對于非定理未必終止（作判斷），稱 FS 為半可判定的；

• FS 為可判定的，當且僅當定理集合為遞回集；

5.Herbrand 定理：子句集 S 為不可滿足的，當且僅當 S 的基例的有窮集合是不可滿足的，

證明： 假設 S 的有限個基例為 S1 ，S2 …Sn ，

1、 當有限個基例不可滿足，則 S 為不可滿足的 S├S1 ∧S2 ∧…∧Sn 因此，如果{ S1 , S2 ,…,Sn}為不可滿足的，則 S 一定不可滿足，

2、 當 S 為不可滿足時，有限基例為不可滿足的， l 反證法：假設 S 不可滿足，但是有限基例都為可滿足的， l 則根據緊致性，有所有的基例集合是可滿足的， l 需要語意樹的定理來證明，我們略，

二.判斷題

1 F

? ( A → ( B → A ) ) \Diamond (A \rightarrow (B\rightarrow A)) ?(A→(B→A))不是永真式， □ ( A → ( B → A ) ) \Box (A \rightarrow (B\rightarrow A)) □(A→(B→A))才是, 因為這個公式的可能世界可能不存在，參考試卷第1頁第8題和第29頁第9題

2 F

見試卷第1頁第4題，x可能不是A中的自由變元

3 F

見現代邏輯學152頁，假如A沒有可能世界，就可以同時滿足

4 T

在命題邏輯中，對不可滿足的子句集S，歸結原理是完備的，即：若子句集不可滿足，則必然存在一個從S到空子句的歸結演繹；若存在一個從S到空子句的歸結演繹，則S一定是不可滿足的，但是，對于可滿足的子句集S，用歸結原理得不到任何結果，

百度百科歸結原理

5 F

滿足傳遞性 ? ? ? A → ? A \leftrightarrow \Diamond \Diamond A \rightarrow \Diamond A ???A→?A成立，見試卷第9頁，可以舉個反例，例如， w 1 w_1 w1?可達世界 w 2 w_2 w2?，而 w 2 w_2 w2?可達世界 w 3 w_3 w3?，假設A在 w 3 w_3 w3?成立，而在 w 2 w_2 w2?不成立

6 T

見試卷19頁8題

7 T

見試卷第9頁第9題

8 F

可能 ∑ \sum ∑本身就是錯的

9 T

根據BigPan說的，感覺是錯的，就是對的，哈哈哈，瞎猜的

10 F

符號還要求是可數集合，見老師講義01，2.2.3

三. 選擇題

1.AD(B?)

等價性代表自反，對稱，傳遞，而自反可以推匯出連續，對稱+傳遞->歐幾里得性質，所以B正確(歐幾里得運算式,但是試卷1頁1題中卻沒有選擇它)，而D和連續性等價，所以正確，A與傳遞性有關(見試卷9頁第5題)，

2.C

A中可能世界可能不存在，比如從w1開始，B由于不滿足連續性，比如w3，就不成立，D同理

C可能不對，自反+傳遞為偏序，見現代邏輯學149

3.BD

P 1 ( x ) P_1(x) P1?(x)中的x是約束變元， P 2 ( x ) P_2(x) P2?(x)中的x是自由變元， p 3 ( y ) p_3(y) p3?(y)中的y是約束變元， P 4 ( z ) P_4(z) P4?(z)中的z是自由變元

4.BCD

見講義4.6，一階謂詞邏輯是半判定的，

5.D

對于A，除非x1是無窮小，B中后繼不可能比前面的小，C中變元v不確定，

四.證明計算題

1. 見試卷29頁證明題第2題

2. 見試卷29頁證明題第1題

3. 見李文生PPT中43頁

4. 不會，放棄

5. 見試卷29證明題第3題

五.參考資料下載鏈接

為了滿足大家列印的需求，把我用到的資料都放在這里，

圖3 參考資料截圖

鏈接：https://pan.baidu.com/s/1si357WPM4eg1JCWYvRYECQ
提取碼：3jxv