# 臺灣博碩士論文加值系統

(44.210.149.205) 您好！臺灣時間：2024/04/16 19:46

:::

### 詳目顯示

:

• 被引用:0
• 點閱:146
• 評分:
• 下載:0
• 書目收藏:0
 邏輯是數學裡專門探討敘述的推理演繹的一個分支，被認定為推理的研究。由於數學的本質是由關於數學物件的敘述以及驗證這些敘述的證明所構成，因此，整個數學領域可以用邏輯加以分析。而理論電腦科學的核心部分---演算法，其觀念的基礎就是計算的觀念，也是個數學物件，可由邏輯分析之。在這篇論文裡，我們提供了邏輯的基本性質，並且利用這些性質來研究一些計算問題，特別是漢彌爾頓路徑(Hamiltonian Path)這個圖型理論的問題。
 Logic is a branch of mathematics that investigates the deductions about statements and is recognizedas the study of reasoning. Because of this, the whole mathematics can be investigatedby logic and is even governed by it since the essentials of mathematics consist of statementsabout mathematical objects and the proofs that verify these statements. Since the underlyingconcept of algorithms, the critical part of theoretical computer science, is that of computation,which is also a mathematical object, it can aslo be analyzed by logic. In this thesis we providethe basic properties of logic, and then use them to investigate some computational problems,especially the graph-theoretic problem Hamiltonian path.
 1 Introduction 11.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Categories inside Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 Computational Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Topics on Propositional Logic 42.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3.1 Equvalence between Propositions . . . . . . . . . . . . . . . . . . . . . . 122.4 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Topics on Predicate Logic 193.1 First-order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.3 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.1.4 Weakness of First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Second-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Graph-Theoretic Problems as Expressed in Logical Formulae 314.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 The Successor Function in Graph-Theoretic Problems . . . . . . . . . . . . . . . 325 Concluding Remarks 37Bibliography 39
 [1] R. Fagin Generalized rst-order spectra and polynomial-time recognizable sets," pp. 43{73 in Complexity of Computation, edited by R. M. Karp SIAM-AMS Proceedings, vol. 7,1974.[2] P. Kolatis and M. Vardi { 1 laws and decision problems for fragments of second-orderlogic," Proc. 3rd IEEE Symp. on Logic In Comp. Sci, pp. 2{11, 1988.[3] N. Immerman Relational queries computable in polynomial time," Information and Control,68, pp. 86{104, 1986.[4] M. Y. Vardi The complexity of relational query languages," Proceedings of the 14th ACMSymp. on the Theory of Computing, pp. 137{146, 1982.[5] C. H. Papadimitriou A note on the expressive power of PROLOG," Bull. of the EATCS,26, pp. 21{23, 1985.[6] C. H. Papadimitriou Computational complexity, second edition, Addison-Wesley Longman.[7] E. Gradel The expressive power of second-order Horn logic," Proc. 8th Symp. on Theor.Aspects of Comp. Sci., vol. 480 of Lecture Notes in Computer Science, pp. 466{477, 1991.[8] H.-D. Ebbinghaus, J. Flum, and W. Thomas Mathematical logic, second edition, Springer.[9] H. B. Enderton A Mathematical Introduction to Logic, Academic Press.[10] D. van Dalen Logic and Structure, fourth edition, Springer.[11] R. P. Grimaldi Discrete and Combinatorial Mathematics, an Applied Introduction, fthedition, Pearson Addison-Wesley.[12] E. Mendelson Introduction to Mathematical Logic, fourth edition, Chapman & Hall/CRC.[13] L. Henkin The completeness of rst-order functional calculus," J. Symb. Logic, 14, pp.159 { 166, 1949.[14] K. Godel Die Vollstandigkeit der Axiome der Logischen Funktionenkalkuls" (The completenessof the axioms of the logical function calculus), Monat, Math. Physik, 37, pp. 349{ 360, 1930.[15] K. Godel Uber formal unentscheidbare Satze der Principia Mathematica und verwandterSysteme" (On formally undecidable theorems in Principia Mathematica and related systems),Monatschefte fur Mathematik und Physik, 38, pp. 173 { 198, 1931[16] L. Henkin, J. D. Monk and A. Tarski Cylindric Algebras, North Holland, 1971 { 1985.[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein Introduction to Algorithms,second edition, MIT Press, Cambridge, Massachusetts, 2001[18] E. Horowitz, S. Sahni, D. Mehta Fundamentals of Data Structures in C++, ComputerScience Press, An imprint of W. H. Freeman and Company, New York, 1995.[19] S. Hedman A rst course in logic : an introduction to model theory, proof theory, computability,and complexity, Oxford, New York, Oxford University Press, 2004.[20] S. Russell, P. Norvig Arti cial Intelligence, a Modern Approach, second edition, PrenticeHall Series in Arti cial Intelligence, 2003.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 發生抗藥性Enterobactercloacae菌血症之危險因子及Enterobactercloacae菌血症之死亡預後因子分析:著重於藥物治療效果 2 多軸慣性量測系統的設計與實現 3 從語言使用到構式固化：漢語多義結果動詞「V-開」的認知語言學研究 4 超薄氧化層純水補償技術及氫對ONO介電層可靠度之影響 5 寡核苷酸微陣列同時快速診斷鑑定多種重要防檢疫森林病原真菌之研發 6 豬脂締素及其受體表現調控機制與功能之探討 7 中國大陸中央銀行獨立性的政治經濟分析：一個官僚部門競爭途徑之研究 8 任務導向平衡訓練合併感覺操弄對腦中風患者平衡功能與姿勢控制之療效研究 9 自動化網路安全防禦系統 10 應用壓阻式微懸臂梁生物感測器偵測巴斯德桿菌之研究 11 點棒可視圖的厚度最佳漸近上界 12 虛擬化多核心之省電投射技術 13 以統計方法來自動偵測線上遊戲機器人程式 14 經驗為良師?股市崩盤期之投資人行為分析 15 側掃聲納回散射訊號之海床地貌影像分析研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室