matematika diskrit - materi 1

7/21/2019 Matematika Diskrit - Materi 1

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

Matematika Diskrit 

7/21/2019 Matematika Diskrit - Materi 1

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

 Aturan Perkuliahan

• Toleransi keterlambatan 15 menit dari Jadwalperkuliahan di mulai 

• Selama perkuliahan HP Silent •

Mahasiswa wajib menggunakan pakaian berkerahdan bersepatu• Mahasiswa wajib membawa DHK

7/21/2019 Matematika Diskrit - Materi 1

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

 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

7/21/2019 Matematika Diskrit - Materi 1

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

Etika Mahasiswa

7/21/2019 Matematika Diskrit - Materi 1

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

Sistem Penilaian

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

* Ujian

UAS : 40 %

* Ujian

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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)

7/21/2019 Matematika Diskrit - Materi 1

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

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.

7/21/2019 Matematika Diskrit - Materi 1

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

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.

7/21/2019 Matematika Diskrit - Materi 1

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

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 

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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"

7/21/2019 Matematika Diskrit - Materi 1

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

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.

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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 

7/21/2019 Matematika Diskrit - Materi 1

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

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.

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

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 

7/21/2019 Matematika Diskrit - Materi 1

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

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 

7/21/2019 Matematika Diskrit - Materi 1

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

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 

7/21/2019 Matematika Diskrit - Materi 1

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

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

7/21/2019 Matematika Diskrit - Materi 1

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

Inferensi 

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

  (p q)

7/21/2019 Matematika Diskrit - Materi 1

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

 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

7/21/2019 Matematika Diskrit - Materi 1

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

 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