matematika diskrit

Matematika Diskrit

Kontrak Kuliah Jadwal Kuliah GBPP (Garis Besar Program Pengajaran) Pustaka Pertemuan 1 Proposisi

Kontrak

Dalam menentukan nilai akhir, akan digunakan pembobotan sebagai berikut:

Kegiatan Bobot Nilai (%) Ujian Tengah Semester 25 Ujian Akhir Semester 35 Tugas Individu15 Kelompok 15 Keaktifan 10

Apa yang dipelajari

Proposisi Himpunan Relasi Algoritma KOmbinasi Aljabar Boolean Teori Graf Teori Tree

Jadwal Kuliah

Pertemuan 1

Pejelasan kontrak kuliah, GBPP, Jadwal, Pustaka

Proposisi : Definisi Proposisi Mengkobinasi Proposisi

Pertemuan 2Tabel Kebenaran Hukum-hokum logika Proposisi bersyarat

Pertemuan 3Relasi : Definisi relasi Sifat-sifat relasi biner Relasi keekuivalenan Matrik relasi Pertemuan 4Algoritma : Notasi algoritma Algoritma eucilides Algoritma rekursif Kompleksitas algoritma

Pertemuan 6

Kombinasi Definisi Kombinasi Permutasi dan kombinasi bentuk umum

Pertemuan 7 Kombinasi dengan perulangan Koefisien binomial

UTS

Pertemuan 8

Aljabar boolean Aljabar Boolean Aljabar Boolean Dua Nilai Hukum – hukum Aljabar Boolean Fungsi Boolean

Permuan 9 Penjumlahan dan perkalian dua fungsi Komplemen Fungsi Aplikasi Aljabar Boolean

Pertemuan 10Graf : Sejarah graf Definisi Graf Jenis-Jenis Graf Terminologi Graf Representasi Graf Pertemuan 11 Graf isomorfik Graf Planar Graf dual

Pertemuan 12 Lintasan dan sirkuit euler Lintasan dan sirkuit Hamilton Beberapa Aplikasi GrafPertemuan 13Pohon Definisi Pohon Sifat-sifat pohon Pohon rentangPertemuan 14 Pohon berakar Pohon terurut Pohon biner UAS

PUSTAKA

Richard Johnsonbaugh.1993. Discrete Mathematics forth edition. DePaul University. Chicago

Rinaldi Munir, “ Matematika Diskrit”, edisi ketiga, penerbit Informatika Bandung, 2005

Seymour Lipschutz,”Seri Penyelesaian Schaum”, jilid1, salemba teknika, 2001

MATEMATIKA DISKRIT Apa ?

Cabang matematika yg mempelajari tentang obyek diskrit. Apa yang dimaksud dengan kata diskrit (discrete)?

Objek disebut diskrit jika: terdiri dari sejumlah berhingga elemen yang berbeda elemen-elemennya tidak bersambungan

(unconnected). Contoh: himpunan bilangan bulat (integer)

Lawan kata diskrit: kontinyu atau menerus (continuous). Contoh: himpunan bilangan riil (real)

• Komputer digital bekerja secara diskrit. Informasi yang disimpan dan dimanipulasi oleh komputer adalah dalam bentuk diskrit.

Kenapa belajar ?

Matematika diskrit merupakan ilmu dasar dalam pendidikan informatika atau ilmu komputer.

Matematika diskrit memberikan landasan matematis untuk kuliah-kuliah lain di informatika : algoritma, struktur data, basis data, otomata dan teori bahasa formal, jaringan komputer, keamanan komputer, sistem operasi, teknik kompilasi, dsb.

Matematika diskrit adalah matematika yang khas informatika Matematika Informatika.

1. Brp byk almt internet valid yg mungkin pd 1. Brp byk almt internet valid yg mungkin pd suatu jaringan komputer ?suatu jaringan komputer ?

2. Brp probabilitas menang suatu undian ?2. Brp probabilitas menang suatu undian ?

3. Bgmn menentukan lintasan terpendek antar 3. Bgmn menentukan lintasan terpendek antar kota ?kota ?

4. Bgmn mengurutkan suatu kumpulan data ?4. Bgmn mengurutkan suatu kumpulan data ?

Proposisi

Pengertian Proposisi Operator Logika Tabel Kebenaran

Pengertian Proposisi

Proposisi adalah sebuah pernyataan yang bisa bernilai benar (true/T) atau salah (false/F) tetapi tidak sekaligus keduanya.

Kita katakan bahwa nilai kebenaran (truth value) dari sebuah proposisi adalah benar atau salah.

Dalam rangkaian dijital, nilai ini dinyatakan sebagai 1 dan 0

“Gajah lebih besar daripada tikus.”

Apakah ini sebuah pernyataan?Apakah ini sebuah pernyataan? YAYA

Apakah ini sebuah proposisi?Apakah ini sebuah proposisi? YAYA

Apakah nilai kebenaran Apakah nilai kebenaran dari proposisi ini?dari proposisi ini?

BENARBENAR

Proposisi atau Pernyataan

“520 < 111”




SALAHSALAH


“y > 5”

Nilai kebenaran dari pernyataan tersebut Nilai kebenaran dari pernyataan tersebut bergantung pada y, tapi nilainya belum bergantung pada y, tapi nilainya belum ditentukan.ditentukan.


