なぜ「情報数学」か？ 離散数学 情報処理で処理の対象となるデータ、モノ、概念を 式として記述する 他人に伝えることができる 　　式として記述する 他人に伝えることができる それに基づいてプログラムが書ける その対象の分類、整理にも役立つ 集合，論理 対応，写像（関数） 無限を扱う手段としての帰納法 関係（e.g 大小関係） グラフ 離散数学

「情報数学」のホームページ http://www.info.kindai.ac.jp/math-cs

情報数学（第1回） 集合と論理の基礎

1.1 集合 数学的な議論をする際に、 議論の対象を明確にしておくための標準的な仕組み

集合とは 集合(set)とは、ものの集まりであって、以下の条件をみたすものをいう ある対象がその集合に属するかどうか明確に判断できる 資料1.1.1 集合とその要素 集合とは 集合(set)とは、ものの集まりであって、以下の条件をみたすものをいう ある対象がその集合に属するかどうか明確に判断できる その集合に属する2つの対象が同一のものかどうか判断できる 要素(element) 元(member) 明確に判断できる：　判断基準が存在する 𝑝∈𝐴：　𝑝は𝐴の要素である (𝑝 is an element of 𝐴) 𝑝∉𝐴：　𝑝は𝐴の要素でない (𝑝 is not an element of 𝐴) 集合は大文字、要素は小文字

資料1.1.1 集合とその要素 集合の外延的記法（枚挙法） 要素を列挙して集合を記述する際、その集合に属するすべての要素を順不同で、重複無く、「,」で区切って列挙し、全体を中カッコ「{」、「}」で囲んで記述する 　外延的記法(denotation)、枚挙法(enumeration)という 𝑉= 𝑎, 𝑒, 𝑖, 𝑜, 𝑢 𝑂 1 ={1, 3, 5, 7, 9}　 {}もOK？ 𝑎,𝑒,𝑖,𝑜,𝑢 と {𝑎,𝑖,𝑢,𝑒,𝑜} は同じ集合 {1, 1, 2, 1, 3, 2, 4} は不適切 𝑎,𝑏,𝑐,…,𝑧 {1, 2, 3,…, 99} は厳密には不適切だがよく使われる

有限集合 要素の数が特定できる集合を有限集合(finite set)、そうでない集合を無限集合(infinite set)という 資料1.1.2 集合の要素数 有限集合 要素の数が特定できる集合を有限集合(finite set)、そうでない集合を無限集合(infinite set)という 有限集合𝑆の要素数を 𝑆 または 𝑛(𝑆) と表記する 要素数の特定には集合の要件 (A) 要素であるかどうかが明確 (B) 要素間の区別が明確 が必要 𝑉= 𝑎,𝑒,𝑖,𝑜,𝑢 とすると 𝑉 =5 要素数が特定できないのは、 　いくらでも多くの要素が存在するから 無限集合

離散集合 すべての要素をとびとびに配置できる集合を離散集合(discrete set)と呼ぶ 枚挙法で全要素を列挙できる有限集合は離散集合 資料1.1.2 集合の要素数 離散集合 すべての要素をとびとびに配置できる集合を離散集合(discrete set)と呼ぶ 枚挙法で全要素を列挙できる有限集合は離散集合 𝒩= 0,1,2,3,… , 𝒵={…,−2,−1,0,1,2,…}は枚挙法（まがい）で全?要素を列挙できるので離散集合 𝒬（有理数の集合）は下図のように配置できるので離散集合 分母 0/1 1/1 2/1 3/1 4/1 -4/1 -3/1 -2/1 -1/1 0/2 1/2 2/2 3/2 4/2 -4/2 -3/2 -2/2 -1/2 0/3 1/3 2/3 3/3 4/3 -4/3 -3/3 -2/3 -1/3 0/4 1/4 2/4 3/4 4/4 -4/4 -3/4 -2/4 -1/4 分子

