Himpunan

1- Himpunan

Himpunan adalah kumpulan objek-objek. Matematika diskrit berfokus pada struktur seperti graf (himpunan ujung-ujung dan rusuk) dan aljabar Boole (himpunan dengan operasi tertentu yang didefinisikan di dalamnya).

1.1 Definisi
Himpunan adalah suatu sistem yang berupa sekelompok atau sejumlah benda atau objek-objek berbeda yang berada dalam suatu kesatuan dan mempunyai sifat keterkaitan di antara anggota-anggotanya. Objek yang terdapat di dalam himpunan disebut elemen, unsur, atau anggota.
Contoh 1 : A adalah himpunan huruf hidup dalam abjad, atau A = {a, i, u, e, o}

1.2 Penyajian Himpunan
Terdapat banyak cara untuk menyajikan himpunan, diantaranta dengan cara mengenumerasi elemen-elemennya, menggunakan simbol-simbol baku, menyatakan syarat keanggotaan, dan menggunakan diagram venn.

1.2.1 Enumerasi
Penyajian himpunan dengan enumerasi dapat dilakukan jika himpunan tersebut terbatas dan tidak terlalu besar. Enumerasi dapat dilakukan dengan cara dengan menuliskan semua elemen himpunan yang bersangkutan di antara dua buah tanda kurung kurawal. Pada umumnya nama suatu himpunan ditandai dengan huruf kapital.
Contoh 2 : Himpunan A yang berisi semua huruf hidup dalam abjad, maka secara enumerasi dapat ditulis A = {a, i, u, e, o}.

Untuk menuliskan himpunan dengan jumlah anggota yang sangat besar dan telah memiliki pola tertentu dapat dilakukan dengan menggunakan tanda ‘...’ (ellipsis).
Contoh 3 : Himpunan B yang berisi 50 buah bilangan asli pertama, maka secara enumerasi dapat ditulis, B = { 1, 2, 3, . . . , 50 }.

Suatu objek pada suatu himpunan dapat menjadi anggota atau bukan anggota himpunan tersebut. Untuk menyatakan keanggotaan tersebut digunakan notasi berikut :
x A untuk menyatakan x merupakan anggota himpunan A
x A untuk menyatakan x bukan anggota himmpunan A
Contoh : A = {1, 2, 3, 4, 5} S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
1 A dan 1 S
6 A dan 6 S

1.2.2 Simbol-simbol Baku
Terdapat sejumlah simbol baku yang berbentuk huruf tebal (boldface) yang biasanya digunakan untuk mendefinisikan himpunan yang sering digunakan, yaitu:
N = himpunan bilangan asli, N = {1, 2, 3, . . . }
Z = himpunan bilangan bulat, Z = {. . . , -2, -1, 0, 1, 2, . . . }
Q = himpunan bilangan rasional, yaitu himpunan yang dapat dibentuk dari p/q
R = himpunan bilangan riil
C = himpuan bilangan kompleks

1.2.3 Notasi Pembentuk Himpunan
Notasi pembentukan himpunan dinyatakan dengan menulis syarat yang harus dipenuhi oleh anggotanya, yaitu
Notasi : {x | syarat yang harus dipenuhi oleh x }, dengan aturan sebagai berikut,
1. bagian kiri tanda ‘|’ menyatakan elemenen himpunan
2. tanda ‘|’ dibaca dimana atau sedemikian sehingga
3. bagian kanan tanda ‘|’ menyatakan syarat keanggotaan himpunan
4. setiap tanda ‘,’ di dalam syarat keanggotaan dibaca sebagai dan.
Contoh 4: A adalah himpunan bilangan asli yang kecil dari 8, dengan enumerasi dinyatakan dengan A = {1, 2, 3, 4, 5, 6, 7}. Dengan notasi pembentuk himpunan dapat dinyatakan dengan, A = {x | x N, x < 8 }


1.2.4 Diagram Venn
Diagram venn menyajikan himpunan secara grafis. Cara penyajian himpunan ini diperkenalkan oleh matematikawan Inggris John Venn tahun 1881. Himpunan semestas (U) digambarkan sebagai suatu segi empat, sedangkan himpunan lainnya yang merupakan bagian dari himpunan semesta digambarkan sebagai lingkaran di dalam segi empat. Dua himpunan yang mempunyai anggota yang sama digambarkan dengan lingkaran beririsan.

