Ambiguitas dan Logika

Dalam teori automata (automata terbatas, automata pushdown, ...) dan dalam kompleksitas, ada gagasan "ambiguitas". Otomat bersifat ambigu jika ada kata $w$ dengan setidaknya dua proses penerimaan yang berbeda. Sebuah mesin $k$ ambigu jika untuk setiap kata $w$ diterima oleh mesin paling tidak ada $k$ berjalan berbeda untuk menerima $w$ .

Gagasan ini juga didefinisikan atas tata bahasa bebas konteks: tata bahasa bersifat ambigu jika ada kata yang dapat diturunkan dalam dua cara yang berbeda.

Juga diketahui bahwa banyak bahasa memiliki karakterisasi logis yang bagus di atas model yang terbatas. (Jika bahasa $L$ teratur, ada rumus urutan kedua monadik $\phi$ atas kata-kata sedemikian sehingga setiap kata $w$ dari $L$ adalah model $\phi$ , sama dengan NP jika setara dengan rumus urutan Kedua di mana setiap kuantifikasi urutan kedua eksistensial.)

Oleh karena itu, pertanyaan saya ada di tepi dua domain: apakah ada hasil, atau bahkan definisi kanonik, "ambiguitas" dari formula dari logika yang diberikan?

Saya bisa membayangkan beberapa definisi:

• $\exists x \phi(x)$ tidak ambigu jika terdapat paling banyak satu$x$ sehingga$\phi(x)$ berlaku dan$\phi(x)$ tidak ambigu.
• $\phi_0\lor\phi_1$ akan ambigu jika ada model keduanya$\phi_0$ dan$\phi_1$ , atau jika$\phi_i$ ambigu.
• Rumus SAT akan non-ambigu jika ada paling banyak satu tugas yang benar.

Oleh karena itu, saya bertanya-tanya apakah itu adalah gagasan terkenal, kalau tidak, mungkin menarik untuk mencoba melakukan penelitian tentang topik ini. Jika gagasan ini diketahui, adakah yang bisa memberi saya kata kunci yang dapat saya gunakan untuk mencari informasi tentang masalah ini (karena "ambiguitas logika" memberikan banyak hasil yang tidak terkait), atau buku / pdf / referensi artikel?

Aturan dalam tata bahasa dan aturan inferensi dalam logika dapat dianggap sebagai aturan produksi yang memberi kita "barang baru" dari "barang yang diketahui". Seperti halnya ada banyak cara untuk menghasilkan (atau mengurai) sebuah kata sehubungan dengan tata bahasa, demikian juga ada banyak cara untuk menghasilkan (atau membuktikan) formula logis. Analogi ini dapat ditarik lebih jauh. Sebagai contoh, sistem logis tertentu menerima bentuk-bentuk bukti normal. Demikian juga, tata bahasa tertentu mengakui pohon parse kanonik.

Jadi saya katakan contoh Anda dari logika akan ke arah yang salah. Analogi yang benar adalah

"parse tree": "word" = "proof": "formula logis"

Bahkan, jenis tata bahasa yang cukup umum akan dapat mengekspresikan aturan logika inferensi tipikal, sehingga kata-kata yang benar secara tata bahasa akan menjadi formula yang dapat dibuktikan secara tepat. Dalam hal ini pohon parse akan menjadi buktinya.

Dalam arah yang berlawanan, jika kita mau memikirkan aturan inferensi yang sangat umum (yang tidak harus memiliki rasa logis tradisional), maka setiap tata bahasa akan diekspresikan sebagai sistem aksioma (terminal) dan aturan inferensi (produksi). Dan sekali lagi kita akan melihat bahwa buktinya sama dengan pohon parse.

Hanya dua komentar. Saya harap mereka membantu.

Definisi standar semantik logika dan kebenaran mengikuti presentasi Tarski, melanjutkan dengan induksi pada struktur formula. Kemungkinan lain adalah memberikan semantik berbasis game seperti yang disarankan oleh Hintikka. Kebenaran dan kepuasan semua didefinisikan dalam hal strategi dalam permainan. Untuk formula orde pertama, orang dapat membuktikan bahwa formula itu benar di bawah gagasan Tarski jika dan hanya jika ada strategi kemenangan di permainan Hintikka.

Menuju memformalkan pertanyaan Anda, orang dapat bertanya apakah permainan mengakui beberapa strategi. Ada juga pertanyaan menarik tentang apakah strategi harus ditentukan. Hintikka mengharuskan mereka untuk menjadi deterministik. Bukti bahwa aslinya Hintikka dan semantik Tarski adalah setara membutuhkan Aksioma Pilihan. Seseorang juga dapat memformalkan kebenaran dalam hal permainan dengan strategi non-deterministik dengan komplikasi yang lebih sedikit.

