Вычислить минимальное значение Bitvector в Z3

Question

У меня есть следующий фрагмент кода: (объявлять-сопзЬ L4 (_ BitVec 6)) (объявлять-Const L1 (_ BitVec 6)) (объявлять-Const L0 (_ BitVec 6)) (объявлять-Const l2 (_ BitVec 6))

(assert (= l2 (_ bv8 6))) 

;; All is encoding the set that contains {0, 1, 2, 3, 4, 5} 
(define-const All (_ BitVec 6) #b111111) 
;; Empty is encoding the empty set 
(define-const Empty (_ BitVec 6) #b000000) 

(define-fun LT_l ((S (_ BitVec 6)) (l (_ BitVec 6))) Bool 
    ;; True if for all x in S x < l 
    (= (bvand (bvshl All l) S) Empty)) 

(define-fun is_in ((e (_ BitVec 6)) (S (_ BitVec 6))) Bool 
    ;; True if e is an element of the "set" S. 
    (not (= (bvand (bvshl (_ bv1 6) e) S) Empty))) 

(define-fun is_minimal ((e (_ BitVec 6)) (S (_ BitVec 6))) Bool 
    ;; True if e is the minimal element of S 
    (and (is_in e S) ;; S contains e 
     ;; (1 << e) - 1 represents the set of elements that are smaller than e 
     (= (bvand (bvsub (bvshl (_ bv1 6) e) (_ bv1 6)) S) Empty))) 

;; To encode that forall x in L0 and forall y in L1. x < y 
(define-fun LT ((L0 (_ BitVec 6)) (L1 (_ BitVec 6))) Bool 
    ; True if forall x in L0 and forall y in L1, x < y 
    (or (= L0 Empty) 
     (= L1 Empty) 
     (exists ((min (_ BitVec 6))) (and (is_minimal min L1) (LT_l L0 min))))) 

(assert (not (= L0 Empty))) 
(assert (not (= L1 Empty))) 
(assert (not (= L4 Empty))) 
(assert (LT_l L4 l2)) 
(assert (LT L0 L1)) 
(check-sat) 
(get-model) 
(assert (LT L1 L0)) 
(check-sat) 

Когда я запускаю этот код я модель: сидел (модель (определить-потеха мин 0() (_ BitVec 6) # b000011) (define-fun L1() (_ BitVec 6) # b001000) (определить-весело L0() (_ BitVec 6) # b000100) (определить-весело L4() (_ BitVec 6) # b000100) (определить-весело l2() (_ BitVec 6) # b001000) ) unsat

Почему результат min является:

(define-fun min!0() (_ BitVec 6) 
    #b000011) 

и не b001000, так как наименьшее значение L1 это и не b000011.

Кто-то может мне объяснить?

Наконец, я определяю функцию Lt_l, которая проверяет, что для всех x в S x < l, но теперь я хотел сделать GT_l, который проверяет, что для всех x в S l < x. У меня есть следующий код:

(define-fun GT_l ((S (_ BitVec 6)) (l (_ BitVec 6))) Bool 
    (= (bvand (bvneg (bvshl (_ bv0 6) l)) S) Empty)) 

Но это не работает почему?

Благодаря

Answer 1

В вашем примере, вы представляете наборы с использованием битовых векторов. Например, бит-вектор #b101000 представляет собой набор {5, 3}. Выход (define-fun L1() (_ BitVec 6) #b001000) в основном говорит о том, что L1 является «установленным» {3}. Одна из возможных путаниц заключается в том, что битовые векторы используются для представления множеств и элементов. Битовый вектор min!0 представляет собой элемент. Выход (define-fun min!0() (_ BitVec 6) #b000011) говорит, что min!0 - это значение 3, и это действительно «минимальное значение» в L1.