Logika Proposisi
Adri Priadanailkomadri.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”
Nilai kebenaran dari pernyataan tersebut
bergantung pada y, tapi nilainya belum
ditentukan.
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? TIDAK
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”
TIDAK
TIDAK
Hanya pernyataanlah yang bisa menjadi
proposisi.
Ini adalah sebuah permintaan.
Apakah ini sebuah pernyataan?
Apakah ini sebuah proposisi?
Proposisi atau Pernyataan ?“x < y jika dan hanya jika y > x.”
Apakah ini pernyataan ? YA
Apakah ini proposisi ? YA
Apakah nilai kebenaran
dari proposisi ini ? BENAR
… karena nilai kebenarannya
tidak bergantung harga
spesifik x maupun y.
Penggabung Preposisi
Beberapa contoh terdahulu menunjukkan bahwa beberapa proposisi dapat digabung menjadi sebuah proposisi gabungan.
Hal ini kita formal-kan dengan melambangkan proposisi sebagai huruf-huruf; 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 operator-
operator 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
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 dan operator-operator dapat digabungkan
menjadi suatu pernyataan baru.
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
didasarkan pada tautologi (p ˄ (p → q)) → q
dalam hal ini p dan p → q adalah hipotesis,
q adalah konklusi.
q
p
qp
Inferensi
2. Modus Tollen
didasarkan pada tautologi (~q ˄ (p → q)) → ~p
dalam hal ini ~q dan p → q adalah hipotesis,
~p adalah konklusi.
p
q
qp
Inferensi
3. Silogisme Hipotesis
didasarkan pada :
tautologi ((p → q) ˄ ((q → r)) → (p → r)
rp
rq
qp
Inferensi
4. Silogisme Disjungitf
didasarkan pada :
tautologi ((p ˅ q) ˄ ~p) → q
pq
qp
qpqp
Inferensi
5. Simplifikasi
didasarkan pada :
tautologi (p ˄ q) → p
qp
qpqp
Inferensi
5. Penjumlahan
didasarkan pada :
tautologi p → (p ˅ q)
qpqp
qp
Matur Nuwun