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

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

№ 1221 

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

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

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

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

Часть VII 

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

Под редакцией профессора Н.В. Крапухиной 

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

Москва     Издательский Дом МИСиС     2010 

УДК 510.8 
 
К59 

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

Козловский А.В., Прокопчук Ю.Ю., Широков А.И. 
К59  
Дискретная математика: Основные теоретико-множественные 
конструкции. Ч. VII: Учеб. пособие / Под ред. проф. Н.В. Крапухиной. – М.: Изд. Дом МИСиС, 2010. – 128 с. 
ISBN 978-5-87623-300-8 

Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое фундаментальное понятие современной математики, как n-местное (в частности, бинарное) 
отношение на множестве, а также излагается относящийся к нему логический 
и математический аппарат.  
Содержание пособия соответствует программам учебных курсов «Математическая логика и теория алгоритмов» и «Дискретная математика». 
Предназначено для студентов, обучающихся по специальностям 230401, 
230102 и 080801 и изучающих данные учебные курсы. 
УДК 510.8 

ISBN 978-5-87623-300-8 
© Козловский А.В., Прокопчук Ю.Ю., 
Широков А.И., 2010 

ОГЛАВЛЕНИЕ 

Введение....................................................................................................5 
Упражнения к разделу «Введение» ................................................7 
Примечания.......................................................................................9 
Глава XIII. Бинарные отношения на множествах................................10 
§ 1. Основные понятия...........................................................................10 
1. Определение n-местного отношения, где n∈N+, 
на множестве...................................................................................10 
2. Определение бинарного отношения на множестве. 
Терминология и обозначения........................................................11 
3. Способы задания отношений.....................................................14 
4. Свойства отношений и связи между ними...............................18 
5. Действия над отношениями.......................................................19 
Упражнения к § 1 главы XIII.........................................................28 
Примечания.....................................................................................42 
§ 2. Простые, или элементарные, отношения ......................................43 
1. Отношения, порожденные свойствами соответствий 
(корреспондентные отношения)....................................................43 
2. Отношения типа рефлексивности .............................................44 
3. Отношения типа симметричности ............................................48 
4. Совершенные и связанные отношения.....................................50 
5. Отношения типа транзитивности..............................................54 
Упражнения к § 2 главы XIII.........................................................57 
Примечания.....................................................................................87 
Глава XIV. Сложные бинарные отношения. Задачи анализа и 
синтеза отношений .................................................................................89 
§ 1. Составные, или сложные, бинарные отношения..........................89 
1. Введение......................................................................................89 
2. Эквивалентность.........................................................................90 
3. Толерантность.............................................................................93 
4. Порядки .......................................................................................96 
Упражнения к § 1 главы XIV.........................................................99 
Примечания...................................................................................105 
§ 2. Задачи анализа и синтеза отношений ..........................................108 
1. Анкета отношения. Задачи анализа отношений ....................108 
2. Задачи синтеза отношений ......................................................111 
Упражнения к § 2 главы XIV.......................................................111 
Библиографический список.................................................................115 

Приложение 1. Математические конструкции,  построенные из 
бинарных графиков ..............................................................................117 
1. Бинарные графики, или графики.............................................117 
2. Понятия, связанные с понятием «композиция графиков»....118 
Упражнения...................................................................................123 
Примечания...................................................................................123 
Приложение 2. Указатель знаков и обозначений ..............................124 
Приложение 3. Указатель терминов ...................................................125 
 

ВВЕДЕНИЕ 

1. Как и многие элементы речи, слово «отношение» (или его синонимы «реляция», «связь» и т.д.) представляет собой полисем 
[13, с. 57–62]. В различных научных областях оно служит термином 
[7, с. 594, ст. «Термин»] для понятий, объемы и содержания [14, с. 7] 
которых вообще говоря различны, хотя и могут иметь общие черты. 
В философии и логике [2, с. 264, ст. «Отношение»; 7, с. 418, ст. «Отношение»] понятие «отношение» является категорией [14, с. 8], в которой в самом общем виде отражены взаимосвязи и взаимозависимости 
как между отдельными предметами, процессами, явлениями, так и их 
сторонами. Наличие отношений между объектами любой сферы действительности взаимообуславливает их существование и развитие. По 
мнению великого греческого мыслителя Аристотеля (384–332 до Р.Х.), 
человеческое познание состоит главным образом в выявлении необходимых связей между предметами [6, с. 216, ст. «Необходимость»; с. 
217, ст. «Необходимые и достаточные условия»].  
2. Число n, где n∈N+, всех предметов, находящихся в данном отношении, называют его местностью, или арностью, а само отношение – n-местным, или n-арным. Приведем несколько примеров.  
При n = 1 реляцию называют унарной, или свойством. Предметы 
разносторонне характеризуются своими свойствами. Они выражают 
отношение предмета «к самому себе», независимо от того, в каких 
связях находится он с другими предметами. Так, свойство натурального числа «быть четным» не является следствием, вытекающим, 
например, из тех фактов, что другие являются четными или нет, хотя 
какие-то связи между четными числами имеют место – см. раздел 
«Упражнения к разделу «Введение»». 
При n = 2 отношение называют двухместным, или бинарным. 
Примерами таких отношений между людьми служат родственные 
(отец–сын), производственные (начальник–подчиненный), социальные (партия–партия) и т.д. связи. 
При n = 3 связь называют трехместной, или тернарной. Например, отношения между людьми «отец–мать–сын» и «начальник–его 
заместитель–подчиненные» – тернарные.  
3. В математике изучаются как отношения между математическим 
объектами [14, с. 11], так и различного рода связи между отношениями. 
Примерами математических свойств являются следующие: быть простым – для натуральных чисел [20, гл. VII, § 1, Примечание 2; с. 76], 

