metode bukti -...

play next backrec

teori-1

contoh

A. LANGSUNG1. SATU-SATU2. KASUS-PERKASUS3. KESELURUHAN4. ELIMINASI5. EKIVALENSI

B. TDK LANGSUNG

2. KONTRAPOSISI1. KONTRADIKSI

METODE BUKTI

SI-S1 STMIK AMIKOM YOGYAKARTA

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

http://www.novapdf.com


play next backrec

satu-satu

contoh

Pembuktian dilakukan dengan mengecek satu persatu.

definisi

contoh

Buktikan bhw bilangan genap x, 10x40 merupakan jumlahan

dua bilangan prima





play next backrec

teori-1

contoh

Pembuktian dilakukan dengan membagi menjadi beberapa kasus dan dibuktikan secara terpisah.

definisi

contoh

Buktikan bhw untuk setiap bil riil x, jika |x|> 4 maka x2>16

kasus-kasus





play next backrec

contoh

Pembuktian dilakukan secara umum. Artinya, ambil sebarang objek dan

dibuktikan kebenarannya

definisi

contoh Buktikan, jika a dan b bilangan

ganjil maka a+b adalah genap

menyeluruh





play next backrec

contoh

Pembuktian dilakukan dengan mencari semua kemungkinan,

kmd dicek syarat tentang pememnuhannya

definisi

contoh Buktikan, jika p sebarang bil prima ganjil maka p=6n+1 atau

p=6n+5 atau p=3.

eliminasi





play next backrec

contoh

Pembuktian dilakukan secara dua arah. Pembuktian bi-implikasi

definisi

contoh

Misalkan a dan b bil bulat. Buktikan, bhw a dan b memiliki sisa yg sama jika dibagi bil pos n jika dan hanya

jika (a-b) habis dibagi n

ekivalensi





play next backrec

contoh

a = k n + c b = l n + c(a – b) = k n + c – l n – c =

= (k-l) n atau (a-b)/n (a-b)/n (a-b) = k n, untuk suatu k

bulat.k B maka l,m B shg k = l – m(a-b) = (l-m) n = l n + x - (m n + x)

bukti

ekivalensi





play next backrec

contoh

Pembuktian dilakukan dengan :1. Andaikan INGKARAN-nya benar2. Buktikan sehingga hasilnya kontradiksi

dengan hipotesa.

definisi

contoh 1. Buktikan bahwa tidak ada bilangan

bulat yang terbesar2. Buktikan bahwa hasilkali 2 bil ganjil

adalah ganjil

kontradiksi





play next backrec

contoh

Andaikan ada bil bulat terbesar, misal No.Maka n bulat n No.Dr sisi lain, n bulat maka n+1 bulat. Krn

No bulat maka No+1 bulat, misal k=No+1.

Ada k bulat dan No k.Kontradiksi dg No bil bul terbesar.Pengandaian salah.

bukti

kontradiksi





play next backrec

contoh

Pembuktian dilakukan denganmembuktikan kontraposisi-nya

definisi

contoh 1. Misalkan n sebarang bil bulat.

Buktikan, jika n2 bil genap maka n bil genap.

2. Untuk setiap bil bulat m dan n. Buktikan, jika m.n=1 maka m = 1 dan

n =1

kontraposisi





play next backrec

teori-1

contoh

Misalkan P(n) : statemen ygdidefinisikan dlm bil bulat

dan a suatu bil bulat yg tetap danterkecil.

INDUKSI MAT.

1. P(a) benar2. Jika P(k) benar maka P(k+1)

benar.P(n) berlaku untk setiap n





play next backrec

teori-1

contoh

1. Buktikan bhw : 1+2+…+ n = n(n+1)/2, untuk

semua bil bulat, n

CONTOH

2. Buktikan bhw : 12+22 + ….+ n2 =

n(n+1)(2n+1)/6, untuk setiap bilbulat n





Set Theory(1a)

Hand OutMATEMATIKA DISKRIT

Teknik Informatika STMIK AMIKOM Yogyakarta




14

Introduction

