1. HIMPUNAN Himpunan didefinisikan sebagai kumpulan objek-objek yang berbeda (Liu, 1986). Atau himpunan objek dengan syarat keanggotaan tertentu. Contoh : S {1,2,3,4,5} S {x | bulat 1 x 5 } Jika suatu objek x merupakan anggota dari himpunan A, maka dituliskan x S dan dibaca : “ x adalah anggota A”, atau “ x ada dalam S”, atau “x adalah elemen S”. Sebaliknya jika x bukan anggota S, dituliskan x S . Himpunan yang tidak mempunyai anggota, disebut himpunan kosong (empty set) dan dilambangkan dengan : Q = {} himpunan kosong ( Ø ) Contoh 2 : himpunan orang Indonesia yang pernah ke bulan. Beberapa sifat himpunan kosong adalah sebagai berikut : Himpunan kosong adalah himpunan bagian semua himpunan. Jadi Ø A untuk semua himpunan A. Himpunan kosong adalah tunggal. 1.1 Penyajian Himpunan Ada dua cara untuk menyatakan himpunan : List / mendaftar, yaitu menuliskan tiap-tiap anggota himpunan di antara 2 kurung kurawal. Misalkan A adalah nama-nama pasaran jawa, yaitu : pon, wage, kliwon, legi, pahing. Maka A ditulis sebagai A = {pon, wage, kliwon, legi, pahing} Dengan syarat keanggotaan, yaitu menuliskan sifat-sifat yang ada pada semua anggota himpunan di antar 2 kurung kurawal. Misalkan A adalah himpunan yang menyatakan nama-nama pasaran jawa, maka dituliskan sebagai A = {x | x nama-nama pasaran jawa} Kadang-kadang suatu himpunan hanya dapat dinyatakan dengan salah satu cara, tetapi kadang-kadang juga dapat dinyatakan dengan keduanya. 1.2 Operasi antar Himpunan Kesamaan himpunan A=B jika dan hanya jika x A, x B dan y A, y B
Himpunan bagian (subset) dan himpunan bagian sejati (proper subset) Jika A dan B adalah himpunan-himpunan maka A disebut himpunan bagian (subset) dari B bila dan hanya bila setiap anggota A juga merupakan anggota B. A B jika dan hanya jika x A, x B Perhatikan Gambar 1.1. Jika A adalah himpunan bagian B, dikatakan juga bahwa B memuat A (symbol B A ).
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 1
B A
Gambar 1.1 P disebut himpunan bagian sejati (proper subset) dari Q jika P tidak sama dengan Q, artinya setidaknya ada satu unsur di dalam Q yang tidak ada di dalam P. Misalkan, P ={a, b} merupakan himpunan bagian sejati dari himpunan Q = {y, x, b, c, a}. Untuk menyatakan P adalah himpunan bagian sejati Q, dapat dituliskan PQ Perbedaan antara (simbol keanggotaan himpunan) dan (simbol himpunan bagian). x A berarti bahwa elemen x adalah salah satu diantara elemen-elemen A. Sedangkan A B berarti bahwa setiap anggota A merupakan anggota B.
Irisan / Intersection Irisan dua buah himpunan A dan B (ditulis A B ) adalah himpunan semua elemen-elemen anggota A atau anggota B. A B {x S | x A dan x B} . Daerah yang diarsir menunjukkan himpunan A B. S
A
B
Gambar 1.2
Gabungan / Union Gabungan dua buah himpunan A dan B (ditulis A B) adalah himpunan semua elemen-elemen anggota A atau anggota B. A B {x S | x A atau x B} . Daerah yang diarsir merupakan himpunan A B. S
A
B
Gambar 1.3 jika A B {} , maka A dan B adalah himpunan lepas atau saling asing.
Selisih (-)
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 2
Selisih himpunan B dari himpunan A (symbol A-B) adalah himpunan semua elemen x dalam S sedemikian hingga x anggota A, tapi x bukan anggota B. A B {x S | x A dan x B} S
A
B
Gambar 1.4
Selisih Simetri ( ) Selisih simetri antara himpunan A dan B, dilambangkan A B adalah himpunan yang mengandung tepat semua unsure yang ada dalam A atau di dalam B namun tidak di dalam keduanya. Dengan kata lain, A B adalah himpunan : A B {x | x ( A B) dan x ( A B)} A B ( A B) ( A B) . Himpunan A B dapat dilihat pada Gambar 1.5. Daerah yang diarsir adalah daerah A B. S
A
B
Gambar 1.5 1.3 Semesta Pembicaraan / Universe Bilangan rasional yaitu bilangan perbandingan (q) b q ; b, c z; c ≠ 0 c Semesta pembicaraan adalah himpunan yang memuat seluruh objek yang akan menjadi pembicaraan. S A A = {| x S dan x A} A = S-A Ac
Gambar 1.6
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 3
1.4 Sifat-sifat Operasi 1.
A B B A Komutatif A B B A
2.
( A B) C A ( B C ) Asosiatf ( A B) C A ( B C )
3.
A ( B C ) ( A B) ( A C ) Distributif A ( B C ) ( A B) ( A C )
4.
A S A A S S Identitas A Ø A A Ø Ø
5.
A A Ø S Ø Komplemen Ø S A A S
6.
( A ) A adalah hukum Komplemen Ganda
7.
( A B) A B De Morgan ( A B) A B
8.
A ( A B) A ( A B)
9.
A B A B
10.
A B ( A B) ( B A)
A Absorbsi A
1.5 Cacah Himpunan Berhingga (Kardinalitas) Cacah anggota himpunan A ditulis n(A) atau |A|. Jika A1, A2,…, An adalah himpunan yang saling asing. ( Ai Aj Ø, i j ) , maka n( A1 A .... An) n( A1) n( A2) ... n( An) Teorema: Untuk sembarang 2 buah himpunan A dan B yang hingga, berlaku : n( A B) n( A) n( B) n( A B) -
Untuk sembarang 3 himpunan A, B, dan C yang hingga, berlaku :
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 4
n( A B C ) n( A) n( B) n(C ) n( A B) n( A C ) n( B C ) n( A B C )
Untuk sembarang n himpunan A1, A2, …, An, berlaku:
-
n (A1 A2 … An) = ∑ n (Ai) - ∑ n (Ai ∩ Aj) + n (Ai ∩ Aj ∩ Ak) - …+ (-1)n-1 n (A1 ∩ A2 ∩ … ∩ An) Contoh : Dari 100 orang mahasiswa, diketahui 37 orang menyukai mata kuliah Jaringan Komputer (Jarkom), 27 orang suka mata kuliah Basis Data (BD), dan 12 orang suka kedua-duanya. a. b. c.
Berapa orang yang suka Jarkom atau BD? Berapa orang yang suka Jarkom tetapi tidak suka BD? Berapa orang yang tidak suka kedua-duanya? S
Jarkom
BD
25 12
15
Gambar 1.7 Penyelesaian : Misal : P = Mahasiswa yang suka Jarkom n(P) = 37 Q = Mahasiswa yang suka BD n(Q) = 27 P Q mahasiswa yang suka Jarkom dan DB P Q mahasiswa yang suka Jarkom atau DB a. n( P Q) n( P) n(Q) n( P Q) = 37 + 27 – 12 = 52 n( P Q ) b. P ( P Q) ( P Q )
n( P ) n( P Q ) n( P Q )
c.
n( P Q ) n( P ) n( P Q ) 37 12 25 n( P Q) S ( P Q) ( P Q) Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 5
n(S ) n( P Q) ( P Q) n( P Q ) n( S ) n( P Q ) 100 - 52 48
1.6 Power Set (Himpunan Kuasa) A = Himpunan hingga Power set dari A ditulis P(A). Didefinisikan sebagai himpunan dari semua himpunan bagian dari A. Jika n menunjukkan jumlah elemen dari A, maka:
n( P( A)) 2 n( A) B = {a, b} P(B) = {Ø, {a}, {b}, {a,b}}
1.7 Successor Untuk sembarang himpunan A tertentu, himpunan A {A} dinamakan pengganti (successor) A, dilambangkan A+. {A} adalah himpunan yang mengandung A sebagai satu-satunya unsur. Dengan kata lain, A+ adalah himpunan yang terbentuk dari semua unsur himpunan A ditambah dengan satu unsur lagi yaitu himpunan A itu sendiri. A A {A} n( A ) n( A) 1 Contoh : Jika A ={a, b}, maka A+ = {a, b} {{a, b}} = {a, b, {a,b}} 1.8 Multiset Contoh : A = {a, a, b, b, b, c, e, f, f } B = {a, b, b, c, c, c, d, d, f } Operasi pada Multiset Interseksi A B minimal cacah elemen (A, B) Contoh : A B {a, b, b, c, f }
Union Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 6
A B maximal cacah elemen (A, B) Contoh : A B {a, a, b, b, b, c, c, c, d , d , e, f , f }
Selisih A – B = {a, b, e, f} B – A = {c, c, d, d}
AB A B ( A B) ( A B)
{a, b, c, c, d , d , e, f }
A+B A B {a, a, a, b, b, b, b, b, c, c, c, c, d , d , e, f , f , f }
1.9 Prinsip Inklusi dan Eksklusi A = himpunan hingga Kardinalitas A |A| = n(A) 1.
| A B || A| | B |
2.
| A B | min ( | A |, | B | )
3.
| A B | | A | | B | 2 | A B |
4.
| A B | | A | -| B |
n( A B) n( A) n( B) n( A B)
Untuk 2 himpunan A dan B, maka menjadi : | A B | | A| | B |- n | A B |
Untuk 3 himpunan A, B, C, maka menjadi : | A B C | | A | | B | | C | -| A B | -| AC | -| B C | | A B C | Contoh 1 : Fasilitas-fasilitas yang terdapat di 9 ruang kuliah Mipa Selatan adalah sebagai berikut : Ruang R1 R2 R3 R4 R5 R6 R7 R8 R9
AC OHP Ada Tidak ada Tidak ada Ada Tidak ada Tidak ada Tidak ada Ada Tidak ada Ada Ada Ada Tidak ada Tidak ada Tidak ada Tidak ada Tidak ada Ada Tabel 1
Tape Tidak ada Ada Tidak ada Tidak ada Ada Tidak ada Tidak ada Ada Ada
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 7
Ada berapa ruang yang mempunyai fasilitas AC atau OHP atau Tape ? Penyelesaian : Misal : A1 = Ruang ber-AC A2 = Ruang ber-OHP A3 = Ruang ber-Tape Maka A1 A2 A3
A1 3 A1 A2 2
A2 5
A3 4 A1 A3 1
A2 A3 3
A1 A2 A3 1
Dengan demikian A1 A2 A3 = 3 + 5 + 4 - 2 - 1 - 3 + 1 =7 Contoh 2 : Diketahui banyaknya bilangan bulat antara 1 dan 250 yang habis dibagi oleh 2, 3, 5, dan 7. Misalkan : A1 adalah himpunan bilangan bulat antara 1 dan 250 yang habis dibagi dengan 2, A2 adalah himpunan bilangan bulat antara 1 dan 250 yang habis dibagi dengan 3, A3 adalah himpunan bilangan bulat antara 1 dan 250 yang habis dibagi dengan 5. dan A4 adalah himpunan bilangan bulat antara 1 dan 250 yang habis dibagi dengan 7. Berapakah A1 A2 A3 A4 ? Penyelesaian : 250 250 250 250 A2 83 A1 125 A3 50 A4 35 3 2 5 7 250 A1 A2 41 2 x 3
250 A1 A3 25 2 x 5
250 A1 A4 17 2 x 7
250 A2 A3 16 3 x 5
250 A2 A4 11 3 x 7
250 A3 A4 7 5 x 7
250 A1 A2 A3 8 2 x 3 x 5
250 A1 A2 A4 5 2 x 3 x 7
250 A1 A3 A4 3 2 x 5 x 7
250 A2 A3 A4 2 3 x 5 x 7
250 A1 A2 A3 A4 1 2 x 3 x 5 x 7
Maka akan diperoleh : A1 A2 A3 A4 =125 + 83 + 50 + 35 – 41 – 25– 17 – 16 – 11 – 7 + 8 + 5 + 3 + 2 – 1 = 193.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 8
1.10 Dualitas Dual E* dari sebuah kesamaan E yg melibatan himpunan adalah kesamaan yg didapatkan dg penukaran dengan ∩, ∩ dengan , Ф dengan U, dan U dengan Ф, yaitu dg mengganti pemunculan , ∩, Ф, dan U pd E dengan ∩, , U, dan Ф. Contoh: - (U ∩ A) (B ∩ A) = A Dual: (Ф A) ∩ (B A) = A - (A B) ∩ (A BC) = A Ф dual?
1.11 Kumpulan Himpunan Kumpulan himpunan (class of sets) adalah himpunan yang anggota-anggotanya adalah himpunan. Misalkan X adalah kumpulan himpunan, maka subset dari X disebut juga sebagai subclass.
1.12 Fundamental Produk Suatu fundamental produk dari himpunan A1, A2, ..., An adalah suatu pernyataan berbentuk A1e1 A2e 2 ... Anen di mana Aiei adalah salah satu dari Ai atau AiC . Contoh: Untuk himpunan A, B, dan C, berikut ini merupakan beberapa fundamental produknya: P1 A B C
P2 A B C C P3 A B C C Jumlah fundamental produk untuk n himpunan adalah 2 x 2 x ... x 2 = 2n.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 9
