DIKTAT

MATEMATIKA DISKRIT

Tim Dosen

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNIK MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS INDRAPRASTA PGRI

2012

0

BAB I

LOGIKA PROPOSISI

Logika merupakan study penalaran (reasoning).

Definisi Penalaran : cara berfikir dengan mengembangkan sesuatu berdasarkan akal budi dan

bukan dengan perasaan/pengalaman.

Logika difokuskan pada hubungan antara pernyataan-pernyataan (statement).

Contoh: Semua pengendara motor memakai helm

Setiap orang yang memakai helm adalah mahasiswa

Jadi, semua pengendara sepeda motor adalah mahasiswa

Logika tidak membantu menentukan apakah pernyataan-pernyataan tersebut benar/salah.

Kalimat yang bernilai benar/salah disebut Proposisi (Preposition)

1. PROPOSISI (PREPOSITION)

Definisi Proposisi : kalimat deklaratif yang bernilai benar (true)/salah (false), tetapi tidak

dapat sekaligus keduanya. Kebenaran/kesalalahan dari sebuah kalimat disebut nilai

kebenarannya (truth value).

Contoh : (a) 6 adalah bilangan genap

(b) Soekarno adalah Presiden Indonesia yang pertama

(c) 2 + 2 = 4

(d) Ibukota Provinsi Jawa Barat adalah Semarang

(e) kemarin hari hujan

(f) suhu dipermukaan laut adalah 21oC

Secara simbolik, proposisi dilambangkan dengan huruf kecil seperti p, q, r…

1

Missal : p = 6 adalah bilangan genap

r = 2 + 2 = 4

2. INGKARAN (NEGASI)

Bila p merupakan suatu pernyataan yang bernilai benar, maka ~p merupakan pernyataan

yang bernilai salah, demikian sebaliknya.

Notasi : = tidak p

Table kebenaran

T F

F T

T = TRUE (benar)

F = FALSE (salah)

Contoh : = semua mahasiswa di kelas ini memakai baju hijau

= tidak semua mahasiswa di kelas ini memakai baju hijau

= beberapa mahasiswa di kelas ini memakai baju hijau

= ada beberapa mahasiswa di kelas ini memakai baju hijau

3. KONJUNGSI (CONJUCTION/DAN)

Dari dua pernyataan p dan q dapat dibentuk pernyataan majemuk dalam bentuk

yang disebut konjungsi dari penyataan .

2

Notasi :

Table kebenaran

T T T

T F F

F T F

F F F

Contoh : = hari ini hujan

= murid-murid diliburkan dari sekolah

= hari ini hujan dan murid-murid diliburkan dari sekolah

4. DISJUNGSI (DISJUNCTION/ATAU)

Bernilai salah bila kedua-duanya salah.

Notasi :

Table kebenaran

T T T

T F F

F T F

F F F

3

Contoh : = hari ini hujan

= murid-murid diliburkan dari sekolah

= hari ini hujan atau murid-murid diliburkan dari sekolah

5. DISJUNGSI EKSKLUSIF

Definisi: misalkan p dan q adalah proposisi. Eksekutif or p dan q, dinyatakan dengan notasi

adalah proposisi yang bernilai benar bila hanya salah satu dari p dan q benar, selain itu

nilainya salah.

Notasi :

hanya benar jika salah satu, tapi tidak keduannya, dari proposisi atomiknya benar.

Table kebenaran:

T T F

T F T

F T T

F F F

6. KONDISIONAL (IMPLIKASI/PROPOSISI BERSYARAT)

Suatu pernyataan majemuk yang berbentuk

Notasi :

4

Table kebenaran

T T T

T F F

F T T

F F T

Contoh : jika adik lulus ujian, maka ia mendapat hadiah dari ayah

Jika suhu mencapai 80oC, maka alarm berbunyi

7. BIKONSISIONAL/(BIIMPLIKASI)

Implikasi yang mempunyai dua arah yang berbentuk

Notasi :

Table kebenaran

T T T

T F F

F T F

F F T

Contoh:

(a) Jika udara diluar panas maka anda membeli es krim, dan jika anda membeli es krim maka

udara diluar panas.

(b) Anda naik jabatan jika anda punya koneksi, dan anda punya koneksi jika anda naik

jabatan.

Penyelesaian:

5

(a) Anda membeli es krim jika dan hanya jika udara diluar panas.

(b) Anda naik jabatan jika dan hanya jika anda punyaa koneksi.

HUKUM-HUKUM LOGIKA PROPOSISI

1. HUKUM IDENTITAS

(i)

(ii)

2. HUKUM NULL/DOMINASI

(i)

(ii)

3. HUKUM NEGASI

(i)

(ii)

4. HUKUM IDEMPOTEN

(i)

(ii)

5. HUKUM INVOLUSI

(NEGASI GANDA)

(i)

6. HUKUM PENYERAPAN

(ABSORPSI)

(i)

(ii)

7. HUKUM KOMUTATIF

(i)

(ii)

8. HUKUM ASOSIATIF

(i)

(ii)

6

9. HUKUM DISTRIBUTIF

(i)

(ii)

10. HUKUM De Morgan

(i)

(ii)

8. INFERENSI

Proses penarikan kesimpulan dari beberapa proposisi disebut inferensi (inference). Didalam

proposisi terdapat sejumlah kaidah inferensi, antara lain:

Modus Ponen (law detachment)

Kaidah ini didasarkan pada tautology , yang dalam hal ini,

