跳到主要內容

臺灣博碩士論文加值系統

(44.210.149.205) 您好!臺灣時間:2024/04/16 19:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳韋霖
研究生(外文):Wei-Lin Wu
論文名稱:探討漢彌爾頓路徑問題在給定額外述詞符號之二階邏輯下的表示法
論文名稱(外文):A Study on Expressing the Hamiltonian Path Problem inSecond-Order Logic with Some Additional Predicate Symbols
指導教授:趙坤茂
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:40
中文關鍵詞:命題邏輯述詞邏輯一階邏輯存在性二階邏輯漢彌爾頓路徑
外文關鍵詞:propositional logicpredicate logicfirst-order logicexistential second-order logicHamiltonian path
相關次數:
  • 被引用被引用:0
  • 點閱點閱:146
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
邏輯是數學裡專門探討敘述的推理演繹的一個分支,被認定為推理的研究。由於數學的
本質是由關於數學物件的敘述以及驗證這些敘述的證明所構成,因此,整個數學領域可以用
邏輯加以分析。而理論電腦科學的核心部分---演算法,其觀念的基礎就是計算的觀念,也是
個數學物件,可由邏輯分析之。在這篇論文裡,我們提供了邏輯的基本性質,並且利用這些
性質來研究一些計算問題,特別是漢彌爾頓路徑(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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top