ilmu kom puter fak mipa ugm

ILMUKOM

PUTER

FAKMIPAUGM

Logika Informasi

Materi.

1). Logika Proposisi. a). Pengenalan Informal b). Penghubung Logis (Operator, Functor) c). Tabel Kebenaran dp Formula. d). Penghubung Logis yang lain. e). Memanipulasi Formula Proposisinal. f). Negasi dp Formula Proposisional. g). Argumen.

Logika Proposisional (Notasi operator logis/functor)

Konjungsi p &q p . q p q p q K p q

Disjungsi p q p + q p q p q A p q Negasi ~p p p’ p p N p

Implikasi p q p q p q p q C p q

Bi-implikasi p q p q p q p q E p q

Operator Notasi lainnya Burke Kuliah Polan Daliyo dia

Logika Proposisional (Notasi Polandia/Tabel Kebenaran)

Notasi Polandia juga disebut Lukasiewics atau sebagai notasi bebas- kurung atau notasi prefix (+ab) , pada prinsipnya operator diadika me ngawali operand mereka. Selain itu ada notasi postfix (ab+) , yg juga disebut no tasi kebalikan polandia, dimana operator muncul sesudah operand. Notasi yang kita gunakan sehari-hari disebut dengan notasi infix ( a+b) Dalam aritmatika didapat contoh sbb :

Notasi Infix Notasi Prefix Notasi Postfix

p + q +pq pq+

p + q x r +pxqr pqrx+

(p + q) x r x+pqr pq+rx

(p x r) + (q + r) +xprxqr prxqrx+

p x ( r + q) x q xpx+rqq prq+xqx

((p + q) + r) + s +++pqrs pq+r+s+

p + (q + (r + s)) +p+q+rs pqrs+++


Catatan.

1).Perhatikan bahwa pada masing-masing notasi kemunculan setiap variabel mempunyai urutan yang sama.

2). Terlihat bahwa kurung sama sekali tidak digunakan.

3). Tidak perlu adanya prioritas untuk masing-masing operator.

4). Variabel hanya menggunakan satu huruf tunggal.

5). Operator monadika pada notasi infix selalu mendahului operand.

6). Perhatikan formula –pq akan mempunyai dua interpretasi dalam notasi infix yaitu : -(p-q) dan ((-p)-q) sehingga diperlukan simbol khusus yang berbeda untuk monadika negasi, misalnya e.


Lukasiewicz (Notasi Polandia) menggunakan operator dengan hurf besar seperti terlihat dibawah ini untuk membedakan dengan variabel.

Infix Polandia

p Np

p q Apq

p q Kpq

p q Cpq

p q Bpq

p q Epq

p q Rpq

p q Jpq

p q Spq

N – NegasiA – Alternasi (Alternation)K – KonjungsiC – ConditionalB – Non-implikasi??E – EkuivalenR – Non-Ekuivalen, Exclusif Or??J – Joint deniel, NorS – Nand, Incompatibility ??


Beberapa Contoh.

Infix Polandia

p (q r) KpAqr

(p q) r AKpqr

((p) (q) NANpNq

p q r p q r ANpANqAKrNpAqNr

((p q) r) s KKKpqrs

p (q (r s)) KpKqKrs

Sekali tak diperlukan kurung dan konektif utama dapat dilihat segera pada awal dp ekpresi


Beberapa Contoh.

1). p q r s dapat diekpresikan menjadi KKKpqrs atau KpKqKrs

2). p (p q (q r s)) diekpresikan KpCApqCCqrs

3). AEqNqq : disajikan dng notasi infix (p (q)) q

4). NCCpqNCqp : disajikan dng notasi infix ((p q) ((q p)))

5). NCRAqp : disajikan dng notasi infix (r (q p))

6). CKpKCpqCNrNqEpNRrq : disajikan dng notasi infix : (p (p q) r q) (p (r q))


1. Notasi Polandia : Epq Disajikan dalam notasi yang lain. a. p q b. p q c. p q2. Notasi Polandia : CKpqr Disajikan dalam notasi yang lain. C(p q)r = (p q) r3. Notasi Polandia : CpCpr Disajikan dalam notasi yang lain. Cp (p r) = p (p r)

4. Notasi Polandia : ECKpqrCpCpr Disajikan dalam notasi yang lain

Contoh :


Contoh :

Notasi Polandia : E CKpqr CpCprDisajikan dalam notasi yang lain.Cari tanda dominan : E yang sama dengan Ruas kiri (dr ) : C Kpq r Tanda dominan : C yang sm dng Tanda berikutnya : K yg sm dng ( ada dengan &) didapat : p q C (pq) r didapat : (pq) rRuas kanan (dr ) : C p Cpr didapat : C p (p r) di dapat : p (p r)Akhirnya didapat : ((p q) r) (p (p r))


