離散数学-セット

ドイツの数学者 G. Cantorセットの概念を導入しました。彼は、特定のルールまたは説明によって選択された明確で区別可能なオブジェクトのコレクションとしてセットを定義しました。

Set理論は、カウント理論、関係、グラフ理論、有限状態機械など、他のいくつかの研究分野の基礎を形成します。この章では、のさまざまな側面について説明します。Set Theory。

セット-定義

セットは、さまざまな要素の順序付けられていないコレクションです。セットは、セットブラケットを使用してその要素をリストすることにより、明示的に記述できます。要素の順序が変更されたり、セットのいずれかの要素が繰り返されたりしても、セットは変更されません。

セットのいくつかの例

すべての正の整数のセット
太陽系のすべての惑星のセット
インドのすべての州のセット
アルファベットのすべての小文字のセット

セットの表現

セットは2つの方法で表すことができます-

名簿または表形式
集合の内包的記法

名簿または表形式

セットは、それを構成するすべての要素をリストすることによって表されます。要素は中括弧で囲まれ、コンマで区切られます。

Example 1 −英語のアルファベットの母音のセット、$ A = \ lbrace a、e、i、o、u \ rbrace $

Example 2 −10未満の奇数のセット$ B = \ lbrace 1,3,5,7,9 \ rbrace $

集合の内包的記法

セットは、セットの要素に共通するプロパティを指定することによって定義されます。セットは$ A = \ lbrace x：p（x）\ rbrace $として記述されます

Example 1 −集合$ \ lbrace a、e、i、o、u \ rbrace $は次のように記述されます−

$ A = \ lbrace x：\ text {xは英語のアルファベットの母音} \ rbrace $

Example 2 −セット$ \ lbrace 1,3,5,7,9 \ rbrace $は次のように記述されます−

$ B = \ lbrace x：1 \ le x \ lt 10 \ and \（x \％2）\ ne 0 \ rbrace $

要素xが任意のセットSのメンバーである場合、それは$ x \ in S $で示され、要素yがセットSのメンバーでない場合、それは$ y \ notin S $で示されます。

Example− $ S = \ lbrace1、1.2、1.7、2 \ rbrace、1 \ in S $であるが、$ 1.5 \ notin S $の場合

いくつかの重要なセット

N −すべての自然数のセット= $ \ lbrace1、2、3、4、..... \ rbrace $

Z −すべての整数のセット= $ \ lbrace .....、-3、-2、-1、0、1、2、3、..... \ rbrace $

Z⁺ −すべての正の整数のセット

Q −すべての有理数の集合

R −すべての実数のセット

W −すべての整数のセット

セットのカーディナリティ

$ | S | $で表される集合Sのカーディナリティは、集合の要素の数です。この番号は、基数とも呼ばれます。セットに無限の数の要素がある場合、そのカーディナリティは$ \ infty $です。

Example− $ | \ lbrace 1、4、3、5 \ rbrace | = 4、| \ lbrace 1、2、3、4、5、\ dots \ rbrace | = \ infty $

XとYの2つのセットがある場合、

$ | X | = | Y | $は、同じカーディナリティを持つ2つのセットXとYを示します。Xの要素数がYの要素数と正確に等しい場合に発生します。この場合、XからYへの全単射関数「f」が存在します。
$ | X | \ le | Y | $は、セットXのカーディナリティーがセットYのカーディナリティー以下であることを示します。Xの要素数がYの要素数以下の場合に発生します。ここでは、XからYへの単射関数 'f'が存在します。
$ | X | \ lt | Y | $は、セットXのカーディナリティがセットYのカーディナリティよりも小さいことを示します。Xの要素数がYの要素数より少ない場合に発生します。ここで、XからYへの関数 'f'は単射関数ですが、全単射ではありません。
$ If \ | X | \ le | Y | $および$ | X | \ ge | Y | $、次に$ | X | = | Y | $。セットXとYは、一般に同等のセットと呼ばれます。

セットの種類

セットは多くのタイプに分類できます。そのうちのいくつかは、有限、無限、サブセット、ユニバーサル、適切、単集合などです。

有限集合

一定数の要素を含む集合は、有限集合と呼ばれます。

Example− $ S = \ lbrace x \：| \：x \ in N $および$ 70 \ gt x \ gt 50 \ rbrace $

無限セット

無限の数の要素を含むセットは、無限セットと呼ばれます。

Example− $ S = \ lbrace x \：| \：x \ in N $および$ x \ gt 10 \ rbrace $

サブセット

Xのすべての要素がセットYの要素である場合、セットXはセットYのサブセット（$ X \ subseteq Y $として記述）です。

Example 1− $ X = \ lbrace 1、2、3、4、5、6 \ rbrace $および$ Y = \ lbrace 1、2 \ rbrace $とします。ここで、セットYのすべての要素がセットXにあるため、セットYはセットXのサブセットです。したがって、$ Y \ subseteq X $と書くことができます。

Example 2− $ X = \ lbrace 1、2、3 \ rbrace $および$ Y = \ lbrace 1、2、3 \ rbrace $とします。ここで、セットYのすべての要素がセットXにあるため、セットYはセットXのサブセット（適切なサブセットではありません）です。したがって、$ Y \ subseteq X $と書くことができます。

