Все шпаргалки / Математическая логика / 

Исчисление предикатов. Расширение принципа резолюции (линейность и упорядоченность литер в дизъюнкте).

см. вопрос 18, 10Линейная резолюция может быть существенно усилена в исчислении предикатов введением понятия упорядоченного дизъюнкта и использование информации о резольвированных литерах. Идея метода заключается в рассмотрении дизъюнкта как последовательности литер, а не множества их. Отсюда упорядоченным дизъюнктом будем называть дизъюнкт с определённой последовательностью литер. При наличии в упорядоченном дизъюнкте двух одинаковых литер следует удалить старшую литеру, сохранив самую младшую.Другим усилением линейной резолюции является использование информации о резольвироваемых литерах. Обычно при выполнении процедуры резольвирования происходит удаление резольвируемых литер. Однако, оказывается, что –эти литеры несут полезную информацию, которая может быть использована для усиления линейной резолюции. Вместо удаления резольвируемых литер предлагается обрамлять их квадратом. Если за обрамлённой литерой в упорядоченном дизъюнкте не следует никакая другая литера, то её можно удалить. И наоборот, если за обрамлённой литерой в упорядоченном дизъюнкте следует никакая-либо литера, то её следует оставить для последующего использования. Используя резольвенты центрального стержня на предыдущих этапах резольвирования для сравнения с необрамлённой литерой в качестве боковых ветвей, можно получить все литеры упорядоченного дизъюнкта обрамлёнными квадратами. В этом случае можно удалить весь дизъюнкт.