быть конечным – для множеств [20, гл. VII, § 3, п. 1; с. 45], быть пустым – для кортежей [17, гл. II, § 1, п. 3; с. 75] и т.д. Образцами бинарных реляций служат такие: быть не меньше, чем – для чисел, включаться – для множеств [17, гл. I, § 2, п. 4; с. 25], быть равными – для 
кортежей [17, гл. II, § 1, п. 4; с. 76]. Представителем тернарного отношения служит реляция  

находиться между 

для точек х,y,z∈R, где R – числовая прямая [20, гл. VII, с. 80]. Это 
отношение можно определить, например, так:  

 
Р(х,y,z) ≡df [(точка) y находится правее (точки) х 
 
и левее (точки) z], 
(1) 

что формально можно записать следующим образом:  

 
x < y < z. 

Это знакосочетание по определению равносильно такому соотношению: 

 
(x < y) ∧ (y < z), 

которое свидетельствует о том, что некоторые трехместные соотношения могут быть заменены комбинациями двухместных. 
Приведем, наконец, пример n-местной реляции. Ею служит отношение, изображаемое n-местной формулой [15, гл. II, § 1, п. 4; с. 61]  

 
Σi∈[1;n]mi ≥ 0, 
(2) 

где  

 
(∀i: 1 ≤ i ≤ n)(mi∈Z)1). 

4. Как мы уже говорили в [21, Введение, п. 3; с. 5–6], современной 
математике присущ э к с т е н с и о н а л ь н ы й ,  или о б ъ е м н ы й ,  
п о д х о д , который характеризуется тем, что некоторые понятия из различных наук уточняются, или эксплицируются [6, с. 367, ст. «Экспликация»], посредством определенных теоретико-множественных объектов2). Это позволяет иметь дело только с последними, а для них уже 
применимы все известные математические методы [14, с. 9, 1-й абзац]. Данный труд посвящен, в основном, изучению математической, 
а именно, теоретико-множественной модели общенаучного понятия 
отношение и его разновидностям. 

5. Понятия множество и кортеж, изученные нами в главах I и II пособия [17], являются категориями [14, с. 8] современной математики, 
на 
основе 
которых 
могут 
быть 
«построены» 
теоретикомножественные конструкции «любой степени сложности». Простейшие среди них – множества кортежей (то есть графики) и кортежи множеств – подробно изучены в главах III и IV пособия [18].  
6. Сделаем краткий обзор представленного пособия. В главе XIII читатель получает сведения об отношениях на множествах. В её первом 
параграфе вводится в рассмотрение определение понятия n-местное 
отношение на множестве и его важнейшего частного вида – бинарного отношения, которое ниже мы называем просто отношением. 
Здесь же описываются способы задания отношений, а также связи 
между отношениями и операции над ними. В § 2 определяются основные элементарные, или простые, свойства отношений, и выявляются логические связи между этими свойствами.  
Первый параграф главы XIV посвящен изучению наиболее важных с прикладной точки зрения классов сложных, или производных, 
отношений: эквивалентности, толерантности и порядка. В соответствующем месте мы будем говорить о них более детально. И, наконец, в § 2 этой главы рассматриваются вопросы анализа и синтеза 
отношений.  
7. Авторы благодарят Р.Е. Гун за большую помощь в работе над 
пособием.  

Упражнения к разделу «Введение» 

1. Приведите несколько примеров логических связей между свойствами типа «n – четное число», где n∈N, и другими свойствами. 

Решение 
(1) а) Утверждение 

 
если n – четное число, а m∈N, то n⋅m – четное число 
(I) 

