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

A Study on Expressing the Hamiltonian Path Problem in Second-Order Logic with Some Additional Predicate Symbols

吳韋霖(Wei-Lin Wu)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00745

摘要

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

並列關鍵字

propositional logic ； predicate logic ； first-order logic ； existential second-order logic ； Hamiltonian path

參考文獻

[2] P. Kolatis and M. Vardi { 1 laws and decision problems for fragments of second-order

[3] N. Immerman Relational queries computable in polynomial time," Information and Control,

[4] M. Y. Vardi The complexity of relational query languages," Proceedings of the 14th ACM

[6] C. H. Papadimitriou Computational complexity, second edition, Addison-Wesley Longman.

[7] E. Gradel The expressive power of second-order Horn logic," Proc. 8th Symp. on Theor.