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