Часть 5.

2.2.3. Значение семантики на примере "мира блоков"

В заключение этого раздела рассмотрим вопросы присвоения значений истинности некоторым выражениям исчисления предикатов на примере из "мира блоков". Предположим, мы хотим промоделировать мир блоков, изображенный на рис. 2.3, и сконструировать алгоритм управления для руки робота. Для представления качественных отношений в этом мире можно использовать предложения исчисления предикатов. С помощью этих предложений нужно описать, свободна ли верхняя грань данного блока, можно ли взять блок а, и т.д. Предположим, что компьютер обладает знаниями о расположении каждого блока и руки, а также способен отслеживать перемещение блоков на столе (используя трехмерную систему координат).

В этом примере из "мира блоков" нужно очень точно определить свои действия. Сначала необходимо создать набор выражений исчисления предикатов, который должен фиксировать текущее состояние мира блоков в рассматриваемой предметной области. В разделе 2.3 будет представлена интерпретация и возможная модель мира блоков, описанная набором выражений исчисления предикатов.

Исчисление предикатов декларативно, т.е. не существует никакой принятой синхронизации или порядка рассмотрения каждого выражения. Тем не менее в разделе 7.4 мы дополнительно рассмотрим процедурную семантику (procedural semantics) или ясно определенную методологию для оценки этих выражений во времени. Конкретный пример процедурной семантики для выражений исчисления предикатов - это язык PROLOG (глава 14). Создаваемое нами ситуационное исчисление связано с рядом вопросов, включающих проблему фреймов и немонотонности логических интерпретаций. Эти вопросы будут представлены на рассмотрение позже. Для этого примера достаточно сказать, что выражения исчисления предикатов будут оцениваться слева направо.

87

оп{с,а)

on(b,d)

ontable{a)

ontable(d)

clear(b)

clear(c)

handempty

Рис. 2.З. Мир блоков и его описание в исчислении предикатов

Здесь оп(с,а) означает, что блок с находится на блоке a; ontable(a) - блок а лежит на столе; clear(c) - на блоке с нет других блоков; handempty - рука пуста.

Чтобы можно было поднять один блок и поставить его на другой, оба блока должны быть свободными (открытыми для руки). На рис. 2.3 блок а не свободен. Поскольку рука может перемещать блоки, она может изменять состояние мира и освобождать их. Предположим, она снимает блок с с блока а и обновляет базу знаний, удалив из нее утверждение оп(с,а). Программа при этом должна сделать логический вывод, что блок а теперь свободен.

Следующее правило описывает действие "блок стал свободным".

VX(-,3 Y оn (Y, Х)->clear(Х))

Следовательно, для любого X X свободен, если не существует Y такого, что Y находится на X.

Это правило определяет не только значение "блок свободен", но и действие "освободить блоки". Например, блок d не свободен, потому что, если переменная X принимает значение d, a Y- Ь, то предложение является ложным. Чтобы сделать это определение истинным, блок to следует удалить с блока d. Это легко сделать, потому что в компьютере записано местоположение всех блоков.

Помимо использования вышеописанного правила для определения условия освобождения блока, можно добавить другие правила, описывающие операции укладки одного блока на другой. Например: чтобы положить X на Y, сначала нужно освободить руку, затем освободить X, Y и уж потом взять X (pick_up(X)) и поставить (put_down) его на Y.

VX\/Y((hand_empty^clear(X)^Clear(Y)^pick_up(X)^put_down(X,Y))-> stack(X,Y))

Заметим, что в вышеупомянутом описании необходимо связать с каждым предикатом действие руки робота, например pick_up(X) (взять X). Как отмечалось ранее, для этого необходимо дополнить семантику исчисления предикатов требованием, чтобы действия выполнялись в том порядке, в котором они предписываются правилами. Однако эту проблему лучше рассмотреть отдельно.

88

На рис. 2.3 представлена семантическая интерпретация этих выражений исчисления предикатов. Она отображает константы и предикаты в набор выражений из области определения D (в данном случае это блоки и отношения между ними). Интерпретация сопоставляет значение истинности Т с каждым выражением в описании. Для других наборов блоков, находящихся в другом расположении, или же, например, для группы из четырех акробатов, могла бы быть предложена другая интерпретация. Вопрос заключается не в уникальности интерпретаций. Главное, интерпретация должна обеспечивать значение истинности для всех выражений в наборе, а сами выражения должны достаточно детально описывать мир, предоставляя все необходимые выводы. В следующем разделе эти идеи используются для формальной основы правил вывода исчисления предикатов.

2.3. Правила вывода в исчислении предикатов

2.3.1. Правила вывода

Семантика исчисления предикатов обеспечивает основу для формализации теории логического вывода (logical inference). Возможность логически выводить новые правильные выражения из набора истинных утверждений - это важное свойство исчисления предикатов. Логически выведенные выражения корректны, потому что они совместимы со всеми предыдущими интерпретациями первоначального набора выражений. Вначале обсудим вышесказанное неформально, а затем введем ряд определений для формализации этих утверждений.

Говорят, что интерпретация, которая делает предложение истинным, удовлетворяет этому предложению. Если интерпретация удовлетворяет каждому элементу набора выражений, то говорят, что она удовлетворяет набору. Выражение X логически следует из набора выражений S исчисления предикатов, если каждая интерпретация, которая удовлетворяет S, удовлетворяет и X. Это утверждение дает основание для проверки правильности правил вывода: функция логического вывода должна производить новые предложения, которые логически следуют из данного набора предложений исчисления предикатов.

Важно верно понимать значение слов логически следует: логическое следование выражения X из S означает, что оно должно быть истинным для каждой интерпретации, которая удовлетворяет первоначальному набору выражений S. Это означает, например, что любое новое выражение исчисления предикатов, добавленное к миру блоков на рис. 2.3, должно быть истинным в этом мире. Оно должно быть истинным и при любой другой интерпретации, которую мог бы иметь этот набор выражений.

