Logika Proposisi Adri Priadana ilkomadri.com
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)
Matematika Diskrit
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 Teknik Informatika atau ilmu komputer. Basic algoritma, struktur data, basis data, otomata dan teori bahasa formal, jaringan komputer, keamanan komputer, sistem operasi, teknik kompilasi, dsb.
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
Proposisi atau Pernyataan ? “Gajah
lebih besar daripada tikus.”
Apakah ini sebuah pernyataan?
YA
Apakah ini sebuah proposisi?
YA
Apakah nilai kebenaran dari proposisi ini?
BENAR
Proposisi atau Pernyataan ? “520
< 111”
Apakah ini sebuah pernyataan?
YA
Apakah ini sebuah proposisi?
YA
Apakah nilai kebenaran dari proposisi ini?
SALAH
Proposisi atau Pernyataan ? “y
> 5”
Apakah ini sebuah pernyataan? Apakah ini sebuah proposisi?
YA TIDAK
Nilai kebenaran dari pernyataan tersebut bergantung pada y, tapi nilainya belum ditentukan.
Pernyataan jenis ini kita sebut sebagai fungsi proposisi atau kalimat terbuka.
Proposisi atau Pernyataan ? “Sekarang
tahun 2004 dan 99 < 5.”
Apakah ini sebuah pernyataan?
YA
Apakah ini sebuah proposisi?
YA
Apakah nilai kebenaran dari proposisi ini?
SALAH
“Tolong
untuk tidak tidur selama kuliah”
Apakah ini sebuah pernyataan?
TIDAK
Ini adalah sebuah permintaan.
Apakah ini sebuah proposisi?
TIDAK
Hanya pernyataanlah yang bisa menjadi proposisi.
Proposisi atau Pernyataan ? “x
< y jika dan hanya jika y > x.”
Apakah ini pernyataan ? Apakah ini proposisi ? … karena nilai kebenarannya tidak bergantung harga spesifik x maupun y. Apakah nilai kebenaran dari proposisi ini ?
YA YA
BENAR
Penggabung Preposisi
Beberapa contoh terdahulu menunjukkan bahwa beberapa proposisi dapat digabung menjadi sebuah proposisi gabungan.
Hal ini kita formal-kan dengan melambangkan proposisi sebagai hurufhuruf; seperti p, q, r, s; dan memperkenalkan operator-operator logika.
Operator Logika
Kita 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 operatoroperator 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 jika dan hanya jika q” dapat dibaca “jika p maka q dan jika q maka 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 Pernyataan-pernyataan dan operator-operator dapat digabungkan menjadi suatu pernyataan baru.
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 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 Suatu tautologi adalah pernyataan yang selalu bernilai benar Contoh:
R(R)
Jika ST sebuah tautologi, kita tulis S T. JIka ST sebuah tautologi, kita tulis S T.
Kontradiksi Suatu kontradiksi adalah pernyataan yang selalu bernilai salah. Contoh:
R(R)
Negasi dari sebarang tautologi adalah sebuah kontradiksi, sebaliknya, negasi dari sebuah kontradiksi adalah sebuah tautologi.
Inferensi Apabila kita diberikan beberapa proposisi atau deret proposisi, kita dapat menarik kesimpulan baru dari proposisi-proposisi tersebut. Proses penarikan kesimpulan dari beberapa proposisi tersebut disebut sebagai inferensi.
Inferensi 1. Modus Ponen
pq p q didasarkan pada tautologi (p ˄ (p → q)) → q dalam hal ini p dan p → q adalah hipotesis, q adalah konklusi.
Inferensi 2. Modus Tollen
pq q
p didasarkan pada tautologi (~q ˄ (p → q)) → ~p dalam hal ini ~q dan p → q adalah hipotesis, ~p adalah konklusi.
Inferensi 3. Silogisme Hipotesis
pq qr pr didasarkan pada : tautologi ((p → q) ˄ ((q → r)) → (p → r)
Inferensi 4. Silogisme Disjungitf
pq p
pq q
q
p
didasarkan pada : tautologi ((p ˅ q) ˄ ~p) → q
Inferensi 5. Simplifikasi
pq
pq
p
q
didasarkan pada : tautologi (p ˄ q) → p
Inferensi 5. Penjumlahan
p
q
pq
pq
didasarkan pada : tautologi p → (p ˅ q)
Matur Nuwun