Расширим понятия формулы, введя так называемые ограниченные кванторы. Допустим, что нам надо записать на языке логики предикатов следующее утверждение «для всякого x>5 существует y>0 такое, что xy=1». Отметим, что здесь написано не «для всякого x» и «существует y», а «для всякого x>5 « и «существует y>0 «. Если на это не обратить внимание, то получается формула ("x)($y)(xy=1) имеющая другой смысл, нежели исходное утверждение. Для правильного перевода надо немного изменить исходное предложение по форме (не меняя, разумеется, смысла): «для всякого x справедливо, если x>5, то существует y такой, что y>0 и xy=1». Правильный перевод имеет вид ("x)[x>5®($y)(y>0&(xy=1)].

Если рассматривать более длинные исходные предложения, то соответствующие им формулы логики предикатов будут, вообще говоря, довольно громоздкими. Для того, чтобы частично избавиться от усложнения при переводе на язык логики предикатов, вводятся ограниченные кванторы. Пусть B(x) – формула с одной свободной переменной x. Тогда выражение "B(x) называется ограниченным квантором общности $B(x) – ограниченным квантором существования. С помощью ограниченных кванторов исходное предложение предыдущего абзаца можно записать довольно просто: ("x>5)($y>0)(xy=1).

Более формально, ограниченные кванторы вводятся следующим образом: формула ("B(x)F(x) есть сокращение формулы ("x)B(x)®F(x)), формула ($B(x)F(x) – сокращение формулы ($B(x)&F(x)). Для ограниченных кванторов справедливы аналоги законов 22-33.

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

Ограниченные кванторы часто вводятся неявно. Для переменных, пробегающих множество истинности формулы B(x), вводят специальное обозначение. Например, в геометрии довольно часто применяется следующее соглашение: А, B, C, D,… обозначаются точки, буквами a, b, c, d,… прямые, а буквами a, b, g,… – плоскости, т.е. с нашей точки зрения первые пробегают множество истинности формулы T(x), вторые – Пр(x), третьи – Пл(x).

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

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

Рассмотрим информационную систему под условным названием «Сделки». Система содержит сведения о сделках купли-продажи, произведенных некоторой фирмой. Предметом сделок служат партии товаров, определяемые номером партии, наименованием товара, единицей измерения и количеством. Используются следующие атрибуты: HOM – номер партии товара, НАИМ – наименование товара, ЕД – единица измерения, КОЛ – количество единиц товара в партии, ДАТА – дата сделки, АГЕНТ – покупатель или продавец, СЕК – номер секции склада, СРОК – срок годности. Информация хранится в виде отношений: ПАР (НОМ, НАИМ, ЕД, КОЛ), ПОК (НОМ, ДАТА, АГЕНТ), ПРОД (НОМ, ДАТА, АГЕНТ), СКЛАД (СЕК, НОМ, СРОК). Первое отношение содержит сведения о партиях товара, которые были предметом сделок, второе – сведения о покупках, третье – о продажах партий товара. В четвертом указывается, в какой секции склада хранится купленная (но еще не проданная) партия товара и срок годности товара в партии. Система может вычислять отношение РАН(x,y)=«x раньше y», определенное на доменах атрибутов ДАТА и СРОК.

Формализуем эту информационную систему в многоосновной логике предикатов следующим образом. Введем восемь сортов переменных (по количеству атрибутов), для каждого атрибута – свой сорт. Переменные будут принимать значения в доменах соответствующих атрибутов. Другими словами, области интерпретации (основы) будут состоять из доменов атрибутов. Переменные по сортам синтаксически различать не будем. А для того, чтобы указать, что переменная x, например, изменяется по домену атрибута НАИМ, а y – по домену атрибута ЕД, будем писать: xÎНАИМ, yÎЕД. Каждому отношению поставим в соответствие предикат той же местности, что и отношения, с соответствующими типами переменных. Предикат и отношение будем обозначать одинаково. Например, отношению ПАР(НОМ, НАИМ, ЕД, КОЛ) будет соответствовать предикат ПАР(x, y, u, v), где xÎНОМ, yÎНАИМ, uÎЕД, vÎКОЛ. Сигнатура å, таким образом, будет содержать 5 символов предикатов:

å={ПАР(x, y, u, v), ПОК(x, y, z), ПРОД(x, y, z), СКЛАД(x, y, z), РАН(x,y)}.

В сигнатуру å можно добавлять константы, интепретируемые как элементы доменов атрибутов.

Эта формализация позволяет запросы к информационной системе представлять формулами логики предикатов указанной сигнатуры. Расмотрим следующий запрос:

Q₁. «Каковы номера партий товаров, купленных у фирмы b, и каково наименование товара в этих партиях?»

Запрашиваемая информация содержится в двух отношениях ПАР(НОМ, НАИМ, ЕД, КОЛ) и ПОК(НОМ, ДАТА, АГЕНТ), которые связаны номером партии товара, АГЕНТ – b. Если взять конъюнкцию предикатов

ПАР(x, y, u, v)&ПОК(x, z, фирма b),

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

F₁(x, y)=xÎНОМ&yÎНАИМ&($u ÎЕД)($zÎДАТА)[ПАР(x, y ,u, v)&ПОК(x, z, фирма b)]

Формула F₁(x,y) представляет собой перевод запроса Q₁ на язык многоосновной логики предикатов.

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

Q₂.»Каковы наименования товаров, единицы измерения и количество единиц в партиях товара, срок годности, которого истекает 20.03.01?»

Q₃. «Для каких фирм срок годности товара, купленного у этих фирм, истекает 20.03.01?»

Q₄. «Какой товар хранится на складе более, чем в двух партиях?»

Q₅. «Какие из закупленных партий товаров в последствии проданы?»

Эти на язык логики предикатов будут переведены формулами F₂ – F₅:

F₂(x,y,z)=xÎНАИМ&yÎЕД&zÎКОЛ&($uÎСЕК)($vÎНОМ)($wÎСРОК)

[ПАР(v,x,y,z)&СКЛАД(u,v,w)&РАН(w,20.03.01)],

F₃(x)=xÎАГЕНТ&("yÎНОМ)("zÎДАТА)("uÎСЕК)

("vÎСРОК)[ПОК(y,z,x)&СКЛАД(u,y,v)®РАН(v,20.03.01)],

F₄(x)=x xÎНАИМ&($y₁,y₂ÎНОМ)($z₁,z₂ÎЕД)($u₁,u₂ÎКОЛ)($v₁,v₂ÎСЕК)

($w₁,w₂ÎСРОК)[y₁¹y₂&ПАР(y₁,x,z₁,u₁)&СКЛАД(v₁,x,w₁)&

ПАР(y₂,x,z₂,u₂)&СКЛАД(v₂,x,w₂),

F₅(x)=xÎНОМ&($yÎНАИМ)($zÎЕД)($uÎКОЛ)($v₁,v₂ÎДАТА($w₁,w₂ÎАГЕНТ)

ПАР(x,y,z,u)&ПОК(x,v₁,w₁)&ПРОД(x,v₂,w₂) &РАН(v₁,v₂)].

Рассмотрим второй вариант выбора сигнатуры для формализации запросов Q₁ – Q₅. Для этого вначале к имеющимся восьми основам (доменам восьми исходных атрибутов) добавим девятую основу: множество сделок СДЕЛ. Далее, вместо предикатов ПАР(x,y,u,v), ПОК(x,y,z), ПРОД(x,y,z), СКЛАД(x,y,z) введем функции:

наим : НОМ®НАИМ,

ед : НОМ®ЕД,

кол : НОМ®КОЛ,

сдел : СДЕЛ®НОМ,

тип : СДЕЛ®{пок, прод},

дата : СДЕЛ®ДАТА,

агент : СДЕЛ®АГЕНТ,

сек : НОМ®СЕК,

срок : НОМ®СРОК,

а предикат РАН(x,y) оставим. Функции имеют естественный смысл: Например, функция наим номеру партиии товара ставит в соответствие наименование товара в этой партии, функция сдел ставит в соответствие сделке номер партии товара, относительно которого эта сделка была заключена. Новую сигнатуру будем обозначать буквой D. К сигнатуре D, как и к å, можно добавлять константы. Тогда запросы Q₁ – Q₅ будут переведены следующим образом:

G₄(x,y)=xÎНОМ&yÎНАИМ&y=наим(x)&(($zÎСДЕЛ)

[x=сдел(z)тип(z)=пок&агент(z)=фирма b,

G₂(x,y,z)=xÎНАИМ&yÎЕД&zÎКОЛ&

($uÎНОМ)[x=наим(u)&y=ед(u)&z=кол(u)&РАН(срок(u),20.03.01)],

G₄(x)=xÎНАИМ&($u₁,u₂ÎНОМ)[$v₁,v₂ÎСЕК)[u₁¹u₂&сек(u₁)=v₁&сек(u₂)=v₂],

G₅(x)=xÎНОМ&($v₁,u₂ÎСДЕЛ)[x=сдел(u₁)&x=сдел(u₂)&тип(u₁)=

пок&тип(u₂)=прод&РАН(дата(u₁), дата(u₂))].

Сигнатуру å можно назвать «реляционной» (или «предикатной»), а D – «функциональной». Разумеется возможны и другие варианты выбора сигнатуры.