Logika Informatika [PDF]

Citation preview

LOGIKA MATEMATIKA



Modul 03 Tujuan Instruksional Umum Memahami dan membangun argumen atau kalimat mengevaluasinya dan menentukan validitas.



SKEMA Skeme (schemas) merupakan satu cara untuk menyederhanakan suatu proposisi majemuk yang rumit dengan memberi huruf tertentu untuk menggentikan satu subekspresi ataupun sub subekspresi. Satu ekspresi logika tertentu , misalnya : (A (A



∨



∧



B) dapat diganti dengan P, sedangkan



B) dapat diganti dengan Q. Jadi P berisi variabel peoposisional A dan B, demokian



juga Q. P disini bukan variabel proposisional karena nilai P tergantung dari nilai A dan B. Contoh 2 :



P = (A



∧



B) dan Q = (A



∨



B), maka (P → Q) = ((A



∧



B)



→ (A ∨ B))



Jadi sekarang perhatikan hal berikut: (1). Ekspresi apa saja berbentuk (



¬



P) disebut negasi.



(2.) Ekspresi apa saja berbentuk ((P ∧ Q) disebut konjungsi. (3). Ekspresi apa saja berbentuk (P



∨



Q) disebut disjungsi.



(4). Ekspresi apa saja berbentuk (P → Q) disebut implikasi (conditional). (5). Ekspresi apa saja berbentuk (P



↔



∧ B) → (A ∨ (A ∨ B).



Maka contoh diatas ((A



∧



B) dan disjungsi



Q) disebut ekuivalensi (biconditional).



B)) desebut implikasi yang berisi konjungsi



Sekarang perhatikan aturan berikut :



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



