Cтраница 2
В контексте метода резолюции цели являются отрицательными дизъюнктами, которые должны быть опровергнуты системой. [16]
Выводим литеру-ответ методом резолюции. [17]
Выводим литеру-ответ методом резолюции. Обратите внимание на применение унификации к термам, содержащим cons ( а, Ь), который обрабатывается просто как функциональный символ f ( a b); ср. [18]
Заметим, что метод резолюции аналогичен общему нисходящему методу, описанному в предыдущем разделе. Нетрудно видеть, что в линейном дереве опровержения множество всех шагов резолюции, в которых цель или подцель разрешается относительно правила, соответствует дереву поиска. В самом деле, при выполнении этих шагов цель или подцель расширяется. [19]
В заключение описан метод резолюции. [20]
Докажите при помощи метода резолюций, что множество дизъюнктов в этом примере невыполнимо. [21]
Мы видели, что метод резолюций решает эту проблему для конечного множества дизъюнктов или формул ( § 1.1.12 - 1.1.13) В данном параграфе этот результат обобщается на случай бесконечного множества. [22]
Представляет интерес свойство завершаемости метода резолюций: конечное множество S невыполнимо тогда и только тогда, когда пустой дизъюнкт может быть выведен из S с помощью резолюций. Из-леммы 1.3 следует достаточность этого условия. Пустой дизъюнкт, будучи невыполнимым, не может быть логическим следствием из выполнимого множества дизъюнктов. [23]
В контексте построения доказательств методом резолюций оказывается целесообразным формулировать высказывания как множества литералов. [24]
На доказательстве от противного основан метод резолюции. [25]
В предыдущей главе мы рассматривали метод резолюций как правило вывода, которое может быть использовано для порождения новых дизъюнктов из уже имеющихся. Мы видели также, что неограниченное применение резолюции может порождать много лишних и ненужных дизъюнктов наряду с полезными. Хотя можно использовать стратегию выбрасывания, чтобы выбросить некоторые из этих ненужных и бесполезных дизъюнктов после того, как они порождены, на их порождение уже будет потеряно время. Далее, если порождены бесполезные дизъюнкты, то нужны большие ресурсы машинного времени и памяти для того, чтобы определить, что эти дизъюнкты действительно лишние и ненужные. Поэтому для получения эффективных процедур доказательства теорем мы должны не допустить порождения большого числа бесполезных дизъюнктов. Это приводит к обсуждению стратегий резолюции. [26]
Если эрбранова область бесконечна, метод резолюций остается применимым, по крайней мере в принципе. В действительности известно, что если множество дизъюнктов невыполнимо, то оно допускает невыполнимое конечное подмножество. [27]
В частности, может быть использован метод резолюций, применяемый в системах автоматического доказательства, обучения и автоматического синтеза программ. Кроме того, логическая модель представления знаний поддерживается языком логического программирования Пролог, что делает естественной ее практическую реализацию. [28]
Отметим, что тот же самый метод резолюций способен строить запись и на основе информации о селекторном предикате. [29]
Следующие теоремы касаются корректности и полноты метода резолюций. [30]