matematika diskrit siap print

Upload: ratu-uniqua-ke-dua

Post on 07-Apr-2018

368 views

Category:

Documents


8 download

TRANSCRIPT

  • 8/4/2019 Matematika Diskrit Siap Print

    1/253

  • 8/4/2019 Matematika Diskrit Siap Print

    2/253

    2

    Tujuan Pembelajaran

    Mahasiswa mampu memahami konsep

    logika, metode pembuktian, himpunan,

    fungsi, induksi matematis & rekursi, relasidan dapat mengaplikasikannya pada

    permasalahan nyata.

  • 8/4/2019 Matematika Diskrit Siap Print

    3/253

    3

    Kompetensi

    Mahasiswa mampu menjelaskan dengan benar konsep

    logika dan dapat mengambil kesimpulan yang benar,

    Mahasiswa mampu mengaplikasikan metode-metode

    pembuktian yang efesien,

    Mahasiswa mampu menjelaskan & mengaplikasikan

    konsep himpunan dan fungsi,

    Mahasiswa menjelaskan induksi matematis dan rekursi

    & mengaplikasikan pada permasalahan nyata

    Mahasiswa menjelaskan konsep relasi &mengaplikasikan pada permasalahan nyata.

  • 8/4/2019 Matematika Diskrit Siap Print

    4/253

    Cara Belajar

    Perhatikan ketika dosen mengajar

    Kerjakan latihan seluruhnya

    4

  • 8/4/2019 Matematika Diskrit Siap Print

    5/253

    Bab dari Buku

    Bab 1 Logic and Proof

    Bab 2 Sets, function, sequence and sums

    Bab 4 Induction and recursion

    Bab 7 Advance Counting Technique

    Bab 8

    Relation

    5

  • 8/4/2019 Matematika Diskrit Siap Print

    6/253

    PERTEMUAN I

    LOGIKA

    6

  • 8/4/2019 Matematika Diskrit Siap Print

    7/253

    Logika

    Mempelajari penalaran/pemikiran (reasoning)

    secara benar

    Logicmempelajari bgm cara mengambilkesimpulan yang benar menurut aturan yang ada ,ex:or,and,not,dll

    Fokus pada relasi antar pernyataan (statement) /

    kalimat (sentence).

    7

  • 8/4/2019 Matematika Diskrit Siap Print

    8/253

    Logika Matematika Logika merupakan studi penalaran; yang secara khusus

    membahas apakah suatu penalaran benar atau tidak. Dasar dari teori logika adalah proposisi.

    Proposisi atau kalimat terbuka adalah kalimat yang bisabernilai benar atau salah, tetapi tidak sekaligus

    keduanya. Proposisi biasanya dinyatakan sebagai kalimat berita

    (bukan kalimat tanya, kalimat perintah dansebagainya).

    Dalam logika tidak disyaratkan adanya hubunganantara kedua kalimat penyusunnya hanya tergantungpada nilai kebenaran kalimat penyusunnya

    8

  • 8/4/2019 Matematika Diskrit Siap Print

    9/253

    Contoh LogikaNyatakan apakah setiap kalimat yang diberikan

    adalah proposisi atau bukan. Jika proposisi,

    bagaimana nilai kebenarannya?

    1. Matahari terbit dari Utara

    2. 1+2 = 3

    3. Kerjakan latihan soal di rumah!

    4. Apakah anda merasa senang kuliah di UPN ?

    5. Bumi adalah satu-satunya planet di jagat raya yang mempunyaikehidupan

    6. N adalah bilangan ganjil.7. Gajah lebih besar daripada kucing.

    8. 1089 < 101

    9. y > 15

    10. x < y jika dan hanya jika y > x 9

  • 8/4/2019 Matematika Diskrit Siap Print

    10/253

    Proposisi Huruf kecil, misal p, q, dan r, digunakan untuk

    menyatakan kalimat proposisi.

    Contoh: Notasi p: 1 + 1 = 3

    untuk mendefinisikan p sebagai proposisi 1+1 =

    3. Nilai kebenaran suatu proposisi ditentukan oleh

    kebenaran kalimat yang menyatakannya. Misal,proposisi 1+1 = 3 bernilai salah, sedangkan

    proposisi ,Paris ibu kota Perancis bernilai benar. Selanjutnya kita akan menulis B untuk

    menyatakan benar dan S untuk menyatakansalah.

    10

  • 8/4/2019 Matematika Diskrit Siap Print

    11/253

    Konjungsi, Disjungsi, & Negasi

    Misalkan p dan q adalah proposisi. Konjungsi p dan q, dinyatakan dengan

    , adalah proposisi p dan q.

    Disjungsi p dan q, dinyatakan dengan

    , adalah proposisi p atau q

    Negasi dari p, dinyatakan dengan atau ~p,

    adalah proposisi bukan p

    11

    qp

    qp

    p

  • 8/4/2019 Matematika Diskrit Siap Print

    12/253

    Tabel Kebenaran

    disjungsi (inclusive or)

    Contoh: p = Joni seorang mahasiswa

    q = Mira seorang sarjana hukum

    p v q = Joni seorang mahasiswa atau Mira seorang

    sarjana hukum

    12

    p q p v q

    S S S

    S B B

    B S B

    B B B

    P ^ q bernilai salah jika p dan q salah

  • 8/4/2019 Matematika Diskrit Siap Print

    13/253

    Tabel Kebenaran(truth table)

    Konjungsi (inclusive and)

    13

    p q p q

    S S S

    S B S

    B S S

    B B B

    P ^ q bernilai benar jika p dan q benar

  • 8/4/2019 Matematika Diskrit Siap Print

    14/253

    Konjungsi, Disjungsi, & Negasi (2)

    Catatan :

    Kata atau pada disjungsi digunakan dalam

    makna inklusif; yakni, dinyatakan benarapabila baik p, atau q, atau keduanya bernilai benar

    dan salah hanya jika kedua p dan q salah

    Sedangkan makna eksklusif-atau, dinyatakan p XOR

    q, bernilai benar apabila baik p atau q benar, tetapitidak keduanya.

    qp

    qp

    14

  • 8/4/2019 Matematika Diskrit Siap Print

    15/253

    Contoh

    1. Untuk proposisi2 berikut:

    p: 1+1 = 3

    q: Satu tahun sama dengan 12 bulanTentukanlah Konjungsi, Disjungsi, Negasi

    beserta nilai kebenarannya

    15

  • 8/4/2019 Matematika Diskrit Siap Print

    16/253

    Contoh (2)

    Jawab:

    a. : 1+1 = 3 dan satu tahun sama dengan 12bulan

    p salah dan q benar, maka nilainya SALAH

    b. : 1+1 = 3 atau satu tahun sama dengan12 bulan

    p salah atau q benar, maka nilainyaBENAR

    c. : 1+1 3

    Karena p salah, maka nilainyaBENAR

    qp

    qp

    16

    p

    p

  • 8/4/2019 Matematika Diskrit Siap Print

    17/253

    Contoh (3)

    2. Untuk proposisi2 berikut:

    p: 1+1 = 3

    q: Satu tahun sama dengan 12 bulanr: Tugu Pahlawan terletak di Surabaya

    Nyatakan proposisi simbolik dengan

    kata-kata dan kemudian evaluasi nilaikebenarannya.

    17

    r)qp(

  • 8/4/2019 Matematika Diskrit Siap Print

    18/253

    Kalimat majemuk

    compound statements

    p, q, r merupakan kalimat / pernyataan sederhana

    (simple statements) Beberapa contoh bentukan compound statements,

    seperti:

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

    18

  • 8/4/2019 Matematika Diskrit Siap Print

    19/253

    Tabel Kebenaran (p r)q

    19

    p q r (p r)qS S S (S B) S= SS S B (S S) S = SS B S (S B) B = BS B B (S S B = BB S S (B B) S = BB S B (B S) S = SB B S (B B) B = BB B B (B S) B = B

  • 8/4/2019 Matematika Diskrit Siap Print

    20/253

    Implikasi

    Disebut juga proposisi kondisional (conditionalproposition) dan berbentuk

    jika p maka q

    Notasi simboliknya : p q Contoh:

    p = " John rajin belajar"

    q = " John dapat hadiah "

    p q = If John rajin belajar then John dapat hadiah "

    20

  • 8/4/2019 Matematika Diskrit Siap Print

    21/253

    Tabel Kebenaran

    21

    p q p qS S B

    S B BB S S

    B B B

    P q benar jika p dan q benar atau p salah

  • 8/4/2019 Matematika Diskrit Siap Print

    22/253

    Hipotesa dan konklusi

    Dalam implikasi p qp disebut anteseden, hipotesa, premis

    (antecedent, hypothesis, premise)

    q disebut konsekuensi atau konklusi(consequence,conclusion)

    22

  • 8/4/2019 Matematika Diskrit Siap Print

    23/253

    Cara menyebut p qjika p maka q if p then q

    jika p, q if p, q

    q jika p q if pp hanya jika q p only if q

    p mengimplikasikan q p implies q

    23

  • 8/4/2019 Matematika Diskrit Siap Print

    24/253

    Eksklusif-Or, Implikasi, Bikondisional

    P Q PQtrue true false

    true false truefalse true true

    false false false

    P Q PQtrue true true

    true false false

    false true false

    false false true 24

    falsefalsetrue

    truetruefalsetruefalsefalse

    truetruetrue

    PQQP

  • 8/4/2019 Matematika Diskrit Siap Print

    25/253

    Kesamaan Logika

    Dua proposisi majemuk P dan Q disebut ekuivalen

    secara logika, ditulis sebagai bila keduanya

    mempunyai nilai kebenaran yang sama, tidak peduli

    nilai kebenaran yang dimiliki oleh proposisi unsur-unsurnya.

    Contoh: hukum De Morgan I

    dan II untuk logika, msg2 adalah

    ekuivalen secara logika.

    25

    QP

    qpqp

    qpqp

  • 8/4/2019 Matematika Diskrit Siap Print

    26/253

    Kesamaan Logika (2)

    Untuk menunjukkan dua proposisi majemukekuivalen secara logika dapat dilakukandengan mengecek nilai kebenaran kedua

    proposisi. Contoh:

    Tunjukkan hukum De Morgan yang pertama

    adalah ekuivalen secara logika.

    26

    qpqp

  • 8/4/2019 Matematika Diskrit Siap Print

    27/253

    Contoh Kesamaan Logika

    Tabel kebenaran untuk kesamaan tersebut adalah:

    Dari tabel di atas terlihat bahwa untuk nilai sembarang yang

    diberikan dari p dan q, dan mempunyai nilai

    kebenaran yang sama, sehingga dapat ditulis:

    27

    qp qp

    qpqp

  • 8/4/2019 Matematika Diskrit Siap Print

    28/253

    Tabel Kesamaan Logika

    28

  • 8/4/2019 Matematika Diskrit Siap Print

    29/253

    Tabel Kesamaan Logika

    untuk Kondisional & Bikondisional

    29

    p)

  • 8/4/2019 Matematika Diskrit Siap Print

    30/253

    Kesamaan Logika

    Keterangan:

    T : Pernyataan yang selalu bernilai BENAR

    (Tautologi)

    F : Pernyataan yang selalu bernilai SALAH

    (Kontradiksi)

    30

  • 8/4/2019 Matematika Diskrit Siap Print

    31/253

    Contoh Pembuktian

    Kesamaan Logika

    1. Tunjukkan bahwa ~(pV(~pq)) dan ~p~q adalahekivalen secara logika TANPA menggunakan tabelkebenaran!

    2. Tunjukkan bahwa (pq) (pVq) adalah sebuah

    Tautologi TANPA menggunakan tabel kebenaran!Petunjuk: Untuk menunjukkan bahwa pernyataandiatas adalah sebuah Tautologi, gunakan daftarkesamaan logika untuk menunjukkan bahwapernyataan tersebut ekivalen dengan T

    31

  • 8/4/2019 Matematika Diskrit Siap Print

    32/253

    Solusi Contoh 1

    ekivalenbenarqp

    qp

    qpT

    qpppqpp

    qpqpp

    32

  • 8/4/2019 Matematika Diskrit Siap Print

    33/253

    Solusi Contoh 2

    33

    TTT

    qqpp

    qpqp

    qpqp

    BABANB

    qpqp

    BA

    )()(

    :

  • 8/4/2019 Matematika Diskrit Siap Print

    34/253

    Latihan

    1. Jika p dan q bernilai benar (T); r dan s bernilai salah (F).

    Tentukan nilai kebenaran kalimat berikut :

    2. Tentukan apakah kalimat berikut ekivalen TANPA

    menggunakan tabel kebenaran :

    srqprqpbrqpa

    .

    .

    pqpqppb

    pqpqpa

    .

    .

    34

  • 8/4/2019 Matematika Diskrit Siap Print

    35/253

    Latihan

    3. Buktikan apakah kalimat berikut merupakan tautologi atau

    kontradiksi!

    35

    qpqbqqpa

    .

    .

  • 8/4/2019 Matematika Diskrit Siap Print

    36/253

    Proposisi Bersyarat

    Definisi:

    Misal p dan q adalah proposisi, proposisi majemuk

    jika p maka q disebut proposisi bersyarat dan

    dinotasikan sebagai p q Proposisi p disebut hipotesis (anteseden) dan

    proposisi q disebut konklusi (konsekuen)

    36

  • 8/4/2019 Matematika Diskrit Siap Print

    37/253

    Proposisi Bersyarat

    Nilai kebenaran dari proposisi bersyarat

    diberikan oleh tabel kebenaran berikut:

    37

  • 8/4/2019 Matematika Diskrit Siap Print

    38/253

    Implikasi p q

    Jika p, maka q

    Jika p, q

    p mengakibatkan q

    p hanya jika q

    p cukup untuk q

    Syarat perlu untuk p

    adalah q

    q jika p

    q ketika p

    q diakibatkan p

    q setiap kali p

    q perlu untuk p

    Syarat cukup untuk q

    adalah p

    38

  • 8/4/2019 Matematika Diskrit Siap Print

    39/253

    Proposisi Bersyarat

    Dalam percakapan sehari-hari, hipotesis dan konklusi dalamproposisi bersyarat biasanya berhubungan, tetapi dalamlogika, hipotesis dan konklusi dalam proposisi bersyarat tidakharus merujuk pada permasalahan yang sama.

    Logika memperhatikan bentuk proposisi dan hubungan antarproposisi tetapi tidak memperhatikan pokok permasalahandari proposisi itu sendiri.

    Perhatikan bahwa proposisi bersyarat yang benar berbedadengan proposisi bersyarat dengan konklusi yang benar.

    39

  • 8/4/2019 Matematika Diskrit Siap Print

    40/253

    Proposisi Bersyarat

    Contoh:1. Misal: p = 1 > 2

    q = Satu meter sama dengan 100 cm

    Tentukan nilai kebenaran dari proposisi bersyarat p q

    (Jika 1 > 2 maka satu meter sama dengan 100 cm)Jawab:

    p: salah q: benar

    Maka menurut tabel kebenaran 2.1, proposisi diatas bernilaiBENAR

    40

  • 8/4/2019 Matematika Diskrit Siap Print

    41/253

    Proposisi Bersyarat

    2. Tunjukkan bahwa pq ekivalen secara logika dengan ~pVq.

    Jawab:

    Tabel kebenaran untuk pq dan ~pVq:

    Kesimpulan: pq ekivalen scr logika dgn ~pVq

    pq ~pVq

    41

  • 8/4/2019 Matematika Diskrit Siap Print

    42/253

    Proposisi Bersyarat

    3. Bagaimana nilai kebenaran proposisi berikut:

    If today is Friday, then 2x3=5

    Jawab:

    p : today is Friday

    q : 2 x 3 = 5

    Proposisi di atas akan selalu bernilai BENARkecualipada hari Jumat

    42

  • 8/4/2019 Matematika Diskrit Siap Print

    43/253

    Proposisi Bersyarat

    4. Bagaimana nilai kebenaran proposisi berikut: Jika mhs ikut ujian, makaia harus membawa kartu ujian

    Jawab:

    p: Mhs ikut ujian

    q: mhs membawa kartu ujian

    43

  • 8/4/2019 Matematika Diskrit Siap Print

    44/253

    Bikondisional

    Misal p dan q adalah proposisi, proposisimajemukp jika dan hanya jika q disebut proposisibikondisional (dwisyarat) dan dinotasikan sebagai

    p q. Nilai kebenaran p q sebagai berikut:

    44

  • 8/4/2019 Matematika Diskrit Siap Print

    45/253

    Bikondisional

    Catatan : Cara lain menyatakan p jika dan hanya jika q adalah:

    p adalah syarat perlu dan cukup untuk q

    Jika p maka q, dan sebaliknya

    Contoh:

    1. p: You can take the flightq: You buy a ticket

    pq: You can take the flight if and only if you

    buy a ticket

    Pernyataan diatas benar jika p dan q keduanya benarataukeduanya salah. Pernyataan di atas salah jika hanya salahsatu dari p dan q yang benar.

    45

  • 8/4/2019 Matematika Diskrit Siap Print

    46/253

    Bikondisional

    3. Tunjukkan dgn tabel kebenaran bahwa:p q (pq) (qp)

    Jawab:Tabel kebenarannya sbb:

    Karena nilai kebenaran pq sama dengan nilai kebenaran(pq) (qp), maka keduanya ekivalen.

    46

  • 8/4/2019 Matematika Diskrit Siap Print

    47/253

    Konvers, Kontrapositif, Invers

    Misal sebuah kondisi bersyarat p q Konvers-nya : q p

    Kontrapositif-nya : ~q ~p

    Invers-nya : ~p ~q

    Contoh:

    Tentukan Konvers, Kontrapositif, dan Invers dari: Jika adapencuri masuk rumah, maka pintu dalam keadaan terbuka

    p: Ada pencuri masuk rumah

    q: Pintu dalam keadaan terbuka

    47

  • 8/4/2019 Matematika Diskrit Siap Print

    48/253

    Konvers, Kontrapositif, Invers

    Konvers (q p):

    Jika pintu dalam keadaan terbuka, maka ada pencurimasuk rumah

    Kontrapositif (~q

    ~p):Jika pintu dalam keadaan tertutup, maka tidak adapencuri masuk rumah

    Invers (~p ~q):

    Jika tidak ada pencuri masuk rumah, maka pintudalam keadaan tertutup

    48

  • 8/4/2019 Matematika Diskrit Siap Print

    49/253

    Ekspresi Logika

    Contoh 4. Ubah ke dalam ekspresi logika:

    Anda mempunyai akses internet hanya jika anda mahasiswa

    Matematika ITB atau anda bukan mahasiswa TPB

    Solusi. Misal a : Anda punya akses internetm: Anda mhs Matematika ITB

    f : Anda mhs TPB

    a (m f)

    49

  • 8/4/2019 Matematika Diskrit Siap Print

    50/253

    Ekspresi Logika (2)

    Soal 1. Ubah kedalam ekspresi logika.

    Anda tidak boleh naik roller coaster jika tinggi anda

    kurang dari 100 cm, kecuali usia anda sudah

    melebihi 16 th.

    Saya akan ingat tentang kuliah besok hanya jika

    kamu mengirim sms.

    Pantai akan erosi ketika ada badai

    50

  • 8/4/2019 Matematika Diskrit Siap Print

    51/253

    Logika Inferensi

    Modus Ponen

    Modus Tollen

    q

    p

    qp

    p

    q

    qp

    51

    Penambahan Disjungtif

    qpqp

    qp

    Penyederhanaan Konjungtif

    qpqpqp

  • 8/4/2019 Matematika Diskrit Siap Print

    52/253

    Logika Inferensi (2)

    Silogisme Disjungtif

    Silogisme Hipotesispq

    qp

    qpqp

    rp

    rq

    qp

    52

    Dilema

    Konjungsi

    rrq

    rp

    qp

    qp

    q

    p

  • 8/4/2019 Matematika Diskrit Siap Print

    53/253

    Contoh

    Pada suatu hari, Anda hendak pergi ke kampus dan baru sadar bahwaAnda tidak memakai kacamata. Setelah mengingat-ingat, ada beberapafakta yang Anda pastikan kebenarannya :

    a. Jika kacamataku ada di meja dapur, maka aku pasti sudah melihatnya ketikasarapan pagi.

    b. Aku membaca koran di ruang tamu atau aku membacanya di dapur.

    c. Jika aku membaca koran di ruang tamu, maka pastilah kacamata kuletakkan dimeja depan.

    d. Aku tidak melihat kacamataku pada waktu sarapan pagi.

    e. Jika aku membaca buku di ranjang, maka kacamata kuletakkan di meja sampingranjang.

    f. Jika aku membaca koran di dapur, maka kacamataku ada di meja dapur.

    Berdasarkan fakta-fakta tersebut, tentukan di mana letak kacamata

    tersebut !

    53

  • 8/4/2019 Matematika Diskrit Siap Print

    54/253

  • 8/4/2019 Matematika Diskrit Siap Print

    55/253

    Inferensi yang dapat dilakukan adalah sbb :

    PonenModusdengant

    (3)darikesimpulanr(c)faktatr4.

    DisjungtifSilogismedenganr

    (2)darikesimpulans

    (b)faktasr3.TollenModusdengans

    (1)darikesimpulanp

    (f)faktaps2.

    TollenModusdenganp(d)faktaq

    (a)faktaqp1.

    55

    Kesimpulan kacamata ada di meja tamu

  • 8/4/2019 Matematika Diskrit Siap Print

    56/253

    Latihan

    1. Show that the hypotheses It is not sunny this afternoon and it iscolder than yesterday, We will go swimming only if it is sunny, Ifwe do not go swimming, then we will take a canoe trip, If we takea canoe trip, then we will be home by sunset lead to the conclusionWe will be home by sunset.

    2. Show that hypotheses If you send me an email message, then I will

    finish writing the program, If you do not send me an emailmessage, then I will go to sleep early, If I go to sleep early, then Iwill wake up feeling refreshed lead to the conclusion If I do notfinish writing the program then I will wake up feeling refreshed.

    56

  • 8/4/2019 Matematika Diskrit Siap Print

    57/253

    Predikat

    Pernyataan yg melibatkan variabel, seperti x>3,x=y+3, dan x+y=z sering ditemukan dalam ilmumatematika dan komputer.

    Pernyataan tsb blm memiliki nilai kebenaran jika nilai

    dari variabelnya belum didefinisikan.

    Pernyataan x lebih besar dari 3 memiliki 2 bagian:

    Bag. 1: variabel x itu sendiri, yg merupakan subjek daripernyataan

    Bag 2: predikat, lebih besar dari 3, yg mengacu pada sifatyg dapat dimiliki oleh subjek pernyataan

    57

  • 8/4/2019 Matematika Diskrit Siap Print

    58/253

    Propotional Function

    Pernyataan x lebih besar dari 3 dapat dinyatakandgn P(x), dimana P merupakan predikat lebih besardari 3 dan x adalah variabel.

    P(x) juga dapat dikatakan sebagai propotional

    function P pada x. Jika x sudah diberikan sebuah nilai, maka P(x)

    menjadi sebuah proposisi dan memiliki nilaikebenaran.

    x dapat juga merupakan anggota dari sebuahhimpunan domain (daerah asal) D.

    58

  • 8/4/2019 Matematika Diskrit Siap Print

    59/253

    Propotional Function

    Contoh:

    Misal P(x) menyatakan x >3. Bagaimana nilai

    kebenaran untuk P(4) dan P(2)?

    Jawab:

    P(4) x = 4 shg pernyataannya menjadi 4 >3, nilai

    kebenarannya adalah BENAR

    P(2) x = 2 shg pernyataannya menjadi 2>3, nilaikebenarannya adalah SALAH

    59

  • 8/4/2019 Matematika Diskrit Siap Print

    60/253

    Propotional Function

    Propotional function juga dapat melibatkan lebih dari 1

    variabel.

    Contoh: pernyataan x = y + 3 dapat dinyatakan dengan

    Q(x,y) dimana x dan y adalah variabel dan Q adalah

    predikat.

    Nilai kebenaran dari Q(1,2) adalah SALAH dan nilai

    kebenaran dari Q(3,0) adalah BENAR

    60

    Propotional Function

  • 8/4/2019 Matematika Diskrit Siap Print

    61/253

    Propotional Function

    dengan daerah Domain

    Contoh:

    P(x): x adalah bilangan ganjil; x D

    D = himpunan bilangan bulat positif

    Jika x = 1, maka P(1) bernilai BENAR

    Jika x = 2, maka P(2) bernilai SALAH

    Jika x = 3, maka P(3) bernilai BENAR

    dst.

    61

  • 8/4/2019 Matematika Diskrit Siap Print

    62/253

    Universal Quantor

    Misalkan P adalah fungsi proposisi dengan daerah asal D.

    dibaca untuk setiap x, P(x)

    merupakan kuantor universal, dan dibaca untuk setiapatau untuk semua

    Pernyataan bernilai BENAR jika berlaku untuk semuax pada domain D.

    Pernyataan bernilai SALAH jika berlaku hanya padasebagian x pada domain D.

    )x(P,x

    )x(P,x

    62

    )x(P,x

  • 8/4/2019 Matematika Diskrit Siap Print

    63/253

    Universal Quantor

    Contoh 1:

    Tulislah pernyataan berikut dengan simbol

    universal quantor: Untuk setiap x, x2 0

    Jawab:

    P(x) : x2 0, maka:

    63

    0x,x 2

  • 8/4/2019 Matematika Diskrit Siap Print

    64/253

    Universal Quantor

    Contoh 2:

    Tulislah pernyataan berikut dengan simbol

    universal quantor: Untuk semua x, jika x > 1,

    maka x2> 1

    Jawab:

    P(x): x > 1 x2 > 1, maka:

    64

    1x1x,x 2

  • 8/4/2019 Matematika Diskrit Siap Print

    65/253

    Universal Quantor

    Contoh 3:

    Misal P(x): x + 1 > x

    Bagaimana nilai kebenaran dari

    dimana domainnya adalah semua bilangan real?Jawab:

    D = himp. Bil real. Karena P(x) benar untuk semuabilangan real x, maka

    bernilai BENAR

    )x(P,x

    )x(P,x

    65

  • 8/4/2019 Matematika Diskrit Siap Print

    66/253

    Universal Quantor

    Contoh 4:

    Misal P(x): x < 2. Bagaimana nilai kebenaran dari

    untuk domain semua bilangan real?

    Jawab:P(x) tidak benar untuk setiap bilangan real x, karena

    (misal) untuk x=3, maka P(x) SALAH. Sehingga

    bernilai SALAH

    )x(P,x

    )x(P,x

    66

  • 8/4/2019 Matematika Diskrit Siap Print

    67/253

    Existential Quantor

    Misalkan P adalah fungsi proposisi dengan daerah asalD.

    dibaca untuk beberapa x, P(x)

    merupakan kuantor eksistensial, dan dibaca untukbeberapa, ada, atau setidaknya ada.

    Pernyataan bernilai BENAR jika berlaku untuksetidaknya salah satu x dari domain D.

    Pernyataan bernilai SALAH jika tidak ada ygberlaku dari domain D.

    )x(P,x

    )x(P,x

    67

    )x(P,x

  • 8/4/2019 Matematika Diskrit Siap Print

    68/253

    Existential Quantor

    Contoh 1:

    Tuliskan pernyataan berikut dengan simbol

    kuantor eksistensial: Untuk beberapa x, x2

    0

    Jawab:

    P(x): x2 0, maka

    68

    0x,x 2

  • 8/4/2019 Matematika Diskrit Siap Print

    69/253

    Existential Quantor

    Contoh 2:

    Tuliskan pernyataan berikut dengan simbol

    kuantor eksistensial: Untuk setidaknya satu x,

    jika x>1, maka x2>1

    Jawab:

    P(x): x>1 x2>1, maka:

    69

    1x1x,x 2

  • 8/4/2019 Matematika Diskrit Siap Print

    70/253

    Existential Quantor

    Contoh 3:

    Misal P(x): x > 3. Bagaimana nilai kebenaranpada domain semua bilangan real?

    Jawab:P(x) bernilai benar untuk beberapa nilai x,misal 4 dan 5. Sehingga bernilai

    BENAR

    )x(P,x

    )x(P,x

    70

    l

  • 8/4/2019 Matematika Diskrit Siap Print

    71/253

    Existential Quantor

    Contoh 4:

    Misal P(x): x2 < 0. Bagaimana nilai kebenaran

    untuk domain semua bilangan real?

    JAWAB:Pernyataan tersebut SALAH, karena untuk semua x,

    adalah salah bahwa kuadrat x bernilai negatif.

    )x(P,x

    71

  • 8/4/2019 Matematika Diskrit Siap Print

    72/253

    Negasi dari Quantor

    ~( )

    ~( )

    Contoh:

    Tentukan negasi dari: Semua manusia memiliki

    orangtua Tentukan negasi dari:Ada orang Indonesia yang tidak

    suka gado-gado

    )x(P,x

    )x(P,x

    72

    )(~, xPx

    )(~, xPx

    K G d

  • 8/4/2019 Matematika Diskrit Siap Print

    73/253

    Kuantor Ganda

    Contoh :

    Untuk setiap orang x, terdapat seorang y sedemikian

    hingga y adalah ibu dari x.

    Jawab :

    x"dariibuadalahy":y)P(x,y),P(x,y)x)((

    73

    K G d

  • 8/4/2019 Matematika Diskrit Siap Print

    74/253

    Kuantor Ganda

    Contoh :

    Terdapat seorang y sehingga untuk semua orang x, y

    adalah ibu dari x.

    Jawab :

    x"dariibuadalahy":y)P(x,dimanay),P(x,x)y)((

    74

  • 8/4/2019 Matematika Diskrit Siap Print

    75/253

    y)P(x,y)x)((y)P(x,y)x)((

    y)P(x,y)x)((y)P(x,y)x)((

    :Ingkaran

    y)P(x,x)y)((y)P(x,y)x)((

    y)P(x,x)y)((y)P(x,y)x)((

    y)P(x,))((y)P(x,y)x)((

    :gandakuantorantarHubungan

    xy

    75

    C h

  • 8/4/2019 Matematika Diskrit Siap Print

    76/253

    Contoh

    Apakah ingkaran kalimat berikut :

    a.

    b.

    P.kanmenyelesaidapat

    tidakCC)komputerprogramP)(masalah(

    2knkbulatbilangannbulatbilangan

    P.kanmenyelesai

    dapatCC)komputerprogramP)(masalah(b.

    2knkbulatbilangannbulatbilangana.

    :Jawab

    76

  • 8/4/2019 Matematika Diskrit Siap Print

    77/253

    Latihan

    1. Ubahlah ke ekspresi logika predikata.Setiap mhs dalam kelas ini telah mengambilKalkulus I.

    b.Semua orang Indonesia makan pecel lele.

    c.x+y = y+x berlaku untuk semua bilangan real x dan y.

    d.Untuk setiap x ada nilai y sehingga x+y = 0.

    e.Untuk setiap x, y dan z berlaku hukum asosiatif x+(y+z) =(x+y)+z.

    2. Cari negasi dari ekspresi logika predikat hasil no.1lalu ubahlah kedalam kalimat.

    77

  • 8/4/2019 Matematika Diskrit Siap Print

    78/253

    Latihan

    3.Artikan kalimat ini dalam bhs Indonesia:bila C(x) : x mempunyai komputer,

    F(x,y): x dan y berteman,

    dan domainnya adalah semua mhs di kampus.

    a. x (C(x) y ( C(y) F(x,y))),

    b. xy z((F(x,y) F(x,z) (y z) F(y,z))

    c. x y (xy=1)

    78

  • 8/4/2019 Matematika Diskrit Siap Print

    79/253

    ARGUMEN & METODE PEMBUKTIAN

    Argumen adalah suatu deret proposisi yang dituliskansebagai :

    p1

    p2

    p3

    .

    pn----------

    p1, p2, , pn disebut hipotesis (premis) dan p disebutkonklusi.

    79

    p

  • 8/4/2019 Matematika Diskrit Siap Print

    80/253

    Inference Rule

    Universal

    Instantiation

    UniversalGeneralization

    Existensial

    Instantiation

    Existential

    Generalization

    celementsomeforcP

    xPx

    )(

    )(

    )(

    )(

    xPx

    carbitraryanforcP

    )(

    )(

    xPx

    carbitrarysomeforcP

    80

    )(

    )(

    cP

    xPx

    C h

  • 8/4/2019 Matematika Diskrit Siap Print

    81/253

    Contoh

    Diketahui premis Everyone in this discrete

    mathematics class has taken a course in

    computer science and Marla is a student in

    this class Apakah benar konklusinya adalahMarla has taken a course in computer

    science

    81

    S l i

  • 8/4/2019 Matematika Diskrit Siap Print

    82/253

    Solusi

    Misal :

    P(x) : x is in this discrete mathematics class

    Q(x) : x has taken a course in computer science

    Maka logika kuantor dari premis diatas :

    )(?

    )(

    ))()((

    MarlaQkonklusi

    MarlaP

    xQxPx

    82

    I f R l

  • 8/4/2019 Matematika Diskrit Siap Print

    83/253

    Inference Rule

    )(

    )(

    )()(.2)()(

    ))()((.1

    MarlaQ

    MarlaP

    MarlaQMarlaPMarlaQMarlaP

    xQxPx

    83

    Premise

    Universal InstantiationHasil (1)Premise

    Modus Ponen

  • 8/4/2019 Matematika Diskrit Siap Print

    84/253

    III. METODE PEMBUKTIAN

    84

    I d k i ik

  • 8/4/2019 Matematika Diskrit Siap Print

    85/253

    Induksi matematika

    merupakan teknik pembuktian yang sangat penting

    dipergunakan secara luas untuk membuktikan

    pernyataan yang berkaitan dengan obyek diskrit.

    (kompleksitas algoritma, teorema mengenai graf,identitas dan ketidaksamaan yang melibatkan

    bilangan bulat, dsb).

    tidak dapat digunakan untuk menemukan rumus

    atau teorema, tetapi hanya untuk melakukan

    pembuktian.

    85

    Berapakah jumlah dari n bilangan ganjil positif

  • 8/4/2019 Matematika Diskrit Siap Print

    86/253

    Berapakah jumlah dari n bilangan ganjil positif

    pertama?

    1 = 1

    1 + 3 = 4

    1 + 3 + 5 = 9

    1 + 3 + 5 + 7 = 16

    1 + 3 + 5 + 7 + 9 = 25

    Tebakan:

    Jumlah dari n bilangan ganjil positif pertama adalah n2.

    Metoda apa yang dapat dipakai untuk membuktikan bahwa

    tebakan ini benar, jika memang pada kenyataannya benar?

    86

    Induksi matematika

  • 8/4/2019 Matematika Diskrit Siap Print

    87/253

    Induksi matematika

    Suatu bukti dengan menggunakan induksi matematika bahwa P(n) benaruntuk setiap n bilangan bulat positif

    terdiri dari tiga langkah:

    1. Langkah basis:

    Tunjukkan bahwa P(1) benar.

    2. Langkah induktif:

    Tunjukkan bahwa P(k) P(k + 1) benar untuk setiap k.P(k) untuk suatu k tertentu disebut hipotesa induksi.

    3. Konklusi:n P(n) bernilai benar.

    87

    Teknik untuk membuktikan proposisi dalam bentukn P(n),

    dengan semesta pembicaraan adalah himpunan bilangan bulatpositif.

    Berapakah jumlah dari n bilangan ganjil positifpertama?

  • 8/4/2019 Matematika Diskrit Siap Print

    88/253

    pertama?

    Tebakan:

    Jumlah dari n bilangan ganjil positif pertama adalah n2

    .

    88

    Bukti:

    Misalkan P(n): proposisi Jumlah dari n bilangan ganjil positif

    pertama adalah n2.

    1. Langkah basis:

    P(1) benar, karena 1 = 12.

    2. Langkah induktif:

    Asumsikan bahwa P(k) benar untuk semua k, yaitu

    1 +3 + 5 + + (2k-1) = k2.Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu

    1 +3 + 5 + + (2k-1) + (2k+1) = (k+1)2.

    1 +3 + 5 + + (2k-1) + (2k+1) = k2 + (2k+1)

    = (k+1)2

    Berapakah jumlah dari n bilangan ganjil positif

  • 8/4/2019 Matematika Diskrit Siap Print

    89/253

    p j g g j p

    pertama?

    3. Konklusi:

    Jumlah dari n bilangan ganjil positif pertama adalahn2.

    Akhir dari bukti.

    89

    ContohGauss 1 + 2 + + n = n (n + 1)/2

  • 8/4/2019 Matematika Diskrit Siap Print

    90/253

    Gauss. 1 + 2 + + n = n (n + 1)/2

    Bukti.

    Misalkan P(n): proposisi 1 + 2 + + n = n (n + 1)/2

    1. Langkah basis:Untuk n = 1 diperoleh peroleh 1 = 1. Jadi, P(1) benar.

    2. Langkah induktif:

    Asumsikan bahwa P(k) benar untuk semua k, yaitu

    1 + 2 + + n = n (n + 1)/2

    Akan ditunjukkan bahwa P(k + 1) benar, yaitu1 + 2 + + k + (k + 1) = (k + 1) ((k + 1) + 1)/2

    Dari 1 + 2 + + k = k (k + 1)/2, diperoleh

    1 + 2 + + k + (k + 1) = k (k + 1)/2 + (k + 1)

    = (2k + 2 + k (k + 1))/2

    = (2k + 2 + k2 + k)/2= (2 + 3k + k2 )/2

    = (k + 1) (k + 2)/2

    = (k + 1) ((k + 1) + 1)/2

    90

    Contoh

  • 8/4/2019 Matematika Diskrit Siap Print

    91/253

    3. Konklusi:

    Jadi 1 + 2 + + n = n (n + 1)/2 benar untuk setiap

    nN.Akhir dari bukti.

    91

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    92/253

    Latihan

    1.Buktikan bahwa n3-n dapat dibagi 3 untuk n bilanganbulat positif.

    2.Buktikan :

    1+2+22

    ++2n

    =2n+1

    -1untuk semua bilangan bulat positif.

    3. Buktikan 22n-1 habis dibagi 3 untuk semua bil.bulat

    n1

    4.

    n

    i

    ni

    riilbilrbulatbilsemuauntukr

    rr

    0

    1

    1.0.1

    1

    92

    Metode Pembuktian

  • 8/4/2019 Matematika Diskrit Siap Print

    93/253

    Contoh Penyangkal (Counter Example).

    Tunjukkan bahwa pernyataan

    setiap bilangan bulat positif adalah hasil tambah dari tigabilangan kuadrat

    adalah salah.

    Solusi. Pernyataan ini benar untuk beberapa nilai, mis.

    1=02+02+12; 2=02+12+12 ; 3=12+12+12 ; 4=02+02+22 ;5=02+12+22 ; 6=12+12+22 .

    Tapi kita tidak dapat mengekspresikan seperti di atas untukbilangan 7.

    Jadi bilangan 7 merupakan contoh penyangkal daripernyataan di atas.

    93

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    94/253

    Latihan

    Tunjukkan bahwa jika segitiga siku-siku RSTdengan sisi tegak r, s, dan sisi miring tmempunyai luas t2/4, maka segitiga tersebutsama kaki.

    Buktikan bahwa jika n bulat dan tidak habisdibagi oleh 2 atau 3 maka n2 1 habis dibagi24.

    Tunjukkan bhw tidak ada solusi bulat x dany yang memenuhi x2 + 3y2 =8.

    94

  • 8/4/2019 Matematika Diskrit Siap Print

    95/253

    IV. PERMUTASI DAN

    KOMBINASI

    95

    Prinsip Perkalian

  • 8/4/2019 Matematika Diskrit Siap Print

    96/253

    Prinsip Perkalian

    Jika sebuah aktivitas bisa dibentuk dalam tlangkah berurutan dan langkah 1 bisa

    dilakukan dalam n1 cara; langkah kedua bisa

    dilakukan dalam n2cara; .; langkah tbisadilakukan dalam nt cara, maka banyaknya

    aktivitas berbeda yang mungkin adalah

    n1.n2.nt.

    96

    Prinsip Perkalian

  • 8/4/2019 Matematika Diskrit Siap Print

    97/253

    Prinsip Perkalian

    Contoh 1:Sebuah panitia yang terdiri dari enam orang terdiri dari Ali,Budi, Cokro, Dewi, Edi, dan Franky akan memilih seorangketua, sekretaris, dan bendahara. Ada berapa banyak carapemilihan ini bisa dilaksanakan ?

    Jawab:Pemilihan dilakukan dgn 3 langkah berurutan:

    1. Memilih ketua (ada 6 cara) n12. Memilih sekretaris (ada 5 cara) n23. Memilih bendahara (ada 4 cara) n

    3

    Total ada n1 x n2 x n3 = 6 x 5 x 4 = 120 cara

    97

    Prinsip Perkalian

  • 8/4/2019 Matematika Diskrit Siap Print

    98/253

    Prinsip Perkalian

    Contoh 2:Kursi di sebuah auditorium akan diberi nomor yangterdiri dari 1 huruf dan sebuah bil integer positif ygtidak melebihi 100. Ada berapa kursi yang dapat

    dilabeli dgn nomor yg berbeda?Jawab:

    1. Memilih huruf (ada 26 cara)

    2. Memilih angka (ada 100 cara)

    Total ada 26 x 100 = 2600 nomor berbeda yg dapatdigunakan untuk melabeli kursi

    98

    Prinsip Perkalian

  • 8/4/2019 Matematika Diskrit Siap Print

    99/253

    Prinsip Perkalian

    Contoh 3:Ada berapa banyak plat nomor kendaraan bermotor di Surabaya yg dapatdibuat jika nomor terdiri dari huruf L, diikuti dgn 4 digit angka, dan 2 hurufbelakang?

    Jawab:

    1. Memilih huruf pertama L (1 cara)

    2. Memilih digit angka I (9 cara)3. Memilih digit angka II (10 cara)

    4. Memilih digit angka III (10 cara)

    5. Memilih digit angka IV (10 cara)

    6. Memilih huruf belakang I (26 cara)

    7. Memilih huruf belakang II (26 cara)Total ada 26.26.9.10.10.10 = 6.084.000 plat nomor

    99

  • 8/4/2019 Matematika Diskrit Siap Print

    100/253

    Prinsip Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    101/253

    Prinsip Penjumlahan

    Jika aktivitas pertama dapat dilakukan dalamn1 cara, aktivitas kedua dengan n2cara, , dan

    aktivitas ke-t dengan nt cara, dan jika aktivitas2

    ini tidak dapat dilakukan pada waktu ygbersamaan, maka ada n1 + n2+ + nt cara

    untuk melakukan aktivitas tersebut

    101

    Prinsip Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    102/253

    Prinsip Penjumlahan

    Contoh 1:Mengacu pada Contoh 1 sebelumnya, ada berapa banyak carapemilihan ini bisa dilaksanakan apabila Ali atau Budi harus menjadiketua ?

    Jawab:

    Jika Ali sebagai ketua, maka sekretaris bisa dipilih dalam 5 cara.

    Setelah pemilihan ketua dan sekretaris, bendahara bisa dipilih dalam4 cara. Oleh karena, apabila Ali sebagai ketua jumlah total darikemungkinan untuk memilih pengurus yang lain adalah 5.4 = 20 cara.

    Jika Budi sebagai ketua jumlah total dari kemungkinan untuk memilihpengurus yang lain adalah 5.4 = 20 cara

    Karena kedua kasus saling lepas, menurut prinsip penjumlahan,terdapat 20 + 20 = 40 cara pemilihan pengurus bisa dilaksanakanapabila Ali atau Budi harus menjadi ketua.

    102

    Prinsip Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    103/253

    Prinsip Penjumlahan

    Contoh 2:Misal akan dipilih satu orang perwakilan anggotapengurus himajur dari 15 laki-laki dan 17perempuan untuk menghadiri rapat di fakultas.

    Ada berapa macam cara untuk memilih perwakilantersebut?

    Jawab:

    1. Memilih anggota dari 15 laki-laki 15 cara

    2. Memilih anggota dari 17 perempuan 17 caraMaka ada 15 + 17 = 32 cara untuk memilih

    perwakilan

    103

    Prinsip Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    104/253

    Prinsip Penjumlahan

    Contoh 3:Seorang mhs dapat memilih sebuah topik tugas akhirdari salah satu daftar dari 3 daftar judul ygdisediakan. Ketiga daftar tsb masing2 memiliki 23,

    15, dan 19 topik tugas akhir. Ada berapa banyak topikyg dapat dipilih?

    Jawab:

    Dari daftar I dapat dipilih 23 topik

    Dari daftar II dapat dipilih 15 topikDari daftar III dapat dipilih 19 topik

    Maka ada 23 + 15 + 19 = 57 topik yg dapat dipilih

    104

    Contoh Perkalian & Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    105/253

    Contoh Perkalian & Penjumlahan

    Contoh 4:Sebuah password komputer terdiri dari 6 s.d. 7 karakter, dimana tiapkarakter dapat berupa huruf besar atau sebuah digit angka. Password tsbminimal memiliki 1 digit angka. Ada berapa banyak kombinasi password?

    Jawab:

    Misal: P6 = jumlah total pwd yg terdiri dr 6 kar

    P7 = jumlah total pwd yg terdiri dr 7 karP: jumlah total pwd yg terdiri dari 6 atau 7 kar = P6 + P7Utk P6 & P7: jumlah pwd yg terdiri dari huruf dan setidaknya 1 digit angka =

    jumlah pwd keseluruhan jumlah pwd tanpa digit angka

    P6 = (26+10)6 266 = 1.867.866.560

    P7 = (26+10)7 267 = 70.332.353.920

    P = P6 + P7 = 72.200.220.480 kemungkinan password

    105

    Contoh Perkalian & Penjumlahan

  • 8/4/2019 Matematika Diskrit Siap Print

    106/253

    Contoh Perkalian & Penjumlahan

    Contoh 5:

    Misal dalam sebuah rak ada 4 buku

    Matematika yg berbeda, 3 buku Biologi yg

    berbeda, & 2 buku Fisika yg berbeda. Berapabanyak cara 2 buku dengan bidang yg berbeda

    bisa dipilih dari rak tersebut?

    106

    Permutasi

  • 8/4/2019 Matematika Diskrit Siap Print

    107/253

    Permutasi

    Permutasi menggunakan prinsip perkalian Permutasi dari n unsur yang berbeda x1, x2, ,

    xn adalah sebuah pengurutan dari n unsur x1,

    x2, , xn. Permutasi MEMPERHATIKAN urutan objek yg

    disusun

    Banyaknya permutasi dari n unsur = n!

    107

    Permutasi

  • 8/4/2019 Matematika Diskrit Siap Print

    108/253

    Permutasi

    Contoh:

    Hitung banyaknya permutasi dari 3 huruf A, B,

    C

    Tuliskan semua permutasi A, B, C

    Jawab:

    - n =3, maka permutasi = n! = 3! = 6

    - ABC, ACB, BAC, BCA, CAB, CBA

    108

    Permutasi r dari n unsur

  • 8/4/2019 Matematika Diskrit Siap Print

    109/253

    Permutasi r dari n unsur

    Contoh di atas mengasumsikan bahwa yg dipermutasikanadalah seluruh n.

    Permutasi r dari n mempermutasikan r

    (r n) dari n unsur yang ada.

    P(n,r) = Banyaknya permutasi-r dari sebuah himpunan dariobjek-objek yang berbeda

    109

    )!(

    !

    ),( rn

    n

    rnP

    Permutasi r dari n unsur

  • 8/4/2019 Matematika Diskrit Siap Print

    110/253

    Permutasi r dari n unsur

    Contoh 1:

    Ada berapa cara untuk memilih juara I, II, dan

    III dari 100 orang yg mengikuti sebuah lomba?

    Jawab:

    n = 100 r = 3

    P(100,3) = 100.99.98 = 970.200 cara

    110

    Permutasi r dari n unsur

  • 8/4/2019 Matematika Diskrit Siap Print

    111/253

    Permutasi r dari n unsur

    Contoh 2:Misal seorang sales akan mengunjungi 8 kota ygberbeda satu-persatu. Ia harus mulai dari 1 kotatertentu, tetapi setelah itu bebas untuk memilih rute

    ke 7 kota lainnya. Ada berapa kemungkinan rute?Jawab:

    Jumlah kota yg dipermutasikan = 7

    Jumlah rute = 7! = 5040 rute

    111

    Permutasi r dari n unsur

  • 8/4/2019 Matematika Diskrit Siap Print

    112/253

    Permutasi r dari n unsur

    Contoh 3:

    Ada berapa banyak permutasi dari huruf ABCDEFGH

    yang terdiri dari substring ABC?

    Jawab:Krn ABC harus muncul sebagai 1 kesatuan, maka

    jumlah yg dipermutasikan = 6 (ABC, D, E, F, G, H)

    Jumlah permutasi = 6! = 720 permutasi

    112

    Generalisasi Permutasi

  • 8/4/2019 Matematika Diskrit Siap Print

    113/253

    Generalisasi Permutasi

    Teorema: Misal X adalah barisan yg memiliki nunsur, dimana ada n1 unsur yg sama untuk

    jenis 1, n2 unsur yg sama untuk jenis 2, dst

    sampai ntunsur yg sama utk jenis t.Banyaknya permutasi dari X:

    113

    !!...!!

    21 tnnnn

    Generalisasi Permutasi

  • 8/4/2019 Matematika Diskrit Siap Print

    114/253

    Generalisasi Permutasi

    Contoh:Ada berapa permutasi dari kata MASSACHUSETTS?

    Jawab:

    Jumlah huruf: 13

    Jumlah M: n1 = 1 Permutasi

    Jumlah A: n2

    = 2

    Jumlah S: n3 = 4

    Jumlah C: n4 = 1

    Jumlah H: n5 = 1

    Jumlah U: n6 = 1

    Jumlah E: n7 = 1

    Jumlah T: n8 = 2

    114

    64.864.800

    96

    8006.227.020.!2!1!1!1!1!4!2!1

    !13

  • 8/4/2019 Matematika Diskrit Siap Print

    115/253

    Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    116/253

    Kombinasi

    Contoh 1:a. Hitunglah banyaknya kombinasi 2 dari tiga huruf

    A, B, dan C.

    b. Daftarlah kombinasi 2 dari tiga huruf A, B, dan C.Jawab:

    a. n = 3 r = 2

    C(3,2) = 3!/(3-2)!2! = 3b. AB, AC, BC

    116

    Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    117/253

    Kombinasi

    Contoh 2:Ada berapa cara untuk memilih 5 pemain dari10 orang pemain tenis untuk mengikuti

    lomba?Jawab:

    n = 10 r = 5

    C(10,5) = 10!/5!5! = 252Ada 252 cara untuk memilih 5 pemain

    117

    Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    118/253

    Kombinasi

    Contoh 3:Ada berapa banyak cara untuk membentuk suatu kelompokbelajar Mat Diskrit jika anggota kelompok tsb terdiri dari 3mhs jur TF dan 4 mhs jur SI, jika ada 9 mhs TF dan 11 mhs SI?

    Jawab:

    Langkah 1: Memilih 3 mhs TF dari 9 C(9,3)Langkah 2: Memilih 4 mhs SI dari 11C(11,4)

    118

    caraTotal

    xTotal

    CxCTotal

    LangkahxLangkahTotal

    720.27

    !7!4

    !11

    !6!3

    !9

    )4,11()3,9(

    21

    Generalisasi Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    119/253

    Generalisasi Kombinasi

    Merupakan perluasan dari kombinasi ygmembolehkan pengulangan suatu unsur.

    Teorema: Jika X merupakan sebuah himpunan

    yg mempunyai tjenis unsur dimanapengulangan dibolehkan, maka banyaknya

    seleksi kunsur tak berurut dari X adalah:

    C(k+t-1, t-1) = C(k+t-1, k)

    119

    Generalisasi Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    120/253

    Generalisasi Kombinasi

    Contoh 1:

    Ada berapa cara untuk memilih 4 kelereng dari

    sebuah kantong yg berisi sedikitnya 4 kelereng

    dari 3 jenis warna merah, biru, dan kuning?Jawab:

    jenis warna kelereng: t = 3

    banyaknya kelereng yg dipilih: k = 4Banyaknya cara: C(4+3-1, 4-1) = C(6,3) = 20

    120

    Generalisasi Kombinasi

  • 8/4/2019 Matematika Diskrit Siap Print

    121/253

    Generalisasi Kombinasi

    Contoh 2:Sebuah toko kue memiliki 4 jenis kue ygberbeda. Ada berapa cara kita bisa megambil

    6 buah kue?Jawab:

    Jenis kue: t = 4

    Banyaknya kue yg diambil: k = 6Banyaknya cara = C(6+4-1, 4-1) = 84

    121

    Pigeonhole

  • 8/4/2019 Matematika Diskrit Siap Print

    122/253

    Pigeonhole

    Prinsip Pigeonhole: Jika ada m ekor merpatidan n buah sarang, dan m > n, maka

    setidaknya ada sarang yang berisi lebih dari 1

    merpati Secara umum:

    Jika ada k+1 atau lebih objek yang diletakkan

    dalam kkotak, maka setidaknya ada 1 kotakyang berisi 2 atau lebih objek

    122

    Prinsip Pigeonhole

  • 8/4/2019 Matematika Diskrit Siap Print

    123/253

    p g

    Dari 8 orang, setidaknya ada 2 orang yangmemiliki hari lahir yg sama

    Dari 13 orang, setidaknya ada 2 orang yg

    memiliki bulan lahir yg sama Dari 367 orang, setidaknya ada 2 orang yg

    lahir pada tgl & bulan yg sama

    123

    Prinsip Pigeonhole Umum

  • 8/4/2019 Matematika Diskrit Siap Print

    124/253

    p g

    Jika N objek ditempatkan pada k kotak, makaada setidaknya 1 kotak yang berisi setidaknya

    objek

    Contoh 1:Dari 100 orang, setidaknya ada

    yang lahir di bulan yang sama

    124

    kN/

    912/100

    Prinsip Pigeonhole Umum

  • 8/4/2019 Matematika Diskrit Siap Print

    125/253

    p g

    Contoh 2:Berapa jumlah mhs dlm kelas Mat Diskrit ygdibutuhkan untuk memastikan bahwa setidaknya 6mhs mendapat nilai yg sama, jika ada 5 kemungkinan

    nilai yaitu A, B, C, D, dan E?Jawab:

    k = 5 y = 6

    N = 26, dibutuhkan 26 mhs agar adaminimal 6 mhs dengan nilai yang sama

    125

    ykN /

    Prinsip Pigeonhole Umum

  • 8/4/2019 Matematika Diskrit Siap Print

    126/253

    p g

    Contoh 3:Tunjukkan bahwa jika 30 kamus dalam sebuahperpustakaan memiliki total jumlah halaman 61.327,maka salah satu kamus paling tidak memiliki 2045halaman.

    Jawab:

    pigeon: halaman N = 61.327

    pigeonhole: kamus k = 30

    Maka sebuah kamus setidaknya memilikiatau 2045 halaman

    126

    30/327.61

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    127/253

    1. Dalam sebuah kartu bridge lengkap, berapa macamcara untuk mengambil :

    a. sebuah jantung atau sebuah daun

    b. sebuah jantung atau kartu AS

    c. sebuah AS atau sebuah king

    d. sebuah kartu bernomor 2 hingga 10

    2. Misalkan 2 buah dadu yang berbeda warna (merah

    dan putih). Ada berapa macam cara untukmendapatkan jumlah angka 4 atau 8 ?

    127

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    128/253

    3. Jika dua dadu yang berbeda dilontarkan, adaberapa banyak kemungkinan angka yangmuncul? Bagaimana jika 5 dadu ? Bagaimanajika n dadu ?

    4. Berapa banyak bilangan yang terdiri dari 2atau 3 digit yang dapat dibentuk denganmenggunakan angka-angka 1, 3, 4, 5, 6, 8 dan

    9, jika perulangan tidak dibolehkan.

    128

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    129/253

    5. Suatu perusahaan mempunyai 5 orang karyawanlaki-laki dan 7 karyawan perempuan. Pimpinan

    perusahaan akan memilih 5 orang diantaranya untuk

    bersama-sama mengerjakan suatu proyek. Berapa

    banyak tim yang dapat ia bentuk apabila di dalamtim tersebut harus terdiri dari:

    a. 3 laki-laki dan 2 perempuan

    b. paling sedikit ada 1 karyawan laki-lakic. paling banyak ada 1 karyawan laki-laki

    129

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    130/253

    6. Sebuah grup terdiri dari 7 wanita dan 3 pria.Ada berapa macam cara berbaris yang

    mungkin dilakukan jika ketiga pria tersebut

    harus berdiri bersebelahan satu dengan yanglain.

    7. Berapa macam penyusunan berbeda yang

    dapat dilakukan pada huruf a,a,b,c?

    130

  • 8/4/2019 Matematika Diskrit Siap Print

    131/253

    I. HIMPUNAN

    131

    HIMPUNAN (SETS)

  • 8/4/2019 Matematika Diskrit Siap Print

    132/253

    ( )

    Himpunan: Sekumpulan obyek yangdisebut elemen/anggota himpunan

    Cara pendefinisian himpunan: { }

    Contoh: Himpunan mhs TF UPNV: A={Ani, Budi, Citra}

    Himp. Bil asli < 5: B = {1, 2, 3, 4}

    C = {x|x adalah integer positif atau nol}

    C= {0, 1, 2, 3, }

    132

    NOTASI HIMPUNAN

  • 8/4/2019 Matematika Diskrit Siap Print

    133/253

    anggota himpunanContoh: Ani A, 2 B

    himpunan bagian

    Contoh: D = {Budi, Citra}; D A { } atau himpunan kosong

    Ingat!!:

    133

    2}2{}{

    AAdanA

    Operasi pada Himpunan

  • 8/4/2019 Matematika Diskrit Siap Print

    134/253

    UNION (U)Diketahui himpunan :

    A={a, b};

    B={d, e};

    A U B = {a, b, d, e}

    BA

    BxAxSxBA |

    134

    Operasi pada Himpunan (2)

  • 8/4/2019 Matematika Diskrit Siap Print

    135/253

    INTERSECTION ()Diketahui himpunan :

    A={a, b, c};

    B={b, g, i}

    A B = {b}

    BA

    BxAxSxBA |

    135

    Operasi pada Himpunan (3)

  • 8/4/2019 Matematika Diskrit Siap Print

    136/253

    SELISIH(-)Diketahui himpunan :

    A={a, b, c};

    B={b, c, d, e}

    A-B={a}B-A={d, e}

    BA

    }|{ BxAxSxBA

    136

    Operasi pada Himpunan (4)

  • 8/4/2019 Matematika Diskrit Siap Print

    137/253

    SYMMETRIC DIFFERENCE ( )

    Diketahui himpunan :

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

    A B={b, d, e, f, g}

    BA

    137

    Operasi pada Himpunan (5)

  • 8/4/2019 Matematika Diskrit Siap Print

    138/253

    }|{ AxSxAc

    138

    KOMPLEMEN

    Diketahui himpunan :

    S={a, b, c, d, e, f, g};

    A={a, c, e, g}

    Ac={b, d, f}

    A

    S

    Properti Aljabar (Teorema 1)

  • 8/4/2019 Matematika Diskrit Siap Print

    139/253

    Komutatif1. A U B = B U A

    2. A B = B A

    Asosiatif

    3. A U (B U C) = (A U B) U C

    4. A (B C) = (A B) C

    139

    Properti Aljabar (2)

  • 8/4/2019 Matematika Diskrit Siap Print

    140/253

    Distributif5. A (B U C) = (A B) U (A C)

    6. A U (B C) = (A U B) (A U C)

    Idempotent

    7. A U A = A

    8. A A = A

    140

    Properti Aljabar (3)

  • 8/4/2019 Matematika Diskrit Siap Print

    141/253

    Komplemen - Universal Set

    16. A U S = S

    17. A S = A

    - Empty Set

    18. A U = A

    19. A =

    BABA

    BABA

    S

    S

    AA

    SAA

    AA

    .15

    .14

    .13

    .12

    .11

    )(.10

    )(.9

    141

    Himpunan Kuasa (Power Set)

  • 8/4/2019 Matematika Diskrit Siap Print

    142/253

    Misal A adalah sembarang himpunan. Power Set dariA (P(A)) adalah himpunan yang anggota2nya adalahsemua himpunan bagian dari A. Jika A memiliki nanggota, maka P(A) memiliki 2n anggota.

    Contoh:A = {x, y}. Carilah P(A)

    Himp2. bagian A adalah , {x}, {y}, {x, y}

    Maka P(A) = {, {x}, {y}, {x, y}}

    142

    Prinsip Inklusi dan Eksklusi

  • 8/4/2019 Matematika Diskrit Siap Print

    143/253

    Misal A adalah sebuah himpunan.|A| = Jumlah elemen pada himpunan A

    Teorema 2: |A U B| = |A| + |B| - |A B|

    Teorema 3:

    |AUBUC| = |A| + |B| + |C| - |AB| -

    |AC| - |BC| + |ABC|

    143

    Contoh

    Prinsip Inklusi dan Eksklusi

  • 8/4/2019 Matematika Diskrit Siap Print

    144/253

    Prinsip Inklusi dan Eksklusi

    1. A computer company wants to hire 25programmers to handle desktop applicationprogramming jobs and 40 programmers forweb application programming. Of those hired,

    10 will be expected to perform jobs of bothtypes. How many programmers must behired?

    144

    Contoh

    Prinsip Inklusi dan Eksklusi (2)

  • 8/4/2019 Matematika Diskrit Siap Print

    145/253

    Prinsip Inklusi dan Eksklusi (2)

    Jawab: Mis. A = himp. desktop programmer |A| = 25

    B = himp. web programmer

    |B| = 40

    |A B| = 10

    Maka jumlah programmer yang harus

    dipekerjakan: |AUB|=25+40-10 = 55

    145

    Contoh

    Prinsip Inklusi dan Eksklusi (3)

  • 8/4/2019 Matematika Diskrit Siap Print

    146/253

    Prinsip Inklusi dan Eksklusi (3)

    2. Pada Jur. TF, didapat informasi tentang jumlah mahasiswayang mengambil mata kuliah sebagai berikut:

    260 mahasiswa mengambil MK Statistik, 208 mengambilMK Kalkulus II, dan 160 mengambil MK Grafika. 76 mhsmengambil Statistik dan Kalkulus II; 48 mhs mengambil

    Statistik dan Grafika, 62 mengambil Kalkulus II dan Grafika.Ada 30 mhs yg mengambil ketiga MK tsb dan jumlah

    seluruh mahasiswa 622.

    a. Berapa mhs yg tidak mengambil ketiga MK tsb?

    b. Berapa mhs yg mengambil Statistik dan Kalkulus II,tetapi tidak mengambila Grafika?

    146

    Jawab :

  • 8/4/2019 Matematika Diskrit Siap Print

    147/253

    463076

    CBABACBAb.

    150472622CBA

    CBA472622

    CBA30624876160208260622

    CBA|CBA||CB|-|CA|-|BA|-|C||B||A|S

    CBACBASa.

    622||30,|CBA|62,|CB|48,|CA|76,|BA|

    160|C|Grafika,MKmhshimpC

    208|B|II,KalkulusMKmhshimpB

    260|A|Statistik,MKmhshimpA

    S

    147

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    148/253

    1. Nyatakan himpunan di bawah ini dalam notasi himpunana. A=himp bil bulat antara 1 dan 5

    b. B=himp yg anggotanya kucing, meja, buku, air

    c. himp bil riil yang lebih besar 1

    2. Tentukan apakah pernyataan berikut benar?

    1,2,32d.1,2,31,2,3g.1,2,32c.2,12f.1,2,32b.

    2,12e.1,2,32a.

    148

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    149/253

    3. Misalkan diantara 400 tamu-tamu yang datang, 200diantaranya bisa berbahasa Perancis dan 50 orang dapat

    berbahasa Belanda. Tamu yang bisa berbicara dalam kedua

    bahasa tersebut hanya 20 orang. Berapa banyak tamu yang

    tidak bisa berbicara dalam kedua bahasa tersebut?

    149

  • 8/4/2019 Matematika Diskrit Siap Print

    150/253

    V. RELASI DAN FUNGSI

    150

    Hasil Kali Kartesian

  • 8/4/2019 Matematika Diskrit Siap Print

    151/253

    Adalah himpunan semua pasangan berurutan (a,b) dengan

    Simbol : A x B

    Contoh :

    Misalkan himpunan A={a,b,c}; B={,,}; C={1,2,3}.Hitunglah A x B dan (A x B) x C !

    Penyelesaian :

    A x B = {(a,),(a,),(a, ),(b, ),(b, ),(b, ),(c, ),(c, ),(c, )}

    (A x B) x C = {((a,),1),((a,),1),((a, ),1),((b, ),1),((b, ),1),((b, ),1),((c, ),1),((c, ),1),((c, ),1), ((a,),2),((a,),2),((a, ),2),((b, ),2),((b, ),2),((b, ),2),((c, ),2),((c, ),2),((c, ),2), ((a,),3),((a,),3),((a, ),3),((b, ),3),((b, ),3),((b, ),3),((c, ),3),((c, ),3),((c, ),3)}

    BbdanAa

    BbA,aba,BxA

    151

    Relasi

  • 8/4/2019 Matematika Diskrit Siap Print

    152/253

    Hubungan antara anggota-anggota himpunan direpresentasikandengan menggunakan struktur yang disebut relasi.

    Untuk mendeskripsikan relasi antara anggota-anggota dua himpunan Adan B, dapat digunakan pasangan terurut dengan anggotapertamanya diambil dari A dan anggota keduanya diambil dari B.

    Karena ini merupakan relasi antara dua himpunan, maka disebutrelasi biner.

    Definisi.

    Misalkan A dan B himpunan.

    Suatu relasi binerdari A ke B adalah subhimpunan (subset) dari AB.

    Untuk relasi biner R berlaku R AB.

    Digunakan notasi aRb untuk menyatakan (a,b)R dan aRb untukmenyatakan (a,b)R.

    Jika (a, b) merupakan anggota R, a dikatakan berelasi dengan b olehR.

    152

    Contoh 1

  • 8/4/2019 Matematika Diskrit Siap Print

    153/253

    Misalkan O himpunan orang,

    A himpunan angkutan kota, danN relasi yang mendeskripsikan siapa yangmenaiki angkot tertentu.

    O = {Aang, Bida, Charlie, Dina},

    A = {Cicaheum-Ledeng (CL), Kelapa-Dago (KD), Stasiun-

    Sadang Serang (SS)}N = {(Aang, CL), (Bida, CL), (Bida, KD), (Charlie, SS)}

    Artinya Aang naik Cicaheum-Ledeng,

    Bida naik Cicaheum-Ledeng dan Kelapa-Dago,Charlie naik Stasiun-Sadang Serang, dan

    Dina tidak menaiki salah satu dari angkot tersebut.

    153

    Relasi pada Himpunan

  • 8/4/2019 Matematika Diskrit Siap Print

    154/253

    Definisi.

    Suatu relasipada himpunan A adalah relasi dari A ke A.

    Relasi pada himpunan A adalah subhimpunan (subset)

    dari AA.

    Contoh 2.

    Misalkan A = {1, 2, 3, 4}.

    Himpunan terurut manakah yang terdapat dalam relasi

    R = {(a, b) | a < b} ?

    Solusi.

    R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

    154

    Matriks Relasi

  • 8/4/2019 Matematika Diskrit Siap Print

    155/253

    Disebut juga matriks nol-satu

    Jika ,

    masing-masing terdiri dari m dan n elemen, dan R

    adalah relasi dari A ke B, maka R dapat ditulis dalam

    matriks mxn dimana :

    n21m21 b,,b,bBdana,,a,aA

    ][M ijR m

    155

    Rbajika

    Rbajika

    m ji

    ji

    ij ),(,0

    ),(,1

    Contoh 1

  • 8/4/2019 Matematika Diskrit Siap Print

    156/253

    156

    R 1 2 3 4

    1

    2

    3

    4

    1 1

    2

    3

    4

    2

    3

    4

    1 1 1

    1 1

    1

    R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

  • 8/4/2019 Matematika Diskrit Siap Print

    157/253

    Contoh 3

  • 8/4/2019 Matematika Diskrit Siap Print

    158/253

    0101

    0110

    1001

    RM 321 ,, aaaA

    4321 ,,, bbbbB

    331332224111 ,,,,,,,,,,,

    sehingga,1jikahanyadanjika,

    babababababaR

    mRba ijji

    158

    Misal matriks relasi R :

    Karena ordo matriks 3x4, maka

    dan

    Digraph Relasi

  • 8/4/2019 Matematika Diskrit Siap Print

    159/253

    Digraph (directed graph), terdiri dari vertex dan edge.

    Vertex melambangkan elemen pada himpunan Edge melambangkan relasi antara elemen yang satu dengan yang

    lainnya

    Contoh : Misal,

    maka digraph :

    1,4,4,3,4,2,3,2,2,2,1,2,2,1,1,14,3,2,1

    R

    A

    159

    1

    2

    3

    4

    Sifat Relasi - Refleksif

  • 8/4/2019 Matematika Diskrit Siap Print

    160/253

    Definisi.

    Relasi R pada himpunan A disebut refleksifjika(a,a)R untuk setiap anggota aA.

    Apakah relasi berikut pada {1, 2, 3, 4} refleksif?

    160

    R = {(1, 1), (1, 2), (2, 3), (3, 3), (4, 4)} Tidak.

    R = {(1, 1), (2, 2), (2, 3), (3, 3), (4, 4)} Ya.

    R = {(1, 1), (2, 2), (3, 3)} Tidak.

    Sifat Relasi - Simetris & Antisimetris

    Definisi.

  • 8/4/2019 Matematika Diskrit Siap Print

    161/253

    Apakah relasi berikut pada {1, 2, 3, 4} simetris atauantisimetris?

    161

    R = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)} simetris

    R = {(1, 1)} simetris &

    antisimetris

    R = {(1, 3), (3, 2), (2, 1)} antisimetris

    R = {(4, 4), (3, 3), (1, 4)} antisimetris

    Definisi.

    Relasi R pada himpunan A disebut simetris jika (b,a)Rsetiap kali (a,b)R untuk setiap a,bA.

    Relasi R pada himpunan A disebut antisimetris jika(a,b)R dan tidak ada (b,a)R, kecuali a = b.

    Sifat Relasi - Transitif

  • 8/4/2019 Matematika Diskrit Siap Print

    162/253

    Definisi.

    Relasi R pada himpunan A disebut transitifjika setiap kali(a,b)R dan (b,c)R, maka (a,c)R untuk a,b,cA.

    Apakah relasi berikut pada {1, 2, 3, 4} transitif?

    162

    R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} Ya.

    R = {(1, 3), (3, 2), (2, 1)} Tidak.

    R = {(2, 4), (4, 3), (2, 3), (4, 1)} Tidak.

    Sifat Matriks Representasi RelasiMatriks yang merepresentasikan relasi refleksif ?

  • 8/4/2019 Matematika Diskrit Siap Print

    163/253

    Matriks yang merepresentasikan relasi refleksif ?

    Setiap elemen diagonal dari matriks Mrefharuslah 1.

    163

    1

    .

    .

    .

    1

    1

    refM

    Matriks yang merepresentasikan relasi simetris?

    Matriksnya juga simetri, yaitu MR = (MR)t.

    1101

    10010010

    1101

    RM

    matriks simetri,

    relasi simetris.

    0011

    00110011

    0011

    RM

    matriks tak-simetri,

    relasi tak-simetris.

    Komposisi RelasiD fi i i

  • 8/4/2019 Matematika Diskrit Siap Print

    164/253

    Definisi.

    Misalkan R relasi dari A ke B dan S relasi dari Bke C. Komposisi dari R dan S adalah relasi yangmemuat himpunan terurut (a,c), dengan aA,cC, di mana terdapat anggota bB sehingga(a,b)R dan (b,c)S. Komposisi dari R dan Sdinotasikan oleh SR.Jika relasi R memuat pasangan (a, b) dan relasi

    S memuat pasangan (b,c), maka SR memuatpasangan (a,c).

    164

    Contoh 4

    Contoh

  • 8/4/2019 Matematika Diskrit Siap Print

    165/253

    Contoh.

    Misalkan D dan S relasi pada A = {1, 2, 3, 4}.D = {(a, b) | b = 5 - a} b sama dengan (5 a)

    S = {(a, b) | a < b} a lebih kecil dari b

    D = {(1, 4), (2, 3), (3, 2), (4, 1)}

    S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

    SD = {(2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}

    165

    D memetakan suatu anggota a ke anggota (5 a), dan setelah

    itu S memetakan (5 a) pada semua anggota yang lebih besardari (5 a), yang menghasilkan

    SD = {(a,b) | b > 5 a} atau SD = {(a,b) | a + b > 5}.

    Kuasa dari Relasi

  • 8/4/2019 Matematika Diskrit Siap Print

    166/253

    Definisi.

    Misalkan R relasi pada himpunan A.

    Kuasa Rn, n = 1, 2, 3, , didefinisikan secara induktif

    R1 = R

    Rn+1 = RnR

    Dengan kata lain:

    Rn = RR R (sebanyak n kali)

    Teorema.Relasi R pada A transitif jika dan hanya jika Rn R untuk setiapbilangan bulat positif n.

    166

    Contoh

  • 8/4/2019 Matematika Diskrit Siap Print

    167/253

    Misalkan A={a,b,c,d} dan R={(a,b),(b,c),(c,d)}.

    Maka kuasa dari R :

    R2= R o R = {(a,c),(b,d)}

    R3= R2 o R ={(a,d)}

    R4= R3 o R = { }

    NB TF-E : Adi (IK), Teguh, Bagus, Prasetyo Adhi

    167

    Irisan dan Gabungan

  • 8/4/2019 Matematika Diskrit Siap Print

    168/253

    Hakikatnya relasi merupakan himpunan.

    Contoh :

    Misal A={-1,0,1} dan B{0,1}. Relasi R dan S:

    Maka,

    {(-1,1)}SR

    (1,1)}(0,0),(0,1),(-1,1),{(-1,0),SR

    (-1,1)}(1,1),{(0,0),S

    (0,1)}(-1,1),{(-1,0),R

    168

    Misalkan relasi R dan S direpresentasikan

  • 8/4/2019 Matematika Diskrit Siap Print

    169/253

    Misalkan relasi R dan S direpresentasikan

    oleh matriks

    169

    011

    111

    101

    SRSR MMM

    001

    110

    101

    SM

    Apakah matriks yang merepresentasikan RS andRS?Solusi: Matriks-matriks tersebut adalah

    000

    000

    101

    SRSR MMM

    010

    001

    101

    RM

    Transitif Closure

  • 8/4/2019 Matematika Diskrit Siap Print

    170/253

    Merupakan relasi yang diperoleh dengan caramenambahkan anggota agar suatu relasi yang tidaktransitif menjadi transitif.

    1. Menggunakan kuasa relasiR+ = R u R2 u R3 u

    2. Algoritma Warshall

    170

    Contoh

    Misalkan A={a b c d} dan R={(a b) (b c) (c d)}

  • 8/4/2019 Matematika Diskrit Siap Print

    171/253

    Misalkan A={a,b,c,d} dan R={(a,b),(b,c),(c,d)}

    Maka kuasa dari R :R2= R o R = {(a,c),(b,d)}

    R3= R2 o R ={(a,d)}

    R4= R3 o R = { }

    R+ = R u R2 u R3 u R4

    = {(a,b),(b,c),(c,d)} u {(a,c),(b,d)} u {(a,d)} u { }= {(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}

    171

    Algoritma Warshall

  • 8/4/2019 Matematika Diskrit Siap Print

    172/253

    0 1 0 0

    0 0 1 0

    0 0 0 1

    0 0 0 0

    0 1 1 1

    0 0 1 1

    0 0 0 1

    0 0 0 0

    172

    Baris-1 (k) : {b}Kolom-1 (b) : {}A(b,k)={}

    0 1 0 0

    0 0 1 0

    0 0 0 1

    0 0 0 0

    Baris-2 (k) : {c}Kolom-2 (b) : {a}A(b,k)={(a,c)}

    0 1 1 0

    0 0 1 0

    0 0 0 1

    0 0 0 0

    0 1 1 1

    0 0 1 1

    0 0 0 1

    0 0 0 0

    Baris-3 (k) : {d}

    Kolom-3 (b) : {a,b}A(b,k)={(a,d),(b,d)}

    Baris-4 (k) : {}

    Kolom-4 (b) : {a,b,c}A(b,k)={}

    R = {(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}

    Fungsi

  • 8/4/2019 Matematika Diskrit Siap Print

    173/253

    Jika suatu relasi menghubungkan suatu himpunan Ake himpunan B dimana tiap anggota A memiliki

    TEPAT satu relasi dengan sembarang anggota B.

    Fungsi dari A ke B ditulis

    BbdanAauntukbaf ,)(

    173

    A B A B A B

    Contoh fungsi :

  • 8/4/2019 Matematika Diskrit Siap Print

    174/253

    174

    A B A B

    Contoh relasi yang bukan fungsi :

    A disebut DOMAIN, dan B disebut KODOMAIN. Elemen-elemen B yangberelasi dengan elemen A disebut RANGE (himpunan penyelesaian)

    Jenis fungsi - Injective

  • 8/4/2019 Matematika Diskrit Siap Print

    175/253

    INJECTIVE (one to one function)

    Jika tiap anggota dari domain memiliki range yang

    UNIK satu sama lain.

    Contoh injective : Contoh bukan injective :

    175

    A B A B

    Jenis fungsi - Surjective

  • 8/4/2019 Matematika Diskrit Siap Print

    176/253

    SURJECTIVE (Onto function)jika kodomain = range

    Contoh onto : Contoh bukan onto :

    176

    A BA B

    Jenis fungsi - Bijection

  • 8/4/2019 Matematika Diskrit Siap Print

    177/253

    BIJECTION (one to one correspondence)

    jika mempunyai sifat one to one dan onto

    Contoh :

    177

    A B

  • 8/4/2019 Matematika Diskrit Siap Print

    178/253

    VI. RELASI REKURENSI

    178

  • 8/4/2019 Matematika Diskrit Siap Print

    179/253

    INGAT !!!

    KONSEP REKURSIF

    179

    Konsep

  • 8/4/2019 Matematika Diskrit Siap Print

    180/253

    Suatu barisan yang didefinisikan secara rekursif jika kondisi

    awal barisan ditentukan, dan suku-suku barisan selanjutnya

    dinyatakan dalam hubungan dengan sejumlah suku-suku

    sebelumnya.

    Contoh :

    Barisan 3, 5, 7, 9, dapat dinyatakan sbb :

    )(2

    )(3

    1

    0

    rensirelasirekuaa

    lkondisiawaa

    kk

    180

    Contoh 1

  • 8/4/2019 Matematika Diskrit Siap Print

    181/253

    Suatu barisan co, c1, c2, didefiniskan secara rekursif.

    Untuk semua bilangan

    dengan kondisi awal c0=1 dan c1=2. Hitunglah c5 ?

    Solusi

    ,2k1. 21 kkk ckcc

    18194112.5331.5

    3315.4121.4

    1212.351.3

    511.221.2

    345

    234

    123

    012

    ccc

    ccc

    ccc

    ccc

    Contoh 2Menara Hanoi

    A B CA B

  • 8/4/2019 Matematika Diskrit Siap Print

    182/253

    Cara memindahkan k cakram dari tiang A ke C adalah sbb :1. pindahkan (k-1) cakram dari tiang A ke B

    2. pindahkan cakram paling bawah dari tiang A ke C

    3. pindahkan (k-1) cakram dari tiang B ke C

    Misalkan mn adalah jumlah minimal untuk memindahkan n cakram dari satu tiang

    ke tiang yang lain. Langkah 1 memerlukan mk-1 perpindahan, langkah 2

    memerlukan 1 perpindahan, dan langkah 3 memerlukan mk-1 perpindahan. Jadi

    jumlah keseluruhan perpindahan minimal :

    mk=mk-1+1+mk-1=2mk-1+1Sehingga didapatkan persamaan rekursif :

    m1=1 (kondisi awal)

    mk=2mk-1+1 (relasi rekurensi)

    182

    A B C

    m1=1 (kondisi awal)

    mk=2mk-1+1 (relasi rekurensi)

  • 8/4/2019 Matematika Diskrit Siap Print

    183/253

    Maka untuk memindahkan :

    - 2 cakram, dibutuhkan m2=2m1+1=2.1+1= 3

    - 3 cakram, dibutuhkan m3=2m2+1=2.3+1=7- 4 cakram, dibutuhkan m4=2m3+1=2.7+1=15

    183A B CA

    Penyelesaian relasi rekurensi

  • 8/4/2019 Matematika Diskrit Siap Print

    184/253

    Perhitungan dengan rekursif sangat memakanwaktu.

    Waktu running yang dibutuhkan akan jauhlebih lama dibandingkan dengan program

    non-rekursif.

    Menyelesaikan relasi rekurensi, ada 2 :

    Cara iterasi

    Melalui persamaan karakteristik

    184

    Metode 1 - Cara Iterasi

  • 8/4/2019 Matematika Diskrit Siap Print

    185/253

    Prinsip : hitung suku-suku barisan secaraberurutan terus menerus hingga diperoleh

    pola tertentu sebagai dasar pembuatan

    rumus eksplisit.

    185

    Pola Deret (barisan)

  • 8/4/2019 Matematika Diskrit Siap Print

    186/253

    )(1,1

    1.. .1

    3

    )2)(1()1(...4.33.22.1

    6)12)(1(...32

    2

    )1(...321

    12

    2222

    geometrideretruntukr

    rrrr

    nnnnn

    nnnna

    nnn

    nn

    186

    U-Ubdimana1)b,(naU

    AritmatikaDeret

    1

  • 8/4/2019 Matematika Diskrit Siap Print

    187/253

    1r;r)-(1

    )r-a(1Sn

    1r;

    1)-(r

    1)-a(rSn

    UUrdimana,arU

    GeometriDeret

    )U(a2

    nS

    UUbdimana1)b,(naU

    n

    n

    1

    n1-nn

    nn

    n1-nn

    n

    187

    Contoh 1

  • 8/4/2019 Matematika Diskrit Siap Print

    188/253

    Carilah rumus eksplisit, untuk semua bilangan bulat k1,

    Penyelesaian

    Berdasarkan pola yang ada, diperoleh rumus eksplisit :

    )(2

    )(1

    1

    0

    rekurensirelasiaa

    awalkondisia

    kk

    kkaa

    aaaaaa

    aaaaa

    aaaaaa

    k 212.

    2.4222)2(22)2(2)2(2

    2.322)2(2)2(2

    2.22)2(22

    0

    001234

    00123

    0012

    01

    188

    Contoh 2

    Carilah rumus eksplisit yang menyatakan masalah Hanoi.

  • 8/4/2019 Matematika Diskrit Siap Print

    189/253

    p y g y

    Penyelesaian.

    mk merupakan deret geometri dengan r=2 sehinggadiperoleh rumus eksplisit :

    1

    212

    1

    1

    m

    kbulatbilanganuntukmmkk

    1222...222

    12221)1)12(2(21)12(2121221)12(212

    1211.212

    123321

    123

    1234

    12

    123

    1

    12

    kkkkm

    mmmmmmm

    mm

    189

    1212

    12 1)1(

    k

    k

    km

    Metode 2 Persamaan Karakteristik

  • 8/4/2019 Matematika Diskrit Siap Print

    190/253

    Sebuah relasi rekurensi linier berkoefisienkonstan, secara umum ditulis sebagai berikut

    C0 an + C1 an-1 + C2 an-2+ + Ck an-k = f(n)

    dimana Ci, untuk i = 0,1,2,,k adalah

    konstanta dan f(n) adalah sebuah fungsinumerik dengan variabel n.

    Relasi rekurensi tersebut dikatakan relasi

    rekurensi linier berderajat k , jika C0 dan Ckkeduanya tidak bernilai 0 (nol).

    190

    Contoh :

  • 8/4/2019 Matematika Diskrit Siap Print

    191/253

    2 an + 2 an-1 = 3n

    adalah sebuah relasi rekurensi linier berderajat 1

    tn = 7 tn-1

    adalah sebuah relasi rekurensi linier berderajat 1

    an an-1 an-2 = 0

    adalah sebuah relasi rekurensi linier berderajat 2

    bn-3 3bn = n+3adalah sebuah relasi rekurensi linier berderajat 3

    191

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    192/253

    Tentukan apakah persamaan di bawah inimerupakan relasi linier dengan koefisien konstan

    an 7an-1 + 10an-2 = 0 YA

    bk = bk-1 + bk-2 + bk-3 YA

    ck = 2ck-2 YA dk = d

    2k-1 + dk-2 BUKAN

    ek = ek-1.ek-2 BUKAN f

    k 2f

    k-1+ 1 = 0 YA

    hk = -hk-1 +(k-1)hk-2 YA

    192

    Relasi rekurensi linier homogen dengan

    koefisien konstan

  • 8/4/2019 Matematika Diskrit Siap Print

    193/253

    Sebuah relasi rekurensi linier berkoefisien konstandapat dinyatakan dalam bentuk

    C0 an + C1 an-1+ + Ck an-k = f(n).

    Bila nilai f(n) = 0, maka diperoleh relasi rekurensi

    yang memenuhiC0 an + C1 an-1 + C2 an-2+ + Ck an-k = 0.

    Relasi rekurensi demikian disebut dengan relasirekurensi homogen dan solusi dari relasi rekurensi

    homogen ini dinamakan solusi homogen atau jawabhomogen.

    193

    Misalkan suatu relasi rekurensi homogen linier dengan koefisienkonstan :

    C0an + C1an-1 + C2an-2+ + Ckan-k = 0 dengan ck0 dan nk

    Persamaan karakteristik :

    tk tk 1 0

  • 8/4/2019 Matematika Diskrit Siap Print

    194/253

    tk + c1tk-1+ + ck =0

    Misalkan 1, 2, , k adalah akar-akar persamaan karakteristik. Ada 2kemungkinan akar :

    1. Semua akar berbeda

    an = c11n + c22

    n+ + ckkn

    dengan c1, c2, , ck adalah konstanta yang nilainya ditentukan

    berdasarkan kondisi awal.

    2. Ada akar kembar

    1=2=p, p+1, , kMaka penyelesaiannya :

    an = (c1 + c2n + + cpnp-1) 1n + cp+1p+1n, + + ckkndengan c1, c2, , ck adalah konstanta yang nilainya ditentukanberdasarkan kondisi awal

    194

    Contoh

  • 8/4/2019 Matematika Diskrit Siap Print

    195/253

    1. an = 3an-1 + 4an-2untuk n2 dengan kondisiawal a0=1 dan a1=3

    2. an 3an-1 + 3an-2 an-3= 0 untuk n3 dengankondisi awal a0=1, a1=2, a2=4

    3. an 7an-1 + 16an-2 12an-3= 0 untuk n3dengan kondisi awal a0=1, a1=4, a2=8

    195

    an = 3an-1 + 4an-2untuk n2 dengan kondisi

    awal a0=1 dan a1=3

    R l i 3 4 0 k l i k i h li i d

  • 8/4/2019 Matematika Diskrit Siap Print

    196/253

    Relasi an - 3an-1 - 4an-2 = 0 merupakan relasi rekurensi homogen linier dengan

    koefisien konstan c1=-3, c2=-4, derajat k=2. Persamaan karakteristik yang sesuaiadalah

    t2 3t 4 = 0

    (t-4)(t+1) = 0

    akar-akar pers. karakteristik 1=4, 2=-1. Karena semua akar berbeda, makapenyelesaiannya :

    an = c11n + c22n= c14n + c2(-1)n

    a0 =1 sehingga 1 = c140 + c2(-1)

    0

    1 = c1 + c2a1 =3 sehingga 3 = c14

    1 + c2(-1)1

    3 = 4c1 - c2

    Dari 2 persamaan tersebut dapat diperoleh c1=4

    /5 dan c2=1

    /5.Maka penyelesaian relasi rekurensi an - 3an-1 - 4an-2 = 0 adalah

    an =4/5 (4)

    n + 1/5 (-1)n

    196

    an 3an-1 + 3an-2 an-3= 0 untuk n3

    dengan kondisi awal a0=1, a1=2, a2=4

    R l i 3 3 0 k l i k i h li i

  • 8/4/2019 Matematika Diskrit Siap Print

    197/253

    Relasi an - 3an-1 + 3an-2 an-3 = 0 merupakan relasi rekurensi homogen linier

    dengan koefisien konstan c1=-3, c2=3, c3=-1, derajat k=3. Persamaankarakteristik yang sesuai adalah

    t3 - 3t2 + 3t 1 = 0

    (t -1)3 = 0

    akar-akar pers. karakteristik 1=2=3=1. Karena semua akar sama, makapenyelesaiannya :

    an = (c1 + c2n + + cpnp-1) 1n =(c1 + c2n + c3n2).1n = c1 + c2n + c3n2a0 =1 sehingga 1 = c1 + c2.0 + c3.0

    2

    1 = c1

    a1 =2 sehingga 2 = c1 + c2.1 + c3.12

    2 = c1 + c2 + c3

    a2 =4 sehingga 4 = c1 + c2.2 + c3.224 = c1 + 2c2 + 4c3

    Dari 3 persamaan tersebut dapat diperoleh c1=1, c2=1/2 dan c3=

    1/2

    Maka penyelesaian relasi rekurensi an - 3an-1 + 3an-2 an-3 = 0 adalah

    an = 1 +1/2n +

    1/2n2 197

    Penyelesain relasi rekurensi linier

    tidak-homogen (penyelesaian total)

  • 8/4/2019 Matematika Diskrit Siap Print

    198/253

    penyelesaian homogen+

    penyelesaian khusus

    Untuk f(n) 0

    Kesulitan : tidak ada metode yang pasti sehingga

    menggunakan perkiraan bentuk umumnya(undetermined coeeficients)

    198

    Beberapa pola perkiran untuk fungsi f(n)f(n)

    (D,a :

    konstan)Sifat pers. karakteristik c(t)

    Bentuk penyelesaian

    khusus

  • 8/4/2019 Matematika Diskrit Siap Print

    199/253

    konstan)

    Dan a bukan akar pers.karakteristik c(t) (c(a)0) Pan

    Dan a adalah akar pers.karakteristik c(t) kelipatan

    m

    Pnman

    Dnsan a bukan akar pers.karakteristik c(t) (c(a)0) (P0+P1n++Psns)an

    Dnsan a adalah akar pers.karakteristik c(t) kelipatanm

    (P0+P1n++Psns)nman

    Dns 1 bukan akar pers.karakteristik c(t) (c(1)0) P0+P1n++Psns

    Dns 1 adalah akar pers.karakteristik c(t) kelipatan

    m

    (P0+P1n++Psns)nm

    199

    Contoh 1 : an-7an-1+10an-2=4nuntuk n2

    dengan kondisi awal a0=8 dan a1=36

    1/ P RRLH 7 + 10 0

  • 8/4/2019 Matematika Diskrit Siap Print

    200/253

    1/ Pers. RRLH : an - 7an-1 + 10an-2 = 0

    2/ Pers.karakteristik : t2 - 7t + 10 = (t-5)(t-2) = 0

    3/ Akar karakteristik : 1=5, 2=2

    4/ Penyelesaian homogen : an = c15n + c22

    n

    5/ Karena f(n)=4n dan 4 bukan akar karakteristik, maka bentuk

    penyelesaian khusus an=P(4)n

    . Kemudian substitusikan kerelasi rekurensi mula-mula :

    P(4)n 7 (P(4)n-1)+10(P(4)n-2) = 4n

    P(4)n-2(42-7.4+10) = 4n

    -2 P (4)n-2 = 4n

    -2 P = 16P = -8

    Sehingga penyelesaian khususnya adalah an = -8(4)n.

    200

    6/ Penyelesaian total = homogen + khususan = c15

    n + c22n - 8(4)n

    7/ Substitusi kondisi awal0 0 0

  • 8/4/2019 Matematika Diskrit Siap Print

    201/253

    a0=8 shg 8 = c15

    0

    + c22

    0

    - 8(4)

    0

    8 = c1+ c2

    8

    16 = c1+ c2

    a1=36 shg 36 = c151 + c22

    1 - 8(4)1

    36 = 5c1+ 2c2 32

    68 = 5c1+ 2c2

    Dengan substitusi diperoleh c1=12 dan c2=4.

    8/ Rumus eksplisit :an = 12.5

    n + 4.2n - 8(4)n

    201

    Contoh 2 : an-7an-1+10an-2=7.3n+4nuntuk n2

    1/ Penyelesaian homogen sama seperti contoh 1 : an = c15n + c22

    n

    2/ Karena f(n)=7.3n+4n, maka penyelesaian khususnya adalah jumlah dari penyelesaiankhusus relasi :

  • 8/4/2019 Matematika Diskrit Siap Print

    202/253

    khusus relasi :

    an-7an-1+10an-2=7.3n

    an-7an-1+10an-2=4

    n (contoh 1)

    Penyelesaian khusus untuk f(n)=4n adalah an = -8(4)n.

    Penyelesaian khusus f(n)=7.3n, karena 3 bukan akar karakteristik, maka digunakanbentuk an=P(3)n. Jika disubstitusikan ke relasi mula2 :

    P(3)n-7P(3)n-1+10P(3)n-2 = 7.3n

    P(3)n-2

    (32

    -7.3+10) = 7.3n

    -2P(3)n-2 = 7.3n

    -2P(3)n-2 = 7.3n

    -2P = 7.32

    P = -63/2Sehingga an= -(

    63/2)3n.

    Jadi penyelesaian khusus yang sesuai untuk f(n)= 7.3n+4n, adalah :an = -8(4)

    n - (63/2)3n

    Sehingga penyelesaian totalnya :

    an = c15n + c22

    n - 8(4)n - (63/2)3n

    202

    Contoh 3 : an 4an-1 + 4an-2 = 2n untuk n2

    1/ Pers RRLH : a 4a + 4a = 0

  • 8/4/2019 Matematika Diskrit Siap Print

    203/253

    1/ Pers. RRLH : an 4an-1 + 4an-2 = 0

    2/ Pers.karakteristik : t2 - 4t + 4 = (t-2)(t-2) = 03/ Akar karakteristik : 1=2=2

    4/ Penyelesaian homogen : an = (c1+ c2n) 2n

    5/ Karena f(n)=2n dan 2 adalah akar karakteristik kelipatan 2 (2 akar kembar),maka bentuk penyelesaian khusus an=Pn

    22n. Kemudian substitusikan kerelasi rekurensi mula-mula :

    Pn22n 4(P(n-1)22n-1) + 4(P(n-2)22n-2) = 2n

    P2n-2(n2.22 - 4(n-1)2.2 + 4(n-2)2) = 2n

    P(4n2 - 8(n2-2n+1) + 4(n2-4n+4)) = 22

    8P = 4

    P = 1/2Sehingga penyelesaian khususnya adalah an = -1/2n22n.

    6/ Penyelesaian total :

    an = (c1+ c2n) 2n -1/2n

    22n

    203

    Latihan

  • 8/4/2019 Matematika Diskrit Siap Print

    204/253

    Carilah penyelesaian total relasi rekurensiberikut :

    an - 5an-1 + 6an-2 = n24nuntuk n2

    an

    - 2an-1

    + an-2

    = 5+3n untuk n2

    204

  • 8/4/2019 Matematika Diskrit Siap Print

    205/253

    VII. GRAPH

    205

    Konsep

  • 8/4/2019 Matematika Diskrit Siap Print

    206/253

    Graph adalah suatu diagram yang memuatinformasi tertentu.

    Contoh :

    Struktur organisasi, Bagan alir pengambilan mata kuliah,

    Peta, dll.

    206

    Dasar-dasar Graph

    Suatu graph terdiri dari 2 himpunan berhingga, yaitu

  • 8/4/2019 Matematika Diskrit Siap Print

    207/253

    g p p gg , y

    himpunan titik (V(G)) dan himpunan garis (E(G)). Graf yang tidak mempunyai titik (sehingga tidak

    mempunyai garis) disebut graf kosong.

    Jika semua garisnya berarah maka disebut graph berarah(directed graph)

    Jika semua garisnya tidak berarah disebut graph takberarah (undirected graph)

    Setiap garis berhubungan dengan satu atau 2 titik, yangdisebut titik ujung.

    Garis yang berhubungan dengan satu titik ujung disebutloop.

    207

    Dasar-dasar Graph (2)

    Dua garis berbeda yang menghubungkan titik ujung yang

  • 8/4/2019 Matematika Diskrit Siap Print

    208/253

    sama disebut garis pararel. Dua titik dikatakan berhubungan (adjacent) jika ada garis

    yang menghubungkan keduanya.

    Titik yang tidak mempunyai garis yang berhubungan

    dengannya disebut titik terasing. Sebuah graf yang tidak mempunyai loop dan tidak

    mempunyai rusuk-rusuk yang sejajar disebut graf sederhana.

    Jika terdapat sebuah edge e yang menghubungkan verteks v

    dan w, kita tulis e = (v,w). Dalam konteks ini, (v,w)menyatakan sebuah edge antara v dan w dalam sebuahgraph.

    208

    Graph Berarah Sebuah graf terarah atau digraf G terdiri dari

  • 8/4/2019 Matematika Diskrit Siap Print

    209/253

    suatu himpunan V dari verteks dan suatuhimpunan E dari edge sedemikian rupasehingga setiap rusuk e E menghubungkanpasangan verteks terurut.

    himpunan verteks-verteks

    V = {v1, v2, v3, v4, v5}

    dan himpunan rusuk-rusuk

    E = {e1, e2, e3, e4, e5, e6}

    209

    v1 v2 v3

    v4 v5

    e2 e1

    e3

    e4

    e5

    e6

    Weighted Graph

  • 8/4/2019 Matematika Diskrit Siap Print

    210/253

    Sebuah graf dengan bilangan-bilangan padaedge-nya disebut graf berbobot(weighted

    graph). Dalam sebuah graf berbobot, panjang

    lintasan adalah jumlah bobot edge dalam

    lintasan.

    210

    a bc

    de

    8

    4

    4

    9

    62

    1253

    Derajat Suatu Titik

    Derajat titik v adalah jumlah garis yang berhubungan

  • 8/4/2019 Matematika Diskrit Siap Print

    211/253

    Derajat titik v adalah jumlah garis yang berhubungandengan titik v dan garis suatu loop dihitung 2 kali.

    Derajat total G adalah jumlah derajat semua titikdalam G

    211

    v1 v2

    v3

    v5

    v4

    v6

    e1

    e2

    e5

    e4e3 D(v1)=4 D(v4)=2

    D(v2)=2 D(v5)=1

    D(v3)=1 D(v6)=0

    Derajat total = 4+2+1+2+1+0 = 10

    Walk

    Misalkan v0 dan vn adalah verteks-verteks dalam

  • 8/4/2019 Matematika Diskrit Siap Print

    212/253

    sebuah graf. Sebuah walk dari v0 ke vn denganpanjang n adalah sebuah barisan berselang-seling dari n+1 verteks dan n edge yang berawaldengan verteks v0 dan berakhir dengan verteks

    vn,(v0, e1, v1, e2, , vn-1, en, vn)

    dengan ei insiden pada verteks vi-1 dan vi untuk

    i = 1,2, , n.

    212

    Path dan Sirkuit

  • 8/4/2019 Matematika Diskrit Siap Print

    213/253

    Path adalah walk dari v ke w yang semua garisnyaberbeda.

    Path sederhana adalah path dari v ke w yang semuatitiknya berbeda.

    Sirkuit/cycleadalah path yang dimulai dan diakhiri padatitik yang sama.

    Sirkuit sederhana adalah sirkuit yang semua titiknyaberbeda.

    213

    Contoh

    v3 v4e2

    e5

    e4

  • 8/4/2019 Matematika Diskrit Siap Print

    214/253

    214

    v1

    v2

    v6 v5

    e1

    e2

    e8

    e3

    e7

    e9

    e6 e10

    a. v1 e1 v2 e3 v3 e4 v3 e5 v4 Path dari v1 ke v4

    b. v1 e1 v2 e3 v3 e5 v4 e5 v3 e6 v5 Walk dari v1 ke v5

    c. v2 e3 v3 e5 v4 e10 v5 e6 v3 e7 v6 e8 v2 Sirkuit

    d. v2 e3 v3 e5 v4 e10 v5 e9 v6 e8 v2 Sirkuit sederhana

    Dari graph diatas tentukan barisan titik dan garis berikut apakahWalk, path, path sederhana, sirkuit, sirkuit sederhana.

    Graph terhubung dan Tidak Terhubun Dua titik v dan w dalam G dikatakan terhubung bila dan

  • 8/4/2019 Matematika Diskrit Siap Print

    215/253

    hanya bila ada walk dari v ke w. Graf G dikatakan terhubung (connected) bila dan hanya

    bila setiap 2 titik terhubung.

    Graf G dikatakan tidak terhubung (unconnected) bila

    dan hanya bila ada 2 titik yang tidak terhubung.

    215

    Connected Graph Unconnected graph

    Euler Path dan Cycle

    Euler path adalah sebuah path pada graph

  • 8/4/2019 Matematika Diskrit Siap Print

    216/253

    Euler path adalah sebuah path pada graph

    G yang melewati setiap edge/garis tepat 1

    kali dan melewati setiap vertex/titik paling

    sedikit sekali.

    Euler cycle/sirkuit adalah euler path yang

    kembali ke vertex awal.

    216

    Permasalahan 7 JembatanKonigsberg

    A

  • 8/4/2019 Matematika Diskrit Siap Print

    217/253

    Masalah : mungkinkah seseorang berjalan mengelilingi

    kota yang dimulai dan diakhiri pada tempat yang sama,

    dengan melintasi ketujuh jembatan masing-masing tepat

    1 kali ?

    Apakah graph tersebut merupakan sirkuit EULER ?

    217

    B

    A

    D

    C B C

    D

    Teorema Euler

    Jika graph G memiliki vertex berderajat ganjil maka

  • 8/4/2019 Matematika Diskrit Siap Print

    218/253

    Jika graph G memiliki vertex berderajat ganjil, makatidak ada euler cycle dalam G.

    Jika G adalah sebuah connected graph dan setiapvertexnya berderajat genap, maka terdapat EULERCYCLE dalam G.

    Jika graph G memiliki lebih dari 2 vertex berderajatganjil, maka tidak ada euler path.

    Jika G connected graph dan memiliki tepat 2 vertex

    berderajat ganjil, maka ada EULER PATH yangberawal di satu vertex berderajat ganjil dan berakhirdi vertex berderajat ganjil lainnya.

    218

    Contoh

    E

  • 8/4/2019 Matematika Diskrit Siap Print

    219/253

    219

    A

    B C

    D Euler path :EDBACD

    1

    2

    3

    4

    5

    Euler cycle :

    1345321

    Algoritma Fleury

    Algoritma untuk mencari EULER CYCLE dalam

  • 8/4/2019 Matematika Diskrit Siap Print

    220/253

    g

    sebuah connected graph yang tidak memilikivertex berderajat ganjil.

    Langkah-langkah :

    Pilih sembarang vertex (v). Dari v, pilih sebuah edge yang bukan merupakan cut

    edge (bridge). Beri tanda pada edge tersebut.

    Melalui edge tersebut, telusuri vertex lainnya.

    Ulangi langkah 2 dan 3 hingga semua edge terlewatidan berakhir di vertex awal (v).

    220

    ContohA B

    C D

    E FA B A B A B

  • 8/4/2019 Matematika Diskrit Siap Print

    221/253

    221

    C D

    E F

    A B

    C D

    E F

    A B

    C D

    E F

    A B

    C D

    E F

    C D

    E F

    A B

    C D

    E F

    A B

    C D

    E F

    A B

    C D

    E F

    A B

    C D

    E F

    Hamilton Path dan Cycle

  • 8/4/2019 Matematika Diskrit Siap Print

    222/253

    Hamilton path adalah path dalam sebuah graph

    yang melewati tiap vertex tepat 1 kali dan tidak

    harus melalui semua garis.

    Hamilton cycle adalah hamilton path yang

    kembali ke titik awal

    Graph yang mengandung hamilton cycle tidak

    memiliki loop dan multiple edge

    222

    Contoh

  • 8/4/2019 Matematika Diskrit Siap Print

    223/253

    223

    A

    B C

    DE

    Hamilton cycle : A-B-C