Почему объединение так важно для механизмов вывода?

17

Я сам изучаю Автоматизированное доказательство теорем / SMT-решатели / Помощники по проверке и выкладываю серию вопросов о процессе, начиная здесь .

Я продолжаю читать об Алгоритме Объединения .

  • Что это такое и почему это так важно для двигателей вывода ?
  • Почему это так важно для информатики?
Гай Кодер
источник

Ответы:

11

Унификация является настолько фундаментальным понятием в информатике, что, возможно, мы даже воспринимаем это как должное. Каждый раз, когда у нас есть правило, уравнение или шаблон, и мы хотим применить его к некоторым данным, унификация используется, чтобы специализировать правило на данных. Или, если мы хотим объединить два общих, но частично совпадающих правила, объединение предоставляет нам наиболее общее объединенное правило. Объединение лежит в основе

  • Теорема доказатели и помощники доказательства, в том числе некоторые из них на основе объединения более высокого порядка.
  • Реализация Пролога (как Резолюция).
  • Алгоритмы вывода типов.
  • Компьютерная лингвистика / обработка естественного языка.
  • Термин переписывания систем, таких как Мод, который может быть использован в качестве основы семантики языка программирования.
  • Дедуктивные базы данных.
  • Экспертные системы или, в более общем смысле, искусственный интеллект.
  • Системы компьютерной алгебры.
  • Сопоставление с образцом в функциональных языках (по крайней мере, частично ... только сопоставление).
  • Некоторые подходы разбора.
  • Некоторые языки запросов, особенно с использованием семантической паутины.
Дэйв Кларк
источник
8

Корректоры, такие как Изабель / HOL, работают на синтаксическом уровне в логическом исчислении. Представьте, что у вас есть правило modus ponens (MP)

PQ,P  Q

и доказательство цели

(aб)(сd),aб !сd

Мы, люди, сразу же видим, что это следует за modus ponens, но машина должна соответствовать цели, чтобы управлять синтаксически (независимо от того, делаете ли вы apply rule mpили apply simp), и это то, что делает объединение. Алгоритм находит с и , создает экземпляр правила и применяет его.φ ( P ) = a b φ ( Q ) = c dφφ(п)знак равноaбφ(Q)знак равносd

Хорошая вещь о методах помощников, как simpсейчас, заключается в том, что если ваша цель

(aб)(сd),a !d

что они найдут подходящую последовательность применений правил MP, и с совместимыми унификациями для соответствующих шагов и решат поставленную задачу.пQпппQ


Обозначение: С набор логических формул, обозначенияΓзнак равно{φ1,...,φN}

Γψ

означает следующее:

Если я вывел / доказал все формулы в (то есть они действительны ), то это правило утверждает, что также допустимо.Γψ

В некотором смысле правило является последним шагом в (длинном) доказательстве . Доказательства - это не что иное, как цепочки таких приложений правил.Γψψ

Обратите внимание, что правила обычно содержат схематические переменные ( и выше), которые могут быть заменены произвольными формулами, если одна и та же переменная заменяется на одну и ту же формулу во всех случаях; Результатом этого формата является конкретный экземпляр правила (или интуитивно понятный шаг проверки). Эта замена выше обозначена которая была найдена объединением.пQφ

Часто люди используют вместо .

Рафаэль
источник
3
часто используется для семантики, тогда как это синтаксическая манипуляция, для которой обычно используется . Это может зависеть от сообщества, хотя.
Дэйв Кларк
2

Я не думаю, что это важно для вывода двигателей . Однако алгоритм объединения очень полезен для вывода типов . Это два очень разных вида вывода.

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

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

jmad
источник
Я не думаю, что первое предложение действительно; смотри мой ответ.
Рафаэль
1
Я также не согласен с первым предложением. Решение (специализация унификации) является ядром Пролога, который является одним из наиболее распространенных языков реализации для экспертных систем и других механизмов вывода.
Дэйв Кларк
@ Рафаэль и Дейв: вы говорите, что алгоритм объединения непосредственно используется в механизмах логического вывода?
Джмад
@jmad: Я не уверен , что есть алгоритм объединения, и я также не уверен , какие системы называются «логический вывод». Я знаю, что унификация широко используется везде, где появляется логика и / или формальная семантика; см. ответ Дэйва для списка.
Рафаэль
@ Рафаэль: это в значительной степени проблема, которую я хотел решить: кажется, что механизмы вывода - это не вывод, который я знаю о типе и логике.
Джмад