Z3 Forall với mảng

Question

Z3 cung cấp ẩn số cho vấn đề đơn giản:

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

Tôi thấy rằng nó sẽ trở thành sat nếu phủ định forall, nhưng điều này có vẻ như là một điều đặc biệt đơn giản không thể giải quyết.

Điều này đang gây ra vấn đề vì loại vấn đề tôi muốn giải quyết giống như,

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

Trường hợp phủ định cuộc sống một mình không phải là vấn đề tương tự, vì vậy điều đó không thể được thực hiện ở đây. Có cách nào để đặt ra vấn đề kiểu này với Z3 để có được kết quả không / bão hòa không?

Answer 1

Các vấn đề với bộ định lượng luôn là vấn đề với bộ giải SMT, đặc biệt nếu chúng liên quan đến mảng và bộ định lượng xen kẽ như trong ví dụ của bạn. Về cơ bản bạn có exits u. forall y. P(u, y). Z3, hoặc bất kỳ trình giải mã SMT nào khác, sẽ gặp khó khăn trong việc giải quyết các loại vấn đề này.

Khi bạn có một khẳng định được định lượng giống như bạn làm ở nơi bạn có forallở cấp cao nhất hoặc được lồng vào exists, logic sẽ trở thành bán quyết định. Z3 sử dụng MBQI (khởi tạo bộ định lượng dựa trên mô hình) để giải quyết các vấn đề như vậy theo phương pháp phỏng đoán, nhưng nó thường không làm được như vậy. Vấn đề không chỉ là z3 không có khả năng: Không có quy trình quyết định cho những vấn đề như vậy và z3 làm hết sức mình.

Bạn có thể thử đưa ra các mẫu định lượng cho các vấn đề như vậy để giúp z3, nhưng tôi không thấy cách dễ dàng để áp dụng điều đó trong bài toán của bạn. (Các mẫu định lượng áp dụng khi bạn có các hàm chưa được giải thích và các tiên đề được định lượng. Xemhttps://rise4fun.com/z3/tutorialcontent/guide#h28). Vì vậy, tôi không nghĩ rằng nó sẽ hiệu quả với bạn. Ngay cả khi nó đã làm, các mẫu rất khó lập trình và không mạnh mẽ đối với những thay đổi trong đặc điểm kỹ thuật của bạn có thể trông vô hại.

Nếu bạn đang xử lý các bộ định lượng như vậy, các bộ giải SMT có lẽ không phù hợp. Hãy xem xét các trình dò ​​định lý bán tự động như Lean, Isabelle, Coq, v.v., được thiết kế để xử lý các bộ định lượng theo cách kỷ luật hơn nhiều. Tất nhiên, bạn mất tự động hóa hoàn toàn, nhưng hầu hết các công cụ này có thể sử dụng bộ giải SMT để xả các mục tiêu con đủ "dễ dàng". Bằng cách đó, bạn vẫn thực hiện việc "nâng nặng" theo cách thủ công, nhưng hầu hết các mục tiêu con đều do z3 tự động xử lý. (Đặc biệt trong trường hợp Lean, xem tại đây:https://leanprover.github.io/)

Answer 2

Có thêm một dấu ngoặc đóng (bên phải) cần được xóa. Ngoài ra, hãy thêm khẳng định trước câu lệnh forall.

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

Chạy đoạn mã trên và bạn sẽ nhận được câu trả lời là unsat.

Đối với chương trình thứ hai, câu trả lời của bí danh có thể hữu ích cho bạn.