Matematika LogikaLogika Preposisi

Yenni Fatman, S.T.

@2012

Teknik Informatika -Unpas

Ekivalensi Logis .. (1)

Negasi Ganda p p

Hukum Komutatif

(pq) (qp)

(pq) (qp)

(pq) (qp)

Hukum Asosiatif

(pq) r p (qr)

(pq) r p (qr)

Hukum Distributif

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

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

Ekivalensi Logis .. (2)

HukumIdempoten

(pp) p

(pp) p

Hukum Identitas

(p0) p

(p1) 1

(p0) 0

(p1) p

Hukum Asosiatif

(p p) 1

(p p) 0

Ekivalensi Logis .. (3)

Hukum de Morgan

(pq) p q

(pq) p q

(pq) (p q)

(pq) (p q)

Kontrapositif (p q) (q p)

Implikasi (p q) (p q)

(p q) (p q)

Formula Valid dan Inkonsisten

Suatu formula

dikatakan validjika dan hanya jika formula tersebut

tautologiSuatu formula dikatakan invalid jika dan hanya jika tidak valid

Suatu formula dikatakan

inkonsisten jika

dan hanya jika formula tersebut

kontradiksiSuatu formula dikatakan konsisten jika dan hanya jika tidak konsisten

Implikasi Validitas

Formula adalah

valid jika dan hanya jika

negasinya inkonsistenFormula adalah

inkonsisten jika dan hanya jika

negasinya valid

Formula adalah

invalid jika dan hanya jika ada interpretasi yang menyebabkannya salahFormula adalah

konsisten jika dan hanya jika ada interpretasi yang menyebabkannya benar

Implikasi Validitas

Jika formula adalah valid, maka formula tersebut konsisten, tetapi tidak sebaliknya

Jika formula adalah inkonsisten, maka formula tersebut invalid, tetapi tidak sebaliknya

p p– Formula inkonsisten

– Formula invalid

p p– Formula valid

– Formula konsisten

p p– Formula invalid

– Formula konsisten

Implikasi Validitas

p p p p

0 1 0

1 0 0

p p– Formula inkonsisten

– Formula invalid

p p– Formula valid

– Formula konsisten

p p– Formula invalid

– Formula konsisten

P P p p

0 1 1

1 0 1

p p p

p

0 1 1

1 0 0

Bentuk Normal Formula

Formula dapat dibentuk dengan menggunakan kombinasi operator logika ,,,, dan

Formula yang hanya menggunakan kombinasi operator logika ,, dan

disebut Bentuk Normal– Bentuk Normal Konjungsi: dan

– Bentuk Normal Disjungsi: dan

Transformasi Bentuk Normal

Eliminasi operator dan , dengan menggunakan aturan:

F G = (F G) (F G )

F G = F G

Gunakan Hukum Distributif (dan hukum lainnya)

Pindahkan operator ke tepat sebelum atom, dengan menggunakan aturan:

– ( F) = F

– De Morgan:

•(pq) p q

•(pq) p q

Transformasi Bentuk Normal

Ubah (P (Q R)) S ke dalam bentuk normal konjungsi!

(P (Q R)) S = (P (Q R)) S

= (P (Q R)) S

= ( P (Q R)) S

= ( P (Q R)) S

= (( P Q) ( P R)) S

= ( P Q S ) ( P R S)

Transformasi Bentuk Normal

Ubah (p q) r ke dalam bentuk normal disjungsi!

(p q) r = (p q) r

= ( p ( q)) r

= ( p q ) r

Pembuktian Logika

Logika Proposisional adalah alat bantu untuk argumentasi berdasarkan fakta dan kesimpulan– Fakta

– Konklusi / Kesimpulan

– Argumentasi = fakta + konklusi

– Fakta + konklusi adalah benar DAN terdapat hubungan logis Argumentasi benar

– Faktar benar tapi konklusi salah Argumentasi salah

Pembuktian Logika

