論理数学
担当者上出 哲広教員紹介
学年・開講期1年次 前期  [理工学部 情報電子工学科]
科目の種類専門基礎
区分・単位必修 2単位
科目ナンバー3A111

授業の概要(ねらい)

 本科目では、情報科学の基礎としての論理と集合について学習します。論理に関連する事柄としては、命題論理と述語論理の意味論と形式体系について学習します。意味論と形式体系の対応関係を表した定理として、健全性定理と完全性定理があります。また、命題論理と述語論理の論理式の標準形についても学習します。集合に関連する事柄としては、集合、写像、関係、順序、束およびブール代数について学習します。まず、集合を用いて写像を定義でき、逆に写像を用いて集合を定義できるということを学習します。次に、集合を用いて関係を定義し、関係の特別なケースとして同値関係と順序を定義します。次に、順序を持つ集合として順序集合を定義し、代数構造である束との関係を学習します。束の特別なケースがブール代数です。ブール代数は命題論理の代数的意味論を与えるものでもあり、命題論理の代数的な別表現とみなすこともできます。
 本科目は、コンピュータの基礎である論理回路や人工知能の基礎である論理プログラミングや知識ベースシステムの構成を理解するために必要となる科目です。命題論理やブール代数はコンピュータ内で用いられている演算の基礎を与える体系です。述語論理は論理プログラミングを基にした知識ベースやwebオントロジー言語などの基礎として用いられています。また、本科目は、コンピュータ(=計算する機械)の基礎理論である計算論(計算可能性理論および計算複雑さの理論)を理解するために必要な科目です。集合、写像および関係の概念は計算の停止性や一意性を議論するために必要となる概念です。また、本科目で学ぶ対角線論法や帰納法といった基本的な証明手法は、コンピュータの原理的な限界を証明したり、効率の良いプログラムを記述したりするのに必要になるものです。
 本科目は、情報電子工学科における以下のディプロマポリシーに関連する科目です。「自然科学の基礎的な知識を持ち、それを課題解決に活用することができる」。「ソフトウェアとしての情報システムを構築し運用することができる」。「幅広いメディア表現技術を応用し機能的で使い易いマルチメディアコンテンツを制作することができる」。本科目は、JABEE対応プログラムの必修科目であり、学習・教育到達目標「3.コンピュータ科学に関連する数学と数学を中心とした理工学の基礎知識を応用できる」における中項目「3-1. コンピュータ科学の基礎である集合と論理、推論と証明、写像の理解と応用力の育成」に対応しています。

授業の到達目標

 本科目では、論理と集合における以下の項目について理解することを目標とします。(1)命題論理の意味論と形式体系。(2)述語論理の意味論と形式体系。(3)論理式の標準形。(4)集合と写像。(5)順序集合。(6)束とブール代数。学生自身が、上記項目について説明できるようになることを目標とします。

成績評価の方法および基準

 期末試験(30パーセント)、中間試験(20パーセント)、小テスト(50パーセント、LMSで実施)により成績を評価します。100点満点で60点以上を合格とします。試験終了後、解答の一部をビデオコンテンツなどで解説します。また、希望者には、試験終了後にオフィスアワーなどを利用して試験結果に関連する個別指導を実施します。

教科書・参考文献

種別書名著者・編者発行所
教科書 なし。LMS上に教材(ビデオコンテンツ、オンラインテスト、講義スライド、その他学習資料)を提示します。
参考文献論理と集合から始める数学の基礎嘉田勝(著)日本評論社(ISBN: 978-4535784727)
参考文献例題で学ぶ集合と論理鈴木登志雄(著)森北出版株式会社(ISBN: 978-4627061910)
参考文献Logic and structure (5th edition)Dirk van DalenSpringer(ISBN: 978-1447145578)

準備学修の内容

 本科目では、毎回の授業で演習問題を出題します。それら問題を解くことによって、予習・復習に努めてください。また、各回において、LMS上で小テスト(オンラインテスト)を実施します。各回の授業後にこの小テストを受験して下さい。授業のビデオコンテンツがLMS上で配信されます。授業で理解できなかった内容についてはこれらビデオコンテンツで復習して下さい。また、授業の発展的内容に関するビデオコンテンツもLMS上で配信されます。さらに知識を深めたい場合は、それらビデオコンテンツを視聴して下さい。毎回の授業の教材(ビデオコンテンツ、オンラインテスト、講義スライドおよび補足資料)は、だいたい1週間前にLMSに提示されます。
 各回の予習と復習の目安は以下の通りです。予習として、次回の講義スライドおよびその他講義資料に目を通して疑問点をまとめて下さい(30分程度)。また、それら疑問点については授業前にオフィスアワーなどを利用して講師に質問することを勧めます。復習として、各回の小テストの受験、各回の演習問題への解答、および各回において授業で分からなかった部分に関するビデオコンテンツ視聴による復習を実施して下さい(2時間30分程度)。

その他履修上の注意事項

 授業ではLMSを使用します。各回の学習資料がLMS上に提示されます。授業には必ずこれら学習資料をプリントアウトして持ち込んで下さい。また、授業期間中にLMSでアンケートを実施します。

授業内容

授業内容
第1回導入: 論理に関する基礎事項・本講義の概要
第2回命題論理(1): 命題・論理式・真理値表・付値・トートロジー
第3回命題論理(2): 論理的に同値な論理式・論理和標準形・論理積標準形
第4回命題論理(3): 構文論・意味論・シーケント計算・シーケント計算による証明
第5回命題論理(4): 健全性定理・完全性定理・カット除去定理
第6回述語論理(1): 量化記号・述語論理の論理式
第7回述語論理(2): 述語論理の意味論・恒真な論理式・冠頭標準形・述語論理の形式体系
第8回述語論理(3): ゲーデルの完全性定理・コンパクト性定理・中間試験
第9回集合と写像(1): 集合・基数・集合演算
第10回集合と写像(2): 写像・全射・単射・全単射
第11回集合と写像(3): 無限集合・可算集合・非可算集合・対角線論法
第12回関係: 関係・同値関係・順序
第13回束とブール代数: 束・ブール代数
第14回論理学の歴史とコンピュータの起源: ゲーデルの不完全性定理・チャーチのテーゼ
第15回発展的話題・まとめ・期末試験