Корректоры, такие как Изабель / HOL, работают на синтаксическом уровне в логическом исчислении. Представьте, что у вас есть правило modus ponens (MP)
P→Q,P ⟹ Q
и доказательство цели
(a∨b)→(c∧d) , ∨ б ⟹ !c ∧ d
Мы, люди, сразу же видим, что это следует за modus ponens, но машина должна соответствовать цели, чтобы управлять синтаксически (независимо от того, делаете ли вы apply rule mp
или apply simp
), и это то, что делает объединение. Алгоритм находит с и , создает экземпляр правила и применяет его.φ ( P ) = a ∨ b φ ( Q ) = c ∧ dφφ ( P) = a ∨ bφ ( Q ) = c ∧ d
Хорошая вещь о методах помощников, как simp
сейчас, заключается в том, что если ваша цель
( a ∨ b ) → ( c ∧ d) , ⟹ !d
что они найдут подходящую последовательность применений правил MP, и с совместимыми унификациями для соответствующих шагов и решат поставленную задачу.п∧ Q ⟹ Pп⟹ P∨ Q
Обозначение: С набор логических формул, обозначенияΓ = { φ1, … , ΦN}
Γ ⟹ ψ
означает следующее:
Если я вывел / доказал все формулы в (то есть они действительны ), то это правило утверждает, что также допустимо.Γψ
В некотором смысле правило является последним шагом в (длинном) доказательстве . Доказательства - это не что иное, как цепочки таких приложений правил.Γ ⟹ ψψ
Обратите внимание, что правила обычно содержат схематические переменные ( и выше), которые могут быть заменены произвольными формулами, если одна и та же переменная заменяется на одну и ту же формулу во всех случаях; Результатом этого формата является конкретный экземпляр правила (или интуитивно понятный шаг проверки). Эта замена выше обозначена которая была найдена объединением.пQφ
Часто люди используют вместо .⊨⟹
Я не думаю, что это важно для вывода двигателей . Однако алгоритм объединения очень полезен для вывода типов . Это два очень разных вида вывода.
Вывод типа важен для информатики, потому что типы важны в теории языков программирования, которая является важной частью информатики. Типы также близки к логике и интенсивно используются в автоматическом доказательстве теорем. Существуют реализации алгоритмов унификации во многих, если не во всех, помощниках по проверке и специалистах по SMT.
Механизмы вывода связаны с искусственным интеллектом, который также важен, но очень отличается. (Я видел связи между обучением и логикой, но это кажется надуманным.)
источник