2024 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 / 5-6 Fri
- Class
- -
- Course Code
- CSC.T261
- Number of credits
- 200
- Course offered
- 2024
- Offered quarter
- 3Q
- Syllabus updated
- Mar 17, 2025
- Language
- Japanese
Syllabus
Course overview and goals
Mathematical logic is the study of reasoning in mathematics. We analyze mechanisms of mathematical reasoning using mathematical techniques. In this course, we first present propositional logic, which is a logical framework focusing on logical connectives such as conjunction, disjunction, implication, and negation and show their mathematical properties. Then, we introduce first-order predicate logic, in which we can use universal and existential quantifiers binding individual parts. We extend the Boolean model of propositional logic to the one for first-order predicate logic. In this course, we study logic not only from Boolean semantics but also from a deductive system, that is, natural deduction. The soundness and completeness properties between the Boolean model and natural deduction are also explained in this course. We learn fundamental knowledge and the technique of formalization in mathematical logic, which is also applied to computer science, especially the theoretical study of programming languages.
Course description and aims
You can learn fundamental knowledge of the mathematical logic of computer science, which will be indispensable for the theory of programming languages and the symbolic approach in artificial intelligence. You will understand the relationship between the syntax aspect and the semantical aspect in mathematical logic, through cases of propositional and first-order predicate logic. Furthermore, you will learn how the notion of truth and false in mathematical statements is defined mathematically and the reasoning in mathematical science including computer science.
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
We will give lectures in this course. We will assign exercises in several classes, which help you to understand the material covered in the lecture.
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.
Dirk van Dalen: Logic and Structure, 4th edition, Springer-Verlag
Evaluation methods and criteria
Reports (50%) and final examination (50%)
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 it is necessary to limit the number of students in the course, priority may be given to students in the department of computer science.