Teori
Himpunan
Pelajarilah semesta ini. Jangan merasa kecewa jika dunia
tidak mengenal anda,tetapi
kecewalah jika anda tidak mengenal dunia.
(Kong
Fu Tse – filusuf China)
Dalam kehidupan
sehari-hari kita sering membicarakan objek-objek diskrit, misalnya buku, komputer,
mahasiswa, nilai ujian, dan lain-lain. Ilmu Komputer atau Informatika menjadikan objek-objek diskrit sebagai titik
pokok pembicaraan. Pada prakteknya, data yang diolah oleh komputer adalah
bentuk diskrit, misalnya data angka, data karakter, data suara (digital), data
gambar (digital).
Dalam membicarakan objek diskrit, kita sering
berhadapan dengan situasi yang berhubungan dengan sekumpulan objek didalam
suatu kelompok atau kelas, dan kita mengacu objek yang termasuk di dalam suatu
kelompok. Misalnya, ”semua mahasiswa Pendidikan Teknik Informatika Undiksha Angkatan
2008” adalah sebuah kelompok yang terdiri atas sejumlah mahasiswa Undiksha Angkatan
2008 dari jurusan Pendidikan Teknik Informatika.
Terminologi dasar tentang sekumpulan objek diskrit
adalah himpunan. Himpunan digunakan
untuk mengelompokkan objek bersama-sama. Teori himpunan merupakan konsep paling
dasar dalam pembahasan objek-objek diskrit. Banyak konsep Ilmu
Komputer/Informatika yang diacu dalam terminologi himpunan. Kuliah Matematika
Diskrit ini kita mulai dari konsep himpunan ini.
1.1
Definisi
Himpunan
Cukup
banyak definisi tentang himpunan. Definisi
yang kita pakai di sini diambil dari [LIU85].
|
Himpunan (set) adalah kumpulan objek-objek yang berbeda.
Seperti yang kita singgung di bagian
pengantar, himpunan digunakan untuk mengelompokkan sejumlah objek. Objek yang
terdapat di dalam himpunan disebut elemen,
unsur, atau anggota.
1.2
Penyajian Himpunan
Terdapat banyak cara untuk menyajikan
himpunan. Di sini kita mengemukakan 4 cara penyajian, yaitu mengenumerasi
elemen-elemennya, menggunakan simbol-simbol baku, menyatakan syarat
keanggotaan, dan menggunakan diagram Venn.
- Enumerasi Mengenumerasi artinya menuliskan semua elemen himpunan yang bersangkutan di antara dua buah tanda kurung kurawal. Biasanya suatu himpunan diberi nama dengan menggunakan huruf kapital maupun dengan menggunakan simbol-simbol lainnya.
|
Himpunan A yang berisi empat buah bilangan asli
pertama dapat ditulis sebagai .
A = {1, 2, 3, 4}.
|
Himpunan B yang berisi lima buah bilangan genap positif pertama adalah
B = {4, 6, 8, 10}.
|
Meskipun himpunan biasanya digunakan untuk
mengelompokkan objek yang mempunyai sifat mirip, tetapi dari definisi himpunan
kita mengetahui bahwa sah-sah saja elemen-elemen di dalam himpunan tidak
mempunyai hubungan satu sama lain, asalkan berbeda.
Sebagai contoh, {kucing, a, Amir, 10, paku} adalah himpunan yang terdiri dari
lima elemen, yaitu kucing, a, Amir, 10, paku.
|
Contoh-contoh himpunan lainnya:
R = {a, b, {a,b,c},{a, c}}. C = {a,{a},{{a}}} k = {{}}.
Perhatikan dari contoh 1.4, C adalah himpunan yang terdiri
dari 3 elemen, yaitu a, {a}, dan {{a}}. Contoh 1.4
memperlihatkan bahwa suatu himpunan dapat merupakan anggota himpunan lain. Perhatikan
juga bahwa K hanya berisi satu elemen, yaitu {}. Lebih lanjut, {} disebut
himpunan kosong, sering dilambangkan dengan Ø (lihat upabab 1.4).
Untuk menuliskan
himpunan dengan jumlah anggota yang besar dan telah memiliki urutan tertentu
dapat dilakukan dengan menggunakan tanda ’...’(ellipsis).
|
Himpunan
alfabet ditulis sebagai {a,b,c,....... x,y, z}., dan himpunan 100 buah bilangan asli pertama ditulis sebagai
{1,2.....100}.
Untuk menuliskan
himpunan yang tak berhingga banyak anggotanya, kita dapat juga menggunakan
tanda ’...’(ellipsis).
|
Himpunan bilangan bulat positif ditulis sebagai {1,2,3....}.
Terhadap suatu
himpunan, suatu objek dapat menjadi anggota atau bukan anggota himpunan
tersebut. Untuk menyatakan keanggotaan tersebut digunakan notasi berikut:
untuk menyatakan x
merupakan anggota himpunan A; dan
untuk menyatakan x
bukan merupakan anggota himpunan A.
|
Misalkan dan , maka
|
Bila maka
2. Simbol-simbol Baku
Terdapat
sejumlah simbol baku yang biasa digunakan untuk mendefinisikan himpunan yang
sering digunakan, antara lain:
P = himpunan bilangan bulat positif = {1,2,3,...}
N = himpunan bilangan alami (natural) = {1,2,...}
Z = himpunan bilangan bulat = {...,-2,-1,0,1,2,...}
Q = himpunan bilangan rasional
R = himpunan bilangan riil
C = himpunan bilangan kompleks
Kadang-kadang
kita berhubungan dengan himpunan-himpunan yang semuanya merupakan bagian dari
sebuah himpunan yang universal. Himpunan yang universal ini disebut semesta dan
disimbolkan dengan U. Himpunan U harus diberikan secara
eksplisit atau
diarahkan berdasarkan pembicaraan. Sebagai contoh, misalnya U = {1,2,3,4,5} dan A adalah himpunan bagian dari U,
dengan A = {1,3,5}.
3. Notasi Pembentuk Himpunan
Cara lain
menyajikan himpunan adalah dengan notasi pembentuk himpunan (set builder). Dengan cara penyajian ini,
himpunan dinyatakan dengan menulis syarat yang harus dipenuhi oleh anggotanya.
|
Aturan dalam
penulisan syarat keanggotaan:
a. Bagian di kiri tanda ’|’ melambangkan
elemen himpunan
b. Tanda ’|’ dibaca dimana atau sedemikian sehingga
c. Bagian di kanan tanda ’|’ menunjukkan
syarat keanggotaan himpunan
d. Setiap tanda ’,’ di dalam syarat
keanggotaan dibaca sebagai dan
|
(i)
A adalah himpunan bilangan bulat positif yang kecil
dari 5,dinyatakan sebagai
A = {x|x adalah himpunan bilangan bulat positif lebih kecil dari 5}
Atau dalam
notasi lain yang lebih ringkas:
}
Yang
ekivalen dengan {1,2,3,4}
(ii). B adalah himpunan bilangan genap positif yang lebih kecil atau sama dengan
8, dinyatakan sebagai
B = {x|x
adalah himpunan bilangan genap positif lebih kecil atau sama dari 8}
Atau dalam notasi lain yang
lebih ringkas:
Yang ekivalen dengan {2,4,6,8}
(iii) Notasi pembentuk himpunan sangat berguna
untuk menyajikan himpunan yang
anggota-anggotanya tidak mungkin dienumerasikan. Misalnya Q adalah himpunan bilangan rasional,
dinyatakan sebagai
(iv) M adalah himpunan mahasiswa yang mengambil kuliah Matematika Diskrit,
M = {x|x adalah mahasiswa yang mengambil kuliah Matematika Diskrit}
4. Diagram Venn
Diagram Venn menyajikan
himpunan secara grafis. Cara penyajian himpunan ini diperkenalkan oleh
matematikawan Inggris yang bernama John Venn pada tahun 1881. di dalam diagram
Venn, himpunan semesta (U)
digambarkan sebagai suatu segi empat sedangkan himpunan lainnya digambarkan
sebagai lingkaran di dalam segi empat tersebut.
Misalkan dan .
Ketiga himpunan tersebut digambarkan
dengan diagram Venn
Pada Gambar 2.1.
Gambar 1.1
Diagram Venn untuk Contoh 1.10
1.3
Kardinalitas
Misalkan A merupakan himpunan yang
elemen-elemennya berhingga banyaknya. Jumlah elemen A disebut kardinal dari himpunan A.
Catatan
Di
dalam buku ini, kita menggunakan notasi |A|
untuk menyatakan kardinalitas himpunan.
(i)
B = {x|x merupakan bilangan prima yang lebih
kecil dari 20},
Maka |B| = 8, dengan elemen-elemen B adalah 2,3,5,7,11,13,17,19
T = {kucing, a, Amir, 10, paku} maka |T| = 5, dengan elemen-elemen T (yang berbeda) adalah kucing, a, Amir,
10, dan paku.
(ii)
A = {a, {a}, {{a}}, maka |A| = 3, dengan elemen-elemen A
(yang berbeda) adalah a, {a}, dan {{a}}.
Himpunan yang
tidak berhingga banyak anggotanya
mempunyai kardinalitas tidak berhingga pula. Sebagai contoh, himpunan bilangan
riil mempunyai jumlah anggota tidak berhingga, maka |R| = ∞.
1.4
Himpunan Kosong
Himpunan yang tidak memiliki
satupun elemen atau himpunan dengan kardinal = 0 disebut himpunan kosong (null set).
(i)
E = {x|x<x},
maka n(E) = 0
(ii)
P = {orang Indonesia
yang pernah ke bulan}, maka n(P) = 0
(iii)
A = {x|x
adalah akar-akar persamaan kuadrat },
n(A) = 0
perhatikan bahwa himpunan {{
}} dapat juga ditulis sebagai {Ø}, begitu pula himpunan {{ }, {{ }}} dapat juga
ditulis sebagai {Ø, {Ø}}.
1.5 Himpunan
Bagian (subset)
Himpunan A dikatakan himpunan bagian dari himpunan B jika dan hanya jika setiap elemen A merupakan elemen dari B.
Dalam hal ini, B dikatakan superset dari A.
Dalam diagram Venn, A B digambarkan pada Gambar 1.2.
Gambar
1.2 Diagram Venn untuk AB
(iii) {1,2,3} {1,2,3,4,5}
(iv) {1,2,3} {1,2,3}
(v)
N Z R C
(vi)
Jika A =
{(x,y)|x + y <4,x , y 0 } dan B = 0 dan y 0}, maka B A.
Perlu dicatat, bahwa untuk sembarang himpunan A,
1.
A adalah
himpunan bagian dari A itu
sendiri (A A ),
2.
himpunan
kosong merupakan himpunan bagian dari A
(Ø A).
Dari (1) dan
(2) di atas, bahwa Ø A dan A A, maka Ø dan A disebut
himpunan bagian tak sebenarnya (improper
subset) dari himpunan A. Sebagai contoh, jika A = {1,2,3}, maka {1,2,3} adalah improper subset dari A. Untuk membuktikan bahwa Ø A, kita harus memperlihatkan bahwa implikasi ”jika x Ø, maka x A” selalu benar ( sesuai dengan definisi himpunan bagian ). Kita
hanya perlu menyatakan bahwa bagian hipotesis (yaitu x Ø) selalu bernilai
salah karena Ø tidak mempunyai anggota. Oleh karena itu, kalimat tersebut akan
selalu bernilai benar tanpa tergantung kepada himpunan A.
Jika kita
ingin menekankan bahwa A adalah
himpunan bagian dari B tetapi A ≠ B
maka kita menulis A B, dan kita katakan bahwa A
adalah himpunan bagian sebenarnya (proper
subset) dari himpunan A. Sebagai contoh, himpunan {1} dan
{2,3} merupakan proper subset dari {1,2,3}.
Catatlah bahwa
himpunan {Ø } bukan merupakan himpunan bagian dari himpunan {{Ø}}, namun ia
merupakan anggota himpunan{{Ø }}.
1.6
Himpunan yang Sama
Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika setiap elemen A merupakan elemen B dan sebaliknya setiap elemen B
merupakan elemen A. Sebaliknya, A
tidak sama dengan B.
|
(i)
jika A = {0,1} dan B = {x|x (x-1) = 0}, maka A
= B
(ii)
jika A = {3,5,8,5} dan B = {5,3,8}, maka A = B
(iii) jika A
= {3,5,8,5} dan B = {3,8}, maka A ≠ B
tiga prinsip yang perlu diingat dalam memeriksa
kesamaan dua buah himpunan:
1.
urutan elemen dalam himpunan tidak
penting.
Jadi {1,2,3} = {3,2,1} = {1,3,2}
2.
pengulangan elemen tidak mempengaruhi
kesamaan dua buah himpunan.
Jadi, {1,1,1,1}={1,1}={1}
{1,2,3}={1,2,1,3,2,1}
3.
untuk tiga buah himpunan, A, B,
C berlaku aksioma berikut:
(a)
A = A, B = B,
dan C = C
(b)
Jika A = B, maka B = A
(c)
Jika A = B, dan B = C maka A = C
1.7
himpunan yang ekivalen
definisi 1.5.
himpunan A dikatakan ekivalen
dengan himpunan B jika dan hanya jika kardinal
dari kedua himpunan tersebut sama.
|
Contoh 1.15.
Jika A = {1,3,5,7} dan B = {a,b,c,d}, maka A~B
1.8
HIMPUNAN SALING LEPAS
Definisi 1.6.
Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak memiliki
elemen yang sama.
|
Diagram Venn yang menggambarkan dua
himpunan yang saling lepas ditunjukan pada gambar 1.3.
Gambar 1.3
diagram venn untuk A Í B
Contoh 1.16
Jika A = { x | x Î P,x < 8} dan B = {10,20,30,....}, maka
A // B
1.9 HIMPUNAN KUASA
Definisi
1.7
Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan yang elemennya
merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A
itu sendiri.
|
Contoh 1.17.
Jika A =
{1,2}, maka P(A) = {Ø, {1}, {2}, {1,2}}
Contoh 1.18.
Himpunana kosong dari himpunan kosong
adalah P(Ø) = {Ø}, dan himpunan kuasa dari {Ø} adalah P({Ø}) = {Ø,{Ø} }}.
Berapa banyak anggota himpunan kuasa dari sembarang himpunan A? Jika |A| = m,
maka |P(A)| = 2m . Kardinalitas himpunan kuasa ini dapat dibuktikan
sebagai berikut:
Bukti:
Susun elemen-elemen A sebagai barisan (a1,a2,.....an).
Bentuk himpunan bagian Ai dari A dan juga
bentuk barisan-barisan biner
Ei = (e1i, e2i,.......eni}
Dengan
eji = 1 bila aj ada di dalam Ai
eji = 0 jika aj tidak ada di dalam Ai
Banyaknya kombinasi Ei yang
mungkin adalah 2n-1. mengingat himpunan kosong juga merupakan
himpunan bagian A, maka terbukti bahwa jumlah himpunan bagian dari himpunan A
sama dengan 2n.
1.10 OPERASI
TERHADAP HIMPUNAN
a. Irisan
Definisi 1.8
Irisan
(intersection) dari himpunan A dan B adalah himpunan yang setiap elemennya
merupakan elemen dari himpunan A dan himpunan B.
|
Diagram venn untuk A Ç B ditunjukan pada gambar 1.4
Gambar 1.4 diagram
venn untuk A Ç B (daerah A Ç B diarsir)
Pada dua himpunan yang saling
lepas, irisannya adalah himpunan kosong.
Contoh 1.19.
Tinjau (i),
(ii), dan (iii) di bawah ini.
(i)
Jika A = {2,4,6,8,10} dan B = {4,10,14,18},
maka A Ç B = {4,10}.
(ii)
Jika A = {(x,y) | x + y = 7, x,y ÎR} dan B = {(x,y) |x – y = 3,x,y Î R}, maka A Ç B = {(5,2)}
(iii)
Jika A = {3,5,9} dan B = {-2,6}, maka A Ç B = Ø. Artintya:A//B
b. Gabungan
Definisi 1.9
Gabungan(union) dari himpunan
A dan B adalah himpunan yang setiap
anggotanya merupakan anggota himpunan A atau himpunan B.
|
diagram venn untuk A È B ditunjuk pada gambar 1.5
|
Gambar 1.5 diagram venn untuk A È B(daerah A È B diarsir)
Contoh 1.20.
Tinjau (i) dan (ii) di bawah ini.
(i) Jika
A = {2,5,8} dan B = {7,5,22}, maka A È B = {2,5,7,8,22}
(ii)
A È Ø = A
c. Komplemen
definisi 1.10.
Komplemen dari suatu himpunan
A terhadap suatu himpunan semesta U adalah suatu himpunan yang elemennya
merupakan elemen U yang bukan elemen A.
diagram venn untuk Ā ditunjuk pada gambar 1.6
contoh 1.21.
misalkan U = { 1, 2, 3
,............9},
(i) Jika A = {1,3,7,9}, maka Ā
= {2,4,6,8}
(ii) Jika A = {x|x/2Î P, x < 9}, maka Ā = {1,3,5,7,9}
Gambar 1.6 Diagram venn untuk Ā (daerah Ā diarsir)
Contoh 1.22.
Misalkan:
A = himpunan semua mobil
buatan dalam negeri
B = himpunan semua mobil impor
C = himpunan semua mobil yang
dibuat sebelum tahun 1990
D = himpunan semua mobil yang
nilai jualnya kurang dari Rp 100 juta
E = himpunan semua mobil milik
mahasiswa universitas tertentu
(i) pernyataan ”mobil universitas ini produksi
dalam negeri atau diimpor dari luar
negeri” dapat dinyatakan dalam notasi himpunan sebagai ( E ∩ A) U (E ∩
B) atau E Ç ( A È B)
(ii) Pernyataan ”semua mobil produksi dalam negeri
yang dibuat sebelum tahun 1990 yang nilai jualnya kurang dari 100 juta” dapat
dinyatakan dalam notasi himpunan sebagai A Ç C ÇD
(iii) Pernyataan bahwa ”semua mobil impor buatan
setelah tahun 1990 mempunyai nilai jual lebih dari Rp 100 juta dapat dinyatakan
dalam notasi himpunan sebagai
d. Selisih
Definisi 1.11.
Selisih dari dua himpunan A
dan B adalah suatu himpunan yang elemennya merupakan elemen A dan bukan elemen
B. Selisih antara A dan B dapat juga dikatakan sebagai komplemen himpunan B
relatif terhadap himpunan A.
|
Diagram
venn untuk A – B ditunjuk pada gambar 1.7
|
Gambar 1.7
diagram venn untuk A – B (daerah A – B diarsir)
Contoh 1.23.
Tinjau (i),
(ii), (iii), dan (iv) di bawah ini.
(i)
Jika
A = {1, 2, 3,......10} dan B = {2, 4, 6, 8, 10}, maka A – B = {1, 3, 5, 7,9}
dan B – A = Ø
(ii)
{1, 3, 5} – {1, 2, 3} = {5}, tetapi{1, 2, 3} – {1, 3,
5} = {2}
(iii)
A = himpunan fungsi terus menerus ( kontinu) dan
terbatas di dalam selang [0.1]
B = himpunan fungsi differentiable di dalam selang [0.1]
B – A = himpunan fungsi diferentiable tidak terbatas di dalam
selang [0.1]
(iv)
Komplemen
dari sembarang himpunan A terhadap semesta U dapat juga didefinisikan sebagai Ā
= U – A
e. Beda setangkup (symmetric difference)
Definisi 1.12.
Beda setangkup dari himpunan A dan B adalah sesuatu himpunan yang
elemennya ada pada himpunan A atau B, tetapi tidak pada keduanya.
|
Diagram
venn untuk AÅ B diarsir ditunjukan pada gambar 1.8.
Gambar 1.7
diagram venn untuk A Å B
(daerah A Å B diarsir)
Contoh 1.24.
Tinjau (i) dan (ii) di bawah
ini.
(i)
Jika
A = { 2, 4, 6 } dan B = {2, 3, 5}, maka A Å B = {3, 4, 5, 6}
(ii)
A =
himpunan segitiga sama kaki,
B = himpunan segitiga siku-siku,
(iii)
A Å B = himpunan segitiga sama kaki yang tidak siku-siku
dan segitiga siku-siku yang tidak sama kaki.
Contoh 1.25.
Misalkan:
U = Himpunan mahasiswa
P = Himpunan mahasiswa yang nilai ujian UTS di atas 80
Q = Himpunan mahasiswa yang nilai
ujian UAS di atas 80
Seorang mahasiswa mendapat nilai A jika nilai UTS dan UAS keduanya di
atas 80, mendapat nilai B jika salah satu ujian di atas 80, dan mendapat nilai
C jika keduanya di bawah 80. maka dalam notasi himpunan
(i)
pernyataan “semua mahasiswa yang mendapat nilai A”
adalah P Ç
Q
(ii)
pernyataan “semua yang mendapat nilai B” adalah P Å Q
(iii)
pernyataan
“semua mahasiswa mendapat nilai C” adalah U – (P È Q)
f. Perkalian kartesian
Definisi 1.13.
Perkalian kartesian (Cartesian
products) dari himpunan A dan B adalah himpunan yang elemennya semua
pasangan berurutan (ordered pairs)
yang mungkin terbentuk dengan komponen kedua dari himpunan A dan B.
|
Contoh 1.26.
Tinjau (i) dan (ii) di bawah ini.
(i)
misalkan C = {1, 2, 3}, dan D = {a, b}, maka perkalian
kartesian C dan D adalah C x D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3,
b) }
(ii)
misalkan A = himpanan semua bilangan riil, maka A x B =
himpunan semua titik di bidang datar
Catatan
1.
jika A dan B merupakan himpunan berhingga, maka: |A x
B| = |A| . |B|
2.
Pasangan berurutan (a,b) berbeda dengan (b,a).
3. Perkalian
kartesian tidak komutatif, yaitu A x B ¹ B x A dengan syarat A dan
B tidak kosong. Pada contoh
1.24 (i) di atas, D x C = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3) } ¹ C x D.
4. Jika A = Æ atau B = Æ maka A x B = B x A = Æ
Contoh 1.27.
misalkan:
A = himpunan makanan = { s =
soto, g = gado-gado, n = nasi goreng, m = mie rebus}
B = himpunan minimum = { c =
coca-cola, t = teh, d = es dawet}
Berapa banyak kombinasi
makanan dan minuman yang dapat disusun dari kedua himpunan di atas?
Jawab
| Ax B | = | A| . | B | = 4.3 = 12 kombinasi makanan dan minuman, yaitu
{(s, c), (s, t), (s, d), (g, c), (g, t), (g, d), (n, c), (n, t), (n, d), (m,
c), (m, t),(m, d)}.
1.11 Sifat- Sifat Operasi Himpunan
1.
Hukum identitas:
-
A È Æ = A
-
A Ç U = A
-
A Å Æ = A
|
2.
Hukum null:
-
A Ç Æ = Æ
-
A È U = U
-
A Å A = Æ
|
3.
Hukum Komplemen
- A È Ā = U
- A Ç Ā = Æ
|
4. hukum idempotent:
- A È A = A
-A Ç A = A
|
5. Hukum Involusi:
- = A
|
6. Hukum Penyerapan:
- AÈ(AÇB)
= A
- AÇ(AÈB)
= A
|
7.
Hukum Komutatif:
- A È B = B È A
- A Ç B = B Ç A
- A Å B = B Å A
|
8. Hukum Asosiatif:
-
A È (B È C)=(A È B) È C
-
A Ç (B Ç C)=(A Ç B) Ç C
-
A Å (B Å C)=(A Å B) Å C
|
9. Hukum distributif :
- AÈ(B Ç C) = (AÈB)Ç (AÈC)
- A Ç (BÈC) = (AÇB) È (AÇC)
|
10. Hukum DeMorgan :
-
-
|
11. Hukum 0/1:
-`f = U
-`U = Æ
|
|
1.12 Perapatan Operasi Himpunan
Perapatan (generalization) operasi dapat dilakukan dengan menggunakan dasar perapatan yang ada pada operasi
aritmatika biasa.
Misalkan A1, A2,A3,....,An
merupakan himpunan, maka:
|
Contoh 1.28.
Misalkan:
A1={0,2,3}
A2={1,2,3,6}
A3={-1,0,3,9}
Maka,
= {-1,0,1,2,3,6,9}
Contoh 1.29.
Misal
A = {1,2},B =
{a,b} dan C = {a,b},
Maka
A X B X C = {(1,a,a), (1,a,b), (1, b, a), (1, b, b), (2, a,a), (2,a,b), (2,b,a),(2,b,b)}
Notasi
perapatan diatas dapat mempermudah penulisan ekspresi yang panjang, misalnya:
A Ç (B1 È B2 È......È Bn) = (A Ç B1) È (A ÇB2) È...È(A ÇBn)
Menjadi: AÇ
1.13 Prinsip Inklusi-Ekslusi
Berapa banyak anggota didalam
gabungan dua buah himpunan A dan B? Penggabungan dua buah menghasilkan dua buah
himpunan baru yang elemen-elemenya berasal dari himpunan A dan himpunan B.
Himpunan A dan himpunan B
mungkin saja memiliki elemen-elemen yang sama. Banyaknya elemen bersama antara
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 didalam çAÈBç, karena itu, jumlah elemen hasil
penghubungan seharusnya adalah jumlah elemen dimasing-masing himpunan dikurangi
dengan jumlah elemen didalam irisannya, atau çAÈBç = çAç + çBç- çAÇBç
Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi.
Dengan cara yang sama, kita dapat menghitung jumlah elemen hasil operasi beda
setangkup:
çA Å Bç = çAç + çBç - 2çA Ç Bç
Contoh1.30
Kita ingin menghitung banyaknya bilangan bulat antara 1 dan 100 yang habis
dibagi 3 atau 5.
Misalkan,
A = himpunan bilangan bulat yang habis dibagi 3
B = himpunan bilangan bulat yang habis dibagi 5
A Ç B =
himpunan bilangan bulat yang habis dibagi 3*5 yang ditanyakan
adalah çAÈBç?
Terlebih dahulu harus dihitung
çAç = ë100/3û = 33, çBç= ë100/5û = 20, çA
Ç Bç= ë100/ (3
* 5) û = 6
Untuk mendapatkan
çA È Bç= çAç + çBç-çA Ç Bç= 33 + 20-6 = 47
Jadi, ada 47 buah bilangan yang habis dibagi 3 atau 5.
Prinsip inklusi dapat dirapatkan lebih dari dua
buah himpunan, untuk tiga buah himpunan A,B dan C, berlaku
çA È B È C ç= çAç + çBç + çCç- çAÇBç - çA Ç Cç- çB Ç Cç + çA Ç B Ç Cç
Kerjakan 1 :
Sebanyak 1232 orang mahasiswa
mengambil mata kuliah Bahasa Inggris. 879 orang mengambil kuliah Bahasa
Perancis, dan 114 mengambil kuliah Bahasa Jerman. Sebanyak 103 orang mengambil
kuliah Bahasa Inggris dan Perancis, 23 orang mengambil kuliah Bahasa Inggris
dan Jerman, dan 14 orang mengambil kuliah Bahasa Perancis dan Bahasa Jerman.
Jika 2092 orang mengambil paling sedikit satu buah kuliah Bahasa Inggris,
Bahasa Perancis, dan Bahasa Jerman, Berapa banyak mahasiswa yang mengambil
kuliah ketiga buah Bahasa tersebut???
1.14 Prinsip
Dualitas
Pada upabab 1.10 kita dapat melihat
bahwa beberapa sifat operasi himpunan merupakan analog satu sama lain. Sebagai
contoh, pada hukum komplemen, A = U analog dengan A = Ø, begitu juga pada hukum asosiatif, A (B C) = (A B) C analog dengan A (B C) = (A B) C. Hukum yang satu diperoleh dari hukum yang
lain dengan cara mengganti tanda dengan , dengan , Ø dengan
U, U dengan Ø, dan membiarkan komplemen tetap seperti dinyatakan sebelumnya. Prinsip
ini dikenal sebagai Prinsip Dualitas.
Definisi
1.14.
Prinsip
dualitas pada himpunan. Misalkan S adalah suatu kesamaan yang melibatkan
himpunan dan operasi-operasi seperti komplemen, dan . Jika S* diperoleh dari S dengan mengganti → , → , Ø → U, U → Ø, maka kesamaan S*
juga benar dan disebut dual dari kesamaan S.
Prinsip
dualitas merupakan Prinsip yang penting dalam aljabar himpunan, karena kita
dapat menggunakan prinsip ini untuk menurunkan hukum yang lain atau membuktikan
suatu kalimat himpunan.
1. Hukum
identitas:
A Ø = A
|
Dualnya:
A U = A
|
2.
Hukum null:
A Ø = Ø
|
Dualnya :
A U = U
|
3.
Hukum komplemen:
A = S
|
Dualnya:
A = Ø
|
4.
Hukum idempoten:
A A = A
|
Dualnya:
A A = A
|
5.
Hukum penyerapan:
A (A B) = A
|
Dualnya:
A (A B) = A
|
6.
Hukum komutatif:
A B = B A
|
Dualnya:
A B = B A
|
7.
Hukum asosiatif:
A (B C) = (A B) C
|
Dualnya:
A (B C) = (A B) C
|
8. Hukum distributif:
A (B C) = (A B) (A C)
|
Dualnya:
A (B C) = (A B) (AC)
|
9.
Hukum komutatif:
A B = B A
|
Dualnya:
A B = B A
|
10. Hukum De Morgan:
=
|
Dualnya:
=
|
11. Hukum 0/1
=
|
Dualnya:
= Ø
|
Contoh 1.32.
Dual dari (A
B) (A ) = A adalah (A B) (A ) =
A.
1.15
Partisi
Tinjau sekumpulan mahasiswa di sebuah
kelas. Bagaimana caranya agar dosen membagi (partisi) himpunan ini?
Dosen dapat membagi menjadi beberapa buah himpunan bagian, yang dalam hal ini
setiap himpunan bagian mungkin berisi 1 orang mahasiswa, 2 orang mahasiswa, dan
seterusnya, bahkan kosong. Tidak ada mahasiswa yang sama berada dalam dua atau
lebih himpunan bagian yang berbeda. Gabungan dari seluruh himpunan bagian itu
adalah seluruh mahasiswa dalam kelas.
Definisi
1.15.
Partisi
dari sebuah himpunan A adalah sekumpulan himpunan bagian tidak kosong A1,A2
…..dari A sedemikian sehingga :
(a)
A1 A2 …. = A, dan
(b)
Himpunan bagian Ai saling lepas; yaitu
Ai ∩ Aj = Ø untuk i ≠ j
Contoh
1.33.
Misalkan
A = { 1, 2, 3, 4, 5, 6, 7, 8}, maka { {1},{2, 3, 4},{7, 8},{5, 6}} adalah
partisi A.
Catatlah
bahwa partisi membagi himpunan A menjadi beberapa buah “blok”. Pada contoh
diatas, himpunan A dibagi menjadi 4 buah blok, yaitu {1},{2, 3, 4},{7, 8}, dan
{5, 6}. Jika himpunan A terbatas jumlah elemennya, maka jumlah blok yang dapat
dibentuk tidak lebih besar dari │A│.
1.16
Multiset
Dari definisi
himpunan, himpunan adalah kumpulan elemen yang berbeda. Namun pada beberapa
situasi, adakalanya elemen himpunan tidak seluruhnya berbeda, misalnya himpunan
nama-nama mahasiswa di sebuah kelas. Nama-nama mahasiswa di dalam sebuah kelas
mungkin ada yang sama, karena itu ada perulangan elemen yang sama di dalam
himpunan tersebut. Himpunan yang elemennya boleh berulang (tidak harus berbeda)
disebut himpunan-ganda atau multiset.
Contohnya, {1, 1, 1, 2, 2, 3}, {2, 2, 2}, {2, 3, 4}, {} adalah himpunan
ganda. Multiplisitas dari suatu elemen pada multiset adalah jumlah
kemunculan elemen tersebut pada multiset. Sebagai contoh: Jika M
= { 0, 1, 01, 1, 0, 001, 0001, 00001, 0, 0, 1}, maka multiplisitas elemen 0
adalah 4.
Himpunan
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, dengan mengasumsikan elemen-elemen di dalam multiset semua
berbeda.
Operasi
Antara Dua Buah Multiset:
DEFINISI 1.16.
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 1.34.
Jika
P = { a, a, a, c, d, d} dan Q = { a, a, b, c, c }, maka 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 1.35.
Jika P = { a, a, a, c, d, d } dan Q
= { a, a, b, c, c } maka P Q = { a, a, c }
3. P
– Q adalah suatu multiset yang multiplisitas elemennya sama dengan:
–
multiplisitas elemen tersebut pada P dikurangi
multiplisistasnya pada Q, jika selisihnya positif
–
0, jika selisihnya nol atau negative
Contoh 1.36.
Jika P = { a, a, a,
b, b, c, 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. Catatan: Beda setangkup tidak
didefinisikan pada multiset.
Contoh
1.37.
Jika
P = { a, a, b, c, c } dan Q = { a, b, b, d } maka P + Q = { a, a, a, b, b, b,
c, c, d }
1.17 Pembuktian Kalimat Himpunan
Kalimat himpunan adalah
pernyataan yang menggunakan notasi himpunan. Kalimat dapat berupa
kesamaan himpunan, misalnya “A (B C) = (A B) (A C)” adalah sebuah
kesamaan himpunan, atau berupa kalimat implikasi seperti “jika A B = Ø dan A (B C) maka selalu
berlaku bahwa A C”.
Terdapat beberapa metode untuk membuktikan kebenaran suatu atau kalimat
himpunan. Penggunaan metode bergantung pada kalimat akan dibuktikan. Untuk
suatu kalimat himpunan, kita dapat membuktikannya dengan beberapa cara yang
menghasilkan kesimpulan benar. Dibawah ini dikemukakan beberapa cara pembuktian
kalimat himpunan.
1.
Pembuktian dengan Diagram Venn
Buatlah diagram venn untuk ruas kiri kesamaan dan diagram Venn untuk ruas
kanan kesamaan. Jika diagram Venn keduanya sama, berarti kesamaan tersebut
benar.
Contoh 1.38.
Misalkan A, B, dan C
adalah himpunan. Buktikan A
(B C) = (A B) (A C) dengan diagram Venn.
Bukti:
Diagram Venn untuk ruas
kiri dan kanan masing-masing ditunjukan pada Gambar 1.8. Dari diagram
Venn untuk masing-masing ruas diatas, keduanya memberikan area arsiran yang
sama. Jadi, terbukti bahwa A (B C) = (A B) (A C).
Gambar 1.8 Diagram Venn untuk pembuktian
A (B C) = (A B) (A C).
Dengan diagram Venn, pembuktian dapat dilakukan dengan cepat. Ini adalah
kelebihan metode ini. Namun, kekurangannya, diagram Venn hanya dapat digunakan jika
himpunan yang digambarkan tidak banyak jumlahnya. Selain itu, metode ini mengilustrasikan
ketimbang membuktikan fakta. Banyak matematikawan yang tidak menganggapnya
sebagai metode valid untuk pembuktian secara formal.
2.
Pembuktian dengan Menggunakan Tabel Keanggotaan
Kesamaan
himpunan juga dapat dibuktikan dengan menggunakan tabel keanggotaan (membership
tables). Kita menggunakan angka 1 untuk menyatakan bahwa suatu elemen
adalah anggota himpunan, dan 0 untuk menyatakan bukan himpunan (nilai ini dapat
dianalogikan true dan false pada logika Boolean).
Contoh 1.39.
Misalkan A, B, dan C adalah himpunan. Buktikan bahwa
A (B C) =(A B) (A C)
Tabel keanggotaan untuk kesamaan tersebut adalah seperti di bawah ini.
Karena kolom A (B C) dan kolom (A B) (A C) sama, maka kesamaan
tersebut benar.
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
|
3.
Pembuktian dengan Sifat Operasi Himpunan
Sebagai contoh, misalkan A dan B himpunan. Buktikan bahwa
(A B) (A ) = A
Bukti:
(A B) (A ) = A
(B ) (hukum
distributif)
= A (hukum
komplemen)
= A (hukum identitas)
Contoh 1.40.
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) (hukum
komplemen)
= A B (hukum
identitas)
Contoh 1.41.
Misalkan A dan B himpunan. Tunjukan
bahwa
(A – B) – C = (A – C) – B
Bukti:
(A – B) – C = (A ) – C (definisi
operasi selisih)
= (A ) (definisi operasi selisih)
= (A ) (hukum
asosiatif)
= (A – C) (definisi
operasi selisih)
= (A – C) – B (definisi operasi selisih)
Kerjakan 2
:
Tunjukkan
bahwa A () = A
Kerjakan
3 :
Buktikan
bahwa untuk sembarang himpunan A dan B, bahwa
(i)
(ii)
4.
Pembuktian dengan Menggunakan Definisi
Contoh 1.42.
A dan B himpunan. Jika A B = Ø dan A
(B C) maka A C. Buktikan!
Bukti:
(i) Dari
definisi himpunan bagian, jika setiap juga . Misalkan . Karena , maka dari
definisi himpunan bagian, x juga .
Dari
definisi operasi gabungan (),berarti atau
(ii) Karena dan A B = Ø, maka
Dari (i) dan (ii), harus benar.
Karena juga berlaku , maka dapat
disimpulkan .
Contoh 1.45.
Misalkan A, B, dan C adalah tiga buah himpunan. Buktikan jika maka
Bukti:
(i) Karena maka dari definisi himpunan bagian juga adalah
(ii) Karena , maka dari
definisi operasi irisan, jika maka dan .
(iii) Karena maka dari definisi himpunan bagian, juga Jika symbol y diganti dengan x, maka juga
Dari (ii) dan (iii) dapat
disimpulkan bahwa
SOAL
LATIHAN
1.Tentukan apakah pernyataan
dibawah ini benar atau salah:
(a) Ø}{Ø} (b) Ø{Ø}
(c) {Ø}{ Ø} (d)
(e) jika dan , maka
(f) jika dan , maka
(g) jika Ø,{Ø}}, maka Ø
(h) jika Ø,{Ø}}, maka {{Ø}}
(i) Ø Ø (j) ØØ
(k) {Ø}Ø (l)
(m)
(n)
(o) jika dan, maka
(p) jika dan , maka
2. Jika Ø} dan , tentukan himpunan berikut:
(a) A - Ø (b) A - { Ø} (c) {{a,c}} – A
(d) (e) {a} – {A} (f) P(A – B)
(g) Ø – A (h) (i)
(j)
3. Jika
diketahui dan (tunjukan bahwa
.
4. Jika diketahui
, apakah berarti bahwa B = C?
5. Misalkan A himpunan mahasiswa tahun pertama, B himpunan mahasiswa tahun
kedua, C himpunan mahasiswa Jurusan Mtematika, D himpunan mahasiswa jurusan Teknik
Informatika, E himpunan mahasiswa yang mengambil kuliah Matematika Diskrit, F
himpunan mahasiswa yang menonton pertunjukan pantomime pasa Senin malam, G
himpunan mahasiswa yang begadang sampai lewat tengah malam pada hari Senin
malam. Nyatakan pernyataan berikut dalam notasi teori himpunan:
(a) Semua mahasiswa tahun kedua jurusan
Teknik Informatika mengambil kuliah Matematika
Diskrit.
(b) hanya mereka yang mengambil kuliah
Matematika Diskrit atau yang pergi nonton pertunjukan pantomime yang begadang
sampai lewat tengah malam pada hari Senin malam.
(c) Mahasiswa yang mengambil kuliah
Matematika Diskrit tidak ada yang pergi nonton pertunjukan pantomime pada Senin
malam. (Penyebabnya adalah tugas pekerjaan rumah yang sangat banyak dalam
kuliahMatematika Diskrit).
(d) Pertunjukan pantomime itu hanya untuk
mahasiswa tahun pertama dan mahasiswa tahun kedua.
(e) Semua mahasiswa tahun kedua yang bukan
dari Jurusan Matematika atau pun Jurusan Teknik Informatika pergi nonton pertunjukan
pantomim.
6. Di antara bilangan bulat 1-300, berapa banyak yang tidak habis dibagi 3
atau 5?
7. Diantara bilangan bulat 1-300, berapa banyak yang
habis dibagi 3 tetapi tidak habis dibagi 5 atupun 7?
8. Di antara 100
mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45
orang mempelajari biologi, 15 mempelajari matematika dean biologi, 7 mempelajari
matematika dan fisika, 10 mempelajari fisika dan biologi, dan 30 tidak
mempelajari satu pun di antara ketiga bidang tersebut.
(a) Hitunglah banyaknya mahasiswa yang mempelajari ketiga bidang tersebut.
(b) Hitunglah banyaknya mahasiswa yang mempelajari hanya satu di antara ketiga
bidang tersebut.
9. Misalkan A, B,
dan C himpunan. Tunjukan bahwa
.
10. Buktikan bahwa jika maka A = B.
11. Buktikan untuk himpunan A, B, dan C, bahwa
(a)
(b)
(c) jika , maka
12. Didefinisikan A, B, C, D, dan E
sebagai berikut:
A
= {1, 2, 3, 4}, B = {1, 2, {2}, {{4}}},
C
= {1, {1, 2}, {{1, 2, 3}}}, D = {1, 2, 2, 1},
Untuk
tiap W, X, Y, Z yang didefinisikan di bawah ini, nyatakan apakah ia
adalah elemen atau himpunan bagian dari tiap-tiap himpunan A, B,C, D.
W
= {1, 2, 3} X = {1, 2, 3} Y = {4}
Z = {2}
13. Diketahui A = { +, - }, B = {00, 01,
10, 11}.
(a) Daftar A x B
(b) Berapa banyak elemen dan ?
14. tentukan semua partisi dari himpunan
B
= { Ø , 1, 2, {2}, {{4}}}.
15. Diketahui
multiset dan Q = {0, 1, 2, 3, 3, 3, 3, 4, 4}. Tentukan
(a) (b) (c) (d)