Термин логически следует вовсе не означает, что X выведено из S, или что его можно вывести из S. Это просто означает, что X истинно для каждой интерпретации (потенциально до бесконечности), которая удовлетворяет S. Однако системы предикатов могут иметь бесконечное число возможных интерпретаций, поэтому практическая необходимость проверять все интерпретации возникает весьма редко. В вычислительном отношении правила вывода (inference rule) позволяют определять, когда выражение как компонент интерпретации логически следует из этой интерпретации.

Понятие логически следует обеспечивает формальное основание для доказательства разумности и правильности правил вывода.

89

Правило вывода обеспечивает создание новых предложений исчисления предикатов на основе данных предложений. Следовательно, правила вывода производят новые предложения, основанные на синтаксической форме данных логических утверждений. Если каждое предложение X, полученное с помощью некоторого правила вывода на множестве S логических выражений, также логически следует из S, то говорят, что это правило вывода обосновано (sound).

Если система правил вывода способна произвести каждое выражение, которое может логически следовать из S, то говорят, что эта система правил вывода является полной. Приведенное ниже правило modus ponens и принцип резолюции (resolution), представленный в главе 12, являются примерами обоснованных правил вывода, которые при использовании соответствующих стратегий полны. Логические системы вывода обычно используют обоснованные правила вывода, однако далее (в главах 5, 9, 10 и 14) мы рассмотрим эвристические рассуждения и рассуждения на основе здравого смысла, которые опускают это требование.

Формализуем эти мысли с помощью следующих определений.

ОПРЕДЕЛЕНИЕ

УДОВЛЕТВОРЯТЬ, МОДЕЛЬ, АДЕКВАТНОСТЬ

Для выражения X исчисления предикатов и интерпретации / имеют место следующие определения.

Если X имеет значение 7 на / при конкретных значениях переменных, то говорят, что / удовлетворяет X.

Если / удовлетворяет X при всех значениях переменных, то / является моделью X. X выполнимо (satisfiable) тогда и только тогда, когда существуют такая интерпретация и значение переменной, которые ему удовлетворяют; в противном случае X невыполнимо (unsatisfiable).

Набор выражений выполним тогда и только тогда, когда существуют интерпретация и значения переменных, которые удовлетворяют каждому элементу. Если набор выражений невыполним, то говорят, что он противоречив (inconsistent). Если X имеет значение Т для всех возможных интерпретаций, то говорят, что X имеет силу, или адекватно (valid).

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

Выражение ЭХ (р(Х) л -.р(Х)) противоречиво, потому что оно не может быть удовлетворено ни при какой интерпретации или значениях переменных. С другой стороны, выражение VX (p(X) v -ip(X)) адекватно.

Для проверки адекватности выражений, не содержащих переменных, можно использовать метод таблиц истинности. Поскольку не всегда можно определить, адекватно ли выражение, содержащее переменные (как говорилось выше, процесс может не закончиться), говорят, что полное исчисление предикатов "неразрешимо". Однако существуют методы доказательства, которые позволяют генерировать любое выражение, логически следующее из данного набора выражений. Они называются процедурами полного доказательства (complete proof procedures).

90

ОПРЕДЕЛЕНИЕ

ПРОЦЕДУРА ДОКАЗАТЕЛЬСТВА

Процедура доказательства (proof procedure) - это комбинация правил вывода и алгоритма применения этих правил к набору логических выражений для создания новых предложений.

В главе 11 представлены процедуры доказательства для правил резолюции (resolution inference rule).

Используя эти определения, можно формально определить термин "логически следует".

ОПРЕДЕЛЕНИЕ

ЛОГИЧЕСКИ СЛЕДУЕТ, ОБОСНОВАННЫЙ И ПОЛНЫЙ

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

Правило вывода обосновано (sound), если каждое выражение исчисления предикатов, полученное в соответствии с правилом из множества S выражений исчисления предикатов, также логически следует из S.

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

Правило modus ponens (правило отделения, или модус поненс) - это обоснованное правило вывода. Если дано выражение вида P->Q и другое выражение вида Р, и оба выражения истинны на интерпретации /, то modus ponens позволяет нам сделать вывод, что О тоже истинно на этой интерпретации. Действительно, поскольку modus ponens является обоснованным правилом, О истинно для всех интерпретаций, для которых Р и P-ҐQ являются истинными.

Определения правила modus ponens и ряда других полезных правил вывода даны ниже.

ОПРЕДЕЛЕНИЕ

МОДУС ПОНЕНС, МОДУС ТОЛЛЕНС, ИСКЛЮЧЕНИЕ "И", ВВЕДЕНИЕ "И", УНИВЕРСАЛЬНОЕ ИНСТАНЦИРОВАНИЕ

Если известно, что предложения Р и Р->0 истинны, то модус поненс позволяет вывести О.

Согласно правилу вывода модус толленс (modus tollens), если известно, что P-*Q является истинным и О ложно, можно вывести -Р.

Исключение "И" - правило, позволяющее вывести истинность обоих конъюнктов на основе истинности конъюнктивного предложения. Например, если РаО истинно, можно сделать вывод, что Р и О истинны.

Введение "И" позволяет вывести истинность конъюнкции из истинности ее конъюнктов. Например, если Р и О истинны, то конъюнкция PaQ истинна. Универсальное инстанцирование сводится к следующему: если любую переменную, стоящую под квантором всеобщности в истинном предложении, заменить любым соответствующим термом из области определения, то результирующее выражение - истинно. Таким образом, если а принадлежит той же области определения, что и X и VXр(X), то можно вывести р{а).

91

В качестве простого примера применения правила модус поненс в исчислении высказываний рассмотрим следующие предложения: "если идет дождь, то земля будет влажной" и "идет дождь". Если Р обозначает "идет дождь" и О есть "земля, влажная", то первое выражение можно записать в виде P-+Q. Поскольку действительно сейчас идет дождь (Р истинно), получаем систему аксиом.

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

