Algoritma & Struktur Data
sub : Logika Proposisional
Logika
• Berguna untuk melakukan penalaran matematika
• Digunakan dalam mendesain rangkaian elektronik.
• Logika adalah suatu sistem yang didasarkan pada proposisi.
• Suatu 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 suatu proposisi adalah :
– benar (T) atau salah (F).
• Dalam rangkaian digital, nilai ini dinyatakan sebagai 1 dan 0
Proposisi atau Pernyataan
contoh 1:
“Gajah lebih besar daripada tikus.”
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? YA
Apakah nilai kebenaran dari proposisi ini? BENAR [ True ]
Proposisi atau Pernyataan
contoh 2
“520 < 111”
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? YA
Apakah nilai kebenaran dari proposisi ini? SALAH [ False ]
Proposisi atau Pernyataan
contoh 3
“y > 5”
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? 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
contoh 4
“Sekarang tahun 2007 dan 99 < 5.”
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? YA
Apakah nilai kebenaran dari proposisi ini? SALAH
Proposisi atau Pernyataan
contoh 5
“Tolong untuk tidak tidur selama kuliah”
Apakah ini sebuah pernyataan? TIDAK Ini adalah sebuah permintaan.
Apakah ini sebuah proposisi? TIDAK Hanya pernyataan yang bisa menjadi proposisi.
Proposisi atau Pernyataan
contoh 6
“Jika gajah berwarna merah, mereka dapat berlindung di bawah pohon cabe.”
Apakah ini pernyataan? yes
Apakah ini proposisi? yes
Apa nilai kebenaran proposisi tersebut ? probably false
Proposisi atau Pernyataan
contoh 7
“x < y jika dan hanya jika y > x.”
Apakah ini pernyataan ? YA
Apakah ini proposisi ? YA … karena nilai kebenarannya
tidak bergantung pada nilai X maupun Y.
Apakah nilai kebenaran dari proposisi ini ? BENAR
Menggabungkan Proposisi
Beberapa contoh sebelumnya menunjukkan bahwa beberapa proposisi dapat digabung menjadi sebuah proposisi gabungan Æ proposisi majemuk ( compound proposition ).
Selanjutnya notasi proposisi di-formal-kan dengan menggunakan alfabet / huruf-huruf; seperti p, q, r, s; dan dengan memperkenalkan : operator-operator logika.
Operator logika
Kita akan membahas operator-operator berikut:
1. Negasi (NOT)
2. Konjungsi - Conjunction (AND)
3. Disjungsi - Disjunction (OR)
4. Eksklusif OR (XOR)
5. Implikasi (jika – maka)
6. 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.
Operator logika XOR
Gerbang logika XOR (exclusive OR)
Eksklusif OR.
Gerbang ini mempunyai dua state masukan. (Masing-masing state mempunyai nilai biner, yang merepresentasikan suatu nilai logika, yaitu TRUE dan FALSE).
Kunci dari gerbang ini adalah, outputnya akan bernilai TRUE, jika salah satu dari dua inputnya bernilai TRUE.
1. Negasi (NOT) (Ingkaran, atau Penyangkalan)
Operator Uner, Lambang/simbol : ¬
| P | ¬P |
| BENAR | SALAH |
| SALAH | BENAR |
2. Konjungsi (AND)
Operator Biner, Lambang: ∧
| P | Q | P^Q |
| Benar | Benar | Benar |
| Benar | Salah | Salah |
| Salah | Benar | Salah |
| Salah | Salah | Salah |
3. Disjungsi (OR)
Operator Biner, Lambang: ∨
| P | Q | PVQ |
| Benar | Benar | Benar |
| Benar | Salah | Benar |
| Salah | Benar | Benar |
| Salah | Salah | Salah |
4. Eksklusif Or (XOR)
Operator Biner, Lambang: ⊕
| P | Q | P⊕Q |
| Benar | Benar | Salah |
| Benar | Salah | Benar |
| Salah | Benar | Benar |
| Salah | Salah | Salah |
5. Implikasi (jika - maka)
Operator Biner, Lambang: →
Implikasi p → q adalah proposisi yang bernilai salah jika p benar dan q salah, dan bernilai benar jika lainnya.
| P | Q | P→Q |
| Benar | Benar | Benar |
| Benar | Salah | Salah |
| Salah | Benar | Benar |
| Salah | Salah | Benar |
0 komentar:
Posting Komentar