請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9022完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂 | |
| dc.contributor.author | Wei-Lin Wu | en |
| dc.contributor.author | 吳韋霖 | zh_TW |
| dc.date.accessioned | 2021-05-20T20:06:51Z | - |
| dc.date.available | 2009-08-14 | |
| dc.date.available | 2021-05-20T20:06:51Z | - |
| dc.date.copyright | 2009-08-14 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-08-11 | |
| dc.identifier.citation | [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. Gr adel 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. G odel Die Vollst andigkeit der Axiome der Logischen Funktionenkalk uls' (The completeness of the axioms of the logical function calculus), Monat, Math. Physik, 37, pp. 349 { 360, 1930. [15] K. G odel Uber formal unentscheidbare S atze der Principia Mathematica und verwandter Systeme' (On formally undecidable theorems in Principia Mathematica and related systems), Monatschefte f ur 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. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9022 | - |
| dc.description.abstract | 邏輯是數學裡專門探討敘述的推理演繹的一個分支，被認定為推理的研究。由於數學的
本質是由關於數學物件的敘述以及驗證這些敘述的證明所構成，因此，整個數學領域可以用 邏輯加以分析。而理論電腦科學的核心部分---演算法，其觀念的基礎就是計算的觀念，也是 個數學物件，可由邏輯分析之。在這篇論文裡，我們提供了邏輯的基本性質，並且利用這些 性質來研究一些計算問題，特別是漢彌爾頓路徑(Hamiltonian Path)這個圖型理論的問題。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-20T20:06:51Z (GMT). No. of bitstreams: 1 ntu-98-R96922105-1.pdf: 536197 bytes, checksum: 80a5207073547b08d0faaf36ab396fcf (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 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 | |
| dc.language.iso | en | |
| dc.title | 探討漢彌爾頓路徑問題在給定額外述詞符號之二階邏輯下的表示法 | zh_TW |
| dc.title | A Study on Expressing the Hamiltonian Path Problem in
Second-Order Logic with Some Additional Predicate Symbols | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 徐熊健,張雅惠 | |
| dc.subject.keyword | 命題邏輯,述詞邏輯,一階邏輯,存在性二階邏輯,漢彌爾頓路徑, | zh_TW |
| dc.subject.keyword | propositional logic,predicate logic,first-order logic,existential second-order logic,Hamiltonian path, | en |
| dc.relation.page | 40 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2009-08-11 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf | 523.63 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。