Contoh

( ( p q ) r ) ( ( p r ) q ( K p q ) r ) ( ( p r ) q C ( K p q ) r ( ( p r ) q C ( K p q ) r ( ( ( p ( N r ) ) q ) C ( K p q ) r ( K p ( N r ) q ) C ( K p q ) r ( K p ( N r ) ( N q ) ) C ( K p q ) r ( C ( K p ( N r ) ( N q ) )

E ( C ( K p q ) r ( C ( K p ( N r ) ( N q ) ) )

E C Kpq r C Kp N r N q


Prioritas dp Operator.Seperti pd ungkapan dlm ilmu hitung, maka didalam operator logika pun terdapat prioritas sebagai berikut :1). Operator mempunyai prioritastertinggi2). Operator berprioritas berikutnya3). Operator berprioritas berikutnya4). Operator berprioritas berikunya5). Dan seterusnya operator yang lain termasuk dan seterusnya.

Contoh 1). p q r s dapat diinterpretasikan sebagai (p q) (r s) 2). p q akan diinterpretasikan dengan (p) q 3). “Saya lapar” dan “saya malas” atau “Saya bahagia” dan “Saya telah makan enak” diartikan sebagai ????


Operator yang mempunyai prioritas sama dilakukan dengan urutan dari kiri ke kakan seperti terlihat dalam contoh dibawah ini >

Contoh1). p q r s t u v Diartikan sebagai : (((((p q) r) s) t) u) v

2). p q r s p r t Diartikan sebagai : ??????????.

Logika Proposisional (Tabel Kebenaran dp Formula)

Bagaimana membangun tabel kebenaran :

Satu tabel kebenaran dapat ditentukan dengan mengambil setiap kombinasi yang mungkin daripada nilai kebenaran daripada semua variabel yang terlibat dan kemudian mengevaluasi efek daripada setiap operator Sebagai contoh :

((p) q)

p q p ((p) q) T T F T T F F F F T T T F F T T


Untuk bentuk yang lebih komplek adalah :

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

Urutan evaluasinya menjadi :

( (p q) (( p) ( q))) 3 1 2 1 4 2 1 3 2 1

F T T T T F T F F T F T F F T F T T T F T F F T T T F T F T T F F F T T F T T F


Untuk formula dengan 3 variabel maka akan didapat 2^3 = 8 baris , untuk 4 variabel didapat 2^4 = 16 baris. Sebagai contoh : ((p q) ((p) (r)))

(( p q) (( p) ( r))) 1 2 1 4 2 1 3 2 1

F T T T T F T F F T F T T T F F T T T F T T F F T F T F F T T T F F F F T T T F T F F T T T F T F T T F F T T T F T T F T F F F F T F T F T T F F F F T F T T F

Logika Proposisional [Tabel Kebenaran (TK) Identis]

Simbol =T berarti bahwa pada tabel kebenaran, dua formula mempunyai nilai kebenaran yang sama (identik).

Contoh : 1) (pq) =T (p)(q) ; buatlah TK nya. 2) (pq) =T (p)(q) ; buatlah TK nya. 3) p q =T p q ; buatlah TK nya. 4) p q =T (p q) (p q) ; buatlah TK nya 5) p (p q) =T p q ; buatlah TK nya

Logika Proposisional [Interpretasi dan Model]

Andaikan P adalah formula proposisi ( perhatikan disini digunakan huruf murda/capital untuk menyajikan suatu formula sedang huruf kecil untuk variabel proposisi (atomika)). Suatu interpretasi dpP adalah suatu penugasan (assignment) daripada nilai kebenaran pdsemua variabel proposisi/atom ( pemberian nilai kebenaran pd atom)yg muncul pada P.

Perhatikan bahwa setiap baris pada tabel kebenaran adalah suatu interpretasi. Untuk setiap interpretasi maka P mempunyai nilai kebenaran (lihat bahwa setiap baris P mempunyai nilai T atau F)

Logika Proposisional [ Interpretasi dan Model ]

Andaikan S suatu himpunan daripada formula proposisi, suatu interpretasi disebut model daripada S jika setiap anggauta daripada S bernilai kebenaran T untuk interpretasi tersebut.

Contoh : Andaikan S adalah himpunan dp formula proposisi :

{ p q , q r , r s }

dan interpretasi : I1 : {p=T,q=F,r=T,s=T} ; I2 : { p=T, q=T,s =T , r=T} ; I3 : {p=T,q=T,r=F,s=F} ; I4 : { p=T, q=T,r =T, s=F} ; Interpretasi yang mana yang merupakan model dp S ? Gambarkan tabel kebenarannya.

