Унификация против SAT решатель

Я читал в Википедии, что объединение - это процесс решения проблемы выполнимости.

В то же время я знаю, что такие решатели называются «решателями SAT» или «решателями SMT». Так это разные имена для одного и того же?

Если вы говорите, что они разные, пожалуйста, укажите на недостатки в моем лечении.

terminology sat-solvers unification Val
источник

информатика часто ссылается на «проблему выполнимости», но на самом деле это частный случай общей проблемы [упоминаемой в статье в Википедии об объединении], которая может иметь более сложные предложения, такие как «существует» и «для всех», кроме просто булевы переменные. в CS ссылка на «проблему выполнимости» может быть действительно сокращением для пропозициональной или логической проблемы выполнимости , сокращенно SAT. Процесс объединения в SAT называется резолюцией

vzn

Решатели SAT решают проблему булевой удовлетворенности . Это «проблема определения, могут ли переменные данной булевой формулы быть назначены таким образом, чтобы формула оценивалась как ИСТИНА».

Например, найти присвоение значений истинности переменным таким образом, чтобы является истинным. Решатель SAT может вернуть решение, такое как , , . $a,b,c$ $(a \lor b \lor c)\land (\lnot a \lor \lnot b \lor c)\land (a \lor \lnot b \lor \lnot c)\land (\lnot a \lor b \lor \lnot c)$ $a=true$ $b=true$ $c=true$

Решатели SMT решают более общую проблему, а именно: теории удовлетворенности по модулю . Это «проблема решения логических формул относительно комбинаций фоновых теорий, выраженных в классической логике первого порядка с равенством». Эти теории могут включать «теорию действительных чисел, теорию целых чисел и теории различных структур данных, таких как списки, массивы, битовые векторы и так далее».

Пример, данные , введенные переменные и и , спрашивает , является ли следующее выполнима , Решатель SMT ответил бы да, с решением , , и . $x:int$ $y:int$ $f:int\to int$ $f(x+2) \neq f(y-1) \land x=(y- 4)$ $x=-2$ $y=2$ $f(0)=1$ $f(1)=3$

Унификация - это особый метод, который принимает два термина и находит замену, которая делает условия равными. Например, при заданных терминах и объединение приведет к замене . Объединение, вероятно, используется внутри решателей SMT. $book(x,\text{"Fishing"},2010)$ $book(\text{D.~Smith},y,2010)$ $\{x\mapsto\text{D. Smith},y\mapsto\text{"Fishing"}\}$

Дэйв Кларк
источник

Все слова знакомы в предложении «Объединение, вероятно, используется где-то в SMT-решателях (и, возможно, в SAT-решателях)», но я этого не понимаю. Вы также находите такое определение SMT, что трудно понять, является ли SAT частным случаем этого.

Val

SAT имеет дело с логикой высказываний. Логика первого порядка, на которой основан SMT, является более общей.

Дэйв Кларк

Унификация против SAT решатель

Ответы: