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

ОГЛАВЛЕНИЕ 

От авторов 
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 

4) Пара S4=df<F,<R,Q,Z,N», 
где F - 
ч е т ы р е х м е с т н ы й 
г р а ф и к , 
составленный 
единственно из всех четверок вида 
<r,q,z,n>eRxQxZxN, компоненты каждой из которых удовлетворяют 
условию r+q+z+n>0, является четырехместным отношением сумма 
четырех указанных компонент строго положительна между множествами кортежа <R,Q,Z,N>. 

2. Что представляют собой графики бинарных отношений на 
множестве X, заданных соотношениями: 1) x=y; 2) x;^y. 

Ответ. 1) АX ; 2) X \АX . 
*3. Пусть 

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

где neN +,- кортеж к о н е ч н ы х 
множеств. Сколько существует 
отношений между множествами этого кортежа? 

Ответ. 2, где p= |X1 | • X2 I •...• |Xn |=Pig[1;n] IXi | [16, гл. III, § 3, 
примечание3, с. 54]. 
Решение 

Общий вид отношения над кортежем множеств (I) таков: 

<G, Y>, 
(II) 

где 

Gcnig[1;n]Xi. 
(III) 

Таким образом, два р а з л и ч н ы х отношения над (I) необходимо 
отличаются только первыми компонентами пар вида (II). Отсюда, в 
силу (III), следует, что над (I) имеется столько различных отношений, 
сколько 
существует 
подмножеств 
множества 
Пi,[1;n]Xi, 
Пусть 
p=|X1|-|X2|-...-|Xn|. Поскольку мощность булеана р(X) множества X есть 

2|X| [15, гл. I, § 3, упр. 2, с. 51], то интересующее нас число равно p . 

4. Постройте 
все 
отношения 
между 
множествами 
кортежа 
Y=<Xi>1<i<2, когда |X1|=m, а |X2|=n, где m,neN, 1<m,n<2, а переменные т и п принимают значения независимо друг от друга. 

p 
Ответ. См. результат упр. 3. 1) при m=n=l верно: p=1, а 2=2; 
p 
2) при m=1, n=2 или m=2, n=1 верно p=2, а 2 =4; 3) при m=n=2 верно: 
p 
p=4, а 2 =16. 

5. Приведите примеры отношений над кортежем множеств Y. 
6. Докажите, что если для кортежа (1) из п. 1 верно 

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

9 

то отношение <G, X> является одновременно и п у с т ы м , и полным. 
Решение 

1) Покажем, что (I)^(G=0). Пусть G^0. Тогда существует xeG. 
Согласно формуле (2) из п. 1 xen1<i<nXi, и поэтому x=<x1,x2,…,xn>, 
где 

(Vie[1;n])(xieXi). 

Отсюда следует, что (Vie[1;n])(Xi;^0), что противоречит (I). Итак, 
при условии (I) верно: G=0, и поэтому отношение <G, Y> - пустое. 

2) Покажем, что (I)^(nig[1;n]Xi=0). Пусть Ili^;n]Xi^<Z>. Тогда существует xеП1<i<nXi, Согласно определению прямого произведения 
множеств x=<x1,x2,…,xn>, где (Vie[1;n])(xieXi). Отсюда следует, что 
(ViE[1;n])(Xi;.0). По это противоречит (I). Таким образом, равенство 
П1<i<nXi=0- верное. Из результатов п. 1) получаем, что n1<i<nXi=G. 
Итак, из (I) вытекает, что отношение <G, Y>(=<0, Y>) - полное. 

7. Приведите пример отношения, всюду определенного по одной 
из своих координат и частичного по другой. Если такой пример удастся найти, сделайте вывод о зависимости или независимости указанных свойств. 

