Лекция 7. Предикаты и кванторы

В предыдущих лекциях мы рассмотрели один из первоначальных раз-

делов математической логики – алгебру высказываний. Однако для ре-

альной математической практики выразительные возможности алгебры

высказываний явно недостаточны. Мы не можем выразить, например,

мысль типа «существует объект x с некоторым свойством A». Для то-

го, чтобы записывать подобные утверждения, нам нужны понятия преди-

ката и квантора. Напомним определение предиката из вводного курса

математики.

Пусть задано некоторое предложение P(x1, x2, . . ., xn), содержащее n

переменных, принимающих значения из некоторого множества M. Это

предложение называется n-арным предикатом с областью определения

M, если при замене переменных x1, x2, . . . , xn, на элементы изM получа-

ется высказывание.

Пример. Предложение x + y = 7 нельзя рассматривать как выска-

зывание. Действительно, не зная конкретного значения переменных x и

y, нельзя приписать этому предложению значения «истина» или «ложь».

Однако, при подстановке вместо переменных x, y, элементов из множе-

ства комплексных чисел получается высказывание. Поэтому предложе-

ние x + y = 7 – бинарный предикат с областью определения C.

Можно дать более строгое определение предикатов на основе тео-

рии множеств. Пусть, например, M - множество всех людей, живущих

в настоящее время. Рассмотрим бинарный предикат P(x, y): человек x

знает человека y. Составим список P следующим образом: переберем все

пары a, b. Если P(a, b) = И , т.е. a знает b, то в этот список поместим па-

ру (a, b). Если P(a, b) = Л, то пара (a, b) не входит в список P. Свойство

«знает» полностью характеризуется списком P.

Поскольку любой n-арный предикат P может быть подвергнут про-

цессу составления списка и получения подмножества P в M × · · · × M,

то приходим к следующему определению.

ОПРЕДЕЛЕНИЕ 7 n-арным предикатом, определенным на мно-

жестве M называется некоторое подмножество в декартовой

произведенииMn = M ×· · ·×M.

Особую роль играет в математике бинарный предикат «равно». Для

его обозначения используется знак « = ». Имеем a = b тогда и только

тогда, когда a и b—один и тот же объект. Если некоторое математическое

утверждение высказано по a, то есть P(a) = И , то и P(b) = И.

Однако возможны осложнения, что показывает следующий известный

пример из [4]. Пусть n - число планет солнечной системы. Тогда

1. Коперник не знал, чтоn > 6;

2. на самом деле n = 9, подставим n в 1) и получим, что

3. Коперник не знал, что 9 > 6.

Где ошибка?

Рассмотрим логические знаки ∃ и ∀, рассматривавшиеся во вводном

курсе математики. Они имеют следующие названия:

∃ - квантор существования.

∀ - квантор всеобщности.

Пусть P(x) - предикат от одной переменной, определенный на множе-

ствеM. И сходя из P(x) и квантора ∃ можно составить высказывание

∃x P(x).

Это высказывание истинно тогда и только тогда, когда P(x) пре-

вращается в истинное высказывание хотя бы при одном значении x из

множестваM.

Пример. Пусть P(x) определен на M— множестве действительных

чисел и P(x) = x2 > 4. Тогда ∃x P(x) - это есть ∃x x2 > 4 - истинное

высказывание.

Пусть P(x) - предикат от одной переменной, определенный на множе-

ствеM. И сходя из P(x) и квантора ∀ можно составить высказывание

∀x P(x).

Это высказывание истинно тогда и только тогда, когда P(x) пре-

вращается в истинное высказывание при каждом значении x из множе-

стваM.

Если P(x) - предикат на M = R из предыдущего примера, то исполь-

зуя ∀, составим высказывание ∀x x2 > 4. Это ложное высказывание,

так как при x = 1, получим: 12 > 4.

Рассмотрим следующие высказывания

∃x∃y x+ y = 3

∃x∀y x+ y = 3

∀x∃y x+ y = 3

∀x∀y x+ y = 3

∃x∃y x+ y = 3

Какие из данных высказываний истинны?

