Перед тем как определить синтаксис правильных выражений в исчислении предикатов, определим алфавит и грамматику для создания символов языка. Это соответствует лексическому аспекту определения языка программирования. Символы исчисления предикатов, подобно лексемам в языке программирования, являются неприводимыми (минимальными) синтаксическими элементами: они не могут быть разбиты операциями языка на составляющие.
Мы представляем символы исчисления предикатов как строки букв и цифр, начинающиеся с буквы. Пробелы и неалфавитно-цифровые символы использовать нельзя, хотя символ подчеркивания (_) может использоваться для удобства чтения.
ОПРЕДЕЛЕНИЕ
СИМВОЛЫ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
Алфавит исчисления предикатов состоит из следующих элементов.
1. Набор букв английского алфавита как верхнего, так и нижнего регистра.
2. Набор цифр — 0, 1,..., 9.
3. Символ подчеркивания _.
Символы в исчислении предикатов начинаются с буквы, за которой следует последовательность перечисленных выше знаков.
Приведем пример допустимых знаков в алфавите исчисления предикатов.
aR69p_z Вот пример недопустимых знаков в алфавите исчисления предикатов.
К допустимым символам исчисления предикатов относятся следующие.
George f/геЗ tom_andjerry bill XXXX friends_of Приведем примеры строк, содержащих неразрешенные знаки.
3/ack "no blanks allowed" ab%cd ***71 duck\\\
Символы (или идентификаторы), как будет показано в подразделе 2.2.2, используются для обозначения объектов, свойств или отношений в области рассуждения. Как и в большинстве языков программирования, использование "слов", которые имеют зарезервированное значение, помогает понимать программный код. Например, выражения л(д,к) и любит(Джордж,Кейт) формально эквивалентны (т.е. имеют одинаковую структуру). Однако второй вариант может быть удобнее для понимания (людьми-читателями) смысла отношений, описанных этим выражением. Следует подчеркнуть, что такие подробные имена предназначены исключительно для улучшения удобочитаемости выражений. Единственное значение, которое может иметь выражение исчисления предикатов, — это значение, определяемое их формальной семантикой.
Круглые скобки, запятые (,) и точки (.) используются исключительно для правильного построения выражений и не обозначают объекты или отношения из области рассуждения. Они называются несобственными символами (improper symbol[А.Д.2] ).
Символы исчисления предикатов могут представлять переменные, константы, функции или предикаты. Константами называют определенные объекты или свойства из области рассуждения. Символьные константы должны начинаться со строчной буквы (буквы нижнего регистра). Таким образом, george, tree, tall и blue — примеры правильных символьных констант. Константы true (истина) и false (ложь) зарезервированы как символы истинности.
Идентификаторы переменных используются для обозначения общих классов объектов или свойств из области рассуждения. Переменные представляются идентификаторами, начинающимися с прописной буквы. Так, George, BILL и Kate — допустимые переменные, в то время как geORGE и bill — нет.
Исчисление предикатов также допускает существование функций для объектов из некоторой области рассмотрения. Идентификаторы функций (подобно константам) начинаются с символа нижнего регистра (строчной буквы). Функции обозначают отображение одного или нескольких элементов множества (называемого областью определения функции) в однозначно определяемый элемент другого множества (множества значений функции). Элементы определения и множества значений — это объекты из области рассмотрения. Помимо обычных арифметических функций, таких как сложение и умножение, функции могут определять отображения между нечисловыми областями.
Заметим, что наше определение символов исчисления предикатов не содержит чисел или арифметических операторов. Система счисления не включена в примитивы исчисления предикатов. Мы лишь аксиоматически определили "базовое" исчисление предикатов [Manna и Waldinger, 1985]. Его производные представляют теоретический интерес, но они менее важны в применении исчисления предикатов в качестве модели представления искусственного интеллекта. Для удобства включим арифметику в язык описания.
Каждый функциональный символ связан с арностью (arity), указывающей на количество параметров этой функциональной зависимости. Так, например, символ father мог бы обозначать функцию арности 1, которая позволяет определить отца, a plus мог бы быть функцией арности 2, которая отображает два числа в их арифметическую сумму.
Функциональное выражение — это идентификатор функции, за которым следуют его аргументы (или параметры). Аргументы — это элементы области определения функции. Число аргументов равно арности функции. Аргументы заключаются в круглые скобки и разделяются запятыми. Например,
f(X,Y)
father(david) price(bananas)
Все эти выражения являются правильно определенными функциональными выражениями.
Каждое функциональное выражение обозначает отображение аргументов в единственный объект множества значений, называемый значением функции. Например, если father— это унарная функция, то father(david) является функциональным выражением, значением которого (по желанию автора) есть george. Если plus — это функция арности 2, определенная на множестве целых чисел, то plus(2,3) является функциональным выражением, значением которого является целое число 5. Замена функции ее значением называется ее оцениванием (evaluation).
Понятие символа исчисления предикатов, или терма, формализовано следующим определением[А.Д.3] .
ОПРЕДЕЛЕНИЕ СИМВОЛЫ И ТЕРМЫ К символам исчисления предикатов относятся следующие.
1. Символы истинности true и false. Это зарезервированные символы.
2. Символы констант — это символьные выражения, начинающиеся с символа нижнего регистра (строчный символ).
3. Символы переменных — это символьные выражения, начинающиеся с символа верхнего регистра (прописной символ).
4. Функциональные символы — это символьные выражения, начинающиеся с символа нижнего регистра (строчный символ). С функциями связывается арность, указывающая на число их аргументов.
Функциональное выражение (function expression) состоит из функциональной константы арности л, за которой следуют п термов гьt2, ..., tn, заключенных в круглые скобки и отделенных друг от друга запятыми.
Терм исчисления предикатов может быть константой, переменной или функциональным выражением.
Таким образом, термом исчисления предикатов обозначают объекты и свойства из области определения данной задачи. Примеры термов:
cat
tlmes(2,3)
X
blue
motherljane)
kate
Символы в исчислении предикатов могут также представлять предикаты. Предикатные символы, подобно константам и именам функций, начинаются с буквы нижнего регистра. Предикат указывает на отношения между несколькими объектами (в том числе нулевым числом объектов) в мире. Количество объектов, связанных таким образом, определяет арность предиката. Примеры предикатов:
like equals on near part_of
Атомарное высказывание (атомарная формула) (atomic sentence), самая примитивная единица языка исчислений предикатов, является предикатом арности п, за которым следует п термов, заключенных в круглые скобки и разделенных запятыми. Вот примеры атомарных высказываний.
Символами предикатов в этих выражениях являются likes, friends и helps. Символ предиката может быть использован с различным числом аргументов. В этот пример включены два различных предиката likes, один из которых зависит от двух, а другой [А.Д.4] — от трех аргументов. Если символ предиката используется в предложениях с различной арностью, то считается, что он представляет два различных отношения. Таким образом, отношение предиката определяется его именем и арностью. Два отличных предиката likes могли бы составлять часть одного и того же описания мира; однако этого избегают, так как могут возникнуть недоразумения.
В приведенных выше примерах предикатов bill, george и kate являются постоянными символами и представляют объекты из области определения задачи. Аргументы предиката являются термами и могут также содержать переменные или функциональные выражения. Например,
frlends(father_of(david),father_of{andrew))
является предикатом, описывающим отношения между двумя объектами из области рассуждения. Аргументы здесь представлены как функциональные выражения, значения которых (будем считать, что father_of(david) есть george и father_of(andrew) есть alien) являются параметрами предиката. После оценки функциональных выражений представленное выше выражение примет вид.
fhends(george, alien)
Эти идеи формализованы в следующем определении.
ОПРЕДЕЛЕНИЕ
ПРЕДИКАТЫ И АТОМАРНЫЕ ПРЕДЛОЖЕНИЯ
Символы предиката — это символы, начинающиеся с символа нижнего регистра. Предикаты связаны с положительным целым числом, определяющим арность, или "число аргументов", предиката. Предикаты с одинаковым именем, но различной арностью считаются различными.
Атомарное предложение— это предикатная константа арности п, за которой следуют п термов ti, t2, —, tn, заключенных в круглые скобки и отделенных запятыми. Значения истинности true и false тоже являются атомарными предложениями.
Атомарные предложения также называются атомарными выражениями, атомами или предложениями.
Мы можем комбинировать атомарные предложения и формировать предложения в исчислении предикатов, используя логические операторы. Это те же самые логические связки, которые используются в исчислении высказываний
Л, V, -I, —> И =.
Переменная, встречающаяся в предложении в качестве параметра (аргумента), относится к неопределенным объектам в области определения. Исчисление предикатов первого порядка (подраздел 2.2.2) включает два символа: кванторы переменных (variable quantifier) V и 3. Они ограничивают значение предложения, содержащего переменную. За квантором следует переменная и предложение, как показано ниже.
ЗУ friends(Y, peter) VX likes(X, icejcream)
Квантор всеобщности V означает, что предложение истинно для всех значений переменной. В примере VX likes(X,ice_cream) выражение истинно для всех значений X в области определения X. Квантор существования 3 указывает, что предложение истинно[А.Д.5] по крайней мере для одного значения в области определения. Выражение 3/ friends( Y,peter) истинно, если имеется по крайней мере один объект Y, который является другом Питера. Более подробно кванторы рассматриваются в подразделе 2.2.2. Предложения в исчислении предикатов определены индуктивно.
ОПРЕДЕЛЕНИЕ
ПРЕДЛОЖЕНИЯ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ Каждое атомарное предложение есть предложение.
1. Если s — предложение, то его отрицание -в тоже является предложением.
2. Если S) и s2— предложения, то их конъюнкция Sias2тоже является предложением.
3. Если Sj и s2— предложения, то их дизъюнкция з^гтоже является предложением.
4. Если S] и s2— предложения, то их импликация я^вгтоже является предложением.
5. Если S] и s2 — предложения, то их эквивалентность Si=s2тоже является предложением.
6. Если X — переменная и s предложение, то VX s есть предложение.
7. Если X — переменная и s предложение, то ЭХ s есть предложение.
Далее следуют примеры правильно построенных предложений.
Пусть times (умножить) и plus (сложить) — символы функций арности 2 и пусть equal (равно) и foo являются предикатными символами арности 2 и 3 соответственно.
plus( two, three) (сложить два и три) — это функция, т.е. не атомарное предложение.
equal (plus(two,three), five) — это атомарное предложение.
equal{plus(2,3), seven) — это атомарное предложение. Заметим, что это предложение при стандартной интерпретации операций сложения и уравнивания является ложным. Формальная правильность и истинность значения — независимые понятия.
ЭХ foo{X,two,plus{two,three))Aequal(plus(two,three),five) — предложение, потому что оба конъюнкта являются предложениями.
(foo(two,two,plus(two,three)))->equal{plus{two,three),five)=true) — это предложение, потому что все его компоненты — предложения, связанные логическими операторами.
Определение предложений исчисления предикатов и приведенные примеры приводят к мысли о необходимости проверки: является ли выражение предложением. Метод такой проверки можно записать в виде рекурсивной функции verify_sentence, которая получает в качестве параметра рассматриваемое выражение и возвращает значение success (успех), если выражение является предложением.
function verify_sentence(expression); begin case
выражение является атомарным предложением: return SUCCESS; выражение имеет вид Q X s, где Q — либо V либо Э,а X — переменная, если verify_sentence(s) возвращает SUCCESS then return SUCCESS else return FAI1; выражение имеет вид —is:
if verify_sentence(s) возвращает SUCCESS[А.Д.6] then return SUCCESS else return FAll;
выражение имеет вид sxop s2, где op — бинарный логический оператор:
if verify_sentence(s1) возвращает SUCCESS и
verify_sentence(s2) возвращает SUCCESS then return SUCCESS else return FAIL; в остальных случаях: return FAIL end end.
В заключение этого раздела приведем пример использования исчисления предикатов. Рассмотрим модель простого мира. Рассматриваемая область определения — набор семейных отношений в библейской генеалогии.
mother{eve,abel)
mother(eve,cain)
father(adam,abel)
father(adam,cain)
VXW father(X, Y)vmother(X, Y)->parent(X, Y)
VXV WZ parent(X, Y)Aparent(X,Z)->sibling{Y,Z)
В этом примере для определения набора отношений родителей и детей использованы предикаты mother (мать) и father (отец). В терминах этих предикатов импликация дает общее определение других отношений, в том числе родительских и братских. Интуиция подсказывает, что импликацию можно использовать для описания братских отношений, например sibling(cain, abel). Для реализации этого процесса на компьютере необходимо его формализовать, т.е. определить алгоритмы вывода. При задании этих алгоритмов нужно соблюдать осторожность, поскольку они действительно должны выводить правильные заключения из данного набора утверждений исчисления предикатов. Для того чтобы это было именно так, вначале определим семантику исчисления предикатов (подраздел 2.2.2), а затем перейдем к правилам вывода (раздел 2.3).
