Matematika Diskrit/Logika

Apakah itu matematika diskrit?

Matematika diskrit adalah Cabang matematika yang mengakaji objek objek diskrit. apa yang dimaksud dengan kata diskrit? benda disebut diskrit jika ia terdiri dari sejumlah berhingga elemen yang berbeda atau elemen elemen yang tdak bersambungan. diskrit juga diartikan dengan tidak saling bersambungan atau lawan dari kontinu, objek yang dibahas dari matematika diskrit seperti Logika, Teori Himpunan, matriks, Relasi dan Fungsi, induksi matematika, algoritma, teori bilngan bulat, barisan dan deret teori grab, aljabar boolean, kombinatorial, teori peluang diskrit, fungsi pembangkit dan analisis rekurens, teori grab. contoh contoh persoalan dalam kehidupan sehari hari yang diselesaikan dengan matematika diskrit antara lain.

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

2. Bagaimana nomor ISBN sebuah buku divalidasi?

3. " makanan murah tidak enak", "makanan enak tidak murah". Apakah kedua pernyataan tersebut menyatukan hal yang sama? 

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

Contoh-contoh persoalan di atas memperlihatkan bahwa matematika diskrit digunakan bilamana kita menghitung objek-objek, mengkaji relasi antara objek-objek dikaji, dan langkah langkah didalam proses dianalisis.

Bab 1 Logika 

Logika merupakan studi penalaran (reasoning) yaitu cara berpikir dengan mengembangkan sesuatu berdasarkan akal budi dan bukan dengan perasaan atau pengalaman. pelajaran logika difokuskn pada hubungan antara pernyataan pernyataan.

               Semua pengendara sepeda motor memakai helm

               Setiap orang yang memakaihelm adalah mahasiswa

               Jadi, semua pengendara sepeda motor adalah mahasiswa

Meskipun logika tidak membantu menentukan apakah pernyataan-pernyataan tersebut benar atau salah, tetapi jika kedua pernytaan tersebutbenar, maka penalaran dengan menggunakan logika membawa kita pada kesimpulan bahwa pernyataan 

            Semua pengendara sepeda motor adalah mahasiswa 

juga benar.

1.1  Proposisi

  Didalam matematika, tidak semua kalimat berhubungan dengan logika. hanya kalimat yang bernilai benar atau salah saja yang digunakan dalam penalaran kalimat tersebut dinamakan proposisi.

Definisi 1.1.  Proposisi adalah kalimat deklaratif yang bernilai benar(true) atau salah (false), tetapi tidak dapat sekaligus keduanya. kebenaran atau kesalahan dari sebuah kalimat disebut nilai kebenarannya (truth value).

Contoh 1.1

kalimat-kalimat berikut ini

a)   6 adalah bilangan genap

b)  Soekarno adalah Presiden Indonesia yang pertama

c)  2 + 2 = 4

d)  Ibukota Provinsi Jawa Barat adalah Semarang

e)  12   >  19 

f)  Kemarin Hujan  

g)  Suhu di permukaan laut 21 derajat Celcius.

h)  Pemuda itu tinggi

i)  Kehidupan hanya ada diplanet bumi

Semua merupakan proposisi a, b, dan c bernilai benar, tetapi proposisi d salah karena ibu kota jawa Barat seharusnya adalah Bandng dan proposisi e bernilai salah karena seharusnya 12 < 19. Proposisi f sampai i memang tdak dapat langsung ditetapkan kebenarannya, namun suatu hal yang pasti, proposisi tersebut tidak mungkin benar dan sekaligus salah. demikian pula halnya untuk proposisi g dan h. Proposisi i bisa benar atau salah, karena sampai saat ini ada ilmuan yang dapat memastikan kebenarannya.

 Contoh 1.2

Kalimat-kalimat berikut

a) Jam berpa kereta api Argo Bromo tiba di Gambir

b) Serahkan uangmu sekarang!

c) x +3 = 8

e) x >3

Bukan proposisi, kalimat a adalah kalaimat tanya, sedangkan kalimat b adalah kalimat perintah, keduanya tidak mempunyai nilai kebenaran. dari contoh 1.1 dan contoh 1.2 di atas, kita dapat menyimpulkan bahwa proposisi selalu dinyatakan sebagai kalimat berita, bukan sebagai kalimat tanya atau kalimat perintah. 

1. 2 Mengkoninasikan Proposisi

Semua merupakan proposisi a, b, dan c bernilai benar, tetapi proposisi d salah karena ibu kota jawa Barat seharusnya adalah Bandng dan proposisi e bernilai salah karena seharusnya 12 < 19. Proposisi f sampai i memang tdak dapat langsung ditetapkan kebenarannya, namun suatu hal yang pasti, proposisi tersebut tidak mungkin benar dan sekaligus salah. demikian pula halnya untuk proposisi g dan h. Proposisi i bisa benar atau salah, karena sampai saat ini ada ilmuan yang dapat memastikan kebenarannya