– верное. *Таким образом, множество Nч, состоящее только из всех 
натуральных четных чисел, представляет собой идеал алгебры <N, ⋅> 
[10, с. 107].*  
б) Обратное к утверждению (I) предложение  
любое четное число, например r, может быть представлено в виде: 

r = n⋅m, m∈N, где по меньшей мере одно из чисел m,n – четное – 
справедливое.  

Доказательство 
Поскольку r – четное число, то в силу своего определения оно 
может быть представлено в виде: r = 2⋅t, где t∈N.  
(2) а) Утверждение  

если m и n – четные числа, 
то (m + n), (m ⋅ n) и (m ÷ n) – четные числа 

– правильное. Таким образом, множество Nч замкнуто [21, с. 89, Определение 2] относительно бинарных операций сложения, умножения и частичного вычитания3) натуральных чисел.  
б) Утверждение  

если r – четное число, то существуют такие четные числа m и n, 
что r = m + n и r = m ÷ n 

– верное. *Оно свидетельствует о том, что бинарные операции + и ÷ 
типа Nч × Nч → Nч – сюръективные [19, с. 33, Определение 1].*  

Доказательство 
Пусть r∈Nч. Тогда верно равенство r = r + 0 = r ÷ 0, но 0 – число 
четное.  
в) Утверждение  

если r – четное число, то существуют такие ч е т н ы е  ч и с л а  

 
m и n, что r = m ⋅ n 
(II) 

– выполнимое и опровержимое.  

Доказательство 
Пусть r – четное число. Тогда r = 2⋅q, где q∈N. Если q – четное 
число, то утверждение (II) – верное, так как q = 2⋅s, где s∈N, и поэтому r = 2⋅(2⋅s). Если же q – нечетное число, то утверждение (II) – 
ложное.  
*Таким образом, операция умножения типа Nч × Nч → N не является, вообще говоря, сюръективной [19, с. 33, Определение 1].* 
(3) Утверждение  

каждое натуральное число, например, n, 
 
может быть представлено в виде n = 2m⋅r, где m∈N, 
(III) 

– верное, так как n = 20⋅n. Обратное к утверждению (III) предложение  

любое число вида 2m⋅r, где m∈N+, а r∈N, – натуральное 

– очевидно, справедливое.  
(4) Утверждение  

каждое натуральное положительное число 
n может быть представлено в виде n = 2m⋅p, 
 
где m∈N, а р – п р о с т о е  ч и с л о  
(IV) 

– неверное, поскольку, например, число 18 = 2⋅32 не имеет указанного представления. Конверсия утверждения (IV): 

любое число указанного вида – натуральное 

– очевидно, справедливая.  
(5) Утверждение  

(∀n∈N)[(n – четное число) ⊕ (n – нечетное число)] 

– несомненно правильное.  

Примечания 

1) Отметим, что хотя для любого n∈N+ существует n-местное отношение – см., например, формулу (2), «Евклид ХХ века» Н. Бурбаки 
считает, что при построении современных математических теорий 
можно ограничиться рассмотрением (по-видимому, в качестве исходных) только бинарных отношений [3, с. 35]. Например, отношение Р(x, y, z), изображенное правой частью определения (1), может 
быть представлено так:  

 
(x < y) ∧ (y < z),  

то есть через конъюнкцию бинарных соотношений x < y и y < z.  
2) Так, логическое понятие «свойство» отождествляется с вполне 
определенной совокупностью, а именно – его областью определения 
– см. [17, гл. I, Приложение 1; с. 42–43].  
3) Бинарная операция частичного вычитания на множестве N, 
обозначаемая знаком ÷, определяется так: 

 
m
n, если m
n,
m
n
0, если m
n.

−
≥
⎧
÷
= ⎨
<
⎩
 

ГЛАВА XIII. БИНАРНЫЕ ОТНОШЕНИЯ 
НА МНОЖЕСТВАХ 

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

1. Определение n-местного отношения, 
где n∈N+, на множестве 

Напомним необходимые в этой главе понятия, обстоятельно проанализированные нами в пособии [19, гл. V, § 1, с. 6–8].  
Определение 1. Пусть n∈N+, а 

 
Y =df (Xi)i∈[1,n] 
(1) 

– кортеж множеств. Пару вида 〈Φ, Y〉, где 

 
Φ⊆Пi∈[1,n]Xi, 

называют n-местным, или n-арным, отношением (syn. n-местной, 
или n-арной, реляцией) на кортеже множеств (1), или между 
множествами кортежа (1).  
Реляцию обычно обозначают строчной буквой из второй половины греческого алфавита. Допустим, что 

 
ϕ =df 〈Φ, Y〉 
(2) 

