Математическая логика и теория алгоритмов

Алгоритм приведения к предваренной нормальной форме

Шаг 1. Используя законы логики исключить эквиваленцию и импликацию.

Шаг 2. Занести отрицание к атомарным формулам.

Шаг 3. С помощью законов 22-23, 28-31 вынести кванторы вперед, используя при необходимости переименование связанных переменных (законы 32-33).

 

Рассмотрим пример. Пусть

F=("x)P(x)®($y)("z)(P(y)&Q(y,z)).

Выполнив шаг 1, получим формулу

F₁=Ø("x)P(x)Ú($y)("z)(P(y)&Q(y,z)).

С помощью закона 26 перейдем к формуле

F₂=($x)ØP(x)Ú($y)("z)(P(y)&Q(y,z)).

Тем самым, шаг 2 также выполнен. Применим закон 30 слева  направо Q₁=$, Q₂=$, u=y, получим формулу

F₃=($x)($y)[ØP(x)Ú("z)(P(y)ÚQ(y,z))].

(Пользуемся  тем, что ØP(x) не содержит y, а ("z)(P(y)&Q(Y,z)) не содержит х. Так как формула ØP(x) не содержит z, то применение закона 26 слева направо дает формулу

F₄=($x)($y)("z)[ØP(x)ÚÚ(P(y)&Q(y,z))].

Это и есть искомая  формула, имеющая ПНФ и равносильная формуле F.

 

В предыдущем примере  выполнение шага 3 можно организовать по-другому. В формуле F₂ связанную переменную y заменим на переменную х (закон 33), получим формулу

F₃^/=($x)ØP(x)Ú($x)("z)(P(x)&Q(x,z)).

Используя закон 23, перейдем к формуле

F₄^/=($x)[ØP(x)Ú("z)(P(x)&Q(x,z))].

Затем, как и  в предыдущем абзаце, с помощью  закона 28 вынесем квантор по z за квадратную скобку. Получим формулу

F₅^/=($z)("z)[ØP(x)Ú(P(x)&Q(x,z)].

Формула F₅^/, как и формула F₄, имеет предваренную нормальную форму и равносильна формуле F. В некоторых ситуациях формула F₅^/ предпочтительнее формулы F₄, поскольку содержит меньше кванторов. (Кстати, бескванторную часть формулы F₅^/ можно упростить).

Перейдем к  изучению сколемовской нормальной формы. Отметим вначале, что в логике первого порядка понятие конъюнктивной нормальной формы вводится точно так же, как и в логике высказываний. Сохраняется полностью алгоритм приведения к КНФ и утверждение теоремы 1.3.

 

Определение. Формула G имеет сколемовскую нормальную форму (сокращенно: СНФ), если

G=("x)…("x_n)H,

где формула  Н не содержит кванторов и имеет  конъюнктивную нормальную форму.

Например, формула ("x)[P(x)Ú(P(y)&Q(x,y)] имеет сколемовскую нормальную форму, а формулы ("x)($y)Q(x,y), ("x)[P(x)&(P(y)ÚQ(x,y)] не имеют.

В отличие от предыдущего случая предваренной нормальной формы мы здесь вначале рассмотрим алгоритм приведения к СНФ, а затем  сформулируем теорему.

Алгоритм приведения к сколемовской нормальной форме

Шаг 1 – Шаг 3 – те же, что и в предыдущем алгоритме.

Шаг 4. Бескванторную часть привести к конъюнктивной нормальной форме.

Шаг 5. Исключить кванторы существования.

Этот шаг изложим  на примере. Пусть после выполнения четвертого шага имеем формулу

F=($x)("y)($z)("u)($v)H(x,y,z,u,v),

где Н – не содержит кванторов. Предположим, что  формула не содержит константы с, символов одноместной функции f и  двухместной функции g. Тогда в  формуле Н заменим х на с, z –  на f(y), v заменим на g(y,u). Все кванторы существования вычеркнем. Получим  формулу

G=("y)("u)H(c,y,f(y),u,g(g,u)).

Это и есть результат  выполнения шага 5.

Приведем пример приведения к СНФ. Пусть

F=($x)("y)[P(x,y)®($z)(Q(x,z)&R(y))].

Применяя закон 23, получаем формулу

F₁=($x)("y) )($z)[ØP(x,y)Ú(Q(x,z)&R(y))].

Она имеет предваренную нормальную форму. Приводим бескванторную часть к КНФ:

F₂=($x)("y) )($z)[ØP(x,y)Ú(Q(x,z)&(ØP(x,y)Ú(R(y))].

Сделаем подстановку x=a, z=f(y), получим искомую формулу

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,… прямые, а буквами 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ÎНАИМ&($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>. Показать, что следующие предикаты определяются формулами сигнатуры s=(£):

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

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

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

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

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

 

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