Z3 Forall dengan array

Question

Z3 tidak diketahui untuk masalah sederhana:

(assert
(forall ((y (Array Int Int)))
   (= (select y 1) 0))
 )
(check-sat)

Saya telah menemukan bahwa itu menjadi sat jika meniadakan forall, tetapi ini sepertinya hal yang sangat sederhana untuk tidak dapat dipecahkan.

Ini menyebabkan masalah karena kelas masalah yang ingin saya selesaikan lebih seperti,

(declare-fun u () Int)
(assert
 (forall ((y (Array Int Int)) )
     (=> 
        (= u 0) (<= (select y 1) 0))
 )
)
(check-sat)

Dimana meniadakan forall saja bukanlah masalah yang sama, sehingga tidak bisa dilakukan disini. Adakah cara untuk mengajukan jenis masalah ini ke Z3 untuk mendapatkan hasil un / sat?

Answer 1

Masalah dengan bilangan selalu bermasalah dengan pemecah SMT, terutama jika melibatkan larik dan bilangan bolak-balik seperti dalam contoh Anda. Anda pada dasarnya memiliki exits u. forall y. P(u, y). Z3, atau pemecah SMT lainnya, akan kesulitan menangani masalah semacam ini.

Ketika Anda memiliki pernyataan terukur seperti yang Anda lakukan di mana Anda berada foralldi level teratas atau bersarang exists, logika menjadi semi-decidable. Z3 menggunakan MBQI (model-based quantifier instantiation) untuk memecahkan masalah tersebut secara heuristik, tetapi sering kali gagal melakukannya. Masalahnya bukan hanya karena z3 tidak mampu: Tidak ada prosedur keputusan untuk masalah tersebut, dan z3 melakukan yang terbaik.

Anda dapat mencoba memberikan pola pembilang untuk masalah seperti itu untuk membantu z3, tetapi saya tidak melihat cara mudah untuk menerapkannya dalam masalah Anda. (Pola pengukur berlaku jika Anda memiliki fungsi yang tidak diinterpretasikan dan aksioma yang dikuantifikasi. Lihathttps://rise4fun.com/z3/tutorialcontent/guide#h28). Jadi, saya rasa itu tidak akan berhasil untuk Anda. Meskipun demikian, pola sangat sulit untuk diprogram, dan tidak kuat terkait dengan perubahan dalam spesifikasi Anda yang mungkin terlihat tidak berbahaya.

Jika Anda berurusan dengan bilangan seperti itu, pemecah SMT mungkin tidak cocok. Lihatlah ke dalam penguji teorema semi-otomatis seperti Lean, Isabelle, Coq, dll., Yang dirancang untuk menangani pembilang dengan cara yang jauh lebih disiplin. Tentu saja, Anda kehilangan otomatisasi penuh, tetapi sebagian besar alat ini dapat menggunakan pemecah SMT untuk menjalankan sub-tujuan yang "cukup mudah". Dengan begitu, Anda masih melakukan "pekerjaan berat" secara manual, tetapi sebagian besar sub-tujuan secara otomatis ditangani oleh z3. (Khususnya dalam kasus Lean, lihat di sini:https://leanprover.github.io/)

Answer 2

Ada satu tanda kurung penutup (kanan) tambahan, yang perlu dihapus. Juga, tambahkan assert sebelum pernyataan forall.

(assert ( forall ( (y (Array Int Int) ) ) 
   (= (select y 1) 0) 
))
(check-sat)

Jalankan kode di atas dan Anda akan mendapatkan unsat sebagai jawabannya.

Untuk program kedua, semoga jawaban alias 'berguna bagi Anda.