himpunan - matematika diskrit

12
HIMPUNAN MATEMATIKA DISKRIT Universitas Gunadarma Fakultas Ilmu Komputer PTA 2010/2011 Achmad Rizky 20109214 Ahmad Aqil Azizi 21109259 Ahmad Idannul Furqon 20109429 Aldo Serena Widodo 26109761 Angga Septian Nugroho 21109631

Upload: achmad-rizky

Post on 25-Jun-2015

2.235 views

Category:

Documents


11 download

DESCRIPTION

Tugas Matematika Diskrit tentang Himpunan

TRANSCRIPT

Page 1: Himpunan - Matematika Diskrit

HIMPUNAN

MATEMATIKA DISKRIT

Universitas GunadarmaFakultas Ilmu Komputer

PTA 2010/2011

Achmad Rizky 20109214Ahmad Aqil Azizi 21109259Ahmad Idannul Furqon 20109429Aldo Serena Widodo 26109761Angga Septian Nugroho 21109631

Page 2: Himpunan - Matematika Diskrit

1.1 HIMPUNAN

Himpunan adalah suatu kumpulan / koleksi dari obyek-obyek sembarang. (Cara pengumpulan obyek-obyek itu biasanya berdasarkan sifat/keadaan mereka yang sama, ataupun berdasarkan suatu aturan tertentu/yang ditentukan).

Contoh (1.1)

Misalnya himpunan yang terdiri dari mahasiswa-mahasiswa Jakarta atau himpunan dari semua bilangan asli yang lebih besar dari 9, ataupun himpunan yang terdiri dari ayam, bebek, dan sapi.

Catatan (1):• Obyek-obyek di atas disebut elemen (unsur anggota) himpunan dan biasanya dinyatakan

dengan huruf kecil, misalnya a,b,p,x dan lain-lain.• Suatu himpunan biasanya dinyatakan dengan huruf besar, misalnya himpunan A, B, P, Y dan

lain-lain.• Bila a merupakan elemen dari himpunan A, sedangkan b bukan elemen dari himpunan A,

maka kita dapat menuliskan a∈B , b∉A

Kita mengenal 2 bentuk dalam penulisan suatu himpunan sebagai berikut :

1. Bentuk pendaftaran (Tabular-Form) yaitu dengan menuliskan semua elemen himpunan tersebut di dalam kurung kurawal. Sebagai contoh :Himpunan A = {Jakarta, Medan, Surabaya}Himpunan N = {1, 2, 3, ...}Himpunan P = { ∅ ,12, IV, α}

2. Bentuk pencirian (Set-Builder Form) yaitu dengan menuliskan sifat/ketentuan mengenai elemen himpunan tersebut. Sebagai contoh:Himpunan S = { x | x adalah bilangan genap }Himpunan T = { x | x adalah pelajar yang pandai }

Contoh (1.2) :

Kita dapat mengubah penulisan himpunan dari tabular-form ke set-builder form atau sebaliknya.

Misalnya M = { x | x adalah nama hari dalam satu minggu } = { Senin, Selasa, Rabu, Kamis, Jumat, Sabtu, Minggu }, atau P = { x | x2 – 4 = ∅ } = {-2, 2} ataupun N = { x | x bilangan asli } = { 1, 2, 3, ...} dan lain-lain.

Bentuk mana yang dipakai, tergantung mana yang lebih mudah dan menyenangkan.

Catatan (2) :

Suatu himpunan disebut hingga bila banyak anggotanya ( yang berbeda ) hingga. Kalau banyak anggotanya tak hingga, disebut himpunan tak hingga.

Dapat dicatat bahwa anggota-anggota yang sama, dihitung sekali. Himpunan yang tidak mempunyai anggota disebut himpunan hampa (kosong) dinyatakan dengan ∅ .

Page 3: Himpunan - Matematika Diskrit

Contoh (1.3) :Contoh himpunan ∅ : A = { x | x2 = 9, x genap}

Catatan (3) :Himpunan A dan B dikatakan sama, A = B bila mereka mempunyai anggota-anggota yang

sama.

Contoh (1.4) :A = { 2, 1, 4}, B = { 4, 1, 2} maka A = B. Juga bila P = { x | x2 – 3x = -2 }, Q = { 2, 1}, R = {1 ,2 ,2 ,

1} maka P = Q = R