Apakah ini sebuah proposisi?Apakah ini sebuah proposisi? TIDAKTIDAK


Pernyataan jenis ini kita sebut sebagai Pernyataan jenis ini kita sebut sebagai fungsi proposisifungsi proposisi atau atau kalimat terbukakalimat terbuka..

“Sekarang tahun 2004 dan 99 < 5.”




SALAHSALAH


“Tolong untuk tidak tidur selama kuliah”

TIDAKTIDAK

TIDAKTIDAK

Hanya pernyataanlah yang bisa menjadi Hanya pernyataanlah yang bisa menjadi proposisi.proposisi.

Ini adalah sebuah permintaan.Ini adalah sebuah permintaan.

Apakah ini sebuah pernyataan?Apakah ini sebuah pernyataan?

Apakah ini sebuah proposisi?Apakah ini sebuah proposisi?


“x < y jika dan hanya jika y > x.”

Apakah ini pernyataan ?Apakah ini pernyataan ? YAYA

Apakah ini proposisi ?Apakah ini proposisi ? YAYA

Apakah nilai kebenaran Apakah nilai kebenaran dari proposisi ini ?dari proposisi ini ? BENARBENAR

… … karena nilai kebenarannya karena nilai kebenarannya tidak bergantung harga tidak bergantung harga spesifik x maupun y.spesifik x maupun y.


Penggabung Proposisi

Beberapa contoh terdahulu menunjukkan bahwa beberapa proposisi dapat digabung menjadi sebuah proposisi gabungan.

Hal ini kita formal-kan dengan melambangkan proposisi sebagai huruf-huruf; seperti p, q, r, s; dan memperkenalkan operator-operator logika.

Operator logikaKita akan membahas operator-operator berikut:

Negasi (NOT) Konjungsi (AND) Disjungsi (OR) Eksklusif OR (XOR) Implikasi (jika – maka) Bikondisional (jika dan hanya jika)

Tabel logika (tabel kebenaran/ truth table) dapat dipakai untuk menunjukkan bagaimana operator-operator tsb diatas menggabungkan beberapa proposisi menjadi satu proposisi gabungan.

Negasi (NOT)

Operator Uner, Lambang:

P P

Benar Salah

Salah Benar

Konjungsi (AND)

Operator Biner, Lambang:

P Q PQ

Benar Benar Benar

Benar Salah Salah

Salah Benar Salah

Salah Salah Salah

Disjungsi (OR) Operator Biner, Lambang:

Tamu Boleh Menyumbang barang atau uang

P Q PQ

Benar Benar Benar

Benar Salah Benar

Salah Benar Benar

Salah Salah Salah

Eksklusif Or (XOR)

Operator Biner, Lambang: Saya akan melihat pertandingan itu di TV atau di lapangan

P Q PQ

Benar Benar Salah

Benar Salah Benar

Salah Benar Benar

Salah Salah Salah

Implikasi (jika - maka) Operator Biner, Lambang:

Jika besok cerah (p), maka aku akan datang ke rumahmu (Q)

P = hipotesis, Q = konklusi

P Q PQ

Benar Benar Benar

Benar Salah Salah

Salah Benar Benar

Salah Salah Benar

Bikondisional (jika dan hanya jika)

Operator Biner, Lambang: (P Q) ( Q P)

P Q PQ

Benar Benar Benar

Benar Salah Salah

Salah Benar Salah

Salah Salah Benar

Pernyataan dan Operasi

Pernyataan-pernyataan dan operator-operator dapat digabungkan menjadi suatu pernyataan baru.

P Q P Q (P)(Q)

Benar Benar Salah Salah Salah

Benar Salah Salah Benar Benar

Salah Benar Benar Salah Benar

Salah Salah Benar Benar Benar

Pernyataan dan Operasi

P Q PQ (PQ) (P)(Q)

Benar Benar Benar Salah Salah

Benar Salah Salah Benar Benar

Salah Benar Salah Benar Benar

Salah Salah Salah Benar Benar

Pernyataan-pernyataan dan operator-operator dapat digabungkan menjadi suatu pernyataan baru.

Pernyataan-pernyataan yang ekivalen

P Q (PQ) (P)(Q) (PQ)(P)(Q)

Benar Benar Salah Salah Benar

Benar Salah Benar Benar Benar

Salah Benar Benar Benar Benar

Salah Salah Benar Benar Benar

Pernyatan (PQ) dan (P)(Q) adalah ekivalen secara logis, karena

(PQ)(P)(Q) selalu benar.

Tautologi dan Kontradiksi

Suatu tautologi adalah pernyataan yang selalu bernilai benar

Contoh: R(R) (PQ)(P)(Q)

Jika ST sebuah tautologi, kita tulis S T. JIka ST sebuah tautologi, kita tulis S T.

Suatu kontradiksi adalah pernyataan yang selalu bernilai salah.

Contoh: R(R) ((PQ)(P)(Q))

Negasi dari sebarang tautologi adalah sebuah kontradiksi, sebaliknya, negasi dari sebuah kontradiksi adalah sebuah tautologi.

Kontradiksi

Latihan

Kita tahu tautologi berikut:

(PQ) (P)(Q)

Latihan di kelas :

Tunjukkan bahwa (PQ) (P)(Q).

matematika diskrit

Documents