Contoh 5 : Misalkan U = {1, 2, 3, ... , 10}, A = {1, 3, 5, 7, 9} dan B = {1, 2, 3, 4}
Perhatikan bahwa himpunan A dan B mempunyai anggota yang sama yaitu 1 dan 3, sehingga dianggram venn-nya dapat dinytakan sebagai berikut :






Gambar 1 Diagram Venn

Himpunan yang sama ( A = B)
Himpunan A dikatakan sama dengan himpunan B, jika anggota A juga merupakan anggota B.
Contoh : A = {1, 2, 3}
B = {3, 1, 2}, maka A = B

Himpunan kosong adalah himpunan yang tidak memiliki anggota.
Contoh : A himpunan sapi yang bersayap. Karena tidak ada sapi yang bersayap maka anggota himpunan A adalah himpunan kosong, ditulis A = {} atau A= .

Himpunan A dikatakan equivalen dengan himpunan B, jika jumlah anggota A sama dengan jumlah anggota B.
Contoh :
A = {1, 2, 3}
B = {a, b, c}, maka A ~ B

Himpunan bagian adalah himpunan dimana anggotanya merupakan bagian dari anggota yang lain.
Contoh :
A = {a, b, c, d, e}
B = {a, e}, maka B A

Himpunan terhingga adalah himpunan yang jumlah anggotanya terbatas
Contoh: A = {2, 5, 6, 7, 8, 9, 12}
Himpunan tak hingga adalah himpunan yang jumlah anggotanya tidak terbatas.
Contoh : A = {1, 2, 3,4, 5, 6, ... }

Kardinalitas
Misalkan A merupakan himpunan berhingga, maka jumlah elemen berbeda di dalam A disebut kardinal dari himpunan A. Kardinal dinotasikan dengan
n(A) atau |A|

Contoh 5 :
A = {x | x N, x < 8 }, maka |A| = 7.

Himpunan yang tidak berhingga mempunyai kardinal tidak berhingga.

Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari kedua himpunan tersebut sama.
Contoh 6 :
Jika A = {1, 2, 3, 4, 5} dan B = {a, b, c, d, e}, maka A ~ B sebab |A| = |B| = 5.

Himpunan semesta atau universal adalah himpunan yang terdiri dari himpunan-himpunan lain sehingga elemen-elemenya terdiri dari elemen-elemen tersebut. Semua objek pembicaraan di simbolkan dengan S.
Contoh : A adalah semua huruf hidup
B adalah semua huruf mati, maka S dari A dan B adalah semua huruf.

Himpunan lepas (disjoint) adalah himpunan-himpunan yang saling tidak memiliki unsur atau elemen yang sama.
Contoh : A = { 1, 2, 3, 4}
B = { 5, 6, 7, 8}

Himpunan bersendi adalah himpunan yang anggotanya-anggotanya terdiri dari anggota-anggota himpunan yang terkait.
Contoh : A = {1, 2, 3, 4, 5}
B = {2, 3, 5} maka elemen persekutuannya {2, 3, 5}

Himpunan komplemen adalah himpunan yang anggotanya di luar himpunan tersebut yang berada di dalam semesta pembicaraan.
Contoh A = {2, 3, 5} dan S = {1, 2, 3, 4, 5}
Ac = {1, 4}

Himpunan gabungan adalah suatu himpunan yang anggota-anggotanya terdiri dari anggota-anggota himpunan yang terkait.
Contoh A = {1, 2, 3, 4, 5}
B = {2, 4, 5, 6}, maka A B = {1, 2, 3, 4, 5, 6}
Jika sebuah himpunan berukuran besar atau tak terbatas, kita bisa menggambarkan dengan mendaftarkan sifat yang diperlukan untuk menjadi anggotanya. Contoh B adalah himpunan yang terbentuk dari bilangan-bilangan bulat genap posif, yakni bilangan 2, 4, 6, 8, dan seterusnya, dapat ditulis
B = {x | x bilangan bulat genap positif} Garis tegak “ |” dibaca ‘dimana’.
Jika X adalah sebuah himpunan terhingga, maka
| X | = banyaknya anggota di dalam X.
Jika diberikan dua himpunan X dan Y, maka terdapat berbagai cara untuk mengkombinasikan X dan Y untuk membentuk sebuah himpunan baru.
Himpunan
X Y = { x | x X atau x Y} , dibaca elemen atau anggota.
disebut gabungan dari X dan Y.

