Дискретная математика : основные теоретико-множественные конструкции Ч. V

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

№ 495 
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ 

ИНСТИТУТ СТАЛИ и СПЛАВОВ 

Технологический университет 

МИСиС 

Кафедра автоматизированных систем управления 

А.В. 
Козловский 
Ю.Ю. Прокопчук 
А.И. Широков 

Дискретная математика 

Основные теоретико-множественные 
конструкции 

Часть V 

Учебное пособие 

Под редакцией профессора А.Г. Дьячко 

Рекомендовано редакционно-издательским 
советом университета 

t 

Москва Издательство ´УЧЕБАª 2007 

УДК 591.45 
К59 

Рецензент 
д-р техн. наук, доц., проф. МГГА Л.П. Рябов 

Козловский А.В., Ю.Ю. Прокопчук, А.И. Широков 
К59 
Дискретная математика: Основные теоретико-множественные 
конструкции Ч. V: Учеб. пособие / Под ред. проф. А.Г. Дьячко. – 
М.: МИСиС, 2007. – 106 с. 

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

Содержание пособия соответствует программе курса «Дискретная математика». 

Предназначено для студентов специальностей 230102 и 010502, изучающих учебные дисциплины «Математическая логика и теория алгоритмов» 
и «Дискретная математика». 

© Московский государственный институт 
стали и сплавов (технологический 
университет) (МИСиС), 2007 

ОГЛАВЛЕНИЕ 

Введение 
4 

Примечания 
7 

Глава IX. одноместные функции 
9 

§ 1. Основные понятия и определения 
9 

1. Определение функции. Терминология. Примеры 
9 

2. Отношение равенства между функциями 
11 

3. О значениях соотношения f(x) = g(y) 
12 

Упражнения 
13 

Примечания 
32 

§ 2. Сужения на множества 
33 

1. Сужения на множества графиков 
34 

2. Сужения на множества соответствий, 
или корреспонденций, и функций 
35 

Упражнения 
36 

Примечания 
46 

Глава X. Виды функций. Операции. Задачи анализа и синтеза 
49 

§ 1. Виды функций 
49 

1. Семантическая независимость основных свойств 
функций. Терминология 
49 

2. Частичные функции и отображения 
49 

3. Функции, тождественные на множествах 
50 

4. Функции, константные на множествах 
Упражнения 
59 

Примечания 
78 

§ 2 Функции типа X 
X (операции) 
78 

1. Определение операции и её диаграмма 
78 

2. Понятия «итерация» и «порядок» элемента области 
отправления операции 
80 

3. Виды элементов области отправления операции 
84 

4. Устойчивые множества 
89 

Упражнения 
90 

Примечания 
97 

§ 3. Задачи анализа и синтеза функций 
97 

1. Задачи анализа функций 
98 

2. Задачи синтеза функций 
100 

Упражнения 
100 

Библиографический список 
102 

Приложение 1. Указатель знаков и обозначений 
103 

Приложение 2. Указатель терминов 
103 

3 

ВВЕДЕНИЕ 

1. Наряду с такими математическими объектами, как м н о ж е ство, кортеж, график, отношение между множе с т в а м и и т.д.1) понятие ф у н к ц и я занимает одно из центральных 
мест в «математическом мире». Мы не отойдем далеко от истины, 
если скажем, что в современных математических и математизированных текстах именно термин функция встречается чаще других. На 
долгом и тернистом пути становления математики выявленные в 
процессе исследования существенные признаки понятия ф у н к ц и я 
вводились в его с о д е р ж а н и е [10, с. 7], а несущественные – удалялись. И только в 1-й половине XX века это понятие было опреде-
лено логически безупречно [2, определение 9, с. 90]. С историей формирования понятия ф у н к ц и я в период ХVII–ХIХ вв. можно познакомиться, например, по литературе [1, т. 5, ст. «Функция», с. 712–713]. 
Анализ его определений, представленных в советских математических учебниках, приведен в предисловии профессора В.А. Успенского к монографии [20, с. 18–23]. 

В настоящее время, по-видимому, наиболее общим и точным является определение функции как частного вида с о о т в е т с т в и я 
[15, гл. V, § 2, п. 1, пп. 3, с. 8]: 

f =df <F, X, Y>, 
(В1) 

график F которого ф у н к ц и о н а л е н [11, гл. I, § 4, п. 4, с. 33–38; 
15, гл. VI, § 1, п. 6, определение (1), с. 33]. Логическая последовательность введения в рассмотрение математических объектов, «ведущая» к понятию ф у н к ц и я , изображена на рис. В1. 

множество 
^ пара 
• 
бинарный график 