部分集合(包含関係) 集合𝐴のすべての要素が集合𝐵の要素でもあるとき、𝐴は𝐵の部分集合(subset)であるといい 𝐴⊆𝐵 と書く 資料1.1.3 部分集合 部分集合(包含関係) 集合𝐴のすべての要素が集合𝐵の要素でもあるとき、𝐴は𝐵の部分集合(subset)であるといい 𝐴⊆𝐵 と書く 𝐵は𝐴を包含(include)する: 𝐵⊇𝐴 𝐴⊆𝐵かつ𝐵⊆𝐴であるとき、𝐴と𝐵 は等しい(equal)といい 𝐴=𝐵 と書く 𝐴⊆𝐵 であり、 𝐵⊆𝐴 でないとき、𝐴は𝐵の真部分集合(proper subset)といい、𝐴⊆𝐵と書く 𝐴⊆𝐵 でも 𝐵⊆𝐴 でもないとき、 𝐴と𝐵は比較不能(incomparable) という

普遍集合、空集合 考慮するすべての対象からなる集合を普遍集合(universal set)とよび、一般的に 𝑈 資料1.1.3 部分集合 普遍集合、空集合 考慮するすべての対象からなる集合を普遍集合(universal set)とよび、一般的に 𝑈 と書く。対象領域、ドメイン(domain)ともいう ・普遍集合を𝒩とする ・普遍集合をすべての人からなる集合とし、𝑈と書く

ベン図（Venn Diagram） 𝒩 𝐴 𝐵 2 4 6 8 3 5 7 9 𝐴={1,2,3,4,5,6,7,8,9} 資料1.1.3 部分集合 ベン図（Venn Diagram） 𝒩　 2 4 6 8 𝐴 3 5 7 9 𝐵 𝐴={1,2,3,4,5,6,7,8,9} 𝐵={1,3,5,7,9}

普遍集合、空集合 考慮するすべての対象からなる集合を普遍集合(universal set)とよび、一般的に 𝑈 資料1.1.3 部分集合 普遍集合、空集合 考慮するすべての対象からなる集合を普遍集合(universal set)とよび、一般的に 𝑈 と書く。対象領域、ドメイン(domain)ともいう ・普遍集合を𝒩とする ・普遍集合をすべての人からなる集合とし、𝑈と書く 要素を持たない集合を空集合(empty set)とよび ∅ と書く 「{}」とも書く ∅ =0 やっぱり 0 は自然数に入れたい ∅ はあらゆる集合の部分集合

クイズ 以下のそれぞれについて (1) 集合としての要件は満たしているか (2) その場合普遍集合は何か (1) 集合としての要件は満たしているか (2)　その場合普遍集合は何か (3)　有限集合かどうか、その場合要素数はいくつか 100以下の自然数の集まり 大きな数の集まり 素数の集まり 近畿大学の学生の集まり 日本人の集まり

1.2 論理 数学的な議論を進めるための「基礎」（きまり）

命題 自然言語の文 数式 正しいか誤りであるかが明確な言明(statement)を命題(proposition)という。 資料1.2.1 命題と述語 命題 自然言語の文 数式 正しいか誤りであるかが明確な言明(statement)を命題(proposition)という。 正しいときは真(true)の命題 誤りのときは偽(false)の命題 真：　T, 1 偽：　F, 0 東大阪市は大阪府の一部である 東大阪市は大阪市の一部である 　1+1=2 　1×1=2 　0∈ 𝒩 + 　𝒩⊆𝒵 坂本龍馬は幕末一の傑物であった 　𝑥+1=4

資料1.2.1 命題と述語 述語 一つ以上の変数（自由変数という）を含む言明であって、それらの変数に値を代入することによって命題となるものを述語(predicate)という 変数の取る値の集合（変域、ドメイン）は明確でないといかん (8)　𝑥+1=4 𝑥に3を代入すると真 それ以外の値だと偽 　𝑄 𝑥 =「 𝑥 2 ≥4」 　𝑃 𝑥 =「𝑥は素数である」 　一部 𝑥,𝑦 =「𝑥は𝑦の一部である」 　𝐹𝑎𝑡ℎ𝑒𝑟 𝑥,𝑦 =「𝑥は𝑦の父親である」

