the logical basis for computer programming

Richard WaldingerRichard WaldingerZohar MannaZohar Manna

LOGIKA & ALJABAR BOOLEAN

PendahuluanPendahuluanKebenaran suatu pernyataan bisa

ditentukan dari strukturnya saja, tanpa harus tahu kebenaran pembentuk-pembentuknya (constituents).

Seperti P or (not P) dan setiap pernyataan dengan bentuk serupa adalah benar, tidak peduli apakah P benar atau salah.

Suatu kalimat abstrak adalah valid jika bernilai benar tanpa mempedulikan kebenaran atau kesalahan dari proposisi-proposisi pembentuknya.

Pendahuluan (CONT)Sebagai contoh, jika kita tahu bahwa kalimat

abstraknot ( P and (not P) ) or Q

valid, maka kita bisa dengan cepat menyimpulkan bahwa kalimat-kalimat kongkrit

not ( [x 0] and (not [x 0]) ) or ( y 0 )bernilai true (benar), tanpa harus tahu apakah x 0 dan y 0 bernilai true atau false (salah).

Pendahuluan (CONT)Sebaliknya, setiap instance dari suatu

kalimat abstrak sepertiP and (not P)

bernilai false tanpa harus tahu apakah P bernilai true atau false. Selanjutnya, kalimat semacam ini akan disebut kalimat contradictory. Perhatikan bahwa suatu kalimat F adalah valid precisely when (ketika secara pasti) negasi (negation) nya, yaitu (not F) adalah contradictory.

Pendahuluan (CONT)Di samping itu, banyak kalimat-kalimat abstrak seperti

P or Q dan not Ptidak valid maupun tidak contradictory; karena mereka mempunyai instances yang bisa bernilai true atau false.

Pendahuluan (CONT)Kemudian ada pasangan kalimat-kalimat abstrak

sepertiif P then Q dan if (not Q) then (not

P),adalah ekuivalen, dalam pengertian bahwa suatu instance konkrit salah satu dari keduanya bernilai true precisely when contoh yang bersesuaian dari satunya bernilai true. Sebagai contoh, dua kalimat kongkrit “Jika seorang mahasiswa mengikuti ujian akhir suatu matakuliah, maka mahasiswa tersebut akan mendapat nilai untuk matakuliah tersebut.”dan“Jika seorang mahasiswa tidak mendapat nilai suatu matakuliah, maka mahasiswa tersebut tidak mengikuti ujian akhir untuk matakuliah tersebut.”adalah contoh dari pasangan kalimat di atas dan keduanya bernilai true. Akan tetapi keduanya tidak valid.

BahasaBahasa Seperti halnya bahasa pada umumnya,

maka logika proposisional terdiri dari kalimat-kalimat (sentences), khususnya kalimat abstrak (abstract sentence).

Aturan sintaktik (syntactic rules) menerangkan tata cara pembentukan kalimat dalam logika proposisional ( pengertiannya sesuai dengan aturan sintaktik dalam setiap bahasa pemrograman (programming language) ).

Bahasa (propositionsBahasa (propositions ))Kalimat-kalimat dalam (bahasa) logika proposisional

dibentuk dari simbol-simbol, yang disebut proposisi (propositions). Simbol-simbol yang dimaksud dikelompokkan menjadi dua, yaitu :Simbol-simbol kebenaran (truth symbols)

true dan falseSimbol-simbol proposisional (propositional symbols)

P, Q, R, S, P1, Q1, R1, S1, P2, Q2, R2, S2, ...(huruf-huruf besar P, Q, R, atau S, dan mungkin dengan indeks-indeks numerik).

Dalam pembicaraan tidak resmi, huruf-huruf skrip E, F, G, dan H, dan mungkin dengan subskrip (indeks) numerik akan digunakan untuk menyatakan kalimat.

Bahasa (Bahasa (Kalimat)Kalimat)Kalimat-kalimat dalam logika proposisional

dibangun dari proposisi-proposisi dengan menerapkan propositional connectives :not, and, or, if-then, if-and-only-if, if-then-else