Правило модус поненс также может быть применено к выражениям, содержащим переменные. Рассмотрите в качестве примера обычный силлогизм "все люди смертны, и Сократ - человек, поэтому Сократ - смертен". Высказывание "Все люди смертны" может быть представлено в исчислении предикатов (по-русски и по-английски) так.

VX (человек(Х)->смертный(Х)). \/Х (man(X)->mortal(X)).

"Сократ - человек"

человек(сократ). man(socrates).

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

человек(сократ)->смертный (сократ). man(socrates)^>mortal(socrates).

Применив правило модус поненс, приходим к выводу mortal(socrates). Он может быть добавлено к набору выражений, которые логически следуют из первоначальных утверждений. Можно использовать так называемый алгоритм унификации для определения автоматическим решающим устройством правомочности замены X на socrates и возможности применения правила модус поненс. Унификация обсуждается в подразделе 2.3.2.

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

2.3.2. Унификация

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

92

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

Унификация - это алгоритм определения необходимых подстановок с целью приведения в соответствие двух выражений исчисления предикатов. Пример такого процесса приведен в предыдущем подразделе, где терм socrates из выражения man(socrates) был использован в качестве подстановки для X в выражении VX(man(X)=>mortal(X)). Эта подстановка позволила применить правило модус поненс и получить вывод mortal(socrates). Еще один пример унификации был рассмотрен выше, когда обсуждались фиктивные переменные (dummy). Поскольку р(Х) и р( Y) эквивалентны, для приведения предложений в соответствие (match) друг другу Y можно заменить на X.

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

Весьма важный аспект этой формы заключается в требовании, чтобы все переменные стояли под знаком квантора всеобщности. Это обеспечивает полную свободу в выполнении подстановок. Переменные, стоящие под квантором существования, можно устранить из предложений в базе данных, заменив их константами, обеспечивающими истинность предложения. Например, ЗХ parent(X,tom) может быть заменено выражением parent(bob,tom) или parent(mary, torn), принимая во внимание, что Боб (bob) и Мэри (тагу) являются родителями Тома (torn) в этой интерпретации.

Процесс удаления переменных, связанных квантором существования, усложнен тем фактом, что значение этих подстановок может зависеть от значения других переменных в выражении. Например, в высказывании VX ЗУ mother(X,Y) значение переменной Y под квантором существования зависит от значения X. Сколемизация (skolemization) - это замена каждой переменной, связанной квантором существования, функцией нескольких или всех имеющихся в предложении переменных, которая возвращает соответствующую константу. В вышеупомянутом примере, поскольку значение Y зависит от X, Y можно заменить сколемовской функцией (skolem function) f от X. Это порождает предикат VX mother(X,f(X)). Сколемизация- это процесс, который также позволяет связывать переменные, стоящие под квантором всеобщности, с константами. Этот аспект подробно обсуждается в главе 12.

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

Процесс унификации осложняется тем фактом, что переменная может быть заменена любым термом, включая другие переменные и функциональные выражения произвольной сложности. Эти выражения могут тоже содержать переменные. Например, father(jack) можно использовать в качестве подстановки для X в выражении тап(Х) для получения вывода, что отец Джека смертен.

Приведем несколько реализаций выражения

foo(X,a,goo(Y)). Их можно получить путем следующих подстановок.

foo(fred,a,goo(Z))

foo{W,a, goo(jack))

foo(Z,a,goo(moo(Z)))

93

В этом примере экземпляры подстановки, или унификации, которые делают начальное выражение идентичным каждому из трех, можно записать в виде

{fred/X,Z/Y} {W/XJack/Y] {Z/X,moo(Z)/Y}

Запись X/Y, ... означает, что X является подстановкой для переменной Y в первоначальном выражении. Подстановка также называется связыванием. Говорят, что переменная связана со значением, используемым в качестве подстановки.

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

Хотя константу можно систематически использовать в качестве подстановки для переменной, любая константа рассматривается как "базовый экземпляр" и не может быть заменена. Нельзя также два различных "базовых экземпляра" использовать в качестве подстановки для одной и той же переменной.