Himpunan
X Y = { x | x X dan x Y} , dibaca elemen atau anggota.
disebut irisan dari X dan Y.

Himpunan kuasa (power set) dari suatu himpunan A adalah suatu himpunan yang elemennya merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A sendiri.
Himpunan kuasa dinotasikan dengan (A) atau 2|A|
Contoh 7 :
Jika A = {1, 2, 3}, maka (A) = { , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

1.3 Operasi Himpunan
Gabungan atau union ( )
Gabungan dua himpunan A dan B adalah jika anggota-anggota himpunannya termasuk di dalam himpunan A atau himpunan B, atau A B.
Contoh 8 :
Misalkan A = {1, 3, 5, 6, 7} dan B = {2, 4, 6} maka A B ={1, 2, 3, 4, 5, 6, 7}

Irisan atau perpotongan atau persendian ( )
Irisan dua himpunan A dan B adalah jika anggota-anggotanya merupakan anggota dari himpunan A dan anggota himpunan B atau anggotanya termuat di A dan B.
Contoh 9:
Misalkan A = {1, 2, 3, 4, 5} dan B = {1, 3, 6}, maka A B = {1, 3}

Komplemen dari suatu suatu himpunan A terhadap suatu himpunan semesta U adalah suatu himpunan yang elemennya merupakan elemen U yang bukan elemen A. dinotasikan dengan atau A’ atau Ac = { x | x U dan x A}

Selisih atau pengurangan
Selisih himpunan A dan B adalah jika anggotan-anggotanya merupakan anggota himpunan A dikurangi dengan anggota himpunan B.
Contoh : A = { 1, 2, 3, 4, 5, 7} dan B = {4, 5, 6}, maka A – B = {1, 2, 3, 7}

Himpunan sembarang X adalah himpunan bagian (subhimpunan) dari dirinya sendiri karena anggota sembarang anggota di X berada di X. Jika X adalah himpunan bagian dari Y dan X tidak sama dengan Y, kita katakan bahwa X adalah himpunan bagian murni (proper subset) dari Y. Himpunan kosong adalah himpunan bagian dari setiap himpunan. Himpunan dari semua himpunan bagian (murni atau tidak) dari himpunan X, dinotasikan dengan ρ( X), disebut himpunan kuasa (power set) dari X.
Contoh : Misaklkan A = {a, b, c}, maka anggota-anggota dari ρ( A) adalah
{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}


Beda setangkup dari himpunan A dan B adalah suatu himpunan yang elemennya ada pada himpunan A atau B, tetapi tidak pada keduanya. Dinotasikan dengang;
A B = (A B ) – (A B) = ( A- B) ( B - A).
Contoh :
Misalkan A ={2, 4, 6} dan B ={ 2, 3, 5,6, 7}, maka A B ={3, 4, 5, 7}

Perkalian kartesian dari himpunan A dan B adalah himpunan yang elemennya semua pasangan berurut (ordered pairs) yang dibentuk dari komponen pertama dari himpunan A dan komponen kedua dari himpunan B. Dinotasikan dengan;
A x B = {(a, b) | a A dan b B }.
Contoh :
Misalkan A = {1, 2, 3, 4} dan B = {a, b}, maka A x B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b), (4, a), (4, b)}.

Perampatan Operasi Himpunan
Operasi himpunan dapat dilakukan terhadap 2 atau lebih himpunan. Dalam hal ini, perampatan (generalization) operasi himpunan dengan menggunakan operasi dasar perampatan yang ada operasi aritmatika biasa.
Misalkan A1 , A2 , . . . , An-1 , An merupakan himpunan, maka
1. A1 A2 . . . An-1 An =
2. A1 A2 . . . An-1 An =
3. A1 A2 . . . An-1 An =

Teorema 1.1
Jika |X| = n maka |ρ( X)| = 2n