Ответ. Пусть X1=df{l, 2, 3}, а X2=df{4, 5, 6}. Тогда X1xX2={<1,4>, 
<1,5>, <1,6>, <2,4> , <2,5>, <2,6>, <3,4> , <3,5>, <3,6>}. Пусть 
G=df{<l,4> , <2,4>, <3,5>}. Тогда <G, (X)1<i<2>- отношение, всюду 
определенное по 1-й координате, так как np1G={1, 2, 3}=X1, и частичное по 2-й координате, так как np2G={4, 5}сX2. 

Таким образом, указанные свойства независимы. 

8. Пусть 

Q=df<G, Y> 
(I) 

- отношение между множествами кортежа 

Y=df<Xi>1<i<n 
(II) 

множеств. Введем обозначения следующих свойств отношения (I): 

A=df(Q - полное), 
(III) 

B=df(Q - всюду определенное), 
(IV) 

а 

C^df ((Vi:1<i<n)( I Xi 1=1). 
(V) 

10 

Выявите, к какому классу соотношений - и с т и н н ы х , 
л о ж н ы х , 
в ы п о л н и м ы х 
либо о п р о в е р ж и м ы х 
[14, гл. III, §4, п. 5, 
с. 52]- относятся следующие импликации: 
1)A^B; 
2) B^A; 
3) C^A; 4) C^B; 5) C^AлB; 6) A^C; 7) B^C; 8) AлB^C. 

Ответ. Импликации 1) и 3) - 5) - истинные; а 2) и 6) - 8) - выполнимые и опровержимые. 
Решение 

1) Очевидно, что импликация 

(G=n1<i<nXi)^(Vi:1<i<n)(npiG=Xi) 

- верная. 

2) Покажем, что импликация 

(Vi:1<i<n)(npiG=Xi)^(G=n1<i<nXi) 

- выполнимая и опровержимая. 

2а) Если верно C, то верно A и B (см. п. 4) и 5)), а поэтому верно B^A. 

26) См. ответ к упр. 7. Если G1=df{<l,4>, <2,5>, <3,6>}, то 
np1G1={1, 2, 3}=X1 и np2G1={4, 5, 6}=X2, то есть <G1, (Xi)1<i<2> всюду 
определенное отношение, но ясно, что оно не является полным, так 
как G1;^n1<i<2Xi. 

3) Пусть верны соотношения С и (Vi:1<i<n)(xieXi). Тогда 
G={<x1,x2,…,xn>}=n1<i<nXi, то есть Q - полное отношение. 

4) Пусть верно C. Тогда в силу 3) верно А, а в силу 1) - B. 
5) Поскольку импликация 

( P ^ Q ) A ( P ^ R ) ^ 
( P ^ Q A R ) , 

где P, Q и R - соотношения,- тождественно истинное соотношение 
[1, упр. 1, с. 52], то, подставляя в него C, А и B на места P, Q и R соответственно, из п. 3) и 4) получаем 5). 

6) Покажем, что импликация А ^ С - выполнимая и опровержимая. 

6а) Пусть Y1=dfY2=df{a}. Тогда для отношения 

Q=df<{<a, a>}, (Yi) 1<i<2 > 

верны соотношения А и С, и, стало быть, соотношение А^С. 

66) См. ответ к упр. 7. Отношение <X1xX2, (Xi)1<i<2>- полное, 
но для него неверно С. 

7) Покажем, что импликация B ^ С - выполнимая и опровержимая. 

11 

7а) См. п. 6а). Для отношения Q верны соотношения В и С и, 
следовательно, B^С. 

76) См. ответ к упр. 7. Отношение <G, (Xi)1<i<2> - всюду определенное, но для него неверно С. 

8) См. решение к упр. 7. Отношение <X1xX2, (Xi)1<i<2>- полное и 
всюду определенное, но для него неверно С. 

9. *Найдите необходимые и достаточные условия того, чтобы любое отношение между множествами кортежа Y=<Xi>1<i<n являлось 
определенным по i-й координате.* 