^ произведение двух множеств 
• 
соответствие 
/ 
N. 
\ 
функция 
X 
^ функциональный график 
^ 

Рис. В1 

4 

Столь «короткий путь» включения в математическую теорию и 
практику фундаментального понятия ф у н к ц и я позволяет использовать его уже на самых первых шагах построения «довольно сложных» математических конструкций. Именно так и поступает «Эвклид 
ХХ века» Н. Бурбакú в своей монографии [2, с. 90], вводя строгое 
определение понятия ф у н к ц и я уже на 14-й странице гл. II указанной монографии. 

В советской математической литературе определение функции 
как соответствия с функциональным графиком впервые появилось в 
сочинении [20, с. 182]2). Это логически четкое, ясное и простое определение, в котором ф и г у р и р у ю т т о л ь к о м а т е м а т и ч е с к и е п о н я т и я , постепенно проникает (к сожалению, весьма медленно) во все разделы современной математической науки в виде 
указанной или «близких» ей формулировок. 

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

Необходимость в создании строгого определения понятия 
ф у н к ц и я возникла тогда, когда потребовалось ответить, например, на такие вопросы: 

1) Является ли данный математический объект функцией? 
2) Какие функции считать равными, а какие – различными? 

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

3. Уточнением многих математических понятий и формулировками для них строгих определений мы обязаны переходу от построения 
здания математической науки на и н т е н с и о н а л ь н о й о с н о в е к 
возведению его на э к с т е н с и о н а л ь н о м б а з и с е [4, с. 128, 
ст. «Интенсионал и экстенсионал»; 9, с. 24–31]. Говоря содержательно, указанный переход состоит, в частности, в том, что некоторые 
логические понятия, например, с в о й с т в а и л и о т н о ш е н и я 

5 

[5, 524, ст. «Свойство»; 418, ст. «Отношение»] о т о ж д е с т в л я ю т с я с какими-то теоретико-множественными объектами. Проиллюстрируем сказанное. 

Пример. а) При экстенсиональном подходе логическое понятие 
с в о й с т в о , например, свойство, обозначенное через Р, «приравнивается» к о б л а с т и 
его 
и с т и н н о с т и , помеченной через РИ, 
которая служит частью его о б л а с т и 
о п р е д е л е н и я , поименованной через Ропр6). 

Так, свойство 

Q(x) =df (x - четное число) 
(В2) 

осмысленно для каждого хeZ, где Z - множество, составленное 
только из всех целых чисел. Таким образом, Qопр=Z. Областью истинности свойства (В2) является множество 

By{yeZ: (3zeZ)(y=z+z)} 

[13, гл. I, § 1, п. 3, формулы (4) и (5), с. 24]. 

б) Пусть n e N и n>1. n - м е с т н о е о т н о ш е н и е на м н о ж е стве Х [15, гл. V, § 1, п. 2, с. 8], например, отношение R «приравнивают» к части ВсХn, удовлетворяющей условию 

(V<x1,x2,...,xn>e B)((R(x1,x2,...,xn)=И) л 

л (V<x1,x2,...,xn>eXn\B)((R(x1,x2,...,xn)=Л) @ l!R(x1, x2, ..., xn)). 

Ясно, что 

Rопр = R '^R 
* Например, бинарное отношение < на множестве N определяют 
как множество 

£<x,y>{<x,y>eN2: x<°y}, 

где знак 
<° 
обозначает 
л е к с и к о г р а ф и ч е с к и й 
порядок 
[2, с. 180] на м н о ж е с т в е слов над а л ф а в и т о м {0, 1, 2, …, 
8, 9} с учетом того, что 0<°1<°2<°…<°8<°9*. 

Экстенсиональный подход позволил заменить многие неточные понятия и доказательства теорем более точными и простыми. Он получил свое 
развитие только благодаря построению теории м н о ж е с т в , существованием которой мы обязаны главным образом её создателю гениальному 
немецкому математику Г. Кантору [16, гл. VII, § 1, примечание 3, с. 28]. 

6 

Примечания 

1) Укажем литературу, где эти понятия вводятся. М н о ж е с т в о 
[13, гл. I, § 1, п. 3, 11]; к о р т е ж [13, гл. II, § 1, п. 1, с. 70]; г р а ф и к 
[14, гл. III, § 1, п. 1, определение 1, с. 8]; о т н о ш е н и е м е ж д у 
м н о ж е с т в а м и [15, гл. V, § 1, п. 1, определение 1, с. 6]. 

