趙坤茂臺灣大學:資訊工程學研究所吳韋霖Wu, Wei-LinWei-LinWu2010-05-172018-07-052010-05-172018-07-052009U0001-1008200921272700http://ntur.lib.ntu.edu.tw//handle/246246/183377邏輯是數學裡專門探討敘述的推理演繹的一個分支，被認定為推理的研究。由於數學的質是由關於數學物件的敘述以及驗證這些敘述的證明所構成，因此，整個數學領域可以用輯加以分析。而理論電腦科學的核心部分---演算法，其觀念的基礎就是計算的觀念，也是數學物件，可由邏輯分析之。在這篇論文裡，我們提供了邏輯的基本性質，並且利用這些質來研究一些計算問題，特別是漢彌爾頓路徑(Hamiltonian Path)這個圖型理論的問題。Logic is a branch of mathematics that investigates the deductions about statements and is recognizeds the study of reasoning. Because of this, the whole mathematics can be investigatedy logic and is even governed by it since the essentials of mathematics consist of statementsbout mathematical objects and the proofs that verify these statements. Since the underlyingoncept of algorithms, the critical part of theoretical computer science, is that of computation,hich is also a mathematical object, it can aslo be analyzed by logic. In this thesis we providehe basic properties of logic, and then use them to investigate some computational problems,specially the graph-theoretic problem Hamiltonian path.1 Introduction 1.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Categories inside Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Computational Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Topics on Propositional Logic 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3.1 Equvalence between Propositions . . . . . . . . . . . . . . . . . . . . . . 12.4 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Topics on Predicate Logic 19.1 First-order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.1.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.1.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.1.3 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26.1.4 Weakness of First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . 29.2 Second-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Graph-Theoretic Problems as Expressed in Logical Formulae 31.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 The Successor Function in Graph-Theoretic Problems . . . . . . . . . . . . . . . 32 Concluding Remarks 37ibliography 39application/pdf536197 bytesapplication/pdfen-US命題邏輯述詞邏輯一階邏輯存在性二階邏輯漢彌爾頓路徑propositional logicpredicate logicfirst-order logicexistential second-order logicHamiltonian paththesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183377/1/ntu-98-R96922105-1.pdf