Как использовать Z3 и CVC4 с SMT-LIB для доказательства теорем для группы диэдра D3

В предыдущем сообщении была доказана одна теорема для группы диэдра D3 с использованием Z3 SMT-LIB. В этом посте мы пытаемся доказать эту теорему, используя как Z3, так и CVC4, используя следующий код SMT-LIB:

(set-logic AUFNIRA)
(set-option :produce-models true)
(set-option :incremental true)
(declare-sort S 0)
(declare-fun f (S S) S)
(declare-fun g (S) S)
(declare-fun E () S)
(declare-fun R1 () S)
(declare-fun R2 () S)
(declare-fun R3 () S)
(declare-fun R4 () S)
(declare-fun R5 () S)
(assert (forall ((x S))
            (= (f x E) x)))
(assert (forall ((x S))
            (= (f E x) x)))               
(assert (= (f R1 R1) R2))
(assert (= (f R1 R2) E))
(assert (= (f R1 R3) R4))
(assert (= (f R1 R4) R5))
(assert (= (f R1 R5) R3))
(assert (= (f R2 R1) E))
(assert (= (f R2 R2) R1))
(assert (= (f R2 R3) R5))
(assert (= (f R2 R4) R3))
(assert (= (f R2 R5) R4))
(assert (= (f R3 R1) R5))
(assert (= (f R3 R2) R4))
(assert (= (f R3 R3) E))
(assert (= (f R3 R4) R2))
(assert (= (f R3 R5) R1))
(assert (= (f R4 R1) R3))
(assert (= (f R4 R2) R5))
(assert (= (f R4 R3) R1))
(assert (= (f R4 R4) E))
(assert (= (f R4 R5) R2))
(assert (= (f R5 R1) R4))
(assert (= (f R5 R2) R3))
(assert (= (f R5 R3) R2))
(assert (= (f R5 R4) R1))
(assert (= (f R5 R5) E))
(assert (= (g E) E))
(assert (= (g R1) R2))
(assert (= (g R2) R1))
(assert (= (g R3) R3))
(assert (= (g R4) R4))
(assert (= (g R5) R5))
(check-sat)
(get-model)
(get-value ((f (f R3 R1) (g R3))))
(get-value (R2))
(assert (not (= (f (f R3 R1) (g R3)) R2))) 
(check-sat) 

Когда этот код выполняется с использованием Z3 или CVC4, получаются правильные результаты. Запустите этот код с Z3 онлайн здесь

Вопросы таковы:

  1. В случае Z3 создается сообщение unsupported ; :incremental. Это сообщение, кажется, не меняет результаты, почему?

  2. В случае CVC4 создается сообщение unknown, а Z3 выдает sat. Опять же, это сообщение, похоже, не меняет результатов, почему?

  3. Как выполнить код SMT-LIB с помощью Mathsat.


person Juan Ospina    schedule 23.11.2013    source источник


Ответы (2)


Что касается вопроса 1, опция :incremental не является частью стандарта SMT-LIB 2.0. Стандарт определяет/предлагает небольшой набор опций, которые должны поддерживаться всеми решателями, и :incremental не входит в их число. Вероятно, это специфическая опция CVC4. Z3 просто игнорирует эту команду. Более того, Z3 не требует от пользователя включения пошагового решения.

Что касается вопроса 2, стандарт SMT-LIB 2.0 говорит, что для check-sat существует 3 возможных выхода: unsat, sat и unknown. Результат unknown используется, когда решателю не удалось установить, является ли набор утверждений выполнимым или нет. Некоторые решатели создают «кандидатную модель», даже если они производят unknown.

Насколько я знаю, MathSAT 5 пока не поддерживает квантификаторы. Однако это должно измениться в будущем.

person Leonardo de Moura    schedule 23.11.2013
comment
Большое спасибо, ваши ответы очень полезны. В случае Mathsat, пожалуйста, смотрите ниже. - person Juan Ospina; 23.11.2013
comment
Обратите внимание, что строка 13 содержит forall, и (насколько мне известно) MathSAT не поддерживает квантификаторы. - person Leonardo de Moura; 24.11.2013
comment
Вы правы, в Mathsat необходимо заменить forall на соответствующий набор утверждений. Большое спасибо. - person Juan Ospina; 24.11.2013

Mathsat, кажется, дает правильные результаты, но генерирует сообщение:

введите здесь описание изображения

person Juan Ospina    schedule 23.11.2013