Вопрос по – Ликвидация квантификатора - Дополнительные вопросы

5

Большое спасибо Джошу и Леонардо за ответ на предыдущий вопрос.

У меня есть еще несколько вопросов.

& Lt; 1 & GT; Рассмотрим другой пример.

<code>(exists k) i * k > = 4 and k > 1.
</code>

Это простое решение, я & gt; 0. (как для Int, так и для Real)

Тем не менее, когда я попытался следовать,

<code>(declare-const i Int)
(assert (exists ((k Int)) (and (>= (* i k)  4) (> k 1))))
(apply (using-params qe :qe-nonlinear true))
</code>

Z3 Не удалось устранить квантификатор здесь.

Тем не менее, это может устранить для реального случая. (когда я и к оба действительные) Является ли Quantifier Elvention более сложным для целых чисел?

& Л; 2 & GT; Я использую Z3 C API в моей системе. Я добавляю некоторые нелинейные ограничения на целые числа с квантификаторами в моей системе. Z3 в настоящее время проверяет на удовлетворенность и дает мне правильную модель, когда система является удовлетворительной.

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

Я думал, что z3 делает устранение квантификатора автоматически перед проверкой выполнимости. Но так как он не мог этого сделать в случае 1, описанном выше, я теперь думаю, что он обычно находит модель без исключения квантификатора. Я прав?

В настоящее время z3 может решить ограничения в моей системе. Но это может дать сбой в сложных системах. В таком случае, будет ли хорошей идеей сделать устранение кванторов другим методом без z3 и добавить ограничения к z3 позже?

& Л; 3 & GT; Я могу подумать о добавлении действительных нелинейных ограничений вместо целочисленных нелинейных ограничений в моей системе. В таком случае, как я могу заставить z3 выполнять удаление квантификаторов с помощью C-API?

& Lt; 4 & GT; И наконец, является ли это хорошей идеей, чтобы заставить z3 выполнять удаление квантификаторов? Или он обычно находит модель более разумно, не выполняя Quantifier Elmination?

Благодарю.

Ваш Ответ

1   ответ
6

& Lt; 1 & GT; Теория нелинейной целочисленной арифметики не допускает исключения кванторов (qe). задача решения для нелинейной целочисленной арифметики неразрешима.

Напомним, что Z3 имеет ограниченную поддержку для устранения кванторов нелинейных вещественных арифметических формул. Текущая процедура основана на замене виртуального термина. Будущие версии могут иметь полную поддержку нелинейной реальной арифметики.

& Л; 2 & GT; Исключение квантификатораnot включен по умолчанию. Пользователь должен запросить это. Z3 может найти модели для удовлетворительных формул, даже если исключение квантификатора не включено. Он использует метод, называемый основанной на модели квантификатором (MBQI).Z3 онлайн-учебник  Есть несколько примеров, описывающих возможности и ограничения этой техники.

& Л; 3 & GT; Вы должны включить его при создании объекта Z3_context. Любая опция, заданная в командной строке, может быть предоставлена при создании объекта Z3_context. Вот пример, который позволяет построить модель и исключить квантификатор:

Z3_config cfg = Z3_mk_config();
Z3_context ctx;
Z3_set_param_value(cfg, "MODEL", "true");
Z3_set_param_value(cfg, "ELIM_QUANTIFIERS", "true");
Z3_set_param_value(cfg, "ELIM_NLARITH_QUANTIFIERS", "true");
ctx = mk_context_custom(cfg, throw_z3_error);
Z3_del_config(cfg);

После этого,ctx указывает на объект контекста Z3, который поддерживает построение модели и устранение квантификатора.

& Lt; 4 & GT; Модуль MBQI не является полным даже для линейного арифметического фрагмента. Онлайновое руководство по Z3 описывает фрагменты, которые оно завершает. Модуль MBQI является хорошим вариантом для задач, которые содержат неинтерпретированные функции. Если в ваших задачах используется только арифметика, то устранение квантификаторов обычно лучше и эффективнее. При этом несколько проблем могут быть быстро решены с помощью MBQI.

Я думаю, что в первой строке вы имеете в виду «нелинейную целочисленную арифметику»doesn't принять исключение квантификатора & quot ;.
Да ты прав. Спасибо, что поймали это. Я починю это.
Большое спасибо Леонардо. Только один вопрос - можете ли вы объяснить, почему теория нелинейной целочисленной арифметики не допускает исключения кванторов (qe)? Kaustubh Nimkar
Это еще хуже. Удовлетворенность в теории нелинейной (читай полиномиальной) целочисленной арифметики неразрешима; то есть доказано (с помощью ряда результатов Дэвиса, Патнэма, Робинсона и Матиясевича), что ни один алгоритм не может сказать, учитывая многомерный полином, имеет ли он целые нули. Таким образом, даже не нужно чередование кванторов; один блок экзистенциальных квантификаторов делает его неразрешимым.
Это является следствием первой теоремы G & delta; del & delta; Если вы будете искать «первую теорему о неполноте» G & delta; del, вы найдете несколько хороших (неформальных и формальных) представлений этого результата.

Похожие вопросы