Bahasa

Tujuan pembicaraan kali ini adalah untuk menampilkan uatu bahasa daripada kalimat abstrak yang disebut dng ogika proposisional, dan juga memperkenalkan teknik ntuk menentukan apakah suatu kalimat abstrak yng di erikan itu valid atau contradictory dan apakah dua kali mat abstrak yg diberikan itu ekuivalen. Dengan metode ogika proposisional, kita dapat menentukan kebenaran an kesalahan daripada banyak kalimat konkrit hanya engan melihat bentuk mereka.

Kalimat abstrak dpt bernilai benar/valid atau kontradik ori dan dua kalimat abstrak dapat ekuivalen. Dibawah ni akan dibicarakan BAHASA, ARTI dari KALIMAT.

BahasaPertama dikenalkan simbol-simbol dasar dan menu njukkan bagaimana mereka dikombinasikan untuk membentuk kalimat (abstrak) daripada logika pro posisional. Disampaikan aturan sintaksis yang menjelaskan kom binasi apa daripada simbol-simbol yang diambil me njadi kalimat dalam bahasa tersebut. Disini belum di bicarakan apa arti dari kalimat tersebut.

Proposisi

Simbol-simbol dibawah ini, yang disebut proposisi digu nakan utk membangun suatu kalimat. Mereka adalah :

. Simbol kebenaran : true dan false ( benar dan salah). Untuk menyingkat digunakan T = true atau B = benar , F = false atau S = salah. . Simbol proposisional : p, q, r, p1, p2, ( huruf kecil p, q, r, dan dari mereka dng diberi indeks/ditambah dengan angka bilangan alam) Catatan : Ada beberapa buku yang menggunakan huruf besar P, Q, R, dan mereka dengan indeks.

Kalimat

mat dalam logika proposisional dibangun dari pro si-proposisi dng mengaplikasikan penghubung pro sional seperti : not, and, or, if-then, if-and-only-if

mat dibentuk menurut aturan sbb :

tiap proposisi, yaitu suatu simbol kebenaran atau mbol proposisional, adalah suatu kalimat.

ka P suatu kalimat, maka begitu juga negasinya, itu (not P)

ka P dan Q kalimat, maka begitu juga konjungsi a, yaitu (P and Q)

Kalimat

Lanjutan

. Jika P dan Q kalimat, maka begitu juga disjungsinya yaitu (P or Q)

. Jika P dan Q kalimat, maka begitu juga implikasibya yaitu (if P then Q) dimana P disebut anteseden dan Q disebut konsekuen

. Jika P dan Q kalimat, maka begitu juga bi-implikasi nya/ekuivalensinya, yaitu : (P if and only if Q) dimana P ruas kiri dan Q ruas kanan dp kalimat tsb

Contoh Diberikan : Ekspresi : P : {(not (p or q)) if and only if ((not p) and (not q))} adalah suatu kalimat, karena : p dan q adalah kalimat, jadi (p or q), (not p), (not q) kalimat, jadi (not (p or q)), ((not p) and (not q)) juga kalimat, jadi {(not (p or q)) if and only if ((not p) and (not q))} kalimat. Terdapat 8 kalimat (termasuk P) dan disebut dengan subkalimat daripada P. 7 diantara meraka yang per Tama s/d ketujuh disebut propesubkalimat.

NotasiKalimat : [If {(p or q) and (if q then r)} then {if (p and r) then (not r)}] dapat ditulis dengan bentuk ( struktur) : p or q and If q then r if (p and r) then not r

If Then

Notasi-1 bhs Inggris and or not if-then if-and-only-if Notasi dalam Indonesia konvensional dan atau & atau tidak atau jika-maka atau jika dan hanya jika atau

Contoh

Kalimat :

((not(p or q)) if and only if ((not p) and (not q)))dapat disajikan dengan

(( (p q)) q))) atau (( (p q))

((

p) (

(( p) ( q)))

Interpretasi[ Suatu interpretasi I adalah suatu assignment/ penentuan nilai kebenaran, baik true maupun false untuk setiap kumpulan daripada simbol-simbol proposisional; Interpretasi kosong adalah Interpretasi yang mengassign/menentukan suatu nilai kebenaran tidak pada satupun simbol proposisional (sama sekali) (the empty interpretation assigns a truth value to no propotitional symbols at all). Untuk setiap kalimat P, suatu interpretasi I dikatakan menjadi suatu interpretasi untuk P jika I mengasign suatu nilai kebenaran, baik true maupun false, pada setiap simbol proposisional daripada P.]

Contoh Pandang kalimat P : p or ( not q ) , salah satu interpretasi I untuk F adalah p = false dan q = true , yaitu I : p = true q = false interpretasi yang lain adalah I : p = false q = true Juga boleh mengassign kebenaran untuk simbolsimbol yang tidak terdapat pada suatu kalimat , misal nya I : p = false q = false r = true adalah merupakan interpretasi untuk P=(p or (not q)) ,walaupun P tidak memuat r.

Aturan SemantikAndaikan P suatu kalimat dan I adalah interpretasi untuk P. Maka nilai kebenaran daripada P (dan semua subkalimatnya) dengan interpretasi I ditentukan dengan menggunakan aturan-aturan semantik dibawah ini : Aturan proposisi. Nilai kebenaran daripada setiap simbol proposisional : p, q, r, .. dalam P adalah sama seperti nilai kebena ran yang di asign/diberikan padanya oleh I. Aturan true. Kalimat True adalah true/benar dalam I

Aturan Semantik - 1 Aturan falseKalimat False adalah false/salah dalam I Aturan not Negasi not P adalah true/benar jika P false/salah, dan false/salah jika P benar/true. Aturan and Konjungsi/Conjunction P and Q adalah true/benar jika P dan Q keduanya true/benar, dan false/salah jika tidak demikian ( yaitu jika P false/salah atau jika Q false/salah).

Aturan Semantik-2 Aturan or Disjungsi/Disjunction P or Q adalah true/benar jika P true/benar atau jika Q true/benar, dan false/salah jika tidak demikian ( yaitu jika P dan Q keduanya false/salah). Aturan if-then Implikasi/Implication if P then Q adalah true/benar jika P false/salah atau jika Q true/benar, dan false/salah jika tidak demikian ( yaitu jika P true/benar dan Q false/salah).

Aturan Semantik-3 Aturan if-and-only-if Ekuivalensi/equivalence P if and only if Q adalah true/benar jika nilai kebenaran daripada P sama seper ti nilai kebenaran daripada Q ( yaitu, jika P dan Q keduanya true/benar atau jika P dan Q keduanya salah), dan false/salah jika tidak demikian ( yaitu jika P true/benar dan Q false/salah atau jika P false/salah dan Q true/benar). Aturan if-then-else Nilai kebenaran daripada kondisional/conditional If F then G else H adalah nilai kebenaran daripada P jika Q true/benar dan nilai kebenaran daripada R jika P false/salah ).

RingkasanF true false P Q P and Q true true true true false false false true false false false falseF true true true true false false false false G true true false false true true false false

not F false true P or Q true true true false if P then Q P if and only if Q true true false false true false true trueif F then G else H true true false false true false true false

H true false true false true false true false

Properti Suatu KalimatDefinisi (Valid, Satisfiable, ekuivalens, konsisten). Kontradiksi, Implies,

Suatu kalimat P dikatakan valid/benar jika ia true/benar untuk setiap interpretasi (I) daripada P. Kalimat-kalimat valid daripada logika proposional disebut Tautologi. Suatu kalimat P dikatakan satisfiable/dapat-puas jika ia true dibawah suatu interpretasi (I) daripada P. Suatu kalimat P dikatakan kontradiksi/ contradictory ( unsatisfiable/tak terpenuhi) jika ia false dibawah setiap/semua interpretasi (I) daripada P.

Properti suatu Kalimat - 1 Suatu kalimat P implies suatu kalimat Q jika, untuk sebarang Interpretasi (I) daripada P dan Q, jika P true untuk I maka Q true untuk I. Dua kalimat P dan Q ekuivalen/ equivalent jika , dibawah setiap interpretasi (I) untuk P dan Q , P mempunyai nilai kebenaran yang sama dengan nilai kebenarannya Q. Seperangkat kalimat P1,P2,P3,. Dikatakan konsisten jika terdapat suatu interpretasi untuk P1,P2,P3,. Dibawah mana setiap Pi bernilai true.( i = 1, 2, 3, . . . .)

Contoh

* Kalimat p adlh satisfiable/terpenuhi karena ia true untuk sua tu interpretasi (I) yg memberikan nilai true utk p, ttpi ia tak valid. * Kalimat p or (not p) adlh satisfiable/terpenuhi dan juga valid * Kalimat p and (not p) adalah kontradiksi * Kalimat p and q adalah implies kalimat p, karena untuk setiap interpretasi (I) dimana (p and q) true, p juga true. * Kalimat p dan (not(not p) adalah ekuivalen. * Kalimat p dan q tidak ekuivalen.

Pohon Semantik1. Andaikan ingin membuktikan validitas kalimat : G : if ( If p then q) then (if (not p) then (not q)) p memp. dua kemungkinan nilai yaitu true dan false :1

p=true2

p = false3

dari kalimat G : if (if p then q) then ( if (not p) then (not q)) t t

Pohon Semantik-1 kalimat G : if (if p then q) then ( if (not p) then (not q)) t f t subkalimat G : ( if (not p) then (not q)) f t kalimat G : if (if p then q) then ( if (not p) then (not q)) t t t f t1 p=true 2 t (true) p=false 3

Pohon Semantik-2 Kalimat P: if (if p then q) then (if (not p) then(not q)) f f Kalimat G : if (if p then q) then ( if (not p) then (not q)) tf t f1 p=true t (true) 2 q=true 4 p=false 3 q=false 5

Pohon Semantik-3 Perhatikan pada Node 4 1 p=true 2 t (true) q=true 4 f (false) q=false 5 t (true) p=false 3

Pohon Semantik-4

1 q=true 2 kalimat H : kalimat H : if if t q then t q then t q = false 3 ( if p then q ). ? t ( if p then q ). t ? t

Pohon Semantik-5 1 q=true 2 kalimat H :t (true)

q=false 3 q then f 1

if t

( if p then q ). ? ? f

q=true 2 t (true)

q=false 3 t (true)

Pembuktian dengan Falsifikasi.dengan menggunakan aturan if-then maka antecedent (not p) or (not q) dan consequent {not(p and q)} masing-masing haruslah bernilai true dan false yaitu : Selanjutnya dari benarnya (not p) or (not q) kita tak dapat menyimpulkan tentang (not p) maupun (not q) sehingga kita beralih ke salahnya not(p and q) ; karena not ( p and q)= false maka (p and q), dengan aturan not, bernilai true , seterusnya p and q berarti, dengan aturan and p dan q harus bernilai true, didapat : Dari label terlihat bahwa p pada antecedent bernilai true, jadi (not p) bernilai false; begitu pula untuk (not q) akan bernilai false. Kesimpulan dari ini semua adalah antecedent, dengan aturan or, bernilai false. Tetapi disepan dikatakan bahwa antecedent bernilai true, sehingga terjadi kontradiksi ( tf ) yang berarti pengandaian bahwa kalimat salah adalah tidak benar, ini dapat disimpulkan bahwa kalimat E bernilai true yaitu kalimat valid.

Contoh-1 E : if {(not p) or (not q)} then {not(p and q)} f E : if {(not p) or (not q)} then {not(p and q)} f t f E : if {(not p) or (not q)} then {not( p and q)} f t t t f t t ( E : if {(not p) or (not q)} then {not( p and q)} ) f f t tf f t f t t

Contoh-1(lanjt)

( E : if {(not p) or (not q)} then {not( p and q)} ) f f t tf f t f t t Jadi dari pengandaian ketidak-benarnya kalimat E, mengakibatkan terjadi tf , yaitu true sekaligus false yg berarti ada kontradiksi sehingga pengandaian diatas (bahwa kalimat E false) dicabut, yang berarti kalimat E true

Contoh-2 Kalimat F : (if p then q) if and only if ((not p) or q) Andaikan F false maka akan dibuktikan terjadi kontra diksi dibawah suatu interpretasi. 1. Menurut aturan if-and-only-if maka F dapat false untuk dua kemungkinan, yaitu : (a) ruas kiri true dan ruas kanan false, (b) ruas kiri false dan ruas kanan true. 1. Kasus pertama yaitu if p then q adalah true dan ((not p) or q) adalah false, kita tulis sbb : (if p then q) if and only if ((not p) or q) t f f

Contoh-2 (lanjt)

Kalimat F : (if p then q) if and only if ((not p) or q) 3. Dari : (if p then q) if and only if ((not p) or q) t f f

Jika subkalimat (if p then q), ruas kiri, true maka kita tidak dapat menentukan nilai p dan q, sehingga kita lihat subkalimat ((not p) or q), ruas kanan, false; dengan demikian subkalimat dari subkalimat kanan, yaitu not p dan q harus dua-duanya false. Karena not p false mala p true.

Didapat : (if p then q) if and only if ((not p) or q)

tf t

f

f

f t f f

Kesimpulan terjadi kontradiksi untuk kasus pertama maka haruslah kalimat F true.

Contoh-2 (lanjt)

Selanjutnya kasus kedua yaitu : if p then q adalah false dan ((not p) or q) adalah true, kita tulis sbb : (if p then q) if and only if ((not p) or q) f f tPada subkalimat , ruas kiri, (if p then q) false, maka jelaslah bahwa p bernilai true dan q bernilai false,

sehingga : (if p then q) if and only if ((not p) or q) f t f f f t tf f

Kesimpulan terjadi kontradiksi untuk kasus kedua maka kalimat F true. Dari dua kasus tersebut maka disimpulkan F true

Contoh-31. Apakah kalimat diobawah ini valid atau tak valid :

G : if

{if p then q}

then {if (not p) then (not q)}Andaikan false maka : antecedentnya t dan konsekuen nya false jadi :

1.

if {if p then q} then {if (not p) then (not q)} f t f

2.

if {if p then q} then {if (not p) then (not q)} f t fdibenarkan.

t

f t f

f t

3. Kesimpulan memang benar bahwa kalimat G false, pengandai an

Soal 1. Apakah kalimat dibawah ini valid atau tak valid : G : if {if(not p) then q}

then {if (not q) then p } and (p or q) 2. Apakah kalimat/formula dibawah ini tautologi : ( a ) (p q) p ; ( c ) (p ( p q)) q ; (b) (p q) q (d) ( p) p

( e ) (pq)((pq)(qp) ; (f) (p ( p) (q ( q)) 3. Buktikan bahwa : p (q r) (pq) r ; dengan tidak menggunakan tabek kebenaran 4. Seperti diatas untuk : ( p ( q r)) (qr)(pr)r

Soal-1 1. Tunjukan bahwa nilai kebenaran rumusan pernyata an berikut ini tak tergantung pada komponen-kom ponennya : a. (p (p b. (p q) ( p q) c. ((p q) (q r)) (p r) 2. Buktikan ekuivalensi berikut ini tanpa menggunakan tabel kebenaran . a) p(qr) (pq) (pr) ; b) (p q) (p q) ( p q) c) (p q) (p ( q)) ( p q) 3. Buktikan soal nomor 2 diatas dng tabel kebenaran. 4. Tunjukan rumusan ini merupakan tautologi : a) (p q) (p q); b) p (q p) ;