matematika diskrit - materi 1

7/21/2019 Matematika Diskrit - Materi 1

http://slidepdf.com/reader/full/matematika-diskrit-materi-1 1/30

Matematika Diskrit



Aturan Perkuliahan

• Toleransi keterlambatan 15 menit dari Jadwalperkuliahan di mulai

• Selama perkuliahan HP Silent •

Mahasiswa wajib menggunakan pakaian berkerahdan bersepatu• Mahasiswa wajib membawa DHK



Aturan UTS dan UAS

• Tidak di berikan ujian susulan baik UTS dan UAS(kecuali menyertakan surat keterangan orangtua, wali/sakit)

• Tidak diberikan tugas susulan, maupunpenerimaan tugas yang terlambat dikumpul sesuai jadwal

• Bila terdapat kecurangan/nama terdaftar dalamberita acara ujian langsung diberikan nilai E

• Wajib membawa buku kuning selamamelangsungkan ujian



Etika Mahasiswa



Sistem Penilaian

Absen : 10 %Tugas /Quiz : 20 %UTS : 30 %

* Ujian

UAS : 40 %

* Ujian



Buku Referensi

Rosen, K.H., 2012, Discrete Mathematics and Its Applications Seventh Edition, McGraw-Hil,New York.

Haggard, G., Schlipf, J., dan Whitesides, S., DiscreteMathematics for Computer Science, 2006,Thomson Higher Education, USA.

Munir, R., 2012, Matematika Diskrit, Informatika,Bandung



Materi 1. Logika2. Teori Himpunan3. Matriks4. Relasi dan fungsi 5. Induksi matematik6. Algoritma

7. Teori Bilangan bulat 8. Baris dan deret 9. Teori Grup dan Ring10. Aljabar Boolean11. Kombinatorial12. Teori Peluang Diskrit

13. Fungsi Pembangkit dan Analisa Rekurens14. Teori Graf (termasuk Tree)15. Kompleksitas Algoritma16. Pemodelan Komputasi (Otomata dan Teori Bahasa Formal)



Logika dan Proposisi •

Logika adalah dasar dari penjabaran matematika(mathematical reasoning)• Logika mempelajari penjabaran (reasoning ) secara benar • Fokus pada relasi antar pernyataan (statement ) /

kalimat (sentence ).

Contoh:Semua pengendara sepeda motor memakai helmSetiap orang yang memakai helm adalah mahasiswa Jadi, semua pengendara sepeda motor adalah mahasiswa

• Perhatikan bahwa logika tidak harus memperhatikan isi kalimat; jika diketahui bahwa dua kalimat pertama diatas benar, maka kalimat ketiga harus benar.



Logika dan Proposisi •

Proposisi adalah kalimat deklaratif (yaitu, kalimat yangmenyatakan fakta) yang bisa benar atau salah, tetapi tidakkeduanya.

• Proposisi merupakan sebuah pernyataan atau kalimat yang punya nilai kebenaran (benar = 1 / salah = 0).

Proposisi disimbolkan dengan huruf p, q, dsb.

• Contoh proposisi: – Bandung adalah ibukota Jawa Barat –

1 + 1 = 2Contoh bukan proposisi: – Sekarang jam berapa? – Baca dengan seksama.



Kombinasi Proposisi • Jika p dan q adalah proposisi, dapat dibentuk

proposisi (majemuk) baru (compound proposition ) dengan menggunakan konektif

• Macam-macam konektif: – AND (konjungsi) Simbol ^ – Inclusive OR (disjungsi) Simbol v – Exclusive OR Simbol

–

NOT (negasi) Simbol – Implikasi Simbol

– Implikasi ganda Simbol



Konektif Negasi (NOT)Operasi negasi membalikkan nilai kebenaran suatu pernyataan.Contoh :p : Ibukota Kalbar adalah Singkawang~p : Ibukota Kalbar Bukan Singkawang

p bernilai S ( salah ) dan ~p bernilai B ( benar )

Konjungsi (AND)• p q• Hubungan p q bernilai true (benar) jika

kedua p dan q adalah benar selain itubernilai false (salah).

Contoh :• p = Harimau adalah binatang buas• q = Malang adalah ibukota Jawa Timur • p ^ q = Harimau adalah binatang buas dan

Malang adalah ibukota Jawa Timur • p ^ q salah.• Perhatikan bahwa tidak perlu ada

keterkaitan antara p dan q



Konektif

Disjungsi (Inclusive OR)• p v q• Hubungan p v q bernilai false (salah) jika

kedua p dan q adalah salah, selain itubernilai true (benar).

Contoh:• p = Jono seorang mahasiswa• q = Mira seorang sarjana hukum• p v q = Jono seorang mahasiswa atau Mira

seorang sarjana hukum

Exclusive OR• p

q, “Either p or q” (but not both )• p q bernilai benar hanya jika p benar dan

q salah, atau p salah dan q benar Contoh• p = "John is programmer • q = "Mary is a lawyer"• p q = "Either John is a programmer or

Mary is a lawyer"



Konektif IMPLIKASI (IF-THEN)

• Disebut juga Proposisi Kondisional(condotional proposition)

• p disebut antecedent, hypothesis,premise

• q disebut konsekuensi atau konklusi

(consequent, conclusion)• Jika p maka q.• p q• Hubungan p

q bernilai salah (false) jika p benar dan q salah, selain itu

bernilai benar (true)Contoh :• p = Maria learns discrete mathematics• q = Maria will find a good job• p → q = If Maria learns discrete mathematics, then she will find