Contoh teori bahasa Anda mengingatkan determinisme, hubungan simulasi, dan penerimaan bahasa. Hubungan simulasi antara automata menyiratkan inklusi bahasa antara bahasa mereka meskipun sebaliknya tidak benar. Untuk automata deterministik, kedua gagasan itu bertepatan. Orang dapat bertanya apakah mungkin untuk memperluas hubungan simulasi dengan cara yang 'halus' untuk menangkap kesetaraan bahasa untuk automata non-deterministik. Kousha Etessami memiliki makalah yang sangat bagus yang menunjukkan bagaimana melakukan ini dengan menggunakan k-simulasi ( A Hierarchy of Polynomial-Time Computable Simulasi untuk Automata). Secara intuitif, 'k' mencerminkan tingkat non-determinisme yang dapat ditangkap oleh hubungan simulasi. Ketika 'k' sama dengan tingkat non-determinisme dalam otomat, simulasi dan kesetaraan bahasa bertepatan. Makalah itu juga memberikan karakterisasi logis dari k-simulasi dalam hal logika modal poladik dan fragmen variabel terikat dari logika orde pertama. Anda mendapatkan inklusi bahasa, determinisme, game, logika modal, dan logika urutan pertama, semuanya dalam satu paket bemper.

Ini dimulai sebagai komentar di bawah jawaban Andrej Bauer, tetapi terlalu besar.

Saya pikir definisi yang jelas tentang ambiguitas dari sudut pandang Teori Model Hingga adalah: $ambiguous(\phi) \implies \exists M_1,M_2 | M_1 \vDash \phi \wedge M_2 \vDash \phi \wedge M_1 \vDash \psi \wedge M_2 \nvDash \psi$

Dengan kata lain, ada model tata bahasa Anda yang dikodekan sebagai rumus yang dapat dibedakan dengan beberapa rumus ψ , mungkin sub-rumus ϕ .$\phi$$\psi$$\phi$

Anda dapat menghubungkan ini dengan respons Andrej tentang bukti melalui Kompleksitas Deskriptif. Kombinasi dari keberadaan pengkodean model tertentu ditambah penerimaannya oleh TM yang sesuai sebagai model formula yang diberikan ADALAH bukti bahwa aksioma dan inferensi (dan karenanya tata bahasa setara) dikodekan dalam formula itu konsisten.

Untuk membuat ini sepenuhnya kompatibel dengan jawaban Andrej, Anda harus mengatakan bahwa model itu "dihasilkan" oleh rumus yang bertindak sebagai filter pada ruang semua model yang mungkin terbatas (atau sesuatu seperti itu), dengan penyandian dan tindakan penyaringan pada model input sebagai "bukti". Bukti yang berbeda kemudian menyaksikan ambiguitas.

Ini mungkin bukan sentimen populer, tetapi saya cenderung menganggap teori model hingga dan teori pembuktian sebagai hal yang sama dilihat dari sudut yang berbeda. ;-)

Tidak yakin tentang pertanyaan yang diterapkan ke CS, tetapi coba cari istilah Vagueness and logic. Dalam filsafat logika, ambiguitas biasanya dibuat berbeda dari ketidakjelasan (lihat di sini misalnya), dan saya pikir apa yang Anda cari adalah ketidakjelasan (karena ketidakjelasan didefinisikan sebagai istilah di mana ada kasus batas). Buku utama dalam bidang ini adalah Ketidakjelasan Timothy Williamson (tetapi juga lihat daftar pustaka di situs Stanford di atas).

Saya (juga) setuju dengan Anrej.

Saya pikir kompleksitas deskriptif adalah karakterisasi tanpa komputasi (yang membuatnya menarik dengan caranya sendiri) dan oleh karena itu contoh ambiguitas komputasi dari teori bahasa formal (automata / tata bahasa / ...) yang Anda berikan terlihat berada dalam domain yang sangat berbeda . Dalam kompleksitas bahasa deskriptif sesuai dengan kelas kompleksitas dan kueri (dalam bahasa) sesuai dengan masalah komputasi (bukan algoritma). Tidak ada cara yang dimaksudkan untuk memeriksa / menghitung kueri AFAIK, jadi jika Anda tidak mencari ambiguitas komputasi IMHO contoh-contoh tersebut menyesatkan.