Senin, 04 Maret 2013

Himpunan

19.27    No comments



Relasi antar himpunan

Subhimpunan

Dari suatu himpunan, misalnya A = {apel, jeruk, mangga, pisang}, dapat dibuat himpunan-himpunan lain yang elemen-elemennya adalah diambil dari himpunan tersebut.

  • {apel, jeruk}

  • {jeruk, pisang}

  • {apel, mangga, pisang}

Ketiga himpunan di atas memiliki sifat umum, yaitu setiap anggota himpunan itu adalah juga anggota himpunan A. Himpunan-himpunan ini disebut sebagai subhimpunan atau himpunan bagian dari A. Jadi dapat dirumuskan:

B adalah himpunan bagian dari A jika setiap elemen B juga terdapat dalam A.

B \subseteq A \equiv \forall_x \, x \in B \rightarrow x \in A

Kalimat di atas tetap benar untuk B himpunan kosong. Maka \varnothing juga subhimpunan dari A.

Untuk sembarang himpunan A,

\varnothing \subseteq A

Definisi di atas juga mencakup kemungkinan bahwa himpunan bagian dari A adalah A sendiri.

Untuk sembarang himpunan A,

A \subseteq A

Istilah subhimpunan dari A biasanya berarti mencakup A sebagai subhimpunannya sendiri. Kadang-kadang istilah ini juga dipakai untuk menyebut himpunan bagian dari A, tetapi bukan Asendiri. Pengertian mana yang digunakan biasanya jelas dari konteksnya.

Subhimpunan sejati dari A menunjuk pada subhimpunan dari A, tetapi tidak mencakup A sendiri.

B \subset A \equiv B \subseteq A \wedge B \neq A

Superhimpunan

Kebalikan dari subhimpunan adalah superhimpunan, yaitu himpunan yang lebih besar yang mencakup himpunan tersebut.

A \supseteq B \equiv B \subseteq A

Kesamaan dua himpunan

Himpunan A dan B disebut sama, jika setiap anggota A adalah anggota B, dan sebaliknya, setiap anggota B adalah anggota A.

A = B \equiv \forall_x\; x \in A \leftrightarrow x \in B

atau

A = B \equiv A \subseteq B \wedge B \subseteq A

Definisi di atas sangat berguna untuk membuktikan bahwa dua himpunan A dan B adalah sama. Pertama, buktikan dahulu A adalah subhimpunan B, kemudian buktikan bahwa B adalah subhimpunan A.

Himpunan Kuasa

Himpunan kuasa atau himpunan pangkat (power set) dari A adalah himpunan yang terdiri dari seluruh himpunan bagian dari A. Notasinya adalah \mathcal{P}(A).

Jika A = {apel, jeruk, mangga, pisang}, maka \mathcal{P}(A):

{ { }, {apel}, {jeruk}, {mangga}, {pisang}, {apel, jeruk}, {apel, mangga}, {apel, pisang}, {jeruk, mangga}, {jeruk, pisang}, {mangga, pisang}, {apel, jeruk, mangga}, {apel, jeruk, pisang}, {apel, mangga, pisang}, {jeruk, mangga, pisang}, {apel, jeruk, mangga, pisang} }

Banyaknya anggota yang terkandung dalam himpunan kuasa dari A adalah 2 pangkat banyaknya anggota A.

|\mathcal{P}(A)| = 2^{|A|}

Kelas

Suatu himpunan disebut sebagai kelas, atau keluarga himpunan jika himpunan tersebut terdiri dari himpunan-himpunan. Himpunan A = \{ \{a,\,b\},\, \{c,\,d,\,e,\,f\},\,\{a,\,c\},\,\{,\}\}adalah sebuah keluarga himpunan. Perhatikan bahwa untuk sembarang himpunan A, maka himpunan kuasanya, \mathcal{P}(A) adalah sebuah keluarga himpunan.

Contoh berikut, P = \{ \{a,\,b\}, c\} bukanlah sebuah kelas, karena mengandung elemen c yang bukan himpunan.

Kardinalitas

Kardinalitas dari sebuah himpunan dapat dimengerti sebagai ukuran banyaknya elemen yang dikandung oleh himpunan tersebut. Banyaknya elemen himpunan \{apel, jeruk, mangga, pisang\} adalah 4. Himpunan \{p, q, r, s\} juga memiliki elemen sejumlah 4. Berarti kedua himpunan tersebut ekivalen satu sama lain, atau dikatakan memiliki kardinalitas yang sama.

