7. prinsip inklusi-eksklusi
TRANSCRIPT
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
1/16
Page 1 of16
Modul Mengajar PS S-2 Pendidikan Matematika
Hari Ketujuh
Bentuk umum prinsip inklusi dan eksklusi
Syamsul Rizal
Prinsip Inklusi-Eksklusi (Principle of Inclusion-Exclusion), Rosen, p 500/526
Berapa banyak unsur dalam penyatuan dua set terbatas? Pada Bagian 2.2 kita menunjukkan bahwa
jumlah elemen dalam penyatuan dua set A dan B adalah jumlah dari jumlah elemen dalam set dikurangi
jumlah elemen dalam persimpangan mereka. Artinya, IA U BI = IAI + IBI- IA n BI.
Seperti yang kami tunjukkan di Bagian 5.1, rumus untuk jumlah elemen dalam penyatuan dua set?
berguna dalam masalah counting. Contoh 1-3 memberikan ilustrasi tambahan kegunaan
dari formula ini.
In a discrete mathematics class every student is a major in computer science or mathematics,
or both. The number of students having computer science as a major (possibly along with
mathematics) is 25; the number of students having mathematics as a major (possibly along with
computer science) is 13; and the number of students majoring in both computer science and
mathematics is 8. How many students are in this class?
Solution: Let A be the set of students in the class majoring in computer science and B be the set
of students in the class majoring in mathematics. Then A n B is the set of students in the class
who are joint mathematics and computer science majors. Because every student in the class
is majoring in either computer science or mathematics (or both), it follows that the number of
students in the class is I A UBI. Therefore,
Dalam kelas matematika diskrit ada mahasiswa Unsyiah, IAIN Ar-Raniry,
atau keduanya. Jumlah siswa yang berasal UNSYIAH adalah 25, jumlah mahasiswa dari IAIN adalah 13;
dan jumlah mahasiswa Unsyiah dan IAIN adalah 8. Berapa jumlah mahasiswa di kelas ini?
Solusi: Misalkan A himpunan mahasiswa UNSYIAH dan B adalah himpunan
mahasiswa IAIN. Maka A B adalah himpunan mahasiswa dari Unsyiah dan IAIN. Karena setiap siswa di
kelas jurusan berasal dari ilmu komputer atau matematika (atau keduanya), berarti jumlah siswa di kelas
adalah A U B. untuk itu
IA U BI = IAI + IBI - IA BI
= 25 + 13 - 8 = 30.
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
2/16
Page 2 of16
Misalkan ada 1807 mahasiswa baru di PPs Unsyiah. Dari jumlah tersebut, 453 yang mengambil mata
kuliah ilmu komputer, 567 yang mengambil mata kuliah matematika, dan 299 yang mengambil mata
kuliah keduanya: ilmu komputer dan matematika. Berapa banyak yang tidak mengambil mata kuliah
baik dalam ilmu komputer atau dalam matematika?
Solusi: Untuk menemukan jumlah mahasiswa baru yang tidak mengambil mata kuliah baik dalam
matematika maupun ilmu komputer, kita misalkan
Yang mengambil MK ilmu Komputer = IAI = 453,
Yang mengambil MK Matematika IBI = 567,
dan IA BI = 299. Jumlah mahasiswa baru mengambil MK baik ilmu komputer atau matematika.
Jadi
IA U BI = IAI + IBI-IA BI = 453 + 567-299 = 721.
Akibatnya, ada 1807 - 721 = 1086 mahasiswa baru yang tidak mengambil MK keduanya yaitu komputeratau matematika.
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
3/16
Page 3 of16
Mencari Formula untuk Jumlah Elemen di Gabungan Tiga Himpunan (Set)
Kita akan menghitung gabungan 3 set. Berbeda dengan gabungan dua set, di mana kita hanya
mengurangkan 1 irisan dari dua gabungan tersebut. Pada gabungan 3 set, di samping mengurangi
irisan atau intersection yang terjadi, kita juga harus menjumlahkan irisan dari gabungan 3 set.
Lihat hubungan dan gambar di bawah ini
Contoh soal
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
4/16
Page 4 of16
Sebanyak 1232 mahasiswa mengambil MK Bahasa Spanyol, 879 mengambil MK bahasa Prancis,
dan 114 mengambil MK bahasa Rusia. Selanjutnya, 103 mengambil bahasa Spanyol dan Perancis, 23
mengambil bahasa Spanyol dan Rusia, dan 14 mengambil Perancis dan Rusia. Jika 2092 mahasiswa
mengambil setidaknya satu dari Spanyol, Perancis, dan Rusia, berapa banyak siswa mengambil MK
semua tiga bahasa?
Solusi:
MisalkanS adalah himpunan mahasiswa yang mengambil bahasa Spanyol,
F adalah himpunan mahasiswa yang mengambil MK bahasa Prancis, dan
R adalah himpunan mahasiswa yang mengambil MK bahasa Rusia.
maka
dan
Kita masukkan ke dalam formula gabungan tiga set
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
5/16
Page 5 of16
2092 = 1232 + 879 + 114 - 103 - 23 - 14 + IS n F n RI.
Kita sekarang memecahkan/mencari IS n F n R I. Kita menemukan bahwa IS n F n RI = 7. Oleh karena itu,
ada tujuh mahasiswa yang mengambil MK untuk Spanyol, Perancis, dan Rusia. Ini diilustrasikan dalam
Gambar 4.
Dalam sebuah survey dari 120 orang, diketahui
65 membaca majalah Newsweek 20 membaca majalah Newsweekdan Time,45 membaca majalah Time, 25 membaca majalah Newsweekdan Fortune,42 membaca majalah Fortune, 15 membaca majalah Time dan Fortune,8 membaca kesemua 3 majalah
(A) Tentukan jumlah orang yang membaca setidaknya satu dari tiga majalah.
(B) Isikan angka yang benar dari orang pada delapan daerah dari diagram Venn pada Gambar. 1-9
bila N, T, dan F masing-masing menunjukkan himpunan orang yang membaca Newsweek, Time,
dan Fortune,.
(C) Tentukan jumlah orang yang membaca tepat satu majalah.
(a)
(NTF)= (N) + (T ) + (F ) (NT ) (NF) (TF) + (NTF)
= 65 + 45 + 42 20 25 15 + 8 = 100
(b)
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
6/16
Page 6 of16
(b) Diagram Venn pada Gambar diperlukan. 1-9 (b) diperoleh sebagai berikut:
65 membaca majalah Newsweek 20 membaca majalah Newsweekdan Time,45 membaca majalah Time, 25 membaca majalah Newsweekdan Fortune,42 membaca majalah Fortune, 15 membaca majalah Time dan Fortune,8 membaca kesemua 3 majalah
8 membaca semua tiga majalah,
20-8 = 12 membaca Newsweek dan Time tetapi tidak semua tiga majalah,
25-8 = 17 membaca Newsweek dan Fortune tapi tidak semua tiga majalah,
15-8 = 7 baca Time dan Fortune tapi tidak semua tiga majalah,
65-12 - 8 - 17 = 28 baca Newsweek saja,
45-12 - 8 - 7 = 18 hanya membaca Time,
42-17 - 8 - 7 = 10 baca Fortune saja,
120 - 100 = 20 tidak baca majalah sama sekali.
(C)28+ 18 + 10 = 56 yang membaca tepat 1 majalah
Sekarang kita telah siap membuat formula yang umum untuk gabungan-gabungan set
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
7/16
Page 7 of16
MisalA, B, C, D masing-masing menyatakan yang mengambil MK art, biology, chemistry, dandrama. Berikut adalah mahasiswa di asrama:
12 mengambilA, 5 mengambilA dan B, 4 mengambil B dan D, 2 mengambil B,C,D,20 mengambil B, 7 mengambilA dan C, 3 mengambil Cdan D, 3 mengambilA, C,D,20 mengambil C, 4 mengambilA dan D, 3 mengambilA, B,C, 2 mengambil A, B, C dan D,8 mengambil D, 16 mengambil B dan C, 2 mengambilA, B, D, 71 tidak mengambil sama sekali
Misalkan T banyaknya mahasiswa yang mengambil paling sedikit 1 MK. Sesuai denganTeorema 5.9
T= s1 s2 + s3 s4
Di mana:s1 = 12 + 20 + 20 + 8 = 60 ,s2 = 5 + 7 + 4 + 16 + 4 + 3 = 39 ,s3 = 3 + 2 + 2 + 3 = 10 ,s4 = 2.
Jadi T= 29, dan N= 71 + T= 100.
Teorema 1: Prinsip Inklusi-Eksklusi
Misalkan A1, A2, .,An adalah himpunan-himpunan yang terbatas, maka
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
8/16
Page 8 of16
References:
Epp, Susanna S. (2011). Discrete Mathematics with Applications, 4 th Edition, Cengage
Learning
Lipschutz, S., Lipson, M.L. (2007). Theory and Problems of Discrete Mathematics, Schaum'sOutline, 3rd ed.
Rosen, K. H. (2007). Discrete Mathematics and Its Applications, 6th Ed., McGraw-Hill
http://www.goodreads.com/author/show/74450.Seymor_Lipschutzhttp://www.goodreads.com/author/show/74450.Seymor_Lipschutz -
7/30/2019 7. Prinsip Inklusi-Eksklusi
9/16
Page 9 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
10/16
Page 10 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
11/16
Page 11 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
12/16
Page 12 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
13/16
Page 13 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
14/16
Page 14 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
15/16
Page 15 of16
-
7/30/2019 7. Prinsip Inklusi-Eksklusi
16/16
Page 16 of16