7-Analisis Relasional [PDF]

Citation preview

Materi 7 : Analisis Relasional 7.1



Pendahuluan



Dalam Logika Relasional, dimungkinkan untuk menganalisis properti kalimat dengan cara yang sama seperti di Logika Proposisional. Diberikan sebuah kalimat, kita dapat menentukan validitas, kepuasan (satisfiability), dan sebagainya dengan melihat kemungkinan pernyataan kebenarannya. Dan kita dapat mengkonfirmasi entailmen logis atau persamaan logis dari kalimat dengan membandingkan pernyataan kebenaran yang memuaskan mereka dan yang tidak. Masalah utama dalam melakukan analisis semacam ini untuk Logika Relasional adalah bahwa jumlah kemungkinannya lebih besar daripada di Logika Proposisional. Untuk bahasa dengan n konstanta objek dan m relasi konstanta arity k, basis Herbrand memiliki elemen m*nk; dan akibatnya, ada 2m*nk kemungkinan pernyataan kebenaran untuk dipertimbangkan. Jika kita memiliki 10 objek dan 5 konstanta relasi arity 2, ini berarti 2500 kemungkinan. Untungnya, seperti Propositional Logic, ada beberapa pintasan yang memungkinkan kita menganalisis kalimat dalam Logika Relasional tanpa memeriksa semua kemungkinan ini. Dalam materi ini, kita mulai dengan metode tabel kebenaran dan kemudian melihat beberapa metode yang lebih efisien ini. 7.2



Tabel Kebenaran



Seperti dalam Propositional Logic, pada prinsipnya dimungkinkan untuk membangun tabel kebenaran untuk setiap rangkaian kalimat dalam Relational Logic. Tabel kebenaran ini kemudian dapat digunakan untuk menentukan validitas, kepuasan, dan sebagainya atau untuk menentukan persyaratan logis (logical entailment) dan kesetaraan logis (logical equivalence). Sebagai contoh, mari kita asumsikan kita memiliki bahasa dengan hanya dua konstanta objek 𝑎 dan 𝑏 dan dua konstanta relasi 𝑝 dan 𝑞. Sekarang pertimbangkan kalimat yang ditunjukkan di bawah ini, dan anggaplah kita ingin mengetahui apakah kalimat-kalimat ini secara logis memerlukan ∃𝑥. 𝑞(𝑥). 𝑝(𝑎) ∨ 𝑝(𝑏) ∀𝑥. (𝑝(𝑥) ⇒ 𝑞(𝑥)) Tabel kebenaran untuk masalah ini ditampilkan di bawah. Masing-masing dari empat kolom pertama mewakili salah satu elemen dasar Herbrand untuk bahasa ini. Dua kolom tengah mewakili premis (premises) kita, dan kolom terakhir mewakili kesimpulan (conclusion).



Melihat tabel tersebut, kita melihat bahwa ada 12 pernyataan kebenaran yang membuat premis pertama benar dan sembilan yang membuat premis kedua benar dan lima yang membuat keduanya benar (baris 1, 5, 6, 9, dan 11). Perhatikan bahwa setiap pernyataan kebenaran yang membuat kedua premis benar juga membuat kesimpulannya benar. Oleh karena itu, premisnya secara logis memerlukan kesimpulan. 7.3



Pohon Semantik (Semantic Trees)



Sementara metode Tabel Kebenaran bekerja pada prinsipnya, tidak praktis ketika tabel menjadi sangat besar. Seperti Propositional Logic, terkadang kita dapat menghindari pembuatan tabel seperti itu dengan secara bertahap membuat "pohon semantik" yang sesuai. Dengan menyatukan unit penjalaran dan penyederhanaan dengan pembentukan pohon, kita sering kali dapat memangkas subpohon yang tidak menguntungkan sebelum mereka dihasilkan dan dengan demikian mengurangi ukuran pohon. 7.4



Model Boolean