Ответ. Достаточное условие: |Xi|=l. Это условие не является необходимым - см. ответ к упр. 8. 

10. Какие логические связи имеют место между следующими 
свойствами отношения Q: 

A(Q)=df(Q - всюду определенное), 
B(Q)=df(Q - не всюду определенное), 
C(Q)=df(Q - частичное). 

Ответ. 1) A^1B; 2) A^lC; 3) C^B. 
Решение 

3) Соотношение 

(Vi:1<i<n)(npiG(zXi)^(3i:1<i<n)(npiG(zXi) 

- тождественно истинное [14, гл. IV, § 3, п. 5, формула (IV.3.24), 
с. 99]. 

11. *Сколько существует n-местных отношений, где neN, на конечном множестве X? 

Указание. Познакомьтесь с решением к упр. 3. 
Ответ: 2^n . 
12. *Сколько существует соответствий между конечными множествами X и Y? 

Указание. Познакомьтесь с решением к упр. 3. 
Ответ: 2|X|·|Y|. 

Примечания 

1) ' З т г ^ Г Ч - 
ХЛ иТ-ГМГ^ XrCWJr^^rwrxr^XADXJX^Xf^ 
'Г^Г^ЛЛТ-Т Г Т 
] X i 
ХЛ r r Y 
C\i^C\r>XJCKXJCKXr\^ 

д е к а р т о в о 
п р о и з в е д е н и е 
м н о ж е с т в 
к о р т е ж а (1) [16, 
гл. III, § 3, п. 3, с. 48]. 

2) Здесь и ниже знакосочетание П0Д(z1,z2) обозначает наибольший общий делитель чисел z1,z2eZ. 

12 

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

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

Обычно с о о т в е т с т в и я , или к о р р е с п о н д е н ц и и (см п. 2 
из § 1) обозначают греческими прописными буквами и изображают 
так: 

r=df <G,X,Y>, 
(1) 

где GcXxY в силу (2) из п. 1 § 1. Таким образом, соответствие - это 
т р о й к а [15, гл.II, §1, п. 3, с. 75], 1-я компонента кото1ой есть 
подмножество прямого произведения ее 2-й и 3-й компоненте Соответствия вида (1) называют соответствиями типа X^Y. Множество G, представляющее собой 2-график, называют графиком корреспонденции (1), множество X (Y, np1G и np2G) - областью ее отправления и обозначают через Дотр(Г) (соответственно областью прибытия Дир(^),областью определения Допр(Г) и значений Дзн(Г)). 

Пример 1. 1) Если U=df{a, b, с, d, е}, V=df{a, Р, у, 5}, а H=df{<b,P>, 
<b,y>, <с,Р>, <с,у>, <d,y>,<d,8>}, то тройка S=df<H,U,V> – корреспонденция. Ее графиком является график Н, Дохр(2)=U, Дпр(2)=V, 
Допр(2)=пр1Н={b, с, d) и Дзн(Ь)=пр2Н={Р, у, 5}. 

2) Для любых множеств X и Y тройки <0,X,Y> и <XxY,X,Y> являются соответствиями. Первое из них называют пустым, а второе полным соответствиями типа X—>Y. «Это, так сказать, «крайние» соответствия между множествами X и Y» [18, с. 173]. 

3) Соответствие IX=<АX2, X, X> называют тождественным для 
множества X [1, с. 90]2). 

Пусть G - график соответствия (1). Если соотношение <x,y>eG верное, то говорят, что 

(объект) у соответствует (объекту) x 
относительно (корреспонденции) Г. 

Для любого xenp1G говорят, что 

(корреспонденция) Г определена для (предмета) х, 

и обозначают этот факт так: !Г(х), или !Gr(x), или просто !G(x), если 
из контекста ясно, о каком соответствии идет речь. Для всякого 
yenp2G говорят, что 

(предмет) y есть значение, принимаемое (соответствием) Г, 

13