2026 (Current Year) Faculty Courses School of Computing Undergraduate major in Computer Science
Logic in Computer Science
- Academic unit or major
- Undergraduate major in Computer Science
- Instructor(s)
- Shin-Ya Nishizaki
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 5-6 Tue (S2-203) / 5-6 Fri (S2-203)
- Class
- -
- Course Code
- CSC.T261
- Number of credits
- 200
- Course offered
- 2026
- Offered quarter
- 3Q
- Syllabus updated
- Oct 1, 2026
- Language
- Japanese
Syllabus
Course overview and goals
Mathematical logic is the study of reasoning itself using rigorous mathematical techniques.
This course begins with propositional logic, focusing on logical connectives—conjunction, disjunction, implication, and negation—along with their mathematical properties. Next, we introduce first-order predicate logic, which incorporates universal and existential quantifiers binding individual variables, and extend Boolean semantics accordingly.
Throughout the lectures, logic is explored from both semantic and syntactic perspectives: standard model-theoretic semantics (such as Boolean models) and formal deductive systems (specifically, natural deduction). We also examine core meta-logical properties, including soundness and completeness, which bridge semantic truth and formal provability.
By mastering these fundamental concepts and formalization techniques, students will acquire the theoretical foundation essential for computer science applications, particularly formal verification and the foundations of programming languages.
Course description and aims
Upon completing this course, students will gain fundamental knowledge of mathematical logic essential for programming language theory and symbolic artificial intelligence. Students will be able to formulate statements within formal frameworks, understand the rigorous definition of truth and falsity in mathematical logic, and clarify the relationship between syntax and semantics through propositional and first-order predicate logic. Furthermore, students will develop the ability to treat reasoning itself as a mathematical object and carry out formal derivations.
Keywords
Mathematical logic, reasoning, propositional logic, first-order predicate logic, Boolean model, functional completeness, conjunctive normal form, disjunctive normal form, duality between conjunction and disjunction, natural deduction, soundness, completeness, compactness, structure, model
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
Each class consists of lectures covering fundamental topics and hands-on exercises provided in the course materials to reinforce understanding.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction to Mathematical Logic: history of mathematical logic and the relationship between mathematical logic and computer science |
Gain an understanding of the history of mathematical logic and the relationship between mathematical logic and computer science |
| Class 2 | Syntax of propositional logic: proposition, structural |
Gain an understanding of the syntax of propositional logic, especially structural induction of propositions |
| Class 3 | Intuitive introduction of propositional logic's semantics: propositions as polynomials |
Gain an intuitive understanding of Boolean semantics of propositional logic |
| Class 4 | Formal introduction of propositional logic's semantics: valuation, semantic function, tautology, satisfiability, unsatisfiability |
Gain a formal understanding of the semantics of propositional logic. |
| Class 5 | Exercises of propositional logic's semantics I |
Understanding how to prove propositional logic's properties |
| Class 6 | Mathematical properties of propositional logic: functional completeness, disjunctive normal form, conjunctive normal form, and duality |
Understanding the theoretical properties on the propositional logic |
| Class 7 | Exercises of propositional logic's semantics II |
Understanding how to prove propositional logic's properties |
| Class 8 | Deductive system for propositional logic: natural deduction and formalization of mathematical proofs. |
Understanding formalism of propositional logic's proof in the natural deduction |
| Class 9 | Examples of formal proofs in natural deduction |
Understanding how to write formal proofs in the natural deduction |
| Class 10 | Soundness theorem of propositional logic and natural deduction |
Understanding the soundness theorem of propositional logic and natural deduction |
| Class 11 | Completeness theorem of propositional logic and natural deduction |
Understanding the completeness theorem of propositional logic and natural deduction |
| Class 12 | Exercises of natural deduction in propositional logic. |
Learning how to handle the natural deduction |
| Class 13 | Syntax of first-order predicate logic: first-order language and similarity type |
Understanding the first-order language and similarity type |
| Class 14 | The semantics of first-order predicate logic: structures and models |
Understanding the semantics of first-order predicate logic |
| Class 15 | The semantics of first-order predicate logic: structures and models |
Understanding the semantics of first-order predicate logic |
| Class 16 | Mathematical properties of first-order predicate logic: prenex normal form |
Understanding prenex normal forms |
| Class 17 | Examples of semantics of first-order predicate logic |
Understanding the semantics of the first-order predicate logic and its theoretical structure. |
| Class 18 | A deductive system of first-order predicate logic: natural deduction |
Understanding of natural deduction for the first-order predicate logic |
| Class 19 | A deductive system of first-order predicate logic: natural deduction |
Understanding of natural deduction for the first-order predicate logic |
| Class 20 | Soundness of the first-order predicate logic |
Understanding of soundness theorem of first-order predicate logic and natural deduction |
| Class 21 | Exercises of natural deduction in the first-order predicate logic |
Understanding of resolution |
| Class 22 | Advanced topics on the first-order predicate logic |
Understanding of importance of Löwenheim-Skolem's theorem |
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)
Course materials will be given in class.
Reference books, course materials, etc.
Logic and Structure, 4th edition, Dirk van Dalen著 Springer-Verlag,
論理と計算のしくみ, 萩谷昌己・西崎真也著、岩波書店
Evaluation methods and criteria
The course is conducted through lectures introducing key theoretical concepts, supplemented by exercises in the lecture materials to deepen understanding. Students' achievement will be assessed based on the final examination and submitted assignments.
Related courses
- CSC.T241 ： Fundamentals of Computing
- XCO.B101 ： Foundations of Computing 1
- XCO.B102 ： Foundations of Computing 2
- CSC.T272 ： Artificial Intelligence
- MCS.T404 ： Logical Foundations of Computing
Prerequisites
Fundamental knowledge on discrete mathematics and naïve set theory
Other
If enrollment must be restricted due to classroom capacity or other administrative constraints, priority will be given to students in the Department of Computer Science.