Definisi:Himpunan A dikatakan himpunan bagian (Subset) dari himpunan B, bila setiap anggota dari

A juga merupakan anggota dari B. Ditulis A⊂B merupakan himpunan super/super set dari A, A⊃B .

Contoh (1.5) :P = { 1,2,4 } Q = {1,4,5,2} maka P⊂Q , jelas karena setiap anggota dari P adalah anggota

Q juga.G = { x | x bilangan genap }, H = { x | x bilangan bulat }, maka G⊂H

Catatan (4) :Notasi “ ≠ ” digunakan juga untuk menyatakan pernyataan “Subset atau Sama

Dengan”. Jadi A⊆B berarti A subset B atau a=b . Bila A⊂B dikatakan pada A subset sebenarnya dari B. Tetapi di dalam buku ini kita menggunakan notasi baik untuk subset sebenarnya ataupun tidak sebenarnya.

Catatan (5) :Kita dapat menuliskan definisi kesamaan 2 himpunan sebagai berikut:A = B jika dan hanya jika A⊂B dan B⊂A

Catatan (6) :Dua himpunan A dan B dikatakan dapat diperbandingkan (Comparable) bila A⊂B atau

B⊂A .

Contoh (1.6) :A = {a, b, c}, B = {a, b} maka A dapat diperbandingkan dengan B karena B⊂A ,

sedangkan S = {2, 4, 5} dan T = {2, 4,6} tidak dapat diperbandingkan S∉T dan T∉S . ( : bukan subset)

Catatan (7) :Kadang-kadang kita jumpai bahwa objek dari suatu himpunan merupakan himpunan pula,

himpunan semacam itu disebut suatu keluarga (family), kelas dari himpunan atau himpunan dari himpunan-himpunan (set of sets). Biasanya kita tulis dengan huruf berbentuk A, B, C dan lain-lain.

Contoh (1.7) :1. Di dalam geometri kita mengenal berkas garis yang mana merupakan himpunan dari garis

lurus. Sedang kita tahu pula bahwa masing-masing garis lurus tersebut adalah himpunan dari titik-titik.

Page 4: Himpunan - Matematika Diskrit

2. Himpunan { (2,3), (1,0), (0,4,7) } adalah suatu keluarga dari himpunan (2,3), (1,0) , dan (0,4,7).

3. A = { 2, (1,4), (0,2,1) }, A bukan suatu keluarga himpunan karena anggotanya ada yang bukan himpunan

Catatan (8) :Untuk membatasi himpunan yang kita bicarakan, di definisikan suatu himpunan yang mana

setiap himpunan dalam pembicaraan kita itu selalu merupakan subsetnya. Himpunan tersebut dinamakan himpunan semesta (universal set) dan dinyatakan dengan . Jadi selalu berlaku A⊂U untuk setiap A.

Contoh (1.8):Dalam geometri datar yang menjadi himpunan semesta adalah himpunan semua titik pada

bidang datar.

Catatan (9) :Keluarga semua subset dari suatu himpunan S biasa disebut himpunan kuasa (power set)

dari S ditulis 2S. Banyaknya anggota dari 2S adalah 2n dimana n adalah jumlah anggota dari S. Di sini termasuk pula ∅ , karena ∅ merupakan subset dari himpunan manapun.

Contoh (1.9) :M = (a,b), subset-subset dari M adalah ∅ , (a), (b), (a,b) = M, jadi 2M = { ∅ , (a), (b), m

}. Banyaknya anggota dari 2M = 22 = 4

Catatan (10) :2 himpunan disebut saling lepas (saling asing/ disjoint) bila tidak mempunyai anggota

sama.

Contoh (1.10)i. A = (4,3), B = (2,0) sailng lepasii. P = (1, 2, 3), Q = (1 , 6 ,7) tidak saling lepas karena 1⊂P juga 1⊂Q

1.2 DIAGRAM VENN

Untuk menggambarkan hubungan antara himpunan-himpunan dapat kita menggunakan diagram Venn. Himpunan kita gambarkan sebagai daerah lingkaran sedangkan semesta sebagai daerah empat persegi panjang. Perhatikan contoh-contoh berikut:

