Himpunan Ganda

·       Himpunan yang elemennya boleh berulang (tidak harus berbeda) disebut himpunan ganda (multiset).

Contohnya, {1, 1, 1, 2, 2, 3}, {2, 2, 2}, {2, 3, 4}, {}.

·       Multiplisitas dari suatu elemen pada himpunan ganda adalah jumlah kemunculan elemen tersebut pada himpunan ganda.  Contoh: M = { 0, 1, 1, 1, 0, 0, 0, 1 }, multiplisitas 0 adalah 4.

·       Himpunan (set) merupakan contoh khusus dari suatu multiset, yang dalam hal ini multiplisitas dari setiap elemennya adalah 0 atau 1.

·       Kardinalitas dari suatu multiset didefinisikan sebagai kardinalitas himpunan padanannya (ekivalen), dengan mengasumsikan elemen-elemen di dalam multiset semua berbeda.

Operasi Antara Dua Buah Multiset:

Misalkan P dan Q adalah multiset:

1.    P Q adalah suatu multiset yang multiplisitas elemennya sama dengan multiplisitas maksimum elemen tersebut pada himpunan P dan Q.

     Contoh: P = { a, a, a, c, d, d } dan Q ={ a, a, b, c, c },

 P Q = { a, a, a, b,  c, c, d, d }

2.    P Q adalah suatu multiset yang multiplisitas elemennya sama dengan multiplisitas minimum elemen tersebut pada himpunan P dan Q.

     Contoh: P = { a, a, a, c, d, d } dan Q = { a, a, b, c, c }

 P Q = { a, a, c }

3.  P – Q adalah suatu  multiset yang multiplisitas elemennya sama dengan:

   multiplisitas elemen tersebut pada P dikurangi multiplisitasnya pada Q, jika selisihnya positif

        0, jika selisihnya nol atau negatif.

     Contoh: P = { a, a, a, b, b, c, d, d, e } dan Q = {  a, a, b, b, b, c,

                   c, d, d, f } maka P – Q  = { a, e }

4.    P + Q, yang didefinisikan sebagai jumlah (sum) dua buah himpunan ganda, adalah suatu multiset yang multiplisitas elemennya sama dengan penjumlahan dari multiplisitas elemen tersebut pada P dan Q.

     Contoh: P = { a, a, b, c, c } dan Q = { a, b, b, d },

                  P + Q = { a, a, a, b, b, b, c, c, d }

Pembuktian Pernyataan Perihal Himpunan

·       Pernyataan himpunan adalah argumen yang menggunakan notasi himpunan.

·       Pernyataan dapat berupa:

1.    Kesamaan (identity)

Contoh: Buktikan “A Ç (B È C) = (A Ç B) È (A Ç C)”

2.    Implikasi

Contoh: Buktikan bahwa “Jika A Ç B = Æ dan A Í (B È C) maka selalu berlaku bahwa A Í C”.

1. Pembuktian dengan menggunakan diagram Venn

Contoh 26. Misalkan A, B, dan C adalah himpunan. Buktikan A Ç (B È C) = (A Ç B) È (A Ç C) dengan diagram Venn.

Bukti:

A Ç (B È C)                            (A Ç B) È (A Ç C)   

Kedua digaram Venn memberikan area arsiran yang sama.

Terbukti bahwa A Ç (B È C) = (A Ç B) È (A Ç C).  

                                               

·       Diagram Venn hanya dapat digunakan jika himpunan yang digambarkan tidak banyak jumlahnya.

·       Metode ini mengilustrasikan ketimbang membuktikan fakta. Diagram Venn  tidak dianggap sebagai metode yang valid untuk pembuktian secara formal. 

2. Pembuktikan dengan menggunakan tabel keanggotaan

Contoh 27. Misalkan A, B, dan C adalah himpunan. Buktikan bahwa A Ç (B È C) = (A Ç B) È (A Ç C). 

Bukti:

A	B	C	B È C	A Ç (B È C)	A Ç B	A Ç C	(A Ç B) È (A Ç C)
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	1	1	1	1

Karena kolom A Ç (B È C) dan kolom (A Ç B) È (A Ç C) sama, maka A Ç (B È C) = (A Ç B) È (A Ç C). 