集合の内包的記法 {𝑥∈𝐷∣𝑃 𝑥 } {𝑥∣𝑃 𝑥 } 𝑥 𝑥∈𝐷,𝑃 𝑥 資料1.2.2 述語を用いた集合の定義 集合の内包的記法 あるいは　 {𝑥∈𝐷∣𝑃 𝑥 } {𝑥∣𝑃 𝑥 } 𝑥 𝑥∈𝐷,𝑃 𝑥 により𝑃(𝑥) が真になるような 𝑥 の値（𝐷 の要素）すべてからなる集合を表す　集合の内包的記法(connotation)という 　{𝑛∣𝑛∈𝒩,𝑛<100} or {𝑛∈𝒩∣𝑛<100} 　{𝑥∣𝐹𝑎𝑡ℎ𝑒𝑟 徳川家康,𝑥 } 　{2𝑛+1∣𝑛∈𝒩} 　{2𝑛+1∣𝑛∈𝒩,𝑛<5} 　{𝑝/𝑞∣𝑝∈𝒵, 𝑞∈ 𝒩 + } (6)　 𝑚,𝑛 𝑚,𝑛∈𝒩,0≤𝑚,𝑛≤2 (7)　{𝑚×𝑛∣𝑚,𝑛∈𝒩, 0≤𝑚,𝑛≤2} 0 は自然数じゃないとしたいかも 𝒬 は情報科学では余り使わない

演習 以下の集合を内包的記法で記述しなさい {2𝑛∣𝑛∈𝒩, 𝑛<5} 10進１桁の偶数の集合 3の倍数の集合 素数の集合 　以下の集合を内包的記法で記述しなさい 10進１桁の偶数の集合 3の倍数の集合 素数の集合 X-Y平面上の下図のような点の集合 {2𝑛∣𝑛∈𝒩, 𝑛<5} {3𝑛∣𝑛∈𝒩} {𝑝∣𝑝∈𝒩,𝑝>1,𝑝は1と𝑝以外の約数を持たない} . . . . . {(𝑥,𝑦)∣𝑥,𝑦∈𝒩,𝑥≥𝑦}

1.3 基本論理演算、集合演算とその性質 こみいった集合、命題、述語を定義するための 論理演算と集合演算 表裏一体なのでセットで理解すべし

基本論理演算 命題（または述語）𝑃,𝑄 に対して 否定 ¬𝑃 （教科書では~𝑃） 論理和（選言） 𝑃∨𝑄 論理積（連言） 𝑃∧𝑄 資料1.3 基本論理演算、集合演算とその性質 基本論理演算 命題（または述語）𝑃,𝑄 に対して 　否定 ¬𝑃　（教科書では~𝑃） 　論理和（選言） 𝑃∨𝑄 　論理積（連言） 𝑃∧𝑄 もまた命題（述語） 𝑷 ¬𝑷 T F 𝑷 𝑸 𝑷∨𝑸 T F 𝑷 𝑸 𝑷∧𝑸 T F

集合の基本演算 普遍集合𝑈, その部分集合𝐴,𝐵 補集合(complement) 𝐴 和集合(union) 𝐴∪𝐵 資料1.3 基本論理演算、集合演算とその性質 集合の基本演算 普遍集合𝑈, その部分集合𝐴,𝐵 補集合(complement) 𝐴 和集合(union) 𝐴∪𝐵 積集合(product)、共通部分(intersection) 𝐴∩𝐵 𝑈 𝑈 𝑈 𝐴 𝐴 𝐵 𝐴 𝐵 補集合　 𝐴 和集合　𝐴∪𝐵 積集合　𝐴∩𝐵