Kalimat dibentuk menurut aturan-aturan (rules) berikut :setiap proposisi, yaitu suatu simbol kebenaran

atau suatu simbol proposisi merupakan kalimat.

apabila F kalimat, maka demikian juga negasi (negation) nya (not F).

apabila F dan G kalimat, maka demikian juga konjungsi (conjunction) nya, yaitu (F and G), selanjutnya F maupun G disebut conjuncts dari (F and G).

Kalimat (CONT)Kalimat (CONT)Kalimat dibentuk menurut aturan-aturan (rules)

berikut :apabila F dan G kalimat, maka demikian juga disjungsi

(disjunction) nya, yaitu (F or G), selanjutnya F maupun G disebut disjuncts dari (F or G).

apabila F dan G kalimat, maka demikian juga implikasi (implication) nya, yaitu (if F then G). Selanjutnya F disebut antecedent dan G disebut consequent dari (if F then G). Kalimat (if G then F) disebut converse dari kalimat (if F then G).

apabila F dan G kalimat, maka demikian juga ekuivalensi (equivalence) nya, yaitu (F if and only if G), selanjutnya F disebut sisi-kiri (left-hand side) dan G disebut sisi-kanan (right-hand side) dari (F if and only if ). G

apabila F, G dan H kalimat, maka demikian juga kondisional (conditional) nya, yaitu (if F then G else H). Selanjutnya F, G, dan H masing-masing disebut klausa-if (if-clause), klausa-then (then-clause), dan klausa-else (else-clause) dari kondisional (if F then G else H).

Kalimat (Contoh-contoh)Ekspresi berikut

E : ((not(P or Q)) if and only if ((not P) and (not Q)))merupakan kalimat (sentence), karena

P dan Qkeduanya merupakan kalimat, jadi

(P or Q), (not P), dan (not Q)merupakan kalimat, sehingga

(not (P or Q)) and ((not P) and (not Q))merupakan kalimat, jadi ekspresi E,((not(P or Q)) if and only if ((not P) and (not Q))),merupakan kalimat.

NotasiNotasi

(not (P and (not Q)))

not (P or Q) if and only if

(not P) and (not Q)

(if ((P or Q) and (if Q then R)) then (if (P and Q)

then (not R)))

Notasi (cont)(if ((P or Q) and (if Q then R)) then (if (P and Q)

then (not R)))

bisa ditulis sebagai berikut :

Notasi(konvensional)

Notasi yang Notasi yang digunakandigunakan

Notasi Notasi konvensional konvensional

and atau &

or not ~ atau

if – then atau

if and only if atau

