himpunan - · pdf filecatatan: 1. jika a dan b merupakan ... himpunan mahasiswa yang...
TRANSCRIPT
HIMPUNANAdri Priadana
ilkomadri.com
Definisi
• Set atau Himpunan adalah bentuk dasar
matematika yang paling banyak
digunakan di teknik informatika
• Salah satu topik yang diturunkan dari
Himpunan adalah Class atau collection
Definisi
• Himpunan (set) adalah kumpulan objek-
objek yang berbeda.
• Objek di dalam himpunan disebut
elemen, unsur, atau anggota.
• BEM adalah contoh sebuah himpunan,
di dalamnya berisi anggota berupa
mahasiswa. Tiap mahasiswa berbeda
satu sama lain.
Notasi Himpunan
• Himpunan dinyatakan dg huruf capital
misal : A, B, G
• Sedangkan elemennya dg huruf kecil a,
b, c..,1,2,..
Penyajian Himpunan
1. Enumerasi
menyebutkan semua anggota dari himpunan tersebut.
contoh : Himpunan tiga bilangan ganjil pertama: A = {1,3,5}.
Keanggotaan Himpuan
x A : x merupakan anggota himpunan A;
x A : x bukan merupakan anggota himpunan A.
Contoh 1.
Misalkan: A = {1,3,5,8}, R = { a, b, {a, b, c}, {a, c} }, K = {{}}
maka
1 A,
{a, b, c} R, a R, sedangkan {a} R ,
{} K
Penyajian Himpunan
Contoh 2.
Misalkan: P1 = {a, b}, P2 = { {a, b} }, dan P3 = {{{a, b}}},
maka :
a P1
a P2
P1 P2
P1 P3
P2 P3
Penyajian Himpunan
2. Simbol Simbol Baku
Beberapa simbol baku pada himpunan
N = himpunan bilangan alami (asli) = { 1, 2, 3,... }
Z = himpunan bilangan bulat = { ..., -2, -1, 0, 1, 2, ... }
Q = himpunan bilangan rasional
R = himpunan bilangan riil
C = himpunan bilangan kompleks
sedangkan U menyatakan himpunan semesta.
Contoh: Misalkan U = {a, b, c, d, e} dan A adalahhimpunan bagian dari U, dengan A = {a, d, e}.
Penyajian Himpunan
3. Notasi Persyaratan
A = {x | syarat yang harus dipenuhi oleh x}
contoh :
A adalah himpunan bilangan asli yang lebih kecil dari 10
A = { x | x ≤ 10 dan x ∈ N } atau A = { x ∈ N | x ≤ 10 }
yang ekivalen dengan A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Penyajian Himpunan
4. Diagram Venn
untuk menyatakan relasi antar himpunan
Misal U = {1, 2, …, 7, 8}, A = {1, 2, 3, 5} dan B = {2,
5, 6, 8}.
maka notasi dalam diagram Venn:
U
1 2
53 6
8
4
7A B
Himpunan Berhingga (Finite Set)
• Himpunan yang mempunyai anggota berhingga
disebut himpunan berhingga (finite set)
• Sembarang himpunann yang anggotanya tak
berhingga disebut himpunan tak berhingga(infinite
set)
• contoh A={a,b,c,d,e,f} adalah finite set, sedangkan Z
adalah infinite set.
Kardinalitas
Misalkan A merupakan himpunan berhingga, maka
jumlah elemen berbeda di dalam A disebut kardinal
dari himpunan A. (menyatakan banyaknya anggota
dari himpunan)
Notasi: n(A) atau A
contoh :
(i) B = { x | x merupakan bilangan prima lebih kecil
dari 20}, atau B = {2, 3, 5, 7, 11, 13, 17, 19}
maka B = 8
(iii) A = {t, {t}, {{t}},{{{t}}} }, maka A = 4
Himpunan Kosong (null set)
• Himpunan yang tidak mempunyai anggota atau
kardinalitasnya = 0
• Contoh :
A ={x|x < x} , maka n(A)= 0
• Notasi : {} atau Ø
• {Ø} atau {{}} bukan himpunan kosong karena ia
memiliki satu elemen yaitu Ø atau {}
Himpunan Bagian (Subset)
Himpunan A disebut himpunan bagian (subset) dari
himpunan B jika dan hanya jika setiap anggota A
merupakan anggota dari B.
Dalam hal ini, B dikatakan superset dari A.
Notasi: A B
Diagram Venn:
U
AB
Himpunan Bagian (Subset)
Catatan :
A dan A A, maka dan A disebut himpunan
bagian tak sebenarnya (improper subset) dari himpunan
A.
Contoh: A = {a,b,c}, maka {a,b,c} dan adalah
improper subset dari A.
Himpunan Bagian (Subset)
Contoh.
(i) { a, b, c} {a, b, c, d, e}
(ii) { a, b, c} {a, b, c }
TEOREMA 1. Untuk sembarang himpunan A berlaku hal-hal
sebagai berikut:
(a) A adalah himpunan bagian dirinya sendiri (yaitu, A A).
(b) Himpunan kosong merupakan himpunan bagian dari setiap
himpunan (dalam hal ini A ( A)).
(c) Jika A B dan B C, maka A C
Himpunan Bagian (Subset)
Catatan :
A B tidak sama dengan A B
Pada :
A B : A adalah himpunan bagian dari B tetapi A B.
A adalah himpunan bagian sebenarnya (proper subset) dari B.
Contoh: {a} dan {b,c} adalah proper subset dari {a,b,c}
sedangkan :
A B : digunakan untuk menyatakan bahwa A adalah himpunan
bagian (subset) dari B yang memungkinkan A = B.
Himpunan yang Ekivalen
Himpunan A disebut ekivalen dengan himpunan B jika
dan hanya jika kardinal dari kedua himpunan tersebut
sama.
Notasi : A ~ B A = B
A = { 1,2,3,4} dan B = { ali, budi, joko,tuti }, maka
A ~ B sebab A = B = 4
Himpunan yang Sama
A = B jika dan hanya jika setiap anggota A merupakan
anggota B dan sebaliknya setiap anggota B merupakan
anggota A.. Jika tidak demikian, maka A B.
Notasi : A = B A B dan B A
Himpunan Kuasa Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan
yang anggotanya merupakan semua himpunan bagian dari A,
termasuk himpunan kosong dan himpunan A sendiri.
Notasi : P(A) atau 2A
Jika A = m, maka P(A) = 2m.
Contoh 12.
Jika A = { 1, 2 }, maka P(A) = { , { 1 }, { 2 }, { 1, 2 }}
Contoh 13.
Himpunan kuasa dari himpunan kosong adalah P() = {}, dan
himpunan kuasa dari himpunan {} adalah P({}) = {, {}}.
Himpunan Saling Lepas
Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya
tidak memiliki anggota yang sama.
Notasi : A // B
Diagram Venn: U
A B
Contoh 11.
Jika A = { x | x P, x < 8 } dan B = { 10, 20, 30, ... }, maka A // B.
Operasi Terhadap Himpunan
1. Irisan (intersection)
Notasi : A B = { x x A dan x B }
Contoh
(i) Jika A = {a,b,c,d,e} dan B = {c,e,f,g}, maka A B = {c,e}
(ii) Jika A = { 1,2,3} dan B = { 4,5}, maka A B = . Artinya: A // B
Operasi Terhadap Himpunan2. Gabungan (union)
Notasi : A B = { x x A atau x B }
Contoh:
(i) Jika A = { a, b, c} dan B = { b,c,d,e }, maka A B = {
a,b,c,d,e }
(ii) A = A
Operasi Terhadap Himpunan
3. Komplemen (complement)
Notasi : A = { x x U, x A }
Contoh
Misalkan U = { 1, 2, 3, ..., 7 },
jika A = {1, 3, 4, 6}, maka A = {2, 5, 7}
Operasi Terhadap Himpunan
4. Selisih (difference)
Notasi : A – B = { x x A dan x B } = A B
Contoh.
(i) Jika A = { a, b, c,d,e,f} dan B = { c,d,f},
maka A – B = { a,b,e} dan B – A =
(ii) {1, 3, 5} – {1, 2, 3} = {5},
tetapi {1, 2, 3} – {1, 3, 5} = {2}
Operasi Terhadap Himpunan
5. Beda Setangkup (Symmetric Difference)
Notasi: A B = (A B) – (A B) = (A – B) (B – A)
Contoh 19.
Jika A = { 2, 4, 6 } dan B = { 2, 3, 5 }, maka A B = { 3, 4, 5, 6 }
Operasi Terhadap Himpunan
TEOREMA 2. Beda setangkup memenuhi sifat-sifat berikut:
(a) A B = B A (hukum komutatif)
(b) (A B ) C = A (B C ) (hukum asosiatif)
Contoh 20. Misalkan
U = himpunan mahasiswa
P = himpunan mahasiswa yang nilai ujian UTS di atas 80
Q = himpunan mahasiswa yang nilain ujian UAS di atas 80
Seorang mahasiswa mendapat nilai A jika nilai UTS dan
nilai UAS keduanya di atas 80, mendapat nilai B jika salah
satu ujian di atas 80, dan mendapat nilai C jika kedua ujian
di bawah 80.
(i) “Semua mahasiswa yang mendapat nilai A” : P Q
(ii) “Semua mahasiswa yang mendapat nilai B” : P Q
(iii) “Semua mahasiswa yang mendapat nilai C” : U – (P Q)
Operasi Terhadap Himpunan
6. Perkalian Kartesian (cartesian product)
Notasi: A B = {(a, b) a A dan b B }
Contoh.
(i) Misalkan C = { 1, 2, 3 }, dan D = { a, b }, maka
C D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
(ii) Misalkan A = B = himpunan semua bilangan riil, maka
A B = himpunan semua titik di bidang datar
Operasi Terhadap Himpunan
Catatan:
1. Jika A dan B merupakan himpunan berhingga,
maka: A B = A . B.
2. (a, b) (b, a).
3. A B B A dengan syarat A atau B tidak kosong.
Pada Contoh di atas, C = { 1, 2, 3 }, dan D = { a, b },
D C = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }
C D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
D C C D.
4. Jika A = atau B = , maka A B = B A =
Contoh. Misalkan
A = himpunan makanan = { s = soto, b = bakso, n = nasi
goreng, m = mie ayam}
B = himpunan minuman = { c = coca-cola, t = teh, d = es
jeruk}
Berapa banyak kombinasi makanan dan minuman yang dapat
disusun dari kedua himpunan di atas?
Jawab:
A B = AB = 4 3 = 12 kombinasi dan minuman,
yaitu {(s, c), (s, t), (s, d), (b, c), (b, t), (b, d), (n, c), (n, t), (n, d),
(m, c), (m, t), (m, d)}.
Perampatan Operasi Himpunan
n
iin
AAAA1
21...
n
iin
AAAA1
21...
i
n
inAAAA
121...
i
n
in
AAAA1
21...
Operasi himpunan dapat dilakukan terhadap 2 atau
lebih himpunan.
Dalam hal ini kita akan melakukan perampatan
(generalization) operasi himpunan.
Contoh :
A (B1B2 ... Bn) = (A B1) (A B2) ... (A Bn)
n
ii
n
ii
BABA11
)()(
Hukum yang Berlaku pada
Operasi Himpunan
Contoh Soal
Operasi Terhadap HimpunanDari 45 siswa, diketahui 27 siswa yang menyukai IPA dan
26 siswa menyukai IPS. Siswa yang tidak menyukai
keduanya ada 5 orang. Tentukanlah banyaknya siswa yang
menyukai IPA saja dan IPS saja!
Kita cari terlebih dahulu jumlah siswa yang menyukai kedua
pelajaran tersebut:
n(A ∩ B) = (n(A) + n(B)) - (n(U) – n(X))
n(A ∩ B) = (27 + 26) – (45 – 5)
n(A ∩ B) = 13
Maka dapat disimpulkan bahwa:
Siswa yang menyukai IPA saja = 27 - 13 = 14 siswa
Siswa yang menyukai IPS saja = 26 - 13 = 13 siswa
Prinsip Inklusi-Eksklusi
Ada berapa anggota dalam gabungan
dua himpunan hingga?
|A1 A2| = |A1| + |A2| - |A1 A2|
Contoh
Ada berapa bilangan bulat positif lebih kecil atau sama dengan
100 yang habis dibagi 6 atau 9?
Solusi :
Misalkan A: himpunan bilangan bulat dari 1 sampai 100 yang
habis dibagi 6
B: himpunan bilangan bulat dari 1 sampai 100 yang
habis dibagi 9.
Dengan menggunakan prinsip inklusi-eksklusi, banyaknya
bilangan bulat dari 1 sampai 100 yang habis dibagi 6 atau 9
adalah
2251116
18/1009/1006/100
||||||||
BABABA
Contoh
Misalkan ada 1467 mahasiswa angkatan 2004 di ITB. 97 orang di antaranya adalahmahasiswa TI, 68 mahasiswa SI, dan 12 orang mahasiswa double degree TI dan SI.
Ada berapa orang yang tidak kuliah di TI atauSI?
Solusi
Misalkan
A: himpunan mahasiswa angkatan 2004 di TI
B: himpunan mahasiswa angkatan 2004 di SI
Maka |A| = 97, |B| = 68, dan |AB| = 12.
Banyaknya mahasiswa angkatan 2004 di TI atau MI adalah
|A B| = |A| + |B| - |A B|= 97 + 68 – 12 = 153
Jadi, terdapat 1467 – 153 = 1314 mahasiswa angkatan2004 yang tidak kuliah di TI atau MI.
Perluasan Prinsip Inklusi-Eksklusi
untuk tiga himpunan
Angka 1 merah menunjukkan daerah yang terlibat ketika |A| dihitung,
angka 1 hijau menunjukkan daerah yang terlibat ketika |B| dihitung,dan
angka 1 biru menunjukkan daerah yang terlibat ketika |C| dihitung.
Terlihat bahwa daerah yang beririsan dihitung berulang-ulang.
|A B| dikurangkan (dua 1 merah diambil),
|A C| dikurangkan (dua 1 biru diambil), dan
|B C| dikurangkan (dua 1 hijau diambil) Terlihat bahwa penghitungan hampir benar, kecuali pada daerah di mana ketiga himpunan sama-sama beririsan. Maka perlu ditambahkan kembali |A B C|.
Perluasan Prinsip Inklusi-
Eksklusi untuk tiga himpunan
|A B C| = |A| + |B| + |C|
- |A B| - |A C| - |B C|
+ |A B C|
Perluasan Prinsip Inklusi-
Eksklusi untuk tiga himpunan
Sebanyak 115 mahasiswa mengambil mata kuliah
Matematika Diskrit, 71 Kalkulus, dan 56 Geometri.
Di antaranya, 25 mahasiswa mengambil
Matematika Diskrit dan Kalkulus, 14 Matematika
Diskrit dan Geometri, serta 9 orang mengambil
Kalkulus dan Geometri. Jika terdapat 196
mahasiswa yang mengambil paling sedikit satu dari
ketiga mata kuliah tersebut, berapa orang yang
mengambil ketiga mata kuliah sekaligus?
Solusi
Misalkan
MD: himpunan mahasiswa yang mengambil mata kuliah Matematika
Diskrit,
K: himpunan mahasiswa yang mengambil mata kuliah Kalkulus, dan
G: himpunan mahasiswa yang mengambil mata kuliah Geometri.
Maka
|MD| = 115, |KPB| = 71, |G| = 56,
|MD K| = 25, |MD G| = 14, |K G| = 9, dan
|MD K G| = 196
Dengan mempergunakan prinsip inklusi-eksklusi:
|MDKPBG| = |MD| + |K| + |G| - |MDK| - |MDG| - |KG|
+ |MDKG|
196 = 115 + 71 + 56 - 25 - 14 - 9 + |MD K G|
Jadi, |MD KPB G| = 2
Prinsip Inklusi-Eksklusi
Teorema 1.
Misalkan A1, A2, …, An himpunan hingga.
Maka
||)1(||
||||||
21
1
1
11
221
n
n
kj
nkji
i
j
nji
i
ni
i
AAAAAA
AAAAAA
Contoh 4 Himpunan
|ABCD| = |A| + |B| + |C| + |D| -
|AB| - |AC| - |AD| - |BC| - |BD|- |CD|
+ |ABC|+ |ABD|+ |ACD|+ |BCD|
- |A B C D|
Matur Nuwun