Tabel kebenaran dan pohon semantik adalah cara yang baik untuk merepresentasikan beberapa model secara eksplisit untuk sekumpulan kalimat. Dalam beberapa kasus, hanya ada satu model. Dalam pendekatan ini, kita menulis tabel kosong untuk setiap relasi dan kemudian mengisi nilai berdasarkan batasan masalah. Misalnya, untuk batasan unit apa pun, kita dapat segera memasukkan nilai kebenaran yang sesuai di kotak yang sesuai. Dengan penetapan parsial ini, kita kemudian menyederhanakan batasan (seperti dalam metode pohon semantik), mungkin mengarah ke batasan unit baru. Kita lanjutkan sampai tidak ada lagi kendala unit.



Sebagai contoh, pertimbangkan masalah Perkumpulan yang diperkenalkan di materi 1. Kita diberi batasan yang ditunjukkan di bawah ini, dan kita ingin tahu apakah Dana menyukai semua orang yang disukai Bess. Dengan kata lain, kita ingin memastikan bahwa, di setiap model yang memenuhi kalimat ini, Dana menyukai semua orang yang disukai Bess. Dana menyukai Cody. Abby tidak menyukai Dana. Dana tidak menyukai Abby. Abby menyukai semua orang yang disukai Bess. Bess menyukai Cody atau Dana. Abby dan Dana sama-sama tidak menyukai Bess. Cody menyukai semua orang yang menyukainya. Tidak ada yang menyukai dirinya sendiri. Dalam kasus khusus ini, ternyata hanya ada satu model yang memenuhi semua kalimat ini. Langkah pertama dalam membuat model ini adalah membuat tabel kosong untuk relasi likes.



Data yang kita berikan ada tiga unit: fakta Dana suka Cody, fakta Abby tidak suka Dana dan Dana tidak suka Abby. Dengan menggunakan informasi ini, kita dapat menyempurnakan model kita dengan meletakkan satu di kotak ketiga di baris keempat dan meletakkan nol di kotak keempat dari baris pertama dan kotak pertama di baris keempat.



Sekarang, kita tahu bahwa Abby menyukai semua orang yang disukai Bess. Jika Bess menyukai Dana, maka kita dapat menyimpulkan bahwa Abby juga menyukai Dana. Kita sudah tahu Abby tidak suka Dana, jadi Bess pasti juga tidak suka Dana.



Pada saat yang sama, kita tahu bahwa Bess menyukai Cody atau Dana. Karena Bess tidak menyukai Dana, dia pasti menyukai Cody. Sekali lagi menggunakan fakta bahwa Abby menyukai semua orang yang disukai Bess, kita tahu bahwa Abby juga menyukai Cody.



Abby dan Dana sama-sama tidak menyukai Bess. Menggunakan fakta ini kita bisa menambahkan 0 ke sel pertama dan terakhir dari kolom kedua.



Di sisi lain, Cody menyukai semua orang yang menyukainya. Ini memungkinkan kita untuk meletakkan 1 di setiap kolom dari baris ketiga di mana ada 1 di baris yang sesuai dari kolom ketiga.



Karena tidak ada yang menyukai dirinya sendiri, kita dapat menempatkan 0 di setiap sel secara diagonal.



Akhirnya, dengan menggunakan fakta bahwa Abby menyukai semua orang yang disukai Bess, kita menyimpulkan bahwa Bess tidak menyukai Abby. (Jika dia melakukannya maka Abby akan menyukai dirinya sendiri, dan kita tahu itu salah.)



Pada titik ini, kita memiliki model yang lengkap, dan kita dapat memeriksa kesimpulan kita untuk melihat bahwa model ini memenuhi kesimpulan yang diinginkan. Dalam hal ini, mudah untuk melihat bahwa Dana memang menyukai semua orang yang disukai Bess. Kita memotivasi metode ini dengan membicarakan kasus-kasus di mana kalimat yang diberikan memiliki model yang unik, seperti dalam kasus ini. Namun, metode tersebut juga dapat bermanfaat meskipun ada beberapa model yang memungkinkan.



