BAB 4 PROPOSISI MAJEMUK
1. Pendahuluan Perangkai logika digunakan untuk mengkombinasikan proposisi-proposisi atomik menjadi proposisi majemuk. Untuk menghindari kesalahan tafsir akibat adanya ambiguitas satu orang dengan lainnya, proposisi majemuk yang akan dikerjakan lebih dulu akan diberi tanda kurung sehingga proposisi-proposisi dengan perangkai-perangkai yang berada di dalam tanda kurung disebut fully parenthesized ekspression (fpe). Proposisi majemuk yang sangat rumit dapat dipecah-pecah menjadi subekspresisubekspresi. Subekspresi menjadi subekspresi dan seterusnya tergantung dari tingkat kerumitannya. Teknik ini dinamakan parsing. Tetapi, mungkin saja proposisi majemuk tidak memiliki tanda kurung. Karena itu, urutan proses pengerjaannyaharus ditentukan terlebih dahuludan harus ada ketentuan yang mengatur pengurutan tersebut.
2. Ekspresi logika
Ekspresi logika merupakan istilah lain logika proposisional.
Ekspresi logika sebenarnya adalah proposisi-proposisi yang dibangun dengan variabel- variabel logika yang berasal dari pernyataan atau argumen
Variabel logika berupa huruf-huruf tertentu yang dirangkai dengan perangkai/operator logika dapat dinamakan ekspresi logika atau formula
Setiap ekspresi logika dapat bersifat atomik atau majemuk, tergantung dari variabel proposisional yang membentuknya bersama perangkai/operator yang relevan
Seperti dijelaskan di atas, proposisi majemuk dapat menyebabkan terjadinya ambiguitas, atau kesalahan penafsiran jika tidak dengan tepat meletakkan tanda kurung pada tempatnya yang benar. Contoh:
Jika Dewi belajar, maka ia lulus ujian dan ia mendapat hadiah istimewa.
Pernyataan di atas dapat diubah menjadi variabel proposisional: A = Dewi rajin belajar B = Dewi lulus ujian C = Dewi mendapat hadiah istimewa LOGIKA INFORMATIKA
BY: SRI ESTI
Dalam bentuk ekspresi logika berubah menjadi: A→B˄C Persoalannya adalah ada dua kemungkinan pengerjaan, yakni: ((A→B)˄C) atau (A→(B˄C)) Karena kedua kemungkinan tersebut dapat menghasilkan nilai kebenaran yang berbeda.
Disinilah letak pentingnya ketepatan pemberian tanda kurung biasa sehingga menjadi suatu ekspresi logika yang fpe dan dengan tepat melakukan pengoperasian sesuai aturannya. Pada contoh di atas, ekspresi logika yang tepat adalah: A→(B˄C) Hal ini disebabkan karena pernyataan “Dewi lulus ujian” dan “Dewi mendapat hadiah istimewa” merupakan akibat dari “Dewi rajin belajar”. Jika ekspresi logika ditulis ((A→B)˄C), dapat dibaca pernyataan “Dewi mendapatt hadiah istimewa” tidak berhubungan dengan “Dewi rajin belajar”, yang menjadi akibat “Dewi raji belajar” hanya “Dewi lulus ujian” saja.
3. Skema Skema merupakan satu cara untuk menyederhanakan suatu proposisi majemuk yang rumit dengan memberi huruf tertentu untuk menggantikan satu subekspresi atau subsubekspresi. Misal, (𝐴 ∧ B) dapat diganti dengan P sedangkan (𝐴 ∨ B) diganti dengan Q. Maka P dan Q berisi variabel proposisional A dan B. P dan Q bukan variabel proposisional karena nilainya tergantung pada nilai A dan B.
Contoh 1: P = (A ˄ B) dan Q = (A ˅ B), maka (P Q) = ((A ˄ B) (A ˅ B)) Hal – hal yang perlu diperhatikan: 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 5. Ekspresi apa saja berbentuk (P ↔ Q) disebut ekuivalensi (biconditional)
LOGIKA INFORMATIKA
BY: SRI ESTI
Maka contoh di atas disebut implikasi yang berisi konjungsi (𝐴 ∧ B) dan disjungsi (𝐴∨ B). Aturan yang harus diperhatikan: a) Semua ekspresi atomik adalah fpe. b) Jika P adalah fpe, demikian juga dengan ¬P. c) Jika P dan Q adalah fpe, maka demikian juga dengan (𝑃∧ 𝑄), (𝑃∨𝑄), (𝑃→ 𝑄) dan (𝑃↔𝑄) d) Tidak ada fpe lainnya.
Ekspresi logika yang dijelaskan di atas disebut well-formed formulae (wff). Jadi, wff adalah fpe, demikian juga sebaliknya. Ekspresi logika disebut wff karena penulisannya dilakukan dengan benar.
Contoh 2: 𝐴 → (B → ¬𝐴 ∨ ¬B) 𝐴 → (B → (¬𝐴 ∨ ¬B) Contoh di atas tidak menunjukkan wff atau fpe yang baik karena tanda kurung biasa tidak lengkap dan tidak ada perangkai pada dua proposisi majemuk yang berada pada tanda kurung.
4. Analisis proposisi majemuk Setiap fpe akan mengekspresikan proposisi majemuk. Proposisi majemuk mempunyai subproposisi, yang bisa berupa konjungsi, disjungsi dan sebagainya. 1. Jika Dewi lulus sarjana teknik informatika, maka orang tuanya akan senang dan dia dapat segera bekerja, tetapi jika dia tidak lulus, maka semua usahanya akan sia-sia. 1.1. Jika Dewi lulus sarjana teknik informatika, orang tuanya akan senang, dan dia dapat segera bekerja. 1.1.1. Jika Dewi lulus sarjana teknik informatika. 1.1.2. Orang tuanya akan senang, dan dia dapat segera bekerja. 1.1.2.1. Orang tuanya akan senang 1.1.2.2. Dia dapat segera bekerja. 1.2. Jika dia tidak lulus, semua usahanya akan sia – sia. 1.2.1. Dia tidak lulus. 1.2.2. Semua usahanya akan sia – sia.
LOGIKA INFORMATIKA
BY: SRI ESTI
Teknik memisah – misah atau memilah – milah kalimat menjadi proposisi – proposisi atomik disebut Parsing dan hasilnya dapat diujudkan dalam bentuk Parse Tree.
Gambar 1 Parse Tree
Parse tree mengubah proposisi majemuk menjadi fpe sebagai berikut: A = Dewi lulus sarjana teknik informatika B = Orangtua Dewi senang C = Dewi bekerja D = Usaha Dewi sia-sia Selanjutnya, pernyataan di atas yang berupa proposisi majemuk dapat dibuat fpe sebagai berikut: (𝐴 → (B ∧ C)) ∧ ((¬𝐴) → 𝐸)
5. Aturan pengurutan Aturan pengurutan digunakan untuk memastikan proses pengerjaan subekspresi. Pada masalah perangkai, urutan atau hierarkinya berdasarkan pada hierarki tertinggi. Tabel 1 Hierarki Perangkai
LOGIKA INFORMATIKA
BY: SRI ESTI
Untuk perangkai/ operator yang memiliki hirarki yang sama maka digunakan aturan left associative, yaitu operator disebelah kiri akan didahulukan karena mempunyai hierarki yang lebih tinggi. Contoh: 1. (¬𝐴 ∧ B) menjadi ((¬𝐴 ) ∧ B), bukan (¬ (𝐴 ∧ B) 2. 𝐴 ∧ B ∨ C menjadi ((𝐴 ∧ B) ∨ C), bukan (𝐴 ∧ (B ∨ C)) 3. 𝐴 → B ∧ C menjadi 𝐴 → (B ∧ C) bukan (𝐴 → B) ∧ C 4. 𝐴 ↔ B → C menjadi (𝐴 ↔ (B → C)), bukan ((𝐴 ↔ B) → C)
Tanda kurung yang terlalu banyak disebut redundansi. Jika ada tanda kurung yang sebenarnya tidak diperlukan, bahkan kadang-kadang membuat salah tafsir. Tanda kurung yang tidak diperlukan harus dikurangi untuk menyederhanakannya, tetapi dengan tidak mengubah operasi terhadap bentuk logikatersebut, dan membuat bentuk logika lebih mudah ditafsirkan.
Contoh: A→B→C Manakah yang harus dikerjakan terlebih dahulu? Aturan pengurutan akan menyebutkan jika hierarkinya sama, maka dilaksanakan mulai dari yang kiri. Jadi harus dibaca: (A → B) → C, bukan A → (B → C).
Latihan soal 1. Ubahlah pernyataan-pernyataan berikut menjadi ekspresi logika berupa proposisi majemuk: a. Jika tikus itu waspada dan bergerak cepat, maka kucing atau anjing itu tidak mampu menangkapnya. b. Jika saya tidak keliru, Dewi sudah diwisuda dan pacarnya atau orang tuanya berada disampingnya c. Bowo membeli saham dan membeli properti untuk investasinya, atau dia dapat menanamkan uang di deposito bank dan menerima bunga uang.
LOGIKA INFORMATIKA
BY: SRI ESTI
2. Dengan menggunakan: A : Hari ini adalah hari Sabtu B : Hujan turun C : Hari ini panas Ubahlah ekspresi logika berikut menjadi sebuah pernyataan dalam bahasa indonesia: a. A ˄ B b. (A ˄ B) ˅ (C ˄ A) c. (A ˄ B) ˄ ( A ˅ C) d. (A ˄ B) → C e. A ˄ ( B ˅ C)
3. Tentukan prioritas ekspresi logika berikut ini dan buat tabel kebenarannya. a. A ˅ B b. A ˄ B ˅ C c. A → B ˅ C d. A ↔ B → C e. A ˅ B ˅ C ˄ B ˄ C
4. Jika nilai A dan B adalah T, sedangkan C dan D adalah F, carilah nilai kebenaran dari ekspresi-ekspresi logika berikut: a. A ˄ (B ˅ C) b. (A ˅ B) ˄ C c. ((A ˅ B) ˄ C) ˅ ¬((A ˅ B) ˄ (B ˅ D)) d. (¬(A ˄ B) ˅ ¬C) ˅ (((¬A ˄ B) ˅ ¬D) ˄ C) e. (A ↔ C) ˄ (¬B → D)
LOGIKA INFORMATIKA
BY: SRI ESTI