適切なサブセット

「適切なサブセット」という用語は、「のサブセットであるが等しくない」と定義できます。Xのすべての要素がセットYの要素であり、$ | X |である場合、セットXはセットYの適切なサブセットです（$ X \ subset Y $として記述されます）。\ lt | Y | $。

Example− $ X = \ lbrace 1、2、3、4、5、6 \ rbrace $および$ Y = \ lbrace 1、2 \ rbrace $とします。$ Y $のすべての要素も$ X $に含まれ、$ X $には少なくとも1つの要素が設定された$ Y $よりも多いため、ここで$ Y \ subset X $を設定します。

ユニバーサルセット

これは、特定のコンテキストまたはアプリケーションのすべての要素のコレクションです。そのコンテキストまたはアプリケーションのすべてのセットは、基本的にこのユニバーサルセットのサブセットです。ユニバーサルセットは$ U $として表されます。

Example− $ U $を地球上のすべての動物の集合として定義する場合があります。この場合、すべての哺乳類のセットは$ U $のサブセットであり、すべての魚のセットは$ U $のサブセットであり、すべての昆虫のセットは$ U $のサブセットです。

空のセットまたはヌルセット

空のセットには要素が含まれていません。$ \ emptyset $で表されます。空集合の要素数は有限であるため、空集合は有限集合です。空集合または零集合のカーディナリティはゼロです。

Example− $ S = \ lbrace x \：| \：x \ in N $および$ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $

シングルトンセットまたはユニットセット

シングルトンセットまたはユニットセットには、要素が1つだけ含まれています。単集合は$ \ lbrace s \ rbrace $で表されます。

Example− $ S = \ lbrace x \：| \：x \ in N、\ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $

等しいセット

2つのセットに同じ要素が含まれている場合、それらは等しいと言われます。

Example − $ A = \ lbrace 1、2、6 \ rbrace $および$ B = \ lbrace 6、1、2 \ rbrace $の場合、セットAのすべての要素がセットBの要素であり、セットのすべての要素であるため、これらは等しくなります。 Bは集合Aの要素です。

同等のセット

2つのセットのカーディナリティが同じである場合、それらは同等のセットと呼ばれます。

Example− $ A = \ lbrace 1、2、6 \ rbrace $および$ B = \ lbrace 16、17、22 \ rbrace $の場合、AのカーディナリティはBのカーディナリティに等しいため、これらは同等です。つまり、$ | A | = | B | = 3 $

重複セット

少なくとも1つの共通要素を持つ2つのセットは、オーバーラップセットと呼ばれます。

セットが重複している場合-

$ n（A \ cup B）= n（A）+ n（B）-n（A \ cap B）$
$ n（A \ cup B）= n（A-B）+ n（B-A）+ n（A \ cap B）$
$ n（A）= n（A-B）+ n（A \ cap B）$
$ n（B）= n（B-A）+ n（A \ cap B）$

Example− $ A = \ lbrace 1、2、6 \ rbrace $および$ B = \ lbrace 6、12、42 \ rbrace $とします。共通の要素「6」があるため、これらのセットは重複するセットです。

素集合

2つのセットAとBは、共通の要素が1つもない場合、互いに素なセットと呼ばれます。したがって、互いに素な集合には次の特性があります。

$ n（A \ cap B）= \ emptyset $
$ n（A \ cup B）= n（A）+ n（B）$

Example − $ A = \ lbrace 1、2、6 \ rbrace $および$ B = \ lbrace 7、9、14 \ rbrace $とすると、共通の要素は1つもないため、これらのセットは重複するセットになります。

ベン図

1880年にジョンベンによって発明されたベン図は、さまざまな数学的セット間のすべての可能な論理関係を示す概略図です。

Examples

セット操作

セット操作には、セットユニオン、セット交差、セット差、セットの補集合、および直積が含まれます。

セットユニオン

セットAとBの和集合（$ A \ cup B $で示される）は、A、B、またはAとBの両方にある要素のセットです。したがって、$ A \ cup B = \ lbrace x \： | \：x \ in A \ OR \ x \ in B \ rbrace $。

Example− $ A = \ lbrace 10、11、12、13 \ rbrace $およびB = $ \ lbrace 13、14、15 \ rbrace $の場合、$ A \ cup B = \ lbrace 10、11、12、13、14 、15 \ rbrace $。（共通要素は1回だけ発生します）

交差点を設定

セットAとBの共通部分（$ A \ cap B $で示される）は、AとBの両方にある要素のセットです。したがって、$ A \ cap B = \ lbrace x \：| \：x \ in A \ AND \ x \ in B \ rbrace $。

Example − $ A = \ lbrace 11、12、13 \ rbrace $および$ B = \ lbrace 13、14、15 \ rbrace $の場合、$ A \ cap B = \ lbrace 13 \ rbrace $。

差/相対補数を設定します

セットAとセットBのセットの違い（$ A – B $で示される）は、Aにのみ存在し、Bには存在しない要素のセットです。したがって、$ A --B = \ lbrace x \：| \：x \ in A \ AND \ x \ notin B \ rbrace $。