Dua buah himpunan A dan B memiliki kardinalitas yang sama, jika terdapat fungsi korespondensi satu-satu yang memetakan A pada B. Karena dengan mudah kita membuat fungsi \{(apel,\,p),\,(jeruk,\,q),\,(mangga,\,r),\,(pisang,\,s)\} yang memetakan satu-satu dan kepada himpunan A ke B, maka kedua himpunan tersebut memiliki kardinalitas yang sama.

Himpunan Denumerabel

Jika sebuah himpunan ekivalen dengan himpunan \mathbb{N}, yaitu himpunan bilangan asli, maka himpunan tersebut disebut denumerabel. Kardinalitas dari himpunan tersebut disebut sebagai kardinalitas \mathfrak{a}.

Himpunan semua bilangan genap positif merupakan himpunan denumerabel, karena memiliki korespondensi satu-satu antara himpunan tersebut dengan himpunan bilangan asli, yang dinyatakan oleh 2n\,.

A = \{ 2,\, 4,\, 6,\, 8,\, ...\}

Himpunan Berhingga

Jika sebuah himpunan memiliki kardinalitas yang kurang dari kardinalitas \mathfrak{a}, maka himpunan tersebut adalah himpunan berhingga.

Himpunan Tercacah

Himpunan disebut tercacah jika himpunan tersebut adalah berhingga atau denumerabel.

Himpunan Non-Denumerabel

Himpunan yang tidak tercacah disebut himpunan non-denumerabel. Contoh dari himpunan ini adalah himpunan semua bilangan riil. Kardinalitas dari himpunan jenis ini disebut sebagai kardinalitas \mathfrak{c}. Pembuktian bahwa bilangan riil tidak denumerabel dapat menggunakan pembuktian diagonal.

Himpunan bilangan riil dalam interval (0,1) juga memiliki kardinalitas \mathfrak{c}, karena terdapat korespondensi satu-satu dari himpunan tersebut dengan himpunan seluruh bilangan riil, yang salah satunya adalah y=tan(\pi x - \frac{1}{2}\pi).

Fungsi Karakteristik

Fungsi karakteristik menunjukkan apakah sebuah elemen terdapat dalam sebuah himpunan atau tidak.

\chi_{A}(x) = \begin{cases} 1,\quad\mbox{jika } x \in A \\ 0,\quad\mbox{jika } x \notin A \end{cases}

Jika A = \{apel,\,jeruk,\,mangga,\,pisang\} maka:

\chi_A(apel) = 1
\chi_A(durian) = 0
\chi_A(utara) = 0
\chi_A(pisang) = 1
\chi_A(singa) = 0

Terdapat korespondensi satu-satu antara himpunan kuasa \mathcal{P}(S) dengan himpunan dari semua fungsi karakteristik dari S. Hal ini mengakibatkan kita dapat menuliskan himpunan sebagai barisan bilangan 0 dan 1, yang menyatakan ada tidaknya sebuah elemen dalam himpunan tersebut.

Representasi Biner

Jika konteks pembicaraan adalah pada sebuah himpunan semesta S, maka setiap himpunan bagian dari S bisa dituliskan dalam barisan angka 0 dan 1, atau disebut juga bentuk biner.Bilangan biner menggunakan angka 1 dan 0 pada setiap digitnya. Setiap posisi bit dikaitkan dengan masing-masing elemen S, sehingga nilai 1 menunjukkan bahwa elemen tersebut ada, dan nilai 0 menunjukkan bahwa elemen tersebut tidak ada. Dengan kata lain, masing-masing bit merupakan fungsi karakteristik dari himpunan tersebut. Sebagai contoh, jika himpunan S = {a, b, c, d, e, f, g}, A = {a, c, e, f}, dan B = {b, c, d, f}, maka:

Himpunan Representasi Biner ---------------------------- ------------------- a b c d e f g S = { a, b, c, d, e, f, g } --> 1 1 1 1 1 1 1 A = { a, c, e, f } --> 1 0 1 0 1 1 0 B = { b, c, d, f } --> 0 1 1 1 0 1 0

Cara menyatakan himpunan seperti ini sangat menguntungkan untuk melakukan operasi-operasi himpunan, seperti union, interseksi, dan komplemen, karena kita tinggal menggunakanoperasi bit untuk melakukannya.

  • Operasi gabungan A \cup B setara dengan A or B

  • Operasi irisan A \cap B setara dengan A and B

  • Operasi komplemen A^C setara dengan not A

Representasi himpunan dalam bentuk biner dipakai oleh kompiler-kompiler Pascal dan juga Delphi

0 komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)