Contoh (1.11) :Misalkan A⊂B dan A≠∅ dapat kita gambarkan sebagai berikut:

Page 5: Himpunan - Matematika Diskrit

Misalkan pula A dan B tidak dapat diperbandingkan. Gambar 2, A dan B tidak saling lepas dan gambar 3, A dan B saling lepas.

1.3 OPERASI ANTAR HIMPUNAN

Beberapa operasi yang penting adalah :

1. Gabungan (Union), dinotasikan dengan ∪A U B = (x | x A atau x B)Di dalam diagram Venn:

Contoh (1.12) :S = (a, b, c)T = (a,b,p,r)

Maka S∪T = (a,b,c,p,r).

Catatan (11) :Berlaku :

(i) A∪B=B∪A(ii) A⊂ A∪B ; B⊂A∪B(iii) Bila A⊂B maka A∪B=A(iv) A∪∅=a. A∪U=U

2. Irisan (Intersection), dinotasikan dengan ∩A∩B = ( x | x∈A dan x∈B ).

Page 6: Himpunan - Matematika Diskrit

Di dalam diagram Venn :

Bila A dan B saling lepas maka A∩B=∅

Contoh (1.12) :Bila P = (a,b,c,d,e), Q = (d,e,f,g)maka P∩Q (d,e).Bila R = (p,q,r) maka P∩R=∅

Catatan (12) :(i) A∩B=B∩A(ii) A∩B⊂A; A∩B⊂B(iii) Bila A⊂B maka A∩B=A(iv) A∩∅=∅ , A∩U=A

3. Selisih (Difference), dinotasikan dengan -A – B = ( x | x∈A dan x∈B )

Di dalam diagram Venn :

Contoh 1.13 :S = (a, b, c, d), T = (f,b,d,g)maka S – T = (a, c), dan T – S = (f,g)

Catatan (13) :(i) A−B ⊂A(ii) A−B≠B−A bila A≠B(iii) Bila A⊂B maka A−B=∅ dan B−A⊂B

Page 7: Himpunan - Matematika Diskrit

4. Komplemen dari A, dinotasikan A' atau Ac

Di dalam diagram Venn :

A '=x∨x∉A , x∈U =U−A

Contoh (1.14) :Misalkan U (x | x huruf Latin) dan T = (x | x huruf mati) maka T' = ( x | x huruf hidup) =

(a,e,i,o,u).

Catatan (14) :(i) A∩A'=∅(ii) A∪A'=U(iii) U '=∅ ,∅'=U(iv) A ' '=A(v) A−B=A∩B '(vi) Bila A⊂B maka B '⊂A'

Catatan (15) :Operasi selisih simetri, dinotasikan dengan ∆:A ∆ B = A∪B−A∩B= A−B∪B−ASeperti dalam diagram Venn:

Contoh (1.15) :Bila A = (2,3,4,5,6) dan B = {1,3,4,6} maka A ∆ B = 125).

Catatan (16)Hasil kali cartesius dari 2 himpunan A dan B, yaitu :A x B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}B x A = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}Terlihat bahwa pada umumnya A x B≠B x A

Page 8: Himpunan - Matematika Diskrit

1.4 Aljabar Himpunan

Himpunan dengan operasi yang telah kita jelaskan pada bagian (1, 3) yang lalu, ternyata memenuhi banyak sekali hukum dan kesamaan aljabar. Beberapa diantaranya telah disebutkan. Secara lengkap, hukum dan kesamaan aljabar himpunan tersebut dapat kita lihat pada tabel (1.1)

Hukum Idempoten(1a) A∪A=A(1b) A∩A=A

Hukum Asosiatif(2a) A∪B∩C=A∪B∩C(2b) A∩B∪C=A∩B∩C

Hukum Komutatif(3a) A∪B=B∪A(3b) A∩B=B∩A

Hukum Distributif(4a) A∪B∩C = A∪B∩A∪C (4b) A∩B∩C =A∩B∩ A∩C

Hukum Identitas(5a) A∪∅=A(5b) A∩∅=∅(6a) A∪U=U(6b) A∩U=A

Hukum Involusi(7) A ' '=A

Hukum Komplemen(8a) A∪A'=U(8b) A∩A'=∅(9a) U '=∅(9b) ∅'=U

