Matematika Diskrit BAB III PRINSIP INKLUSI DAN EKSKLUSI

BAB III   PRINSIP INKLUSI DAN EKSKLUSI

Author By : Dra. D. L. CRISPINA PARDEDE, DEA

Misalkan A dan B sembarang himpunan. Penjumlahan |A|+|B| menghitung banyaknya elemen A yang tidak terdapat dalam B dan banyaknya elemen B yang tidak terdapat dalam A tepat satu kali, dan banyaknya elemen yang terdapat dalam   A ∩ B sebanyak dua kali. Oleh karena itu, pengurangan banyaknya elemen yang terdapat dalam A ∩ B  dari |A|+|B| membuat banyaknya anggota A Ç B dihitung tepat satu kali. Dengan demikian,

|A υ B|=  |A|+|B| - |A ∩ B|.

Generalisasi dari hal tersebut bagi gabungan dari sejumlah himpunan dinamakan prinsip inklusi-eksklusi.

Contoh 3.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 A ∩ B. Banyaknya mahasiswa yang menyukai salah satu dari kedua mata kuliah tersebut atau keduanya dinyatakan dengan |A υ B|. Dengan demikian,

|A υ B| =  |A|+|B| - |A ∩ B|

              =  25 + 13 – 8

               =  30.

Jadi, terdapat 30 orang mahasiswa dalam kelas tersebut.

Contoh 3.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 P υ Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan P ∩ Q  himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11.

Normal
0

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

Soal Latihan 3.1.

1. Berapa banyak elemen yang terdapat dalam himpunan  A_1,  A₂ jika terdapat 12 elemen dalam A₁ dan  18 elemen dalam A₂ ,  dan

a.  A₁ ∩ A₂ =Ø

b. |A₁ ∩ A₂| = 6

c. |A₁ ∩ A₂| = 1

d. A₁  A₂

2. Pada sebuah sekolah tinggi terdapat 345 siswa yang mengambil mata kuliah kalkulus, 212 siswa mengambil kuliah matematika diskrit dan 188 siswa mengambil kedua mata kuliah tersebut. Berapa siswa yang mengambil kalkulus saja atau matematika diskrit saja ?

Jika A, B dan C adalah sembarang himpunan, maka

|A υ B υ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C|-|B ∩ C| + |A ∩ B ∩ C|

Contoh 3.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 P υ Q υ R  adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 atau 7 atau 11, dan himpunan P ∩ Q ∩ R  adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 dan 11.  Himpunan P ∩ Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 7,  P ∩ R adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 11, dan Q ∩ R 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 penghitungan tesebut dapat dilihat pada diagram di bawah ini.

Soal Latihan 3.2.

1. Berapa banyak elemen yang terdapat dalam himpunan  A₁ υ A₂ υ A₃  jika terdapat 100 elemen dalam A₁  , 1000 elemen dalam A₂  dan  10000 elemen dalam A₃ ,  dan jika

a.   A₁  A₂  dan   A₂  A₃

b.  Terdapat dua elemen bersama pada setiap pasang himpunan dan satu elemen bersama dari setiap pasangan tiga himpunan.

2. Tentukan banyaknya bilangan bulat positif tidak lebih dari 500 yang habis dibagi oleh 2, 5 dan 7.

3. Seorang mahasiswa harus menjawab 8 dari 10 soal ujian Matematika Diskrit. Berapa banyak pilihan yang ia miliki jika paling sedikit ia harus menjawab 4 dari 5 soal pertama ?

Formulasi prinsip inklusi eksklusi untuk himpunan hingga  A₁ , A₂ , A₃ , ... , A_n , adalah sebagai berikut :

Contoh 3.4.
Berdasarkan prinsip inklusi eksklusi, formula untuk menghitung banyaknya anggota himpunan hasil gabungan empat himpunan hingga.
|A₁ È A₂ È A₃ È A­₄| = |A₁|+|A₂|+|A₃|+|A₄| - |A₁ Ç A₂| - |A₁ Ç A₃| -|A₁ Ç A₄|- |A₂ Ç A₃|- |A₂ Ç A₃|- |A₃ Ç A₄| +|A₁ Ç A₂ Ç A₃| + |A₁ Ç A₂ Ç A₄| +|A₁ Ç A₃ Ç A₄| + |A₂ Ç A₃ Ç A₄|- |A₁ Ç A₂ Ç A₃ Ç A₄|