if – then - else tidak ada ((~(P Q)) ((~P) (~Q)), dan

(((P Q) (Q R)) ((P R) (~R)))

Nilai (arti) sebuah Nilai (arti) sebuah KalimatKalimat

Memperlihatkan bagaimana memberi (atau memasang) nilai-nilai kebenaran (truth values),

true atau false,ke kalimat logika proposisional.

Apakah nilai kebenaran suatu kalimat seperti (P or (not Q)) adalah true atau false jika diketahui apakah nilai-nilai kebenaran dari simbol-simbol proposisional P dan Q itu sendiri true atau false.

Informasi ini disediakan oleh suatu interpretation.

InterpretasiInterpretasi Suatu interpretasi I merupakan suatu pemberian

(assignment) suatu nilai kebenaran, true atau false, ke masing-masing himpunan simbol-simbol proposisional; interpretasi kosong (empty interpretation) tidak memberi nilai kebenaran ke suatu simbol proposisional manapun.

Untuk sebarang kalimat F, suatu interpretasi I dikatakan sebagai interpretasi untuk (interpretation for) F jika I memberi suatu nilai kebenaran, true atau false, ke masing-masing simbol proposisional dari F.

Sebagai contoh, perhatikan kalimat F : P or (not Q)

Salah satu interpretasi untuk F memberi nilai false ke P dan nilai true ke Q, yaitu :

Interpretasi (cont)Interpretasi (cont)Interpretasi lain untuk F adalah :

Selanjutnya bisa dikatakan bahwa P bernilai false dan Q bernilai true di bawah (under) I1 dan P bernilai false dan Q bernilai false under I2.

Aturan-aturan Aturan-aturan SemantikSemantikMenjelaskan bagaimana cara menentukan nilai kebenaran suatu kalimat (sentence), atau aturan-aturan (rules) apa saja yang diperlukan untuk menentukan nilai kebenaran dari suatu kalimat.

Aturan-aturan Semantik Aturan-aturan Semantik (cont)(cont)Misal E suatu kalimat dan I merupakan

suatu interpretasi untuk E. Maka nilai kebenaran dari E (dan semua kalimat-kalimat bagiannya) di bawah I ditentukan dengan menerapkan secara berulang-ulang aturan-aturan semantik berikut :

aturan proposisinilai kebenaran dari masing-masing simbol proposisional P, Q, R, ... dalam E sama dengan nilai kebenaran yang diberikan oleh I pada simbol tersebut.

Aturan-aturan Semantik Aturan-aturan Semantik (cont)(cont)aturan true

kalimat true bernilai true under I.aturan false

kalimat false bernilai false under I.aturan not

negasi (negation) dari F (yaitu, not F) bernilai true jika F false, dan bernilai false jika F true.

aturan andkonjungsi (conjunction) (yaitu, F and G)

bernilai true jika kedua F dan G bernilai true, sebaliknya bernilai false (yaitu, jika F false atau G false).

aturan ordisjungsi (disjunction) (yaitu, F or G)

bernilai true jika F true atau G true, dan sebaliknya bernilai false (yaitu, F dan G G bernilai false).

Aturan-aturan Semantik Aturan-aturan Semantik (cont)(cont)aturan if-then

implikasi (implication) (yaitu, if F then G) bernilai true jika F false atau G true, dan sebaliknya bernilai false (yaitu, jika F true dan G false).

aturan if-and-only-ifekuivalensi (equivalence) (yaitu, F if and only

if G) bernilai true jika nilai kebenaran F sama dengan nilai kebenaran G (yaitu, jika F dan G keduanya bernilai true atau jika F dan G keduanya bernilai false), dan sebaliknya bernilai false (yaitu, jika F true dan G false atau jika F false dan G true).

aturan if-then-elsenilai kebenaran dari kondisional (conditional)

(yaitu, if F then G else H) adalah sama dengan nilai kebenaran dari G jika F bernilai true, dan sama dengan nilai kebenaran dari H jika F bernilai false.

Sifat-sifat KalimatSifat-sifat KalimatSuatu kalimat F dikatakan valid jika F

bernilai true di bawah (under) setiap interpretasi untuk F . Kalimat valid dalam logika proposisional kadang-kadang disebut tautologies.

Suatu kalimat F dikatakan satisfiable jika F bernilai true di bawah suatu interpretasi untuk F .

Suatu kalimat F dikatakan contradictory (atau unsatisfiable) jika F bernilai false di bawah setiap interpretasi untuk F .

Sifat-sifat KalimatSifat-sifat KalimatSuatu kalimat F implies kalimat G jika

untuk setiap interpretasi I sekaligus untuk F dan G. Jika F bernilai true di bawah I maka G juga bernilai true di bawah I.

Dua kalimat F dan G dikatakan equivalent jika di bawah setiap interpretasi I untuk F dan G, F mempunyai nilai kebenaran sama dengan nilai kebenaran G

Suatu kumpulan kalimat-kalimat F1, F2, ... dikatakan consistent jika ada beberapa interpretasi untuk F1, F2, ... di mana masing-masing Fi bernilai true.

Catatan ((satisfiable dan validsatisfiable dan valid)) Suatu kalimat F satisfiable precisely when

negasinya (not F) tidak valid.Diketahui bahwa

F satisfiable precisely when (dengan definisi satisfiabilitas) bernilai true di bawah suatu interpretasi Iprecisely when (dengan aturan not)(not F) bernilai false di bawah suatu interpretasi Iprecisely when (dengan definisi validitas)(not F) tidak valid.