3. Pembuktian dengan menggunakan aljabar himpunan.

Contoh 28. Misalkan A dan B himpunan. Buktikan bahwa (A Ç B) È (A Ç ) = A

Bukti:

(A Ç B) È (A Ç )  = A Ç (B È )     (Hukum distributif)

                        = A Ç U                   (Hukum komplemen)

                        = A                           (Hukum identitas)                                                 

               

Contoh 29.  Misalkan A dan B himpunan. Buktikan bahwa A È (B – A) = A È B

Bukti:

          A È (B – A)  = A È (B Ç )         (Definisi operasi selisih)

                          = (A È B) Ç (A È )   (Hukum distributif)

                          = (A È B) Ç U               (Hukum komplemen)

                          = A È B                          (Hukum identitas)                       

Contoh 30.  Buktikan bahwa untuk sembarang himpunan A dan B, bahwa

         (i)  A È ( Ç B) = A È B    dan

(ii)  A Ç ( È B) = A Ç B

Bukti:

(i)     A È ( Ç B)  = ( A È ) Ç (A Ç B)    (H. distributif)

                                  =  U Ç  (A Ç B)               (H. komplemen)

                                  =  A È B                           (H. identitas)                 

(ii)    adalah dual dari (i)

A Ç ( È B)  = (A Ç ) È  (A Ç B)    (H. distributif)

                                  = Æ  È  (A Ç B)               (H. komplemen)

                                 =  A Ç B                             (H. identitas)                 

         

4. Pembuktian dengan menggunakan definisi 

·       Metode ini digunakan untuk membuktikan pernyataan himpunan yang tidak berbentuk kesamaan, tetapi pernyataan yang berbentuk implikasi. Biasanya di dalam implikasi tersebut terdapat notasi himpunan bagian (Í atau Ì).

Contoh 31.  Misalkan A dan B himpunan. Jika A Ç B = Æ dan A Í (B È C) maka A Í C. Buktikan!

Bukti:

(i)    Dari definisi himpunan bagian, P Í Q jika dan hanya jika setiap x Î P juga Î Q. Misalkan x Î A. Karena A Í (B È C), maka dari definisi himpunan bagian, x juga Î (B È C).

Dari definisi operasi gabungan (È), x Î (B È C) berarti x Î B atau x Î C.

(ii)  Karena x Î A dan A Ç B = Æ, maka x Ï B

Dari (i) dan (ii), x Î C harus benar. Karena "x Î A juga berlaku x Î C, maka dapat disimpulkan A Í C . 

Tipe Set dalam Bahasa Pascal

·       Bahasa Pascal menyediakan tipe data khusus untuk himpunan, yang bernama set. Tipe set menyatakan himpunan kuasa dari tipe ordinal (integer, character).

    Contoh:

type

       HurufBesar = ‘A’..‘Z’;  { enumerasi }

       Huruf = set of HurufBesar;

    var

       HurufKu : Huruf;

Nilai untuk peubah HurufKu dapat diisi dengan pernyataan berikut:

          HurufKu:=[‘A’, ‘C’, ‘D’];

    HurufKu:=[‘M’];

    HurufKu:=[];         { himpunan kosong }

·       Operasi yang dapat dilakukan pada tipe himpunan adalah operasi gabungan, irisan, dan selisih seperti pada contoh berikut:

 {gabungan}

          HurufKu:=[‘A’, ‘C’, ‘D’] + [‘C’, ‘D’, ‘E’];

{irisan}

    HurufKu:=[‘A’, ‘C’, ‘D’] * [‘C’, ‘D’, ‘E’];

{selisih}

HurufKu:=[‘A’, ‘C’, ‘D’] - [‘C’, ‘D’, ‘E’];

·       Uji keanggotaan sebuah elemen di dalam himpunan dilakukan dengan menggunakan opeator in seperti contoh berikut:

          if ‘A’ in HurufKu then    ...

·       Di dalam kakas pemrograman Delphi, set sering digunakan untuk mengindikasikan flag. Misalnya himpunan icon untuk window:

type

       TBorderIcon=(biSystemMenu, biMinimize,

       biMaximaze);

       Huruf = set of TBoderIcon;