Teorema 1.2
Misalkan A, B, serta C adalah himpunan bagian dari U maka berlaku sifat berikut
1. hukum komutatif untuk gabungan
A B = B A
2. hukum komutatif untuk irisan
A B = B A
3. hukum asaosiatif untuk gabungan
(A B ) C = A (B C)
4. hukum assosiatif untuk irisan
(A B ) C = A (B C)
5. hukum distributif
(A B ) C = (A C ) (B C)
A ( B C) = (A C ) (B C)
6. hukum de Morgan
(A B )c = Ac Bc
(A B )c = Ac Bc
7. hukum ikatan (bound laws)
A U = U, dan A =
8. hukum idempoten (idempoten laws)
A U = A, dan A = A
9. hukum penyerapan (absorption laws)
A (A B ) = A, A (A B ) = A
10. hukum involusi (involution laws)
=
A = A

11. hukum 0/1 (1/0 laws)
= U, =

Definisi Prinsip Dualitas pada Himpunan
Misalkan S adalah suatu kesamaan yang melibatkan himpunan (set identity), dan oprasi-operasi seperti , , dan komplemen berlaku. Jika S* diperoleh dari S dengan menggantikan menjadi , menjadi U, dan U menjadi , sedangkan komplemen dibiarkan seperti semula, maka kesamaan S* juga benar dan disebut dual dari kesamaan S.

Prinsip Inklusi-Eksklusi
Misalkan A dan B dua buah himpunan berhingga. Penggabungan dua buah himpunan mengahasilkan himpunan baru yang elemen-elemennya berasal dari himpunan A dan B. Himpunan A mungkin saja memiliki elemen yang sama dengan himpunan B atau sebaliknya, sehingga banyaknya elemen bersama A dan B adalah | A B|. Setiap unsur yang sama itu telah dihitung dua kali sekali pada |A| dan sekali pada |B|, meskipun ia seharusnya dianggap sebagai satu buah elemen di dalam |A B|. Karena itu jumlah elemen hasil penggabungan seharusnya adalah jumlah elemen masing-msaing himpunan dikurangi dengan jumlah elemen di dalam irisannya, yaitu
|A B| = | A| + |B| - | A B|
Prinsip ini dikenal dengan nama prinsip inklusi-ekslusi.

Lemma 1:
Misalkan A dan B adalah himpunan berhingga yang saling lepas maka
| A B| = | A| + |B|

Teorema 1 :
Misalkan A dan B adalah himpunan berhingga yang saling lepas maka |A B| berhingga dan |A B| = | A| + |B| - | A B|. Dengan cara yang sama dapat menghitung operasi beda setangkup :
|A B| = | A| + |B| - 2| A B|

Contoh 9:
Berapa banyaknya bilangan bulat antara 1 dan 100 yang habis di bagi 3 atau 5?
Penyelesaian :
A = himpunan bilangan bulat yang habis dibagi 3
B = himpunan bilangan bulat yang habis dibagi 5
|A B| = himpunan bilangan bulat yang habis di bagi 3 atau 5 (yaitu himpunan bilangan bulat yang habis dibagi oleh KPK –Kelipatan persekutuan terkecil – dari 3 dan 5, yaitu 15)
| A| = |100/3| = 33
| B| = |100/5| = 20
|A B| = |100/15| = 6
sehingga,
|A B| = | A| + |B| - | A B|
= 33 + 20 – 6
= 47
jadi terdapat 47 buah bilangan yang habis dibagi 3 atau 5.

Teorema 2 :
Misalkan A, B, dan C adalah himpunan berhingga, maka
|A B C | = | A| + |B| + |C| - | A B | - | A C | - | B C | + | A B C |
dan untuk r buah himpunan berlaku teorema berikut :
Teorema 3 :
Misalkan A1 , A2 , . . . , An-1 , An adalah himpunan berhingga, maka berlaku
|A1 A2 . . . An-1 An| = - + + . . . + (-1)r-1 |A1 A2 . . . An-1 An|

Partisi dari sebuah himpunan A adalah sekumpulan himpunan bagian tidak kosong, A1 , A2 , . . . , An-1 , An dari A sedemikian sehingga :
1. A1 A2 . . . An-1 An = A
2. himpunan bagian Ai dan Aj saling lepas, yaitu Ai Aj = untuk i j

Latihan :
Misalkan U = { 1, 2, 3, 4, 5, ..., 10}. Misalkan A = {1, 4, 7, 10}, B = {1, 2, 3, 4, 5} dan C = {2, 4, 6, 8}. Daftarkanlah anggota-anggota dari masing-masing himpunan.
1. A B 2. B C
3. A – B 4. B – A
5. 6. U – C
7. 8. A