Переменная не может быть унифицирована с термом, содержащим ее. Поэтому переменная X не может быть заменена на р(Х), поскольку это порождает бесконечное выражение: р(р(р(р(...Х)...). Тест для этой ситуации называется проверкой вхождения (occurs check).

Вообще, процесс решения задачи требует ряда выводов и, следовательно, ряда последовательных унификаций. Логические решающие устройства задач должны поддерживать согласованность подстановок для переменных. Важно, чтобы любая унифицирующая подстановка была сделана согласованно по всем вхождениям этой переменной во все выражения. А выражения должны быть приведены в соответствие друг другу. Эта ситуация уже встречалась, когда терм сократ использовался не только в качестве подстановки для переменной X в предложении человек(Х), но и для переменной X в выражении смертен(Х).

Если переменная связана, все последующие унификации и процедуры вывода должны учитывать это. Если переменная связана с константой, ее уже нельзя связывать с другим термом при последующих унификациях. Если переменная Х\ использовалась в качестве подстановки для другой переменной Хг, а затем была заменена константой, то вХ2тоже необходимо отразить это связывание. Множество замен, используемых в последовательности выводов, играет важную роль, потому что оно может содержать ответ на первоначальный вопрос (подраздел 12.2.5). Например, если р(а,Х) унифицировать с предпосылкой правила p(Y,Z)=>q(Y,Z) при помощи подстановки {a/Y,X/Z}, модус поненс позволяет вывести q(a,X) при той же подстановке. Если мы сопоставим этот результат с предпосылкой правила q(W,b)=>r(W,b), то выведем r(a,b) с учетом множества подстановок {a/W,b/X].

Другое важное понятие- это композиция подстановок унификации. Если S и S' являются двумя множествами подстановок, то композиция S и S' (пишется SS') получается после применения S' к элементам S и добавления результата к S. Рассмотрим пример композиции последовательности подстановок

{X/Y.W/Z}, {V/X}, {a/I/, f(b)/W). Они эквивалентны единственной подстановке {a/Y, f(b)/Z).

Последняя подстановка была выведена путем компоновки {X/Y, W/Z] с {V/X) для получения {V/Y, W/Z] и компоновки результата с {а/У, f(b)/W] для получения {a/Y, f(b)/Z}.

94

Композиция подстановок - это метод, с помощью которого объединяются подстановки унификации. Его можно реализовать, используя рекурсивную функцию unify, которая представлена ниже. Можно показать, что композиция является ассоциативной, но не коммутативной. В упражнениях эти вопросы рассмотрены более подробно.

Последнее требование алгоритма унификации- унификатор (unifier) должен быть максимально общим, т.е. для любых двух выражений должен быть найден наиболее общий унификатор. Это очень важно, поскольку при потере общности в процессе решения уменьшается вероятность достижения окончательного решения или такая возможность исчезает полностью.

Например, предложения р(Х) и р( Y) можно унифицировать любым константным выражением вида {fred/X, fred/Y}. Однако fred не является наиболее общим унификатором. Используя в качестве унификатора любую переменную, можно получить более общее выражение: {Z/X, Z/Y). Решения, полученные при использовании первой подстановки, всегда будут ограничены содержащейся в них константой fred, лимитирующей логические выводы. Следовательно, fred можно использовать в качестве унификатора, но это снижает универсальность результата.

ОПРЕДЕЛЕНИЕ

НАИБОЛЕЕ ОБЩИЙ УНИФИКАТОР

Если s - произвольный унификатор выражения Е, а д - наиболее общий унификатор (most general unifier - mgu) этого набора выражений, то в случае применения s к ? будет существовать еще один унификатор s' такой, что Es=Egs', где Es и Egs' - композиции унификаций, примененные к выражению ?.

Наиболее общий унификатор для набора выражений определяется с точностью до обозначения. В конечном счете, не имеет никакого значения, как называется переменная - X или У, поскольку это не снижает общности для результирующей унификации.

Унификация важна для любой системы решения задач искусственного интеллекта, использующей в качестве средства представления исчисление предикатов. Унификация определяет условия, при которых два (или больше) выражения исчисления предикатов могут быть эквивалентными. Это позволяет использовать для логического представления такие правила вывода, как резолюция (resolution), хотя этот процесс часто требует поиска с возвратом (backtracking) для нахождения всех возможных интерпретаций (см. главу 14).

Ниже будет представлен псевдокод для функции unify (унифицировать), которая вычисляет подстановки унификации (если это возможно) для двух выражений исчисления предикатов. Функция unify получает в качестве параметров два выражения исчисления предикатов и возвращает либо наиболее общую подстановку унификации, либо константу FAIL (отказ), если унификация невозможна. Эта функция определена рекурсивно: вначале она пытается рекурсивно унифицировать исходные компоненты выражений. Если это удается, все подстановки, возвращаемые в результате этой унификации, применяются к остальным выражениям. Затем выполняется второй рекурсивный вызов функции unify, в котором завершается унификация. Рекурсия прекращается, когда параметром становится символ (предикат, имя функции, константа или переменная), или когда все элементы выражения приводятся в соответствие.

Чтобы упростить работу с выражениями, в алгоритме применяется слегка измененный синтаксис. Поскольку функция unify просто проверяет синтаксическое соот-

95

ветствие шаблону, она игнорирует различия между предикатами, функциями и параметрами, свойственные исчислению предикатов. Представляя выражение в виде списка (list) - упорядоченной последовательности элементов, первым из которых является предикат, за которым следуют его параметры, мы упрощаем работу с выражениями. Выражения, в которых сами параметры являются предикатами или функциональными выражениями, представлены как списки в списках. Таким образом сохраняется структура выражения. Списки заключены в круглые скобки (), а элементы списка отделены друг от друга пробелами. Примеры выражений как в исчислении предикатов, так и в синтаксисе списков представлены ниже.

Синтаксис исчисления предикатов Синтаксис списка

p(a,b) (p a b)

р(f(a),g(Х,У)) (р (f a) (g х Y))

equal(eve,mother(Cain)) (equal eve (mother cain) )

Представим функцию unify.

function unify(El,E2); begin case

El и Е2 - константы или пустые списки: %рекурсия завершается if E1=E2 then return {}

else return FAIL; El - переменная: if El входит в Е2 then return FAIL

else return {E2/E1}; E2 - переменная: if E2 входит в El then return FAIL

else return {E1/E2}

El или Е2 - пуст then return FAIL %списки различных размеров

otherwise: %E1 и Е2 списки

begin

HE1:=первый элемент El; HE2:= первый элемент Е2; SUBSl:=unify(HEl,HE2) ; if SUBS1:=FAIL then return FAIL; TEl:=apply(SUBS1,хвост El); TE2:=apply(SUBSl,хвост Е2); SUBS2:=unify(TEl,TE2) ; if SUBS2=FAIL then return FAIL;

else return composition(SUBS1,SUBS2) end end

%конец case end

2.3.3. Пример унификации

Поведение вышеописанного алгоритма можно понять, проследив обработку запроса unify((parents X (fatherX) (mother bill)), (parents bill (father bill) Y))

96

Поскольку ни один параметр не является атомарным символом, при первом вызове функции unify она будет пытаться рекурсивно унифицировать первые элементы каждого выражения с помощью вызова

unify(parents, parents).

Эта унификация успешно выполнится и возвратит пустую подстановку {}. Применение ее к остальным выражениям не вызовет никаких изменений; затем вызывается

unify{(X(fatherX) (mother bill)), (bill (father bill) Y)).

Древовидное описание выполнения алгоритма на этой стадии представлено на рис. 2.4.

Во втором вызове unify ни одно выражение не является атомарным, поэтому алгоритм разделяет каждое выражение на его первый компонент и остальную часть. Затем следует вызов

unify(X, bill).

Этот вызов завершается успешно, поскольку оба выражения атомарные, и одно из них - переменная. В результате вызова возвращается подстановка {bill/X). Она применяется к "хвосту" каждого выражения, а функция unify - к результатам подстановки (рис. 2.5).

unify(((fatherbill) (motherbill)), ((father bill)Y)).

В результате этого вызова должна быть получена унификация (father bill) с (father bill). Это порождает вызовы

unify(father, father) unify (bill, bill) unify(( ),())

Все они успешно завершаются, возвращая пустое множество подстановок, как показано на рис. 2.6.

Затем функция unify вызывается для оставшихся выражений

unify(((mother bill)), (/)). Это, в свою очередь, приводит к вызовам

unify((mother bill), Y) unify(( ),( )).

В первом из них (mother bill) унифицируется с Y. Заметим, что в процессе унификации вместо переменной Y подставляется целая структура (mother bill). Таким образом, унификация завершается успешно и возвращает подстановку {(mother bill)/Y). Вызов

unify((),())

возвращает {}. В результате комбинации с полученной ранее подстановкой {bill/X) приходим к ответу {bill/X (mother bill)/Y). Весь процесс подстановок иллюстрируется на рис. 2.6. Вызовы пронумерованы, чтобы указать порядок их выполнения. Подстановки, возвращенные каждым запросом, помечены на дугах дерева.

97

Рис. 2.5. Дальнейшие шаги унификации выражений ((parents X (father X) (mother bill)) и (parents bill (father bill) Y)

98

Рис. 2.6. Заключительные шаги унификации выражений ({parents X (father X) (mother bill)) u (parents bill (father bill) Y)

99

2.4. Приложение: финансовый советник на основе логики

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

Задача "советника" - помочь пользователю решить, положить деньги на сберегательный счет или вложить их в акции. Некоторые инвесторы, возможно, захотят распределить свой капитал между двумя вариантами. Рекомендации отдельным инвесторам должны зависеть от их дохода и текущей накопленной суммы, т. е. удовлетворять следующим требованиям.

Лица с недостаточными накоплениями должны в первую очередь увеличивать

сумму на счету, независимо от их дохода.

Лица с достаточными накоплениями и стабильным доходом должны рассматри

вать более рискованные, но потенциально более выгодные инвестиции.

Лица с недостаточно высоким доходом, но уже имеющие значительные накопле

ния, могут захотеть рассмотреть возможность распределения их дохода между на

коплениями и акциями, чтобы, с одной стороны, оградить себя от потерь при по

пытке увеличить доход за счет акций, а с другой, рискнуть и значительно увели

чить прибыль.

Соответствие между накоплением и доходом определяется числом иждивенцев, которых данное лицо должно содержать. На каждого иждивенца необходимо иметь в банке по крайней мере $5000. Достаточным считается стабильный доход, составляющий по крайней мере $15000 в год плюс $4000 на каждого иждивенца.

Чтобы автоматизировать эти рекомендации, запишем их на языке исчисления предикатов. Вначале необходимо выделить главное требование, которые следует принять во внимание. Поэтому первое требование - это достаточность сбережений и дохода. Их можно представить с помощью предикатов savingsjaccount (сберегательный счет) и income (доход) соответственно. Это унарные предикаты, параметром которых может быть значение adequate (достаточен) или inadequate (недостаточен). Таким образом, возможны следующие комбинации.

savings_account(adequate). savings_account(inadequate). income(adequate). income(inadequate).

Заключения представим унарным предикатом investment (инвестиции), параметр которого может принимать значения: stocks (акции), savings (сбережения) или combination (сочетание - т.е. разбиение инвестиций).

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

savings_account(inadequate) -* investment(savings).

Аналогично сохранение двух инвестиционных альтернатив можно представить следующим образом.

100

savings_account(adequate) л income(adequate) -> investment(stocks). savings_account{adequate) л income(inadequate) -> investment(combination).

Затем, советник должен определить, достаточны ли сбережения и доходы. Это также можно записать с помощью импликации. Потребность в арифметических вычислениях приводит к использованию функций. Для определения минимума достаточных сбережений создадим функцию minsavings. Функция minsavings зависит от одного параметра, соответствующего числу иждивенцев, и возвращает результат умножения этого параметра на 5000.

Используя функцию minsavings, достаточность сбережений можно определить правилами

VXamount_saved(X) л ЗУ (dependents(Y) л greater(X, minsavings(Y))) -> savings_account{adequate).

VXamount_saved(X) л 3Y{dependents(Y) л -,greater{X,minsavings(Y))) -» savings_account(inadequate),

где

minsavings(X) =5000 * X.

При этих определениях amount_saved(X) и dependents(Y) означают текущую сумму сбережений и число иждивенцев (dependents) инвестора. Здесь greater{X, Y) - стандартная арифметическая проверка, определяющая, что больше: X или Y. В этом примере данная функция формально не определена.

Аналогично функцию minincome можно определить так.

minincome(X) =15000 +(4000 * X).

Функция minincome используется для вычисления минимального приемлемого дохода в зависимости от числа иждивенцев. Текущий доход инвестора представлен предикатом earnings (доходы). Поскольку достаточный доход должен быть стабилен и превышать минимально допустимое значение, earnings имеет два параметра. Первый параметр - заработанная сумма, а второй может принимать значение steady (стабильный) или unsteady (нестабильный). Приведем правила работы советника, описывающего эту ситуацию.

VXearnings(X, steady) ^ 3Y(dependents{Y) ^ greater(X, minincome(Y)))

-> income(adequate).

4Xearnings(X, steady) ^ ЗY (dependents(Y) ^ - greater(X, inincome(Y)))

-> income(inadequate).

VXearnings(X, unsteady) -> income(inadequate).

Чтобы давать консультации, необходимо добавить к этому набору предложений исчисления предикатов описание конкретного инвестора. Это - предикаты amountjsaved (сумма на счету), earnings (доходы) и dependents (иждивенцы). Например, человека с тремя иждивенцами, имеющего $22000 в сбережениях, и с устойчивым доходом в $25000 можно описать так.

amountjsaved (22000). earnings(25000, steady) dependents(3).

101

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

savings_account(inadequate) -»investment{savings).

savings_account(adequate) л income(adequate) -> investment(stocks).

savings_account(adequate) л income(inadequate)

-> investment(combination).

V amount_saved(X) ^ 3 Y (dependents(Y) ^ greater(X, minsavings(Y)))

-> savings_account(adequate).

V Xamount_saved(X) ^ 3 Y(dependents(Y) ^ greater(X, minsavings(Y)))

-> savings_account{inadequate).

V X earnings(X, steady)^3 V (dependents (Y) ^ greater(X, minincome(Y)))

-> income(adequate).

1. VXearnings(X, steady) ^ 3 Y (dependents(Y) ^-i greater(X, minincome(Y))) -> income(inadequate).

VXearnings(X, unsteady) -> income(inadequate).

amounf_sai/ed(22000).

earnings(25000, steady).

dependents^).

Здесь

minsavings(X) = 5000 * X и

minincome(X) = 15000 + (4000 * X).

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

Используя унификацию и правило л*ск)ус поненс, можно вывести правильную инвестиционную стратегию для этого лица как логическое следствие данных выше описаний. На первом шаге нужно унифицировать конъюнкцию высказываний 10 и 11 с первыми двумя компонентами предпосылки из 7. Иными словами,

earnings(25Q00,steady) л dependents(3) нужно объединить с

earnings(X,steady) л dependents(Y) с учетом подстановки {2500 0/Х, 3/У}. Эта подстановка порождает новую импликацию.

earn/ngs(25000, steady) л dependents(3) л -, greafer(25000, minincome(3)) -> income(inadequate).

Оценивая функцию minincome, приходим к выражению

earn/'ngs(25000, steady) л dependents(3) л -i greafer(25000, 27000) -» income(inadequate).

Поскольку в этом частном случае все три компонента предпосылки истинны согласно предложениям 10, 11 и математическому определению функции greater (больше), их конъюнкция тоже истинна. Из этого следует, что истинна и вся предпосылка. Поэтому

102

можно применить правило модус поненс и получить заключение income(inadequate), означающее, что доход недостаточен. Добавим этот вывод к набору предложений, присвоив ему номер 12.

\2. income(inadequate). Аналогично, унифицируя

amount_saved{22000) л dependents(3)

с первыми двумя элементами предпосылки утверждения 4 с учетом подстановки {22000/X, 3/У}, получим импликацию

amount_saved(22000) л dependents(3) л greafer(22000, minsavings{3)) -»savings_account{adequate).

Оценивая функцию minsavings(3), приходим к выражению

amount_saved(22000) л dependents{3) л greafer(22000, 15000) -»savings_account(adequate).

Опять же, поскольку все компоненты предпосылки этой импликации истинны, то вся предпосылка истинна, поэтому можно снова применить модус поненс и получить заключение savings_account(adequate). Представим его как предложение 13.

13. savings_account(adequate).

Анализируя выражения 3, 12 и 13, делаем вывод, что предпосылка в выражении 3 также истинна. Применив модус поненс в третий раз, получаем результат investment(combination). Это предложение и есть рекомендация по инвестициям для данного лица.

На этом примере мы показали использование исчисления предикатов для описания реальной проблемы. Кроме того, мы сделали логические выводы на основе применения правил вывода к исходному описанию задачи. Мы все же не обсуждали, как обеспечить корректность вывода и реализовать этот алгоритм на компьютере. Эти вопросы будут рассмотрены в главах 3, 4 и 5.

2.5. Резюме и дополнительная литература

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

Исчисление предикатов подробно обсуждается в ряде книг по теории вычислительных машин и систем, в том числе в [Manna и Waldinger, 1985], [Gallier, 1986], [Chang и Lee, 1973], [Andews, 1986]. Современные методы доказательства будут представлены в главе 12.

103

Применение исчисления предикатов как языка представления для задач искусственного интеллекта описано в [Genesereth и Nilsson, 1987], [Nilsson, 1998], [Wos, 1995], [Bundy, 1983, 1988] и [Brachman и Levesque, 1985]. Интересные современные приложения автоматизированного вывода описаны в [Veroff, 1997].

2.6. Упражнения

Используя таблицы истинности, докажите тождества из подраздела 2.1.2.

Новый оператор @ (читается "исключающее ИЛИ") можно определить следующей

таблицей истинности.

Создайте выражение исчисления высказываний, эквивалентное Р @ Q, используя только операции л, v и -i.

Докажите их эквивалентность с помощью таблиц истинности.

3. Логический оператор <-» означает "тогда и только тогда". Выражение Р <-> О эквива

лентно (Р -> О)л (О -> Р). Базируясь на этом определении, докажите, что Р <^> Q

логически эквивалентно (Р v О) -» (Рл О).

Используйте при этом таблицы истинности.

Воспользуйтесь последовательностью подстановок с учетом тождеств, приве

денных в подразделе 2.1.2.

Докажите, что в исчислении высказываний импликация транзитивна, т.е. что ((Р -»

О) л (О-> Я)) -» (Р-» R).

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

Подсказка: используйте таблицы истинности и рассмотрите все возможные интер

претации.

б. Абдукция (abduction) - это правило, которое позволяет вывести Р из Р -> О и О.

Покажите, что абдукция необоснована (см. главу 7).

в. Покажите, что правило модус толленс (modus tollens) ((P-»Q)a-iQ)-»-iP ло

гично.

6. Попытайтесь унифицировать следующие пары выражений. Найдите их наиболее об

щие унификаторы или же объясните, почему они не могут быть унифицированы:

a)p(X,Y)и p(a,Z);

б)р(Х,Х)и р(а,Ь);

в) ancestor(X,Y) и ancestor(bill, father(bill));