論理演算、集合演算の諸性質 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 資料1.3 基本論理演算、集合演算とその性質 論理演算、集合演算の諸性質 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 𝑃∧¬𝑃=F 𝐴∩ 𝐴 =∅ 冪等律 𝑃∨𝑃=𝑃, 𝑃∧𝑃=𝑃 𝐴∪𝐴=𝐴 , 𝐴∩𝐴=𝐴 交換律 𝑃∨𝑄=𝑄∨𝑃 𝐴∪𝐵=𝐵∪𝐴 𝑃∧𝑄=𝑄∧𝑃 𝐴∩𝐵=𝐵∩𝐴 結合律 𝑃∨𝑄 ∨𝑅=𝑃∨(𝑄∨𝑅) 𝐴∪𝐵 ∪𝐶=𝐴∪(𝐵∪𝐶) 𝑃∧𝑄 ∧𝑅=𝑃∧ 𝑄∧𝑅 𝐴∩𝐵 ∩𝐶=𝐴∩(𝐵∩𝐶) 分配律 𝑃∧ 𝑄∨𝑅 = 𝑃∧𝑄 ∨(𝑃∧𝑅) 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪(𝐴∩𝐶) 𝑃∨ 𝑄∧𝑅 = 𝑃∨𝑄 ∧(𝑃∨𝑅) 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩(𝐴∪𝐶) 吸収律 𝑃∨ 𝑃∧𝑄 =𝑃 𝐴∪ 𝐴∩𝐵 =𝐴 𝑃∧ 𝑃∨𝑄 =𝑃 𝐴∩ 𝐴∪𝐵 =𝐴 ドモルガン律 ¬ 𝑃∨𝑄 =¬𝑃∧¬𝑄 𝐴∪𝐵 = 𝐴 ∩ 𝐵 ¬ 𝑃∧𝑄 =¬𝑃∨¬𝑄 𝐴∩𝐵 = 𝐴 ∪ 𝐵 同一律 𝑃∨F=𝑃, 𝑃∨T=T 𝐴∪∅=𝐴, 𝐴∪𝑈=𝑈 𝑃∧F=F, 𝑃∧T=𝑃 𝐴∩∅=∅, 𝐴∩𝑈=𝐴

論理演算と集合演算の対応 論理演算 T F ¬𝑃 𝑃∨𝑄 𝑃∧𝑄 集合演算 𝑈 ∅ 𝐴 𝐴∪𝐵 𝐴∩𝐵 資料1.3 基本論理演算、集合演算とその性質 論理演算と集合演算の対応 論理演算 T F ¬𝑃 𝑃∨𝑄 𝑃∧𝑄 集合演算 𝑈 ∅ 𝐴 𝐴∪𝐵 𝐴∩𝐵