Set (himpunan) adalah suatu kumpulan objek-objek yang berbedaex: nama-nama mahasiswa kelas ini, merk-merk disket di toko komp.

Dinotasikan dengan huruf besarex: himpunan A, himpunan B, dll

Objek dalam himp. disebut elemen/anggota himpunanex: A = { 1, 2, 3 }, maka elemen-elemen himpunan A adalah 1, 2, dan

Himpunan yang tidak memiliki anggota disebut himpunan kosong (empty set), dinotasikan dengan ex: C = {x | x mod 5 = 0, 5<x<10}, maka C =




15

Menyatakan Himpunan Ada 2 cara:

1. Menuliskan tiap-tiap anggota himpunan diantara 2 kurung kurawalex: A = {Jhony, Yujiyem, Michael}

2. Menuliskan sifat-sifat dari semua anggota himpunan diantara 2 kurung kurawalex: B = {x | x = bilangan prima yang diawali dari angka 7}

Perhatikan tabel berikut:Cara-1 Cara-2

A = {3,5,7,11,13} A = {x bil prima | 3 x 13} B = {ayam, buku, api} B tidak dapat dinyatakan karena

tidak ada sifat yang sama tidak dapat dinyatakan karena jumlah anggota C tak terhingga

C = {x bil bulat | x>10}




16

Himpunan kuasa bagi himpunan A, adalah himpunan yang unsur-unsurnyaadalah semua himpunan bagian dari suatu himpunan, dinotasikan (A) ex: A = {a,b}, maka (A) = {,{A},{b},{a,b}}B = {1, 2, 3}, maka (B) = {,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Power Set




17

Union Dinotasikan dengan A B, yaitu { x S | x A x B} Diagram Venn:

contoh: A = {a,b}, B = {1,2,3}, dan C = {x|x = 2n, 0≤x<4, xbil. bulat}maka A B = {a,b,1,2,3}, A C = {a,b,1,2,4,8}Tentukan C B dan B C, A (C B) dan (A C) B

Operasi Himpunan




18

Intersection Dinotasikan dengan A B, yaitu { x S | x A x B} Diagram Venn:

contoh:A = {a,b}, B = {1,2,3}, dan C = {x|x = 2n, 0≤x<4, xbil. bulat}maka A B = , B C = {1,2}Tentukan A C dan C A, B (A C), dan (B A) C

Operasi Himpunan




19

Complement Dinotasikan dengan Ac , yaitu { x S | x A} Diagram Venn:

contoh:S = {x Y | Y kumpulan huruf alfabetik sebelum f dan bilangan oktal}A = {a,b}, B = {1,2,3}, dan C = {x|x = 2n, 0≤x<3, xbilangan bulat}Maka: Ac = {c,d,e, 0,1,2,3,4,5,6,7}, Cc = {a,b,c,d,e,3,5,6,7}Tentukan Bc, (Cc)c, (AB)c, (AB)c, dan B komplemen terhadap C

Operasi Himpunan




20

Difference Dinotasikan dengan A – B, yaitu { x S | x A x B } Diagram Venn:

contoh:S = {x Y | Y kumpulan huruf alfabetik sampai h dan bilangan oktal}A = {a,b,c,d}, B = {c,d,e,f}, dan C = {x|x = 2n, 0≤x<3, xbilangan bulat}Maka: S – A = {e,f,g,h, 0,1,2,3,4,5,6,7}, S – C = {a,b,c,d,e,f,g,h,0,3,5,6,7}Tentukan C – S dan A – B, Tentukan pula (B – A)c, (BC)c

Operasi Himpunan




21

Simetric Difference Dinotasikan dengan A B, yaitu (AB)-(AB) Diagram Venn:

contoh:S = {x Y | Y kumpulan huruf alfabetik sampai h dan bilangan oktal}A = {a,b,c,d}, B = {c,d,e,f}, dan C = {x|x = 2n, 0≤x<3, xbilangan bulat}Maka: A B = {a,b,e,f}, B C = {c,d,e,f, 1,2,4}Tentukan A C, tentukan pula (A B C)c

Operasi Himpunan




22

Komutatif, yaitu A B = B A dan A B = B A A = {a,b,c,d}, dan B = {c,d,e,f}

maka,A B = {a,b,c,d,e,f}B A = {a,b,c,d,e,f}A B = {c,d}B A = {c,d}

Sehingga dapat disimpulkan:A B = B A dan A B = B A

Sifat Operasi Himpunan




23

Asosiatif,yaitu (A B) C = A (B C), dan (A B) C = A (B C) A = {a,b}, B = {b,c,d}, C = {1,2,3,4}

maka,A B = {a,b,c,d}, (A B) C = {a,b,c,d,1,2,3,4} B C = {b,c,d,1,2,3,4} A (B C) = {a,b,c,d,1,2,3,4}A B = {b}, (A B) C = B C = A (B C) =

Sehingga dapat disimpulkan:(A B) C = A (B C), dan (A B) C = A (B C)

Sifat Operasi Himpunan




24

1. Tentukan A B, A B, Ac , dan B – A, jika S himpunan bilangan riil R, dimana A = {x R | -1 < x 0} dan B = {x R | 0 x < 3}

2. Jika P = {x | x bilangan genap positif yang tidak lebih besar dari 10}, dan Q = { x = y + z dengan y {1,3,5}, dan z {1,3,5}}, maka tentukan1) P Q2) P Q3) (P Q) (P Q)4) Apakah himpunan P dan Q dikatakan sama (equal), mengapa?

