Matematika Diskrit PDF

Preview

Summary

Matematika Diskrit DAFTAR ISI BAB 1. PENDAHULUAN ..................................................................................................1 A. DEFINISI .................................................................................................................................. 1 B. HU...

Description

Accelerat ing t he world's research.

Matematika Diskrit Julie Kristin

Related papers

Download a PDF Pack of t he best relat ed papers 

KURIKULUM BERBASIS KOMPET ENSI JUR MAT EMAT IKA t ody amanah MAT EMAT IKA DISKRIT UNT UK Maxrizal Maxrizal LECT URE NOT ES MAT EMAT IKA DISKRIT JURUSAN T EKNIK INFORMAT IKA UNIVERSITAS GUNADARMA Danang Priabada

Matematika Diskrit

DAFTAR ISI BAB 1. PENDAHULUAN ..................................................................................................1 A. DEFINISI .................................................................................................................................. 1 B.

HUBUNGAN M ATEM ATIKA DISKRIT DENGAN M ATAKULIAH LAIN............................................. 1

C.

M ATERI YANG DIBAHAS........................................................................................................... 1

D. PENERAPAN / APLIKASI M ATEM ATIKA DISKRIT ........................................................................ 2

BAB 2. DASAR-DASAR LOGIKA ........................................................................................3 A. KALIM AT DEKLARATIF.............................................................................................................. 3 B.

PENGHUBUNG KALIM AT.......................................................................................................... 3

BAB 3. ALJABAR BOOLE ............................................................................................... 13 1.

STRUKTUR ALJABAR............................................................................................................... 13

2.

FUNGSI BOOLEN .................................................................................................................... 13

3.

EKSPRESI BOOLEN ................................................................................................................. 13

4.

BENTUK NORM AL DISJUNGTIF............................................................................................... 16

BAB 4. M ETODE PEM BUKTIAN ..................................................................................... 21 A. PETUNJUK UM UM DALAM EM BUKTIAN ................................................................................ 21 B.

M ETODE PEM BUKTIAN LANGSUNG ....................................................................................... 22

C.

M ETODE PEM BUKTIAN TAK LANGSUNG ................................................................................ 23

D. M ETODE PEM BUKTIAN DENGAN KONTRADIKSI ..................................................................... 23 E.

M ETODE PEM BUKTIAN DENGAN KONTRAPOSISI ................................................................... 24

F.

M EM ILIH M ETODE PEM BUKTIAN ........................................................................................... 25

BAB 5. INDUKSI M ATEM ATIKA ..................................................................................... 26 A. PRINSIP INDUKSI M ATEM ATIKA ............................................................................................. 26 B.

APLIKASI INDUKSI M ATEM ATIKA DALAM PEM ROGRAM AN .................................................... 29

BAB 6. HIM PUNAN ...................................................................................................... 31 A. DASAR TEORI HIM PUNAN ...................................................................................................... 31 B.

M ENYATAKAN HIM PUNAN .................................................................................................... 31

C.

DIAGRAM VENN .................................................................................................................... 33

D. HIM PUNAN BAGIAN DAN KESAM AAN HIM PUNAN ................................................................ 34 E.

SEM ESTA PEM BICARAAN DAN HIM PUNAN ............................................................................ 35

F.

OPERASI-OPERASI PADA HIM PUNAN ..................................................................................... 35

G. PEM BUKTIAN-PEM BUKTIAN HIM PUNAN ............................................................................... 38

H. HIM PUNAN KUASA ................................................................................................................ 41

BAB 7. KOM BINATORIKA ............................................................................................. 42 A. DASAR PERHITUNGAN ........................................................................................................... 42 B.

ATURAN PEM NJUM LAHAN .................................................................................................... 42

C.

ATURAN PERKALIAN .............................................................................................................. 43

D. PENGHITUNG TAK LANGSUNG............................................................................................... 43 E.

KORESPONDENSI SATU-SATU ................................................................................................ 44

F.

KOM BINASI DAN PERM UTASI ................................................................................................ 45

G. FAKTORIAL ............................................................................................................................ 46 H. KOM BINASI ........................................................................................................................... 47 I.

PERM UTASI ........................................................................................................................... 48

J.

KOM BINASI DAN PERM UTASI DENGAN ELEM EN BERULANG.................................................. 48

K.

PETUNJUK DALAM PERHITUNGAN ......................................................................................... 49

L.

KOEFISIEN BINOM IAL ............................................................................................................ 49

M . IDENTITAS-IDENTITAS DALAM KOM BINASI DAN PERM UTASI ................................................. 50 N. SEGITIGA PASCAL .................................................................................................................. 50 O. TEOREM A BINOM IAL DAN M ULTINOM IAL ............................................................................ 50 P.

PRINSIP INKLUSI DAN EKSKLUSI ............................................................................................. 50

Q. BEBERAPA APLIKASI KOM BINATORIKA DALAM ILM U KOM PUTER .......................................... 53

BAB 8. TEORI GRAF...................................................................................................... 54 A. PENGERTIAN GRAF ................................................................................................................ 54 B.

GRAF SECARA FORM AL .......................................................................................................... 55