Example− $ A = \ lbrace 10、11、12、13 \ rbrace $および$ B = \ lbrace 13、14、15 \ rbrace $の場合、$（A-B）= \ lbrace 10、11、12 \ rbrace $および$（B-A）= \ lbrace 14、15 \ rbrace $。ここでは、$（A-B）\ ne（B-A）$を見ることができます

セットの補集合

セットAの補集合（$ A '$で示される）は、セットAにない要素のセットです。したがって、$ A' = \ lbrace x | x \ notin A \ rbrace $。

より具体的には、$ A '=（U-A）$ここで、$ U $はすべてのオブジェクトを含むユニバーサルセットです。

Example− $ A = \ lbrace x \：|の場合 \：x \ \：{belongs \：to \：set \：of \：odd \：integers} \ rbrace $ then $ A '= \ lbrace y \：| \：y \ \：{does \：not \：belong \：to \：set \：of \：odd \：integers} \ rbrace $

デカルト積/クロス積

$ A_1 \ times A_2 \ dots \ times A_n $として表されるn個のセット$ A_1、A_2、\ dots A_n $のデカルト積は、すべての可能な順序対$（x_1、x_2、\ dots x_n）$として定義できます。 $ x_1 \ in A_1、x_2 \ in A_2、\ dots x_n \ in A_n $

Example −2つのセットをとる場合$ A = \ lbrace a、b \ rbrace $および$ B = \ lbrace 1、2 \ rbrace $、

AとBのデカルト積は次のように記述されます-$ A \ times B = \ lbrace（a、1）、（a、2）、（b、1）、（b、2）\ rbrace $

BとAのデカルト積は次のように記述されます-$ B \ times A = \ lbrace（1、a）、（1、b）、（2、a）、（2、b）\ rbrace $

パワーセット

セットSのべき集合は、空のセットを含むSのすべてのサブセットのセットです。カーディナリティnのセットSのべき集合のカーディナリティは$ 2 ^ n $です。べき集合は$ P（S）$として表されます。

Example −

セット$ S = \ lbrace a、b、c、d \ rbrace $の場合、サブセットを計算しましょう-

要素が0のサブセット-$ \ lbrace \ emptyset \ rbrace $（空のセット）
1つの要素を持つサブセット-$ \ lbrace a \ rbrace、\ lbrace b \ rbrace、\ lbrace c \ rbrace、\ lbrace d \ rbrace $
2つの要素を持つサブセット-$ \ lbrace a、b \ rbrace、\ lbrace a、c \ rbrace、\ lbrace a、d \ rbrace、\ lbrace b、c \ rbrace、\ lbrace b、d \ rbrace、\ lbrace c、 d \ rbrace $
3つの要素を持つサブセット-$ \ lbrace a、b、c \ rbrace、\ lbrace a、b、d \ rbrace、\ lbrace a、c、d \ rbrace、\ lbrace b、c、d \ rbrace $
4つの要素を持つサブセット-$ \ lbrace a、b、c、d \ rbrace $

したがって、$ P（S）= $

$ \ lbrace \ quad \ lbrace \ emptyset \ rbrace、\ lbrace a \ rbrace、\ lbrace b \ rbrace、\ lbrace c \ rbrace、\ lbrace d \ rbrace、\ lbrace a、b \ rbrace、\ lbrace a、c \ rbrace、\ lbrace a、d \ rbrace、\ lbrace b、c \ rbrace、\ lbrace b、d \ rbrace、\ lbrace c、d \ rbrace、\ lbrace a、b、c \ rbrace、\ lbrace a、b、 d \ rbrace、\ lbrace a、c、d \ rbrace、\ lbrace b、c、d \ rbrace、\ lbrace a、b、c、d \ rbrace \ quad \ rbrace $

$ | P（S）| = 2 ^ 4 = 16 $

Note −空のセットのべき集合も空のセットです。

$ | P（\ lbrace \ emptyset \ rbrace）| = 2 ^ 0 = 1 $

セットの分割

セットの分割、たとえばSは、次の3つの条件を満たすn個の互いに素なサブセット（たとえば、$ P_1、P_2、\ dots P_n $）のコレクションです。

$ P_i $には空のセットが含まれていません。

$ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ for \ all \ 0 \ lt i \ le n \ rbrack $
サブセットの和集合は、元のセット全体と等しくなければなりません。

$ \ lbrack P_1 \ cup P_2 \ cup \ dots \ cup P_n = S \ rbrack $
2つの異なるセットの共通部分は空です。

$ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace、\ for \ a \ ne b \ where \ n \ ge a、\：b \ ge 0 \ rbrack $

Example

$ S = \ lbrace a、b、c、d、e、f、g、h \ rbrace $とします。

考えられるパーティショニングの1つは、$ \ lbrace a \ rbrace、\ lbrace b、c、d \ rbrace、\ lbrace e、f、g、h \ rbrace $です。

別の可能性のあるパーティショニングは、$ \ lbrace a、b \ rbrace、\ lbrace c、d \ rbrace、\ lbrace e、f、g、h \ rbrace $です。