2) Ю.А. Шиханович был одним из переводчиков монографии [2] с 
французского языка на русский. Отметим, что определение функции, 
приведенное в его труде [20, с. 182], является более общим относительно определения функции, данного в книге [2, с. 90, определение 9]. В 
последней ф у н к ц и я о т о ж д е с т в л я е т с я с о т о б р а ж е н и е м , то есть функцией вида (В1), для которой верно равенство 
пр1F=Х. Согласно определению отображения любое из них является 
функцией, но обратное, вообще говоря, неверно [15, гл. VI, § 3, п. 2, 
определение (1), с. 34]. 

3) *Аналогичное положение дел создалось в свое время с понятием 
а л г о р и т м [1, т. 1, ст. «Алгоритм», с. 202]. Интуитивное п р е д с т а в л е н и е о нем [5, ст. «Представление», с. 475], несмотря на 
весьма неточное его определение, сформировалось настолько ясно и 
отчетливо, что не возникало принципиальных расхождений по поводу того, является ли тот или иной процесс алгоритмическим либо 
нет. И, тем не менее, ситуация оказалась в корне иной, когда в практике стали встречаться классы задач, алгоритмическое решение которых не только было неизвестно, но и сложилось мнение, что они и 
не могут быть решены такими методами. Но, очевидно, строго доказать алгоритмическую неразрешимость этих проблем только на основе интуитивного представления об алгоритмах невозможно. Поэтому в 1-й половине ХХ века были предприняты попытки формализовать такие представления. С этой целью были предложены различные м а т е м а т и ч е с к и е м о д е л и а л г о р и т м о в , то есть логически точные математические конструкции и процедуры, которые и 
отождествлялись с понятием а л г о р и т м [1, т. 1, ст. «Алгоритмов 
теория», с. 226–229]. Впоследствии было установлено, что все такие 
модели эквивалентны в том смысле, что классы решаемых с их помощью задач совпадают. Этот факт послужил основанием для формулирования так называемого тезиса Чёрча (A. Church): 

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

[1, т. 5, ст. «Чёрча тезис», с. 855]. 

7 

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

4) Доказательства теорем о существовании функций, обладающих теми или иными свойствами, мягко говоря, наивны, поскольку не опираются на строгое определение функции (см., например, [17, с. 449, теорема о 
существовании неявной функции]). Поэтому сразу же возникает вопрос: 

О чем идет речь и что доказывается?, 

на который точно ответить нельзя. 

5) Весьма удивительно, что некоторые классики математической логики и математики безапелляционно заявляют, что п о н я т и е 
«ф у н к ц и я » с л е д у е т с ч и т а т ь п е р в о н а ч а л ь н ы м . Так, известный логик А.Чёрч в монографии [19, примечание 39, с. 351] пишет: «В конечном счете понятие ф у н к ц и я или какое-либо сходное понятие, например, понятие к л а с с , считают первоначальным и 
неопределяемым». Не говоря уже о том, что понятия к л а с с и 
ф у н к ц и я – отнюдь не сходные (см., например, [13, гл. I, § 1, примеч. 9, с. 18] и [11, гл. I, § 4, п. 4, с. 39]), естественно спросить у л о г и к а : зачем вводить в теорию в качестве первоначальных два понятия, одно из которых (функция) легко и логически строго «строится» на 
основе другого (класса, множества) (см. рис. В1)? Еще пример. В монографии [18, § 2, с. 12] признанного математика начала ХХ века 
Ф. Хаусдорфа читаем: «Понятие функции т а к о е ж е о с н о в н о е 
и п е р в о н а ч а л ь н о е , как и понятие множества». Как говорится, 
комментарии излишни. 

6) Областью определения свойства Р называют и через Ропр обозначают класс всех объектов, для каждого элемента х которого соотношение Р(х) – осмысленное предложение. Областью истинности 
(ложности) свойства Р называют и через РИ (соответственно РЛ) 
именуют класс всех объектов, д л я к а ж д о г о э л е м е н т а х которого соотношение Р(х) – истинное (ложное) высказывание. Ясно, что 
РИ,РЛ⊆ Ропр [12, гл. III, § 5, прил. 2, с. 72]. 

8 

ГЛАВА IX. ОДНОМЕСТНЫЕ ФУНКЦИИ 

§ 1. Основные понятия и определения 

1. Определение функции. 
Терминология. Примеры 

Согласно изложенному в [15, гл. VI, § 1, п. 1, определение (1), с. 33] 
функция – это с о о т в е т с т в и е , или к о р р е с п о н д е н ц и я , с 
б и н а р н ы м ф у н к ц и о н а л ь н ы м г р а ф и к о м [14, гл. IV, § 1, 
п. 6, определение (1), с. 98]. Поэтому терминология, относящаяся к 
п р о и з в о л ь н ы м к о р р е с п о н д е н ц и я м [15, гл. V, § 2, пп. 1–3, 
с. 13–18], автоматически переносится и на функции, которые мы будем обозначать в основном строчными латинскими буквами. Так, 
если 

