Каковы были недостатки процедуры резолюции Робинсона?

Question

paulson et alii. от LCF для isabelle / hol сказать:

Решение для логики первого порядка, в принципе, но часто разочаровывающее на практике.

Я думаю, что все означает, что они могут доказать любую верную формулу в логике первого порядка.В руководстве автоматического рассуждения я нахожу:

Разрешение

- это оперативно полная теорема, подтверждающая метод доказывания: противоречие (то есть пустое предложение) может быть выведено из любого неудовлетворенного набора положения.

из Википедии:

Попытка доказать доказательную формулу первого порядка в качестве неудовлетворенной может привести к нетерминирующим вычислениям

Почему это разочаровывает?

Answer 1

Хотя «разочаровывает на практике», безусловно, не определяется формально, в отличие от «полного» (который действительно означает «может в конечном итоге доказать каждую истинную формулу»), довольно легко найти примеры, где наивный даже не удаленно адекватно, то есть примеры, которые должны быть легко доказать, но какое разрешение чрезвычайно медленно включается.

Известный пример - кодирование Принцип отверстия голубя для $ n $ отверстия в пропозициональной логике (который является оператором " $ n + 1 $ Голуби не могут вписаться в $ n $ отверстия без дубликатов). Нет никаких доказательств этого оператора, используя только разрешение во времени в суб-экспоненте в $ n $ .

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

Обратите внимание, что любая реализация резолюции должна реализовать стратегию для выбора резольвентов, которая уже является очень сложной проблемой, и активная область исследования, поскольку большинство практических алгоритмов теоремы, доказательства Наивное разрешение, например, Гипер-разрешение .