Lấy một lõi "không" tốt với z3 (logic QF_BV)

Question

Tôi đang sử dụng bộ giải Z2 SMT để giải quyết một vấn đề mà tôi đã thể hiện trong logic QF_BV, sử dụng ngôn ngữ SMTLIB 2.

Mô hình không hài lòng và tôi đang cố gắng để người giải quyết tạo ra một lõi không xác định.

Mô hình của tôi bao gồm một số ràng buộc 'bắt buộc', mà tôi chỉ định sử dụng câu lệnh assert.

Các xác nhận mà tôi muốn được xem xét cho thế hệ không lõi, đã được chỉ định bằng cách sử dụng cấu trúc (assert (! (EXPR) :named NAME)).

Z3 cung cấp cho tôi unsat, như mong đợi. Tuy nhiên, Z3 dường như luôn đổ một "unsat-core" tầm thường bao gồm TẤT CẢ các xác nhận được đặt tên.

Tôi biết rằng có tồn tại một tập hợp con các xác nhận được đặt tên của tôi, đó là một unsat-core. Tôi tìm thấy lõi này bằng cách sử dụng Yices SMT solver, mà thường xuyên mang lại cho tôi tương đối nhỏ hơn unsat-lõi. Mô hình Yices giống với mô hình Z3 (khá nhiều bản dịch từng dòng từ SMT2 sang ngôn ngữ nhập Yices).

Sản xuất các tính năng "tốt" không phải là một tính năng cụ thể của trình giải quyết, hoặc có bất kỳ đề xuất/thay đổi chung nào mà tôi có thể thực hiện để giúp Z3 cung cấp cho tôi cốt lõi tốt hơn không?

Answer 1

Z3 và Yices 1.x sử dụng cùng một cách tiếp cận để tính toán các lõi không xác định. Theo dõi tất cả các xác nhận được sử dụng trong bằng chứng về sự không hài lòng. Tuy nhiên, các bằng chứng được xây dựng bởi mỗi hệ thống có thể khá khác nhau. Có các thuật toán để tính toán các lõi chưa được tối thiểu trên các khả năng được cung cấp bởi Z3 và Yices. Đây là reference.

EDIT: theo mặc định, Z3 sử dụng một số bước xử lý trước trước khi nó cố gắng giải quyết sự cố. Một số bước có thể ảnh hưởng đến việc tạo ra lõi unsat. Đặc biệt, nó loại bỏ các hằng số bằng cách sử dụng các phương trình trong bài toán. Chúng tôi nói Z3 "giải quyết" các phương trình và loại bỏ các biến. Trong số script, bạn có thể nhận được một lõi nhỏ hơn bằng cách vô hiệu hóa bước này. Chúng tôi có thể thực hiện điều đó bằng cách sử dụng tùy chọn

(set-option :auto-config false) 

Z3 sẽ thực thi cấu hình chung. Đối với vấn đề bit vector nó thường là một ý tưởng tốt để vô hiệu hóa "tuyên truyền relevacy":

(set-option :relevancy 0) 

Cuối cùng, chúng tôi bây giờ có thể bật/tắt các bước loại bỏ biến, và thấy hiệu ứng về kích thước lõi unsat.

(set-option :solver true) ;; Z3 will generate the core C0 C1 C2 
(set-option :solver false) ;; Z3 will generate the core C1 C2