Matematika Diskret 2. Prinsip Inklusi dan Eksklusi

Rate This

Prinsip Inklusi dan Eksklusi merupakan perluasan ide dalam Diagram Venn beserta operasi irisan dan gabungan, namun dalam pembahasan kali ini konsep tersebut diperluas, dan diperkaya dengan ilustrasi penerapan yang bervariasi dalam matematika kombinatorik. Kita awali dengan sebuah ilustrasi:

Sebuah perkuliahan umum dihadiri oleh 20 mahasiswa yang memiliki kegemaran membaca dan 30 mahasiswa yang memiliki kegemaran menulis. Berapa mahasiswa di dalam perkuliahan tersebut yang memiliki kegemaran membaca atau menulis?

Dari permasalahan ini terlihat bahwa informasi yang diketahui belum memadai. Banyaknya mahasiswa yang memiliki kegemaran membaca atau menulis hanya dapat diketahui jika banyaknya mahasiswa yang menggemari kedua kegiatan tersebut diketahui.

Prinsip Inklusi-Eksklusi Banyaknya anggota himpunan gabungan antara himpunan A dan himpunan B merupakan jumlah banyaknya anggota dalam himpunan tersebut dikurangi banyaknya anggota di dalam irisannya. Dengan demikian,

n(A B) = n(A) + n(B) – n(A ∩ B)∪

Contoh 1.Dalam sebuah program studi pendidikan matematika yang terdiri atas 350 mahasiswa, terdapat 175 mahasiswa yang mengambil mata kuliah persamaan diferensial dan 225 mahasiswa yang mengambil mata kuliah analisis kompleks, dan 50 mahasiswa yang mengambil mata kuliah persamaan diferensial dan analisis kompleks. Ada berapa mahasiswa di dalam perkuliahan itu jika setiap mahasiswa mengambil mata kuliah persamaan diferensial, analisis kompleks, atau kedua-duanya?

Penyelesaian:Misalkan A adalah banyaknya mahasiswa yang mengambil mata kuliah persamaan diferensial dan B menyatakan mahasiswa yang mengambil mata kuliah analisis kompleks. Maka A B merupakan himpunan mahasiswa yang mengambil kedua mata kuliah tersebut. Banyaknya mahasiswa di dalam kelas itu yang mengambil mata kuliah persamaan diferensial, analisis kompleks, atau kedua-duanya adalah

n(A B) = n(A) + n(B) – n(A ∩ B)∪

= 175 + 225 – 50= 350

Ini berarti, terdapat 350 mahasiswa di dalam kelas yang mengambil mata kuliah persamaan diferensial, analisis kompleks, atau kedua-duanya. Karena banyaknya siswa keseluruhan di dalam kelas tersebut adalah 350 mahasiswa, artinya tidak terdapat mahasiswa yang tidak memilih salah satu dari kedua konsentrasi itu.

Contoh 2Di sebuah jurusan dalam suatu perguruan tinggi terdapat 134 mahasiswa tingkat 3. Dari sekian banyak mahasiswa tersebut, 87 di antaranya mengambil mata kuliah teori graf diskrit, 73 mengambil mata kuliah matematika ekonomi, dan 29 mengambil mata kuliah teori graf dan matematika ekonomi. Berapa banyak mahasiswa yang tidak mengambil sebuah mata kuliah baik dalam teori graf maupun dalam matematika ekonomi?Penyelesaian:Untuk menentukan banyaknya mahasiswa tingkat 3 yang tidak mengambil mata kuliah teori graf ataupun matematika ekonomi, kurangilah banyaknya mahasiswa yang mengambil mata kuliah dari salah satu mata kuliah ini dari keseluruhan banyaknya mahasiswa tingkat 1. Misalkan A merupakan himpunan semua mahasiwa tingkat 3 yang mengambil mata kuliah teori graf, dan B adalah himpunan mahasiswa yang mengambil mata kuliah matematika ekonomi. Maka n(A)=87, n(B)=73, dan n(A ∩ B) = 29. Banyaknya mahasiswa tingkat 3 yang mengambil mata kuliah teori graf atau matematika ekonomi adalah

n(A B) = n(A) + n(B) – n(A ∩ B)∪

= 87 + 73 – 29= 160-29= 131

Ini artinya terdapat sebanyak 134–131 = 3 mahasiswa tingkat 3 yang tidak mengambil mata kuliah teori graf ataupun matematika ekonomi.

Dalam bagian berikutnya akan diuraikan bagaimana cara-cara menentukan banyaknya anggota dalam gabungan antara himpunan terhingga dari sebuah himpunan. Hasil ini kemudian akan dikembangkan menjadi sebuah prinsip yang dinamakan Prinsip Inklusi-Eksklusi.

Sebelum membicarakan gabungan dari n himpunan, dengan n sebagai bilangan bulat positif, sebuah rumusan bagi banyaknya anggota dalam gabungan 3 himpunan A, B, dan C akan diturunkan. Untuk menyusun rumus ini perlu diingat bahwa n(A)+n(B)+n(C) membilang tiap anggota tepat satu kali dari ketiga himpunan tersebut satu kali, anggota yang tepat 2 kali dari himpunan-himpunan itu adalah dua kali, dan anggota-anggota dalam 3 himpunan tersebut 3 kali. Ini diilustrasikan dalam Gambar berikut :

Diagram Venn Tiga Himpunan

Ekspresi final ini membilang tiap anggota satu kali, apakah itu 1, 2 atau 3 dalam 3 himpunan. Jadi,

n(A B C)= n(A)+n(B)+n(C)- n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C)∪ ∪

Teorema (Prinsip Inklusi-Eksklusi)

Aplikasi Prinsip Inklusi-EksklusiPrinsip Inklusi-Eksklusi memiliki banyak aplikasi, di antaranya dalam penyelidikan banyaknya bilangan prima dalam yang tidak meliebihi suatu bilangan bulat positif tertentu. Perhitungan ini dapat dimanfaatkan dalam menjawab permasalahan saringan

Eratosthenes.Dalam saringan Eratosthenes, kita membuat suatu saringan yang mampu menyaring bilangan-bilangan, demikian sehingga yang tersisi setelah disaring hanyalah bilangan prima yang dimaksud.

Untuk memahami prinsip ini, pertama-tama kita kaji pengertian bilangan bulat komposit. Bilangan komposit adalah bilangan yang habis dibagi oleh bilangan prima yang tidak melebihi akar kuadratnya. Sebagai contoh, 50 adalah bilangan komposit. Bilangan ini dapat dibagi habis oleh bilangan prima yang tidak lebih dari 50 7 . Dalam hal ini 50 habis dibagi 2 dan 5. Untuk mencari banyaknya bilangan prima yang tidak lebih dari 100, kita perlu mencari bilangan komposit yang tidak melebihi 100. Karena 100 10 , maka bilanganbiangan prima yang kurang dari 10 adalah 2, 3, 5, 7. Dengan demikian banyaknya bilangan prima yang tidak lebih dari 100 adalah 4 ditambah dengan banyaknya bilangan bulat positif antara 100 yang habis dibagi 2, 3, 5, atau 7.Untuk memecahkan masalah ini akan kita gunakan prinsip Inklusi-Eksklusi

Matematika Diskret 1. Himpunan

Himpunan

Pengertian Himpunan

Himpunan adalah sekumpulan objek yang mempunyai sifat tertentu. Objek yang dimaksud dapat berupabilangan, manusia, hewan, tumbuhan, negara dan sebagainya. Objek ini selanjutnya dinamakan anggota atau elemen dari himpunan itu.

Notasi

Himpunan biasanya dinyatakan dengan huruf besar A, B, C, H, K dan sebagainya. Untuk menyatakan suatu himpunan digunakan simbol “{….}”. Sementara itu untuk

melambangkan anggota himpunan biasanya menggunakan huruf kecil a, b, c, x, y dan sebagainya. Perlu diperhatikan bahwa penulisan anggota dalam suatu himpunan hanya sekali saja Jadi tidak boleh kita menuliskan himpunan sebagai {1,a,b,8,b}. Demikian pula kita tidak boleh menyatakan himpunan sebagai {bunga, kambing, sapi, kerbau, sapi, tumbuhan}. Untuk menyatakan anggota suatu himpunan digunakan lambang “ ” (baca:anggota) sedangkan untuk menyatakan bukan anggota suatu himpunan igunakan

lambang “∉ ” (baca: bukan anggota).

Penulisan Himpunan

Untuk mendefinisikan himpunan digunakan 4 cara, yaitu :

1. Mendaftarkan semua anggotanya.

Contoh:

- A = {a,e,i,o,u}- B = {2,3,5,7,11,13,17,19}

2. Menggunakan sifat dari anggota himpunan

Contoh:

- P = {x | x himpunan bilangan asli antara 7 dan 15}(Maksudnya P = {8,9,10,11,12,13,14})

