Logic and Computation I
This is an advanced undergraduate and graduate-level course in mathematical logic and theory of computation. Topics to be presented in the first semester include: computable functions, undecidability, propositional logic, NP-completeness, first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, modal logic and its decidability.
In the second semester, we will move on to second-order logic, modal $\mu$-calculus, infinite automata, descriptive set theory, admissible recursion, etc.
In the second semester, we will move on to second-order logic, modal $\mu$-calculus, infinite automata, descriptive set theory, admissible recursion, etc.
讲师
日期
2024年09月10日 至 12月19日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周二,周四 | 15:20 - 16:55 | A3-2-301 | ZOOM 08 | 787 662 9899 | BIMSA |
修课要求
Completion of undergraduate course on logic, set theory or automata theory is recommended. But all interested students are welcome.
课程大纲
Part 1. Introduction to Computational Theory
Fundamentals on theory of computation and computability theory (recursion theory) of mathematical logic, as well as the connection between them.
This part is the basis for the following lectures.
Part 2. Propositional Logic and Computational Complexity
The basics of propostional logic (Boolean algebra) and complexity theory including some classical results, such as the Cook-Levin theorem.
Part 3. First Order Logic and formal arithmetic
The basics of first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, the Ehrenfeucht-Fraisse theorem and Lindstrom's theorem.
Part 4. Modal logic
Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic. In "Logic and Computation II", we will move on to second-order logic and modal $\mu$-calculus.
Fundamentals on theory of computation and computability theory (recursion theory) of mathematical logic, as well as the connection between them.
This part is the basis for the following lectures.
Part 2. Propositional Logic and Computational Complexity
The basics of propostional logic (Boolean algebra) and complexity theory including some classical results, such as the Cook-Levin theorem.
Part 3. First Order Logic and formal arithmetic
The basics of first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, the Ehrenfeucht-Fraisse theorem and Lindstrom's theorem.
Part 4. Modal logic
Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic. In "Logic and Computation II", we will move on to second-order logic and modal $\mu$-calculus.
参考资料
[1] H.D. Ebbinghaus, H. Flum and W. Thomas, Mathematical Logic, 3rd ed., Springer 2021.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
听众
Advanced Undergraduate
, Graduate
视频公开
不公开
笔记公开
公开
语言
英文
讲师介绍
博士毕业于美国加州大学伯克利分校，之前就职于东京工业大学和东北大学，并担任15位博士生导师。2022年正式入职BIMSA。是数理逻辑和计算理论领域的国际知名学者，在反推数学和二阶算数模型领域开创了新的研究方法，取得了一系列奠基性的成果，并将这一研究方向引入日本，将日本的数理逻辑研究推向了世界水平。Tanaka教授最著名成果的是二阶算术和逆向数学，例如WKLo的Tanaka嵌入定理和守恒结果的Tanaka公式。