Matematika Diskret 2. 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.

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 2
Di 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

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-Eksklusi
Prinsip 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s