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

УДК 591.45 
П78 

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

Прокопчук Ю.Ю., Широков А.И. 

П78 
Дискретная математика: Основные теоретико-множественные 
конструкции. Ч. III: Учеб. пособие / Под ред. А.Г. Дьячко и 
Е.А. Калашникова. - М.: МИСиС, 2005. - 77 с. 

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

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

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

ОГЛАВЛЕНИЕ 

От авторов 
4 

Введение 
5 

Глава V. Отношения между множествами. Соответствия 
6 

§ 1. Определение отношения между множествами. Виды 
отношений 
6 

1. Определение отношения между множествами 
6 

2. Виды отношений 
7 

Упражнения 
8 

Примечания 
12 

§ 2. Соответствия 
13 

1. Терминология и обозначения 
13 

2. Способы задания соответствий 
14 

3. Образ и полный прообраз множества относительно 
соответствия 
18 

Упражнения 
18 

Примечания 
21 

§ 3. Отношения между соответствиями и операции над ними 
22 

1. Отношения между соответствиями 
22 

2. Действия над соответствиями, порожденные теоретикомножественными операциями 
23 

3. Действия над соответствиями, порожденные 
операциями над графиками 
24 

Упражнения 
27 

Примечания 
32 

Глава VI. Свойства соответствий. Задачи анализа и синтеза 
соответствий 
33 

§ 1. Свойства соответствий 
33 

1. Основные свойства соответствий 
33 

2. Свойства функциональных соответствий 
34 

3. Связи между свойствами соответствий 
35 

Упражнения 
37 

Примечания 
47 

§ 2.3адачи анализа и синтеза соответствий 
47 

1. Задача анализа для соответствий 
47 

2. Задача синтеза для соответствий 
49 

Упражнения 
50 

Примечания 
69 

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

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

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

3 

Памяти 
Юлия Михайловича Сощина 

От авторов 

Данное пособие авторы посвящают памяти Юлия Михайловича 
Сощина, заместителя начальника Вычислительного центра Московского государственного института стали и сплавов (МИСиС), скоропостижно скончавшегося 5 июня 1987 года. 

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

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

4 

ВВЕДЕНИЕ 

1. Понятия множество и кортеж, представленные в главах гл. I и 
II пособия [15], являются к а т е г о р и я м и современной математики 
[12, с. 8], на основе которых могут быть «построены» теоретикомножественные конструкции «любой степени сложности». Простейшие среди них - множества кортежей (то есть графики) и кортежей множ:еств подробно изучены в главах III и IV пособия [16]. Рассмотрим содержание данного пособия. 

В гл. V вводится одно из фундаментальных понятий современной 
математики - отношение меж:ду множ:ествами, и сообщаются сведения об его отдельных видах. А именно, в § 1 это понятие логически строго определяется на основе теоретико-множественных конструкций: кортеж м н о ж е с т в [16,гл. III, §3, п. 3, с. 48], прямое 
п р о и з в е д е н и е 
м н о ж е с т в 
(см. там же) и 
n - г р а ф и к 
[16, гл. III, § 2, п. 3, определение 1, с. 23], и иллюстрируется примерами. 
Здесь же читатель знакомится с некоторыми отдельными видами указанных отношений, в частности, с п-местными отношениями на множестве, свойствами и соответствиями. Последние и служат основным 
объектом изучения в этой и последующей главах. § 2 посвящен подробному изложению общих вопросов, связанных с соответствиями. Полученные здесь результаты базируются в основном на исследованиях, проведенных в [16, гл. IV, § 1, с. 90 – 104]. В § 3 определяются и анализируются некоторые связи между соответствиями и действия над ними, порожденные теоретико-множественными и графиковыми операциями. 

В гл. VI читатель получает сведения об основных свойствах соответствий, проблемах их анализа и синтеза. В § 1 перечисляются указанные свойства и доказывается их семантическая независимость. 
Здесь же приводится строгое определение одного из главных понятий современной математики и ее приложений- функциональных 
соответствий, или функций. Далее рассматриваются виды функций 
и связи между свойствами соответствий. В § 2 изложены постановки 
задач анализа и синтеза соответствий. Решения этих задач проиллюстрированы на примерах. 

2. Некоторые места текста имеют целью уберечь читателя от 
серьезной ошибки, которую он рискует совершить; эти места отмечены знаком Z («опасный поворот») [1, с. 20]. 

3. Авторы благодарят Т.В. Дубравину и М.С. Кузьмина за помощь 
в компьютерной верстке. 

5 

ГЛАВА V. ОТНОШЕНИЯ МЕЖДУ МНОЖЕСТВАМИ. 
СООТВЕТСТВИЯ 

Развúтые в гл. I-IV пособий [15, 16] концепции позволяют построить довольно общую теоретико-множественную конструкцию: 
отношение между множествами (§1, п. 1 данного пособия), конкретизациями которой являются такие фундаментальные понятия 
современной математики как соответствие (§ 1, п. 2), в частности, 
функция (гл. VI, § 1, п. 1), и n-местное отношение на множестве 
(§ 1, п. 2), *в частности, бинарное отношение на множ:естве (гл. X).* 
Эти концепции позволяют также рассматривать некоторые уже введенные понятия с более общей точки зрения. 

§ 1. Определение отношения между 
множествами. Виды отношений 

1. Определение отношения между множествами 

Определение 1. Пусть neN , 

