Файл: Matlog.doc

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

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

Все атрибутивные суждения можно разделить на следующие типы: "a есть P", "Все S есть P", "Ни один S не есть P", "Некоторые S есть P", "Некоторые S не есть P". Эти суждения следующим образом переводятся на язык логики предикатов:

"a есть P" – P(a);

"Все S есть P" – x(S(x)  P(x));

"Ни один S не есть P" – x(S(x)  P(x));

"Некоторые S есть P" – x(S(x) & P(x));

"Некоторые S не есть P" – x(A(x) & P(x)).

Полезно понять и запомнить следующее правило: если кванторная переменная связана квантором общности (), то в формуле используется знак импликации ( )а если кванторная переменная связана квантором существования (), то в формуле используется знак конъюнкции (&).

Пример 2.17.

Перевести на язык логики предикатов следующие суждения:

а) Веста – собака.

Заменим имя "Веста" символом "в" и введем предикат P(x) = "x – собака".

Наше суждение можно выразить формулой: P(в).

б) Всякая логическая функция может быть задана таблицей.

Введем предикаты S(x) = "x – логическая функция"; P(x) = "x может быть задана таблицей".

Наше суждение можно выразить формулой: x(S(x)  P(x)).

в) Ни один народ не хочет войны.

Введем предикаты S(x) = "x – народ"; P(x) = "x хочет войны".

Наше суждение можно выразить формулой: x(S(x)  P(x)).

г) Некоторые журналисты были в космосе.

Введем предикаты S(x) = "x – журналист"; P(x) = "x был в космосе".

Наше суждение можно выразить формулой: x(S(x) & P(x)).

д) Некоторые современники динозавров не вымерли.

Введем предикаты S(x) = "x – современник динозавров"; P(x) = "x вымер".

Наше суждение можно выразить формулой: x(A(x) & P(x)).

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

Пример 2.18.

Суждение “Некоторые студенты сдали все экзамены” записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.

Введем предикаты: A(x) = “x – студент”; B(y) = “y – экзамен”, C(x, y) = ”x сдал экзамен y”. Тогда предложение “Некоторые студенты сдали все экзамены” можно записать в виде следующей формулы:

xy(A(x)&B(y)  C(x, y)).

Построим отрицание этой формулы, применяя равносильные преобразования:

xy(A(x)&B(y)  C(x, y))) xy((A(x)&B(y)  C(x, y)) xy(A(x)&B(y)& C(x, y)).

Это предложение можно прочитать следующим образом:

“Каждый студент не сдал хотя бы один экзамен”.

Язык логики предикатов удобен для записи математических предложений: определений, теорем, необходимых и достаточных условий (см., например [5]).

Пример 2.19.

Записать на языке логики предикатов следующее определение предела числовой последовательности: "Число a является пределом числовой последовательности {a_n}, если для любого положительного числа  существует такой номер n₀, что для всех натуральных чисел n, больших или равных n₀, справедливо неравенство: |a_n - a| < ".

Введем предикаты: P() = " > 0"; Q(n) = "n – натуральное число"; R(n, n₀) = "nn₀"; S(n, ) = "|a_n - a| < ".

Определение предела последовательности может быть записано следующей формулой:

n₀n(P()&Q(n)&Q(n₀)&R(n, n₀)  S(n, )).

Пример 2.20.

Записать в виде формулы логики предикатов великую теорему Ферма (была доказана в 1996 г. Э. Вайлсом (Andrew Wiles)): "Для любого целого n > 2 не существует натуральных чисел x, y, z, удовлетворяющих равенству: xⁿ + yⁿ = zⁿ".

Введем предикаты: N(x) = "x – натуральное число"; M(x) = "x > 2"; P(x, y, z, n) = "xⁿ + yⁿ = zⁿ".

Для любых чисел x, y, z, n условие (посылка) теоремы Ферма есть конъюнкция N(x)&N(y)&N(z)&N(n)&M(n), а заключение есть P(x, y, z, n). Поэтому теорема Ферма формулируется следующим образом:

xyzn(N(x)&N(y)&N(z)&N(n)&M(n)  P(x, y, z, n)).

Если теорема имеет вид x(P(x)  Q(x)), то предикат Q(x) является следствием предиката P(x). При этом предикат Q(x) называется необходимым условием предиката P(x), а предикат P(x) – достаточным условием предиката Q(x).

Пример 2.21.

Запишем в виде формулы логики предикатов утверждение: "Если число делится на 6, то оно делится на 3".

Введем предикаты P(x) = "x делится на 6"; Q(x) = "x делится на 3". Наше утверждение формулируется следующим образом: x(P(x)  Q(x)).

Предикат P(x) (делимость на 6) является достаточным условием предиката Q(x) (делимость на 3). Предикат Q(x) (делимость на 3) является необходимым условием предиката P(x) (делимость на 6).

2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость

Формула есть перевод содержательного рассуждения в формальное рассуждение. Формула имеет смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Каждая интерпретация состоит в указании множества М изменения предметных переменных и задании отношения между переменными с помощью предикатов.

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

Пример 2.22.

Пусть М – множество целых положительных чисел, и дан предикат A(x, y) = “x y”.

Рассмотрим следующие формулы:

1)A(x, y);

2) yA(x, y);

3) xyA(x, y).

Первая формула – это предикат, который является истинным высказыванием для всех пар целых положительных чисел (a, b), таких, что a b.

Вторая формула – предикат “Для всякого целого положительного числа y имеет место x y”, который является истинным только для x = 1.

Третья формула – высказывание “Существует такое x, что для всякого y имеет место x y”. Оно является истинным и соответствует тому, что на множестве М есть наименьшее число (единица).

Пусть задаио множество M изменения предметных переменных формулы A(x₁, x₂, ... , x_n), т. е. (x₁, x₂, ... , x_n) M.

Определение 2.7. Формула A называется выполнимой в данной интерпретации, если существует набор значений переменных (a₁, a₂, ... , a_n) M, для которого A(a₁, a₂, ... , a_n) = И.

Определение 2.8. Формула A называется истинной в данной интерпретации, если A(x₁, x₂, ... , x_n) = И на любом наборе своих переменных (x₁, x₂, ... , x_n) M.

Определение 2.9. Формула A называется общезначимой или тождественно-истинной, если она истинна в каждой интерпретации.

Определение 210. Формула A называется выполнимой, если существует интерпретация, для которой она выполнима.

Проблема разрешимости для логики предикатов, так же, как и для логики высказываний (см. раздел 1.5) заключается в том, чтобы установить, является ли произвольная формула тождественно-истинной.

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

Теорема 2.4. (Теорема Черча). Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Однако, для одноместных предикатов проблема разрешимости решается положительно.

В общем случае выделение общезначимых формул логики предикатов возможно в рамках аксиоматического подхода, который будет рассмотрен ниже (см. раздел 3.3).