– реляция. Кортеж множеств (1) называют её носителем, а n-график Φ 
[18, с. 23, Определение 1], – графиком. Он представляет собой вполне определенную совокупность (быть может, пустую), кортежей 
длины n, или энок [17, гл. II, § 1, п. 3; с. 75]. Примеры n-местных реляций между множествами кортежей приведены в упр. 1 из п. 1 раздела «Упражнения к § 1 главы XIII».  
Если для компонент кортежа (1) выполнено условие  

 
(∀i∈[1;n])(Хi = Х), 

то  

 
Пi∈[1;n]Xi = Xn 

– см. [18, гл. III, § 3, п. 3; с. 49], а дефиниция (2) приобретает такой 
вид: ϕ =df <Φ, Xn>, или, допуская вольность в обозначениях, 

 
ϕ =df 〈Φ, X〉, 
(3) 

где Φ⊆Xn.  

Определение 2. Отношение (реляцию) вида (3) называют nместным, или n-арным отношением (syn. n-местной, или n-арной 
реляцией) на множестве Х. 

2. Определение бинарного отношения 
на множестве. Терминология и обозначения 

Из формулы (3) в п. 1 при n = 2 получаем: 

 
ϕ =df < Φ, X>, 
(1) 

где Φ⊆X2. 

Определение 1. Отношение, или реляцию, вида (1) называют бинарным, или двухместным, отношением (syn. бинарной, или 
двухместной, реляцией) на множестве Х1).  

Пример 1. Следующие реляции получаются при интерпретации, 
или конкретизации [16, гл. III, § 2, п. 1; с. 26], отношения (1) путем 
фиксирования его графика:  

1) OX =df 〈∅, X〉; 
2) EX =df 〈ΔX
2, X〉; 
3) NEX =df 〈X2\ΔX
2, X〉; 
4) PX =df 〈X2, X〉. 

Они носят следующие имена соответственно: 1) пустая; 2) равенства, или диагональная, или тождественная; 3) неравенства, 
или антидиагональная; 4) полная, или универсальная. 
Бинарные отношения, или реляции, на множестве являются основным предметом изучения в этой и следующей главах. Поэтому на 
всем протяжении последних именно их, для краткости речи и пренебрегая полисемией [13, с. 57], мы будем называть просто отношениями, или реляциями, и только о них вести разговор2). 
Легко видеть, что понятие реляция является отдельным видом понятия соответствие [19, с. 8]. Поэтому относящиеся к нему обозначения и терминология [19, с. 8] могут быть использованы и для наименования объектов, разносторонне характеризующих реляцию, 
разумеется, с учетом ее специфики. Познакомимся с ними.  
Итак, в силу Определения 1 из п. 1, отношение, или реляция, – это 
пара [17, с. 75], например, вида (1). Её первая компонента есть часть 

декартова произведения [18, с. 48] второй компоненты (необходимо 
являющейся множеством) на себя (декартового квадрата множества Х). Множество Φ, представляющее собой бинарный график [18, 
с. 90], называют графиком реляции (1), а множество Х (Х, пр1Φ и 
пр2Φ) – её областью отправления, или носителем (соответственно, областью прибытия, областью определения и областью 
значений) и обозначают через Дотпр(ϕ) (соответственно, Дпр(ϕ), 
Допр(ϕ) и Дзн(ϕ)).  
Пусть Ф – график реляции (1), а х,у∈Х. Если принадлежность 
 
<x, y>∈Ф 
(2) 
– верная, то говорят, что  

(объект) х находится в отношении ϕ (с объектом) y. 

Пример 2. См. пример 1. Любой элемент х∈Х находится в отношениях равенства (самому себе) и полного, так как справедливы 
принадлежности <x,x>∈
2
x
Δ и <x,x>∈Х2 соответственно. 
При условии, что х∈пр1Ф, высказываются так: 

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

и этот факт обозначают знакосочетанием !ϕ(х), или !Фϕ(х), или просто !Ф(х), когда из контекста ясно, о какой реляции идет речь.  
Ситуацию, когда у∈пр2Ф, выражают предложением  

(объект) у есть значение, принимаемое (реляцией) ϕ, 

которое стенографируют так: !ϕ–1(y), или !Фϕ
–1 (y), или просто !Ф–1(y) 
[18, с. 90–91]3).  
Таким образом,  

 
!ϕ(х) ≡df (х∈пр1Ф), 
 
!ϕ–1(у) ≡df (у∈пр2Ф). 

Определение 2. Множество  
 
ε<x,y>{<x,y>∈X2: <x,y>∈Ф} 

 
(ε<x,y>{<x,y>∈X2: <x,y>∉Ф}),  

состоящее только из всех пар, принадлежащих (соответственно, не 
принадлежащих) графику Ф, называют областью истинности (со