Отрицание как недостижение цели и устойчивая семантика модели
Как было показано в главах 7 и 9, базы знаний в форме хорновских выражений имеют желаемые вычислительные свойства. Однако во многих приложениях довольно сложно выполнить выдвигаемое при этом требование, чтобы каждый литерал в теле выражения был положительным. Например, может потребоваться сформулировать утверждение: "На прогулку можно выходить, если нет дождя", не будучи вынужденным изобретать такие предикаты, как NotRaining. В этом разделе рассматривается дополнение к хорновским выражениям в форме явного отрицания, которое основано на идее использования отрицания как недостижения цели. Эта идея состоит в том, что истинность отрицательного литерала not Р может быть "доказана" просто на основании того, что попытка доказательства Р окончилась неудачей. В этом заключается одна из форм рассуждений по умолчанию, тесно связанная с предположением о замкнутом мире: предполагается, что нечто является ложным, если нельзя доказать, что оно истинно. Для того чтобы можно было отличить отрицание как недостижение цели от логического оператора "-i", для обозначения первого используется оператор "not".
В языке Prolog допускается применять оператор not в теле выражения. Например, рассмотрим следующую программу Prolog:
IDEdrive <— Drive л not SCSIdrive. SCSIdrive <— Drive л not IDEdrive. SCSIcontroller f-r SCSIdrive.
Drive. (10.4)
Первое правило указывает, что если в компьютере имеется жесткий диск, не являющийся диском SCSI, то это должен быть диск IDE. Согласно второму правилу, если это — не диск IDE, то он должен быть диском SCSI. В третьем правиле утверждается, что из наличия в компьютере диска SCSI следует наличие в нем контроллера SCSI, а четвертое утверждает, что в компьютере обязательно должен быть жесткий диск. Эта программа имеет следующие две минимальные модели:
Мх = {Drive, IDEdrive]
М2 = {Drive, SCSIdrive, SCSIcontroller)
Очевидно, что минимальные модели не позволяют выразить намеченную семантику программ с отрицанием как недостижением цели. Рассмотрим следующую программу:
Р <- not Q. (10.5)
Эта программа имеет две минимальные модели, {Р} и {Q]. С точки зрения логики первого порядка в этом есть смысл, поскольку выражение Р <= -.?> эквивалентно Р v Q. Но с точки зрения языка Prolog это сомнительно: если терм Q ни разу не появляется в этой программе слева от стрелки, то как же он может стать следствием?
Альтернативный подход состоит в использовании идеи стабильной модели, которая представляет собой такую минимальную модель, что каждый атом в модели имеет обоснование: правило, голова которого является атомом, а каждый литерал в теле выполняется. Формально модель м определяется как стабильная модель программы Я, если м— уникальная минимальная модель сокращения Я по отношению к м. Сокращение программы Я определяется путем предварительного удаления из Я любого правила, которое имеет в теле литерал not А, где А имеется в модели, а затем удаления всех отрицательных литералов в оставшихся правилах. Поскольку после этого сокращение программы я становится списком хорновских выражений, оно должно иметь уникальную минимальную модель.
Сокращением программы Р <— not Q по отношению к {Р} является Р, и это сокращение имеет минимальную модель {Р}. Поэтому {Р} — стабильная модель. Сокращение по отношению к {?>} представляет собой пустую программу, и это сокращение имеет минимальную модель {}. Поэтому {Q] — это нестабильная модель, поскольку Q не имеет обоснования в уравнении 10.5. В качестве еще одного примера можно привести сокращение уравнения 10.4 по отношению кмь как показано ниже.
IDEdrive <— Drive. SCSIcontroller <— SCSIdrive. Drive.
Эта программа имеет минимальную модель ми поэтому Мг — стабильная модель. Программирование множества ответов — это разновидность логического программирования с отрицанием как недостижением цели, которая функционирует на основе преобразования логической программы в базовую форму с последующим поиском стабильных моделей (называемых также множествами ответов) с использованием методов проверки пропозициональной модели. Таким образом, программирование множества ответов разработано на основе и системы Prolog, и быстродействующих алгоритмов автоматического доказательства выполнимости пропозициональных высказываний, таких как WalkSAT. И действительно, программирование множества ответов было успешно применено для решения задач планирования, по такому же принципу, как применялись программы автоматического доказательства выполнимости пропозициональных высказываний. Преимуществом планировщиков на основе множества ответов над другими планировщиками является их большая гибкость: операторы и ограничения планирования могут быть выражены в виде логических программ и не привязаны к жесткому формату конкретной формальной структуры планирования. Недостаток методов планирования на основе множества ответов является таким же, как и в других пропозициональных методах: если количество объектов в универсуме очень велико, то может возникать экспоненциальное замедление.