г)ancestor(X,father(X)) иancestor(david,george);

д)q(X)H-,q(a).

а. Скомпонуйте множества подстановок {а/Х, Y/Z} и {X/W, b/Y).

104

б. Докажите, что композиция множеств подстановок ассоциативна.

в. Постройте пример, демонстрирующий, что композиция не коммутативна.

Реализуйте алгоритм unify (подраздел 2.3.2) на выбранном вами языке программирования.

Приведите две альтернативные интерпретации для описания мира блоков (рис. 2.3).

Джейн Доу содержит четырех иждивенцев, имеет стабильный доход $30000 и $15000

на сберегательном счету. Составьте соответствующие предикаты, описывающие эту

ситуацию для системы финансового советника, рассмотренной в разделе 2.4, выполните унификацию и получите выводы, необходимые для выдачи рекомендаций по

инвестициям.

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

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

Следующий пример взят из книги [Wirth, 1976].

Я женился на вдове (давайте назовем ее И/), которая имеет взрослую дочь (назовем ее D). Мой отец (F), который весьма часто навещал нас, влюбился в мою падчерицу и женился на ней. Поэтому мой отец стал моим зятем, а моя падчерица стала моей мачехой. Спустя несколько месяцев моя жена родила сына (S1), который стал шурином (зятем) моему отцу, а потому моим дядей. Жена моего отца, т.е. моя падчерица, тоже родила сына (S2).