論理演算、集合演算の諸性質 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 資料1.3 基本論理演算、集合演算とその性質 論理演算、集合演算の諸性質 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 𝑃∧¬𝑃=F 𝐴∩ 𝐴 =∅ 冪等律 𝑃∨𝑃=𝑃, 𝑃∧𝑃=𝑃 𝐴∪𝐴=𝐴 , 𝐴∩𝐴=𝐴 交換律 𝑃∨𝑄=𝑄∨𝑃 𝐴∪𝐵=𝐵∪𝐴 𝑃∧𝑄=𝑄∧𝑃 𝐴∩𝐵=𝐵∩𝐴 結合律 𝑃∨𝑄 ∨𝑅=𝑃∨(𝑄∨𝑅) 𝐴∪𝐵 ∪𝐶=𝐴∪(𝐵∪𝐶) 𝑃∧𝑄 ∧𝑅=𝑃∧ 𝑄∧𝑅 𝐴∩𝐵 ∩𝐶=𝐴∩(𝐵∩𝐶) 分配律 𝑃∧ 𝑄∨𝑅 = 𝑃∧𝑄 ∨(𝑃∧𝑅) 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪(𝐴∩𝐶) 𝑃∨ 𝑄∧𝑅 = 𝑃∨𝑄 ∧(𝑃∨𝑅) 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩(𝐴∪𝐶) 吸収律 𝑃∨ 𝑃∧𝑄 =𝑃 𝐴∪ 𝐴∩𝐵 =𝐴 𝑃∧ 𝑃∨𝑄 =𝑃 𝐴∩ 𝐴∪𝐵 =𝐴 ドモルガン律 ¬ 𝑃∨𝑄 =¬𝑃∧¬𝑄 𝐴∪𝐵 = 𝐴 ∩ 𝐵 ¬ 𝑃∧𝑄 =¬𝑃∨¬𝑄 𝐴∩𝐵 = 𝐴 ∪ 𝐵 同一律 𝑃∨F=𝑃, 𝑃∨T=T 𝐴∪∅=𝐴, 𝐴∪𝑈=𝑈 𝑃∧F=F, 𝑃∧T=𝑃 𝐴∩∅=∅, 𝐴∩𝑈=𝐴 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 𝑃∧¬𝑃=F 𝐴∩ 𝐴 =∅ 冪等律 𝑃∨𝑃=𝑃, 𝑃∧𝑃=𝑃 𝐴∪𝐴=𝐴 , 𝐴∩𝐴=𝐴 交換律 𝑃∨𝑄=𝑄∨𝑃 𝐴∪𝐵=𝐵∪𝐴 𝑃∧𝑄=𝑄∧𝑃 𝐴∩𝐵=𝐵∩𝐴 結合律 𝑃∨𝑄 ∨𝑅=𝑃∨(𝑄∨𝑅) 𝐴∪𝐵 ∪𝐶=𝐴∪(𝐵∪𝐶) 𝑃∧𝑄 ∧𝑅=𝑃∧ 𝑄∧𝑅 𝐴∩𝐵 ∩𝐶=𝐴∩(𝐵∩𝐶) 分配律 𝑃∧ 𝑄∨𝑅 = 𝑃∧𝑄 ∨(𝑃∧𝑅) 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪(𝐴∩𝐶) 𝑃∨ 𝑄∧𝑅 = 𝑃∨𝑄 ∧(𝑃∨𝑅) 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩(𝐴∪𝐶) 吸収律 𝑃∨ 𝑃∧𝑄 =𝑃 𝐴∪ 𝐴∩𝐵 =𝐴 𝑃∧ 𝑃∨𝑄 =𝑃 𝐴∩ 𝐴∪𝐵 =𝐴 ドモルガン律 ¬ 𝑃∨𝑄 =¬𝑃∧¬𝑄 𝐴∪𝐵 = 𝐴 ∩ 𝐵 ¬ 𝑃∧𝑄 =¬𝑃∨¬𝑄 𝐴∩𝐵 = 𝐴 ∪ 𝐵 同一律 𝑃∨F=𝑃, 𝑃∨T=T 𝐴∪∅=𝐴, 𝐴∪𝑈=𝑈 𝑃∧F=F, 𝑃∧T=𝑃 𝐴∩∅=∅, 𝐴∩𝑈=𝐴 対合律 ¬ ¬𝑃 =¬¬𝑃=𝑃 ( 𝐴 ) = 𝐴 =𝐴 相補律 𝑃∨¬𝑃=T 𝐴∪ 𝐴 =𝑈 𝑃∧¬𝑃=F 𝐴∩ 𝐴 =∅ 冪等律 𝑃∨𝑃=𝑃, 𝑃∧𝑃=𝑃 𝐴∪𝐴=𝐴 , 𝐴∩𝐴=𝐴 交換律 𝑃∨𝑄=𝑄∨𝑃 𝐴∪𝐵=𝐵∪𝐴 𝑃∧𝑄=𝑄∧𝑃 𝐴∩𝐵=𝐵∩𝐴 結合律 𝑃∨𝑄 ∨𝑅=𝑃∨(𝑄∨𝑅) 𝐴∪𝐵 ∪𝐶=𝐴∪(𝐵∪𝐶) 𝑃∧𝑄 ∧𝑅=𝑃∧ 𝑄∧𝑅 𝐴∩𝐵 ∩𝐶=𝐴∩(𝐵∩𝐶) 分配律 𝑃∧ 𝑄∨𝑅 = 𝑃∧𝑄 ∨(𝑃∧𝑅) 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪(𝐴∩𝐶) 𝑃∨ 𝑄∧𝑅 = 𝑃∨𝑄 ∧(𝑃∨𝑅) 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩(𝐴∪𝐶) 吸収律 𝑃∨ 𝑃∧𝑄 =𝑃 𝐴∪ 𝐴∩𝐵 =𝐴 𝑃∧ 𝑃∨𝑄 =𝑃 𝐴∩ 𝐴∪𝐵 =𝐴 ドモルガン律 ¬ 𝑃∨𝑄 =¬𝑃∧¬𝑄 𝐴∪𝐵 = 𝐴 ∩ 𝐵 ¬ 𝑃∧𝑄 =¬𝑃∨¬𝑄 𝐴∩𝐵 = 𝐴 ∪ 𝐵 同一律 𝑃∨F=𝑃, 𝑃∨T=T 𝐴∪∅=𝐴, 𝐴∪𝑈=𝑈 𝑃∧F=F, 𝑃∧T=𝑃 𝐴∩∅=∅, 𝐴∩𝑈=𝐴 算術演算 でおなじみ

