積集合とは？せきしゅうごう

背景

「条件を2つとも満たすもの」を言葉だけで扱うと、条件が3つ4つと増えたときに、どれが残るのかを正しく追えなくなる。集合として記号で書けば、式の変形で結果を確かめられる。プログラムの条件式のAND、データベースの検索条件、Web検索の絞り込みは、どれもこの積集合の計算をしている。

具体例

SUUMOで賃貸物件を探すとき、「駅徒歩10分以内」と「家賃8万円以下」の2つの条件で絞り込むと、表示されるのは両方の条件を満たす物件だけになる。駅徒歩10分以内の物件の集合をA、家賃8万円以下の物件の集合をBとすれば、画面に出るのはA∩Bである。条件を足すほど結果が減るのは、積集合が元のどちらの集合よりも大きくならないからである。

試験での引っ掛け

記号の∩（積集合）と∪（和集合）の取り違えが最も多い。∩は「かつ」（論理積のAND：両方を満たす＝重なり）、∪は「または」（論理和のOR：どちらかを満たす＝全体）と、読み方と論理演算に結び付けて覚える。また集合では、∩は∪に対して、∪は∩に対して、どちらも分配できる。(A∪B)∩C＝(A∩C)∪(B∩C)だけでなく、(A∩B)∪C＝(A∪C)∩(B∪C)も成り立つ。足し算と掛け算の感覚で「後者は成り立たない」と判断させる選択肢に注意する。要素数では、|A∪B|＝|A|＋|B|−|A∩B|のように、重なりの分を引く。

関連用語

• 和集合
• 補集合
• ベン図
• ド・モルガンの法則

出た過去問

• 出典：平成29年度 春期 基本情報技術者試験 午前 問1（IPA）

  集合A，B，Cを使った等式のうち，集合A，B，Cの内容によらず常に成立する等式はどれか。ここで，∪は和集合，∩は積集合を示す。

  正解：(A∩C)∪(B∩C) = (A∪B)∩C

  要点：∩は∪に分配できる：(A∪B)∩C=(A∩C)∪(B∩C)

  集合演算には「∩は∪に対して分配できる」という分配法則があり、(A∪B)∩C は (A∩C)∪(B∩C) に等しくなります。これは要素xがCに属し、かつAまたはBに属する、という条件を書き換えただけなので、A・B・Cの中身に関係なく常に成立します。他の等式は、たとえばA={1}、B={}、C={1}のような具体例を1つ当てはめるだけで両辺が食い違い、反例が作れます。

  この問題の解説ページを見る →