Matematika Diskrit

Yayan Eryk Setiawan, S.Pd.

Bagian Ke-1

Dalam kelas ada 40 siswa, banyak siswa yang memiliki foto-foto

bintang rock (rock stars) favorit mereka.

18 siswa memiliki foto dari Beatles,

16 siswa memiliki foto dari Rolling Stones,

12 siswa memiliki foto dari Elvis Presley (ketika masih muda),

7 siswa memiliki kedua foto dari The Beatles dan Rolling Stones,

5 siswa memiliki kedua foto dari Beatles dan Elvis Presley,

3 siswa memiliki kedua foto dari Rolling Stones dan Elvis Presley.

2 siswa memiliki ketiga foto dari tiga kelompok.

Pertanyaan:

Berapa banyak siswa di kelas yang tidak

memiliki foto apapun dari kelompok rock?

Pertama, kita dapat mencoba untuk berdebat seperti ini:

Ada 40 siswa dalam kelas;

mereka yang memiliki foto Beatles = 18 orang,

mereka yang memiliki foto Rolling Stones = 16 orang,

dan mereka yang memiliki foto Elvis = 12 orang;

jadi kami mengambil 18 + 16 + 12.

Kami mendapatkan –6; (40 – 46 = –6)

(angka negatif berarti terjadi kesalahan dalam perhitungan)

Kami membuat kesalahan ketika jumlah mereka dikurangi

jumlah siswa yang mengumpulkan gambar dua kali dari dua

kelompok !

Sebagai contoh,

Mahasiswa yang memiliki The Beatles dan Elvis Presley

dikurangkan dengan Kolektor Beatles serta dengan kolektor

Elvis Presley.

Untuk memperbaiki perhitungan kami, kita

harus menambahkan kembali jumlah para

siswa yang memiliki dua foto dari rock

stars.

Dengan cara ini kita mendapatkan

40 - (18 + 16 + 12) + (7 + 5 + 3).

Kita tidak boleh membuat kesalahan yang sama lagi!

apa terjadi pada 2 siswa yang memiliki foto dari ketiga rock stars?

jadi kita harus mengurangi mereka sekali lagi! Dengan koreksi ini,

Hasil akhir kami adalah:

40 − (18 + 16 + 12) + (7 + 5 + 3) − 2 = 7. (2.2.1)

Kita tidak bisa menemukan kesalahan dalam rumus ini, melihat dari

segala arah. Tapi belajar dari pengalaman kami sebelumnya, kami

harus lebih berhati-hati: Kita harus memberikan bukti yang tepat!

Misalkan seseorang mencatat data pemilik foto rock stars di

kelas dalam tabel, seperti Tabel 2.1 di bawah ini

Setiap berkoresponden baris untuk satu siswa; kita tidak

mengurutkan semua kebawah semua 40 baris, hanya

sebuah tipical.

Name Bonus Beatles Stones Elvis BS BE SE BSE

Al

Bel

Cy

Di

Ed

.

.

1

1

1

1 1

0

-1

-1

-1 -1

0

0

-1

0 -1

0

0

0

-1 -1

0

0

1

0 1

0

0

0

1 1

0

0

0

0 1

0

0

0

0 -1

TABEL 2.1. Catatan dari siapa yang memiliki foto rock stars

Tabel adalah sedikit konyol (tapi dengan alasan).

Pertama, kami memberikan bonus 1 untuk setiap siswa.

Kedua, kami mencatat dalam kolom terpisah apakah siswa adalah

mengumpulkan (katakanlah) baik Beatles dan Elvis Presley (kolom

berlabel BE), meskipun ini dibaca tidak ada hubungan dari kolom

sebelumnya.

ketiga, kami menempatkan -1 di kolom pengumpulan gambar ganjil,

dan 1 di kolom pengumpulan genap.

Name Bonus Beatles Stones Elvis BS BE SE BSE

Al

Bel

Cy

Di

Ed

.

.

1

1

1

1 1

0

-1

-1

-1 -1

0

0

-1

0 -1

0

0

0

-1 -1

0

0

1

0 1

0

0

0

1 1

0

0

0

0 1

0

0

0

0 -1

Kami menghitung jumlah total entri dalam tabel ini dalam

dua cara yang berbeda.

Pertama, jumlah baris?

Kami mendapatkan 1 untuk Al dan 0 untuk orang lain. Ini

bukan suatu kebetulan. Jika kita mempertimbangkan

seorang mahasiswa seperti Al, siapa yang tidak memiliki

gambar apapun, maka siswa ini memberikan kontribusi

untuk kolom bonus, tapi tempat lain, yang berarti bahwa

jumlah pada baris siswa ini adalah 1.

Selanjutnya, pertimbangkan Ed, yang memiliki semua 3