Pembuktian Logika: proses membuktikan benar/salahnya suatu konklusi/kesimpulan secara logis

Menggunakan fakta-fakta atau argumentasi yang dinyatakan dalam bentuk preposisi yang diasumsikan benar

– Fakta disebut Premis (aksioma, postulat, hipotesa)

– Kesimpulan yang ditarik dari premis disebut konsekuensi logis

Metode Pembuktian

Pembuktian Langsung

– Pembuktian dengan tautologi

Pembuktian Tidak Langsung

– Pembuktian dengan kontrapositif

– Pembuktian dengan kontrakdiksi

Teknik Pembuktian

Tabel Kebenaran

Penyederhanaan / Normalisasi

Aturan Inferensi

Tabel Kebenaran

Cara yang paling sederhana

Langkah-langkah:

– Tentukan formula dari presmi-premis yang ada

– Tentukan metodenya: langsung/tidak langsung

– Buat tabel kebenarannya

– Cek berdasarkan tabel, formula tautology / bukan

– Buat kesimpulan

Tabel Kebenaran (Contoh)

Periksalah kesimpulan dari premis-premis berikut:

– Jika kucing di dalam rumah maka rumah tidak tenang

– Kucing tidak ada di dalam rumah

– Kesimpulan: rumah pasti tenang (Betulkah?)

Tabel Kebenaran: Pembuktian

Langsung

Ubah premis ke dalam preposisi:– p: kucing di dalam rumah

– q: rumah tidak tenang

– p q: Jika kucing di dalam rumah, maka rumah tidak tenang (fakta)

– p: Kucing tidak ada di dalam rumah (fakta)

– q: Rumah pasti tenang (kesimpulan)Yang akan dibuktikan kebenarannya: fakta dan

kesimpulan, yaitu ((p q) p) q

Tabel Kebenaran

p q p q

p (p q) p

q (p q) p q

0 0 1 1 1 1 1

0 1 1 1 1 0 0

1 0 0 0 0 1 1

1 1 1 0 0 0 1

Tabel Kebenaran:

Kesimpulan Pembuktian Langsung

Hasil dari Tabel Kebenaran: Formula bukan tautologi

Berarti “kesimpulan bahwa rumah pasti tenang adalah” salah

Tabel Kebenaran:

Pembuktian tidak langsung

Menggunakan KontradiksiUbah premis ke dalam preposisi:– p: kucing di dalam rumah

– q: rumah tidak tenang

– p q: Jika kucing di dalam rumah, maka rumah tidak tenang (fakta)

– p: Kucing tidak ada di dalam rumah (fakta)

– q: Rumah pasti tenang (kesimpulan)

Tabel Kebenaran:

Pembuktian tidak langsung

Kesimpulan q: Rumah pasti tenang

Pembuktian tidak langsung dengan

Kontradiksi menggunakan negasi dari kesimpulan, yaitu:

– Rumah pasti tidak tenang ( q) = q

Yang akan dibuktikan kebenarannya:

fakta dan kontradiksinya, yaitu ((p q) p) q

Tabel Kebenaran:

Pembuktian tidak langsung

p q p q p (p q) p (p q) p q

0 0 1 1 1 0

0 1 1 1 1 1

1 0 0 0 0 0

1 1 1 0 0 0

Tabel Kebenaran:

Kesimpulan pembuktian tidak

langsung

Hasil dari tabel kebenaran: Formula bukan kontradiksi

(p q) p q diharapkan inkonsisten

Berarti “kesimpulan bahwa rumah pasti tenang adalah” salah

Tabel Kebenaran: Contoh Soal

Buktikan formula q r adalah kesimpulan dari premis p q dan p r

Solusi: periksa formula (p q) (p r) q r

Gunakan tabel kebenaran!

Tabel Kebenaran: Solusi

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

0 0 0 0 1 0 1

0 0 1 1 1 1 1

0 1 0 1 1 1 1

0 1 1 1 1 1 1

Tabel Kebenaran: Kesimpulan

Soal

Formula tersebut Tautology

