earth
湘南 理工学舎

  集 合 (set)

 --目 次--
1.集合とは
2.集合の表し方(例)
3.代表的な集合
4.集合とベン図
5.ドモルガンの法則
6.論理演算子
7.集合代数式

1.集合とは

・集合とはものの集まり。 
・集合を構成するものを要素(element)(または元)という。
a ∈ b:「a は集合b の要素である」 または「a はb に属する」という。 (属さない記号は: )

2.集合の表し方(例)

・{ 2, 4, 6, 8, … }:2で割れる正の整数の集合。
以下の表し方は {x |条件} の形をとり、要素の条件を示している。
・{ x | P(x)} :要素x について 条件P(x)が与えられて、P(x) を満たす集合。
・{ x | x=2y, y ∈ ℕ }:自然数yに対し x=2y を満足する集合
・{ x | x∈A or x∈ B}: A ∪ B:和集合の定義式
 (or:論理和 以下参照)

3.代表的な集合(set/collection)

代表的な集合をベン図 (集合の関係を図式化したもの)を用いて表しました。 また図では集合全体を 「W」としています。

(1)和集合:A∪B (A cup(カップ) B)
(union/sum of set)
A∪B = AまたはB = A or B 

(2)積集合:A ∩ B (Acap(キャップ)B)
(product set)
A∩B= AかつB= A and B 

(3)部分集合:B ⊆ A BはAの部分集合
(subset)
これは A∩B=B ともいえる。

(4)補集合:\( \overline{ A } \) (上バーは notA のこと)
(complement/complementary set)
Aには属さないがWに属する全ての要素の集合。
図(4)の差集合 W∖A (=W-A)でもある。 全体集合Wの明記がなければ補集合\( \overline{ A } \)と表す。

(5)補集合:\( \overline{ B } \)… その他(4)と同様

(6)上記(4)と(5)の和集合 (\( \overline{A} \)) ∪ (\( \overline{B} \))
これは \( \overline{A∩B} \) とも書ける。(後述するドモルガンの法則による)

(7)差集合 A∖B (=A-B) ( = A ∩\( \overline{B} \)でもある)

(8)差集合 A∖B (=A-B) ( = A ∩\( \overline{B} \)でもある)

(9)排他的論理和(参考)
  (exclusive or)
(A∩\( \overline{B} \))∪(\( \overline{A}\)∩B)=(A∪B)∩(\( \overline{A} \)∪\( \overline{B} \))
  =(A∪B)/(A∩B)…差集合
最後の式を言葉にすると「AまたはB、ただし AかつB は含まない」となる。

(10)空集合:要素がない集合のこと。
記号は \( \emptyset \) (または Ø ファイ)
例 A={1,2,3} B={4,5,6}のとき
AとBの和集合は空集合… A∪B= \( \emptyset \) 

(11)真部分集合:B⊂A 
BはAの部分集合かつ A≠B である集合。

4.集合とベン図(set and Ven diagram)

(1)和集合

(1)和集合:A∪B

(2)積集合

(2)積集合:A∩B
(AとBの共通部分)

(3)部分集合

(3)部分集合:B ⊆ A
(BはAの部分集合)

 
  
(4)Aの補集合

(4) Aの補集合:\( \overline{ A } \)
差集合 W∖Aでもある

(5) Bの補集合

(5) Bの補集合:\( \overline{ B } \)
差集合 W∖Bでもある。

(4)と(5)の和集合

(6) 左図(4)と(5)の和集合
(\( \overline{A} \)) ∪ (\( \overline{B} \))

   

  
(7)差集合 A∖B

(7)差集合 A∖B
(=A-B)

(8)差集合 A∖B

(8)差集合 A∖B
(=A-B)

(9)排他的論理和

(9)排他的論理和
(A∪B)∩(\( \overline{A} \)∪\( \overline{B} \))

   

注:排他的論理和とはA,Bのどちらかが真のとき成り立つ。(両方が真の部分は偽(空集合))
 (時間のある方は、ベン図を書いてみて下さい…理解できます。)

5.ドモルガンの法則(De Morgan's laws)

・(\( \overline{A ∩ B } \) = (\( \overline{A} \)∪\( \overline{B} \))   ・(\( \overline{A ∪ B } \) = (\( \overline{A} \)∩\( \overline{B} \))
 この法則は1800年代のものですが、回路の簡素化/簡略化ができることからコンピュータ、電子機器の回路設計に応用されています。

6.論理演算子記号(Logical operation symbol)

以下は集合演算と似ている論理の演算子です。 関連したWebページでよく見かけるので記載しました。
・論理和(または/or) 「∨」, 「+」
・論理積(かつ/and)  「∧」, 「⋅」
・否定 「¬」 
・排他的論理和 「⊕」 「\(\veebar \)」
・補集合 変数記号の右上添字C (例: \( {A^C} \) )   

7.集合代数式(algebra of sets)

集合に関する公式を含め一般式を参考として記載しておきます。
・A∪B= B∪A ・A∩B= B∩A …交換法則
・A∪(B∪C)= (A∪B)∪C
・A∩(B∩C)= (A∩B)∩C …結合法則
・A∪(B∩C)=(A∪B)∩(A∪C)
・A∩(B∪C)=(A∩B)∪(A∩C) …分配法則
・A∪A=A
・A∩A=A 
・A ⊆ A∪B
・B ⊆ A∪B
・A∩B ⊆ A
・A∩B ⊆ B
・A,B ⊆ C なら A∪B ⊆ C
・C ⊆ A,B なら C ⊆ A∩B
・A∪(A∩B)=A
・A∩(A∪B)=A
・(A/B)∪(A∩B)=A ((A-B)∪(A∩B)=A)
・A ⊆ B なら(A/B)= Ø(空集合) 
・Ø/A (=Ø-A) = Ø(空集合) 


coffe

[コーヒーブレイク/閑話]!

 上記にとりあげたドモルガンの法則、排他的論理和は、ブール代数の論理演算にも登場します。 ブール代数は1854年に英国のGerge Booleによって提唱されました。 …この時代はちょうど英国の産業革命の終り頃です…まだコンピュータは存在していません。 ブール代数は変数の値が「0」と「1」の二つのうちいずれしかとりえない離散的な変数を用いる論理です。 コンピュータの理解にはかかせないもの、また無駄を省いた合理的な論理回路の設計にも重要です。 コンピュータの元祖として機械式計算機が1600年代に登場し、第二次世界大戦前、戦中では英国、ドイツ、米国で暗号解読などのため開発がすすめられていましたが、ブール代数の理論を具体化したものは米国のベル研究所でリレー式計算機でした。 それ以降、論理回路の構成装置が真空管、トランジスタ、LSIというように集積度が高められ、高性能(高速、大容量)なコンピュータに進化してきました。
さて、今、量子コンピュータの研究が進められていますが、どのようにして、どのようなコンピュータができるのか興味を惹かれますね!