Различные способы axiomatising а содержит функция для Z3 списков

Question

Axiomatising в содержит-операцию по спискам (on Rise4Fun), как

(declare-fun Seq.in ((List Int) Int) Bool) 

(assert (forall ((e Int)) 
    (not (Seq.in nil e)))) 

(assert (forall ((xs (List Int)) (e Int)) 
    (iff 
    (not (= xs nil)) 
    (= 
     (Seq.in xs e) 
     (or 
     (= e (head xs)) 
     (Seq.in (tail xs) e)))))) 

позволяет Z3 4,0 опровергнуть утверждение

(declare-const x Int) 
(assert (Seq.in nil x)) 
(check-sat) ; UNSAT, as expected 

в моих глазах эквивалент аксиоматизация

(assert (forall ((xs (List Int)) (e Int)) 
    (ite (= xs nil) 
    (= (Seq.in xs e) false) 
    (= 
     (Seq.in xs e) 
     (or 
     (= e (head xs)) 
     (Seq.in (tail xs) e)))))) 

приводит unknown.

Это может быть проблема с триггерами или есть что-то конкретное для домена List, которое могло бы объяснить разницу в поведении?

Answer 1

Ваш сценарий при подъеме4fun отключает двигатель :mbqi. Таким образом, Z3 попытается решить проблемы, используя только E-сопоставление. Когда шаблоны (ака триггеры) не предусмотрены, Z3 выведет триггеры для нас. Z3 использует множество эвристик для вывода паттернов/триггеров. Один из них имеет отношение к вашему сценарию и объясняет, что происходит. Z3 никогда не будет выбирать шаблон/триггер, который создает «соответствующий цикл». Мы говорим, что шаблон/триггер P производит цикл согласования для квантора Q, когда экземпляр Q будет производить новое согласование для Р. Рассмотрим квантор

(assert (forall ((xs (List Int)) (e Int)) 
    (ite (= xs nil) 
    (= (Seq.in xs e) false) 
    (= 
     (Seq.in xs e) 
     (or 
     (= e (head xs)) 
     (Seq.in (tail xs) e)))))) 

Z3 будет не выбрать (Seq.in xs e) в качестве шаблона/trigger для этого квантификатора, потому что он создаст соответствующий цикл. Предположим, что у нас есть основной термин (Seq.in a b). Этот термин соответствует шаблону (Seq.in xs e). Игнорирование квантификатора с помощью a будет b произведет термин (Seq.in (tail a) b), который также соответствует рисунку (Seq.in xs e). Игнорирование квантора с помощью (tail a) и b приведет к выражению (Seq.in (tail (tail a)) b), который также соответствует рисунку (Seq.in xs e) и т. Д.

Во время поиска Z3 блокирует совпадающие контуры с использованием нескольких пороговых значений. Однако производительность обычно затрагивается. Таким образом, по умолчанию Z3 не будет выбирать (Seq.in xs e) в качестве шаблона. Вместо этого он выберет (Seq.in (tail xs) e). Этот шаблон не создает соответствующий цикл, но также предотвращает недопущение Z3 от второго и третьего запросов. Любые ограничения двигателя E-matching обычно обрабатываются двигателем :mbqi. Однако в вашем скрипте отключен :mbqi.

Если вы предоставили шаблоны для второго и третьего запросов в вашем скрипте. Z3 докажет, что все примеры будут unsat. Вот ваш пример с явными узорами/триггеров:

http://rise4fun.com/Z3/DkZd

Первый пример проходит даже без использования шаблонов, потому что только первый квантор необходимо, чтобы доказать пример быть unsat.

(assert (forall ((e Int)) 
    (not (Seq.in nil e)))) 

Обратите внимание, что (Seq.in nil e) идеальный образец для этого квантора, и это один выбранный Z3.