9.Логика предикатов

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

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

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

Рассмотрим подробнее язык логики предикатов.

Синтаксис и семантика. Синтаксис логики предикатов с использованием метаязыка Бэкуса-Наура приведен ниже. Рассмотрим семантику всех синтаксических конструкций, приведенных здесь.

Формула 

Атом

Предложение

Предложение Связка Предложение

Квантор (Переменная,...,Переменная) Предложение

 Предложение

 (Предложение),

Атом 

Предикатный символ (Терм,...,Терм)

Терм=Терм,

Терм 

Функциональный символ (Терм,...,Терм)

Константа

Переменная

Связка  ,

Квантор  ,

Константа  Строка символов, начинающаяся с прописной буквы,

Переменная  Строка символов, со строчной буквы,

Предикатный символ  Строка символов, со строчной буквы,

Функциональный символ  Строка символов, со строчной буквы.

Рис. 8.1.

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

Функции. Для того чтобы задать такие отношения между объектами, когда в точности один объект соответствует множеству других объектов используют функции. Например, если объектами являются двоичные цифры 0 и 1 и десятичные цифры 0,1,...,9, то любому набору из трех двоичных цифр, который представляет двоичное число, можно однозначно сопоставить десятичную цифру. Если двоичные цифры сопоставить с переменными а десятичные с переменной то рассмотренное отношение между двоичными и десятичными цифрами можно представить в виде функции

преобразование_2_в_10

Выражение преобразование_2_в_10 называют функциональным символом. Так при с помощью функции преобразование_2_в_10 получим значение функции, равное Отметим, что функция в логике предикатов не предполагает обязательного наличия какого-либо алгоритма вычисления значения функции по её аргументам. Она лишь задает с помощью констант и переменных определенное отношение между объектами, соответствующими её аргументами, и каким-то одним объектом.

Объектные константы. Каждая объектная константа, называемая в дальнейшем, если это не вызывает путаницы, просто константой, взаимно однозначно сопоставляется в процессе интерпретации с каким-либо одним объектом среды. Константа обозначается строкой символов, которая начинается с прописной буквы, и, чаще всего, эта строка символов совпадает с именем или наименованием объекта и записывается курсивом, например, Владимир, Чудовище, Кот и т. д.

Термы. Константы, переменные и функции являются термами. Выбор констант, переменных и функций для данной среды полностью является прерогативой того, кто использует логику предикатов. Предположим, например, что наша среда имеет такие объекты, как крылья и птицы, и нам известно, что "птицы имеют крылья". Спрашивается, как выразить это знание? Введем константы, которые обозначают конкретный вид птиц, например, Воробей, Синица, Соловей и константу Крылья, которая обозначает объект крылья. Введем также переменную которая обозначает все объекты, которые являются птицами: функциональный символ имеет крылья ставит во взаимно-однозначное соответствие любой птице объект крылья. Тогда функция имеет_крылья задает отношение между объектом крылья и птицей

Если, например, Воробей, то имеет_крылья (Воробей)=Крылья. Но это не единственная возможность выразить отношения между птицами и крыльями. Функция может не содержать аргументов, т.е. иметь только функциональный символ. Термы, которые не содержат аргументов, т.е. константы, переменные и функции без аргументов, называют элементарными термами.

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

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

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

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

Квантор общности . Вспомним, что при решении задачи поиска золота в среде чудовища для того, чтобы выразить правило "В какой бы ячейке агент не находился, если он видит блеск золота, то он должен его взять", было использовано 16 однотипных формул, число которых совпадает с числом ячеек. Эти формулы имели вид

Здесь отдельные переменные. Каждая из них принимает истинное значение, если соответствующий ей объект (в данном случае агент и золото, точнее блеск золота) находится в ячейке Обратим ещё раз внимание на то, что и это индексированные логические переменные с индексами каждая из которых считается единым неделимым символом. Большое количество формул пришлось вводить из-за того, что в логике высказываний нет возможности представить указанное выше правило в виде одной формулы. В логике предикатов такая возможность имеется и, вместо 16 формул в логике высказываний, в логике предикатов можно написать одну

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

"Для всех ячеек с координатами и видит в ней блеск золота, то он должен его взять".

Смысл квантора общности  совпадает с выражение естественного языка: "Для всех...". Множество формул (8.1) логики высказываний эквивалентно одной формуле (8.2) логики предикатов, т.е. имеет место

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

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

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

Квантор существования произносится на естественном языке как "Существует...".

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

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

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

Равенство. Ранее рассматривался атом особого типа терм  терм, называемый равенством, в котором используется знак равенства в инфиксной форме. Этот знак, который является предикатным символом, свидетельствует о том, что формула терм  терм истинна только в том случае, если оба терма соответствуют одному и тому же объекту. Обозначая константы символами , переменные символами , функциональный символ , это можно пояснить с помощью таблицы

Таблица

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

Использование равенства можно пояснить двумя примерами из мира чудовища. Имеем формулу

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

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

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

При описании аксиом и целей конкретной среды возникает много вопросов. Приведем некоторые из них.

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

Как избежать избыточного числа аксиом?

В каком виде аксиомы лучше всего сформулировать?

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

Если существо имеет крылья, то это существо - птица.

Если существо летает и несёт яйца, то это существо - птица.

Те же знания можно выразить на языке логики предикатов в виде таких правил или формул

имеет_крылья (существо)  птица (существо),

имеет_крылья (существо)  несет_яйца (существо) птица (существо)

Для того чтобы перейти к этой форме представления знаний в языке логики предикатов сначала, глядя на предложения русского языка, определяем, что же является объектом, который необходимо сопоставить с константой или переменной. В данном случае речь шла о классе некоторых существ, обладающих определенными свойствами. Поскольку речь идет не о конкретном существе, а о классе существ, то вводим переменную существо для обозначения всех представителей этого класса. Свойства существ задаются фразами русского языка "имеет крылья", "летает", "несет яйца", "птица". Из этих фраз, обозначающих свойства, построим соответствующие предикатные символы, имеет_крылья, летает, несет_яйца, птица. С использованием этих обозначений фразы "существо имеет крылья", "существо летает", "несет яйца", "это существо - птица" заменяются соответственно на предикаты имеет_крылья (существо), летает (существо), несет_яйца (существо), птица (существо). Из этих предикатов образуются формулы или правила (9.1), в которых слову "и" соответствует связка , а словам "Если..., то" - связка .

Вид существа определяет наличие или отсутствие у него перечисленных свойств. Если это существо синица, то она имеет крылья, а если этим существом является кролик, то, естественно, у него нет крыльев. Иначе говоря, фраза "синица имеет крылья", справедлива или истинна в русском языке, а фраза "кролик имеет крылья" ошибочна или ложна. В соответствии с этим предикат имеет_крылья(Синица) принимает истинное значение И, а предикат имеет_крылья(Кролик) - ложное Л. Слова Синица и Кролик в данном случае являются объектными константами. Подставляя значений объектных констант, имеем теперь возможность вычислять истинность или ложность формул (9.1).

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

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