Используя исчисление предикатов, создайте набор выражений, описывающих данную ситуацию. Добавьте выражения, определяющие основные отношения в семье, в том числе определение тестя (или свекра), и, используя правило модус поненс, докажите заключение "Я сам себе дедушка".

105

106

Глава 3. Структуры и стратегии поиска в пространстве состояний

Для того чтобы выжить, организм должен либо защитить себя броней (подобно де­реву или моллюску) и "надеяться на лучшее", либо развивать способность избегать опас­ных путей и стремиться к безопасному соседству. Если он предпочел второе, ему при­дется постоянно задавать себе основополагающий вопрос: "Что я сейчас делаю?".

- Даниэл С. Деннет (Daniel С. Dennett), Объяснение подсознания

Две дороги расходятся в желтом лесу,

Жаль, не могу я пройти по каждой из них.

Был одиноким я странником в этом лесу.

Долго стоял и смотрел на одну из них,

На ту, уходящую в даль, туда, где она исчезает вдали;

Затем я пошел по дороге другой...

- Роберт Фрост (Robert Frost), Невыбранная дорога

3.0. Введение

В главе 2 описано исчисление предикатов - пример языка представления в искусствен­ном интеллекте. Правильно составленные выражения исчисления предикатов позволяют опи­сывать объекты и отношения в области определения, а правила вывода (например, правило отделения modus ponens) - логически получать новые знания из имеющихся описаний. Эти правила вывода определяют пространство, в котором ведется поиск решения задачи. Глава 3 является введением в теорию поиска в пространстве состояний.

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

