Существует ли глобальная конструкция forall на языке SMT или расширение Z3?

По умолчанию глобальные переменные рассматриваются как экзистенциально квантифицированные. Например.

(declare-const x Int)
(assert (exists ((y Int)) (and (= x y) (= x y))))
(check-sat)
(get-model)

Дает

sat
(model 
  (define-fun y!0 () Int
    0)
  (define-fun x () Int
    0)
)

Как заставить его рассматривать x как forall x, как в этом запросе:

(assert (forall ((x Int)) (exists ((y Int)) (and (= x y) (= x y)))))
(check-sat)
(get-model)

Чтобы получить значение y, зависит от x:

sat
(model 
  (define-fun y!0 ((x!1 Int)) Int
    x!1)
)

Это должно быть просто вопросом синтаксиса. Возможно ли это в z3? В другом решателе SMT?

Редактировать:

Чего я хочу добиться, так это выполнить скрипт, например:

(declare-forall-const x Int)
(declare-const y Int)
(assert (and (= x y) (= x y)))
(check-sat)
(get-model)

И получить ответ вида:

sat
(model 
  (define-fun y!0 ((x!1 Int)) Int
    x!1)
)

Другими словами, я хочу объявить параметр forall глобально и ссылаться на него в последующих утверждениях.


person Necto    schedule 13.02.2016    source источник
comment
Чтобы заставить Z3 рассматривать x как универсальное, вы добавляете квантификатор forall, как вы и предлагаете. Итак, я не уверен, в чем проблема.   -  person Christoph Wintersteiger    schedule 13.02.2016
comment
@ChristophWintersteiger, я хочу ввести много таких переменных x1, x2, ..., шаг за шагом, а не в одной assert. Итак, я хочу построить запрос, постепенно вводя условия и переменные (как экзистенциальные, так и универсальные) в контекст один за другим.   -  person Necto    schedule 13.02.2016
comment
Я до сих пор не вижу, в чем проблема. Обратите внимание, что вы можете использовать несколько квантификаторов, например. (навсегда (существует (навсегда (существует....)))).   -  person Christoph Wintersteiger    schedule 14.02.2016
comment
@ChristophWintersteiger, проблема заключается в пошаговом построении запроса путем предоставления множества утверждений и объявлений, постепенно заполняющих контекст z3. Я хочу воспользоваться преимуществами директив z3 push/pop и запустить один экземпляр решателя для нескольких похожих запросов (как обычно делают symbex)   -  person Necto    schedule 14.02.2016
comment
Да, это нормально, и вы можете создавать свои запросы постепенно, и вы можете использовать push/pop. Я до сих пор не вижу, в чем проблема. Есть ли что-то, что не работает?   -  person Christoph Wintersteiger    schedule 14.02.2016
comment
@ChristophWintersteiger, да. Я не могу нажать определение forall x.   -  person Necto    schedule 14.02.2016
comment
Как вы пытаетесь это сделать? Утверждение формулы, содержащей кванторы, ничем не отличается от добавления утверждений без кванторов. Обратите внимание, что (push n) принимает целое число, а не утверждение (это количество областей, которые вы хотите нажать).   -  person Christoph Wintersteiger    schedule 15.02.2016
comment
Кроме того, оба ваших скрипта прекрасно работают, они делают именно то, что должны делать, за исключением, возможно, того, что y!0 можно удалить из модели. Что вы ожидаете, что они вернутся?   -  person Christoph Wintersteiger    schedule 15.02.2016
comment
@ChristophWintersteiger, я расширил вопрос. По сути, мне нужна глобальная декларация declare-forall-const forall, точно так же, как declare-const является глобальной декларацией exists.   -  person Necto    schedule 15.02.2016


Ответы (1)


Это невозможно. В решателе SMT все самые внешние переменные являются экзистенциальными, но никто не заставляет вас использовать только самые внешние переменные. Если у вас есть только одна область квантификатора, популярным подходом является отрицание запроса, то есть вместо проверки выполнимости forall x . phi(x) вы можете проверить невыполнимость exists x . not phi(x).

person Christoph Wintersteiger    schedule 15.02.2016