|
|
Для решения задач эффективного
управления роботом должна быть реализована возможность представления,
исправления и преобразования наборов утверждений, для чего и используется
язык логики. Логический формализм является мощным средством выведения новых
знаний из старых методов математической дедукции. В соответствии с этим
методом новое утверждение истинно, если можно доказать, что оно следует из
утверждения, о котором уже известно, что оно истинно.
На языке логики предикатов можно представить события
окружающего мира в виде так называемых правильно построенных формул (ППФ). Но
главное качество логики предикатов в том, что с ее помощью можно не только
отобразить знания, но и получить из них новые.
Предикаты, или логические функции, используются для
установления связи в рассуждениях. Например, для описания факта "Робот в
помещении rt" достаточно простой формулы-атома: INROOM (ROBOT г1).
Формулы-атомы являются элементарными утверждениями, на
основании которых строят более сложные ППФ, используя набор логических
операций-действий (см. ниже).
Словарь символов
Основными компонентами языка логики предикатов, или ее
словарем символов, являются: имена, константы и переменные, функции и
термины.
Имена - это заимствованные из обычных языков выражения,
служащие для непосредственного обозначения объекта или вещи. Каждое имя в
логике предикатов в отличие от естественных языков имеет только один смысл.
Примерами имен являются: "ROBOT", "манипулятор",
"Unimate", "устройство передвижения", "цех" и
т.д.
Константы и переменные. Константа - это собственное имя
объекта, человека, робота, числа, например: "ведущий вал",
"JOHN" (Джон), "PUMA", "один", "two"
(два) и т.д. Переменная - это символ, смысловое содержание которого совпадает
с содержанием константы, но единственность значения константы заменена здесь
возможностью различных значений, принимаемых переменной. С каждой переменной
связана некоторая непустая область ее возможных значений. Следует особенно
подчеркнуть, что переменная в исчислении предикатов есть определенного рода
символ (х, у и т.д.), а не объект, который этот символ обозначает.
Функции и термины. Определение функции совпадает с
общепринятым в математике: это операция, которая, будучи применена к
чему-либо как аргументу, дает некоторый объект в качестве значения функции
данного аргумента. Функции применяются для установления связей между предметами,
подлежащими рассмотрению. Например, функция mother (мать) применяется для
установления связи между человеком и его родителем по материнской линии:
mother (JOHN) - мать" Джона.
Как и в математике, вводятся понятия области определения _
и области значения функции, а также форма ее представления: f (х) - значение
функции f от аргумента х. Чтобы обозначить значение функции для некоторого
аргумента, обычно пишут имя этой функции и приписывают к нему справа имя
аргумента, взятое в скобки: INROOM (х, у); mohter (JOHN). Если функция
применима к упорядоченной системе из п аргументов, то она называется п-арной:
f(i, к, I,п).
Важную роль в исчислении предикатов играют выражения для
функций, значения которых принадлежат той же области, что и их аргументы.
Такие выражения, построенные на основе символов предметных. переменных и
констант с помощью символов функций, называются термами. Содержательно терму
соответствует имя некоторого объекта или вещи. Константы, например, являются
простейшими видами термов для представления объектов или вещей при
рассуждениях.
Правила соединения символов
Рассмотренные компоненты языка логики предикатов (словарь
его символов) соединяются между собой и интерпретируются в соот- вествии с
определенными правилами, изложенными ниже.
Предложения, высказывания и предикаты. В обычных языках
простейшим выражением является предложение, являющееся соединением слов,
имеющим самостоятельный смысл. Каждому предложению соответствует заключенное
в нем высказывание, причем полагается, что каждое высказывание или истинно,
или ложно и не может быть одновременно и истинным, и ложным. Таким образом,
высказывание может рассматриваться как величина, принимающая лишь два
значения - "истинно" (И) или "ложно" (Л).
Высказывание о каком-либо объекте х можно считать функцией
' F (х), принимающей только два значения - И или Л, причем определенным
высказыванием F (х) становится только тогда, когда переменная х принимает
конкретное значение. Например, предложение "х есть машина"
становится определенным высказыванием, если переменной х придать предметное
значение. Например, если положить, что х = = "робот", то получим
истинное высказывание и, напротив, положив х = "слон", получим
высказывание ложное.
Аналогично неопределенное высказывание о двух, трех и
более объектах представляет собой функцию со значениями И и Л от двух, трех и
более переменных. Именно такие неопределенные высказывания - функции вида F
(хг, х2, ..., хп), аргументы которых (хх, х2, ..., хп) принимают значения из
рассматриваемой области, а сами функции только два значения - И и Л,
называются логическими функциями или предикатами.
Предикат, аргументы которого являются п преметных
переменных, называется п-местным. Если п = 1, то предикат определяет
некоторое свойство объекта; если п > 2, то предикат выражает п-арное
отношение между объектами.
Элементарные и правильно построенные формулы и. логические
операции. Элементарными формулами (или формулами-атомами, атомарными
формулами) принято называть предикаты независимо от их смысла, количества и
содержания термов. Значит, формулы-атомы можно рассматривать как элементарные
величины, принимающие значения И или Л, над которыми возможно производить
логические операции-действия, приводящие к получению новых, более сложных
формул. Для этого используют определенные логические операции, каждая из
которых имеет собственный смысл и символику:
1) конъюйкция, обозначаемая Л, или & и
означающая "и";
2) дизъюнкция, обозначаемая V и означающая
"или"; "... или,... или"; "и/или";
3) импликация, обозначаемая и означающая
"влечет за собой", "если ..., то...", "если ...,
тогда...", "только если";
4) эквивалентность, обозначаемая +* и означающая
"равносильно", "эквивалентно", "тогда и только
тогда";
5) отрицание, обозначаемое 1, или и означающее
"не", "неверно, что...".
Если А и В какие-либо (элементарные или сложные) формулы,
то над ними теперь можно производить действия-операции: пользуясь введенной
символикой, например, АЛВ; AVB; А -* В; А В; "|А; 1В, получая более
сложные формулы. Для однозначного прочтения и восприятия сложных формул
применяют скобки, указывающие, в каком порядке связывать их между собой.
Поэтому следует писать, например, (А -"В) ^С или А -(В -«-С), но не А-*
В^- С. Для уменьшения же числа скобок, как и в арифметических действиях,
устанавливается "старшинство" символов операций в порядке убывания:
**,-*, V, А, ]. Так, например, можно записать без скобок А -*ВЛС, что
означает А-*(ВЛС). Символ отрицания 1, или имеет наименьший ранг, поэтому,
например, ~|А V В означает (1A)VB, ноне l(AVB).
Кроме рассмотренных в логике предикатов используют еще два
символа-связи, выражающих операции утверждения всеобщности и существования:
1) квантор всеобщности, обозначаемый Vx и
означающий "для всех х ... истинно";
2) квантор существования, обозначаемый Зх и
означающий "существует такое х, что... истинно".
Теперь можно дать еще одно определение правильно
построенной формулы на языке робота. ППФ есть выражение в виде конечной
последовательности символов, которое строится на основе элементарных
формул-атомов путем перехода от формулы А к формулам VxA и ЗхА и от формул А
и В к формулам АЛВ, AVB, А -»• В, А ** В, 1А, 1 В. При этом элементарная формула
или ее отрицание, входящие в ППФ, называются литерами (или литералами), а
дизъюнкция литеров называется простым дизъюнктом. Если дизъюнкт не содержит
никаких литер, то он называется пустым дизъюнктом.
Интерпретации и методы решения логических задач
Правильно построенные формулы имеют практический смысл,
становятся осмысленными лишь тогда, когда входящие в них формальные символы
получают какую-либо интерпретацию. Интерпретация - это предписание,
устанавливающее соответствие языковым символам формулы некоторых объектов
предметной области: константам и переменным - элементов этой области;
функциональным символам - конкретных функций, определяющих связи между
реальными объектами и вещами; предикатным символам - конкретных предикатов.
Таким образом, интерпретация, осуществляя связь между языком робота и
описываемой им предметной областью реального мира, позволяет придать ППФ
содержательный смысл, т.е. играет роль семантики языка.
Следует заметить, что противоречивость (неудовлетворимость)
в ходе логического вывода выражается в получении из системы ППФ в качестве
истинных какой-либо формулы и ее отрицания одновременно, так называемой
нуль-формулы (nil).
Один из наиболее эффективных и универсальных методов
поиска логического вывода является предложенный в 1965 г. Дж. Робинсоном так называемый метод резолюций, в основу которого заложена идея доказательства
от противного. Вместо заданной формулы В, которая предполагается
тождественной истинной, рассматривается ее отрицание 1В и доказывается
противоречивость последней формулы. Полученное противоречие доказывает
неудовлетворимость формулы ]В и, следовательно, тождественную истинность
исходной формулы В.
Метод замечателен тем, что сложный процесс логического
вывода он сводит к последовательности очень простых операций, каждая из
которых может быть легко запрограммирована
В основе использования метода резолюций лежат три простых
правила вывода, или резольвенции:
1) если истинны ППФ А и 1AVB, то истинна ППФ В
(правило modus ponens);
2) если истинна ППФ AVA, то истинна ППФ А (правило
факторизации);
3) если истинна ППФ A (N), то истинна ППФ VxA (х)
(правило универсальной специализации), где N - константа.
Эти правила применимы к простым дизъюнктам, на которые
предварительно и "раскладывается" система ППФ { А( V]A, из
противоречивости которой следует, что А выводимо из { А,- . Новые дизъюнкты,
получаемые в результате применения указанных правил, назваются резольвентами.
При образовании резольвент существенную роль играет
процедура унификации, которая для двух данных предикатов
осуществляется подстановкой термов вместо переменных,
делающих предикаты одинаковыми. Например, для неудовлетворимой системы ППФ
вида { А (х) VB (х), ]В (f (г)), ]А (f (z))}, используя первое правило
резольвенции после подстановки терма f(z) вместо переменной х, получим из
первых двух ППФ резольвенту A (f (z)), которая в сочетании с третьей ППФ
системы дает нулевую формулу (одновременное утверждение и отрицание
истинности ППФ). Таким образом, если выбрано два простых дизъюнкта и по одной
литере в каждом из них, то применение правил унификации, а затем резольвенции
дает резольвенту; при этом при доказательстве выводимости ППФ процесс
образования резольвент продожается пока не будет получена нуль-формула,
означающая неудовлетворимость исходной системы { А,- }(=1 V]A, а значит, и
успех доказательства от противного.
Важным качеством системы логического вывода является
возможность установления не только истинности того или иного высказывания, но
и значения переменной, при которой утверждение истинно. В качестве
иллюстрации рассмотрим очень простой с точки зрения homo sapiens пример
решения логической задачи, но совершенно неразрешимой для машины, не
обладающей хотя бы зачатками искусственного интеллекта.
|