結合律が成り立つので 普通はカッコを省略して 𝑃∪𝑄∪𝑅 𝑃 1 ∪ 𝑃 2 ∪…∪ 𝑃 𝑛 と記述する ドモルガン律も 資料1.3 基本論理演算、集合演算とその性質 結合律が成り立つので 普通はカッコを省略して 𝑃∪𝑄∪𝑅 𝑃 1 ∪ 𝑃 2 ∪…∪ 𝑃 𝑛 と記述する ドモルガン律も ¬ 𝑃 1 ∨ 𝑃 2 ∨…∨ 𝑃 𝑛 =¬ 𝑃 1 ∧¬ 𝑃 2 ∧…∧¬ 𝑃 𝑛 ¬ 𝑃 1 ∧ 𝑃 2 ∧…∧ 𝑃 𝑛 =¬ 𝑃 1 ∨¬ 𝑃 2 ∨…∨¬ 𝑃 𝑛 𝐴 1 ∪ 𝐴 2 ∪…∪ 𝐴 𝑛 = 𝐴 1 ∩ 𝐴 2 ∩…∩ 𝐴 𝑛 𝐴 1 ∩ 𝐴 2 ∩…∩ 𝐴 𝑛 = 𝐴 1 ∪ 𝐴 2 ∪…∪ 𝐴 𝑛 と覚えたほうが役に立つ

演習 以下の式を論理演算、集合演算の性質を利用して、な るべく単純な式に書き換えなさい ¬¬¬𝑃 =¬𝑃 ¬(¬ 𝑃∧𝑃 ∨𝑄) 𝐴∩ 𝐵 　以下の式を論理演算、集合演算の性質を利用して、な るべく単純な式に書き換えなさい ¬¬¬𝑃 ¬(¬ 𝑃∧𝑃 ∨𝑄) 𝐴∩ 𝐵 𝐴∩𝐵 ∪(𝐶∩ 𝐷 ) =¬𝑃 =¬ ¬𝑃∨𝑄 =¬¬𝑃∧¬𝑄=𝑃∧¬𝑄 = 𝐴 ∪ 𝐵 = 𝐴 ∪𝐵 = 𝐴∩𝐵 ∩ 𝐶∩ 𝐷 = 𝐴∩𝐵 ∩ 𝐶 ∪ 𝐷 =𝐴∩𝐵∩( 𝐶 ∪𝐷) = 𝐴∩𝐵∩ 𝐶 ∪(𝐴∩𝐵∩𝐷)