Основы логики предикатов и логического вывода

Предикаты

Логика высказываний оперирует с атомами. Атомы являются абстракциями простейших повествовательных предложений, которые могут быть истинными или ложными. Атом рассматривается как неделимое целое, его структура не анализируется. Таким образом, аппарат, подходы и результаты логики высказываний могут быть применены только к очень узкому классу ситуаций - самых простых рассуждений на естественном языке.

В естественном языке встречаются и более сложные повествовательные предложения, истинность которых может меняться при изменении объектов, о которых идет речь, хотя структура предложений не меняется. Например, предложение “Джон любит Мэри” может быть истинным, а предложение “Джон любит Мэгги” ложным. В логике такие предложения, истинность которых зависит от параметров, абстрагируют с помощью предикатов. Например, предикат Любит(х,у) на паре <Джон, Мэри> может принимать значение истина, а на паре <Джон, Мэгги> - ложь. На латыни слово “предикат” (praedicatum) означает “сказуемое”, т.е. то, что в элементарном суждении утверждается о субъекте этого суждения, т.е. свойства этого оюъекта. Например, высказывание “Собака имеет хвост” истинно, “Лошадь имеет хвост” истинно, а “Человек имеет хвост” ложно. Поэтому заменив субъект в суждении переменной x, получим некую форму “х имеет хвост”, которая является функцией от х и принимает значения истинно для одних субъектах-аргументах этой функции и ложно для других. Формализация подобной высказывательной формы и называется предикатом, т.е. функцией, принимающей истинностные значения (истина либо ложь) и определенной на произвольной области изменения своей переменной; n-местный предикат является естественным обобщением функции одной переменной.

Определение 2.7. n-местным предикатом Р(х₁,...,х_n) называется функция Р: Мⁿ®{True, False}, определенная на наборах длины n элементов некоторого множества М и принимающая значения в области истинностных значений (рис.2.3, а). ÿ

Множество М называется предметной областью предиката, а х₁,...,х_n - предметными переменными. Пусть М - множество натуральных чисел и n = 2. Двуместный предикат Р(х,у): х³у+3 истинен на парах <25,1> и <15,12> и ложен на паре <1,1>. Поскольку предикат каждому элементу множества Мⁿ ставит в соответствие True илиFalse, то можно считать, что предикат выделяет на Мⁿ некоторое подмножество, на котором он истинен (рис.2.3, б). Таким образом, предикат на М может характеризовать (задавать) некоторое подмножество элементов М, а именно тех, на которых он истинен.

Предикаты могут быть связаны логическими связками, например, Р(х,у) ÚØQ(х,у). Рассмотрим формулу РÞQ. Она принимает истинное значение на тех аргументах, на которых предикат Р ложен или же предикат Q истинен. Очевидно также, что если на каждом элементе множества Мⁿ , на котором предикат Р истинен, предикат Q тоже истинен, формула РÞQ общезначима. Таким образом, формула РÞQ общезначима тогда и только тогда, когда множество истинности предиката Р является подмножеством множества истинности предиката Q, или, что то же, предикат P сильнее предиката Q, как это показано на рис.2.3, в).

Рис.2.3. Графическое представление предикатов

В качестве аргументов предикатов можно использовать и функции, принимающие значения из предметной области. Например, функция Отец(х) пусть абстрагирует предложение естественного языка “Отец человека по имени х”. Тогда Любит(Отец(Отец(х)),у) - тоже предикат, он будет принимать истинное значение на паре <Мэри, Джон>, если дедушка Мэри действительно любит Джона.

Итак, в отличие от логики высказываний, в которой структура простейших утверждений не анализируется (они там называются атомами), в логике предикатов атомный предикат имеет структуру.

Определение 2.8. Термом будем называть переменную или константу предметной области М, или функцию, принимающую значения в предметной области. Атомный предикат - это n-местная функция F(t₁,...,t_n), принимающая значение в множестве {True, False}, где t_i - термы. ÿ

Введем понятие формулы - комбинации простейших утверждений.