Logika Proposisional [interpretasi dan Model]

p q r s p q q r r s

I1 T F T T F - -I2 T T T T T T TI3 T T F F T T TI4 T T T F T T F

Dari tabel diatas maka interpretasi yang merupakan model daripada Sadalah I2 dan I3. Perhatikan karena I1 sudah memberikan nilai kebenaran F untuk p q maka dua yang lain tak perlu dievaluasi, karena jelas bahwa I1 bukan model.

Logika Proposisional [Tautologi, Absurditi dan Formula Campur]

Sebarang formula yang selalu bernilai kebenaran T, tak tergantungpada nilai kebenaran daripada variabel-variabel proposisinya, disebut tautologi, dan dikatakan sebagai tautologis atau valid. Suatu tautologi adalah suatu formula proposisional yang mengambil nilai T untuk setiap interpretasi yang mungkin. Semua entri dalam kolom pada tabel kebenaran yang merupakan kolom nilai formula tersebut bernilai kebenaran T.

Tautologi


Contoh : p p adalah Tautologi

karena untuk I1 : p = T, maka p p = T I2 : p = F, maka p p = T dan tak ada lagi interpretasi lain.

Untuk menyatakan bahwa suatu formula adalah suatu tautologi/validmaka dituliskan dengan menggunakan metasimbol ╞ , maka contoh diatas menjadi : ╞ (p p)


Tabel dari kebenaran p p adalah :

p p p pT F T

F T T

Tabel dari kebenaran p (p (q p)) adalah :

p ( p (q p))

1 5 2 1 4 1 3 2 1

T F F T F T F F T

T F F T F F F F T

F F T F T T T T F

F F T F T F F T F


Perhatikan hubungan antara metasimbol =T dng ╞ yang dapat dili hat pada contoh dibawah ini :

Menggunakan ╞ menggunakan =T

╞ p (p) p =T (p)╞ (p q) (q p) p q =T q p╞ (p q) (p)(q) (p q) =T (p) (q)╞ ((p )) ((p) (q)) ((p q)) =T (( p) (q))

Baris pertama kiri dibaca : p (p) adl suatu tautologi, kanan :Formula p mempunyai tabel kebenaran sm-dng formula (p)


Tautologi

Dikatakan bahwa dua formula P dan Q adl Ekuivalen Logis jikaekuivalen logisnya ‘ P Q’ adl suatu tautologi ( yang dapat dikatakan juga dengan bahwa mereka mempunyai tabel kebenaran yang sama)

Dikatakan bhw suatu formula P implai logis suatu formula Q jika implikasi logis mereka ‘ P Q’ adalah tautologi.


Absurditi/Kontradiksi

Sebarang formula yang selalu bernilai kebenaran F, tak tergantungpada nilai kebenaran dp variabel-variabel proposisinya, disebut Absurditi atau Kontradiksi atau Unsatisfiable dan dikatakan sbg Absurditi atau Invalid. Suatu Absurditi adalah suatu formula proposisional yang ber nilaiF untuk setiap interpretasi yg mungkin. Semua entri dalam kolom Pada tabel kebenaran yang merupakan kolom nilai formula tersebutbernilai kebenaran F.


Absurditi/Kontradiksi

Contoh : (p p) dan (p p)

adalah absurditi/kontradiksi karena untuk :

I1 : p = T, maka (p p) = F I2 : p = F, maka (p p) = F

dan tak ada lagi interpretasi lain.

Perhatikan bahwa suatu formula proposisional P yg adalah suatu absurditi, maka formula P adalah suatu Tautologi, begitu pula sebaliknya. Jika sebarang formula P adalah suatu absurditi, maka ditulis :

╞ P


Sebarang formula yang, tergantung pada nilai kebenaran dp vari abel-variabelnya, dapat bernilai baik nilai T maupun nilai F dise but suatu formula campur, atau ada yang menyebut contingent.

Contoh :

Tentukan yang mana yang tautologi, absurditi atau formula cam pur : a) p (q p) ; b) p (p (q p) ; c) p (p (q p)).

Formula Campur


Formula Campur

p ( q p) 1 4 2 1 3 1 T T F T T T T T T F T T F F F T T F F T T F F F

p1TTFF

5FFFF

(2FFTT

p1TTFF

4FFTT

(q1TFTF

3FFTF

2FFTT

p1TTFF

p1TTFF

5TTTT

(2FFTT

p1TTFF

4FFTT

(q1TFTF

3FTTT

2FFTT

p1TTFF

2FFTT

ilmu kom puter fak mipa ugm

Documents