Из вводного курса известны следующее равносильности:

∀x P(x) ≡ ∃x P(x)

∃x P(x) ≡ ∀x P(x)

Рассмотрим первую равносильность и составим отрицание для обеих

частей. Получим

∀x P(x) ≡ ∃x P(x)

Это означает, что квантор всеобщности – излишний знак, который в

дальнейшем не будет входить в число основных символов, а будет опре-

деляемым символом. Поэтому знак ∀ - определяемый знак.

Мы можем применять равносильные формулы из алгебре высказыва-

ний:

A ∨ B ≡ A ∧ B.

Представим вместо A высказывание ∀x P(x), вместо B высказы-

вание ∃y Q(y) и получим

∀x P(x) ∨ ∃y Q(y)) ≡ ∀x P(x) ∧ ∃y Q(y) ≡ ∃x P(x) ∧ ∀y Q(y)

В процессе математической деятельности, доказательства теорем,

выработке понятий мы всегда должны отобразить мыслительную дея-

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

и т. п. мы должны создать специальные знаки. Особую роль в математике

играют переменные.

В логике посредством переменной мы будем обозначать произвольный

предмет (индивид). Например, x может означать число, вектор, прямую и

т. п. Также важнейшим понятием в логике являются понятия функции и

предиката.

ОПРЕДЕЛЕНИЕ 8 n - арной функцией, определенной на множе-

стве M, называется правило, сопоставляющее каждому набору

(a1, a2, . . .an) ∈ M однозначно определенный элемент b ∈ M. Если- f

– знак для обозначения функции, то записываем f(a1, a2, . . .an) = b,

гле b – значение функции.

В дальнейшем придерживаемся следующих соглашений.

Обычно f, g,h, . . . - знаки для обозначения функций – функциональ-

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

символы: p, q, r.

Рассмотрим применение функциональных и предикатных символы в

различных математических выражениях.

Рассмотрим выражение (x · y). Здесь y, x - переменные, которые мы

можем заменять на конкретные значения. · - это знак для функции. Дей-

ствительно, заменим x на 2, y на 3, получим 2 · 3, которое есть число. По-

этому · - знак для бинарной функции.

Рассмотрим выражение

x · y = z

Заменим x, y, z на числа 2, 3, 7.Получили 2·3 = 7- ложное высказывание.

Здесь «=» бинарный предикатный символ.

Рассмотрим выражение из школьного курса sin x. Здесь нужно sin

- это сложный символ, не состоящий из частей. Это унарный функ-

циональный символ. Выражение sin x − − ( это понятие будем обсуж-

дать поэднее). Рассмотрим x + y + z = 1 — это тернарный предикат.

Параллельность в геометрии – бинарный предикат и _ – знак для этого

предиката.

В аксиомах Пеано употреблялось x_, другое обозначение S(x) - это

знак для функции, а не для предиката.

На приведенных примерах видно что для выражения наших мыслей о

математических объектах достаточно следующих знаков.

1. логических знаков;

2. знаков для предикатов – предикатных символов p, q, r, . . . ;

3. знаков для функций – функциональных символов f, g,h, . . . .

Лекция 8. Формализация математических теорий на

языке первого порядка

В предыдущих лекциях мы построили исчисление высказываний в виде

формальной системы. Сейчас мы начинаем более трудный и значитель-

ный шаг – рассмотрение формализаций математических теорий. Напом-

ним, что формальная система отражает синтаксические аспекты матема-

тической теории, т.е. отражает процесс переноса нашим мыслей о мате-

матических объектах в отображающие их записи с помощью специаль-

ных символов. Формальная система имеет следующие составные части.

• Первая часть формальной системы – ее язык. Чтобы определить

язык формальной системы нужно задать символы этого языка и его

формулы.

• Вторая часть формальной системы – ее аксиомы. Задать аксиомы

означает выделить некоторые формулы формальной системы, при-

своив им название аксиомы.

• Третья часть формальной системы – ее правила вывода, которые

служат для получения теорем. В них отражены логические законы,

которые используются в математике.

Мы будем рассматривать важный случай формальных систем – теории

первого порядка.