C.

PEWARNAAN ......................................................................................................................... 60

D. CONTOH PROBLEM A GRAF .................................................................................................... 61

BAB 9. RELASI ............................................................................................................. 65 A. RELASI HIM PUNAN ................................................................................................................ 65 B.

OPERASI-OPERASI PADA RELASI ............................................................................................. 66

C.

REPRESENTASI RELASI DALAM GRAF DAN M ATRIKS............................................................... 67

D. JENIS-JENIS RELASI................................................................................................................. 68 E.

RELASI EKUIVALEN ................................................................................................................. 70

F.

TUTUPAN (CLOSURE) ............................................................................................................. 71

G. PARTIAL ORDERING DAN TOTAL ORDER ................................................................................ 71 H. LATTICE ................................................................................................................................. 71

I.

APLIKASI RELASI DALAM ILM U KOM PUTER RELASI BASISDATA .............................................. 72

BAB 10. FUNGSI........................................................................................................... 74 A. FUNGSI YANG DIDEFINISIKAN PADA HIM PUNAN ................................................................... 74 B.

FUNGSI IDENTITAS................................................................................................................. 75

C.

FUNGSI KONSTAN .................................................................................................................. 75

D. FUNGSI LANTAI (FLOOR FUNCTION)....................................................................................... 76 E.

FUNGSI JARAK HAM M ING ..................................................................................................... 76

F.

FUNGSI POLINOM IAL............................................................................................................. 77

G. FUNGSI EKSPONENSIAL ......................................................................................................... 77 H. FUNGSI LOGARITM A .............................................................................................................. 77 I.

KESAM AAN FUNGSI ............................................................................................................... 78

J.

FUNGSI INJEKTIF, SURJEKTIF, DAN BIJEKTIF............................................................................ 78

K.

INVERS FUNGSI ...................................................................................................................... 79

L.

PRINSIP KANDANG M ERPATI (PIGEONHOLE PRINCIPLE) ......................................................... 80

M . KOM POSISI FUNGSI .............................................................................................................. 81 N. FUNGSI DALAM BAHASA PEM ROGRAM AN ............................................................................ 81

BAB 11. FUNGSI........................................................................................................... 82 A. PENDAHULUAN ..................................................................................................................... 82 B.

NOTASI " O" ........................................................................................................................... 82

C.

EFISIENSI ALGORITM A .......................................................................................................... 83

BAB 12. STRUKTUR ALJABAR ........................................................................................ 84 A. SISTEM ALJABAR.................................................................................................................... 84 B.

SEM IGRUP, M ONOID, DAN GRUP SEM IGRUP......................................................................... 84

C.

JENIS-JENIS GRUP .................................................................................................................. 85

D. SUBGRUP .............................................................................................................................. 87 E.

KOSET DAN TEOREM A LAGRANGE ......................................................................................... 87

F.

RING DAN FIELD .................................................................................................................... 87

G. HUBUNGAN ANTARA GRUP,RING, DAN FIELD ........................................................................ 88

Bab 1 Pendahuluan A. DEFINISI Benda dikatakan diskrit j ika ia terdiri dari sejumlah berhingga elemen yang berbeda atau elemen-elemen yang tidak bersambungan. Himpunan bilangan bulat (integer) dipandang sebagai obj ek diskrit. Kita dapat memahami diskrit dengan membandingkan lawan katanya yaitu kontinyu atau menerus (continuous). Himpunan bilangan riil (real) dipandang sebagai objek yang kontinyu. Di dalam matematika kita mengenal fungsi diskrit dan fungsi kontinyu. Fungsi diskrit digambarkan sebagai kumpulan titik-titik, sedangkan fungsi kontinyu digambarkan sebagai kurva. Matematika diskrit adalah cabang matematika yang mengkaj i objek-obj ek diskrit. Matematika diskrit berkembang sangat pesat dalam decade terakhir ini. Salah sat u alasan yang menyebabkan perkembangan pesat ini adalah karena computer digital bekerj a secara diskrit. I nformasi yang disimpan dan dimanipulasi oleh computer adalah dalam bentuk diskrit.

B. HUBUNGAN MATEMATIKA DISKRIT DENGAN MATAKULIAH LAIN Matematika diskrit merupakan ilmu paling dasar di dalam pendidikan informatika atau ilmu computer. Pada dasarnya informatika adalah kumpulan disiplin ilmu dan teknisk yang mengolah dan memanipulasi objek diskrit. Matematika diskrit memberikan landasan matematis unutk kuliah-kuliah lain di informatika. Mahasiswa yang mengambil kuliah seperti algoritma, struktur data, basis data, otomata dan teori bahasa formal, jaringan computer, keamanan computer, system operasi, teknik kompilasi dan sebagainya akan mengealami kesulitan jika tidak mempunyai landasan matematis dari matematika diskrit. Hal ini tidak mengherankan karena kebanyakan kuliah tersebut sering mengacu kepada konsep-konsep di dalam matematika diskrit. Karena itulah kuliah matematika diskrit diberikan pada tahun pertama perkuliahan informatika atau ilmu computer.

