2.3.1 Предикаты

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

В естественном языке встречаются и более сложные повествовательные предложения, истинность которых может меняться при изменении объектов, о которых идет речь, хотя структура предложений не меняется. Например, предложение “Джон любит Мэри” может быть истинным, а предложение “Джон любит Мэгги” ложным. В логике такие предложения, истинность которых зависит от параметров, абстрагируют с помощью предикатов. Например, предикат Любит(х,у) на паре <Джон, Мэри> может принимать значение истина, а на паре <Джон, Мэгги> - ложь. На латыни слово “предикат” (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)(X^*)^*(s₀,)=s. Исходя из этого определения, определим понятие недостижимого состояния конечного автомата. В виде предиката это записывается так: Недостижимо(s)[(X^*)^*(s₀,)=s]. Отсюда: Недостижимо(s) (X^*) [^*(s₀,)=s] или, что то же: Недостижимо(s)(X^*)^*(s₀,)s. В словесной формулировке: “Состояние s конечного автомата недостижимо тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние из начального состояния s₀” . 

Пример 2.13. Существует теорема p_k+1q  (хХ) [(p,х) _k (q,х) & (p,х) = (q,х)] (здесь p_kq обозначает утверждение “состояние p k-эквивалентно состоянию q”, а p_kq обозначает утверждение “состояния p и q k-различимы”. Доказательство необходимости состоит в том, что нужно показать p_k+1q  (хХ) [(p,х) _k (q,х) & (p,х) = (q,х)]. Доказательство этого более простого утверждения проводится от противного, т.е. доказывается его контрапозиция: (хХ)[(p,х)_k(q,х)(p,х)(q,х)]p_k+1q. Из свойств предикатов легко показывается, что эта формула эквивалентна конъюнкции двух утверждений: (хХ)[(p,х)_k(q,х)]p_k+1q и (хХ)[(p,х)(q,х)]p_k+1q. Словами это можно сказать так: “Если существует такой элемент х из Х, что состояния (p,х) и (q,х) k-различимы, то р и q являются k+1- различимыми” и: “Если существует такой элемент х из Х, что (p,х) не равно (q,х), то состояния р и q являются k+1- различимыми”. 