- Q = { t | t biangan asli}(Maksudnya Q = {1,2,3,4,5,6,7,8,9,10,…}

- R = { s | s2-1=0, s bilangan real}(Maksudnya R = {-1,1})

Himpunan Semesta

Himpunan semesta adalah himpunan yang anggotanya semua objek pembicaraan. Himpunan semesta dilambangkan dengan S atau U.

Contoh :

Kalau kita membahas mengenai 1, ½ , -2, -½ , 3 5 ,… maka semesta pembicaraan kita adalah bilangan real. Jadi himpunan semesta yang dimaksud adalah R. Apakah hanya R saja? Jawabannya tidak. Tergantung kita mau membatasi pembicaraanya. Pada contoh di atas bisa saja dikatakan semestanya adalah C (himpunan bilangan kompleks). Namun kita tidak boleh mengambil Z (himpunan bilangan bulat) sebagai semesta pembicaraan.

Himpunan Kosong

Himpunan kosong adalah himpunan yang tidak mempunyai anggota. Dilambangkan dengan “ ” atau { }

Contoh:

- Himpunan bilangan bulat yang ganjil- Himpunan orang yang tingginya 100 meter

Himpunan Bagian

Diberikan himpunan A dan B. Jika setiap anggota A merupakan anggota B maka dikatakan A merupakan himpunan bagian (subset) dari B atau dikatakan B memuat A dan dilambangkan dengan A B.

Jadi A B jika dan hanya jika x A dan x B

Jika ada anggota dari A yang bukan merupakan anggota B maka A bukan bukan

himpunan bagian dari B, dilambangkan dengan A ; B.

Contoh:

- A = {1,3,5} dan B = {0,1,2,3,4,5,6}. Maka A ; B.

- C = {a,b, c, 1,2} dan B = {0,1,2,3,4,5,6}. Maka C t; B, karena ada anggota dari C yang bukan merupakan anggota B, yaitu a. (Pengertian “ada” berarti terdapat satu anggota C yang bukan merupakan anggota B, sudah cukup)

- Suatu himpunan pasti merupakan subset dirinya sendiri. Jadi H ; H.

Operasi Himpunan

Gabungan (Union)

Gabungan dua himpunan A dan B adalah himpunan yang anggotanya semua anggota A atau B atau keduanya.A ∪ B = {x |x ; A atau x ; B}

Notasi: A ∪ B , A + B

Contoh:

A = { mouse, keyboard, scanner} ,B = { monitor,printer}, C = { mouse, keyboard, CPU }

maka:

A ∪ B = {mouse, keyboard, scanner, monitor,printer}A ∪ C = { mouse, keyboard, scanner , CPU }

Irisan (Intersection)

Irisan dari dua himpunan A dan B adalah himpunan yang anggotanya dimiliki bersama oleh himpunan A dan B

Notasi : A ∩ B ={x| x A dan x B}

Contoh:

A = { mouse,keyboard,touch sreen}B = { monitor, touch screen, printer, scanner}C = { monitor,printer, scanner}Maka:A ∩ B = { touch screen }

A ∩ C = { }

Relative Complement/Selisih

Selisih antara dua himpunan A dan B adalah himpunan yang anggotanya hanya menjadi anggota himpunan A tetapi tidak termasuk anggota himpunan B.

Notasi: A — B={x | x A dan x B}

Contoh:

A = { SQLserver,MySQL,MsAcces}B = { MySQL,MsAcces,Oracle}

Maka:A — B = {SQL server }

Symmetric Difference/Beda Setangkup

Beda setangkup dua himpunan A dan B adalah himpunan yang merupakan anggota himpunan A atau anggota himpunan B tetapi bukan merupakan anggota kedua himpunan secara bersamaan.

Notasi: A ⊕ B={x| x A dan x B tetapi x ∉ A ∩ B}

Contoh:

A = { Win3.1, Win3.11, Win95,Win97 }B = { Win95,Win97,Win98,Win98SE, WinME,Win2000 }A ⊕ B = { Win3.1, Win3.11, Win98, Win98SE ,WinME, Win2000 }

Komplemen

Komplemen Himpunan A adalah himpunan yang anggotanya bukan anggota A

Notasi : A’ , Ac

Contoh:

U = { Win3.1, Win3.11, Win95,Win97,Win98,Win98se, WinME,Win2000, WinXP,… }A = { Win3.1, Win3.11, Win95,Win97 }

A’ = {Win98,Win98se, WinME,Win2000, WinXP,… }

Diagram Venn

Adalah suatu cara untuk menggambarkan hubungan antara himpunan-himpunan.

Diagram Ven

Hukum-hukum aljabar Himpunan :

Contoh Soal Penyederhanaan Operasi Himpunan :

Real dan Kompleks mempunyai cardinalitas yang sama

January 11, 2011 by Aria Turns

Kita tahu bahwa himpunan bilangan real merupakan himpuan bagian dari himpuan bilagan kompleks . Apakah itu berarti cardinalitas (banyak elemen) pada lebih besar dari , ? Kita juga tahu bahwa setiap elemen di mempunyai bentuk untuk sebarang . Apakah itu berarti

Tidak, tidak, mempunyai cardinalitas yang sama dengan ,

Kok bisa?

Untuk menujukan 2 himpunan A dan B mempunyai cardinalitas yang sama, kita harus menjukan terdapat fungsi bijektif dari A ke B. Karena dengan adanya fungsi bijektif, itu berati setiap elemen A dan B dapat dipasang-pasangkan. Akan tetapi untuk menujukan bukan dengan cara menunjukan terdapat fungsi bijektif dari ke . Melainkan dengan menujukan mempunyai cardinalitas yang sama

dengan . Diketahui bahwa , itu berarti dengan

menunjukan , kita telah menunjukan

Diberikan fungsi dari ke

yang didefinsikan sebagai berikut

Contoh

•••

Nah.. selanjutnya tinggal kita buktikan bijektif. Errr… Nah.. telah kita tunjukan bahwa

, itu berarti terbukti