Hukum DeMorgan(10a) A∪B '=A'∩B '(10b) A∩B '=A'∪B '

Untuk membuktikan berlakunya hukum-hukum pada aljabar himpunan, kita dapat menggunakan 2 cara.

Cara pertama adalah membuktikan bahwa himpunan hasil operasipada ruas kiri merupakan himpunan bagian dari himpunan hasil pada ruas kanan dan sebaliknya

Hal ini berakibat ruas kanan = ruas kiri.

Cara kedua adalah menggunakan diagram Venn

Contoh (1.16 ):Kita ingin membuktikan hukum DeMorgan : A∪B '=A'∩B '

Cara 1 :Pertama kita tunjukkan bahwa A∪B ' ,⊂A'∩B '

Ambil sembarang x∈ A∪B' berarti x∉ A∪B , yang berarti pula x∉A dan x∉B . Jadi x∈A ' dan x∈B ' , berarti x∈A '∩B Oleh karena itu A∪B ⊂A'∩B ' .

Selanjutnya kita tunjukkan bahwa A '∩B '⊂ A∪B ' . Ambil sembarang x∈A '∩B ' , berarti x∈A dan x∈B . Karena itu x∉A dan x∉B , berarti x∈ A∪B . Jadi x∈ A∪B ' . Sehingga A '∩B '⊂ A∪B ' .

Kita Ingat bahwa bila diketahui 2 himpunan P dan Q yang memenuhi P⊂Q dan Q⊂Pmaka P = Q. Berdasarkan ini, terbukti bahwa A∪B '=A'∩B'

Page 9: Himpunan - Matematika Diskrit

Cara 2 :Dengan diagram Venn, terlihat A∪B ' adalah bagian yang berarsir pada gambar 10a.

A '∩B ' adalah bagian yang berarsir ganda pada gambar 10d. Nampak bahwa kedua bagian A∪B ' serta A '∩B ' adalah sama.

Catatan (17) :Suatu sifat penting yang dimiliki oleh aljabar himpunan adalah sifat dualitas dari kesamaan

himpunan. Dual E dari kesamaan E adalah kesamaan yang diperoleh dengan berturut-turut∪ ,∩ ,∅ , dan U pada E masing-masing diganti dengan ∩ ,∪ ,U dan ∅ . Sebagai

contoh, E : U∩A∪B∩A=A mempunyai dual E :

∅∪A∩B∪A=A

1.5 HIMPUNAN HINGGA DAN PERHITUNGAN ANGGOTA

Kalau A adalah himpunan hingga, artinya A mempunyai anggota sebanyak hingga, kita dapat menyatakan banyaknya anggota A sebagai n(a) atau #(A).

Berikut ini beberapa sifat yang berkaitan dengan banyak anggota himpunan :

1. Jika A dan B himpunan hingga yang saling lepas ( A∩B = ∅ ), maka n A∪B=n AnB

2. Jika A dan B sembarang himpunan hingga, maka A∪B hingga, demikian pula A∩BDi sini n A∪B=n AnB−n A∩B

3. Sifat (2) dapat kita perluas untuk sembarang 3 himpunan hingga A, B dan C.Berarti n A∪B∪C =n An Bn C −n A∩B−n A∩C −nB∩CA∩B∩C

Contoh (1.18):Dari 120 orang mahasiswa semester 5 Sekolah Tinggi Komputer Gunadarma, 100 orang

Page 10: Himpunan - Matematika Diskrit

mengambil paling sedikit satu mata kuliah apilikasi pilihan, yaitu kuliah Asuransi, Perbankan serta Transportasi.

Juga diketahui bahwa:65 orang mengambil Asuransi45 orang mengambil Perbankan42 orang mengambil Transportasi20 orang mengambil sekaligus Asuransi dan Perbankan25 orang mengambil sekaligus Asuransi dan Transportasi15 orang mengambil sekaligus Perbankan dan Transportasi

Kita ingin mengetahui secara tepat berapa orang mahasiswa yang mengambil sekaligus 3 mata kuliah tersebut.

Untuk itu kita gambar diagram Venn seperti pada gambar 11, dengan A menyatakan himpunan mahasiswa yang mengambil Asuransi, B yang mengambil Perbankan dan C yang mengambil Transportasi.

