2024 Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science
Mathematical Logic
- Academic unit or major
- Undergraduate major in Mathematical and Computing Science
- Instructor(s)
- Ryo Kashima
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 3-4 Tue / 3-4 Fri
- Class
- -
- Course Code
- MCS.T313
- Number of credits
- 200
- Course offered
- 2024
- Offered quarter
- 2Q
- Syllabus updated
- Mar 14, 2025
- Language
- Japanese
Syllabus
Course overview and goals
In mathematics class, we learn logic as the language of mathematics (for example, the usage of ∀ and ∃). In this course, we study logic itself mathematically, and we investigate the ability and limitation of logic. We also give an overview of non-classical logics (modal logic, intuitionistic logic, etc.) in computer science. In mathematics and computer science, logic is the foundation and an important tool. This course gives correct understanding of logic.
Course description and aims
At the end of this course, students will be able to
(1) write a logical formula that represents intended meaning correctly;
(2) have a correct understanding of the basic results of mathematical logic, as follows: propositional logic, predicate logic, syntax, semantics, Gentzen's natural deduction, Goedel's completeness theorem, Goedel's incompleteness theorem, compactness, decidability, undecidability, normal form of formulas, etc.; and
(3) have basic knowledge about non-classical logics (modal logics and intuitionistic logic) in computer science.
Keywords
propositional logic, predicate logic, Gentzen's natural deduction, Goedel's completeness theorem, Goedel's incompleteness theorem, modal logic, intuitionistic logic.
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
The course consists of lectures.
Homework assignments are given several times for checking your understanding.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction. | Problems in Chapter 1 of the textbook. |
| Class 2 | Natural deduction. | Problems in Chapter 2 of the textbook. |
| Class 3 | Natural deduction (2). | Problems in Chapter 2 of the textbook. |
| Class 4 | Natural deduction (3). | Problems in Chapter 2 of the textbook. |
| Class 5 | Truth, validity, and satisfiability of logical formulas. | Problems in Chapter 3 of the textbook. |
| Class 6 | Soundness of natural deduction. | Problems in Chapter 4 of the textbook. |
| Class 7 | Completeness of natural deduction (1). | Problems in Chapter 5 of the textbook. |
| Class 8 | Completeness of natural deduction (2). | Problems in Chapter 5 of the textbook. |
| Class 9 | Incompleteness Theorem (1). | Problems in Chapter 6 of the textbook. |
| Class 10 | Incompleteness Theorem (2). | Problems in Chapter 6 of the textbook. |
| Class 11 | Propositional logic. | Problems in Chapter 7 of the textbook. |
| Class 12 | Intuitionistic logic. | Problems in Chapters 10 and 11 of the textbook. |
| Class 13 | Modal logic (1). | Instructed in the class. |
| Class 14 | Modal logic (2). | Instructed in the class. |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
鹿島亮 『数理論理学』 朝倉書店 (ISBN: 978-4-254-11765-3).
Reference books, course materials, etc.
Instructed in the class.
Evaluation methods and criteria
Based on the final exam (50%) and exercise reports (50%) (or, exercise reports (100%) if the final exam is not available).
Related courses
- MCS.T201 ： Set and Topology I
- MCS.T204 ： Introduction to Computer Science
- MCS.T214 ： Theory of Automata and Languages
- MCS.T323 ： Theory of Computation
Prerequisites
No prerequisites.