BAB 9 TABLO SEMANTIK 1. Pendahuluan Tabel kebenaran sangat baik untuk menjelaskan dasar logika dan mudah dipahami. Kesulitan yang timbul adalahbanyaknya jumlah baris yang diperlukanjika variabel proposisionalyang harus ditangani cukup banyak. Ukuran tersebut yakni 2n (n = jumlah variabel proposisional). Jadi, misalnya ada 8 variabel proposisional, maka ada 28 = 256 baris. Dari ukuran 2n ini bisa terbentuk dasar perhitungan 1 Kilobyte = 1024 Byte, atau 210 yakni 1024, demikian juga 1 byte = 8 bit, atau 23. Hal ini dikarenakan perhitungan berdasarkan nilai benar (T ≡ 1) dan salah (F ≡ 0) sebagai konstanta proposisional yang kemudian dipangkatkan. Inilah yang sebenarnya dikenal sebagai bahasa mesin, atau bahasa tingkat rendah (low level language), satu-satunyabahasa yang dimengerti oleh komputer. Ukuran yang besar dari tabel kebenaran menimbulkan banyak kesulitan sehingga dapat dipergunakan cara lain untuk membuktikan konsistensi sekumpulan pernyataanpernyataan dan validitas dari argumen-argumen. Salah satunya adalah Tablo Semantik (Semantik Tableaux).
2. Tablo semantik Penggunaan tablo semantik berbasis pada strategi pembalikan. Strategi pembalikan pada tablo semantik dilakukan dengan memberi negasi pada kesimpulan dan memeriksa hasil yang diperoleh. Tablo semantik bisa dibuktikan apakah kesimpulan yang bernialai F dapat diperoleh dari premis-premis yang bernilai T. jika idak bisa, maka argumen tersebut valid, tetapi jika bisa, maka argumen tidak valid. Jadi, premis-premis yang bernilai T harus menghasilkan kesimpulan yang berniali T juga. Kesimpulan ini disebut semantically entailed dari premis-premis. Tablo semantik sebenarnya hanya bentuk-bentuk proposisi yang dibangun berdasarkan aturan-aturan tertentu yang biasanya berbentuk pohon terbalik dengan cabang-cabang dan ranting-ranting yang relevan.
LOGIKA INFORMATIKA
BY: SRI ESTI
3. Aturan tablo semantik Terdapat 10 aturan dalam tablo semantik yang diurutkan sebagai berikut: Aturan 1: A ˄ B Jika tablo berisi A ˄ B, maka tablo dapat dikembangkan menjadi tablo baru dengan menambahkab A dan B pada tablo A ˄ B. Bentuknya seperti berikut: A˄B A B Aturan 2: A ˅ B Jika tablo berisi A ˅ B maka dapat dikembangkan membentuk tablo baru dengan menambah dua cabang baru, satu berisi A dan satunya adalah B seperti berikut: A˅B
A
B
Aturan 3: A → B A→B
¬A
B
Aturan 4: A ↔ B A↔B A˄B
¬A ˄ ¬B
Aturan 5: ¬¬A ¬¬A A Aturan 6: ¬(A ˄ B) ¬(A ˄ B)
¬A
¬B
Aturan 7: ¬(A ˅ B) ¬(A ˅ B) ¬A ¬B
LOGIKA INFORMATIKA
BY: SRI ESTI
Aturan 8: ¬(A → B) ¬(A → B) A ¬B Aturan 9: ¬(A ↔ B) ¬(A ↔ B) A ˄ ¬B
¬A ˄ B
Aturan 10: Jika ada bentuk logika A dan negasinya (¬A) yang berada pada satu deretan cabang dari tablo, maka terjadi ketidakkonsistenan pada cabang tersebut, dan cabang dinyatakan “tertutup (closed)”, dan cabng tersebut tudak bisa dikembangkan lagi. Hal ini disebabkan karena A dan ¬A tidak mungkin benar bersama-sama pada satusaat tertentu, yakni jika A bernilai T, tidak mungkin ¬A juga bernilai T pada saat yang sama, demikian sebaliknya.
Jika semua cabang tablo tertutup, maka ekspresi logika disebut bersama-sama tidak konsisten atau mereka tidak bisa bernilai benar bersama-sama.
4. Tablo semantik himpunan ekspresi logika Contoh 1: Apakah 2 buah ekspresi logika ini konsisten bersama-sama: ¬(A→B) dan ¬A˅B Tablo semantik yang dibuat seperti berikut: ¬(A→B) ¬A ˅ B
(1) (2)
¬A
B
Aturan 2 pada (2)
A
A
Aturan 8 pada (1)
¬B
¬B
Tutup
Tutup
LOGIKA INFORMATIKA
BY: SRI ESTI
Perhatikan bahwa dua cabang dari tablo di atas tertutup karena cabang sebelah kiri berisi A dan ¬A, sedangkan cabang kanan berisi b dan ¬B, maka kesimpulannya adalahtidak konsisten bersama-sama. Bentuk tablo lainnya: ¬(A→B)
(1)
¬A ˅ B
(2)
¬¬A
Aturan 8 pada (1)
¬B
A
¬A Tutup
Aturan 5
B
Aturan 2 pada (2)
Tutup
Heuristik untuk mengefisienkan pembuatan tablo: 1. Carilah ekspresi logika yang dapat memakai aturan tanpa cabang (satu cabang) 2. Carilah ekspresi logika yang isinya mempunyai bentuk, yang tablonya pasti tertutup, misalnya A dengan negasinya (~A), agar cabang tablo tertutup dan tidak dapat dikembangkan lagi.
Contoh 2: Apakah himpunan dari 4 buah ekspresi logika berikut ini bersama-sama konsisten?: ¬A˅B, ¬(B˄¬C), C→D, dan ¬(¬A˅D) Berikut ini adalah langkah-langkah pembuatan tablo semantik: Langkah 1: Tulis semua ekspresi logika secara berurutan atas ke bawah. (1)
¬A˅B
(2)
¬(B˄¬C)
(3)
C→D
(4)
¬(¬A˅D)
Langkah 2: Pakailah aturan 7 pada baris (2): (1)
¬A˅B
LOGIKA INFORMATIKA
BY: SRI ESTI
(2)
¬(B˄¬C)
(3)
C→D
(4)
¬(¬A˅D)
(5)
¬¬A
(6)
¬D
Langkah 3: Pakailah aturan 5 pada baris (5): (1) ¬A˅B (2) ¬(B˄¬C) (3) C→D (4) ¬(¬A˅D)
(5)
¬¬A
(6)
¬D
(7)
A
Sekarang tidak ada lagi yang tidak bercabang, maka harus memilih salah satudari ekspresi logika untuk meneruskan tablo. Langkah 4: (1) ¬A˅B (2) ¬(B˄¬C) (3) C→D (4) ¬(¬A˅D)
(5)
¬¬A
(6)
¬D
(7)
A
(8) ¬A
B
Tutup Satu cabang tlah tertutup. Karena pada satucabang terdapat A dan ¬A, maka tinggal meneruskan pada cabang yang lain.
LOGIKA INFORMATIKA
BY: SRI ESTI
Langkah 5: Sekarang pakailah aturan 6 pada baris (2): (1) ¬A˅B (2) ¬(B˄¬C) (3) C→D (4) ¬(¬A˅D)
(5)
¬¬A
(6)
¬D
(7)
A
(8) ¬A
B
Tutup (9)
¬B
¬¬C
Tutup Ternyata cabang kiri juga dapat tertutup karena ada B dan ¬B, maka tinggal meneruskan pada cabang yang lain yang masih terbuka. Langkah 6: Sekarang pakailah aturan 5 pada baris (9): (1) ¬A˅B (2) ¬(B˄¬C) (3) C→D (4) ¬(¬A˅D)
(5)
¬¬A
(6)
¬D
(7)
A
(8) ¬A
B
Tutup (9)
¬B
¬¬C
Tutup
C
LOGIKA INFORMATIKA
BY: SRI ESTI
Langkah 7: Sekarang pakailah aturan 5 pada baris (9): (1) ¬A˅B (2) ¬(B˄¬C) (3) C→D (4) ¬(¬A˅D)
(5)
¬¬A
(6)
¬D
(7)
A
(8) ¬A
B
Tutup (9)
¬B
¬¬C
Tutup (10)
C
(11)
¬C Tutup
D Tutup
Akhirnya seluruh tablo tertutup. Tablo semantik yang disusun juga sudah lengkap seluruh ekspresi logika yang harus diturunkan menjadi tablo. Dapat disimpulkan bahwa semua ekspresi logika tersebut tidak konsisten, atau tidak kompatibel bersama-sama.
Latihan: Apakah himpunan dari 3 buah ekspresi logika berikut ini bersama-sama konsisten?: (A˄B)→C, ¬A→D, B˄¬C˄¬D
5. Pembenaran aturan tablo semantik Aturan tablo semantik dapat dipandang sebagai aturan sistem deduktif atau sistem pembuktian yang tidak perlu ditafsirkan pada konteks lain. Aturan tablo semantik sangat sintaksis. Hanya tinggal menuruti aturan yang ada dan tidak ada penentuan terlebih dahulu bahwa premis-premis benar dengan kesimpulan yang disalahkan seperti pada LOGIKA INFORMATIKA
BY: SRI ESTI
strategi pembalikan yang digunakan pada model dan countermodel, tetapi hanya dengan menegasi kesimpulannya, dan tidak memedulikan premis-premis walaupun tetap tergolong stratesi pembalikan. Aturan tablo semantik sangat beralasan dan realistis karena berbasis pada aturan hukum logika yang sudah dibahas sebelumnya. Perhatikan aturan tersebut satu per satu: Aturan 1: A ˄ B A˄B A B Sebenarnya aturan ini menunjukkan bahwa jika (A˄B) benar, maka A dan B juga bernilai benar sehingga cabang tablo untuk ekspresi ini juga benar bersama-sama. Aturan 2: A ˅ B A˅B
A
B
Aturan ini menunjukkan bahwa jika (A˅B) benar, maka A bisa benar atau B juga benar. Untuk itu satu cabang tablo harus menunjukkan hal ini, atau ada konsistensi disini. Aturan 3: A → B A→B
¬A
B
Pada hukum logika juga diketahui (A→B) ≡ ¬A˅B sehingga aplikasinya sama seperti hukum nomor 2. Aturan 4: A ↔ B A↔B A˄B
¬A ˄ ¬B
Pada hukum logika juga diketahui (A↔B) ≡ (A˄B)˅(¬A˄¬B) sehingga aplikasinya sama seperti hukum nomor 2. Aturan 5: ¬¬A ¬¬A A Ini merupakan aplikasi hukum negasi ganda, yakni ¬¬A ≡ A LOGIKA INFORMATIKA
BY: SRI ESTI
Aturan 6: ¬(A ˄ B) ¬(A ˄ B)
¬A
¬B
Pada hukum De Morgan sudah diketahui bahwa ¬(A ˄ B) ≡ ¬A˅¬B sehingga aturan nomor 2 dipakai sekali lagi. Aturan 7: ¬(A ˅ B) ¬(A ˅ B) ¬A ¬B Hukum De Morgan lainnya diketahui bahwa ¬(A ˅ B) ≡ ¬A˄¬B sehingga dipakai aturan nomor 1. Aturan 8: ¬(A → B) ¬(A → B) A ¬B Penyederhanaan bisa dilakukan pada ¬(A → B) sehingga menjadi: ¬(A → B) ≡ ¬(¬A ˅ B)
A→B
≡ (¬¬A˄¬B)
hukum De Morgan
≡ (A˄¬B)
hukum negasi ganda
Oleh karena itu aturan 1 dapat dipakai pada eksprei logika yang diperoleh. Aturan 9: ¬(A ↔ B) ¬(A ↔ B) A ˄ ¬B
¬A ˄ B
Sedangkan untuk ¬(A ↔ B) dapat dilakukan penyederhanaan seperti berikut: ¬(A ↔ B) ≡ ¬((A→B)˄(B→A))
A→B
≡ ¬((¬A˅B)˄(¬B˅A))
A→B
≡ (¬(¬A˅B)˅¬(¬B˅A))
hukum De Morgan
≡ (¬¬A˄¬B)˅(¬¬B˄¬A)
hukum De Morgan
≡ (A˄¬B)˅(B˄¬A)
hukum negasi ganda
LOGIKA INFORMATIKA
BY: SRI ESTI
≡ (A˄¬B)˅(¬A˄B)
hukum komutatif
Setelah selesai akan diperoleh bentuk yang sederhana. Sekali lagi aturan 2 digunakan.
Metode tablo semantik merupakan pendekatansecara langsung untuk memperlihatkan adanya ketidakkonsistenan dalam suatu himpunan dari ekspresi logika, yaitu dengan cara membuang pasangan yang terjadi konflik, misalnya A dengan ¬A. jika semua cabang tertutup, berarti ada ketidakkonsistenan, sedangkan jika ada cabang yang tertutup dan ada yang terbuka walau hanya ada satu berarti konsisten.
Bagaimana jika terjadi tablo yang tidak tertutp dan memastikan adanya konsistensi. Contoh: (1)
A˅¬B
(2)
B˄¬C
(3)
C→A
(4)
B
(5)
¬C
(6)
A
Aturan 1 pada baris (2)
¬B
Aturan 2 pada baris (1)
Tutup (7)
¬C
A
Aturan 2 pada baris (3)
Jelas bahwa tablo tidak bisa ditutup sehingga terjadi konsistensi bersama-sama pada himpunan ekspresi logika. Konsistensi bisa dibuktikan dengan teknik model yaitu dengan mengambil satu variabel proposisi pada cabang yang tidak tertutup, misalnya A atau ¬A, dan berilah nilai T pada variabel tersebut. Misalnya v(A) ≡ T, maka v(¬C) ≡ T (ambil dari baris (3)). Jadi v(C) ≡ F. Periksa dengan baris (2). Jika v(¬C) ≡ T, maka pasti v(B) ≡ T, maka v(¬B) ≡ F. Periksa dengan baris (3). Jika v(¬B) ≡ F, sedangkan v(A) ≡ T, maka v(A˅¬B) ≡ T. jadi mudah ditebak bahwa v(A˅¬B) ≡ T, v(B˄¬C) ≡ T, dan v(A˅¬B) ≡ T. Tabel kebenarannya: A
B
C
¬B
¬C
A˅¬B
B˄¬C
A˅¬B
T
T
F
F
T
T
T
T
6. Tablo semantik pada argumen LOGIKA INFORMATIKA
BY: SRI ESTI
Tablo semantik juga dapat diimplementasikan pada pembuktian validitas suatu argumen. Contoh:
Jika Badu mencontek saat ujian, maka dosen akan datang jika pengawas tidak lalai. Jika Badu mencontek saat ujian, maka pengawas tidak lalai. Dengan demikian, jika Badu mencontek, maka dosen akan datang.
Apakah argumen di atas valid, atau apakah kesimpulan (pernyataan 3) secara logis mengikuti premis-premisnya (pernyataan 1 dan 2)? Dapat dilkukan strategi pembalikan dengan menegasi kesimpulan sehingga ditemukan kesimpulan tidak konsisten dengan premis-premis. Tahap-tahap pembuktian: Langkah 1: Membuat variabel proposisional seperti berikut: A = Badu mencontek saat ujian B = Dosen akan datang C = pengawas lalai Langkah 2: Menyusunnya menjadi ekspresi logika: (10)
A→(¬C→B)
premis
(11)
A→¬C
premis
(12)
A→B
kesimpulan
Jika ditulis akan menjadi seperti berikut: { A→(¬C→B), A→¬C} = A→B Langkah 3: Menyusunnya menjadi deretan untuk dibuat tablo dengan menegasi kesimpulan menjadi ¬(A→B) sehingga penulisan di atas menjadi: (A→(¬C→B))˄(A→¬C)˄¬(A→B) Selanjutnya, susun menjadi urutan berikut: (1)
A→(¬C→B)
(2)
A→¬C
(3)
¬(A→B)
Langkah 4: Buatlah tablonya:
LOGIKA INFORMATIKA
BY: SRI ESTI
(1)
A→(¬C→B)
(2)
A→¬C
(3)
¬(A→B)
(4)
¬¬A ¬B
(5)
A
(6)
¬A
¬C
Tutup (7)
¬A
¬C→B
Tutup (8)
¬¬C
B Tutup
(9)
C Tutup
Seluruh tablo ternyata tertutup, dan ini berati terjadi ketidakkonsistenan pada seluruh argumen. Dapat disimpulkan bahwa dengan pemberian negasi pada kesimpulan, jika premis-premis benar, maka kesimpulan tidak benar, dan sebenarnya kesimpulannya benar sehingga argumen dianggap valid.
Catatan: Jangan lupa memberi tanda negasi pada kesimpulan dari suatu argumen, sesuai dengan stategi pembalikan, dan kemudian mencari semua cabang tablo agar dipastikan tertutup. Jika semua cabang tertutup akan terjadi ketidakkonsistenan, dan berati argumen valid. Jika tablo ada yang terbuka, maka terjadi konsistensi walaupun hanya satu cabang, dan berarti argumen tidak valid. Perhatikan perbedaan antara pemberian tanda negasi dengan tidak untuk melihat perbedaannya: Tidak ada tanda negasi:
(A→A)˅(B˄¬B)
A→A ¬A
B˄¬B A
B ¬B
Tutup
LOGIKA INFORMATIKA
BY: SRI ESTI
Ada tanda negasi:
¬((A→A)˅(B˄¬B)) ¬(A→A) ¬(B˄¬B) ¬¬A ¬A A Tutup
Tablo tertutup tanpa harus menurunkan sisanya. Ini berati bentuk logika tersebut tidak mungkin diberi nilai salah.
Latihan:
Tono atau Tini pergi ke pesta. Jika Tini pergi ke pesta, maka Dewi pergi ke pesta, jika tidak Bowo pergi ke pesta. Bowo pergi ke pesta jika Tono tidak pergi ke pesta. Dengan demikian, Dewi pergi ke pesta.
Latihan soal: 1. Dengan mengguankan tablo seantik, manakah dari kumpulan ekspresi-ekspresi lokal berikut ini yang konsisten bersma-sama: a. A→B, (A˄B)→C, B˅¬A b. (A˅B)→B, A˅(C→D), A, B c. ¬A˅D, B˄¬C, C→D, E˅¬D, A˄¬E
2. Buktikan validitas argumen-argumen berikut ini dengan tablo semantik:
Jika Bowo tinggal di Jogja, dia tinggal di Indonesia. Bowo tinggal di Jogja. Dengan demikian, dia tinggal di Indonesia.
Jika Anik tinggal di Jogja, dia tinggal di Indonesia. Anik tidak tinggal di Jogja. Dengan demikian, dia tinggal di Asia Tenggara.
Jika Wawan tinggal di Jogja, ia akan berbahagia. Jika dia bahagia dan senang belajar, dia akan lulus sekolah jika dia tidak jatuh cinta. Jika dia jatuh cinta, dia akan senang belajar. Dengan demikian, jika dia tinggal di Jogja, dia akan lulus sekolah.
LOGIKA INFORMATIKA
BY: SRI ESTI
