Простая база знаний
Теперь, после определения семантики пропозициональной логики, мы можем сформировать базу знаний для мира вампуса. Для упрощения будем рассматривать только ямы; случай, в котором рассматривается также сам вампус, оставляем читателю в качестве упражнения. Мы предоставим агенту достаточный объем знаний, чтобы он мог сам формировать те логические выводы, которые были описаны неформально в разделе 7.3.
Вначале необходимо определить словарь пропозициональных символов. Для каждого i, у.
• допустим, что высказывание Pif j является истинным, если в квадрате [i, j] имеется яма;
• допустим, что Bi j является истинным, если в квадрате чувствуется ветерок.
База знаний включает перечисленные ниже высказывания, каждому из которых для удобства присвоено отдельное обозначение.
• В квадрате [1,1] отсутствует яма:
Ri: ->Pi,i
• В квадрате чувствуется ветерок тогда и только тогда, когда в соседнем квадрате имеется яма. Такое высказывание должно быть сформулировано для каждого квадрата; на данный момент включены в рассмотрение только непосредственно интересующие нас квадраты:
Ri: ?1,1 <=> (Pi,2 v P2,i)
Дз: B2,i <=> (Pi,i v P2,2 v P3,i)
• Приведенные выше высказывания являются истинными во всех экземплярах мира вампуса. Теперь включим данные о восприятии ветерка для первых двух квадратов, которые были посещены агентом в том конкретном мире, где он находится; это приведет нас к ситуации, показанной на рис. 7.2, б.
R*: -iJBi.i R5: B2li
Таким образом, база знаний состоит из высказываний Rx—Rs- Ее можно также рассматривать как единственное высказывание (как конъюнкцию R± л R2 л R3 л Р4 л Rs), поскольку она подтверждает, что все отдельно взятые высказывания в ней являются истинными.
Логический вывод
В табл. 7.2 воспроизведен в более точной форме процесс формирования рассуждений, который проиллюстрирован на рис. 7.4. Общий алгоритм определения логи-
Напомним, что цель логического вывода состоит в том, чтобы определить, является ли истинным выражение KB \= а для некоторого высказывания а. Например, следует ли из базы знаний высказывание Р2,2? Рассматриваемый в данном разделе первый алгоритм логического вывода представляет собой непосредственную реализацию на практике определения логического следствия: перебрать (перечислить) все модели и проверить, является ли высказывание а истинным в каждой модели, в которой база знаний KB является истинной. Для пропозициональной логики модели представляют собой варианты присваивания значений true или false каждому пропозициональному символу. Возвратившись к примеру с миром вампуса, определим, что соответствующими пропозициональными символами являются Б1(1, В2(Ь Pi, 1, Р1/2, Р2,и р2,2 и P3,i- При наличии семи символов могут существовать 27=12 8 возможных моделей; в трех из них база знаний KB является истинной (табл. 7.2). В этих трех моделях является также истинным высказывание -iPi,2, поэтому в квадрате [1,2] нет ямы. С другой стороны, высказывание Р22 истинно в двух из трех моделей и ложно в одной из них, поэтому мы еще не можем определить, имеется ли яма в квадрате [2,2].
ческого следствия в пропозициональной логике приведен в листинге 7.3. Как и в алгоритме Backtracking-Search, приведенном на с. 131, функция TT-Entails? осуществляет рекурсивный перебор конечного пространства вариантов присваивания значений переменным. Этот алгоритм является непротиворечивым, поскольку он непосредственно реализует определение логического следствия, и полным, поскольку может применяться для любой базы знаний KB и любого высказывания а и всегда заканчивает свою работу, при условии, что количество моделей, подлежащих проверке, является конечным.
Листинг 7.3. Алгоритм перебора истинностной таблицы для получения пропозициональных логических следствий. ТТ обозначает истинностную таблицу, функция PL-True? возвращает истинное значение, если некоторое высказывание является истинным в рамках некоторой модели. Переменная model представляет частично заданную модель — присваивание только некоторым переменным. Вызов функции Extend(Р, true,model) возвращает новую частично заданную модель, в которой высказывание Р имеет значение true
function TT-Entails?(KB, a) returns значение true или false
inputs: KB, база знаний - высказывание в пропозициональной логике а, запрос - высказывание в пропозициональной логике
symbols <— список пропозициональных символов в KB и a return TT-Check-All(KB, a, symbols, [])
function TT-Check-All(KB, a, symbols, model) returns значение true или false if Empty?(symbols) then
if PL-True?(KB, model) then return PL-True?(a, model) else return true else do
P <— First (symbols) ; rest <— Rest (symbols)
return TT-Check-All(KB, a, rest, Extend(P, true, model) and TT-Check-All(KB, a, rest, Extend(P, false, model)
Безусловно, выражение "является конечным" не всегда означает то же, что и выражение "является небольшим". Если KB и а содержат в целом п символов, то количество моделей равно 2П. Таким образом, временная сложность этого алгоритма составляет 0(2П). (Пространственная сложность составляет только О(п), поскольку перебор вариантов присваивания происходит по принципу поиска в глубину.) Ниже будут показаны алгоритмы, которые являются гораздо более эффективными на практике. К сожалению, <Ж* каждый известный алгоритм логического вывода для пропозициональной логики в худшем случае имеет сложность, экспоненциально зависящую от размера ввода. Мы не можем рассчитывать на то, что наши алгоритмы будут действовать лучше, поскольку задача получения пропозиционального логического следствия является KO-NP-ПОЛНОЙ (см. приложение А).