Prinsip Inklusi Dan Eksklusi.docx

TUGAS KELOMPOK MATA KULIAH MATEMATIKA DISTRIK

STAMBUK

NAMA

A 232 18 014

Dwi Wijayanti

A 232 18 018

Elisabet Naomi

A 232 18 020

Yusuf

PRINSIP INKLUSI DAN EKSKLUSI 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. A. 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, |𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| Contoh 1 Dalam sebuah kelas terdapat 25 mahasiswa yang menyukai matematika diskrit, 13 mahasiswa menyukai aljabar linier dan 8 orang diantaranya menyukai matematika diskrit dan aljabar linier. Berapa mahasiswa terdapat dalam kelas tersebut? Jawab : Misalkan A himpunan mahasiswa yang menyukai matematika diskrit dan B himpunan mahasiswa yang menyukai aljabar linier. Himpunan mahasiswa yang menyukai kedua mata kuliah tersebut dapat dinyatakan sebagai himpunan 𝐴 ∩ 𝐵. Banyaknya mahasiswa yang menyukai salah satu dari kedua mata kuliah tersebut atau keduanya dinyatakan dengan |𝐴 ∪ 𝐵|. Dengan demikian

|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| = 25 + 13 − 8 = 30 Jadi, terdapat 30 orang mahasiswa dalam kelas tersebut.

Contoh 2 Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 7 atau 11? Jawab: Misalkan P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11. Dengan demikian 𝑃 ∪ 𝑄 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan 𝑃 ∩ 𝑄 himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11.

Jadi, terdapat 220 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11. Ilustrasi dari perhitungan tersebut dapat dilihat pada diagram di bawah ini.

Jika A, B dan C adalah sembarang himpunan, maka |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶| Contoh 3 Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 5, 7 atau 11? Jawab: Misalkan P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7, dan R himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11. Dengan demikian 𝑃 ∪ 𝑄 ∪ 𝑅 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 atau 7 atau 11, dan himpunan 𝑃 ∩ 𝑄 ∩ 𝑅 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 dan 11. Himpunan 𝑃 ∩ 𝑄 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 7, 𝑃 ∩ 𝑅 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 11, dan 𝑄 ∩ 𝑅 adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan 11.

Jadi, terdapat 376 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 atau habis dibagi 11. Ilustrasi dari perhitungan tersebut dapat dilihat pada diagram di bawah ini.

Formulasi prinsip inklusi eksklusi untuk himpunan hingga A1, A2, A3, … , An , adalah sebagai berikut:

Contoh 4 Berdasarkan prinsip inklusi eksklusi, formula untuk menghitung banyaknya anggota himpunan hasil gabungan empat himpunan hingga.

B. Aplikasi Prinsip Inklusi – Eksklusi Prinsip Inklusi – Eksklusi memiliki banyak aplikasi, di antaranya dalam penyelidikan banyaknya bilangan prima dalam yang tidak melebihi 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 bilangan-bilangan 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. Kita misalkan P1 : sifat bahwa sebuah bilangan bulat habis dibagi 2;

P2 : sifat bahwa sebuah bilangan bulat habis dibagi 3; P3 : sifat bahwa sebuah bilangan bulat habis dibagi 5; P4 : sifat bahwa sebuah bilangan bulat habis dibagi 7. Maka banyaknya bilangan prima yang tidak melebihi 100 adalah 4 + |𝑃1′ 𝑃2′ 𝑃3′ 𝑃4′ | Mengingat bahwa bilangan positif antara 1 dan 100 seluruhnya ada 99, maka

Dengan demikian, terdapat 4 + 21 = 25 bilangan prima yang tidak melebihi 100.