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

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

Например, в рассуждении «Всякий ромб – параллелограмм; ABCD – ромб; следовательно, ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании, а предикат – это то, что утверждается о субъекте. Логи­ка предикатов – это расширение логики высказываний за счет использова­ния предикатов в роли логических функций.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Определение 1. Одноместным предикатом Р (х) на­зывается всякая функция одного переменного, в кото­рой аргумент x пробегает значения из некоторого мно­жества M, а функция при этом принимает одно из двух значений: истина или ложь.

Множество M, на котором задан предикат, называ­ется областью определения предиката.

Множество , на котором предикат принима­ет только истинные значения, называется областью ис­тинности предиката Р (х).

Так, предикат P (x) – «х – простое число» определён на множестве N, а множество для него есть множество всех простых чисел.

Определение 2. Предикат Р (х), определённый на множестве M, называется тождественно истин­ным (тождественно ложным), если .

Определение 3. Двухместным предикатом P (x,у)называется функция двух переменных х и у, определённая на множестве М = М ₁× М ₂ и принимающая значения из множества {1,0}.

В качестве примеров двухместных предикатов можно назвать предикаты: Q (x,у) – «х = у» предикат равенства, определённый на множестве R ²= R × R; F (x,у) – «х || у» прямая х параллельна прямой у, опредёленный на множестве прямых, лежащих на данной плоскости.

Аналогично определяется n -местный предикат.

Говорят, что предикат Р (х) является следствием предиката Q (х) , если ; и предика­ты Р (х) и Q (х) равносильны , если .

Приведём примеры к изложенному материалу.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истин­ности, если M= R для одноместных предикатов и M = R×R для двухместных предикатов:

1) х + 5 = 1;
2) при х = 2 выполняется равенство х ² – 1 = 0;
3) х ² – 2 х + 1 = 0;
4) существует такое число х, что х ³ – 2 х + 1 = 0;
5) х + 2 < З х – 4;
6) однозначное неотрицательное число х кратно 3;
7) (х + 2) – (3 х – 4);
8) х ² + у ² > 0.

Решение. 1) Предложение является одноместным предикатом Р (х), I_P = {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р (х), I_P = {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение является одноместным предикатом Р (х), I_P = (3; +∞);
6) предложение является одноместным предикатом Р (х), I_P = {0; 3; 6; 9};
7) предложение не является предикатом;
8) предложение является двухместным предикатом Q (х,y), I_Q = R×R \ {(0,0)}.

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

Решение. Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенную между ветвями параболы х = у ², она изображена серой частью рисунка: