Вопрос

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

Одним из этапов преобразования в CNF является стандартизация переменных: переименовать все переменные, чтобы каждый квантификатор имел свое уникальное имя переменной.

Большинство общего универсала - наименее специализированное объединение двух пунктов.

Вопрос 1: Я искал пример, который показывает, каковы потенциальные проблемы, если я не стандартизирую переменные, но все онлайн -ресурсы, которые я нашел, только объясняют «как», а не «почему». Не могли бы вы дать мне пример потенциальной проблемы?

Вопрос 2: та же проблема, что и первый вопрос. Что если мы не используем MGU и используем более специализированный универсатор? Каковы потенциальные проблемы? Не могли бы вы дать мне пример?

Я искренне спасибо. Фелипе

Это было полезно?

Решение

  1. Видеть этот ответ - Это пример противоречивого набора пунктов, где мы не можем получить противоречие без переименования переменных. Обратите внимание, что не хватает только переименования переменных после преобразования в CNF, мы должны переименовать переменные, чтобы быть различными раньше каждый применение правила разрешения. Вы можете просмотреть это следующим образом: переменная, появляющаяся в двух различных пунктах, имеет различное значение в каждом из них, поскольку они неявно универсально определены. Если мы не переименованы в переменную в одном из пунктов, мы делаем ложное предположение, что переменная означает одинаковую в обоих пунктах.

  2. Используя MGU, мы получаем самый общий пункт на шаге разрешения. Если мы используем какой -либо универсальный, который является более специализированным, чем их MGU, результирующий пункт слабее. Это означает, что мы не определили все знания, которые могли, и мы можем пропустить вывод пустого предложения, даже если он существует. Например: begin {array} {c} p (x, y) lor q (y) lnot q (d) lnot p (c, d) end {array}, если мы сделаем Решаемый из первых двух положений с использованием MGU, который отправляет $ y to d $, мы получаем $ p (x, d) $, и мы можем продолжить третий пункт. Если мы возьмем более слабый универсатор, например, тот, который также отправляет $ x to d $, мы получаем $ p (d, d) $, и мы не можем принять решение с третьим пунктом. Это означает, что метод больше не завершен.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top