§ 1.2. Основные понятия

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

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

Если в силу каких-нибудь условий каждому элементу х, принадлежащему множеству X (этот факт записывается так: ), оказывается приведенным в соответствие определенный элемент у, принадлежащий множеству Y (), то говорит, что эти условия определяют у как функцию или, иначе, говорят об отображении множества X на множество Y.

Про функцию говорят также, что она определена на множестве X и принимает значения из множества Y; х называют независимой переменной или аргументом, а y — функцией.

Тот или иной конкретный тип функциональной зависимости определяется, с одной стороны, характеристиками множеств X и Y, а с другой — свойствами элементов х и y этих множеств.

Рассмотрим некоторые основные характеристики множеств. В зависимости от того, конечно или бесконечно количество элементов, составляющих множество, все множества делят на конечные и бесконечные. Например, множество букв в русском алфавите конечно; множество молекул в теле конечных размеров также конечно; множества же, состоящие либо из всех целых положительных чисел, либо из всех рациональных чисел, либо из всех вещественных чисел, служат примерами бесконечных множеств. Бесконечными являются также множество всех точек отрезка, множество всех точек плоской фигуры.

Множества можно сравнивать по мощности. Два множества называются равномощными, если между всеми элементами этих множеств может быть установлено взаимно однозначное соответствие. Среди бесконечных множеств оценка по мощности позволяет выделить два важных класса: счетные и континуальные множества.

К счетным множествам относятся те, которые равномощны множеству натурального ряда чисел, а к континуальным — такие множества, которые равномощны множеству всех вещественных чисел.

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

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

Счетными множествами являются также множество всех алгебраических чисел, множество всех рациональных чисел и некоторые другие множества.

Континуальными множествами являются множество всех иррациональных чисел, множество всех точек отрезка линии, множество всех точек плоской фигуры и многие другие. Иногда сопоставление бесконечных множеств по их мощности приводит к утверждениям, которые звучат парадоксально. Например, на первый взгляд кажется странным, что множество точек некоторого отрезка (АВ на рис. 1.1) и множество точек некоторой части того же отрезка (АВ на рис. 1.1) равномощны. Однако это так, в чем легко убедиться, если сделать приведенное на рис. 1.1 вспомогательное построение. Из этого очевидного построения следует, что для любой точки М отрезка А В луч, проходящий через эту точку и полюс О, пересекает отрезок АС в точке , которую можно считать находящейся с точкой М отрезка АВ во взаимно однозначном соответствии. Значит, оба рассматриваемых множества действительно равномощны. Подобным же образом показывается, что множество точек плоской фигуры или даже тела также равномощно множеству всех точек отрезка линии, т. е. имеет мощность континуума.

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

Рис. 1.1.

Если функциях определена на множестве X всех вещественных чисел и принимает значения из множества y, также состоящего из всех вещественных чисел Y, то в этом случае мы имеем вещественную функцию y одной вещественной переменной или Если же функция принимает значения из того же множества вещественных чисел y, а каждый элемент множества , на котором она определена, является последовательностью, состоящей из вещественных чисел , то в этом случае мы имеем вещественную функцию у не одной, а вещественных переменных или .

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

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

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

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

В качестве примера рассмотрим два множества. Первое из них образуют все различные белые клавиши рояля; обозначим эти клавиши слева направо символами перечень этих символов составляет алфавит множества . Второе множество состоит из всех нот октавы, т. е. из семи элементов, и имеет алфавит , причем символами обозначены соответственно ноты до, ре, ми, фа, соль, ля и си. Для настроенного рояля каждому символу из алфавита соответствует один определенный символ из алфавита . Это значит, что переменная y, принимающая значения , является логической функцией независимой переменной , принимающей значения . Эта функция может быть задана, например, в виде таблицы (см. табл. 1.1)

Таблица 1.1

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

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

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

Таблица 1.2

Таблица 1.3

Каждое значение аргумента неоднородной логической функции обычно называют предметом, а саму функцию в этом случае принято называть предикатом. Если множество значений аргумента неоднородной логической функции (множество предметов) может быть и бесконечным, то сами неоднородные логические функции — предикаты, могут быть лишь двух-, трех- и вообще -значны, где m обязательно конечно.

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

Функции нескольких независимых переменных мы также будем делить на два класса. К одному из них будем относить те функции, в которых любая из независимых переменных и сама функция являются логическими переменными, принимающими значения из одного и того же множества. Такие функции будем также называть однородными. В связи с тем, что при построении математического аппарата однородных логических функций рассматривалось множество с элементами «истинное высказывание» и «ложное высказывание», весь этот аппарат обычно называют исчислением высказываний.

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

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

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

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

Пусть речь идет о событии, состоящем в том, что я встретил знакомого мужчину. Это событие может наступить или не наступить в зависимости от того, наступят или нет образующие это сложное событие простые события: один из встречных оказался моим знакомым и этот же встречный был мужчина. Здесь мы имеем дело с однородной логической функцией двух независимых переменных; она однородна, потому что и независимые переменные и сама функция являются событиями, то есть логическими переменными, принимающими значения из одного и того же двухэлементного множества с элементами «событие наступило» и «событие не наступило». Обозначая одну независимую переменную (событие — встреча со знакомым) через , вторую (событие — встреча с мужчиной) через и функцию (событие—встреча со знакомым мужчиной) через y, получаем возможность представить рассматриваемую функцию в виде таблицы (см. табл. 1.4). Примененные при заполнении таблицы знаки 0 и 1 являются символами, соответствующими элементам «событие не наступило» и «событие наступило».

Таблица 1.4

В рассмотренном примере с клавиатурой рояля логическая функция была неоднородной. Там мы имели дело с семизначным одноместным предикатом, предметная переменная которого (номер клавиши) принимала значения из пятидесятиэлементного множества.

Оценка истинности высказывания, определяемого алгебраическим выражением

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

Как известно, день недели может быть установлен, если известны число, месяц и год. Соответствующие этой задаче правила определяют неоднородную логическую функцию — трехместный семизначный предикат; предметные переменные здесь принимают значения из трех множеств: одно из них имеет 31 элемент, другое — 12 и третье — счетное множество элементов.

Единого математического аппарата, пригодного для применения ко всем разновидностям логических функций, в настоящее время не существует. Наибольшего совершенства сейчас достиг аппарат, относящийся к двузначным логическим функциям. Этот раздел математической логики (двузначная логика) является, с одной стороны, основой, на которую опирается все построение математической логики; с другой же стороны, именно аппарат этого раздела имеет в настоящее время наибольшее прикладное значение. Аппарат же многозначной логики еще нельзя считать достаточно сформировавшимся. В связи с отмеченными обстоятельствами мы не будем касаться больше многозначной логики. Основные положения двузначной логики, включающей исчисления двузначных высказываний и предикатов, излагаются в следующих параграфах.