a good job.



Konektif IMPLIKASI GANDA

• Implikasi Ganda (double implication ) dibaca• “p jika dan hanya jika q”

• Notasi simboliknya p q

•

p

q ekivalen dengan (p

q)^(q

p)

p q p q (p q) ^ (q p)

0 0 1 1

0 1 0 0

1 0 0 0

1 1 1 1



Ekivalensi Logikal

• Dua proposisi yang tabel kebenarannya identik disebut ekivalen (logically equivalent ).

• Contoh: p q ekivalen (logically equivalent to ) p q

p q p q p q

0 0 1 1

0 1 1 11 0 0 0

1 1 1 1



Konversi dan Inversi

• Konversi dari p q adalah q p• Inversi dari p

q adalah

p

q• p

q tidak ekivalen q

p•

p

q tidak ekivalen

p

qp q p q q p p q

0 0 1 1 1

0 1 1 0 0

1 0 0 1 1

1 1 1 1 1



Kontrapositif

• kontrapositif dari proposisi p q adalah q p

• p q dan q p ekivalen

p q p

q

q

p0 0 1 1

0 1 1 11 0 0 01 1 1 1



Tabel Kebenaranp q p

q

(p

q) p

(p

q)

T T T F T T F F T T

F T F T T

F F F T T

p

(p

q) adalah sebuah Tautologi, karena kolom terakhir

tabel kebenaran hanya berisi T

p q p q p q (p q) (p q) (p q)

T T T T F F

T F F T F F F T F T F F

F F F F T F

(p q) (p q) adalah sebuah Kontradiksi, karena kolomterakhir tabel kebenaran hanya berisi F



Tabel Kebenaranp

p p

p

T F T F T F

p

p adalah sebuah Kotingen, karena kolom terakhir

tabel kebenaran berisi T dan F.



Ekivalensi Namap T pp F p

Identity laws

p T T

p F F

Domination laws

p p pp p p

Idempotent laws

(p) p Double negation laws

p q q pp q q p

Commutative laws

(p q) r p (q r)(p q) r p ( q r)

Associative laws

Ekivalensi Logika



Ekivalensi Logika

Ekivalensi Namap (q r) (p q) (p r)p (q r) (p q) (p r)

Distributive laws

(p

q)

(

p)

(

q)(p q) ( p) ( q) De Morgan’s laws

p

(p

q)

pp (p q) p

Absorption laws

p

p

T p p F

Negation laws



Ekivalensi Logika

Ekivalensi p q p qp

q

q

pp q p q

p

q

(p

q)

(p

q)

p

q(p q) (p r) p (q r)(p

r)

(q

r)

(p

q)

r (p q) (p r) p (q r)

(p

r)

(q

r)

(p

q)

r

Ekivalensi p q (p q) (q p)p q p qp

q

(p

q)

(

p

q)

(p q) p q



Operasi Logika di dalam Komputer

• Bahasa pemrograman untuk logika berupa tipeBoolean yang hanya mempunyai dua buahkonstanta nilai yaitu True dan False.

• Operator boolean yang digunakan dalampemrograman adalah AND, OR, XOR dan NOT.

•

Operasi Boolean hanya menghasilkan nilai trueatau false



Inferensi

• Inferensi : proses penarikan kesimpulan dari beberapa proposisi

1. Modus Ponenp q (p (p q)) qp

q

• Simbol

dibaca sebagai “ jadi ” atau “karena itu”.

• Modus ponen menyatakan bahwa jika hipotesis p dan implikasi p q benar, maka konklusi q benar

• Contoh : Jika 20 habis dibagi 2, maka 20 adalah bil. Genap20 habis dibagi 2

20 adalah bil genap

Inferensi diatas adalah benar



Inferensi

2. Modus Tollen

p q ( q (p q)) p q

p

• Contoh : Jika n bil. Ganjil, maka n2 bernilai ganjiln2 bernilai genap

n bukan bil. GanjilInferensi diatas adalah benar



Inferensi

3. Silogisme Hipotesis

p q [(p q) (q r)] (p r)q r

p r

• Contoh : Jika saya belajar dengan giat, maka saya lulus ujian Jika saya lulus ujian, maka saya cepat menikah

Jika saya belajar dengan giat, maka saya cepat menikah

Inferensi diatas adalah benar



Inferensi 4. Silogisme Disjungtif

p q [(p q) p ] q p

q

5. Simplifikasi p q (p q) q

p

6. Penjumlahanp p (p q)p q



Inferensi

7. Konjungsi p [(p) (q)) (p q)q

(p q)



Argumen

Argumen adalah suatu deret proposisi yang ditulis sbb:

A1 A1, A2, …, An : Hipotesis A2 B : konklusi ..

An B

• Sebuah argumen dikatakan valid jika konklusi benar bilamana semua hipotesisnya benar (termasuk

tautologi)

• Sebuah argumen dikatakan invalid jika konklusi salahbilamana semua hipotesisnya salah



ArgumenContoh : Perhatikan argumen berikut

“ Jika air laut surut setelah gempa dilaut, maka tsunami datang. Air laut surut setelah gempa dilaut. Karena itu tsunami datang

p = air laut surut setelah gempa dilaut q = tsunami datang

Argumen ditulis : A1 p q A2 pB q

Lihat pada baris 1.Hipotesis 1 (p q) bernilai T Hipotesis 2 (p) bernilai T Konklusi (q) bernilai T

Argumen diatas Valid

Baris 1Baris 2Baris 3Baris 4

matematika diskrit - materi 1

Documents