3.1. Синтаксис и семантика

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

Рис. 3.1. Синтаксис логики предикатов в метаязыке Бэкуса-Наура

3.1.1. Объектные переменные

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

3.1.2. Функции

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

3.1.3. Объектные константы

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

3.1.4. Термы

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

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

3.1.5. Предикатный символ

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

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

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

3.1.6. Атомы

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

3.1.7. Кванторы

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

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

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

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

Смысл квантора общности V совпадает с выражением естественного языка “Для всех...”. Множество формул (3.1) логики высказываний эквивалентно одной формуле (3.2) логики предикатов, т.е имеет место

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

3. Вернемся к примеру со средой чудовища. Во второй главе для того, чтобы выразить знания о наличии чудовища в ячейках, соседних ячейке с координатами если в ней ощущается зловоние, было введено 16 формул (2.5), в которых индексы пробегают множество значений от 1 до 4. Вместо этих 16 формул с помощью квантора общности можно записать одну формулу, помня, что теперь вместо логических переменных используются предикаты, а индексы стали числовыми объектными переменными:

На естественном языке высказывание, соответствующее этой формуле, звучит так: всех ячеек с координатами справед ливо: если ощущается зловоние в ячейке с координатами то существует ячейка, соседняя ячейке с

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

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

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

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

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

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

3.1.8. Равенство

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

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

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

Таблица 3.1 (см. скан)

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

Формула (3.7) с отрицанием равенства, наоборот, будет истинна при различных значениях координат (3,1)

3.1.9. Аксиомы, теоремы, факты и цели

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

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

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

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

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