Logika Proposisional

STSI4106 · Logika Informatika · Sesi 1 — Materi Inisiasi

Kalimat Logika Proposisional, Aturan Sintaktik, dan Interpretasi

Logika proposisional membangun kalimat dari proposisi dan penghubung proposisional, memeriksa keabsahannya lewat tujuh aturan sintaktik, lalu memberi makna pada kalimat itu lewat interpretasi.

Program Studi Sistem Informasi · Fakultas Sains dan Teknologi · Universitas Terbuka

01 · Bahasa Logika Proposisional

Kalimat dan Proposisi

Tidak semua kalimat bisa diolah logika. Hanya kalimat deklaratif — yang nilai kebenarannya bisa ditentukan — yang disebut proposisi.

Kalimat Deklaratif

  • Merupakan fakta
  • Dapat ditentukan nilai kebenarannya (benar/salah)

Kalimat Non-Deklaratif

  • Bukan fakta
  • Tidak dapat ditentukan nilai kebenarannya
Proposisi adalah kalimat deklaratif yang memiliki nilai kebenaran true atau false — hanya satu, tidak keduanya sekaligus.

Coba periksa beberapa kalimat

Proposisi

Merupakan fakta objektif dengan nilai kebenaran yang sudah diketahui, yaitu benar.

01 · Bahasa Logika Proposisional

Simbol dan Penghubung Proposisional

Proposisi dituliskan dengan simbol, lalu disatukan lewat penghubung proposisional untuk membentuk kalimat yang lebih kompleks.

Simbol Proposisional

Ditulis dengan huruf kapital, dengan atau tanpa indeks numerik.

P, Q, R, S  ·  P1, Q1, R1, S1

Simbol Kebenaran

Menuliskan nilai kebenaran suatu proposisi secara utuh.

true, false

Enam penghubung proposisional

not

Aturan Negasi. Contoh: not P.

02 · Aturan Sintaktik

Tujuh Aturan Sintaktik

Tujuh aturan ini menentukan kapan suatu untai simbol sah disebut kalimat logika proposisional, dari proposisi tunggal sampai kondisional bercabang.

I. Aturan Proposisi

Setiap proposisi merupakan kalimat.

Langkah Pemeriksaan Kalimat

  1. Perhatikan simbol-simbol dalam ekspresi. Periksa apakah simbol kebenaran atau simbol proposisi, lalu periksa Aturan I.
  2. Perhatikan penghubung proposisional dalam ekspresi, lalu periksa apakah memenuhi Aturan II–VII.
Contoh 2.1 — Apakah E: not P kalimat logika proposisional? +
P adalah simbol proposisi, sehingga menurut Aturan I, P adalah kalimat. Karena P kalimat, menurut Aturan Negasi, not P juga merupakan kalimat.
Contoh 2.2 — Apakah F: if P then (Q or not P) kalimat logika proposisional? +
P dan Q simbol proposisi, keduanya kalimat menurut Aturan I. not P kalimat menurut Aturan Negasi. Q or not P kalimat menurut Aturan Disjungsi. Karena P dan (Q or not P) kalimat, maka if P then (Q or not P) kalimat menurut Aturan Implikasi.

02 · Aturan Sintaktik

Kalimat Bagian

Kalimat bagian adalah seluruh kalimat — dari simbol terkecilnya sampai kalimat lengkap — yang menyusun sebuah kalimat logika proposisional.

Langkah Penentuan Kalimat Bagian

  1. Perhatikan simbol logika proposisional. Periksa apakah simbol kebenaran atau simbol proposisi, dan periksa Aturan I.
  2. Perhatikan penghubung proposisional. Periksa apakah memenuhi Aturan II–VII.
  3. Susun daftar semua kalimat yang terbentuk dari langkah 1 dan 2.
Contoh 2.3 — Kalimat bagian dari E: not P +
Simbol dalam E adalah P (kalimat, Aturan I). Penghubungnya not (Aturan Negasi). Jadi kalimat bagian dari E adalah {P, not P}.
Contoh 2.4 — Kalimat bagian dari F: if P then (P or not P) +
Simbol dalam F adalah P (kalimat, Aturan I). Penghubungnya not, or, dan if-then. Jadi kalimat bagian dari F adalah {P, not P, P or not P, if P then (P or not P)}.

