Himpunan: Prinsip Inklusi-Eksklusi

Penggabungan dua buah himpunan menghasilkan sebuah himpunan baru yang elemen nya berasal dari himpunan A dan himpunan B. Himpunan A dan himpunan B mungkin saja memiliki elemen yang sama, dan hal tersebut dapat di temukan dalam |A ∩ B|. Setiap unsur yang sama itu telah dihitung dua kali, sekali pada |A| dan sekali pada |B|, meskipn ia dianggap sebagi sebuah elemen pada |A ∪ B|. Karena itu, jumlah elemen hasil penggabungan seharusnya adalah elemen di masing-masing himpunan dikurangi dengan jumlah elemen di dalam irisannya, atau |A ∪ B| = |A| + |B| – |A ∩ B|.

Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi.

Dengan cara yang sama, kita dapat menghitung jumlah elemen
hasil operasi beda setangkup.
Contoh 1:
A = {1,2,3}
B = {2,3,4}

|A ⊕ B| = |A| + |B| - 2 |A ∩ B|
|A ⊕ B| = {1,2,3} + {2,3,4} - 2 {2,3}
|A ⊕ B| = {1,2,2,3,3,4} - 2 {2,3}
|A ⊕ B| = {1,4}
Sebanyak 1148 orang  mendaftar di universitas Harvard,
768 orang mendaftar di universitas Stanford, dan 127
orang mendaftar di MIT. Sebanyak 102 orang mendaftar di
universitas Harvard dan Stanford, 20 orang mendaftar di 
universitas Harvard dan MIT, dan 12 orang mendaftar di 
universitas Stanford dan MIT. Jika 1929 orang mendaftar 
paling sedikit sebuah universitas yaitu Harvard, 
Stanford atau MIT, berapa banyak siswa yang mendaftar ke 
ketiga universitas tersebut ?

Penyelesaian:

Misalkan,
H = himpunan siswa yang mendaftar di universitas Harvard,
S = himpunan siswa yang mendaftar di universitas Stanford, 
M = himpunan siswa yang mendaftar di MIT.

maka,

|H| = 1148, |S| = 768, |M| = 127

|H ∩ S| = 102, |H ∩ M| = 20, |S ∩ M| = 12

dan

|H ∪ S ∪ M| = 1929


Penyulihan nilai-nilai di atas pada persamaan :
|H ∪ S ∪ M| = |H| + |S| + |M| - |H ∩ S| - |H ∩ M| - |S ∩ M| 
+ |H ∩ S ∩ M|

memberikan

1929 = 1148 + 768 + 127 - 102 - 20 - 12 + |H ∩ S ∩ M|

sehingga

|H ∩ S ∩ M| = 10

Jadi, ada 10 orang siswa yang mendaftar ke ketiga 
universitas tsb (Harvard, Stanford dan MIT).

Pustaka:

Munir, R. 2012. Matematika Diskrit. Revisi Kelima. Penerbit Informatika

Leave a Reply

Your email address will not be published. Required fields are marked *