情報論理学 / Logic for Computer Science

単位数: 2. 担当教員: 中野 圭介. 開講年度: 2024. 科目ナンバリング: TEI-PRI312J.

主要授業科目/Essential Subjects

○

授業の目的・概要及び達成方法等

Google Classroomのクラスコードは工学部Webページにて確認すること。
学部シラバス・時間割(https://www.eng.tohoku.ac.jp/edu/syllabus-ug.html)

# 目的
数理論理学は, 情報科学分野全般における数学的・理論的な思考技術の基本として, 更にまた，ソフトウェア科学における形式的技法の基礎として重要である. このような観点から, 情報科学の基礎知識としての数理論理学を修得することを目的とする．

# 概要
数理論理学の基本である命題論理および述語論理について，命題の形式化，モデル，証明論，健全性と完全性などについて講義する．

# 達成目標等
・自然言語で与えられた命題を論理式を用いて形式化する能力の習得
・推論の形式化についての理解
・数学的論証の過程を理解し，明示する能力の習得
・基礎的な数学的構造において，与えられたモデル上における命題の真偽を議論する能力の習得
・証明可能性と恒真性の同等性についての理解

授業の目的・概要及び達成方法等(Ｅ）

The class code for Google Classroom can be found on the Web site of
the School of Engineering:
https://www.eng.tohoku.ac.jp/edu/syllabus-ug.html (JP Only)

# Objective
Mathematical logic is important as the basis of mathematical and theoretical thinking in the field of information science in general, and also as the basis of formal methods and techniques in software science. From this point of view, the objective of this course is to acquire mathematical logic as a basic knowledge of information science.

# Overview
Students will learn basic concepts in propositional logic and predicate logic, including formalization of propositions and
predicates, their models, proof theory, and soundness and completeness.

# Goals
- Ability to formalize propositions in natural language as logic formulae.
- Understanding of formal inference.
- Knowledge of formal proofs and the ability to make formal proofs.
- Ability to determine the validly of a proposition in a variety of theories.
- Understanding of the provability, validity and their equivalence.

他の授業科目との関連及び履修上の注意

集合，関係，写像，（半）順序等の基礎数学の理解を仮定する

他の授業科目との関連及び履修上の注意(Ｅ）

We assume students' familiarity with the basic notions of mathematics, including sets, relations, functions, and (partial) orders.

授業計画

1．導入
2．命題論理式とモデル
3．論理的帰結
4．判断，推論規則，導出
5．自然演繹体系
6．証明図
7．自然演繹体系の健全性と完全性
8．古典論理と直観主義論理
9．帰納的定義と構造帰納法
10．述語論理式，量化子，スコープ，変数の自由出現と束縛出現，代入
11．述語論理式のモデル
12．述語論理の自然演繹体系（全称量化子に関する規則）
13．述語論理の自然演繹体系（存在量化子に関する規則）
14．述語論理の自然演繹体系の健全性と完全性．
15．期末試験およびまとめ

授業計画(Ｅ）

1. Introduction of mathematical logic
2. Propositional formulae and models
3. Logical entailment
4. Judgements, inference rules, and derivations
5. Natural deduction for propositional logic
6. Proof diagrams in natural dedection
7. Soundness and completeness of the natural deduction proof system
8. Classical logic vs. intuitionistic logic
9. Inducitive definition and structural induction
10. Predicate formulae, quantifiers, scoping, free and bound occurrences of variables, and substitutions
11. Models of predicate formulae
12. Natural deduction (for universal quantification)
13. Natural deduction (for existential quantification)
14. Soundness and completeness of the natural deduction for predicate logic
15. Final exam and summary

授業時間外学習

各回の講義内容を復習し，必要ならば疑問点について質問すること．

授業時間外学習（Ｅ）

Students are strongly recommended to review the lectures and highly encouraged to ask questions.

成績評価方法及び基準

小テストと試験による．ただし，試験の代わりにレポートを課す場合がある．

成績評価方法及び基準(Ｅ）

By short tests and the final exam. We may use a reporting assignment as their substitute.

教科書および参考書

• 記号論理入門　［新装版］, 前原昭二, 日本評論社 (2005) ISBN/ISSN: 9784535601444
• 情報科学における論理, 小野寛晰, 日本評論社 (1994) ISBN/ISSN: 9784535608146
• 論理学をつくる, 戸田山 和久, 名古屋大学出版会 (2000) ISBN/ISSN: 9784815803902
• 定理証明手習い, Daniel P. Friedman, Carl Eastlund, ラムダノート (2017) ISBN/ISSN: 9784908686023
• Logic and Structure, Dirk van Dalen, Springer (2013) ISBN/ISSN: 9781447145578

オフィスアワー

事前にメールでアポイントをとること．

オフィスアワー（Ｅ）

Make an appointment in advance by an email.