Himpunan semesta U merupakan himpunan dari 120 orang mahasiswa semester 5 tersebut.

Di sini berarti n A∪B∪C = 100 , n A=65 , n B=45 , nC =42,n A∩B∩C=15 .Berdasarkan sifat (3) di atas diperoleh n A∩B∩C , yaitu banyaknya mahasiswa yang

mengambil sekaligus ketiga mata kuliah tersebut, adalah 8 orang.Sehingga, kalau setiap bagian diagram Venn kita lengkapi dengan banyaknya anggota,

diperoleh gambar 13.

Keterangan :20 – 8 = 12 orang mengambil Asuransi dan Perbankan tetapi tidak mengambil Transportasi.25 – 8 = 17 orang mengambil Asuransi dan Transportasi tetapi tidak mengambil Perbankan.15 – 7 = 8 orang mengambil Perbankan dan Transportasi tetapi tidak mengambil Asuransi65 – 12 – 7 – 8 = 28 orang mengambil Asuransi saja45 – 12 – 7 – 8 = 18 orang mengambil Perbankan saja42 – 17 – 7 – 8 = 10 orang mengambil Transportasi saja120 – 100 = 20 orang tidak mengambil satu pun dari 3 mata kuliah tersebut.

ARGUMEN DAN DIAGRAM VENN

Banyak statemen verbal dapat dialihkan menjadi statemen himpunan. Statemen ini dapat digambarkan dengan diagram Venn. Oleh karena itu, diagram Venn acap kali digunakan untuk

Page 11: Himpunan - Matematika Diskrit

menganalisa validitasnya suatu argumen.

Contoh (1.19) :

Pandang asumsi S1, S2, S3 berikut :S1 : Guru adalah orang yang tenteram hidupnyaS2 : Setiap raja merupakan orang kayaS3 : Tidak ada orang kaya yang juga tenteram hidupnya

Kita hendak menggambarkan asumsi di atas dalam diagram VennHimpunan guru termuat dalam himpunan orang yang tenteram hidupnya (asumsi S1).

Himpunan orang tenteram hidupnya akan saling lepas dengan himpunan orang kaya (asumsi S3). Himpunan raja termuat seluruhnya di dalam himpunan orang kaya (asumsi S2).

Dari sini dapat kita putuskan bahwa konklusi “Tidak ada guru yang merupakan orang kaya” adalah valid. Demikian pula konklusi “Tidak ada seorang pun guru yang juga raja”.

Konklusi “Raja tenteram hidupnya” adalah tidak valid.

Contoh (1.20) :Bagaimana kalau asumsi S2 pada contoh (1.19) yang lalu kita ubah menjadi “Ada raja yang

merupakan orang kaya”?

Diagram Venn berubah menjadi seperti pada gambar 14.

Jadi konklusi “Tidak ada seorang pun guru yang juga raja” adalah tidak valid. Demikian pula halnya konklusi “Semua raja tidak tenteram hidupnya”.

1.7 BUKTI DENGAN INDUKSI MATEMATIKA (INDUKSI LENGKAP)

Page 12: Himpunan - Matematika Diskrit

Jika P adalah suatu proposisi yang didefinisikan pada himpunan bilangan bulat positif N = (1,2,3,...), artinya P(n) bisa bernilai benar (true) atau salah (false) kemudian P mempunyai sifat :

1. P(1) benar2. P(n+1) benar untuk P(n) benar,

maka P adalah benar untuk semua n bilangan bulat positif anggota N.

Contoh (1.21) :Pandang P adalah proposisi yang menyatakan bahwa jumlah n buah bilangan ganjil yang

pertama adalah n.

P(n) : 1 +3 + 5 . . . + (2n – 1) = n2

Bilangan ganjil ke n adalah (2n-1) dan bilangan ganjil berikutnya (yang ke n + 1) adalah (2n-1)

Di sini P(1) : 1 = 12 benarAnggap P(n) benar, maka

P(n+1) : 1 + 2 + 3 + . . . + (2n-1) + (2n+1)= n2 + (2n + 1) = (n + 1)2 benar

Jadi P(n) benar untuk semua bilangan bulat positif n.