Описание всех лабораторных работ (1006390), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

G=(y)[(P(a,y)Q(a, f(y)))&(P(a,y) )R(y))].

Многосортная логика

Расширим понятия формулы, введя так называемые ограниченные кванторы. Допустим, что нам надо записать на языке логики предикатов следующее утверждение «для всякого 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.

Ограниченные кванторы часто вводятся неявно. Для переменных, пробегающих множество истинности формулы B(x), вводят специальное обозначение. Например, в геометрии довольно часто применяется следующее соглашение: А, B, C, D,… обозначаются точки, буквами a, b, c, d,… прямые, а буквами , , ,… – плоскости, т.е. с нашей точки зрения первые пробегают множество истинности формулы 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₁. «Каковы номера партий товаров, купленных у фирмы , и каково наименование товара в этих партиях?»

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

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

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

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

Формула 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НАИМ&(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₂)].

Инструкция по установке и выполнению программы

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

ruby predicate.rb

Файлы исходных данных должны находиться в том каталоге, из которого происходит запуск программы.

Кодировка всех файлов должна быть UTF-8!

В файле query.txt задается формула логики предикатов в ПНФ.

Сначала задаются сорта переменных:

<имя переменной> @ <cорт>

Например:

x @ АГЕНТ

y @ НОМ

…

Далее кванторы (в порядке их появления в формуле!):

<квантор> <имя переменной>

Где квантор всеобщности это any, а существования exists. Например:

any y

exists z

Далее логическое выражение. Например:

(ПОК(y,z,x) and СКЛАД(u,y,v))->(v < '2010-12-31')

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

and - конньюнкция

or - дизьюнкция

not - отрицание

-> - импликация

<=> - эквиваленция.

<имя предиката>(<переменная>, …<переменная>) – предикат заданный таблично.

<переменная> <знак> <переменная>- двуместный предикат, где знак может быть >, <, >=, <=, ==, !=.

В формуле можно использовать константы. Значения констант должны быть заданы в одинарных кавычках.

В неатомарной формуле необходимо в обязательном порядке использовать скобки!

Файлы предикатов должны иметь расширение pr. Имя файла должно совпадать с именем соответствующего предиката.

В файле в первой строке задаются сорта предикатов через табуляцию, в остальных строках задаются комбинации значений переменных соответствующих истинному значению предикатов. Например, для файла ПОК.pr:

НОМ ДАТА АГЕНТ

1 2010-01-11 Рога и Копыта

2 2010-01-21 ИП Иванов

3 2010-01-13 Рога и Копыт0

Программа выводит полученную таблицу значений на экран. Для вывода в файл используется перенаправление вывода:

ruby predicate.rb > out.txt

Задачи для самостоятельной работы

1. Какой из кванторов определяется следующими выражениями: «для всякого x истинно F(x)», «F(x) при произвольном x», «найдется x, такой что F(x)», «для подходящего x верно F(x)»,»всегда имеет место F(x)», «каждый элемент обладает свойством F», «найдется, по крайней мере, один x такой, что F(x)», «существует не менее одного x, что F(x) «, «свойство F присуще всем», «каким бы ни был x F(x истинно», «хотя бы для одного x верно F(x) «.

2. Дана алгебраическая структура <N; xy>. Показать, что следующие предикаты определяются формулами сигнатуры =():

а) «x меньше y»,

б) «y равно x+1»,

в) «x равно 1»,

г) «x равно 2»,

д) «y лежит между x и z».

3. Дана алгебраическая структура <N; x|y>. Показать, что следующие предикаты определяются формулами сигнатуры =(|) (x|y означает, что x делит y нацело:

а) «x равно 1»,

б) «z есть HOD(x,y)»,

в) «z есть HOK(x,y)»,

г) «x – простое число»

Можно ли определить предикаты «x – четное число», «x меньше y» формулой этой же сигнатуры?

4. Пусть М – множество всех точек, прямых и плоскостей трехмерного пространства. Рассмотрим алгебраическую систему < M; xy, p(x), l(x), pl(x) >, где  – отношение принадлежности, p(x) означает, что x есть точка, I(x) – x есть прямая, pI(x) – x есть плоскость.

Выразить следующие предикаты формулами указанной сигнатуры:

а) «плоскости x и y имеют общую точку»,

б) «если плоскости x и y имеют общую точку, то они имеют общую прямую»,

в) «прямые x и y имеют общую точку»,

г) «прямые x и y параллельны»,

д) «прямые x,y и z образуют треугольник».

В формулах можно использовать ограниченные кванторы.

5. Подберите сигнатуру и представьте следующие рассуждения в виде последовательности формул логики предикатов.

5.1. Некоторые из первокурсников знакомы со всеми второкурсниками, а некоторые из второкурсников – спортсмены. Следовательно, ряд первокурсников знаком с некоторыми спортсменами.

5.2. Членом правления клуба может быть каждый совершеннолетний член клуба. Игорь и Андрей – члены клуба. Игорь – совершеннолетний, а Андрей старше Игоря. Следовательно, Андрей может быть членом правления клуба.

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

6. Будут ли равносильны следующие пары формул:

а) (x)(F(x)G(x)) и (x)F(x)(x)G(x);

б) (x)(F(x)&G(x)) и (x)F(x)&(x)G(x);

в) (x)(F(x)G(x)) и (x)F(x)(x)G(x);

г) (x)F(x) (x)G(x) и (x)(y)(F(x)G(y));

д)(x)(F(x)G(x)) и (x)F(x) (x)G(x);

Характеристики

Список файлов лабораторной работы