Berarti formula tersebut Valid

Catatan: Pembuktikan dengan Tabel Kebenaran adalah mudah jika jumlah atom tidak banyak dan formula tidak rumit

Penyederhanaan/Normalisasi

Adalah cara pembuktikan dengan

menyambungkan premis-premis dengan operator logika

Selanjutnya disederhanakan kembali ke

dalam bentuk normal konjungsi atau

disjungsiGunakan ekivalensi logis

Umumnya subtitusikan formula dengan formula lainnya yang ekivalen

Normalisasi: Contoh

Harga saham turun apabila suku bunga naik. Banyak investor kecewa apabila harga saham turun. Pada saat ini suku bunga naik.

Kesimpulan: Investor kecewa (betulkah?)

Normalisasi: Contoh 2

Harga saham turun apabila suku bunga naik. Banyak investor kecewa apabila harga saham turun. Pada saat ini investor kecewa

Kesimpulan: suku bunga naik (betulkah?)

Normalisasi: Contoh

P1: Harga saham turun apabila suku bunga naik.

P2: Banyak investor kecewa apabila harga saham turun.

P3: Pada saat ini suku bunga naik.

C: Investor kecewa (betulkah?)

Normalisasi: Contoh

Ubah ke dalam bentuk simbol-simbol:

– s: harga saham turun

– p: suku bunga naik.

– u: banyak investor kecewa

Maka:

– P1: p s

– P2: s u

– P3: p

– C: u

((p s) (s u) p)

Ubah ke dalam

bentuk normal

Normalisasi: Contoh

((p s) (s u) p)((ps)(su)p)(p (ps)(su))((p p) (p s))(su)(0 (p s))(su)(p s)(su)(p s s) (p s u)(p 0) (p s u)0 (p s u)(p s u)

Normalisasi: Kesimpulan

((p s) (s u) p)– Bernilai benar

(p s u)– Bernilai benar juga

– Karena itu u harus bernilai benar

Karena u benar Kesimpulan benar

Aturan Inferensi

Asumsi terdapat himpunan preposisi yang terdiri dari sejumlah premis P1, P2, P3,.., Pn dan sebuah kesimpulan C.

Aturan inferensi digunakan untuk membuktikan kesimpulan C berdasarkan himpunan premis dalam bentuk rangkaian struktur pohon/tree

Aturan Inferensi: Contoh

Jika Tommy rajin bekerja, maka ia mendapat reputasi kerja yang baik. Jika Tommy memiliki reputasi kerja yang baik, maka karirnya akan meningkat dengan cepat. Karir Tommy mandeg. Oleh karenanya Tommy tidak rajin bekerja (Benarkah?)

Aturan Inferensi: Solusi

Definisikan:

– p: Tommy rajin bekerja

– q: mendapat reputasi kerja yang baik

– r: karirnya akan meningkat dengan cepat

Formula yang didapat:

– P1: p q

– P2: q r

– P3: r

Aturan Inferensi: Langkah-langkah

Langkah Alasan

1 pq Premis P1

2 qr Premis P2

3 pr Langkah 1,2: silogisme hipotetikal

4 r Premis P3

5 p Langkah 3,4: modus tollens

Aturan Inferensi: Langkah-langkah

Langkah Alasan

1 qr Premis P2

2 r Premis P3

3 q Langkah 1,2: modus tollens

4 p q Premis P1

5 p Langkah 3,4: modus tollens

Aturan Inferensi: Kesimpulan

Berdasarkan pembuktian di atas,

terbukti bahwa kesimpulan Tommy tidak rajin bekerja adalah benar

Aturan Inferensi

Adisi P

P Q

Simplifikasi PQ

P

Modus Ponens

P

PQ

Q

Modus Tollens

PQ

Q

P

Silogisme Disjungtif

P Q

P

Q

Silogisme Hipotetikal

PQ

QR

PR

Konjungsi P

Q

P Q

Prinsip Resolusi

P Q

P R

Q R