Cтраница 2
Таким образом мы в процессе поиска вывода пустого дизъюнкта систематически перебираем возможные подстановки и унификации. [16]
Если некоторый R qt q m, - пустой дизъюнкт, то заканчиваем, найдя доказательство. В противном случае продолжаем. [17]
Если удалось унифицировать все литеры верхнего уровня, то выведен пустой дизъюнкт и доказательство завершено успешно. [18]
В отличие от этого, каждое множество дизъюнктов, содержащее пустой дизъюнкт, не может быть подтверждено никаким истинностным означиванием, так как П неподтверждаем. [19]
Входное ( единичное) опровержение-это входной ( единичный) вывод пустого дизъюнкта. [20]
Чтобы доказать выполнимость или невыполнимость предложения методом резолюций, достаточно вывести пустой дизъюнкт из соответствующего множества дизъюнктов. Если мы получим пустой дизъюнкт, противоречивость будет следствием предположения - чр, следовательно, мы докажем, что предложение ( р общезначимо. [21]
Затем с помощью этих дизъюнктов и дизъюнкта ( 3) получаем пустой дизъюнкт П - Таким образом, при поиске опровержения системы ( 1) - ( 3) с помощью тактики положительной гиперрезолюции перебор фактически вырождается в длинное вычисление. [22]
Если S - невыполнимое множество дизъюнктов, то из S резолютивно выводим пустой дизъюнкт. [23]
Линейным опровержением с резолюцией и парамодуляцией называется линейный вывод с резолюцией н парамодуляцией пустого дизъюнкта [ Попов и Фирдман, 1976, с. [24]
Основная идея метода резолюций состоит в том, чтобы проверить, содержит ли S пустой дизъюнкт П - Если S содержит Q, то S невыполнимо. Если S не содержит П, то проверяется следующий факт: может ли П быть получен из S. Будет ясно позднее, что по теореме Эрбрана ( вариант I) проверка получения Q эквивалентна подсчету числа узлов замкнутого семантического дерева для S. По теореме 4.3 S невыполнимо тогда и только тогда, когда существует конечное замкнутое семантическое дерево Т для S. Ясно, что S содержит П тогда и только тогда, когда Т состоит только из одного узла - корневого узла. [25]
Теорема 1.8. Множество дизъюнктов невыполнимо тогда и только тогда, когда существует линейный вывод пустого дизъюнкта. [26]
Множество дизъюнктов S невыполнимо тогда и только тогда, когда R ( S) содержит пустой дизъюнкт. [27]
Правило резолюции обладает свойством полноты в том смысле, что с помощью его всегда можно найти пустой дизъюнкт, если исходное множество дизъюнктов S противоречиво. [28]
Если мы имеем два единичных дизъюнкта, то их резольвента, если она существует, есть пустой дизъюнкт Q. Более существенно, что для невыполнимого множества дизъюнктов применениями правила резолюций можно породить П - Этот результат будет доказан в § 5.6 этой главы. [29]
На рис. 16.6 показан процесс применения резолюций, начинающийся с отрицания нашей предполагаемой теоремы и заканчивающийся пустым дизъюнктом. [30]