Y=df <Xi>ig[1;n] 
(1) 

- кортеж множеств, а 

Gcnig[1;n]Xi.1) 
(2) 

n-местным, или n-арным, отношением между множествами из их 
кортежа (1) называют пару 

Q =df <G, Y>. 
(3) 

n-график G называют графиком отношения (3), а кортеж (1) - его 
носителем. 

Пример 1. 1) Кортеж длины 2 Q1=df<G1,<R,R», где G1 – бинарный график [16, гл. IV, § 1, п. 1, с. 90], состоящий лишь из 
всех пар <x,y>eR2, для компонент каждой из которых верно неравенство x<y, представляет собой д в у х м е с т н о е , или б и н а р ное, о т н о ш е н и е между множествами из кортежа <R,R>, или на 
множестве R, которое называют отношением нестрогого порядка на 
множестве R. 

2) Пара Q2=df<G2,<N,Z,Q», где G1 – т е р н а р н ы й график [16, 
гл. III, § 2, п. 1, с. 23], составленный исключительно из всех троек 
<n,z,q>eNxZxQ, для компонент каждой из которых верно равенство: 

6 

q=HOfl(n,z)2), является трехместным отношением между множествами из их кортежа <N,Z,Q>, которое читают: быть наибольшим общим делителем двух чисел. 

В дефиниции понятия о т н о ш е н и е между 
м н о ж е с т в а м и 
участвуют в основном объекты неопределенные в том смысле, что их 
характеристиками с языковóй точки зрения являются не константы, а 
переменные каких-то видов. Так, кортеж Y может иметь п р о и з в о л ь н у ю положительную длину [15, гл. II, § 1, п. 1, 2, с. 71-73], 
его компонентами могут служить всякие множества, в качестве 
графика отношений может выступать любая часть от ПY 1) и т.д. 
Введение связей между составляющими отношения или их параметрами и предъявление к ним тех или иных требований, определяемых 
чаще всего практическими соображениями, ведет к уменьшению 
разнообразия отношений, выделению их отдельных видов. В изучение некоторых из них мы попытаемся углубиться. 

2. Виды отношений 

Приведем несколько примеров ограничений на составляющие отношения. Сначала рассмотрим некоторые ограничения на его график. 

Определение 1. Отношение (3) из п. 1 называют пустым, если 
G=0, и полным, если G=nig[1;n]Xi. Когда для кортежа (1) из п. 1 верно 

(3ie[1;n])(Xi=0), 
(1) 

объемы этих понятий совпадают - см. упр. 6 к данному параграфу. 
Ясно, что 

(Vie[1;n])(npiGcXi). 
(2) 

Определение 2. Отношение называют определенным (частичным) по i-u компоненте, или i-u координате, если 

npiG=Xi 
(3) 

(соответственно, 

npiGcXi). 
(4) 

Определение 3. Отношение называют всюду определенным, если 
оно определено по любой своей компоненте, то есть 

(Vie[1;n])(npiG=Xi), 
(5) 

7 

не всюду определенным, если 

(3ie[1;n]) (npiGcXi), 
(6) 

и частичным, если 

(Vie[1;n])(npiG(zXi). 
(7) 

Рассмотрим несколько ограничений на параметры кортежа (1) из п. 1. 
1) Если для его компонент выполняется условие 

(Vie[1;n])(Xi=X), 
(8) 

мы получаем отнотпение вида <G,Y>, где Y=<X,X,...,X>, /(Y)=n, а 
GcXn - см. [16, гл. III, § 3, п. 2, с. 49]. Такие отнотпения называют пместными, 
или п-арными, отношениями на множестве 
X. 
*Подробно мы будем говорить о них в главе X.* 

2) Если в равенстве (1) из п. 1 положить n=1, мы получим пару 
вида <G,X>, где GcX. Такие отнотпения называют свойствами [15, 
гл. I, приложение 1, с. 43]. 

3) Когда в равенстве (1) из п. 1 n=2, мы приходим к отнотпениям 
вида <G,<X1,X2», где GcX1xX2, то есть G – 2 - г р а ф и к [16, гл. IV, 
§ 1, п. 1, с. 90]. Такие отношения называют соответствиями, или 
корреспонденциями. Именно они и их виды являются основным 
предметом изучения в этой и следующей главах. 

Упражнения 

1. Пусть neN и 1<n<4. Приведите примеры n-местных отнотпений. 
Решение 

1) Пара S1=df<R+, R> представляет собой о д н о м е с т н о е , или 
у н а р н о е , отношение на множестве R, а именно, свойство быть 
вещественным строго пол ожителъным числом. 

2) Пара S2=df<G,<Z,N», где S2 - б и н а р н ы й г р а ф и к , построенный лишь из всех пар вида <z,m>eZxN, для каждой из которых 
верно равенство | z |=m, является д в у х м е с т н ы м , или б и н а р ным, о т н о ш е н и е м между множествами Z и N, которое читают 
так: натуральное число п есть модуль, или абсолютная величина, 
целого числа z. 

3) Пара S3=df<H,<Q,Z,N», где H - т р е х м е с т н ы й , или т е р н а р н ы й , 
г р а ф и к , составленный только из всех троек вида 
<q,z,n>eQxZxN, компоненты каждой из которых удовлетворяют условию q<z<n, является т е р н а р н ы м о т н о ш е н и е м находиться 
между для множеств кортежа <Q,Z,N>. 

8