(A



(1). Semua ekspresi atomic adalah fpe.



(2). Jika P adalah fpe, maka juga (



¬



P).



(3). Jika P dan Q adalah fpe, maka juga (P ∧ Q), (P



∨



Q), (P → Q), dan (P



↔



Q).



(4).Tidak ada fpe lainnya. Ekspresi-ekspresi logika yang dijelaskan diatas disebut wellformed formulae (wff). Jadi, wff adalah fpe, demikian juga sebaliknya. Eskpresi logika disebut wff karena penulisannya dilakukan dengan benar.Lihat contoh berikut: Contoh 3 :



•



A → (B → (



¬ ∨¬ A



B))



Perhatikan posisi tanda kurung yang benar dan lengkap pada contoh 2 diatas. Sekarang perhatikan contoh yang mirip: Contoh 4 :



¬ ∨¬ → ¬ ∨ ¬



•



A → (B →



•



A → (B



A



(



A



B)) B)



Jelas contoh 4 tidak menunjukan suatu wff atau fpe yang baik karena tanda kurung biasa tidak lengkap dan tidak ada perangkai pada kedua proposisi majemuk yang ada pada tanda kurung.



Sekarang kembali pada masalah skema, jika ada suatu ekspresi logika ( disebut skop negasi (scope of negation). Dengan perangkai utama (main connective) dari (



¬



¬



¬



P), maka P



disebut perangkai



P). Contoh 2 diatas, yakni (P → Q), dapat diuraikan



seperti berikut :



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



(P → Q)



Skop kiri



Perangkai utama



Skop kanan



((A ∧ B) → (A ∨ B)) MENGANALISA PROPOSISI MAJEMUK Setiap fpe akan mengekspresikan proposisi majemuk. Proposisi majemuk mempunyai subproposisi, yang bisa berupa konjungsi , disjungsi, dan sebagainya.lalu,bagaimana cara membuat suatu proposisi majemuk dari suatu pernyataan yang cukup panjang seperti berikut ini : [1]. Jika Dewi lulus sarjana teknik informatika, orang tuanya akan senang, dan dia dapat segera bekerja, tetapi jika dia tidak lulus, semua usahanya akan sia-sia. Proposisi-proposisi yang membentuk pernyataan di atas adalah konjungsi (kata “tetapi” ditengah kalimat kebih sesuai dengan “dan” ) dengan skop kiri dan skop kanan seperti berikut ini: [1.1]. Jika Dewi lulus sarjana teknik informatika, orang tuanya akan senang, dan dia dapat segera bekerja. Dengan [1.2]. jika dia tidak lulus, semua usahanya akan sia-sia.



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



Kedua skop diatas, masih berupa proposisi majemuk, untuk kalimat pertama dengan skop kiri dan skop kanan, dapat dipecah lagi seperti berikut: [1.1.1]. Jika Dewi lulus sarjana teknik informatika, Dengan [1.2.2]. orang tuanya akan senang, dan dia dapat segera bekerja. Kalimat terakhir ini juga masih berbentuk proposisi majemuk, sehingga skop kiri dan skop kanan dapat dipisah seperti berikut: [1.1.2.1]. orang tuanya akan senang, Dengan [1.1.2.2]. dia dapat segera bekerja. Kalimat diatas sudah tidak dapat dipecah lagi. Jadi, kemnali kepada skop kiri dan skop kakan dipermulaan (1.1) dan (1.2) . jika (1.1) sudah selesai dipecah, maka tinggal (1.2) yang menjadi skop kiri dan skop kanan seperti berikut : [1.2.1] Dia tidak lulus Dengan [1.2.2] Semua usahanya akan sia-sia. Tehnik memisah-misah atau memilah-milah kalimat diatas menjadi proposisi-proposisi yang paling kecil (atomik), disebut tehnik parsing, dan hasilnya juga dapat diujudkan dalam bentuk parse tree. Lihat parse tree berikut ini:



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



Parse Tree



1



1.1



1.2



1.1.1



1.1.2



1.1.2.1



1.2.1



1.1.2.2



1.2.2



1.2.1



Untuk mengubah parse tree menjadi ekspresi logika yang berbentuk proposisi majemuk adalah dengan menjadi fpe berikut : A = Dewi lulus sarjana teknik informatika B = Orang tua Dewi senang. C = Dewi bekerja. D = Usaha Dewi sia-sia. Selanjutnya, pernyataan diatas yang berupa proposisi majemuk dapat dibuat fpe sebagai berikut: (A → (B ∧ C))



∧ ((



¬



A) → D)



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



Pada ekspresi ligika diatas, jika dianggap M maka M adalah ekspresi majemuk, yang dirangkai dari subekspresi-subekspresi secara sederhana, jika M berbentuk (P ∧ Q) , maka P dan Q masing-masing berupa subekspresi. Setiap subekspresi ini dinamakan Immediate subexpretions dari M,P,Q, juga dapat berbentuk ekspresi majemuk yang juga mempunyai subekspresi yang sebenarnya juga subekspresi dari M. Lihat contoh tentang Dewi diatas, maka :



M = (A → (B ∧ C))



∧ ((



P = (A → (B ∧ C)) Q = ((



¬



¬



A) → D)



A) → D)



P masih mempunyai subekspresi A dan (B ∧ C), sedangkan (B ∧ C) masih mempunyai subekspresi B dan C. Hanya saja jika berbentuk (



¬



A) , maka subekspresinya A.



M sebenarnya juga dapat dianggap subekspresi dari M sehingga disebut Improper subexpressions, sedangkan subekspresi lainnya disebut proper subexpressions dari M. Salah satu bentuk yang paling banyak dibahas dari ekspresi logika adalah literal. Jadi misalnya A dan B merupakan variabel proposisional, maka A, adalah literal-literal. Akan tetapi, jika berbentuk



•



((A ∧ B)



•



((A ∧ (B



¬



¬



A,B, dan



¬



B



(A ∧ B), maka ia bukan literal.



→ (A ∨ B)) → A)) ∨ B)



Kedua pfe tersebut berbeda proses pengerjaannya. Oleh karena itu, harus ada aturan untuk memprioritaskan penafsiran hasilnya yang disebut aturan pengurutan. Aturan pengurutan (precedence rules) digunakan untuk memastikan proses pengerjaan subekspresi. Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



Pada maslah perangkai, urutan atau hierarkinya berdasarkan pada hierarki tertinggi:



¬∧



Hierarki ke



Simbol perangkai 1 2 3 4 5



Nama Perangkai Negasi Konjungsi Disjungsi Implikasi Ekuivalensi



∨



→ ↔



Disini ada aturan tambahan yakni “ Jika jumpai lebih satu perangkai pada hierarki yang sama, maka akan dikerjakan mulai dari yang kiri”. Contoh (a). (



¬



A ∧ B), harus dibaca ((



¬



A) ∧ B), bukan (



¬



(A ∧ B))



(b). A ∧ B ∨ C, harus dibaca ((A ∧ B) ∨ C), bukan (A ∧ (B ∨ C)) (c). A → B



∧ C, harus dibaca (A → (B ∧ C)), bukan ((A → B) ∧ C)



(d). A↔B → C, harus dibaca (A↔(B → C)), bukan ((A↔B) → C) Sekarang lihat lagi pada contoh tenteng Dewi diatas : (A → (B



∧ C)) ∧ ((



¬



A)



→ D)



Dapat lebih disederhanakan dengan mengurangi tanda kurung biasa menjadi: (A → B



∧ C) ∧ (



¬



A



→ D)



Sebaliknya contoh diatas memakai bentuk : (A → (B



∧ C)) ∧ (



¬



A



→ D)



Tanda kurung yang terlalu banyak disebut redundansi (redundancy) jika ada tanda kurung yang sebenarnya tidak diperlukan, bahkan ada tanda kurung yang Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



sebenarnya tidak diperlukan, bahkan sebenrnya membuat salah tafsir. Tanda kurung yang tidak diperlukan harus dikurangi untuk menyederhanakan, tetapi dengan tidak mengubah operasi terhadap bentuk logika tersebut, dan membuat bentuk logika lebih mudah ditafsirkan. Contoh : A→ B



→C



Manakah yang harus dikerjakan terlebih dahulu? Aturan pengurutan akan menyebutkan jika hierarki sam, maka dilaksanakan mulai dari yang kiri . Jadi harus



dibaca : (A → B)



→ C, bukan A → (B → C). Akan tetapi jika anda ingin



mengerjakan bagian kurung terlebih dahulu, berilah tanda kurung seperti yang terakhir. Oleh karena itu, ekspresi majemuk yang berada pada tanda kurung terdalam akan dilaksanakan , atau diproses lebih awal dari yang lainnya. Aturan tersebut mirip ekspresi aritmatika ( ^, *, /, +, dan -) yang juga biasanya digunakan dalam bahasa pemrograman, misalnya Pascal , C++, dan lain sebagainya. Operator binary disebut left associstive, artinya operator disebelah kiri akan didahulukan karena mempunyai hierarki yang lebih tinggi. Sebaliknya, akan disebut right associstive jika operator sebelah kanan yang dikerjakan terlebih dahulu. Jika perangkainya sama, maka operasi yang dilakukan pertama adalah left associative.



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA



Pusat Pengembangan Bahan Ajar - UMB



BAMBANG JOKONOWO S.SI LOGIKA MATEMATIKA