5. Предикаты и кванторы.

Переменные x, y, …, которых служат для обозначения элементов множества X, называются переменными или предметными переменными, определенными на множестве X.

Определение 5.1. Предикатом (n  местным предикатом) называется предложение, содержащее n предметных переменных, определенных на одном или различных множествах, и которое превращается в высказывание истинное или ложное, если мы заменим предметные переменные их значениями.

n  местный предикат P, содержащий переменные x₁, x₂, …, x_n, определенные соответственно на множествах M₁, M₂, …, M_n, обозначается также символом P(x₁, x₂, …, x_n). Если x₁ = a₁ M₁, x₂ = a₂ M₂, …, x_n = a_n M_n,то через P(a₁, a₂, …, a_n) обозначаем значение предиката.

Отметим, что сам предикат высказыванием не является, но каждое значение предиката высказывание. Так как в логике нас не интересует содержание высказывания, то можно сказать, что предикат принимает два значения 1 и 0, где 1 обозначает "истинное высказывание", 0  " ложное высказывание".

Определение 5.2. Областью истинности предиката P называется множество, обозначаемое ОИ(P) и состоящее из всех значений переменных (a₁, …, a_n)M₁ … M_n, при которых предикат P принимает значение 1:

ОИ(P) ={(a₁, …, a_n)M₁ … M_n P(a₁, a₂, …, a_n) =1}.

Область истинности одноместного предиката, определенного на R удобно изображать на числовой прямой, а двуместного предиката, определенного на R² изображают на координатной плоскости xOy.

Пример 1. Пусть P(x) = [x  простое число]  одноместный предикат, определенный на N. Тогда P(1) = 0, P(2) = 1, P(4) = 0.

5.2. Пусть Q(x) = [ x  <1]  предикат, определенный на R. Тогда ОИ(Q) = (1, 1).

5.3. Пусть R(x, y) = [x² + y²  4]  двуместный предикат, определенный на R², для которого ОИ(R) изображена на рис. 21.

Некоторые, часто встречающиеся, предикаты обозначаются специальными символами. Например, x < y ("x меньше y"); x = y ("x равно y"); A  B ("A включено в B").

Так как принимают значения 1(истинно), 0 (ложно), то к ним применимы все логические операции над высказываниями. Поэтому, если P , Q  предикаты, то P  Q , P  Q , P  Q , P  Q , P , Q также есть предикаты.

Теорема 5.1. Пусть предикаты P и Q, определенные на одном и том же множестве. Тогда

1. ОИ(P  Q) = ОИ(P)ОИ(Q); 2. ОИ(P  Q) = ОИ(P)ОИ(Q);

3. ОИ(P  Q) = С_M(ОИ(P))  ОИ(Q); 3. ОИ(P) = С_M(ОИ(P)) .

Доказательство. Докажем равенство 1.

Пусть aОИ(P  Q). Тогда по определению 5.2 и по определению конъюнкции P(a) = 1 и Q(a) = 1. Следовательно, по определению 5.2 aОИ(P) и aОИ(Q) и по определению пересечения aОИ(P)  ОИ(Q).

Аналогично доказывается, что, если aОИ(P)ОИ(Q), то aОИ(PQ). Откуда по определению равенства множеств следует доказываемое равенство.

Определение 5.3. Предикаты P и Q, определенные на одном и том же множестве называется равносильными, обозначается P  Q, если ОИ(P) = ОИ(Q).

Определение 5.4. Предикат Q называется следствием предиката P, если ОИ(P)  ОИ(Q).

Например, предикаты [ x  1] и [x²  1], определенные на R, равносильны, а предикат [x² > 1]  следствие предиката [x > 1].

Замечание 5.1. С точки зрения логики предикатов имеем.

1. Всякое уравнение или неравенство есть предикат; система уравнений или неравенств  конъюнкция предикатов; совокупность уравнений или неравенств  дизъюнкция предикатов.

2. Множество решений уравнения или неравенства, система (совокупности) уравнений или неравенств  область истинности некоторого предиката.

3) Равносильные уравнения или неравенства, системы (совокупности) уравнений или неравенств  равносильные предикаты.

Определение 5.5. Пусть P(x)  одноместный предикат, определенный на множестве M.

1. Символ (xM)P(x) или x P(x) обозначает высказывание, которое истинно тогда и только тогда, когда ОИ(P) = M ,т.е., когда высказывание P(x) истинно для каждого xM.

2. Символ (xM)P(x) или x P(x) обозначает высказывание, которое истинно тогда и только тогда, когда ОИ(P)   ,т.е., когда высказывание P(x) истинно хотя бы для одного xM.

Символы  и  называются соответственно кванторами общности и существования. Выражение (xM)P(x) читается "для любого xM P(x)", выражение (xM)P(x)  "существует такое xM, что P(x)". Про переменную x говорят, что она связана квантором. Если известно, о каком множестве идет речь, то кванторы можно записывать так xP(x), xP(x)

Например, для предикатов Q(x) = [ x²  0], R(x) = [ x² < 0 ], P(x) = =[x  простое число], определенный на Z, имеем xQ(x)=0, xQ(x)=1, xP(x)=0, xP(x)=1, xR(x)=0, xR(x)=0,

Соединяя высказывания и предикаты операциями алгебры высказываний и кванторными операциями, мы получим формулы логики предикатов. Например, AP(x). x(P(x)Q(x)). Аналогично тому, как это сделано в алгебре высказываний можно ввести понятие формулы и равносильности формул в алгебре предикатов.

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

Теорема 5.2. Пусть P(x) и Q(x)  произвольные предикаты, определенные на множестве М. Тогда справедливы равносильности:

1. x P(x) x Q (x)  x (P(x)  Q (x)),

1. x P(x)  x Q (x)  x (P(x)  Q (x)),

2. (x P(x))  x(P(x)), 2. (x P(x))  x(P(x))

(Формулы А. де Моргана).

Доказательство. Докажем равносильность 2.

Пусть (x P(x))  истинно. Тогда высказывание x P(x)  ложно и по определению 5.5 ОИ(P) =. По теореме 5.1 ОИ(P) = =С_M(ОИ(P))= С_M=M и по определению 5.5 x(P(x))  истинно.

Пусть (x P(x))  ложно. Тогда высказывание x P(x)  истинно и по определению 5.5 ОИ(P)  . По теореме 5.1 ОИ(P) = =С_M(ОИ(P))  M и по определению 5.5 x(P(x))  ложно.

Из доказанного следует равносильность 2.

10