gambar. Dia memiliki 1 di kolom bonus; dalam 3 kolom

berikutnya ia memiliki 3 yang -1. dan 3 kolom berikutnya

ia memiliki 1, satu untuk setiap pasangan gambar

untuk memikirkan 3 lebih baik sebagai 32

.

Barisnya berakhir dengan 33

-1, dengan 33

= 1,

Tetapi dalam menulis cara ini, ide umum dapat melihat lebih

baik. Jadi jumlah baris adalah

1 - 11

= 0 Untuk Bel (1 gambar)

1 - 21

+ 22

= 0 untuk Cy dan Di (2 gambar)

1 - 31

+ 32

- 33

= 0 untuk Ed (3 gambar)

Jika kita pindahkan istilah negatif ke sisi lain dari

persamaan ini, kita mendapatkan sebuah persamaan

dengan makna kombinatorial : Sebagai contoh,

30

- 31

+ 32

- 33

= 0

Diperoleh :

30

+ 32

= 31

+ 33

Karena jumlah baris adalah 0 untuk semua siswa yang

memiliki gambar apapun grup musik, dan itu adalah 1 untuk

mereka yang tidak memiliki gambar sama sekali, jumlah

semua 40 jumlah baris memberikan jumlah para pelajar yang

tidak memiliki gambar persis sama sekali. Di sisi lain, jumlah

kolom?

Dalam "bonus" kolom, kami memiliki 40 kali +1;

Di kolom "Beatles", kami memiliki 18 kali -1;

Di kolom “Stones”, kami memiliki 16 kali -1

Di kolom “Elvis”, kami memiliki 12 kali -1

Di kolom “BS”, kami mendapatkan 7 kali +1

Di kolom “BE”, kami mendapatkan 5 kali +1

Di kolom “SE” kami mendapatkan 3 kali +1

Di kolom “BSE” kami mendapatkan 2 kali -1

Dalam "bonus" kolom, kami memiliki 40 kali +1 = 40

Di kolom "Beatles", kami memiliki 18 kali -1 = -18

Di kolom “Stones”, kami memiliki 16 kali -1 = -16

Di kolom “Elvis”, kami memiliki 12 kali -1 = -12

Di kolom “BS”, kami mendapatkan 7 kali +1 = 7

Di kolom “BE”, kami mendapatkan 5 kali +1 = 5

Di kolom “SE” kami mendapatkan 3 kali +1 = 3

Di kolom “BSE” kami mendapatkan 2 kali -1 = -2

Sehingga diperoleh :

40 – 18 – 16 – 12 + 7 + 5 + 3 – 2 = 7

Hal ini sama dengan (2.2.1) di atas.

Formula ini disebut Formula Inklusi-Eksklusi

atau Formula saringan.

Asal usul nama pertama jelas;

kedua mengacu pada gambar yang kita mulai

dengan satu himpunan objek yang besar dan

kemudian "saringan keluar" benda-benda yang tidak

ingin kita hitung.

Kita bisa memperpanjang metode ini

jika siswa mengumpulkan 4 atau 5

gambar, atau sejumlah grup rock

bukan 3. Daripada menyatakan

sebuah Teorema umum (yang akan

panjang).

Kesimpulannya

Formula Inklusi-Eksklusi adalah Formula dimana :

Memberi 1 bonus pada masing-masing siswa.

Mencatat dalam kolom terpisah setiap data.

Menempatkan -1 dipengumpulan ganjil dan 1 di

pengumpulan genap.

Jumlah setiap barisnya selain satu baris adalah nol (0)

Jumlah setiap kolom menentukan

hasilnya dengan cara masing-

masing jumlah kolom di

tambahkan.

Dalam sebuah kelas semua adalah anak laki-laki,

18 suka bermain catur,

23 suka bermain sepak bola,

21 suka bersepeda

17 suka mendaki.

12 suka bersepeda dan mendaki.

9 suka bermain catur dan sepak bola.

7 suka bermain catur dan bersepeda,

6 suka bermain catur dan mendaki,

12 suka bermain sepak bola dan bersepeda,

9 suka bermain sepak bola dan mendaki,

12 suka bersepeda dan mendaki.

Latihan 2.3.1

4 anak laki-laki yang suka catur, sepak bola, dan bersepeda,

3 yang suka catur, sepak bola, dan hiking,

5 yang suka catur, bersepeda, dan hiking,

7 yang suka sepak bola, bersepeda, dan hiking.

3 anak laki-laki yang seperti semua empat kegiatan.

Pertanyaan :

Selain itu kita tahu bahwa semua orang

suka setidaknya satu dari kegiatan ini.

Berapa banyak anak laki-laki yang ada

di kelas?