03 · Notasi

Notasi dan Konversinya

Kalimat yang sama bisa ditulis dalam tiga notasi — matematika, pseudocode, dan function — dan ketiganya bisa saling dikonversi mengikuti tabel padanan.

Notasi Matematika
Notasi Pseudocode
Notasi Function
¬P
not P
not(P)

Simbol proposisi (P, Q, R, S) ditulis sama pada ketiga notasi. Simbol kebenaran (true, false) hanya dikenal pada notasi pseudocode dan function.

Langkah Konversi Notasi

  1. Perhatikan penghubung dalam kalimat.
  2. Lakukan konversi sesuai tabel padanan di atas.
Contoh 3.1 — Ubah E: not (P or Q) ke notasi matematika dan function +
Notasi matematika dari not adalah ¬ dan or adalah ∨, sehingga notasi matematika E adalah ¬(P ∨ Q). Notasi function-nya adalah not(or(P, Q)).

04 · Interpretasi

Interpretasi

Interpretasi memberi nilai kebenaran true atau false pada tiap simbol proposisional dalam suatu kalimat, sehingga kalimat itu bisa dinilai benar atau salah.

Format penulisan interpretasi I untuk kalimat F: I: {P←true, Q←false} — artinya memberi nilai true ke P dan false ke Q.

Langkah Penentuan Interpretasi

  1. Tentukan simbol proposisional dalam kalimat.
  2. Berikan nilai kebenaran pada tiap simbol proposisional tersebut.
  3. Tuliskan interpretasinya dalam format I: {...}.

Banyak interpretasi yang mungkin: 2n

dengan n = banyak simbol proposisional berbeda dalam kalimat. Pilih n untuk melihat hasilnya:

23 = 8 — misalnya untuk kalimat G dengan simbol P, Q, R, ada 8 interpretasi yang mungkin.

Langkah Pemeriksaan Interpretasi

  1. Tentukan simbol proposisional dalam kalimat.
  2. Periksa apakah semua simbol proposisional itu sudah diberi nilai kebenaran dalam interpretasi. Jika ya, interpretasi bersesuaian dengan kalimat; jika belum lengkap, interpretasi tidak bersesuaian.
Contoh 4.1 — Tentukan suatu interpretasi untuk E: not P +
Simbol proposisional dalam E adalah P. Misalkan P diberi nilai true, sehingga interpretasinya I: {P←true}.
Contoh 4.2 — Semua interpretasi yang mungkin untuk E: not P +
Hanya ada satu simbol proposisional (P), jadi ada 21 = 2 interpretasi yang mungkin: I₁: {P←true} dan I₂: {P←false}.
Contoh 4.3 — Apakah I: {P←true} merupakan interpretasi untuk E: if Q then not P? +
Simbol proposisional dalam E adalah P dan Q. Interpretasi I hanya memberi nilai pada P, sedangkan Q belum diberi nilai. Jadi, I bukan interpretasi untuk kalimat E.

Bacaan Lanjutan

Referensi Rekomendasi

Modul resmi mata kuliah dan tiga rujukan pelengkap untuk memperdalam aturan sintaktik, notasi, dan interpretasi kalimat logika proposisional.

Suprapto. (2020). Logika Informatika (Buku Materi Pokok). Tangerang Selatan: Universitas Terbuka.

Modul resmi mata kuliah STSI4106 — sumber utama seluruh materi Sesi 1 ini.

Bergmann, M., Moor, J., & Nelson, J. (2014). The Logic Book (6th ed.). New York: McGraw-Hill.

Rujukan standar untuk pembentukan kalimat logika proposisional secara formal, termasuk aturan sintaktik.

mheducation.com/highered/product/logic-book-bergmann-moor

Rosen, K. H. Discrete Mathematics and Its Applications. New York: McGraw-Hill.

Referensi pelengkap untuk notasi, tabel kebenaran, dan interpretasi proposisi.

mheducation.com/highered/product/discrete-mathematics-and-its-applications-rosen

Wooldridge, M. (2000). Lecture 07: Propositional Logic (1).

Catatan kuliah yang menjadi salah satu rujukan slide sesi ini.

cs.ox.ac.uk/people/michael.wooldridge/teaching/soft-eng/lect07.pdf