Misalnya, jika kita telah mengabaikan keyakinan bahwa Cody menyukai semua orang yang menyukainya, kita masih memiliki delapan model (sesuai dengan delapan kemungkinan kombinasi perasaan Cody terhadap Abby, Bess, dan Dana). Namun, bahkan dengan ambiguitas ini, dimungkinkan untuk menentukan apakah Dana menyukai semua orang yang disukai Bess hanya dengan menggunakan bagian tabel yang sudah terisi. 7.5



Model Non-Boolean



Seperti yang dijelaskan di materi 6, model dalam Relational Logic adalah pernyataan nilai kebenaran ke atom dasar bahasa kita. Kita memperlakukan setiap atom dasar dalam bahasa kita sebagai variabel dan menetapkannya sebagai nilai kebenaran tunggal (1 atau 0). Secara umum, ini adalah cara yang baik untuk melanjutkan. Namun, terkadang kita dapat melakukannya dengan lebih baik. Pertimbangkan, misalnya, teori dengan empat konstanta objek dan dua konstanta relasi unery. Dalam kasus ini, akan ada delapan elemen di basis Herbrand dan 28 (256) kemungkinan penetapan kebenaran. Sekarang, misalkan kita memiliki batasan bahwa setiap relasi adalah benar untuk satu dan hanya satu objek. Sebagian besar penugasan ini tidak akan memenuhi batasan nilai tunggal dan karenanya menganggapnya sia-sia. Untungnya, dalam kasus seperti ini, ada representasi untuk penetapan kebenaran yang memungkinkan kita menghilangkan kemungkinan seperti itu dan dengan demikian menghemat pekerjaan. Daripada memperlakukan setiap atom dasar sebagai variabel terpisah dengan nilai Booleannya sendiri, kita dapat menganggap setiap relasi sebagai variabel dengan 4 kemungkinan nilai. Untuk menganalisis kalimat dalam teori semacam itu, kita hanya perlu mempertimbangkan 42 (16) kemungkinan. Bahkan jika kita mencari seluruh ruang tugas, ini merupakan penghematan yang signifikan atas metode tabel kebenaran murni. Selain itu, kita dapat menggabungkan representasi ini dengan teknik yang dijelaskan sebelumnya untuk menemukan tugas untuk variabel non-Boolean ini dengan cara yang lebih efisien. Permainan Sukoshi menggambarkan teknik ini dan manfaatnya. (Sukoshi mirip dengan Sudoku, tetapi lebih kecil dan lebih sederhana.) Teka-teki Sukoshi biasanya dimainkan di papan 4x4. Dalam contoh khas Sukoshi, beberapa kotak sudah terisi, seperti pada contoh di bawah ini. Tujuan permainan ini adalah untuk menempatkan angka 1 sampai 4 di sisa kotak papan sedemikian rupa sehingga tidak ada angka yang berulang di baris atau kolom manapun.



Kita bisa memformalkan aturan teka-teki ini dalam bahasa Logika. Setelah kita melakukannya, kita dapat menggunakan teknik yang dijelaskan di sini untuk menemukan solusi. Dalam formalisasi kita, kita menggunakan ekspresi 𝑐𝑒𝑙𝑙(1,2,3) untuk mengekspresikan fakta bahwa sel di baris pertama dan kolom kedua berisi angka 3. Sebagai contoh, kita dapat mendeskripsikan papan awal yang ditunjukkan di atas dengan yang berikut ini kalimat. 𝑐𝑒𝑙𝑙(1,2,4) 𝑐𝑒𝑙𝑙(1,4,1) 𝑐𝑒𝑙𝑙(2,1,2) 𝑐𝑒𝑙𝑙(3,4,3) 𝑐𝑒𝑙𝑙(4,3,4) Kita menggunakan ekspresi yang 𝑠𝑎𝑚𝑒(𝑥, 𝑦) untuk mengatakan bahwa 𝑥 sama dengan 𝑦. Kita dapat melakukan aksioma yang sama hanya dengan menyatakan kapan itu benar dan di mana itu salah. Aksiomatisasi yang disingkat ditampilkan di bawah ini.



