臺灣博碩士論文加值系統

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

1 Introduction 1
1.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Categories inside Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Computational Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Topics on Propositional Logic 4
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Equvalence between Propositions . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Topics on Predicate Logic 19
3.1 First-order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.3 Deduction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.4 Weakness of First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Second-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Graph-Theoretic Problems as Expressed in Logical Formulae 31
4.1 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 The Successor Function in Graph-Theoretic Problems . . . . . . . . . . . . . . . 32
5 Concluding Remarks 37
Bibliography 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-order
logic," 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 ACM
Symp. 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. Gradel 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, fth
edition, 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. Godel Die Vollstandigkeit der Axiome der Logischen Funktionenkalkuls" (The completeness
of the axioms of the logical function calculus), Monat, Math. Physik, 37, pp. 349
{ 360, 1930.
[15] K. Godel Uber formal unentscheidbare Satze der Principia Mathematica und verwandter
Systeme" (On formally undecidable theorems in Principia Mathematica and related systems),
Monatschefte fur 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++, Computer
Science 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, Prentice
Hall Series in Arti cial Intelligence, 2003.