Гарантировано ли нахождение решения в процессе поиска? Является поиск конечным, или в нем возможны зацикливания? Если решение найдено, является ли оно оптимальным?

107

Как процесс поиска зависит от времени выполнения и используемой памяти? Как интерпретатор может наиболее эффективно упростить поиск?

Как разработать интерпретатор для наиболее эффективного использования языка представления?

Теория поиска в пространстве состояний (state space search) дает ответы на эти во­просы. Представив задачу в виде графа пространства состояний, можно использовать теорию графов для анализа структуры и сложности как самой задачи, так и процедуры поиска ее решения.

Граф состоит из множества вершин и дуг, соединяющих пары вершин. В модели про­странства состояний решаемой задачи вершины графа представляют дискретные со­стояния процесса решения, например, результаты логического вывода или различные конфигурации игровой доски. Дуги графа описывают переходы между состояниями. Эти переходы соответствуют логическим заключениям или допустимым ходам в игре. Так, в экспертных системах состояния описывают знания о задаче на определенном этапе ис­следования. Экспертные заключения в форме правил "если ..., то" позволяют получить новую информацию. При этом каждый случай применения правила представляется как дуга между состояниями.

Теория графов является наилучшим инструментом исследования структуры объектов и их отношений. Именно это и привело к созданию теории графов в начале восемнадцатого века. Швейцарский математик Леонард Эйлершзобрел теорию графов, чтобы решить "задачу о кенигсбергских мостах". Город Кенигсберг расположен на двух берегах реки и двух островах. Острова и берега реки соединены семью мостами, как показано на рис. 3.1.

Задача о кенигсбергских мостах формулируется следующим образом. Существует ли маршрут обхода города, при котором каждый мост пересекается ровно один раз? Хотя местные жители после безуспешных попыток найти такой маршрут усомнились в его существовании, никто не мог доказать его отсутствие. Создав модель графа, Эйлер реа­лизовал альтернативное представление карты города (рис. 3.2). Берега реки (rb1 и rb2) и острова (i1 и i2) описываются вершинами графа; мосты представлены помеченными ду­гами между вершинами b1 , b2, ..., b7). Представление в виде графа сохраняет сущест­венную информацию (структуру системы мостов), а несущественные данные (расстояние и направление) игнорируются.

108

Рис. 3.2. Граф системы мостов города Кенигсберга

Кроме того, систему кенигсбергских мостов можно представить в терминах исчисле­ния предикатов. Предикат connect (соединить) соответствует дуге графа и утверждает, что берега реки или острова связаны некоторым мостом. Для каждого моста необходимо задать два предиката connect - по одному для каждого направления движения по мосту.

connect (i1, i2, b1) connect (i2, i1, b1)

connect (rb1, i1, b2) connect (i1, rb1, b2)

