探討漢彌爾頓路徑問題在給定額外述詞符號之二階邏輯下的表示法

Abstract

邏輯是數學裡專門探討敘述的推理演繹的一個分支，被認定為推理的研究。由於數學的 本質是由關於數學物件的敘述以及驗證這些敘述的證明所構成，因此，整個數學領域可以用 邏輯加以分析。而理論電腦科學的核心部分---演算法，其觀念的基礎就是計算的觀念，也是 個數學物件，可由邏輯分析之。在這篇論文裡，我們提供了邏輯的基本性質，並且利用這些 性質來研究一些計算問題，特別是漢彌爾頓路徑(Hamiltonian Path)這個圖型理論的問題。

Logic is a branch of mathematics that investigates the deductions about statements and is recognized as the study of reasoning. Because of this, the whole mathematics can be investigated by logic and is even governed by it since the essentials of mathematics consist of statements about mathematical objects and the proofs that verify these statements. Since the underlying concept 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 provide the basic properties of logic, and then use them to investigate some computational problems, especially the graph-theoretic problem Hamiltonian path.