Значение логической программы


Откуда известно, что логическая программа вычисляет то, что мы хотим? Корректна она или некорректна? Для ответа на подобные вопросы мы должны определить, что же является значением логической программы. Дав такое определение, можно будет проверять, совпадает ли значение программы с предположительным значением.

• Определение: Значениемлогической программы Р, обозначаемым М(Р), называется множество выводимых из Р основных единичных целей. •

Из этого определения следует, что значением логической программы, построенной просто из основных фактов, такой, как программа 1.1, является сама программа. Другими словами, для простых программ программа «значит ровно то, что написано». Рассмотрим программу 1.1, расширенную двумя правилами определения отношения родитель. Что будет ее значением? Оно содержит кроме фактов об отцах и матерях, явно указанных в программе, также все факты вида родитель (X, Y) Для каждой пары Х и Y, такой, что факт oтец(X,Y) или мать(Х,Y) присутствуют в программе. Этот пример показывает, что значение программы в явном виде содержит все то, что программа утверждает неявно.

Если предположить, что подразумеваемое значение программы также задано в виде множества основных единичных целей, то можно спросить, как соотносятся действительное и подразумеваемое значения программы. Мыможем проверить, все ли утверждения программы корректны или вычисляет ли программа все, что нам требуется.

Неформально мы называем программу корректной относительно некоторого заданного значения М, если значение М (Р) программы Р является подмножеством М. Иными словами, корректная программа не вычисляет того, что не требуется. Программа полна относительно М, если М есть подмножество М(Р), т.е. полная программа вычисляет все, что задано. Следовательно, программа Р корректна и полна относительно заданного значения М, если М = М(Р).

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

Например, если в программе для отношения сын содержится только первая аксиома, которая ссылается на отношение отец, то программа неполна относительно интуитивно понимаемого значения отношения сын, так как цель сын(исаак,сара) невыводима. Если к программе добавить правило

сын(Х, Y) ¬ мать(Х, Y), мужчина (Y).

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

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