adalah hipotesis, sedangkan adalah konklusi. Kaidah modus ponen

ditulis dengan cara:

Symbol dibaca sebagai “jadi” atau “karena itu”. Modus ponen menyatakan bahwa

jika hipotesa dan implikasi benar, maka konklusi benar.

Contoh:

Misalkan implikasi “jika 20 habis dibagi 2, maka 20 adalah bilangan genap” dan

hipotesa “20 habis dibagi 2” keduanya benar. Maka menurut modus ponen, inferensi

berikut:

“ Jika 20 habis dibagi 2, maka 20 adalah bilangan genap. 20 habis dibagi 2. Karena

itu, 20 adalah bilangan genap”

Adalah benar. Kita juga dapat menuliskan inferensi diatas sbb:

7

Modus Tollen

Kaidah ini didasarkan pada tautology , kaidah ini modus tollen

ditulis dengan cara:

Contoh:

Misalkan implikasi “jika n adalah bilangan ganjil, maka n2 bilangan ganjil” dan

hipotesa “n2 bernilai genap” keduanya benar. Maka menurut modus tollen, inferensi

berikut:

8

Silogisme Hipotesis

Kaidah ini didasarkan pada tautology . Kaidah ini

silogisme ditulis dengan cara:

Contoh :

Misalkan implikasi “ jika saya belajar dengan giat, maka saya lulus ujian” dan

implikasi “jika saya lulus ujian, maka saya cepat menikah” adalah benar. Maka

menurut kaidah silogisme, inferensi berikut:

Silogisme Disjungtif

Kaidah ini didasarkan pada tautology . Kaidah silogisme

disjungsi ditulis dengan cara:

9

Contoh:

“Saya belajar dengan giat atau saya menikah tahun depan.

Saya tidak belajar dengan giat. Karena itu, saya menikah tahun depan.”

Menggunakan kaidah silogisme disjungtif, atau dapat ditulis dengan cara:

Simplifikasi

Kaidah ini didasarkan pada tautology , yang dalam hal ini, p dan q adalah

hipotesis, sedangkan p adalah konklusi. Kaidah simplifikasi ditulis dengan cara:

Contoh:

“ Hamit adalah mahasiswa UNINDRA dan mahasiswaUIN. Karena itu, Hamit adalah

mahasiswa UNINDRA”

Menggunakan kaidah simplikasi, atau dapat juga ditulis dengan cara:

10

Penjumlahan

Kaidah ini didasarkan pada tautology . Kaidah penjumlahan ditulis

dengan cara:

**

Contoh:Penarikan kesimpulan seperti berikut:

“Taslim mengambil kuliah Matematika Diskrit. Karena itu, Taslim mengambil kuliah

Matematika Diskrit atau mengulang kuliah Algoritma”

Menggunakan kaidah penjumlah, atau dapat juga ditulis dengan cara:

Konjungsi

Kaidah ini didasarkan pada tautology . Kaidah konjungsi

ditulis dengan cara:

11

Contoh:Penarikan kesimpulan seperti berikut:

“Taslim mengambil kuliah Matematika Diskrit. Taslim mengulang kuliah Algoritma.

Karena itu, Taslim mengambil kuliah Matematika Diskrit atau mengulang kuliah

Algoritma”

Menggunakan kaidah konjungsi, atau dapat juga ditulis dengan cara:

9. TAUTOLOGI & KONTRADIKSI

Definisi Tautologi : sebuah proposisi adalah sebuah tautology jika

benar untuk sembarang penyataan

Demikian juga:

12

Definisi Kontradiksi : sebuah proposisi adalah sebuah kontradiksi jika

salah untuk sembarang penyataan dengan kata lain, sebuah

kontradiksi hanya akan mengandung F dalam kolom terakhir dari table kebenarannya.

Contoh:

1. Proposisi “p atau bukan p”, yakni , adalah sebuah tautology. Kenyataan ini

dijelaskan dengan membentuk sebuah table kebenaran:

T F T

F T T

2. Proposisi “p dan bukan p”, yakni , adalah sebuah kontradiksi. Kenyataan ini

dijelaskan oleh table berikut:

T F F

F T F

Latihan soal:

1. Untuk menerangkan karateristik mata kuliah X, misalkan p : “kuliahnya menarik”, dan

q : “dosennya enak”, r : soal-soal ujiannya mudah”. Terjemahknan proposisi-proposisi

berikut dalam notasi simbolik (menggunakan p,q,r):

a. Kuliahnya tidak menarik, dosennya tidak enak, dan soal-soal ujiannya tidak mudah.

b. Kuliahnya menarik atau soal-soal ujiannya tidak mudah, namun tidak keduannya.

c. Salah bahwa kuliahnya menarik berarti dosennya enak dan soal-soalnya mudah.

2. Misalkan p adalah “Hari ini adalah Hari Rabu”, q adalah “Hujan turun” dan r adalah

“Hari ini panas”. Terjemahkan notasi simbolik ini dengan kata-kata:

a.

13

b.

c.

3. Tuliskan table kebenaran untuk setiap proposisi berikut:

a.

b.

4. Periksa kesahihan argument-argumen berikut:

a. Jika hari panas, Anton mimisan. Hari tidak panas. Oleh karena itu, Anton tidak

mimisan,

b. Jika hari panas, Anton mimisan. Anton tidak mimisan. Oleh karena itu, hari tidak

panas.

5. Gunakan table kebenaran untuk menunjukkan bahwa tiap implikasi berikut adalah

tautology:

a.

b.

c.

14