f=df<F,X,Y> 
(1) 

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

Тот факт, что функция (1) имеет область отправления X и область 
прибытия Y, выражают словами 

f есть функция типа X Y, 

или 

(функция) f определена в X и принимает значения в Y, 

f 
или в символах: X 
Y, или f: X Y. 

Пример. 1) П у с т о е м н о ж е с т в о е с т ь ф-г р а ф и к [14, гл. III, 
§ 1, упр. 1, с. 12]. Всякая функция с пустым графиком имеет в качестве областей определения и значений пустое множество. Такими являются, например, любые функции вида <∅ ,X,Y>, где Х и Y – множества. Ту из них, у которой области отправления и прибытия – пустые множества, то есть функцию <∅ ,∅ ,∅ >, называют п у с т о й 
ф у н к ц и е й [2, с. 91]. 

9 

2) Т о ж д е с т в е н н о е 
с о о т в е т с т в и е д л я м н о ж е с т в а 
X 
[15, гл. V, § 2, п. 1, пример 1, разд. 3, с. 13] есть функция, называемая 
тождественной функцией множества X или на множестве Х. Она 

обозначается через IX. Таким образом, IX=df< Д 
, X, X>. 

3) Соответствие типа N ^ N с графиком, состоящим только из всех 

пар вида <n, 
n > , где n e N , есть функция с областью определения, 

содержащей только все квадраты натуральных чисел, и областью 

значений, равной N. 

Для наглядного изображения функций, так же как и для соответ­
ствий, используют «графовый язык» [15, гл. V, § 2, п. 2, с. 16]. Чтобы 
было удобно оперировать с функциями алгоритмически, для их задания используют «табличный язык» [15, гл. V, § 2, п. 2, разд. 3.2, определение (1), с. 17]. Аналитические выкладки ведутся на логикоматематическом языке. 

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

g 
С 
i 

А 
В 
Е 

h 

Рис. IX.1 

f 

Здесь группа знаков A 
B означает, что f есть функция типа А В, 
и т.д. 

Рассмотрим некоторые терминологические вопросы. Если для 
функции (1) верно: !f(x), или, ч т о т о ж е , х∈пр1F [15, гл. V, § 2, 
п. 1, определение (2), с. 14], то в силу функциональности графика F 
справедливо утверждение: 

Для любого х∈пр1F существует е д и н с т в е н н ы й о б ъ е к т y, 

такой, что <x,y>∈F 

10 

f 

j 

(см. результаты упр. 1, 2 и 4 к § 1 гл. VI пособия [15, с. 37]). Именно 
этот объект y и называют значением функции (1) на объекте х и обозначают через f(x)1), что нередко записывают в виде 

f(x)=y. 
(2) 

Таким образом, для функции (1) имеем 

(f(x)=y) =df (<x,y>е F). 

* Отсюда следует, в частности, такое соотношение: 

!f(x) ^> |f(x) 1=1.* 

Когда равенство (2) - верное, говорят также, что 

Функция f переводит, или преобразует, или 
трансформирует, 
или отображает (объект) х в (объект) y. 

Синонимами для терма f(x) служат такие знакосочетания: xf, fx 2). 

2. Отношение равенства между 
функциями 

Понятие ф у н к ц и я , введенное в п. 1, представляет собой о г р а н и ч е н и е понятия3) «соответствие», полученное посредством 
добавления к признакам его графика свойства функциональности. 
Если f=df<F,X,Y> и g=df<G,U,V> - функции, то ответ на вопрос: 

В каком случае f и g считать 
равными? 

не вызывает затруднений. Являясь т р о й к а м и [13, гл. II, § 1, п. 3, 
с. 75], в соответствии с определением отношения р а в е н с т в а 
к о р т е ж е й [13, гл. II, § 1, п. 4, с. 75-76] функции f и g равны тогда 

и только тогда, когда равны их i-е компоненты, где i= 1; 3 . Таким образом, 

(f равняется g) =df (F=G л X=U л Y=V). 
(1) 

Следуя традиции, бинарное отношение равенства функций, как и бинарные отношения равенств любых других математических объектов, обозначают символом =4). 

* Такая вольность в письменной речи, помимо указанных в примечании 4 семиотических осложнений, может послужить причиной известного логического «дискомфорта». Например, если слово «равняется» в левой части определения (1) мы заменим знаком =, то получим равносильность 

11