PRINSIP INKLUSI DAN EKSKLUSI ALJABAR
PRINSIP INKLUSI DAN EKSKLUSI
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.
½P½ = 
½Q½ =
½P Ç Q½ = 
½P È Q½ = ½P½ + ½Q½ -½P Ç Q½ = 142 + 90 – 12 = 220.
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
A1 A2 jika terdapat 12 elemen dalam A1
dan 18 elemen dalam A2 , dan
a.
A1 Ç A2 = Æ
b.
½A1 Ç A2½ = 6
c.
½A1 Ç A2½ = 1
d.
A1 Í A2
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.
½P½ = 
; ½Q½ = ; ½R½ =
; ½Q½ = ; ½R½ =
½P Ç Q½ = 
; ½P Ç R½ = 
; ½P Ç R½ =
½Q Ç R½ =
½P Ç Q Ç R½ = 
½P È Q È R½
= 200 + 142 + 90 – 28 – 18 – 12 + 2 = 376.
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 A1 È A2 È A3 jika terdapat 100 elemen dalam A1 , 1000 elemen dalam A2 dan
10000 elemen dalam A3 ,
dan jika
a. A1
Í A2
dan A2 Í A3
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
A1 , A2 , A3 , ... , An ,
adalah sebagai berikut :
½A1 È A2 È ... È An ½ = 
½Ai½ - 
½Ai Ç Aj½ +
½Ai½ - ½Ai Ç Aj½ +
+ 
½Ai Ç Aj Ç Ak½
- ..... +
½Ai Ç Aj Ç Ak½
- ..... +
+ ( -1 )n+1 ½Ai Ç Aj Ç ... Ç An½ .
Contoh 3.4.
Berdasarkan prinsip inklusi eksklusi, formula
untuk menghitung banyaknya anggota himpunan hasil gabungan empat himpunan
hingga.
½A1 È A2 È A3 È A4½ = ½A1½+½A2½+½A3½+½A4½ - ½A1 Ç A2½ - ½A1
Ç A3½ +
-½A1 Ç A4½- ½A2 Ç A3½- ½A2
Ç A3½- ½A3 Ç A4½ +
+ ½A1 Ç A2 Ç A3½ + ½A1 Ç A2 Ç A4½ +
+ ½A1 Ç A3 Ç A4½ + ½A2 Ç A3 Ç A4½ +
- ½A1 Ç A2 Ç A3 Ç A4½ .
Soal Latihan 3.3.
1. Berapa banyak elemen yang terdapat dalam
gabungan dari lima himpunan jika setiap
himpunan memiliki 10000 anggota, setiap pasang elemen memiliki 1000 elemen
bersama, setiap pasangan tiga himpunan memiliki 100 elemen bersama, setiap
empat himpunan memiliki 10 elemen bersama dan terdapat satu elemen bersama dari
ke lima himpunan ?
2. Tuliskan formula inklusi eksklusi untuk
menghitung banyaknya anggota gabungan enam himpunan dimana tidak ada tiga
himpunan memiliki elemen bersama.
3. Tentukan banyaknya kombinasi 10 dari
himpunan { 3.a, 5.b, 7.c }.
0 komentar :
Post a Comment
Silahkan Berkomentar Sesuai Dengan Topik, Jangan Menggunakan Kata-Kata Kasar, Komentar Dengan Link Aktif Tidak Akan Dipublikasikan
ttd
Admin Blog