Определение 2.9. Правильно построенные формулы (ППФ) логики предикатов - это комбинация атомных предикатов и констант с логическими связками. Они определяются рекурсивно над множеством атомных предикатов с помощью символов операций (связок) Ø, Þ, скобок и одной дополнительной связки ", которая читается “для всех”. Рекурсивно ППФ определяются так:

1. Логические константы True, False есть формулы.

2. Атомный предикат есть формула.

3. Если Р - формула, то Ø(Р) тоже формула.

4. Если Р, Q - формулы, то (PÞQ) - тоже формула.

5. Если Р - формула, то ("х)Р тоже формула.

6. Никаких других формул в логике предикатов нет.

Фактически, добавлением в логике предикатов по сравнению с логикой высказываний является то, что предикаты обычно не имеют фиксированного истинностного значения, их истинность различна для разных значениях их аргументов. В качестве единственной новой логической связки в логике предикатов используется связка ".

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

PÚQ для (ØP)ÞQ,

P&Q для Ø(Ø(P)Ú(ØQ)),

PÛQ для (PÞQ)&(QÞP),

($х)Р для Ø(("х)ØP). ÿ

Новые логические связки " - “для всех” и $ - “существует” называются кванторами: " - “квантор всеобщности” и $ - “квантор существования”. Формула ("х)Р(х) читается так: “Для всех х выполняется Р(х)”. Очевидно, что это уже не предикат, это константа True либо False, в зависимости от того, действительно ли для каждого элемента х предметной области высказывание Р(х) истинно. Аналогично, логической константой является ($х)Р(х), что читается так: “Существует такое х, что для него выполняется Р(х)”. Для конечной предметной области значения этих связок очевидны. Пусть на М={x₁,x₂,...,x_n} определен произвольный предикат Р(х). Тогда очевидно:

("х)Р(х) = Р(х₁)&Р(х₂)&...&Р(х_n)=&_хÎМР(х);

($х)Р(х) = Р(х₁)ÚР(х₂)Ú...ÚР(х_n) =Ú_хÎМР(х).

Пример 2.9. Пусть Р(х) - предикат, определенный на множестве всех людей и означающий “х является студентом”. Тогда ("х)Р(х) ложно, а ($х)Р(х) истинно. Формула ("х) Любит(х, Отец(Отец(Джон))) истинна, если все любят дедушку Джона, а формула ($х)[Р(х)ÞØЛюбит(Отец(Джон), х)] истинна, если отец Джона не любит хотя бы одного студента. Далее, если R(x,y) - предикат, определенный на множестве всех семейных людей и означающий “х и у - супруги”, то ("х)($y)R(х,y) ¹ ($y)("х)R(х,y). Первая формула истинна, вторая - ложна. ÿ

Свободные и связанные переменные. Область действия переменной, указанной в кванторе, если она не очевидна, определяется скобками, например:

G(x,z) = ("t)[Р(t,z)Ú("u)($y)Q(t,y,u)]Þ("r)R(x,r).

Переменная связана, если она находится в области действия квантора. Связанные переменные можно заменять, если это не приводит к изменению смысла формулы. Например, предыдущая формула эквивалентна такой: G(x,z) = ("х)[Р(х,z)Ú("z)($y)Q(x,y,z)]Þ("z)R(x,z).

Интерпретации. Формула логики предикатов является только схемой высказывания. Формула имеет определенный смысл, т.е. обозначает некоторое высказывание естественного языка, если существует какая-либо ее интерпретация. Интерпретировать формулу - это значит связать с ней непустое множество М (конкретизировать предметную область), а также указать соответствие:

- каждой предметной константе конкретный элемент из М;

- каждой n-местной функциональной букве в формуле конкретную n-местную функцию на М;

- каждой n-местной предикатной букве в формуле конкретное отношение между n элементами области интерпретации М. На каждой интерпретации формула логики предикатов должна принять конкретное значение, Trueили False.

Рассмотрим, например, элементарную формулу G(f(a,b),g(a,b)) и следующую ее интерпретацию:

- М - множество действительных чисел;

- а, b - числа 2 и 3 соответственно;

- f - функция сложения аргументов;

- g - функция умножения аргументов;

- G - отношение "не меньше".

При такой интерпретации приведенная формула обозначает высказывание: "сумма 2+3 не меньше произведения 2*3", что неверно. Следовательно, G(f(a,b),g(a,b)) на этой интерпретации равна False. На измененной интерпретации, когда в качестве а и b мы выберем 2 и 1, G(f(a,b),g(a,b))=True.

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

Эквивалентности логики предикатов.

(а) Комбинация кванторов:

1. ("х)("y)P(х,y) = ("y)("х)P(х,y);

2. ($х)($y)P(х,y) = ($y)( $х)P(х,y);

3. ("х)($y)P(х,y) ¹ ($y)("х)P(х,y).

Свойства (а) 1 и 2 аналогичны свойствам коммутативности дизъюнкции и конъюнкции. Свойство 3 доказано в примере 2.9. Оно говорит о том, что перестановка местами кванторов существования и общности меняет смысл высказывания, а в общем случае, конечно, и значение его истинности.

(б) Комбинация кванторов и отрицаний:

1. Ø("х)P(х) = ($х)ØP(х);

2. Ø($х)P(х) = ("х)ØP(х).

Свойства (б) непосредственно следуют из определения квантора $. Это аналог теорем де Моргана.

Пример 2.10.Афоризм Козьмы Пруткова“Нет столь великой вещи, которую не превзошла бы величиною еще большая …” ([П82]) формально в виде предиката может быть записан так: Ø($хØ$уР(у,х) ), где х и у принимают значения в множестве всех вещей, а утверждение Р(а,b) означает “Вещь а превосходит величиной вещь b”. Этот предикат эквивалентен такому: ("х$уР(у,х) ), что дает эквивалентную формулировку этого афоризма, менее замысловатую: “Для любой вещи всегда найдется большая”. ÿ

(в) Расширение области действия кванторов (Q не зависит от х):

1. ("х)P(х)ÚQ = ("х)[P(х)ÚQ];

2. ($х)P(х)ÚQ = ($х)[P(х)ÚQ];

3. ("х)P(х)&Q = ("х)[P(х)&Q];

4. ($х)P(х)&Q = ($х)[P(х)&Q].

Эти свойства являются следствием свойств коммутативности и дистрибутивности дизъюнкции и конъюнкции.

(г) Расширение области действия кванторов (Q зависит от х):

1. ($х)P(х)Ú($х)Q(x) = ($х)[P(х)ÚQ(x)];

2. ("х)P(х)&("х)Q(x) = ("х)[P(х)&Q(x)];

3. ($х)[P(х)&Q(x)] Þ ($х)P(х)&($х)Q(x);

4. ("х)P(х)Ú("х)Q(x) Þ ("х)[P(х)ÚQ(x)].

Свойства (г) 2 и 4 являются следствием свойств 1 и 3 и выводятся с применением теоремы де Моргана. Свойство 1 иллюстрируется следующим высказыванием, обе части которого эквивалентны: “Среди нас есть английский шпион, или же среди нас - японский шпион. Да, в наши ряды затесался английский или японский шпион.”. Свойство 2 иллюстрирует следующее высказывание, обе части которого, очевидно, тоже эквивалентны: “Все - летчики, и все - герои. Каждый - и летчик, и герой”. Высказывание: “Есть у нас комсомолки, спортсменки, красавицы” более сильное, чем высказывание: “Есть у нас комсомолки, есть и спортсменки, есть и красавицы”, потому что второе не обязательно означает, что перечисленными качествами: “быть комсомолкой, спортсменкой и красавицей” обладает одно лицо (свойство 3).

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

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

Простейшие примеры ограниченных предикатов - ("хÎХ)Р(х) и ($хÎХ)Р(х), что имеет смысл: “для всех х, принадлежащих множеству Х, справедливо Р(х)” и “существует такое х, принадлежащее множеству Х, для которого справедливо Р(х)”. Очевидно, что предикат ("хÎХ)Р(х) эквивалентен ("х) (хÎХ)ÞР(х) и ($хÎХ)Р(х) эквивалентен ($х)(хÎХ)&Р(х).

Более общо, иногда удобно записывать предикаты относительно объектов, удовлетворяющих дополнительному условию, например: ("х: R(x))Р(х) и ($х: R(x))Р(х). Первое из них читается: “для любого х, удовлетворяющего условию R(x), справедливо Р(х)”, а второе: “существует х, удовлетворяющее условию R(x), для которого справедливо Р(х)”. Эти ограниченные предикаты эквивалентно можно представить: ("х: R(x))Р(х) º ("х) R(x)ÞР(х) и ($х: R(x))Р(х) º ($х) R(x)&Р(х). ÿ.

Теорема 2.7. Для ограниченных предикатов выполняются законы де Моргана:

Ø("хÎХ)Р(х) = ($хÎХ)ØР(х);
Ø($хÎХ)Р(х) = ("хÎХ)ØР(х);
Ø("х: R(x))Р(х) = ($х: R(x))ØР(х);
Ø($х: R(x))Р(х) = ("х: R(x))ØР(х).

Доказательство этой теоремы остается в качестве упражнения (задача 2.23).ÿ

Пример 2.11.Формальным выражением того факта, что массив х₁, х₂,..., х_n упорядочен по возрастанию, является предикат ("iÎ{1,...,n-1}) х_i£х_i+1, что словесно звучит так: “Любой последующий элемент массива не больше предыдущего элемента”. Выразим формально отрицание этого факта, т.е. утверждение, что этот массив не упорядочен по возрастанию:

Ø("iÎ{1,...,n-1}) х_i£х_i+1 º ($iÎ{1,...,n-1})Ø(х_i£х_i+1) º ($iÎ{1,...,n-1})х_i>х_i+1.

Таким образом, противоположное утверждение звучит так: “Существует пара соседних элементов массива, из которых последующий меньше предыдущего”. ÿ

Пример 2.12. Определение достижимого состояния конечного автомата записывается так: “Состояние s конечного автомата является достижимым тогда и только тогда, когда существует такая входная цепочка, что под ее воздействием автомат переходит в это состояние из начального состояния s₀”. В виде предиката это записывается короче: Достижимо(s)Û($aÎX^*)d^*(s₀,a)=s. Исходя из этого определения, определим понятие недостижимого состояния конечного автомата. В виде предиката это записывается так: Недостижимо(s)ÛØ[($aÎX^*)d^*(s₀,a)=s]. Отсюда: Недостижимо(s) Û("aÎX^*) Ø[d^*(s₀,a)=s] или, что то же: Недостижимо(s)Û("aÎX^*)d^*(s₀,a)¹s. В словесной формулировке: “Состояние s конечного автомата недостижимо тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние из начального состояния s₀” .ÿ

Пример 2.13. Существует теорема p»_k+1q Û ("хÎХ) [d(p,х) »_k d(q,х) & l(p,х) = l(q,х)] (здесь p»_kq обозначает утверждение “состояние p k-эквивалентно состоянию q”, а Øp»_kq обозначает утверждение “состояния p и q k-различимы”. Доказательство необходимости состоит в том, что нужно показать p»_k+1q Þ ("хÎХ) [d(p,х) »_k d(q,х) & l(p,х) = l(q,х)]. Доказательство этого более простого утверждения проводится от противного, т.е. доказывается его контрапозиция: ($хÎХ)[Ød(p,х)»_kd(q,х)Úl(p,х)¹l(q,х)]ÞØp»_k+1q. Из свойств предикатов легко показывается, что эта формула эквивалентна конъюнкции двух утверждений: ($хÎХ)[Ød(p,х)»_kd(q,х)]ÞØp»_k+1q и ($хÎХ)[l(p,х)¹l(q,х)]ÞØp»_k+1q. Словами это можно сказать так: “Если существует такой элемент х из Х, что состояния d(p,х) и d(q,х) k-различимы, то р и q являются k+1- различимыми” и: “Если существует такой элемент х из Х, что l(p,х) не равно l(q,х), то состояния р и q являются k+1- различимыми”.ÿ