connect (rb1, i1, b3) connect (i1, rb1, b3)

connect (rb1, i2, b4) connect (i2, rb1, b4)

connect (rb2, i1, b5) connect (i1, rb2, b5)

connect (rb2, i1, b6) connect (i1, rb2, b6)

connect (rb2, i2, b7) connect (i2, rb2, b7)

Выражение connect{X,Y,Z)=connect(Y,X,Z), указывающее на то, что каждый мост может быть пройден в любом направлении, позволяет исключить половину предикатов.

Представление с помощью предикатов эквивалентно представлению в виде графа в смысле сохранения связности. Однако никакой алгоритм не может преобразовать одно представление знаний в другое без потери информации. Структура задачи более естест­венно отражается в представлении на основе графа. Доказательство Эйлера иллюстриру­ет эти различия.

Чтобы доказать невозможность существования нужного маршрута, Эйлер вводит по­нятие степени вершины графа, замечая, что каждая вершина может иметь четную либо нечетную степень. Вершина четной степени имеет четное число дуг, соединяющих ее с соседними вершинами. Вершина нечетной степени имеет нечетное число таких дуг. Вершины нечетной степени могут использоваться только как начало либо как конец маршрута. Все остальные вершины должны иметь четную степень, поскольку искомый маршрут должен входить в каждую такую вершину и выходить из нее. Иначе такие вер­шины будут пройдены определенное число раз, а затем окажутся тупиковыми. Путеше­ственник не сможет покинуть вершину, не используя еще раз уже пройденную дугу.

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

109

вершине. Итак, маршрут невозможен, если число вершин нечетной степени графа от­лично от 0 или 2, как в задаче о кенигсбергских мостах. Эта задача называется задачей поиска пути Эйлера на графе.

Хотя предикатное представление описывает отношения между мостами, берега­ми и островами, оно не учитывает понятие степени вершины. Представление в виде графа обеспечивает однозначную связь каждой вершины с дугами, в отличие от ар­гументов предикатов. Именно поэтому представление с помощью графа приводит к понятию степени вершины и играет ключевую роль в доказательстве Эйлера. В этом заключается преимущество теории графов с точки зрения анализа структуры объек­тов, свойств и отношений.

В этой главе сначала приводится краткий обзор основ теории графов, а затем - описание пространства состояний задачи и поиска на графах. Поиск в глубину и поиск в ширину - это две стратегии поиска в пространстве состояний. Мы сравним их, от­мечая различия между поиском от цели и поиском на основе данных. В разделе 3.3 описание в пространстве состояний используется для вывода логических заключений. На протяжении всей главы теория графов будет использована для анализа структуры и сложности различных задач.

3.1. Теория графов

3.1.1. Структуры данных для поиска в пространстве состояний

Граф - это множество вершин и дуг между ними. В размеченном графе для каждой вершины задается один или несколько дескрипторов (меток), которые позволяют отли­чить одну вершину графа от другой. На графе пространства состояний эти дескрипторы идентифицируют состояния в процессе решения задачи. Если дескрипторы двух вершин не различаются, то эти вершины считаются одинаковыми. Дуга между двумя вершинами определяется метками этих вершин.

Дуги графа также могут быть размеченными. Метка дуги используется для задания именованного отношения (как в семантических сетях) либо веса дуги (как в задаче о коммивояжере). Дуги между двумя вершинами тоже можно различать с помощью ме­ток (см. рис. 3.2).

Граф называется ориентированным, если каждой дуге приписано определенное на­правление. Дуги в ориентированном графе обычно содержат стрелки, определяющие ориентацию дуги. Дуги, которые можно проходить в любом из двух направлений, могут содержать две стрелки-указателя, но чаще вовсе не имеют стрелок. На рис. 3.3 изобра­жен размеченный ориентированный граф. По дуге (а, b) можно двигаться лишь от вер­шины а к вершине b, по дуге (b,с) можно двигаться в любом из двух направлений.

Путь (path) на графе - это последовательность дуг, соединяющих соседние верши­ны. Путь представляется списком дуг, систематизированным в порядке их следования. На рис. 3.3 список [a,b,c,d] представляет путь, проходящий через вершины a,b,c,d в указанном порядке.

Корневой граф содержит единственную вершину, от которой существует путь к лю­бой вершине графа. Эта вершина называется корнем (root). При изображении корневого графа корень обычно помещают в верхней части рисунка над всеми остальными верши­нами. Граф пространства состояний любой игры обычно является корневым графом,

110

причем в качестве корня выступает начальное состояние игры. Начальные ходы в "крестики-нолики" представлены в корневом графе на рис. U.S. Это ориентированный граф, в котором все дуги являются однонаправленными. Заметим, что этот граф не имеет циклов; игроки не могут (как бы они этого не хотели) аннулировать ходы.

Дерево (tree) - это граф, на котором для любых двух вершин существует не более одного пути между ними. Деревья обычно имеют корни, которые изображаются в верх­ней части рисунка, как и для корневых графов. Поскольку для каждой вершины дерева существует не более одного пути в эту вершину из любой другой вершины, то не суще­ствует путей, содержащих петли или циклы.

Для корневых деревьев или графов отношения между вершинами описываются поня­тиями родителя, потомка и вершин-братьев (siblings) - вершин дерева, имеющих об­щую вершину-родителя. Они используются в обычном смысле наследования: при прохо­де вдоль направленной дуги родитель предшествует потомку. Концы всех направленных дуг, исходящих из одной вершины, называются вершинами-братьями. Аналогично на пути ориентированного графа предок предшествует потомку. На рис. 3.4 вершина Ь яв­ляется родителем вершин е и f (которые являются потомками b и вершинами-братьями). Вершины а и с являются предками вершин gf, h, i, а вершины д, h, / являются потомками а не.

Прежде чем ввести определение пространства состояний задачи, приведем формаль­ные определения рассмотренных выше понятий.