Latihan




25

3. Jika diketahui A = {x: x= bilangan kelipatan 2} dan B = {x: x=bilangan kelipatan 3}Tentukan hasil dari A B

4. Jika A = {1,2,3,4,5} dan B = {3,4}Tentukan A – B, apakah BA, serta apakah A – B adalah komplemen B terhadap A

Latihan




Set Theory




Prinsip Inklusi dan Ekslusi

• |P| adalah kekardinalan (banyaknya unsur) himpunan P

• Misal, P = { a,b,c,d,e}, Q = {d,e,f}Maka:|P| = 5, |Q| = 3, PQ = {d,e}, sehingga |PQ| = 2PQ = {a,b,c,d,e,f}, sehingga |PQ| = 6





• Berikut beberapa hasil:– |PQ| |P| + |Q|– |PQ| min (|P|, |Q|)– |PQ| = |P| + |Q| - 2|PQ|– |P - Q| |P| - |Q|





• Secara umum, untuk himpunan-himpunan A1, A2, ......, Ar, diperoleh:

|...| 21 rAAA

|...|)1(...|| 211

1r

r

rkjikji AAAAAA

rji

jii

i AAA1

||||





• Akan ditunjukkan bahwa:|PQ| = |P| + |Q| - |PQ|

• Contoh 1:Di dalam himpunan 12 buku, 6 diantaranya novel, 7 buku diterbitkan tahun 1984, dan 3 novel diterbitkan tahun 1984.Misal:A1: himpunan buku novelA2: himpunan buku yang terbit tahun 1984Maka:|A1|=6, |A2|=7, dan |A1A2|=3Dengan demikian:|A1A2| =|A1| + |A2| - |A1A2|

= 6+7-3 = 10





• Artinya ada 10 buku yang berupa novel atau yang diterbitkan tahun 1984, atau keduanya.

• Dengan demikian dari 12 buku ada 2 buku yang bukan novel dan tidka diterbitkan tahun 1984





• Contoh 2:Ada 6 komputer dengan spesifikasi, sbb:

Komputer Unit aritmetikFloating point

Memory cakrammagnetik

Monitor grafik

I Ya Ya TidakII Ya Ya YaIII Tidak Tidak TidakIV Tidak Ya YaV Tidak Ya TidakVI Tidak Ya Ya





• Misalnya:A1, A2, dan A3 berturut-turut adalah himpunan komputer dengan unit aritmetik floating point, memori penyimpan cakram magnetik, dan terminal monitor grafik, maka kita peroleh:

|A1|=2, |A2|=5, |A3|=3|A1A2|=2, |A1A3|=1, |A2A3|=3

|A1A2 A3 |=1Dengan demikian:

|A1A2A3 |= 2+5+3-2-1-3+1 = 5Artinya: 5 diantara 6 komputer itu mempunyai 1 atau lebih dari 3 jenis perangkat keras yang disebutkan





• Contoh 3:Berapa banyak bilangan bulat antara 1 sampai 250 yang habis dibagi oleh 2,3,5,dan 7.Misal:A1, A2, A3, dan A4 berturut-turut adalah himpunan bilangan bulat yang habis dibagi 2, 3, 5, dan 7maka:





4132

250|21|

xAA

1252

250|1|

A 83

3250|2|

A 50

5250|3|

A 35

7250|4|

A

2552

250|31|

xAA 17

72250|41|

xAA

1653

250|32|

xAA 11

73250|42|

xAA 7

75250|43|

xAA





1235871116172541355083125|4321| AAAA

8532

250|321|

xxAAA

5732

250|421|

xxAAA

3752

250|431|

xxAAA

2753

250|432|

xxAAA

17532

250|4321|

xxxAAAA

193




Latihan1. Di antara bilangan bulat 1-300, berapa banyak yang tidak

habis dibagi 3, 5, dan 7. Berapa banyak yang habis dibagi 3, tetapi tidak habis dibagi 5 maupun 7

2. Di antara 100 mahasiswa, 32 mempelajari matematika, 20 mempelajari fisika, 45 mempelajari biologi, 15 mempelajari matematika dan biologi, 7 mempelajari matematika dan fisika, 10 mempelajari fisika dan biologi, dan 30 tidak mempelajari satupun di antara ketiga bidang tersebut.

a. Hitunglah berapa banyak yang mempelajari ketiga bidang tersebut

b. Hitunglah berapa banyak yang mempelajari hanya satu dari ketiga bidang tersebut




Latihan3. Enam puluh ribu superter sepakbola yang mendukung

pertandingan di kandang sendiri membeli habis semua cindera mata untuk mobil mereka. Secara keseluruhan laku terjual 20000 stiker, 36000 bendera kecil, dan 12000 gantungan kunci. Kita diberitahu bahwa 52000 superter membeli sedikitnya satu cindera mata dan tidak seorang pun membeli suatu jenis cindera mata lebih dari satu. Selain itu, 6000 superter membeli bendera kecil dan gantungan kunci, 9000 membeli bendera kecil dan stiker, dan 5000 membeli gantungan kunci dan stiker.

a. Berapa banyak suporter yang membeli ketiga macam cindera mata di atas.

b. Berapa banyak suporter yang membeli tepat satu cindera mata.




Latihan

4. Pada sebuah pertemuan reuni yang dihadiri oleh 30 wanita, 17 merupakan keturunan daerah Bantul, 16 keturunan daerah Wonosari, dan 5 bukan keturunan Bantul maupun Wonosari. Berapa banyak di antara 30 wanita itu yang keturunan Bantul dan Wonosari?

5. Diantara 50 mahasiswa di sebuah kelas, 26 memperoleh nilai A dari ujian pertama, dan 21 memperoleh nilai A dari ujian kedua. Jika 17 mahasiswa tidak memperoleh nilai A dari ujian pertama maupun ujian kedua, berapa banyak mahasiswa yang memperoleh dua kali nilai A dari kedua ujian?




Latihan6. Diantara 130 mahasiswa, 60 memakai topi di dalam kelas,

51 memakai syal di leher, dan 30 memakai topi dan syal. Diantara 54 mahasiswa yang memakai sweater, 26 memakai topi, 21 memakai syal, dan 12 memakai topi dan syal. Mereka yang tidak memakai topi maupun syal memakai sarung tangan.

a. Berapa banyak mahasiswa yang memakai sarung tangan

b. Berapa banyak mahasiswa yang tidak memakai sweater memakai topi, namun tidak memakai sarung syal

c. Berapa banyak mahasiswa yang tidak memakai sweater tidak memakai topi ataupun syal




metode bukti -...

Documents