Dengan menggunakan kosakata ini, kita dapat menulis aturan yang mendefinisikan Sukoshi seperti yang ditunjukkan di bawah ini. Kalimat pertama mengungkapkan batasan bahwa dua sel di baris yang sama tidak boleh berisi nilai yang sama. Kalimat kedua mengungkapkan batasan bahwa dua sel di kolom yang sama tidak dapat berisi nilai yang sama. Batasan ketiga mengungkapkan fakta bahwa setiap sel harus berisi setidaknya satu nilai.



Sebagai langkah pertama dalam memecahkan masalah ini, kita mulai dengan memusatkan perhatian pada kolom keempat, karena dua sel di kolom itu sudah terisi. Kita tahu bahwa pasti ada angka 4 di salah satu sel. Ini tidak bisa menjadi yang pertama, karena sel itu berisi 1, dan itu tidak bisa menjadi yang ketiga karena sel itu berisi 3. Ia juga tidak boleh menjadi yang keempat, karena sudah ada 4 di sel ketiga dari baris keempat. Dengan proses eliminasi, angka 4 harus masuk ke sel keempat dari baris kedua, mengarah ke papan yang ditunjukkan di bawah ini.



Pada titik ini, ada empat di setiap baris dan setiap kolom kecuali kolom pertama di baris ketiga. Jadi, kita bisa dengan aman menempatkan empat di sel itu.



Karena hanya ada satu sel kosong di kolom keempat, kita tahu itu harus diisi dengan satu nilai yang tersisa, yaitu: 2. Setelah menambahkan nilai ini, kita memiliki papan berikut.



Sekarang, mari kita alihkan perhatian kita ke kolom pertama. Kita tahu bahwa pasti ada angka 1 di salah satu sel. Tidak boleh yang pertama, karena sudah ada 1 di baris itu, dan tidak boleh yang kedua atau ketiga karena sel tersebut sudah berisi nilai. Akibatnya, angka 1 harus berada di sel pertama dari baris keempat.



Sekali lagi, kita memiliki kolom dengan semua kecuali satu sel terisi. Kolom 1 memiliki 2 di sel kedua, 4 di sel ketiga, dan 1 di sel keempat. Jadi, kita bisa menempatkan 3 di sel pertama kolom itu.



Pada titik ini, kita dapat mengisi satu sel kosong di baris pertama, menuju ke papan berikutnya.



Dan kita juga bisa mengisi satu sel kosong di baris keempat.



Sekarang, mari kita perhatikan kolom kedua. Kita tidak bisa meletakkan 2 di sel kedua, karena sudah ada 2 di baris itu. Karena sel pertama dan terakhir sudah penuh, satu-satunya pilihan adalah meletakkan 2 di sel ketiga.



Menyelesaikan baris ketiga mengarah ke papan di bawah.



Menyelesaikan kolom ketiga mengarah ke papan berikut.



Akhirnya, kita bisa menempatkan 1 di sel kedua dari baris kedua. Dan, dengan itu, papan sudah penuh. Kita memiliki angka yang berbeda di setiap baris dan setiap kolom, seperti yang disyaratkan oleh aturan.



Mengingat tugas awal dalam kasus ini, cukup mudah untuk menemukan tugas lengkap yang memenuhi batasan Sukoshi. Untuk tugas awal lainnya, memecahkan masalah lebih sulit. Namun, teknik yang dijelaskan di sini masih berfungsi untuk mengurangi jumlah pekerjaan yang diperlukan. Nyatanya, hampir semua teka-teki Sukoshi dapat diselesaikan dengan menggunakan teknik ini tanpa trial and error dalam bentuk apa pun.