離散構造   [ GB10914, GB10924 ] Discrete Structures			対象：1学年
第3学期	金3・4 (1,2クラス:3A301, 3,4クラス:3A203)	2単位	担当教員：1,2クラス: 亀山幸義, 3,4クラス: 満保雅浩

概要

離散構造は，記号により表現される概念の総称であり， 論理，集合，関数，グラフ，代数系などを指す．離散構 造の中から，コンピュータサイエンスを支える数学的概 念として特に重要なものを取り上げ，基礎的な事項を学 ぶ．取り上げる題材は，論理と証明，集合と関数，関係 とグラフ, 帰納法と帰納的定義などである．なお，講義 内容に対する理解を深めるため，授業中に演習を行う．

学習・教育目標

コンピュータサイエンスにおいて必要とされる離散数学 の基礎的な用語と概念を理解する．また，これを題材と して，論理的思考，抽象化と形式化の手法，厳密な推論 方法を理解する．

キーワード

記号論理、集合、関数、関係、グラフ、木、帰納的定義.

Keywords

Symbolic Logic, Set, Function, Relation, Graph, Tree, Inductive Definition.

時間割

週	講義内容
１．５週	論理： 命題，論理記号，真理値表, 基本的な証明技法， 限量子 など。
１．５週	集合： 集合の構成法，集合の演算，包含関係，集合に関する推論 など。
１．５週	関数： 定義域・値域，単射・全射，合成関数，部分関数 など。
１．５週	関係： 二項関係，関係の性質，順序、同値関係 など
１．５週	グラフと木： 有向グラフ，無向グラフ，木 など
１．５週	帰納： 帰納的定義，様々なデータ構造，帰納法を使った証明 など
１週	その他：コンピュータサイエンスにおける離散構造　など

教材

講義ノートを Web上に公開する．

参考書籍

離散数学入門 （守屋悦朗 著、サイエンス社、2005年）
工学基礎：　離散数学とその応用（徳山豪 著、数理工学社、2002年）
情報基礎数学 (佐藤泰介ら著、昭晃堂、2007年）
Discrete Structures, Logic, and Computability, 2nd Edition (James L. Hein, Jones and Bartlett Publishers, 2002)

成績評価

出席，演習，期末試験により評価する．

教員メールアドレス

亀山: kamの後にアットマーク，その後にｃｓ．ｔｓｕｋｕｂａ．ａｃ．ｊｐ
満保: mambo の後にアットマーク，以後，亀山と同一

講義のWebページ

http://logic.cs.tsukuba.ac.jp/~kam/discrete/

オフィスアワー

亀山: 金11:00〜12:00, 総合研究棟B-1008

満保: 金11:00〜12:00, 場所は授業中に連絡する.