C. MATERI YANG DIBAHAS Di dalam kuliah matematika diskrit, materi matematika yang diberikan adalah matematika khas informatika, sehingga kadang-kadang kuliah ini dinamakan juga matematika informatika. Adapun materi-materi yang termasuk dalam matematika diskrit adalah: 1.

Logika

2.

Teori Himpunan

1

3.

Matriks

4.

Relasi dan Fungsi

5.

I nduksi Matematik

6.

Algortima

7.

Teori Bilangan Bulat

8.

Barisan dan Deret

9.

Teori Grup dan Ring

10. Alj abar Boolean 11. Kombinatorial 12. Teori Peluang Diskrit 13. Fungsi Pembangkit dan Analisis Rekurens 14. Teori Graf 15. Kompleksitas Algoritma 16. Pemodelan Komputasi Beberapa materi akan dipelajari lebih mendalam, seperti materi algoritma dipelajari secara lebih mendalam pada kuliah Algoritma dan Pemrograman, teori peluang diskrit pada kuliah Probabilitas dan Statistik, Pemodelan komputasi pada kuliah Otomata dan Teori Bahasa Formal, fungsi pembangkit dimasukkan ke dalam kuliah Model dan SI mulasi, sedangkan barisan dan deret biasanya dimasukkan ke dalam kuliah kalkulus.

D. PENERAPAN / APLIKASI MATEMATIKA DISKRIT Berikut ini contoh-contoh persoalan dalam kehidupan sehari-hari yang diselesaikan matematika diskrit:

dengan

1.

Berapa banyak kemungkinan jumlah password yang dapat dibuat dari 8 karakter?

2.

Berapa banyak string biner yang panjangnya 8 bit yang mempunyai bit 1 sejumlah ganj il?

3.

Bagaimana menentukan lintasan terpendek dari satu kota a ke kota b?

4.

“Makanan murah tidak enak”, “Makanan enak tidak murah”. Apakah kedua pernyat aan tersebut menyetakan hal yang sama?

2

Bab 2 Dasar-dasar Logika A. KALIMAT DEKLARATIF Kalimat Deklaratif (Proposisi) adalah kalimat yang bernilai benar atau salah, tetapi tidak keduanya. Berikut ini adalah beberapa contoh Proposisi : 2+ 2= 4 4 adalah bilangan prima Jakarta adalah ibukota negara I ndonesia Penduduk I ndonesia berjumlah 50 j uta

B. PENGHUBUNG KALIMAT Sering kali beberapa kalimat perlu digabungkan menjadi satu kalimat yang lebih panjang. Misalnya kalimat : ` 4 adalah bilangan gena dan 3 adalah bilangan ganjil ` merupakan gabungan dari 2 buah kalimat : ` 4 adalah bilangan genap ` dan kalimat ` 3 adalah bilangan ganjil ` didalam logika dikenal 5 buah penghubung : Simbol

Arti

Bentuk

1

~

Tidak / Not / Negasi

Tidak .........

2

^

Dan / And / Konjungsi

….. dan ……

3

v

Atau / Or / Disjungsi

….. atau ........

4

→

I mplikasi

Jika ....... maka .......

5

↔

Bi – implikasi

......bila dan hanya bila ......

Dalam matematika digunakan huruf – huruf kecil seperti p, q, r, ... untuk menyatakan sub kalimat dan simbol – simbol penghubung untuk menyatakan penghubung kalimat. Misalkan : p menyatakan kalimat ` 4 adalah bilangan genap ` q menyatakan kalimat ` 3 adalah bilangan ganjil `

3

Maka kalimat : 1 4 adalah bilangan genap dan 3 adalah bilangan ganjil ` dapat dinyatakan dengan simbol p ^ q Jika p dan q merupakan kalimat – kalimat, maka tabel kebenaran penghubung tampak pada tabel ( T = True/ benar , F = False/ salah ). Perhatikan bahwa secara umum, jika ada n variabel ( p, q, ...), maka tabel kebenaran memuat 2n baris. P

q

~ p

p^ q

pvq

p→q

p↔q

B

B

S

B

B

B

B

B

S

S

S

B

S

S

S

B

B

S

B

B

S

S

S

B

S

S

B

B

Contoh : Misal

k : Monde orang kaya s : Monde bersuka cita

Tulis bentuk simbolis kalimat berikut ini : a.

Monde orang yang miskin tetapi bersuka cita

b.

Monde orang kaya at au ia sedih

c.

Monde tidak kaya at aupun bersuka cita

d.

Monde seorang yang miskin atau ia kaya tetapi sedih

Anggaplah negasi dari kaya adalah miskin dan negasi dari bersuka cita adalah sedih Penyelesaian : a Kata penghubung tetapi mempunyai arti yang sama dengan kata penghubung sehingga simbolisnya adalah ~ k ^ s

` dan` ,

bkv~ s c Kalimat tersebut berarti bahwa Monde tidak kaya dan sekaligus Monde tidak bersuka cita. Bentuk simbolisnya ~ k ^ ~ s d ~ k v (k ^ ~ s)

4

TAUTOLOGI DAN KONTRADIKSI Dalam argumenta...