Kita dapat membentuk proposisi baru dengan cara mengkombinasikan satu atau lebih proposisi. Operator yang digunakan untuk mengkombinasikan proposisi disebut operator logika. Operator logika dasar yang digunakan adalah dan (and), atau (or), dan tidak (not). Dua operator pertama dinamakan operator biner karena operator tersebut mengoperasikan dua buah proposisi, sedangkan operator ketiga dinamakan operator uner karena hanya membutuhkan satu buah proposisi.

Proposisi baru yang diperoleh dari pengkombinasian terseebut dinamakan proposisi majemuk (compound proposition). Proposisi yang bukan merupakan kombinasi proposisi lain disebut proposisi atomik. Dengan kata lain, proposisi majemuk disusun dari proposisi-proposisi atomik. George Boole dalam bukunya The Laws of Thought mengemukakan bahwa proposisi majemuk ada tiga macam, yaitu konjungsi, disjungsi, dan ingkaran. Ketiganya didefinisikan sebagai berikut

DEFINISI 1.2

Misalkan p dan q adalah proposisi.

Konjungsi (conjuntion) p dan q dinyatakan dengan notasi p ^ q, adalah proposi

p dan q.

Disjungsi (disjuntion) p dan q dinyatakan dengan notasi p V q adalah proposi

p atau q.

Ingkaran atau (negation) dan p, dinyatakan dengan notasi ~p. Adalah proposi

tidak p.

Berikut ini contoh proposisi majemuk dan notasi simboliknya. Ekspresi proposisi majemuk dalam notasi simbolik disebut juga ekspresi logika.

Contoh 1.3

Diketahui proposisi-proposisi berikut :

p : Hari ini hujan

q : murid-murid diliburkan dari sekolah

Maka

p q : Hari ini hujan dan murid-murid diliburkan dari sekolah.

p q : Hari ini hujan atau murid-murid diliburkan dari sekolah.

p : Tidak benar hari ini hujan

atau dengan kata lain, "Hari ini tidak hujan"

p p : Haari ini hujan atau murid-murid tidak diliburkan

Contoh 1.4

Diketahui proposisi-proposisi berikut :

p : Hari ini hujan

q : Hari ini dingin

Maka

p -q : Hari ini dingin atau hari ini tidak hujan.

                 atau dengan kata lain, " Hari ini dingin atau tidak hujan"

p ^ -q : Hari ini tidak hujan dan hari ini tidak dingin

                atau, dengan kata lain,"salah bahwa hari ini tidak hujan"

(-p) : Tidak benar hari ini tidak hujan

              atau dengan kata lain, "Hari ini tidak hujan"

p p : Haari ini hujan atau murid-murid tidak diliburkan

Contoh 1.5

Diketahui proposisi-proposisi berikut:

P : Pemuda itu tinggi

q : Pemuda itu tampan

maka

a) p^q : Pemuda itu tinggi dan tampan.

b) P^~q : Pemuda itu tinggi tapi tidak tampan

c) ~p^~q : Pemuda itu tidak tinggi maupun tampan

d) ~(~p~q) : Tidak benar bahwa pemuda itu pendek atau tidak tampan

e) p(~p^q) : Pemuda itu tinggi, atau pendek dan tampan

f) ~(~p^~q) : Tidak benar bahwa pemuda itu pendek maupun tampan

1.3 Tabel Kebenaran

Nilai tabel kebenaran dari proposisi majemuk ditentukan oleh nilai kebenaran dari proposisi atomiknya dan cara mereka dihubungkan oleh operator logika.

Definisi 1.3 Misalkan p dan q adalah proposisi.

Nilai tabel kebenaran dari proposisi majemuk ditentukan oleh nilai kebenaran dari proposisi atomiknya dan cara mereka dihubungkan oleh operator logika.

Definisi 1.3 Misalkan p dan q adalah proposisi.

Konjungsi  bernilai benar jika  dan  keduanya benar, selain selain itu nilainya adalah      salah

Disjungsi p q bernilai salah jika  dan  keduanya salah, selain selain itu nilainya adalah      benar

Negasi p, yaitu , bernilai benar jika  salah, sebaliknya bernilai salah jika p benar.

Contoh 1.6

Misalkan

          P : 17 adalah bilangan prima

        q : bilangan prima selain ganjil

Jelas bahwa p bernilai benar dan q bernilai salah sehingga konjungsi

       p q : 17 adalah bilangan prima dan bilangan prima selalu ganjil adalah salah

Tabel 1.1 Tabel kebenaran Konjungsi, disjungsi, dan ingkaran

 Konjungsi

p

q

   p^q

T

T

T

T

F

F

F

T

F

F

F

F

Disjungsi

p

q

p q

T

T

T

T

F

T

F

T

T

F

F

F

Ingakaran

p

-q

T

F

F

T