Текст
Федеральное агентство по образованию
ГОУ ВПО «Российская экономическая академия
имени Г В. Плеханова»
Кафедра высшей математики
ПРАКТИКУМ
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Москва 2007
Составители: д-р техн. наук |В. И. Ермаков]
Т А. Ерохина
канд.физ.-мат. наук В. О Локуциевский
М. Н. Максименко
канд. физ.-мат. наук О. Л. Шеметкова
Практикум по дискретной математике. Сост.
|В. И. Ермаков], Т А. Ерохина, В. О. Локуциевский,
М. Н. Максименко, О. Л. Шеметкова. М. Изд-во Рос. экон.
акад., 2007 -91с.
Практикум составлен с учетом программы по дискретной
математике. В работе дается теоретическое изложение материала по каждому из
разделов дисциплины, а также задания для проведения практических
занятий.
Для студентов факультета информатики специальности 010502.65
«Прикладная математика (в экономике)» и экономико-математического
факультета специальности 0801.16.65 «Математические методы в
экономике».
© Российская экономическая академия, 2007
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ 4
Раздел I. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ 4
§ 1. Понятие множества 4
§2. Операции над множествами 8
§3. Метод математической индукции 17
§4. Повторение операций. Конечное число объединений
и конечное число пересечений множеств 21
§5. Мощность множества 24
§6. Бесконечные операции над множествами 26
§7 Разбиения и покрытия 30
§8. Использование операций над множествами при
формулировке поискового предписания в ИПС дескрипторного
типа 32
РазделП. ОСНОВНЫЕ ПОНЯТИЯ СЕМИОТИКИ 34
Раздел III. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ И ОТНОШЕНИЯ 42
§ 1. Определение декартова произведения двух множеств
и его свойства 42
§2. Определение и способы задания бинарного отношения 44
§ 3. Свойства бинарных отношений 47
§ 4. Отношение эквивалентности. 49
§5. Отношения порядка 52
§6. Упорядоченность множества 54
§7 Деревья, лексикографический порядок 56
§8. Операции над бинарными отношениями 59
§9 Понятие функции 61
§10. Декартово произведение п множеств 69
§11. Определение л-арного отношения 69
§12. Операции над «-арными отношениями 73
Раздел IV ТЕОРИЯ ГРУПП 82
§1. Бинарные операции 82
§2. Полугруппы и моноиды 83
СПИСОК ЛИТЕРАТУРЫ 90
3
ПРЕДИСЛОВИЕ
В связи с тем, что курс дискретной математики на
протяжении нескольких лет читается на двух факультетах академии,
возникла необходимость в издании практикума, в котором будут
изложены основные разделы этой дисциплины. Ранее были изданы
методические указания по первому разделу «Основы теории
множеств» и лекция по второму разделу «Декартовы произведения и
отношения». В данной работе мы дополняем первый раздел, вводя
счетные операции над множествами, так как считаем, что конечное
число операций над множествами не дает полного представления о
теории множеств, и добавляем много задач как к простым
операциям над множествами, так и к счетным операциям над
множествами. «Семиотика» выделена во второй раздел. Ранее раздел
«Декартовы произведения и отношения» был представлен в основном
в теоретическом аспекте, в то время как в данной работе появилось
много задач, причем бинарные отношения иллюстрируются с
помощью матриц. Также добавлен новый раздел «Теория групп».
Раздел I. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ
§1, Понятие множества
Понятие множества относится к неопределяемым понятиям
математики и логики. Как правило, это понятие объясняется с
помощью синонимов, таких, как набор, совокупность, собрание
однородных объектов. Эти объекты называют элементами
множества. Примерами множеств являются студенческая группа
(элементами этого множества являются студенты), коробка конфет
(элементы - конфеты), библиотека (элементы - книги). В математике
часто рассматриваются различные множества чисел, например,
четные числа, числа, кратные пяти, интервал от двух до трех. Эле-
4
ментами этих множеств являются точки на числовой прямой.
Множества обозначают прописными латинскими буквами А, В,
а их элементы - малыми латинскими буквами а, Ь,
Утверждение «элемент а принадлежит множеству А»
символически записывается следующим образом:
а еА,
а утверждение «элемент а не принадлежит множеству А»
записывается как
а &А.
Пример 1. Если в качестве множества А рассматривать
интервал (-2; 8), то число 1 принадлежит этому множеству, а числа
8 или 9 не принадлежат интервалу (-2; 8).
Записывается это как
1е(-2;8),
8 е (-2; 8),
9 г (-2; 8).
Множество, которое не содержит элементов, называется
пустым множеством и обозначается символом 0
Пример 2. Множество всех корней уравнения х2 + 1 = 0
является пустым множеством.
Если каждый элемент множества А принадлежит также и
множеству В (рис.1), то говорят, что множество А является
подмножеством множества В. Это обозначается А е В.
Рис. 1
Пример 3. Множество (-1, 6) является подмножеством
множества (-2; 8), что записывается как (-1, 6) с (-2; 8).
Пример 4. Множество чисел, кратных 4, есть подмножество
множества четных чисел.
5
Рисунки типа рис. 1 и другие подобные рисунки называются
диаграммами Венна.
Если множество А является подмножеством множества В и
одновременно множество В является подмножеством множества А.
то множества А и В называются равными.
Это записывается как
А = В
Выражение вида А- В называется теоретико-
множественным равенством, а выражение вида А а В или А^э В
- теоретико-множественным неравенством.
Если множество А является подмножеством множества В, и
при этом эти множества не являются равными, то А называют
собственным подмножеством множества В.
Множества бывают конечными и бесконечными.
Пример 5. Множество всех четных чисел бесконечно.
Пример 6. Множество всех целых двузначных чисел
конечно.
Задание 1
Вместо знака «?» поставить знаки е, ^, э, = и т. д.
Вариант 1 Вариант 2 Вариант 3
1?(-2;8); 0 ? (3; 7]; {1; 3} ? {1, 2; 4; 6}
2?[2;18); 1 ? (1; 3); [-3; 0] ? (-5; 1]
7? [-11, -7); 3?[3;6); {1} ? {1}
6? [9; 14); [-3;1} ? [-3;2] [-3;1} ? [-3;2]
2? {1,3; 5}; 3 ? {3}; [8; 10] ? (8; 10)
{1}?(-2;9); [-4; 1) ? (-4; 1]; 7 ? {7}
0?{0}; И; б)? И; 6]; {18}? [9; 20)
(-4; 6)?[-4; 6] {1; 3}?{1, 2; 4; 6} [2; 5)?[1; 6)
[-3;0]?(-5;1] [-4; 1) ? (-4; 1] [3; 7) ? [3; 8)
[8; 10|? (8; 10) [1,6)7(1,6 {!}?[!, 6)
6
Вариант 4
2 ? (2; 8)
{2} ? {2; 8}
{2} ?{2}
2? {2}
[4;5]?(3;6)
(1,3)?(0;4)
Р; 7] ? [1, 7]
{2; 8}? {1,2; 8; 9}
{1}?[0;2]
(0}?(-1,7)
Вариант 7
0?(-2;1)
1?(-1;4]
1?(-1;1]
(1}?(-1; 1]
2 ? {0; 1, 2}
{1,2}?{0;1;2}
[-3; 0] ? [-4; 1]
(-2; 0) ? [-2; 0]
[-2; 0) ? (-2; 0]
1?{1}
Вариант 10
3 ? (3; 8]
{3} ? [0; 3]
{1,2;3}?[0;3]
4?{1;4;5}
6 ? [0; 7]
(7; 8) ? [7; 8]
[0; 5] ? [0; 6)
[0; 5) ? [0; 5]
0 ? {7}
2? {2}
Вариант 5
2 ? [2; 3)
{2} ? [2; 3]
{3}?[2;4)
4 ? [2; 4)
0 ? [6; 7)
(2;3)?(1,4]
1?{1,3>
2?{1,3;5;7}
3 ? [0; 3]
[4; 5)? [4; 5]
Вариант 8
2 ? {2; 12}
3 ? (3; 15)
3 ? [3; 8)
8 ? [3; 8)
{3;4;5}?[3;8)
[-3; 1)?[-5; 2]
(7; 8)? (6; 9)
(2; 4) ? (1; 5)
[0;1]?[-1;2]
4? {4}
Вариант 11
1 ? (0; 1)
{1} ?(0; 1]
{2;3} ? [2; 3]
2?{1;2;3;4}
{2}?{1;2;3;4}
[-3; 0) ? [-5; 1]
(-4; 1] ? [-4; 1]
0 ? {-4; 0}
0?{4}
4? {4}
Вариант 6
3?{3;4;5}
6?[1;6)
2?(1;7)
{2}? (1,7)
{1;3;5}?[1,5]
{!}?[!, 7)
0?{8}
9?{1, 9; 17}
[2;3]?(1,4)
(2;3]?[2;3]
Вариант 9
2 ? (-2; 3)
{2}?(-2;3)
{2;3}?(-2;3]
{2;3}?(1;4]
{5}?(0;6)
[-7; 1]?[-8; 2)
(6; 9)? [6; 9]
(6; 8] ? [6; 8]
(2; 3) ? [2; 3)
0 ? [2; 3)
Вариант 12
6 ?{6; 7}
{6}? {6; 7}
-2 ? [-2; 3)
{1;2}?{1,2;4}
5? {5}
[-3; 0] ? [-4; 1]
0 ? [-4; 01
[-4; 0) ? [-4; 0]
7? {7}
0 ? [2; 3)
7
§2. Операции над множествами
Суммой или объединением двух множеств А и В называется
множество С, состоящее из всех элементов, принадлежащих хотя
бы одному из множеств А и В (рис. 2). Это обозначается А и В.
Рис. 2
Пример 1. Объединением множества четных натуральных
чисел и множества нечетных натуральных чисел является
множество всех натуральных чисел.
Если множества А и В имеют общие элементы, то каждый из
этих общих элементов входит в объединение только один раз.
Пример 2. Объединением множества А\ {1, 3, 5, 7} и
множества В: {2, 3, 4, 5, 6} является множество С: {1, 2, 3, 4, 5, 6, 7}
Пересечением двух множеств А и В называется множество
С, состоящее из всех элементов, принадлежащих как множеству А,
так и множеству В (рис. 3). Это обозначается как А г\ В.
( ф ;
Рис.3
Пример 3. Пересечением вышеназванных множеств А и В
(из примера 2) является множество {3, 6}.
8
Пример 4. Пересечением натуральных чисел, кратных трем,
и множества чисел, кратных двум, есть множество чисел кратных
шести.
Если множества А и В не имеют общих элементов, то
пересечением таких множеств является пустое множество.
Пример 5. Пересечением множества четных чисел и
множества нечетных чисел является пустое множество.
Задание 2
Выполнить операции над числовыми множествами.
Вариант 1
[-2; 8) п (-2; 7) -
[-2;8]п[7;9] =
[1;6]и[5;8] =
(1,6) и [6; 8] =
(1,7) о (7; 13] =
(1;7]п[7;8) =
[0;5)и[5;9) =
[0; 5) о [5; 9] =
(_оо; 0) п (-оо; -3) =
(-со;0)и[0;2] =
Вариант 3
[-2; 4) п 0 =
(-2; 4) и {4} =
[-3;5]п{5;6;7} =
(-3; 5) г, {4; 21, 28} =
(-3;6)^{4;6;7} =
(-2; 9) п (9; 10) =
(-2; 9) п [9; 10) =
(-2; 9] и (9; 10) =
(-2; 9] г» [9 ;10] =
(-2;0)и[0;3) =
Вариант 2
[-3;5)п(4; + оо) =
[-7;1)и(0; + оо) =
[-6;2)и(1;2) =
[-6;2)п(1;2) =
0 п (3; 7) =
[0; + <х,)о(0;5) =
(-6; 3] п [3; 4] =
[-2; 5) о (5; 9] =
[-2; 5) и (5; 9] =
{2; 3; 7}^ {3; 4; 5; 6}
Вариант 4
[-1,7) и (7; 8) =
[-1,7] и (7; 8) =
[-1;7]и[7;8) =
[-1, 7) о (7; 8) =
[-1;7)п[7;8) =
[-1; 71 о [7; 8) =
[-1;7]п[5;8] =
[-1,7] г» (5; 7) =
[_1,7)п(5;7] =
(_«,; 0) о (-2; + оо) =
9
Вариант 5
(-1,70]п(2;5) =
(-3; 4) и (2; 5) -
<-3;5)и(2;5] =
(-3; 5) о (2; 5] =
(-3; 5) о {0; 1,2; 7; 8} =
(-3; 5) и {0; 1,2; 7; 8} =
(-6; 8) о {8; 9} =
(-6; 8) и {8} =
(-6; 8) и 0 =
0 и (-со; + со) =
Вариант 7
0п(1,5) =
(0; 1) п { 0,2; 0,5 } =
(3}и(3;5] =
(4; 5) и [5; 6) =
(7; 8) о [8; 9) =
0 и [0; 1] =
(-со; + со) о 0 =
(-со; + со) о { 2 } =
(-3; 5) и { 5 } =
(-3;6)и[6;9] =
Вариант 9
(-1;0]и(-2;1) =
(-1, 4) о (2; 5) =
(-со; 5) п [2; 5] =
(-3; + со)^{-3;2;5;6} =
(-3;5)п{-3;1,2;5;8}=
(-3;5)и{-3, 1, 5; 7; 8}=
(-6; 8] о {8; 9} =
(-6;5)и{5}=
(-6; 3) о 0 =
{2} и (-со; + оо) =
Вариант 6
[-2;9)п(3;8] =
(-1,7) и (7;+ оо) =
0 и [3; 4) =
[3,4)и {4} =
(3;4)и{3} =
[3;4)и{4}=
[3; 4)п[3; 5; 4]=
[1,2)и[2;3] =
[1, 2] о [2; 5] =
(_оо; 0] О (-2; + со) =
Вариант 8
[-2; 5] о [5; 8] =
(-1,7) и [7; 9) =
[0; 3,5) о [3; 4) =
[3; 4) и { 3; 4 } =
(3; 4) п { 3; 3,5; 4 } =
[3; 4) о { 4; 5; 6 } =
[3; 4) и [3,5; 4,7] =
[1,6; 2) и [2;+ оо) =
(-со; 2] п [2; 5] =
(-со; 0] о (-4; 9) =
Вариант 10
[-2; 8) и (4; 8] =
[-1,7) и (7;+ оо) =
0 п (3; 4) =
[3;5)и{4;5} =
(3;4)о{3;5;6} =
[3;4МЗ;3,5;4} =
[3; + со)п[3,5;4] =
[1,2) и [2;+ оо) =
[1,2]о[2; + оо) =
[-со; 2] и (-2; + оо)=
10
Для операций объединения и пересечения выполняется пе-
реместительный закон, т. е. эти операции коммутативны
А^В=В^А (1)
АглВ=ВслА. (2)
Также для этих операций выполняется сочетательный закон,
т. е. они ассоциативны
(А^В)иС=А^(ВиС) (3)
(АглВ)пС = Ап(ВпС). (4)
Эти свойства операций следуют из их определений. Кроме
того, для этих операций выполняется распределительный закон,
т. е. они взаимно дистрибутивны
(А и В) п С = (А п С) и (В о С) (5)
(ЛпВ)иС=(ЛиС)п(5и С). (6)
Для желающих более серьезно разобраться в этих вопросах
докажем эти свойства.
Вообще, доказательства теоретико-множественных равенств
проводятся в обе стороны, т. е. для доказательства того, что А = 5,
показывают, что с одной стороны А с: В, а, с другой стороны,
что А^>В.
Вначале берется произвольный элемент х, принадлежащий
множеству, стоящему в левой части равенства, и доказывается, что
он принадлежит также множеству, стоящему в правой части
равенства. Это означает, что множество, стоящее в левой части,
является подмножеством множества, стоящего в правой части.
Далее, аналогичным образом, доказывается, что произвольный
элемент из правой части принадлежит множеству, стоящему в левой
части. Это доказывает, что множество, стоящее в правой части,
является подмножеством множества, стоящего в левой части. Из
определения равенства двух множеств следует истинность
теоретико-множественного равенства.
Докажем равенство (5). Пусть элемент х принадлежит
стоящему в левой части равенства (5) множеству Таким образом, хе
(А и В) гл С, т. е. х принадлежит множеству С и хотя бы одному из
множеств А или В. Но тогда х принадлежит хотя бы одному из
11
множеств А ел С или В г\ С, т. е. входит в правую часть
рассматриваемого равенства.
Обратно, пусть х е {А о С) и (В о С). Тогда х е Л о С или
хе ,6 глС, Следовательно, хеС, а также х входит в Л или в В, т е.
х е Л и#. Итак, равенство (5) доказано. Равенство (6)
доказывается аналогично.
Задание 3
Доказать тождества:
1)А^А=А;
2)АглА=А;
3)А^В = В^А;
4)АглВ = Вг>А;
5)А^(ВглС) = (АиВ)гл (Аи С);
6)Аг^(В^С) = (Аг^ В) и(Ап*С);
7)Лп(ВпО = (^пВ)пС;
8)А^(В^С) = (А^В)^С;
9)(А^В)г^А=А;
Щ(АпВ)иА=А;
11) (Асл В) ^{Ссл О) = (А ^С) п (ЯО С) о (Ли О) п (50 Л);
12) Л и 0=Л;
13)Лп0 = 0.
Теперь определим операцию вычитания множеств.
Разностью двух множеств А и В называется совокупность
тех элементов множества А, которые не содержатся в множестве В
(рис. 4). Это обозначается А \ В. Уточним, что В может не быть
подмножеством множества Л.
/:..
Рис. 4
Пример 6. На районную олимпиаду по математике
отбирают школьников, не имеющих тройки и двойки по этому предмету.
Тогда, если 6 «Б» класс некоторой школы обозначить за множество
А, а всех учащихся школы, имеющих тройки и двойки по
математике, обозначить за Ву тогда разность А \ В есть множество
учеников 6 «Б», имеющих четыре и пять по математике.
Пример 7. Разностью интервалов (-3; 8) и (-3; 6) является
полуинтервал (6; 8).
Обратим внимание на то, что операция разности, в отличие
от предыдущих операций, не коммутативна и не ассоциативна,
подобно операции вычитания чисел в арифметике. Из рис. 5
очевидно отсутствие коммутативности А\В Ф В\А
•О'
Рис.5
Покажем, что(А\В)\С *А\(В\ С).
Множество, стоящее в левой части, состоит из элементов
множества А, не являющихся при этом элементами ни множества
5, ни множества С, т. е. совпадает с множеством А \ (В ^С).
Множество, стоящее в правой части, состоит из элементов множества
А, не являющихся при этом элементами множества В, но при этом
элементы, являющиеся пересечением множеств А и В, и С, входят
в это множество. Таким образом, это множество совпадает с
множеством (А\ 5)и (А п С) (рис. 6).
13
в
Рис. 6
Симметрической разностью двух множеств А и В
называется сумма разностей А \ В и В \ А (рис. 7). Это обозначается как
ААВ.
Заметим, что А А В = (А и В) \ (В п А), так как
симметричная разность состоит из тех элементов множеств А и В, которые не
принадлежат^ и В одновременно.
-... в
-../ -^^ ^
А
А
Л
Рис.7
Заметим, что эта операция, в отличие от предыдущей,
является и коммутативной, и ассоциативной.
Пример 8. Так, если в качестве множества А взять числа,
кратные двум, а в качестве множества В - числа, кратные трем, то
симметрической разностью этих двух множеств будет множество
чисел, кратных двум и трем и при этом не кратных шести.
В математике и информатике часто приходится
рассматривать множества, являющиеся подмножествами некоторого другого
множества, которое играет роль основного множества. Эти
множества являются собственными подмножествами, и ни одно из них
не может совпадать с самим множеством.
14
Это могут быть, например, различные множества точек на
числовой прямой или множества файлов в некотором каталоге.
Если основное множество обозначить за 5, то дополнением
множества Л называется разность 8\А (рис. 8). Это обозначается как СА
или А
Рис. 8
Пример 9. Если в качестве основного множества 5
рассмотреть множество всех целых чисел, а в качестве А - множество
четных чисел, то дополнением множества А будет множество
нечетных чисел.
Сформулируем принцип двойственности:
1) дополнение объединения двух множеств равно
пересечению дополнений этих множеств (рис. 9)
А и В АглВ (7)
2) дополнение пересечения двух множеств равно
объединению дополнений этих множеств (рис. 10)
АслВ = А^В, (8)
Докажем равенство (7). Пусть хе А ^иВ, т. е. х & А и В,
таким образом, х не принадлежит ни множеству А, ни множеству 5,
х & А и х & В, следовательно хе Ли хеВ, что и означает, что
хе Асл В. Мы показали, что А^В с А о В Докажем
утверждение в другую сторону.
Пусть хе А г\ В следовательно, хе А и хе В, что означает,
что х & А и х ё В, т. е. х не принадлежит ни множеству А,
ни множеству 5, следовательно, хе А^В. Показали, что
15
А г\ В с: А^>В Следовательно, равенство доказано. Равенство
(8) докажите аналогичным образом самостоятельно.
Задание 4
Доказать тождества:
I) А\В=АпВ,
2)ААВ = (АиВ) (АпВ);
3) А*иВ А п~В ,
4) А\В =А иВ;
5) ААВ =(А о В)и(4пВ);
6) А\(В\С) = Л и (Л о С);
7) Асл{В\С) = ЛиЯ^ С;
8) (А \В) А (В \ С) =(А\В) А (В \ С);
9) А\(В^С) = (А\В)п(А\С);
10) Л \ (В о С) = (А \В) и (4 \ О;
II) (у1и0)и I = V;
12) Л\(Л\В)=ЛпБ;
13) (Л\В)и;Я = Л;
14) А\0=А;
15) 4\Л = 0;
16) А о (5 А С) = (А о 5) А (А о С);
17) (ЛДЯ)^ (А АС) = (А^ВиС)\(АъВъС);
18) (Л\Я)ДЛ=ЛпЯ;
19) (А\В)АВ=А^В;
20) 4Д(ЛоЯ)=Л\Я;
21) ЛД(4иЯ) = В\Л;
22) Аг^(ААВ)=А\В;
23) Л^(ЛД.В)=Л^Б;
24) АА(ВАС) = (А АВ)АС;
25) Л Д0=Л;
26) А АА = 0.
16
Задание 5
Упростить.
1) А\(А\В) = ,
2) ((А^В)гл А)г^В=
3) А А (А и В) =
4) А А (Л п В)= ,
5) (Л\В) и (В\С) и (С\4)= ,
6) ((Ли#)\Д)\Я = ,
7) ((Л ДЯ)п ( Ли(Я\Л))) \А = 9
8) ((4ДВ)и ( 4и(Д\Л)))\Л = ,
9) ((Ап(А ЬВ))и(А\В)) и (Л пВ) = ,
10) ((Лп(4ДВ))и(Л\Я)) п(ЛпЯ) = ,
11) (Л п (ЛАЯ)) и (4 \ Я) и(Лп5) =
§3. Метод математической индукции
В математике при доказательстве утверждений часто
используется метод математической индукции.
Индукция бывает полной и неполной. Приведем примеры
неполной математической индукции.
1 Доказать, что любое число п, такое, что 2 < п < 15,
является либо простым, либо произведением не более чем трех простых
множителей.
В этом примере доказательство проводится непосредственно
перебором всех чисел 2 < п < 15
2. Правило треугольника.
V аУ Ь \а+Ъ\<\а\ + \Ъ\
Здесь доказательство проводится перебором всех возможных
случаев:
1) а>0, 6>0; 2) а<0, Ь<0; 3) я>0, 6<0; а) |д|<|6|; б) |а|>|6|
4)а<0,6>0;а)|а|>|6|,б)И<|6|.
3. ЕслиР(п) =п2 +п +41, тоР(п) - простое число.
17
В данном случае очевидно, что полный перебор невозможен.
Но если вместо п последовательно подставить натуральные числа,
то оказывается, что Р(п) - простое число для любого п. Но это
утверждение ошибочно. Рассмотрим Р(40).
Р(40) = 402 + 40 + 41 = 40(40 + 1) + 41 = 40 41+41=41*
В случаях, когда полный перебор невозможен, неполная
математическая индукция неприменима. Тогда применяют принцип
полной математической индукции.
Суть этого принципа состоит в следующем: если некоторое
предложение А(п)9 где п - натуральное число, истинно для п = 1
(или при другом значении п, при котором имеет смысл это
утверждение) и из предположения его справедливости для некоторого
натурального значения п = к следует справедливость утверждения
для следующего натурального значения п = к + 1, то утверждение
справедливо для всех натуральных значений п.
Пример 1. Доказать методом математической индукции
формулу суммы п членов арифметической прогрессии
о я,+ а„
п 2
Доказательство:
1. База индукции: докажем истинность предложения при
л=1.
Л1 = аг = — --1
1 * 2
2. Индукционное предположение: предположим, что при
п = к утверждение истинно.
к 2 *
3. Индукционный шаг: исходя из предположения, что
формула верна при п = к, докажем ее истинность при п = к+1.
с -? +п -а1+ак и , п . (ат + а\ + с*'{к-\))к + 2а, + 2</, ^к _
^к+х ~ ^к + ак+\ ~ ~ К + ак+\ ~ " -
18
ах (к + \) + а{ к+с1-(к-1)-к + а]+с1к+с1к _
. _ _
а^к + \) + ал(к + 1) + с1\к2 - к + к + к) _ ах +(а{ +с1к) „
(* + 1>:
2 2
*+*" Ч* + 0
2
4. Вывод: так как утверждение истинно для /7=1,
следовательно, на основании индукционного шага оно истинно для п = 2,
далее для п = 3 и т. д. для любого натурального /7.
Задание б
Доказать методом математической индукции следующие
выражения:
1) формулу суммы геометрической прогрессии:
_Ж-1)
формула суммы геометрической прогрессии, где
ц - знаменатель прогрессии, Ъх - первый член;
2)1 + 2+ +„=^1>,
3)1Ч22 + +й1 = "0и-1Х2я + 1)
.2 , оз , , „з и2(" + 1)2
4) Г+ 2*+ + и*=-
4
5)12+32+52 + + (2л-1)
2 ,12 , в2 , , ,„.. 1Ч2_я(2л-1)(2л + 1)
6)1-2 + 2-3+ +и(л + 1) =
3
л(л + 1)0? + 2)
3
7) для любого п. 5й + 4" -1 кратно 8;
8)1 + 3 + 5+ +(2и-1) = л2
9) I2 +з2 +52 +... + (2«-1)2 = "(4"2~1)
19
10) 1 2 + 2-3 + Нгг-Вп={П-1)П3(П + 1)
11) + + +
13 3 5 (2л-1)(2/1 + 1) 2и + 1
,„ч 15 оз з гг2(п + \) (2и2+2л-1)
12) 15+25 + +п =—- — -,
12
13) доказать, что для любого п (37"+2 + 16л+! +23") кратно 7
(ие/У);
14) доказать, что для любого п (7а + 3)2и+1 + (1Ъ + 25)2и+1 кратно
7;
15) доказать, что для любого п 722п+2 - 472и + 282""1 кратно 25;
16) доказать, что для любого п, а и Ь (ап—Ь") кратно
(а -Ь);
17) доказать, что для любого п,акЬ (а2п~1 + Ь2п~]) кратно (а+Ь);
18) доказать, что для любого п,аиЬ (а2п - Ь2п) кратно (а+Ь);
19) доказать, что для любого п 52""1 • 2П+1 +3"+1 22""1 кратно 19;
20) доказать, что для любого п 32(л+1) • 52" - 33п+2 22л кратно 117;
21) доказать, что для любого п 72" + З2" + 30 • 2 Г кратно 16;
22) доказать, что для любого п п4 - 2п3 +1 \п2 + 62п кратно 24;
23) доказать, что для любого п 2пъ — Зп2 +п кратно 6;
24) доказать, что для любого п 30" 4- 4"(3" - 2п) -1 кратно 11,
25) доказать, что для любого п 2 +3 кратно 19;
26) доказать, что для любого п 36п + 35"+1 + 34п+] +3" кратно 8;
27) доказать, что для любого п п$ + Ап1 + 6п6 + Ап5 + п4 кратно
16;
28) доказать, что для любого п 12п - А2п - 33 кратно 528;
29) доказать, что для любого п 33"+3 - 26л - 27 кратно 676;
30) доказать, что для любого п 42п - З2" - 7 кратно 84;
31) доказать, что для любого и 32и+3+40и-27 кратно 64;
20
32) доказать, что для любого п 36"+10-3" кратно 11,
33) доказать, что для любого п п9 - п5 кратно 30;
34) доказать, что при любых нечетных йГ + 2ЧЗЧ + тп
делится на 1 + 2 + 3+ +т,
35) доказать, что при нечетнохМ п>Ъ целое число
(1 + - + - + + + + ) • (и -1) ! кратно п;
2 3 /2-3 /2-2 л-1
36) доказать, что при любом натуральном п число 5 • 23""2 +33""1
кратно 19;
Юй+1 -9/2-10
37) доказать, что 3 + 33+ +33...3 = тюип^ N
^ у ' 27
п
38) доказать равенство -у 2 + л/2 + = 2С08 7Г ПРИ л € ^
V у ' 2"
п
39) доказать справедливость неравенства для всех натуральных
13 5 2/2-1 1
п>\ < ,
2 4 6 2/2 /3/2 + 1
§4. Повторение операций. Конечное число объединений
и конечное число пересечений множеств
Если есть п множеств А\,А^.., Ап-> то можно взять
объединение п множеств и пересечение п множеств. Эти операции введем
с помощью метода математической индукции:
а) операция объединения п множеств обозначается как
й а,..
1 = 1
При п = 1 результатом этой операции будет множество А \
21
Предположим, что при п < к -1 операция объединения п
множеств определена, и определим ее при п = к следующим
образом:
1=1 7=1
б) операция пересечения п множеств обозначается как
1=1
Введите самостоятельно индуктивное определение
пересечения п множеств аналогичным образом.
Для этих операций имеют место законы дистрибутивности
операций объединения относительно операции пересечения и
операции пересечения относительно операции объединения.
1. Вг,((]А,) = ()(В^А;) (9)
2=1 1=1
2.Ди<П4) = П(Ди4) <10)
1=1 1=1
Также для этих операций имеет место закон двойственности.
10Д=П4 (П)
1=1 7=1
2. ПД = Щ (12)
7=1 /=1
Докажем методом математической индукции формулу (11).
Шаг 1. Индукционное основание: если п - 1, то имеет место
тривиальное равенство Д. = Д
Шаг 2. Индукционное предположение: предположим, что
формула (11) имеет место при п<к — \
Шаг 3. Индукционный шаг Докажем формулу при
~ Та
п ~ к (Ы Л ) = (Ы Д') ^ А (по закону двойственности для двух
2=1 2-1
22
к~\
множеств (7)) = |^| Д г\ А к.. ..(по индукционному предположению)
/=1
к-Л к
1 М
Шаг 4. Индукционное обобщение. Так как формула (11)
имеет место при п = 1, с помощью индукционного шага получаем,
что она имеет место при л = 2, я = 3 и т. д. для любого п.
В качестве упражнения докажите самостоятельно формулы
(9), (10), (12).
Задание 7
Методом математической индукции докажите следующие
тождества и утверждения:
т п п т
< 11<1К)=1к1К)
/=1 у=1 з=\ 1=1
т п п т
2-П<ГК)=П<ГК>
1=1 /=1 ;=1 1=1
3. (0д.)\Л = 0(Д\Л)
;=1 1=1
4.(П4)\Д = П(4\Д)
»=1 1=1
5.5\(У4) = П(5\4)
/=1 1=1
б.5\(П4) = й(^\4)
;=1 /=1
7 Доказать, что если V / Д с: В, то (^ Д с: 5
/=1
п
8. Доказать, что если V / Д. с5, то (| Д с: 2?.
1=1
23
п
9 Доказать, что (^Д есть наименьшее множество, содер-
жащее все множества А \, ^2,..., Ап
п
10. Доказать, что есть наибольшее множество, содер-
жащееся во всех множествах А ь А2,... Ап-
§5. Мощность множества
Имеем два множества - М и N. Пусть/- отображение
множества М на множестве N.
Это обозначает как / М —>И
При отображении/каждому элементу множества М
соответствует некоторый элемент множества М, т. е. \/а а еМ
ЗЪ Ъ е N Да) = Ь
Если при отображении / у каждого элемента множества N
есть элемент множества М, которому он соответствует, т. е. \/Ь
Ъ е N За а^М /(а) = Ь, то такое отображение называется
сюрьективным или отображением «на».
Если при отображении/различным элементам множествам
соответствуют различные элементы множества N. т. е. \/а \/Ь
а €М Ъ €М афЪ,-=>/{а)Ф /(Ь), то такое отображение
называется инъективным.
Отображение, которое одновременно является инъективным
и сюрьективным, называется биективным или взаимно
однозначным соответствием.
Два множества М и N называются равномощными, если
между ними можно установить взаимно однозначное соответствие.
24
Пример 1
Множество натуральных чисел и множество четных чисел
являются равномощными, так как между ними можно установить
взаимно однозначное соответствие /(п) - 2п
12 3 4..
111 1
2 4 6 8..
..п
1
Рис.9
Пример 2
Множество натуральных чисел, кратных 3, и множество
натуральных чисел, кратных 5, являются равномощными.
Взаимно однозначное соответствие /(п) ~—п
3
9
5 10 15
1
...2и
Рис. 10
Множества, равномощные множеству натуральных чисел И,
называются счетными.
Из курса математического анализа вам должно быть
известно, что множество рациональных чисел 0, является счетным, а
множество действительных чисел счетным не является. Множество
конечного множества совпадает с числом его элементов, так как
между ними и множеством Ып - {1, 2,..., п) можно установить
взаимно однозначное соответствие. Это число для множества А
обозначим т{А).
Для мощностей верны следующие утверждения:
1. т(Л\В) = т(А)-т(АглВ)
25
2. т(А и 5) = т(А) + т{В) - т(А гл В)
3. В частности, если А о В = 0, то т(Л ^иВ)~ т(А) + /я(#)
4. /и(Л ^ Л и С) = /я(Л) + го(Д) + т(С) - т(А п 5) - /и(Л п С) -
- т(ВпС) + т(АглВпС)
Задание 8
1. В 11-х классах 49 учеников. Из них 29 пьют, 37 курят,
а 3 не пьют и не курят. Сколько учащихся пьет и курит
одновременно?
2. Из 1000 обследованных в онкологическом диспансере
мужчин 700 курят, а 400 имеют рак легких, при этом 250 курящих
мужчин имеют рак легких:
а) сколько некурящих мужчин не имеет рак легких?
б) сколько некурящих мужчин имеет рак легких?
3. В доме проживает 200 семей, из которых 180 имеют
компьютер и 150 имеют автомобиль, при этом 14 семей не имеют
компьютер, но имеют автомобиль.
Определить:
а) сколько семей не имеет ни компьютера, ни автомобиля?
б) сколько семей имеет и то, и другое?
в) сколько семей имеет компьютер, но не имеет автомобиля?
г) сколько семей имеет либо то, либо другое?
д) сколько семей не имеет ни того, ни другого?
§6. Бесконечные операции над множествами
Операции объединения и пересечения множеств могут быть
обобщены для бесконечного случая, т. е. число взятых
объединений и пересечений может быть счетным, а не равным конечному л,
как в предыдущем случае.
Введем это определение.
Объединением множеств А1 называется множество В такое,
что для каждого элемента х множества В существует такое
множество А{, что х е Д.
26
Уд. =в = {х\31 хеД}
Пересечением множеств Д называется множество Я,
такое, что каждый элемент х множества В принадлежит всем
множествам Д.
р|Д,=В = {х\У1 хеД}
Заметим, что все утверждения § 3 для конечного числа
объединений и пересечений имеет место и для бесконечного числа
объединений и пересечений.
Докажем принцип двойственности.
СМ=П4
I
Докажем, что левая часть лежит в правой части.
Пусть х Е (У Д ), т. е. л: ^ 1^^ э следовательно, х не входит
ни в одно из множеств Д, а это, в свою очередь, означает, что х
принадлежит каждому из дополнений Д , т. е. х е [| Д ,
следовательно, (Уд)сР|д
Обратно, пусть х Е Г| Д , т. е. х входит в каждое из
множеств Д. Таким образом, х не входит ни в одно из множеств Д , а
это обозначает, что х не принадлежит объединению Д , т. е.
х е УД Получим: Р|Д е (УД-) ■
-1
Докажите аналогичным образом, самостоятельно, свойства
(9), (10), (12) для счетного числа объединений.
27
Задание 9
Переформулировать и доказать все 10 свойств из задания 7
для случая счетного числа объединений.
Задание 10
Найти [^)Ап и \\Ап , где множества^ определены сле-
п п
дующим образом:
п
2. д,=[0; 1)
П
3.4,=[0;1].
И + 1 И
/7 -Ь-1 А?
Задание 11
Найти УД,,р|#„, где 2?и =^л\^4я+1, а множества Д, оп-
т п
ределены следующим образом:
1. 4,=[0; -].
п
2. Д,=[0; -)
28
Задание 12
Найти у Ап и \\Ап , где множества Д, определены сле-
п п
дующим образом:
I. Д, = (2--, 3 + -1-]
п п + 1
2. д, = [з--; 4+-^-)
и я + 2
3.4 =[5-1; 4+ -2-]
Л /7 + 2
4. Ап =[5 + 1; 4 + -3-]
л и + 2
5. 4 =(6 + 1; 9-1)
п п
6. 4 =[-4-1; 1 + 1]и(5-1; 6 + 1]
п п п п
7 4 =[-8-1, 1 + 1)и(6--; 6 + 1]
п п п п
5 1 14
8. Ап =[-7--; 2 + -]и(3—, 5ч--)
п п п п
.4/1 + 5 10и + 16п
9 4 = ( ; Н
и п + 1
10. 4 =["2-1; — )и(2 —; 2 + -1-)
л л+1 и+2 и+4
II. 4 =(2-1 3 + !]и(6—!-; 7 + -1-].
п п п+2 п+\
29
Задание 13
Выберем на оси Ох точку Ах (х0, 0). Проведем прямую
через точки С(1, 1) и Ах (х0 , 0). Полученный треугольник назовем
множествами А Найти \\Лх9 \^)АХ.
1<д:<оо 1<л:<оо
С^1Д)
4Л*ь;0)
Рис. 11
Задание 14
Треугольник, симметричный треугольнику Ах
относительно прямой у = х, назовем Вх
Найта 1}(АхАВх)а [)(АХЫЗХ)
1<х<оо
1<л<оо
§7. Разбиения и покрытия
Представление заданного множества в виде объединения
системы множеств, не имеющих попарно общих точек, называется
30
разбиением. Таким образом, если есть множество А, такое, что
А \] В, где для любых Д и 57 , 5, с\В}= & то система {В; }
есть разбиение множества А (рис. 12).
Рис. 12
Очевидно, что множества могут обладать различными
разбиениями.
Пример 10. Множество целых чисел можно представить в
виде объединения множества четных чисел и множества нечетных
чисел, с одной стороны, а также в виде объединения множества
чисел, кратных трем, множества чисел, имеющих при делении на 3
в остатке 1 и множества чисел, имеющих при делении на 3 в
остатке 2, с другой стороны.
Аналогичным образом можно построить сколько угодно
разбиений множества натуральных чисел. Для любого натурального
числа т разбиение всего множества натуральных чисел образуется
т подмножествами: А1 , А2 , ...9Ат> где А> состоит из чисел,
дающих при делении на т остаток 1-1
Любое множество подмножеств множества А, объединение
которых есть множество А, называется покрытием множества А
п
Следовательно, если есть множество А, такое, что А = II 5,,
1=1
то система {В^} есть покрытие множества Л (рис. 13).
31
А,
А 4с:
/ А*
Рис. 13
Таким образом, разбиение есть частный случай покрытия,
т. е. это покрытие, в котором множества Д не пересекаются.
Пример 11, Множество натуральных чисел можно
представить в виде объединения множества нечетных чисел, множества
чисел, не делящихся на три, и множества чисел, кратных шести.
Очевидно, что эти подмножества не являются
непересекающимися: к примеру, 7 принадлежит как множеству чисел, неделящихся
на 3, так и к множеству нечетных чисел.
Пример 12. В урне находятся белые, черные и двухцветные
шары. Тогда множество всех шаров можно представить в виде
объединения двух множеств: множества шаров, имеющих в
окраске белый цвет и множество шаров, имеющих в окраске черный
цвет.
§8. Использование операций над множествами при
формулировке поискового предписания в ИПС
дескрипторного типа
До настоящего момента в нашем изложении никаких
понятий, требующих каких-то познаний в информатике, не возникало.
Правда, мы предполагаем, что каждом}7 приходилось создавать
файл, сохранять его на диске, а также работать в дальнейшем с
32
этим файлом, вызывая его на экран. Таким образом, мы считаем,
что каждый решал, пусть в самом простейшем виде, задачу поиска
единицы информации. Также жаждый из нас пользовался
каталогом в библиотеке или искал нужное слово в словаре, т. е. всем
приходится в какой-то степени заниматься информационным
поиском.
Предметный каталог в библиотеке - это наглядный пример
классификации информации. Все книги библиотеки делятся по
областям знаний, а в каждой области - по предметам, далее - по
более узким специализациям. Если вам нужна книга по
математической логике, то в начале вы выберете естественно-научный
раздел, затем - подраздел математики, а в нем - подраздел
математической логики. Информация на диске записывается аналогичным
образом. Подобные структуры хранения информации используют
естественным образом понятия теории множеств.
Информационный поиск есть процесс отыскания в
некотором множестве всех таких текстов, которые посвящены указанной
в запросе теме или содержат нужные потребителю факты,
сведения.
Информационный поиск осуществляется посредством
информационно-поисковой системы (ИПС). При информационном
поиске отыскиваются такие и только такие факты или сведения,
которые были введены в ИПС. Перед вводом в ИПС текста
определяется его основное смысловое содержание, которое затем
переводится и записывается на одном из информационно-поисковых
языков. Эту запись называют поисковым образом текста.
Остановимся подробнее на примере библиотеки. Существует
единая всемирная система УДК «Универсальная десятичная
классификация», т. е. каждой теме соответствует номер в этой
классификации. Например, тема «Математический анализ» имеет
запись 517.1, а книги по информатике имеют запись 618.3.06.
Таким образом, для множества всех книг в мире имеется
разбиение согласно этой классификации: все книги одной
тематики принадлежат одному подмножеству и имеют одинаковый номер
в УДК.
33
Также в любой библиотеке каждая книга имеет собственный
шифр, таким образом, существует взаимно однозначное
соответствие между множеством книг и множеством существующих
шифров. Множество всех шифров есть также пример разбиения.
Информационно-поисковой системой называется
совокупность информационно-поискового языка, правил перевода с
естественного языка на информационно-поисковый и обратного
перевода, а также критерия соответствия. Прежде чем ввести понятие
информационно-поискового языка познакомимся с основными
понятиями семиотики - науки, исследующей свойства знаков и
знаковых систем как естественных, так и искусственных языков.
Раздел II. ОСНОВНЫЕ ПОНЯТИЯ СЕМИОТИКИ
Математика является наукой, в которой все истины
доказываются с помощью умозаключений. Поэтому для математики
большое значение имеют логические теории как средства
построения математических знаний. А. А. Марков дает определение
математической логики как науки о хороших способах рассуждения.
«Но для того, чтобы обслуживать точнейшую науку - математику,
- считает А. А. Марков,- сама логика должна быть точной наукой.
Это значит, что она должна иметь дело с точными понятиями и
применять точные методы, как и математика». Определенная
ступень абстракции любой научной теории требует создания
специальной символики для обозначения понятий этой теории и для
записи ее общих выводов.
Введение в логику специальных символов дает возможность
формулировать ее законы в самом общем виде. «Мы употребляем
знаки не только для того, чтобы передать наши мысли другим
лицам, но и для того, чтобы облегчить сам процесс нашего
мышления» (Г В. Лейбниц). Термин «знак» в семиотике понимается в
широком смысле как объект произвольной природы, которому при
определенных условиях, образующих знаковую ситуацию,
поставлено в соответствие некоторое значение.
34
Набор знаков данного языка называется его алфавитом, а
сами знаки - буквами этого языка. Таким образом, мы здесь
несколько обобщаем понятие буквы. Так, в этой интерпретации
буквами русского языка являются как обычные русские буквы, так и
знаки препинания, и пробел. Для вышеприведенного примера
УДК буквами являются арабские цифры, точка и пробел.
Далее, из букв можно строить слова.
Слово определяется следующим образом:
- любая буква есть слово;
- если А - слово и В - слово, то АВ - также слово (рис. 14);
- пустое слово (слово, не содержащее букв) есть также слово.
Рис. 14
Таким образом, слова строятся с помощью операции
приписывания, т. е. к слову А приписывается справа слово В.
Операцию приписывания также называют конкатенацией.
Пример 1. Имеем алфавит П = {а, Ъ, с}, тогда а, Ь, с, аЪг
аас, асе, асЪ - суть слова в данном алфавите. Далее, если ас -
слово и Ъаа - суть слова, то асЪаа есть слово, являющееся
результатом приписывания слова Ъаа к слову ас.
Если два слова А и В построены из одинаковых букв,
расположенных в одинаковом порядке, то в дальнейшем мы будем
говорить, что слова А и В графически равны. Так, слова «апшжэбк» и
«апшжэбк» графически равны.
Графическое равенство двух слов записывается как А = В.
Число букв в слове будем называть его длиной. Длину слова
А будем обозначать как | А | Очевидно, что если два слова
графически равны, то они имеют одинаковую длину.
Условимся считать, что пустое слово имеет длину, равную 0.
35
Заметим, что при приписывании слова В к слову Ау
получаем слово, длина которого есть | А + В \
Изучим основные свойства операции приписывания:
1) операция приписывания не коммутативна
АВ Ф ВА\
2) операция приписывания ассоциативна
(АВ)С = А(ВС);
3) если слова А,ВиС таковы, что АС = ВС, тоА=В;
4) если слова А, В и С таковы, что СА = СВ, тоА=В.
Последние два свойства называют также правилами
сокращения.
Введем ряд новых определений: слово В называется началом
слова А (или его префиксом), если существует слово С, такое, что
А = ВС (рис. 15).
Слово С называется концом слова А (или его суффиксом),
если существует слово В, такое, что А = ВС (рис. 15).
Рис. 15
Например, слово «портрет» имеет префикс «порт» и суффикс
«рет». Также оно имеет префикс «пор» и суффикс «трет», так как
очевидно, что слово может иметь несколько префиксов и
суффиксов.
Префиксы и суффиксы имеют следующие свойства:
1. Любое слово есть префикс самого себя. Это очевидно, так
как существует пустое слово, и любое слово есть конкатенация
самого себя и пустого слова.
2. Любое слово есть суффикс самого себя. Доказывается, как
и первое свойство из существования пустого слова, так как любое
слово есть конкатенация пустого слова и самого себя.
3. Пустое слово есть префикс любого слова. Доказательство
этого факта содержится в доказательстве первого свойства.
4. Пустое слово есть суффикс любого свойства.
Доказательство этого факта содержится в доказательстве второго свойства.
36
5. Если А есть начало В, а В есть начало С, то А есть начало
С (свойство транзитивности префиксов).
Докажем это свойство. Если А есть начало В, то существует
слово Д такое, что В = АО. Так как В есть начало С, то существует
такое слово Е9 что С = ВЕ. Тогда С = ;4/)Е и Л есть начало С.
6. Если А есть конец В, а, В есть конец С, то Л есть конец С
(свойство транзитивности суффиксов). Доказывается аналогично
свойству 5.
7 Если А и В суть начала слова С, то Л есть начало В или 5
есть начало^.
Имеем С = ;Ш и С = #Е. Далее, если Л длиннее, чем В, то Л
есть начало А, иначе Л есть начало В (рис. 16).
<* Я»-«Я V
Рис. 16
8. Если А и В суть концы слова С, то Б есть конец А или Л
есть конец В. Имеем С = ОА и С = ЕВ. Далее, если А длиннее, чем
В, то В есть конец Л, иначе А есть конед5 (рис.17).
4. *«« ►
■4
1
5, ,
~~&~4
,'
~~{&,
;
^г *Р^ **
Рис. 17
Эти два последних свойства называют законами двух начал
и двух концов соответственно.
37
Говорят, что А - собственное начало В, если А - начало В и
А -В. Соответственно, А - собственный конец В, если А конец В
иА= В. Тогда эти два закона можно усилить следующим образом:
9. Если А и В суть собственные начала слова С, то А есть
собственное начало В или В есть собственное начало А.
10. Если А и В суть собственные концы слова С то А есть
собственный конец В или В есть собственный конец А.
11. Слово А тогда и только тогда есть начало слова ВС, когда
имеет место одно из двух: А собственное начало слова В
(рис. 18) или А имеет вид ВО, где В - начало С (рис. 19).
«91 *►«*■
Рис. 18
Рис. 19
12. Слово А тогда и только тогда есть конец слова ВС, когда
имеет место одно из двух: А - собственный конец слова С (рис. 20)
или А имеет вид ВС, где В - конец В (рис. 21).
Рис. 20
38
Рис. 21
Слово С есть подслово слова А, если существуют такие слова
В и О, что А имеет вид ВСО (рис. 22).
'/ ' '''
о
4 - -
г
с
я
Рис. 22
Соответственно слово С есть собственное подслово слова А,
если существуют такие слова В и О, что А имеет вид ВСО и хотя
бы одно В или О не пусто. Например, слово «вид» есть подслово
слова «очевидно».
Задание 15
1. Найти все префиксы и суффиксы слов своего варианта.
2. Выписать общие префиксы этих слов.
3. Какой максимальный общий префикс этих слов?
4. Какой максимальный общий префикс первых двух слов?
5. Выписать общие подслова второго и третьего слов.
6. Выписать все подслова второго слова.
Вариант 1
сорока
соковыжималка
сонливость
Вариант 2
умывальник
умышленный
умопомрачение
39
Вариант 3
окрошка
окорока
окна
Вариант 5
золотоносное
золотистый
зол
Вариант 7
оранжерея
оранжевый
оригон
Вариант 9
фрагмент
фракция
фрамуга
Вариант 11
основа
оснащение
основоположник
Вариант 4
особняк
особи
особенность
Вариант 6
одеяло
одесский
одежда
Вариант 8
кардамон
кардан
кардиолог
Вариант 10
мундир
мундштук
муниципальный
Вариант 12
притча
притон
приторный
Кодом называется такое множество слов, которое само
может играть роль алфавита.
Более строгое определение кода следующее.
Множество слов {61 , Ъ2 ,... , Ьп } в алфавите П = {а\ , а2,...
,ат} называется кодом, если не существует таких перестановок
{/1, /2,... , и } и {л *к ,• • и } символов {1, 2,..., я}, что
Ь\\ Ъа Ьы - Ъл Ь]2 6,
]»'
п)
Таким образом, какие бы перестановки символов {1,2,
не взяли 6,1 Ъа &,■„ & Ьд 6;2 &,-„.
Пример 2. Так, множество слов {аЪ, ЬЪ) является кодом, а
множество слов {а, аа) кодом не является.
Пример 3. Множество слов русского языка вместе с
пробелом также является кодом, но это же множество слов без пробела
кодом не является.
40
Так, слово «соковыжималка» является сочетанием слов
«сок», «о», «выжималка». Понятие кода имеет большое значение
для прикладных целей. Кодом, например, является азбука Морзе.
Задание 16
Являются ли кодом следующие множества слов:
1) {а, аЪ}\
2) {а, аа, аЪ},
3) {а, ЪЪ, с};
4) {а, ЪЪ, се, Ьс}у
5) {а, аЪ, ааЪ, аааЪ};
6) {а, аЪ, аЪа, аааЪ};
I) {а, аЪа, аЪааЪ}:
8) {а, аЪа)\
9) {а, ааа, аааа};
10) {ааЪ, аааЪ};
II) {а, аЪ, ас, Ъс};
12) {а, аЪа, аЪЪа, аЪЪЪа, аЪЪЪЪа)
Итак, познакомившись с основными понятиями семиотики,
вернемся к ИПС. Проанализируем, что представляет собой запись
в УДК. Это иерархическая система, в которой префикс длины 3
означает более широкую тему.
В большинстве информационно-поисковых языков основной
словарный состав задается его перечислением и представляет
собой фрагмент лексики того или иного естественного языка.
Отобранные из естественного языка слова и словосочетания, в
совокупности образующие основной словарный состав, служат как бы
алфавитом данного информационно-поискового языка. В
некоторых информационно-поисковых языках основной словарный
состав задается методом порождения, который заключается в том,
что для таких информационно-поисковых языков правила
образования устанавливают, как из данного алфавита строить слова
информационно-поискового языка, а из этих слов - фразы.
Дескриптор есть лексическая единица информационно-
поискового языка, служащая для описания основного смыслового
41
содержания документов. Таким образом, дескрипторы служат для
формулировки информационных запросов при поиске документов
вИПС.
Раздел III. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ
И ОТНОШЕНИЯ
К изучению данного раздела можно приступать лишь после
изучения основ теории множеств.
В данном разделе даются определения и примеры
декартовых произведений и отношений над множествами, а также
введены основные операции над множествами. Кроме классических
операций над множествами вводятся также реляционные
операции. В работе сделана попытка, основываясь на принятых в нашей
стране определениях, познакомить студентов с реляционными
операциями над множествами. Самостоятельное чтение
американской литературы может вызвать затруднения у студентов из-за
различного подхода к понятию отношения, принятого в разных
странах. Изучение этих операций целесообразно, так как они
широко используются в прикладных целях.
§ 1. Определение декартова произведения двух множеств
и его свойства
Декартовым или прямым произведением множеств А и В
называют множество АхВ всех упорядоченных пар элементов (а, Ь),
где а е А, Ь е В. Элементы а и Ь называют при этом
компонентами или координатами пары (а, Ь). Соответственно, а называется
первой координатой пары, а Ъ - второй координатой пары.
Если одно из множеств А или В пусто, то произведением
АхВ будет пустое множество.
Известным примером декартова произведения является
множество декартовых координат в прямоугольной системе коор-
42
динат, с заданными взаимно перпендикулярными осями
координат, на каждой из которых выбрано положительное направление и
задан отрезок единичной длины.
Тогда каждая точка на плоскости имеет две координаты:
первая называется абсциссой, а вторая - ординатой.
Свойства декартова произведения:
1) декартово произведение не коммутативно
А хВФВхА,
2) декартово произведение не ассоциативно
{{А хВ)хС)*(Ах(Вх С)).
Для доказательства первого факта достаточно привести
пример, когда коммутативность (переместительный закон) не
выполняется.
Пример 1. Пусть А = {1}, В = {2, 3} Тогда
ЛхД={(1,2),(1,3)},
ЯхЛ = {(2, 1),(3, 1)}
Обратим внимание, что в случае, если А-В,
переместительный закон имеет место. Для доказательства второго факта
достаточно привести пример, когда не выполняется ассоциативность
(сочетательный закон).
Пример 2. Пусть А={1}9 Я={2}, С={3} Тогда
((/4х5)хС)={((1, 2), 3)}, т. е. декартово произведение состоит из
одной пары, первая координата которой есть пара (1, 2), а вторая
координата - элемент 3. В то время как (Ах(ВхС))={(\, (2, 3))},
т. е. это декартово произведение состоит из пары, первой
координатой которой является число 1, а второй координатой является
пара.
Задание 17
Найти декартовы произведения А х А, АхВ, ВхА, ВхВ:
1) А = [-2;4), В = 0;
2) А = (-2; 4), В = {4},
3) Л = [-3; 5], В ={5; 6; 7},
4) Л = (-3; 5), Я ={4; 21, 28};
5) А = (-3; 6), В ={4; 6; 7};
6) А = (-2; 9), В = (9; 10);
7) А = (-2; 9), В = [9; 10);
43
8)
9)
10)
И)
12)
13)
А--
А--
А--
А--
А--
А--
= (-2; 9],
= (-2; 9],
= [-1, 7),
= [-1,7],
= [-1,7],
= [-1,7),
5 =
5 =
5 =
в--
в--
в--
- (9; Ю);
= [9; 10];
= (7; 8);
= (7; 8);
= [7; 8);
= (7; 8].
§2. Определение и способы задания бинарного отношения
Говорят, что в М задано бинарное отношение Т, если МхМ
есть декартово произведение и в МхМ выделено произвольное
подмножество Т Таким образом, произвольное подмножество
Та МхМ есть бинарное отношение.
Мы будем говорить, что элемент а находится в отношении Т
к элементу Ь в том и только в том случае, когда пара (а, Ь)
принадлежит множеству Т Для этого возможны два равносильных
способа обозначения: аТЬ или (а, Ь)еТ
Пример 3. Отношение равенства чисел есть бинарное
отношение. Ему принадлежат все пары вида (о, а), где а -
действительное число.
Пример 4. Отношение на действительных числах а <Ь есть
бинарное отношение. Ему принадлежат все точки декартовой
плоскости, у которых первая координата меньше, чем вторая. Эти
точки образуют полуплоскость, расположенную левее биссектрисы
первого и третьего координатных углов.
Пример 5. Бинарное отношение между людьми «быть
родственниками» представляет собой множество пар людей, имеющих
общего предка.
Перечислим основные способы задания бинарных
отношений. Бинарные отношения могут быть заданы:
1. Списком (перечислением) пар.
2. Матрицей.
Пусть Т аМхМ, где М = {а], а2, ап}. Тогда отношению
Т соответствует квадратная матрица С порядка п9 в которой эле-
44
мент С,у, стоящий на пересечении /-й строки и у-го столбца, равен
1, если между а2 и я, есть отношение К; в противном случае Су = 0.
1? если {аи а]) еТ
Си =^\ 0, если (аи ц) & Т
Пример 6. Пусть множество М- {1, 2; 3; 4; 5}, отношение
7 = {(а; 6): (а - Ь) четное число}
Задать отношение списком и матрицей.
1. Т = {(1, 1), (1; 3), (1, 5), (2; 2), (2; 4), (3; 1), (3; 3), (3; 5),
(4; 2), (4; 4), (5; 1), (5; 3), (5; 5)}.
2. V
Я
1
2
3
4
5
[атрица пят
1
1
0
1
0
1
ь на пять:
2
0
1
0
1
0
3
1
0
1
0
1
4
0
1
0
1
0
5
1
0
1
0
1
Пример 7. Пусть множество М- {а; Ь; с). Зададим систему
множеств всех подмножеств множества М. Обозначим ее ДМ);
Р№ = {ф\ {о}, {Ь}, {с}, {а, Ъ), {Ь, с), {а, с}, {а ,Ь ,с) }
Составить матрицы следующих отношений на системе множеств ДМ):
а) 7
Ф
{а}
№
{с}
\а,Ь)
{Ь,с}
{а, с}
{а,Ь,с}
Ф
0
0
0
0
0
0
0
0
иметь н
0
1
0
0
1
0
1
1
епуст
{Ь}
0
0
1
0
1
1
0
1
оепе
{с}
0
0
0
1
0
1
1
1
эесечени
{а,Ъ}
0
1
1
0
1
1
1
1
е»
{Ь,с}
0
0
{а, с}
0
1
0
{а,Ь,с}
0
45
б) К2 - «быть дополнением» (без повторов)
я
ф
{«}
\Ъ)
\с)
{а,Ъ}
{Ь,с}
{а, с)
{аф,с}
Ф
0
0
0
0
0
0
0
1
{а}
0
0
0
0
0
1
0
0
{Ь}
0
0
0
0
0
0
1
0
{с}
0
0
0
0
1
0
0
0
1а, Ь}
0
0
0
1
0
0
0
0
{Ь,с}
0
1
0
0
0
0
0
0
{а, с}
0
0
1
0
0
0
0
0
{а,Ь,с}
1
0
0
0
0
0
0
0
Пример 8» Зададим отношения на множестве элементов
структуры
/\
ьО О с
Ао «о о о о
/ ё *
Пусть М = {а, Ь, с, Ы, е, /, §, И) - множество людей.
1. Зададим отношение К} - «быть близким другом».
Д; = {(а, Ь), (а, с), (Ъ, <0, Ф, е), (с, Д (с, & (с ,Н), (Ь, а), (с, а),
(4Ь),(е,Ь),ис),(8,с),(Ь,с)}
2. Зададим отношение К2 - «быть начальником».
К2 = {(а, Ь), (а, с), (а, О), (а, е), (а, Д (а, §), (а, К), (Ь, О), (Ь, е),
(с,А(с,8)Лс,Щ
3. Зададим отношение Я3 «быть отцом».
К3= {(а, Ь), (а, с), ф, О), (Ь, е), {с, А (о, ё), (с, К).
Задание 18
1. Пусть М = {1, 2. 3, 4, 5, 6} Задать списком и матрицей
отношения К1} К2, Я3, К4, Я5, если:
а) &! «быть строго меньше»;
б) К2 «иметь общий делитель, отличный от 1»;
46
в) Я3 - «иметь один и тот же остаток при делении на 3»;
г) Я4 «а - делитель (а + /?)»;
д) Я5 «{а + Ъ) - четное число».
Для всех отношений указать 0(Я) и (2(Я).
2. Пусть М = Р(А); А = {1, 2, 3, 4}
Составить матрицы отношений для Р(А)\
а) Л7 «являться строгим включением с:»;
б) Я2 «являться нестрогим включением с ».
3. Задать списком указанные ниже отношения на множестве
элементов структуры
о а
а
Ы ?о ои
а) Я] «быть прямым начальником»;
б) Я2 «быть дедушкой»;
в) Я3 «быть сыном или дочерью».
§ 3. Свойства бинарных отношений
Пусть/? аМхМ.
1. Отношение Я - рефлексивно, если \/а: {а, а) еЯ
Тогда в матрице отношения Л на главной диагонали стоят
только единицы: VI Сц= 1
2. Отношение Я - не рефлексивно, если За (а, а) 0 Я.
В этом случае на главной диагонали матрицы есть хотя бы
один 0.
3. Отношение Я - антирефлексивно, если \/а: (а,а) 0 Я.
Тогда на главной диагонали матрицы стоят только нули: \/г
Си = 0.
4. Отношение Я - симметрично, если \/а \/Ъ\(а, Ь) е Л =>
47
(Ь, а) е К. Тогда в матрице отношения У\ У]\ Су = 1 => С,-,- = 1.
Значит, матрица симметрична относительно главной диагонали.
5. Отношение К - не симметрично, если За, Ь: (а, Ь) е К и
(Ь, а) еК.
6. Отношение К - антисимметрично, если Уа V Ъ а Ф Ь'
(а, Ь) еК => (Ь, а) 0К; если же (а, Ъ) еКк (Ь, а) еК,тоа = Ь.
Тогда в соответствующей матрице отношения ни для каких
\,у. / Ф] не выполняется Су = С;, = 1.
Таким образом, отсутствуют единицы, симметричные
относительно главной диагонали.
Пример 9. Отношение между людьми К - «быть моложе».
Поскольку Уа\ {а, а) & К, то ни для какой пары (а, Ь) в К нет
симметричной пары (Ь, а) в К.
7 Отношение Л - транзитивно, если из того, что Уа УЪ V
с: (а, Ъ) е К и (Ь, с) е К следует, что (а, с) € К. В матрице такого
отношения должно выполняться следующее: если Су = 1 и С,* = 1,
тоС,* = 1, И, у, к.
Пример 10. Определим свойства отношений, заданных:
1) на множестве Л^ /?т = {(а, Ъ)\ а - делитель Ь}
- рефлексивно: — = 1 Уа еИ\
а
- не антирефлексивно;
- не симметрично, антисимметрично, так как 6 делится на 3,
но 3 не делится на 6;
Ъ с с Ъ с
- транзитивно: если — е Ы,— € ТУ, то — =
а Ъ а а Ъ
2) на системе множеств ДМ): К2 {(А,В): АОВ Ф ф,
А,Вс2/3(М)}:
- не рефлексивно, так как ф € @(М), фг\ф- ф ,
- не антирефлексивно, так как если АФ ф,то АглА фф
- симметрично, так как если АслВ Ф ф ,чо В слАф ф ,
не антисимметрично, так как У А Ф В (А,В)еК и
48
не транзитивно, так как из того, что А ел В Ф ф,
В глС Ф ф необязательно следует, что АглС Ф ф
Задание 19
1. Для множества элементов структуры
О
е / § к к I
определить свойства следующих отношений:
а) К] = {(а, Ь): «а - непосредственный начальник Ь»};
б) К2 = {{а, Ь)\ «а - двоюродный брат или сестра 6»};
в) Кз = {(а, Ь): «а - моложе Ь»}
2. Составить матрицы отношений и определить по ней
свойства данных отношений:
М= {1,2, 3,4, 5, 6, 7, 8}:
а)Д<={(я, Ь)\а > Ь};
б) К5 = {(а, Ъ)\ (а + 1) делитель {Ь + а)}\
в) К6= {(а, Ь)\ {а + Ъ + 1) четкое число}
§ 4, Отношение эквивалентности
Отношение эквивалентности есть очень важный частный
случай бинарного отношения.
Бинарное отношение Т с: МхМ называется отношением
эквивалентности, заданным на множестве М, тогда и только тогда,
когда оно рефлексивно, симметрично и транзитивно.
Таким образом, это отношение удовлетворяет следующим
трем условиям:
1) \/а ае М => (а, а)еТ, т. е. отношение Т удовлетворяет
условию рефлексивности;
49
2) \/сМЪ аеМ, Ье М если (а, Ь)еТ, то (Ь. а)е7\ т. е.
отношение Т удовлетворяет условию симметричности;
3) \/а\/Ь\/с аеМ, ЬеМ, сеМ если (а, Ь)еТ и (й, с)еГ, то
(а, с)еТ, т. е. отношение Г удовлетворяет условию транзитивности.
Отношение равенства чисел (пример 3) есть отношение
эквивалентности, так как является рефлексивным, симметричным и
транзитивным.
А бинарное отношение «<» для чисел (пример 4) не является
отношением эквивалентности, так как оно не удовлетворяет
условию симметричности.
Бинарное отношение между людьми «быть родственниками»
(пример 5) не является отношением эквивалентности, так как оно
не удовлетворяет условию транзитивности, хотя оно и
рефлексивно, и симметрично. Ведь один и тот же человек (обозначим его Ь)
может иметь двоюродного брата по отцу (обозначим его а, т. е.
имеем (я, Ь)еТ) и двоюродного брата по матери (обозначим его с,
т. е. имеем (Ь, с)еТ), которые не являются двоюродными
братьями, т.е. (а, с)ёТ
Пример 6. Бинарное отношение для натуральных чисел
«иметь одинаковый остаток при делении на некоторое число» есть
отношение эквивалентности. Например, все числа, имеющие при
делении на 5 остаток 1, являются эквивалентными.
Пример 7. Отношение для студентов «учиться на одном
факультете» есть также отношение эквивалентности (разумеется, при
предложении, что нельзя одновременно учиться на двух
факультетах).
Любое отношение эквивалентности Т порождает разбиение
множества М на непересекающиеся классы - классы
эквивалентности, верно и обратное. Докажем это предложение.
Теорема. Если Т есть отношение эквивалентности на
множестве М, то существует разбиение множества М - \^М1, такое,
что (а, Ь) е Т тогда и только тогда, когда существует число /,
такое, что а еМъ ЬеМ^
50
Доказательство: Обозначим через {а} подмножество
элементов множествам, эквивалентных а, т. е.
{а}={Ь | аТЬ }
Тогда выполняются два утверждения:
1. а е {а}
2. Если {а}гл{Ь}*0у то {а}={Ь}
Утверждение 1 очевидно, так как из условия рефлексивности
имеем аТа.
В утверждении 2 надо доказать теоретико-множественное
равенство {о}={Ь} Для этого надо показать, что из условия
{а}г\{Ь}*0 следует, что {а}а{Ь} и {Ь}а{а}.
Сначала покажем, что {а}с:{Ь}, т. е. получим, что \/у уе {а}
^уе{Ь}.
Итак, если {<я}п{&}^0, то существует такой элемент х,
который принадлежит одновременно множеству {а} и множеству
{Ь}
Так как хе{а}, то в силу определения множества {а} имеем
аТх. Из условия симметричности отношения Т получаем хТа, а так
как уе {а}, то имеем аТу.
Отношение Г, будучи отношением эквивалентности,
является транзитивным. Поэтому из хТа и аТу вытекает хТу, а так как
хе { Ъ), то имеем ЪТх.
Вновь используя условие транзитивности, из ЬТх и хТу
получаем ЬТу, т. е. уе {Ь}, что и требовалось доказать.
Симметрично получаем, что {Ь}а{а},и утверждение 2
доказано.
Из утверждений 1 и 2 получаем, что множество подмножеств
вида {а}, где ае М, образует разбиение множествам,
удовлетворяющее условию теоремы.
Теорема доказана.
Обратное утверждение доказывается очень просто.
Сформулируйте его и докажите самостоятельно.
Полученное таким образом разбиение называется
разбиением на классы эквивалентности.
51
Два элемента а, Ъ принадлежат одному классу
эквивалентности множествам, если (а, Ь) е Т
Пример 8. Для отношения из примера 6 «иметь одинаковый
остаток при делении на 5» разбиением множества натуральных
чисел на классы эквивалентности являются следующие пять
классов эквивалентности:
А/,: {1,6,П,...}
М2: {2,7,12,...}
М3: {3,8,13,...}
М: {4, 9, 14, }
М5: {5, 10, 15, ...}
Таким образом, множество натуральных чисел представляет
собой объединение пяти непересекающихся подмножеств
N = Л/] и М^> Мз*и М^МЪ.
Следовательно, два числа а, Ь находятся в отношении
эквивалентности Г, т. е. (а, Ь) е 77, если при делении на 5 они имеют
одинаковый остаток.
В этом примере число классов эквивалентности конечно, а
число элементов в каждом классе бесконечно.
Пример 9в Теперь рассмотрим пример, когда в один класс
попадают все действительные числа с одинаковой дробной частью,
т. е. отношение эквивалентности Т определяется следующим
образом: (а, Ъ)^Т тогда и только тогда, когда (а)=ф), где (Ь) есть
операция взятия дробной части (т. е. (Ь) = Ь - [й], а [Ь] есть операция
взятия целой части),
В этом случае число классов эквивалентности бесконечно,
так как число различных дробей, принадлежащих интервалу (0, 1)
бесконечно. Каждый класс также бесконечен, так как мощность
каждого класса имеет мощность множества целых чисел.
§5. Отношения порядка
Среди бинарных отношений важными также являются
отношения порядка.
52
Говорят, что отношение нестрогого порядка задано на
множестве М, если Т есть бинарное отношение, которое
рефлексивно, антисимметрично и транзитивно.
Таким образом, оно подчинено следующим трем условиям:
1) \/а ае М => (а, а)еТ, т е. отношение Т удовлетворяет
условию рефлексивности;
2) \/а\/Ь аеМ, Ье Месли (а, Ь)еТи (Ъ, а) еГ, то а = Ь, т. е.
отношение Т удовлетворяет условию антисимметричности;
3) \/сМЪ\/с аеМ, ЬеМ, сеМ если (а, Ь)еТ и (6, с)еТ, то
(а, с)еТ, т. е. отношение Г удовлетворяет условию транзитивности.
Пример 10. Отношение «<» для чисел есть отношение
нестрогого порядка. Действительно, для любых действительных
чисел а, Ь9 с выполняются все три условия: а < а, если а < Ь иЬ < а,
то а = Ь, и если а < Ъ и Ъ < с, то а < с.
Пример 11* Отношение «быть подмножеством» также
является отношением нестрого порядка, так как любое множество
является подмножеством самого себя, а также если АаВ и Во4, то
А = В, и, наконец, если АаВ, ВаС, то АаС.
Теперь введем отношение строгого порядка.
Говорят, что на множестве М задано отношение строгого
порядка Г, если есть бинарное отношение, подчиненное
следующим трем условиям:
1) \/а аеМ => (я, а)ёТ, т. е. оно удовлетворяет условию
антирефлексивности;
2) \/а\/Ъ (а, Ь) и (6, а) не могут принадлежать Т
одновременно, т. е. отношение Т удовлетворяет условию
несимметричности;
3) \/а\/Ь\/с аеМ, ЬеМ, сеМ если (а, Ь)еТ и (6, с)еТ, то
(а, с) е Г, т. е. отношение Т удовлетворяет условию
транзитивности.
Таким образом, отношение строгого порядка есть бинарное
отношение, удовлетворяющее условиям антирефлексивности,
несимметричности и транзитивности.
Пример 12. Отношение «<» для чисел есть отношение
строгого порядка. Так, про любое действительное число а нельзя ска-
53
зать, что а < а, для любых двух действительных чисел а, Ь либо
а < Ьу либо Ъ < а, и значит, они не могут иметь место
одновременно. А для любых трех чисел имеем: если а < Ь иЬ < с, то а < с.
Пример 13. Отношение «быть собственным
подмножеством» является отношением строгого порядка.
Пример 14. Отношение между людьми «один старше
другого» также является отношением строгого порядка.
Пример 15, Другой пример отношения между людьми «один
является предком другого» также является отношением строгого
порядка, так как никакой индивидуум не может быть предком
самого себя (антирефлексивно), далее, если один есть предок
другого, то второй не может быть предком первого (несимметричность).
Свойство транзитивности также очевидно, так как если А является
предком В (например, отцом), а В является предком С
(предположим, также отцом), то А будет также предком С (в данном случае
дедом).
§6. Упорядоченность множества
Введем теперь определение упорядоченности.
Два элемента аеМ и Ъ<еМ являются сравнимыми в данном
порядке ТсгМхМ, если про них можно сказать
(а, Ь)еТили (6, #)еГ, или а = Ъ.
Множество М с введенным порядком Т является
упорядоченным (линейно упорядоченным), если любые два элемента этого
множества являются сравнимыми.
Про множество М, на котором просто введен некоторый
порядок Г, т. е. в котором существуют сравнимые элементы, говорят,
что оно частично упорядоченно.
Заметим, что среди вышеприведенных примеров свойством
упорядоченности обладает множество всех точек на
действительной числовой прямой Я (пример 12), так как любые два
действительные числа можно сравнить между собой.
Для подмножеств (пример 13) это свойство не имеет места,
так как по отношению включения можно сравнить далеко не все
54
подмножества. Например, числовой интервал (-2; 5) нельзя
сравнить с отрезком [0; 7] по отношению включения. Таким образом,
это множество является частично упорядоченным, но не является
линейно упорядоченным.
Среди линейно упорядоченных множеств выделяют вполне
упорядоченные множества. Для его определения введем
определение условия минимальности.
Говорят, что множество М удовлетворяет условию
минимальности для некоторого отношения порядка Т, если в любом его
непустом подмножестве ХаМ существует такой элемент а, что V*
хеХ, имеет место а Тх.
Итак, множество называется вполне упорядоченным, если
оно является линейно упорядоченным и удовлетворяет условию
минимальности.
Пример 16. Множество натуральных чисел является вполне
упорядоченным.
Пример 17. Множество действительных чисел не является
вполне упорядоченным, так как для интервалов не существует
минимального элемента.
Обратим внимание на то, что одно и то же множество может
быть линейно упорядоченным относительно одного порядка и
лишь частично упорядоченным относительно другого порядка.
Так, множество всех людей с введенным отношением
старшинства является линейно упорядоченным (роль равенства играет
отношение «быть ровесниками»), а это же множество с
отношением «быть предком» не является линейно упорядоченным, так как
про любых двух людей нельзя сказать, что один является предком
другого.
Вообще иерархические системы, т. е. системы, подобные
генеалогическому дереву, играют большую роль и в математике, и в
информатике, ведь файлы на жестком диске расположены, как на
дереве. Остановимся на этом подробнее.
55
§7, Деревья, лексикографический порядок
Имеем некоторый алфавит. Заметим, что его мощность
должна быть не меньше, чем максимальное число ветвлений в
некоторой вершине дерева. Не ограничивая общности, возьмем
латинский алфавит. Дерево в математике строится сверху вниз.
Пусть корень (начальная вершина) дерева называется а. Тогда в
первом ярусе самая левая вершина есть аа, следующая - аЬ, затем
ас и т. д., во втором ярусе вершины, выходящие из вершины аа,
имеют названия ааа, ааЬ, аас, и т. д., вершины, выходящие из
вершины аЪу имеют названия аЬа, аЪЪ, аЬс, Таким образом,
вершина, находящаяся в л-м ярусе, имеет название длины п. Если
из вершины не выходит ни одной ветви, то она называется
концевой.
Пример 18
Рис. 23
В дереве естественным образом устанавливается отношение
предшествования: одна вершина предшествует другой, если ее имя
является префиксом имени второй вершины. Так, вершина с
именем аа (рис. 23) предшествует вершине с именем ааЬаЬ. В этом
порядке сравнимые вершины находятся на одной ветви: та,
которая находится выше, предшествует той, которая находится ниже.
Такой порядок графически иллюстрирует отношение между
людьми «быть предком»; вершины, расположенные выше, изо-
56
бражают предка, а вершины, расположенные ниже, - потомка.
Если рассматривать дерево, изображенное на рис. 23, как
генеалогическое, то аа есть прадед ааЬаЬ.
Разумеется, в этом порядке вершины дерева не представляют
собой упорядоченное множество, а лишь частично упорядоченное
множество. Ведь в этом порядке вершины ааа и аЬаЬЪ не
сравнимы.
Введем другой порядок. Пусть одна вершина предшествует
другой, в двух случаях:
1 Если имя первой является префиксом имени второй.
2. Если все буквы, кроме последней буквы, в них
совпадают, а последняя буква в первом слове расположена в алфавите
раньше, чем последняя буква во втором слове.
Так, в дереве (рис.23) вершина аЪ предшествует вершине
аЬаЬЬ, а вершина аЬаЪаа предшествует вершине аЬаЬаЪ. В этом
порядке число вершин по-прежнему не является упорядоченным
множеством; к примеру, вершины ааЬЬ и аЪаЬ не являются
сравнимыми, но теперь можно сравнивать вершины, выходящие из
одной и той же вершины. В отношениях между людьми это можно
интерпретировать как отношение «быть или предком или старшим
братом». Иногда такой порядок называют «деревянным»
(А. Л. Драгалин).
Если для некоторых целей нужно, чтобы все вершины
дерева были упорядочены, то порядок можно определить следующим
образом. Одна вершина предшествует другой в двух случаях:
1. Если имя первой является префиксом имени второй.
2. Выделяется максимальный общий префикс двух имен, и
далее если следующая за максимальным общим префиксом буква
имени первой вершины расположена раньше, чем такая же буква
имени второй вершины. Этот порядок называется
лексикографическим, алфавитным или словарным.
Пример 19. Примером множества с лексикографическим
порядком является множество слов русского языка, а порядок на
этом множестве совпадает с порядком в орфографическом словаре.
Так, слово «Пантелеймон» предшествует слову «пантеон», так как
буква «л» предшествует букве «о». Естественно, что множество
57
слов любого языка является упорядоченным, и в соответствии с
этим порядком располагается в словаре.
Пример 20, В качестве примера возьмем фрагмент
генеалогического дерева французской королевской династии Бурбонов.
Этот пример хорошо иллюстрирует понятие порядка, так как
вопрос престолонаследия это задача о порядке в иерархической
системе.
Людовик XIII
Людовик XIV
Людовик
Людовик Филипп Шарль
Филипп Орлеанский
Филипп
Людовик
герцог Орлеанский
Людовик\ Людовик XV ФИЛИПП
Людовик
Луи -Филипп
Луи -Филипп
герцог Людовик XVI Людовик XVIII Шарль XI Луй-Филипп I
Бургундский
Луи-Жозеф Людовик XVII
Рис. 24
Обратим внимание, что выбранный во Франции порядок
престолонаследия является именно лексикографическим.
Так, после Людовика XVI королем стал его сын Людовик
XVII, который пережил своего отца лишь на два года. А после его
смерти престол перешел к его дяде Людовику XVIII, так как он,
будучи братом Людовика XVI, был следующим в лексикографиче-
58
ском порядке. У Людовика XVII не было наследников, и престол
перешел к его брату, но после него власть перешла от основной
ветви Бурбонов к орлеанской ветви, т. е. к Луи-Филиппу I.
Пример 21. В виде лексических деревьев можно представить
также расположение файлов в компьютере. Обычно имя А
присваивается мягкому диску, а далее следуют жесткие диски по
порядку В, С, В и Е. На каждом диске располагаются файлы и
каталоги. Файлы соответствуют концевым вершинам, а каталоги
внутренним вершинам, в свою очередь, каталоги состоят из
файлов и подкаталогов, где опять файлы соответствуют концевым
вершинам, а подкаталоги - внутренним и т. д.
В качестве примера нарисуем фрагмент дерева,
соответствующего строению диска Е.
ВООТ СОРУ СУК1ЫЛС РШ пшзопуфз зеШрйуехе
аийэехес ЬаХ соттапс! сот ВЫ) ОВД) сП сО
роз1 ехе сйё <1о81зх1 с1п
Рис. 25
§8. Операции над бинарными отношениями
Ввиду того, что по определению отношения являются
множествами, к ним применимы те же операции, что и к самим
множествам, т. е. операции объединения, пересечения, дополнения,
разности и симметрической разности. Таким образом, если Ги5
59
суть бинарные отношения на множестве М, то бинарными
отношениями в М будут также следующие подмножества в М: 7Ъ5,
Тп5, Т = М\Т,Т^,ТА8.
Пример 22. Если в качестве первого отношения взять
бинарное отношение равенства действительных чисел, а в качестве
второго отношения взять бинарное отношение неравенства чисел,
то их объединением будет вся декартова плоскость, т. е. множество
КхК.
Пример 23. Пусть Т - множество чисел, кратных двум, 5 -
множество чисел, кратных трем, тогда их пересечением является
множество чисел, кратных шести.
Пример 24. Если в качестве множества М взять декартову
плоскость, т. е. КхК, а в качестве отношения Т - отношение
нестрогого порядка «<», т. е. множество всех пар (а, 6), таких, что
а < Ьу то дополнением этого отношения будут такие пары (а, Ь),
что а > Ь, т. е. дополнением к отношению «<» будет отношение
Пример 25. Пусть Т - отношение нестрогого порядка «<»,
а 5 - отношение строгого порядка «<». Тогда 7Д5 есть отношение
равенства «=».
Пример 26. Пусть отношение Т нестрогого порядка «<»,
а 5 - отношение нестрогого порядка «>», тогда ТА5 есть отношение
неравенства, т. е. «^».
Кроме ранее рассмотренных операций, к бинарным
отношениям применимы операции обращения и умножения,
определенные ниже.
Операция обращения отношения Т задается следующим
образом: результатом применения этой операции является множество
пар вида (6, я), где (а, Ъ) суть пары, принадлежащие Т Эта
операция обозначается как
Операция обращения Т - унарная, т. е. применяется к
одному отношению и результатом ее является другое отношение Vх.
60
Пример 27. Результатом обращения отношения нестрогого
порядка «<» является отношение нестрогого порядка «>», а
результатом обращения строгого порядка «<» является отношение строго
порядка « >».
Операция умножения Т и 5 - бинарная, т. е. применяется к
двум отношениям Т и 5 на множестве А/, а результатом ее является
третье отношение на том же множестве М, задаваемое следующим
образом:
То8 = %а,Ь) ЗсеМ,(аус)^Т,(с,Ь)е8}.
Пример 28. Пусть Т = {(1, 2), (3, 4)}, 5 = {(2, 3), (4, 5)}
Тогда То8= {(1,3), (3,5)}
Пример 29. Произведением нестрогого порядка «<» и
строгого порядка «<» на множестве действительных чисел является
строгий порядок «<». (Докажите это самостоятельно в качестве
упражнения).
Пример 30. Установить самостоятельно, как строится
произведение строгого порядка «<» и равенства «=» на множестве /?.
Заметим, что операция умножения отношений в общем
случае не коммутативна, но ассоциативна.
§9. Понятие функции
Теперь введем понятие функции - одного из основных
понятий математики. Пусть Ми N - два произвольных множества.
Говорят, что наМ определена функция/ принимающая значения из
ТУ, если каждому элементу хеМ поставлен в соответствие по
определенному закону один и только один элемент у еЛ/, т. е. у =У(х).
Обычно в математическом анализе в качестве множеств М и
N рассматриваются некоторые множества числовой прямой Л,
которые обозначаются какХи 7 соответственно. При этом X
называется областью определения данной функции, а У - множеством
всех значений, принимаемых этой функцией, - ее областью
изменения. Например, у функции у = Хп х областью определения явля-
61
ется К\ положительная полуось числовой прямой, а множеством
значений вся числовая прямая Л.
Таким образом, числовая функция есть подмножество
множества КхЯ, т. е. является бинарным отношением
т={(х,лт,
при этом среди этих пар (х, Дх)) нет таких, у которых абсциссы
совпадают.
Бинарное отношение К а X У называется функцией, если
для любых х е X и у19у2 е У таких, что (х\у ) е К и
(х;у2) е К следует, что ух = у2
Пример 31. Зададим отношение К на декартовом
произведении множеств А = {1; 2; 3; 4; 5} и В = (1; 2; 3; 4} Отношение
помечено на рис. 26 символом «х».
о
А
Ж X
з X * X Ж
2 | X X
,— . . . . , >
V "2 :3 4 .5 А
Рис.26
Зададим это отношение перечислением пар
К = {(1; 2),(1; 3),(2; 3),(2; 4),(3; 3),(3; 4),(4; 2),(4; 3)}
Очевидно, что Л - не функция.
Пример 32. Является ли функцией отношение, заданное
рис. 27 Если да, является ли отношение К~ функцией?
62
X
Рис.27
Зададим это отношение перечислением пар
Д = {а;2),(2;3),(3;3),(4;3),(5;4)}
Очевидно, что это функция. Рассмотрим отношение К~
Л-'={(2;1),(3;2),(3;3),(3;4),(4;5)}
Ясно, что К~ не функция.
Если а элемент, принадлежащий М, то соответствующий ему
элемент Ь =/{а) называется его образом. Каждый элемент а может
иметь единственный образ (как следует из определения функции),
при этом для Ь может существовать не один элемент из множества
А/, образом которого он является. Совокупность всех тех элементов
а из М, образом которых является данный элемент Ь из Ы9
называется прообразом или полным прообразом элемента Ъ и
обозначается /1 (Ь). Например, для функции у = х2 элемент 4 имеет два
прообраза 2 и -2, т. е. полный прообраз для 4 есть множество
Г\А) = {-2, 2}
Пусть X некоторое множество из М, тогда совокупность
{/{а)} всех элементов видака), где аеХ, называется образом X и
обозначаетсяДХ). Так, если для функции^ = х2 в качествеXвзять
множество (0; 2), то ДА) = (°; 4).
Так как функция есть бинарное отношение, то понятие
обратной функции легко вводится с помощью операции обращения
63
бинарных отношений, а понятие сложной функции - с помощью
понятия умножения отношений.
Итак, если функция / определяется как множество пар
Т={(х, Дх))}, то обращением функции/4 есть множество пар вида
Г' = {(Дх),х)}
Пример 33. Функция 1п (х), обратная к экспоненциальной
функции ех, есть множество пар вида (еху х), где хеК, так как
7Ч(х,^тоГЧ(^х)}
Обратим внимание на то, что множество значений функции
становится областью определения обратной к ней функции.
Но при применении операции обращения отношения к
функциям могут возникнуть определенные трудности. Ведь для
того, чтобы бинарное отношение было функцией необходимо,
чтобы каждому элементу хеМ был поставлен в соответствие один и
только один элемент уеЫ. В то же время элементу уеМ может
соответствовать более чем один элемент хеМ. Таким образом,
бинарное отношение Г1 = {(Дх), х)}, которое является обращением
функции, само может не являться функцией.
Пример 34. Пусть Г={(1, 2), (2, 3), (3, 3)} В этом случае Тл
= {(2, 1), (3, 2), (3, 3)} элементу 3 соответствуют сразу два
элемента 2 и 3, поэтому обращение отношения Г, которое было функцией,
функцией не является.
Поэтому при построении обратной функции из множества Т
= {(Дх), х)} выбирают только такие пары, у которых вторые
элементы различны. В примере 33 таких проблем не возникло, так как
показательная функция является монотонной, и каждый образ у
имеет единственный прообраз х.
Пример 35. Пусть /[х)=х2 - функция, определенная на всей
числовой прямой Л = (-оо3 +оо). Она представляет собой множество
пар Т {(х, х2)} Множество значений этой функции есть
луч [0, +оо). Тогда для обратной функции область определения есть
луч [0, +оо). Если мы сделаем обращение этого отношения, то
получим 7"1 {(х2, х)}, отношение, которое не является функцией,
так как, например, числу 4 соответствуют два образа 2 и -2.
Графически Дх) = х2 представляет собой параболу, а ее обращение -
параболу, лежащую на боку. Для построения обратной функции,
64
т. е. арифметического квадратного корня мы должны из множества
Т выбрать пары с различными вторыми координатами. Ввиду
того, что числам -а и а соответствует одно и то же значение, для
этого выбора достаточно сузить область определения, т. е. в качестве
исходного отношения Т\ взять подмножество отношения Т
множество {(х, х2)}, где хе[0, +оо). К этому отношению применяем
операцию обращения и получаем: Vх = (х2, х)}, где область
определения [0, +оо) и множество значений [0, +оо). Что касается
построения сложной функции, то она представляет собой умножение
двух отношений, каждое из которых является функцией. В этом
случае дела обстоят более благоприятно, чем с обращением, так
как отношение, полученное с помощью умножения двух функций,
само является функцией. Докажите это самостоятельно в качестве
упражнения.
Пример 36. Пусть Т={(1, 2), (2, 3), (3, 4)}, 8={(1, 2), (2, 3),
(3, 7), (5, 0)} Оба отношения являются функцией. Тогда То 8 =
{(1, 3), (2, 7)}, т. е. тоже функция.
Пример 37. Пусть /(х) = х2, эта функция представляет собой
множество пар Т = {(х, х2)}; (р(х) - $т х, эта функция представляет
собой множество пар 5 = {(х, $т х)}. Тогда композиция этих
функций То 8= {(х, $ш х2)} также является функцией. Она обозначается
Ф (Дх))- Постройте в качестве упражнения функцию Лр (х)).
Пусть К - некоторое отношение. Областью определения
отношения К называется множество О(Я) = {х | (х\у) е К для
некоторого у}
Областью значений отношения К называется множество
Е(К) = {у | (х\у) е К для некоторого х}
В примере 31 В(К) = {1; 2; 3; 4}; Е(К) = {2; 3; 4}
В примере 32 0(К) = {1; 2; 3; 4; 5}, Е(К) = {2; 3; 4};
Я(Д"1) = {2;3;4}, Е(К~]) - {1; 2; 3; 4; 5}
Применяют следующую терминологию.
Если Е(/)=Т, то функция / называется сюръскцией (сюръек-
тивной функцией или отображением «на»).
65
Если функция / такова, что для любых элементов
х1?х2 е /)(/) таких, что х} Ф х2 следует, что /(х\) Ф /(х2), то
функция/называется инъекцией (инъективной функцией или
отображением «в»). Функция / называется взаимно однозначной или
биективной, если она сюръективна и инъективна.
Пример 38. На рис. 28 показаны функции / [0;1] —> [0;1];
1€{1;2;3;4}
Рис.28
Функция /х сюръективна, но не инъективна; функция /3
биективна; функция /2 инъективна, но не сюръективна; функция
/4 не инъективна и не сюръективна.
Пример 39. Рассмотрим три функции /( К —> К;
/ = 1; 2;3
1) функция /г(х) = ех инъективна, но не сюръективна;
2) функция /2(х) = Х'51ПХ сюръективна, но не
инъективна;
3) функция /3(х) = 2х + 1 биективна.
Пример 40. Чему равна композиция функций Дх)=2х и
Н= \ = *(/(*)) = 1 +/(*) = 1 + 2х; \ К -> К
р/=Ъ2=/(я(х)) = 2&(х)) = 2(1 + х) = 2 + 2х; А, Л->Л.
66
Пример 41. Чему равна композиция функций /(х) = 2х и
§(х) = 1о§2 х ? Каковы области определения функций и их
композиций?
/(х) = 2* К-+К; #(х) = 1о§2х К ^ К.
Рассмотрим композиции в произвольном порядке:
4=/°* = *(/(*)) = 1ог22* = х, хеЛ,
^ = * ° / = /(*(*)) = 21062 * = х, где х>0.
Таким образом, В(/)=К; ОД=Л+; ОД) = Л; ОД,) = Л +
В заключение можно добавить, что Дх) является инъектив-
ной, но не сюръективной; %(х) является биективной. Однако
\ = /°8~ биекция, а /^ = 8°/- инъективна, но не сюръектив-
на.
Задание 20
1. Являются ли Л и К'1 функциями?
•■>■ °
х
X
Рис. 29
2. Пусть отношение К задано на декартовом произведении
множеств К и Р, где К - множество ключевых слов. Р - множество
\уеЪ-страниц. Пара (х; у) принадлежит К, если только ключевое
слово х содержится на странице^. Является ли функцией К(К)~1 ?
3. Пусть отношение /? задано на декартовом произведении
множеств В и Ы, где В - множество всех документов,
содержащихся в папке «Входящие», а ТУ - множество всех номеров, служащих
67
для регистрации этих документов. Является ли К функцией?
И является ли функцией К~ ?
4. Пусть отношение К задано на декартовом произведении
множеств В и Р9 где В - множество всех книг в книжном магазине,
Р - множество цен. Пара (х; у) принадлежит К, если и только если
книга х имеет цену у. Являются ли 7? и К ~ функциями?
5. Для заданных типов функций определить:
- свойства У;
- имеет ли/обратную функцию /_1 ?
- свойства /"'
а) Дх) = л/х;
б) /О) = 5П1 X ,
в)/(х) = 2х-1,
г) Дх) = х2
Д) /(*) = !§*,
е) Дх) = а*
6. Чему равна композиция функций/^ и §(х), если:
а) Дх) = 2х,#(х) = 1§х;
б) /(х) = х3,#(х) - л/х;
в) Дх) = 2*,#(х) = х + 1?
Каковы области определения функций и их композиций?
7 Найти композицию преобразований:
а
а
а
(\2Ъ
)
\12\
гаЪс\
сЪс
Р =
Р =
V
/аЪсй\
Ъйас
р =
123
1321
(аЪсЛ
\ЪЪа
(аЪсй^
сасИ
68
§10. Декартово произведение п множеств
Перед тем, как ввести декартово произведение п множеств,
введем понятие кортежа или гс-ки. Кортежем или и-кой
называется последовательность элементов, т. е. множество, в котором
каждый элемент занимает определенное место.
Примерами кортежей являются последовательность людей,
стоящих в очереди, последовательность слов во фразе,
последовательность букв в слове, а также алфавит.
Обозначается кортеж как: (#ь а2, ..., ап), а аи а2, ..., ап суть
его элементы. Эти элементы называются компонентами кортежа.
Число элементов кортежа называется его длиной.
Декартово произведение А\х А2х х Ап множеств А\9 А2,
Ап представляет собой множество всех упорядоченных п-ок
(энок) элементов (аь а2, ..., ап\ где а^еАи а2е А2,..., апе А„. В
этом случае а\ называется первой координатой, а2 называется
второй координатой и т. д.
Если хотя бы одно из множеств А\, А2у ..., Ап пусто, то
декартово произведение является пустым.
Рассмотрим частный случай декартова произведения, когда
М = А19М = А3,...9М=А„.
В этом случае будем говорить, что декартово произведение
Мх Мх ... х М есть декартово произведение и-й степени
множества М. Обратим внимание, что в этом случае декартово
произведение является коммутативным. В частности, декартово
произведение Кх Кх К, где К - множество действительных чисел, определяет
трехмерное геометрическое пространство, где элементы
а = (х, у9 г) являются точками трехмерного евклидового
пространства.
§11. Определение и-арного отношения
Ранее было введено понятие бинарного отношения Т Оно
определялось как произвольное подмножество декартова
произведения МхМ.
69
Аналогично, п-арным (или п-местным) отношением
называется любое подмножество Т декартова произведения п-й
степени: Та Мп
Точками отношения Т являются последовательности вида
(а\, а2, ..., #п), гд& щ е М. Число п называют также типом или
рангом отношения.
Пример 42. Примером трехместного отношения является
множество всех троек (аь а2, <з3), таких, что а3 = а\+ а2, я, е Я.
В пространстве К3 множество всех таких троек образует
плоскость г = х +у.
Пример 43. Аналогично можно рассмотреть множество всех
четверок (аь а2, аъ, а4), таких, что а4 = аъ + а2+ #ь я, е К,
Это четырехместное отношение образует в пространстве К4
гиперплоскость Х\ + Х2 + Хъ - Х4 = 0.
Пример 44. Множество всех четверок (аь #2, #з, яи), таких,
что ^1 + а3 = а2 + а4, где а, е <2? также является примером
четырехместного отношения.
Так как отношение есть подмножество, то можно определить
его мощность как число элементов его составляющих.
В вышеприведенных примерах отношения состояли из
бесконечного числа элементов.
Пример 45. Составим отношение, представляющее собой
расписание занятий у студентов-дневников. Студенты могут быть
заняты от первой до шестой пар. Таким образом, расписание на
один день можно рассматривать как шестиарное отношение, в
котором 7-м элементом является название предмета или прочерк
(пара свободна).
Возможен следующий вариант расписания: {(введение в
информатику; культурология; история; иностранный язык; -; -)}
Это отношение ТаМ6, где М состоит из всех предметов,
которые преподают в этом учебном заведении или прочерка.
В нашем примере отношение является одноэлементным, т. е.
его мощность равна 1.
Если мы рассмотрим расписание на неделю, то такое
отношение будет шестиэлементным, т. е. его мощность равна 6, так как
в неделе 6 рабочих дней. В данном случае мощность отношения
70
случайно совпала с его арностью. В общем случае они естественно
различны. Во всех выше рассмотренных примерах а, было просто
элементом: числом, названием предмета или прочерком.
Рассмотрим примеры, где щ является в свою очередь множеством.
Пример 46. Напишем расписание на один день таким
образом, что /-ми элементами будут множества, состоящие из двух
элементов: названия предметов и номера аудитории.
Имеем такой вариант расписания: {((введение в
информатику; 307); (культурология; 519); (история; 102); (английский язык;
517);-;-)}.
Это отношение Та М6, где М есть декартово произведение М
= М\х М2,М\- множество всех предметов,М2- множество
номеров всех аудиторий. В этом случае а, есть кортеж, состоящий из
двух элементов, первый элемент принадлежит М\ и означает
название предмета, а второй элемент принадлежит М 2 и означает
номер аудитории.
Пример 47. Такие сложные отношения удобнее записывать
в виде столбца. Перепишем предыдущее отношение в виде
следующих столбцов:
^введение в информатику, 307^
культурология, 519
история, 102
английскийязык, 517
V )
Если записать отношения в виде столбцов, тогда получается
таблица, число строк которой определяет арность отношения. Все
строки таблицы имеют равное число столбцов и представляет
собой кортежи с одинаковыми М\, М2, Мп. Название любого
множества М^ есть его атрибут. В примере с расписанием занятий,
первый атрибут - ПРЕДМЕТ, а второй - НОМЕР АУДИТОРИИ.
71
Само множество М, называется доменом атрибута, это множество
является множеством значений, которые может принимать данный
атрибут. Для домена вводится обозначением = йот (атрибут).
В нашем примере доменом атрибута «ПРЕДМЕТ» является
множество всех изучаемых студентами данного курса предметов, а
доменом атрибута «НОМЕР АУДИТОРИИ» является множество
всех номеров аудитории данного вуза. Эти множества
обозначаются как Лот (ПРЕДМЕТ) и Лот (НОМЕР АУДИТОРИИ)
соответственно.
Схемой отношения К называется конечное множество имен
атрибутов {М\, М2, ...,Мп}
В нашем примере схема отношения следующая: {предмет,
номер аудитории}
Число имен меток образует формат отношения. В нашем
примере формат отношения равен двум.
Окончательно отношение расписания можно записать
следующим образом:
ПРЕДМЕТ НОМЕР АУДИТОРИИ
введение в информатику 307
культурология 318
история 102
английский язык 517
Пример 48. Этот пример можно еще усложнить, рассмотрев
в качестве М = Мхх М2х М3, гдеМиМ2~ такие же, как и в
примере 40, аМ3 - множество преподавателей. Тогда /-й элемент
отношения сх\ будет представлять собой кортеж, состоящий из трех
элементов. Атрибутом М\ будет ПРЕДМЕТ, атрибутом М2
НОМЕР АУДИТОРИИ, атрибутом М3 ФАМИЛИЯ
ПРЕПОДАВАТЕЛЯ.
Схемой отношения Т является в этом случае множество имен
атрибутов {ПРЕДМЕТ; НОМЕР АУДИТОРИИ; ФАМИЛИЯ
ПРЕПОДАВАТЕЛЯ}.
72
Окончательно, отношение расписания запишется следую-
щим образом:
ПРЕДМЕТ НОМЕР АУДИТОРИИ
введение в информатику
культурология
история
иностранный язык
307
519
102
517
ФАМИЛИЯ
ПРЕПОДАВАТЕЛЯ
Иванов И. И.
Фёдоров Ф. И.
Петров П. П.
Сидорова С. А.
§12» Операции над «-арными отношениями
Выше были введены операции над бинарными
отношениями. Для и-арных отношений операции вводятся аналогично.
Таким образом, если Т и8 суть «-местные отношения в
множестве М, то «-местными отношениями в М будут также
следующие подмножества: Ти8, Тгл8, Т = М \ Т, Г^, ТАЗ.
Пример 49. Дополнением отношения, состоящего из троек,
таких, что а\ = а2 + #з, является отношение, состоящее из троек (аь
а2, а3) таких, что а\ Ф а2 + а3.
Аналогичным образом строятся примеры объединения,
пересечения, разности и симметрической разности. (Постройте эти
примеры самостоятельно в качестве упражнения).
Пример 50. В качестве примера, иллюстрирующего выше
введенные определения, и для построения новых операций дадим
фрагмент расписания электричек на Ярославском вокзале.
В данном примере элементом отношения является строка
таблицы, а число строк таблицы (в данном случае - 8) есть тип
отношения, т. е. перед нами 8-арное отношение. Каждый элемент
данного отношения характеризуется четырьмя столбцовыми
позициями: время отправления, пункт назначения, дни недели и
остановки. Каждый элемент данного отношения, т. е. строка,
представляет собой 4-местный кортеж.
73
ВРЕМЯ
ОТПРАВЛЕНИЯ
[ 10-53
11-03
11-14
11-21
11-36
11-47
15-22
16-22
ПУНКТ
НАЗНАЧЕНИЯ
Пушкино
Фрязино
Красноармейская
Монино
Пушкино
Александров
Пушкино
Софрино
ДНИ
НЕДЕЛИ
воскресенье
кроме среды
суббота,
воскресенье
по раб. дням
по раб. дням
ежедневно
по раб.дням
ежедневно
ОСТАНОВКИ 1
со всеми ост.
со всеми осг.
кроме Красный
Строитель
со всеми ост.
со всеми ост.
Мытищи,
Пушкино,
далее везде
со всеми осг.
кроме
Тайнинская
Обратим внимание на то, что элемент кортежа также может
быть множеством. Так, в нашем примере, четвертый элемент всех
кортежей есть множество станций, на которых останавливается
поезд. К этим множествам применимы обычные операции над
множествами. При составлении дополнения в качестве основного
множества берется множество всех остановок от Москвы до
конечной остановки, которая задана вторым элементом кортежа. Запись
«со всеми остановками» означает, что множество всех остановок
данного поезда совпадает с основным множеством. Для последней
строки «кроме Тайнинская» имеем задание множества всех
остановок поезда с помощью понятия дополнения: из основного
множества (множества всех остановок от Москвы до Софрино)
вычитается множество, состоящее из одного элемента - станции
Тайнинская. В нашем примере формат отношения задан множеством
имен (меток) столбцов: {ВРЕМЯ ОТПРАВЛЕНИЯ, ПУНКТ
НАЗНАЧЕНИЯ, ДНИ НЕДЕЛИ, ОСТАНОВКИ}
Здесь доменом атрибута ДНИ НЕДЕЛИ является множество:
{понедельник, вторник, среда, четверг, пятница, суббота,
воскресенье} Оно обозначается <^ога{ДНИ НЕДЕЛИ} А доменом
атрибута ОСТАНОВКИ является множество всех остановок поезда.
Кроме классических операций над отношениями в
информатике вводятся и другие операции, позволяющие оперировать с от-
74
ношениями для чисто прикладных целей. Эти операции
называются реляционными. К их числу относят операции выбора, проекции
и соединения. Все эти операции применяются к одноэлементным
отношениям, записанным в виде таблицы.
Выбор - это унарная операция над отношением. Результатом
ее применения к отношению Т является другое отношение, которое
представляет собой подмножество кортежей с определенным
значением в выделенном атрибуте. Пусть Т - отношение со схемой Я,
М- атрибут в Я и аеК. Тогда ам=а(Т) - обозначение операции
выбора: выбрать в Т кортежи, в которых значение атрибута М равно
а и составить новое отношение, элементами которого являются эти
кортежи. Таким образом, в результате применения этой операции
понижается арность отношения, точнее, она не повышается, так
как может не измениться.
Пример 51. Пусть отношение Т задается таблицей
А/,
1
2
3
3
4
Мг
2
2
1
1
2
Мг
3
1
2
3
1
М4
4
3
4
2
2
Тогда выбор по второму элементу <5м=2(Т) осуществляется
следующим образом:
Мх
1
2
4
М2
2
2
2
М3
3
1
1
м4
4
3
2
Затем осуществим выбор по третьему элементу, равному 1.
Получаем выбор (амз=;(ом2=2(7))> который задается следующей
таблицей:
мх
2
4
м2
2
2
М»
1
1
М4
3
2
75
На практике часто приходится осуществлять выбор таким
образом, чтобы значение атрибута определялось не одним
элементом, а могло принимать все значения некоторого подмножества В.
Определим операцию обобщенного выбора следующим образом:
результатом ам^в(Т) будет множество строк таблицы, у которой
атрибут М будет принимать значения из 5 аМ.
Пример 52. Для отношения Т из примера 51 осуществим
выбор таким образом, что значения атрибута М3 могут принимать
значения 53
з={1,2}.Р«
М\
2
3
4
;зультатом такого выбо]
М2
2
1
2
Мз
1
2
1
ра будет та
М4
3
4
2
Построим пример применения операции «выбор» с
помощью отношения «Расписание».
Пример 53. Пусть пассажиру требуется поехать из Москвы в
Тарасовку в воскресенье. Сначала пассажир выделит из
расписания поезда, которые идут в нужном ему направлении, т. е. поезда,
у которых имена второго атрибута принадлежат множеству
{Пушкино, Красноармейская, Александров, Софрино}
Проведя операцию выбора по второму имени атрибута, пас-
сажир получит следующий фрагмент:
ВРЕМЯ
ОТПРАВЛЕНИЯ
10-53
11-14
! 11-36
11-47
15-22
16-22
ПУНКТ
НАЗНАЧЕНИЯ
Пушкино
Красноармейская
Пушкино
Александров
Пушкино
Софрино
ДНИ
НЕДЕЛИ
воскресенье
суббота,
воскресенье
по раб. дням
ежедневно
по раб.дням
ежедневно
ОСТАНОВКИ |
со всеми ост.
кроме Красный
Строитель
со всеми ост.
Мытищи,
Пушкино,
далее везде
со всеми ост.
кроме
Тайнинская
76
Далее в расписании он выделит те поезда, для которых
множество значений четвертого имени атрибута содержит
«Тарасовка».
Проведя операцию выбора по четвертому имени атрибута,
пассажир получит следующий фрагмент;
ВРЕМЯ
ОТПРАВЛЕНИЯ
10-53
11-14
11-36
15-22
16-22
ПУНКТ
НАЗНАЧЕНИЯ
Пушкино
Красноармейская
Пушкино
Пушкино
Софрино
ДНИ
НЕДЕЛИ
воскресенье
суббота,
воскресенье
по раб. дням
по раб.дням
ежедневно
ОСТАНОВКИ
со всеми ост.
кроме Красный
Строитель
со всеми ост.
со всеми ост.
кроме
Тайнинская
Затем пассажир сделает выбор по третьему имени атрибута,
т. е. по дням недели. Тогда поезда, идущие по рабочим дням, он
исключает из рассмотрения, и окончательно он получает
следующий фрагмент:
ВРЕМЯ
ОТПРАВЛЕНИЯ
10-53
11-14
16-22
ПУНКТ
НАЗНАЧЕНИЯ
Пушкино
Красноармейская
Софрино
ДНИ
НЕДЕЛИ
воскресенье
суббота,
воскресенье
ежедневно
ОСТАНОВКИ
со всеми ост.
кроме
Красный Строитель
кроме
Тайнинская
Теперь введем оператор проекции.
Как и оператор выбора, он также является унарным
оператором на отношениях. Но если оператор выбора выбирает в
отношении подмножество строк, то оператор проекции выбирает
подмножество столбцов.
Пусть Т - отношение со схемой К и X с: К, т. е.
подмножество имен атрибутов. Проекция Г насесть отношение Т\
полученное вычеркиванием столбцов, соответствующих атрибутам в К\Х, и
77
исключением из оставшихся столбцов повторяющихся строк.
Обозначается эта операция как кх(Т).
Пример 54. Пусть отношение Т - такое же, как и в примере
51, т. е. задается таблицей
А/,
1
2
3
3
4
М2
2
2
1
1
2
Мг
3
1
2
3
1
М4
4
3
4
2
2
Х={ М, ;М3}
Тогда 71^(7) задается следующей таблицей
Мх
1
2
3
3
1 4
М3
3
1
2
3
1
Пример 55. Приведем пример применения оператора
проекции для расписания. Предположим, что пассажир регулярно
совершает путь Москва - Мытищи. Он решил переписать
интересующие его поезда, зная, что все поезда останавливаются в
Мытищах. Тогда его не интересуют ни второй, ни четвертый
атрибуты, а переписанный им фрагмент будет выглядеть следующим
образом:
78
ВРЕМЯ
ОТПРАВЛЕНИЯ
10-53
11-03
11-14
11-21
11-36
11-47
15-22
16-22
ДНИ
НЕДЕЛИ
воскресенье
кроме среды
суббота,
воскресенье
по раб. дням
по раб. дням
ежедневно
по раб.дням
ежедневно
Таким образом, пассажир применяет оператор проекции на
первый и третий атрибуты. Последней реляционной операцией,
которую мы введем на множестве, будет операция соединения.
Соединение - это бинарная операция для комбинирования двух
отношений по их общим атрибутам, ее результатом является третье
отношение.
Пусть Т есть отношение со схемой Ки а 5 - отношение со
схемой К2. Соединением отношений Ти 5является отношение (?,
содержащее все кортежи д над 7Ъ5, такие, что для каждого
кортежа д существуют кортежи д из Т и # из 5, такие, что #г = #(7) ^ =
<7(5), т. е. если вычеркнем из кортежа д атрибуты, несодержащиеся
в схеме К, то получим кортеж из Г, а если вычеркнем из кортежа #
атрибуты, несодержащиеся в схеме К, то получим кортеж из 5.
Таким образом, каждый кортеж в <2 является комбинацией
кортежа из Г и кортежа из Я с равными значениями атрибутов из К
и из & Эта операция обозначается как Т><8.
Пример 56, Пусть отношение Т задается таблицей
Мх
1
2
3
4
М2
2
2
1
2
Мг
3
1
3
1
М4
4
3
2
2
79
А отношение хУ задается таблицей
М\
1
2
3
Мг
3
1
2
М$
4
3
4
Тогда Т><\8 задается таблицей
м,
1
2
М2
2
2
Л/з
3
1
М4
4
3
А/5
4
3
Пример 57. Проиллюстрируем выполнение этой операции
на примере составления расписания. Имеем номера групп и
предметов, которые надо провести преподавателям кафедры высшей
математики в этих группах.
ГРУППА
101
101
102
102
201
201
202
203
203
ПРЕДМЕТ
математический анализ
линейная алгебра
математический анализ
линейная алгебра
теория вероятностей
математическое программирование
математическая логика
теория вероятностей
математическое программирование
Это отношение назовем отношением типа: ГРУППА
ПРЕДМЕТ
Имеем список преподавателей кафедры и названия
предметов, которые они традиционно ведут.
80
ПРЕПОДАВАТЕЛЬ
Алексеев С. С,
Иванов Л. Л.
Сидорова И. А.
Федорова А. М.
НАЗВАНИЕ ПРЕДМЕТА
линейная алгебра,
математическая логика
математический анализ,
теория вероятностей
линейная алгебра,
математическое
программирование
линейная алгебра,
математическое
программирование
Это отношение назовем преподаватель - предмет.
Осуществляя соединение двух предыдущих соединений по
атрибуту ПРЕДМЕТ, получаем следующие варианты:
ГРУППА
101
101
101
101
101
102
102
102
102
102
201
201
202
203
203
ПРЕДМЕТ
математический анализ
математический анализ
линейная алгебра
линейная алгебра
линейная алгебра
математический анализ
математический анализ
линейная алгебра
линейная алгебра
линейная алгебра
теория вероятностей
математическое
программирование
математическая логика
теория вероятностей
математическое
программирование
ПРЕПОДАВАТЕЛЬ
Иванов Л.Л.
Федорова А. М.
Сидорова А. И.
Алексеев С. С.
Федорова А. М.
Иванов Л. Л.
Федорова А. М.
Алексеев С. С.
Федорова А. М.
Сидорова А. И.
Иванов Л. Л.
Сидорова А. И.
Алексеев С. С.
Иванов Л. Л.
Сидорова А. И.
81
ГРУППА 1 ПРЕПОДАВАТЕЛЬ
Отношение типа группа-преподаватель строится с помощью
оператора проекции следующим образом:
101
101
101
102
102
102
102
102
201
201
202
203
1 203
Иванов Л. Л.
Федорова А. М.
Сидорова А. И.
Иванов Л. Л.
Федорова А. М.
Алексеев С. С.
Федорова А. М.
Сидорова А. И.
Иванов Л. Л.
Сидорова А.И.
Алексеев С. С.
Иванов Л. Л.
Сидорова А. И.
Итак, мы перечислили основные свойства отношений и
ввели операции над отношениями.
Раздел IV. ТЕОРИЯ ГРУПП
§1. Бинарные операции
Пусть X произвольное множество. Бинарной
алгебраической операцией из X в У называется произвольное отображение Т
X х X —> У Таким образом, каждой упорядоченной паре (а, Ъ),
где а ^ X Ъ е X ставится в соответствие однозначно
определенный элемент т(а,Ъ)
Говорят, что множество X замкнуто относительно бинарной
операции Т, если \/ а \/ Ь а, Ь е X т(а,Ь) еХ.
82
Иногда, вместо т(а, Ь) пишут а т Ъ , а чаще бинарную
операцию обозначают каким-нибудь специальным символом * о ? «э
+ ИТ Д.
На X может быть задано много разных операций. Желая
выделить одну из них, используют скобки (X, *) и говорят, что
операция * определяет на X алгебраическую структуру
Пример 1. На множестве целых чисел ^Г помимо
естественных операций +, • можно задать операции вида
п о т - п + т-пт
п *т ^ -п-т и т. д.
Мы получаем различные алгебраические структуры: (Д +),
(Д.)ДД о),(д*)
§2. Полугруппы и моноиды
Бинарная операция на множестве X называется
ассоциативной, если (а*Ъ)*с = а* (Ь*с) для любых а, Ь, с е. X.
Она называется коммутативной, если \/ а \/ Ь а, Ь е X
выполняется равенство а *Ъ =Ъ * а.
Пример 2, Операция * на 2, заданная правилом п *т = - п
- т, коммутативна, но не ассоциативна.
п * т =-п-т =-т-п = т*п
(1 * 2) * 3 (-1 -2) * 3 = - (-1 -2) -3 О
1 * (2 * 3) 1 * (-2 -3) - 1 - (-2 -3) 4
0*4
Пример 3. На множестве Мп(Я) всех квадратных матриц
порядка п > 1 операция умножения ассоциативна, но не
коммутативна.
Элемент ееХ называется единичным (или нейтральным)
относительно рассматриваемой бинарной операции *, если V*
хеХ выполняется е* х х * е = х.
Теорема. В любой алгебраической структуре (X, *) может
существовать не более одного единичного элемента.
83
Доказательство, Предположим противное. Пусть е еще
один единичный элемент. Тогда е е • е = е. Получили
противоречие, что и требовалось доказать.
Множество X с заданной на нем бинарной операцией
называется полугруппой, если:
- оно замкнуто относительно этой операции;
- операция ассоциативна.
Множество X с заданной на нем бинарной операцией
называется моноидом,, если:
- оно замкнуто относительно этой операции;
- операция ассоциативна;
- существует единичный элемент.
Примеры
1. Различные множества чисел вместе с операцией сложения
или умножения, замкнутые относительно рассматриваемой
операции (то есть содержащие вместе с любыми своими элементами их
сумму или, соответственно, произведение), образуют полугруппу.
2. Мп(К) квадратные матрицы порядка п с
действительными элементами;
(Мп(К)7 +) - коммутативный моноид с нейтральным
элементом нулевой матрицей;
(Мп(К), •) - некоммутативный моноид с нейтральным
элементом единичной матрицей Е.
3. Множество натуральных чисел N по сложению моноид
(единичный элемент - ноль).
4. п2 \пт\т е 21 - множество целых чисел, делящихся
на и. (л2, +) - коммутативный моноид, а (п2, •) - коммутативная
полугруппа без единицы (п > 1).
5. Пусть О, - произвольное множество и М(Г2) - множество
всех его преобразований (отображений ^ в себя). (М(П),о) -
моноид, где о - композиция отображений, единичный элемент -
тождественное преобразование.
84
Выделим частный случай, когда О - конечное множество из
п элементов. Каждое преобразование/ О. —> П определяется
указанием упорядоченной последовательности У(1),Д2), ...,У(гс).
Выбирая всевозможные последовательности, получим ровно пп
преобразований. Пусть п = 2. Элементов М(П) будет 2=4.
Элементы е, / §, И моноида М({1,2}) и их полярные произведения
полностью задаются двумя таблицами.
е
/
§
и
1
1
2
1
2
2
2
1
1
2
е
I
ё
и
е
е
/
ё
к
г
/
е
ё
И
ё
ё
к
ё
к
к
к
ё
ё
к
М( \1,2}) - некоммутативный моноид.
6. Пусть О - произвольное множество. Р(Г2) - множество его
подмножеств. Рассмотрим операции пересечения и объединения.
(Аг\В)пС = Ап(Вг\С)\
Аг^П = А /^
(Р(П),п) - моноид.
Единичный элемент-само множество О..
(АиВ)иС = Аи(ВиС/\
А^0 = А ]=>
(Р(П),и) - моноид.
Единичный элемент - пустое множество.
7 Если на множестве Рх всех конечных
последовательностей элементов произвольного множества (алфавита) X задать
операцию * по правилу (х\> — >хт)*(у1,...,уп)
(х\>->хт*У\-~>Уп)> то Рх -полугруппа.
Элемент а моноида (М, •, е) называется обратимым, если
найдется элемент Ь еМ у для которого а-Ь = е = Ь-а
8 этом случае элемент Ь называется обратным.
85
Теорема. Обратный элемент однозначно определен.
Доказательство. Предпололсим противное: существует
такой элемент а, у которого два обратных 6,6' Итак, имеем:
а-Ь = е -Ъа и а-Ъ ~е-Ъ -а, следовательно,
Ь =е-Ь -(Ь- а)Ъ = Ъ(а -Ь ) -Ъ-е-Ъ , т. е. Ъ -Ъ
Получили противоречие, что и требовалось доказать.
Пример 4. Приведем пример решения задачи.
Показать, что множество 2 с операцией °
пот = п + т + пт является коммутативным моноидом. Что
служит в (2,о) нейтральным элементом? Найти все обратимые
элементы.
Решение
1) очевидно, что множество 2 замкнуто относительно
операции оэ
2) докажем ассоциативность
(пот)°1 = п + т + пт + 1 + п1 + т1 + пт1 |
по(то1) = по(т + 1 + т1) = п + т+1 + т1 + пт + п1 + пт1)
=> ассоциативность выполняется;
3) существует единичный элемент ноль
поО = п + 0 + п-0 = п = 0°п
4) V п,т е 2 имеет место коммутативность топ— пот
для => коммутативный моноид.
Найдем обратимые элементы
по х = О
=>
пох = п + х + пх = 0
п _7
х~~ м , /' Х(=^=> п может быть только О
и других обратимых элементов нет.
86
Пример 5. На множестве действительных чисел Я зададим
операцию х х х у - 8Ш х • $т у Проверим, ассоциативна ли эта
операция на множестве Л
(х X у) X 2 = 81П(81П X • 81П у) • 81П 2, X X (у X г) = 81П X 8Ш(81П у • 81П 2).
К П
при х - у ~ — и 2 ~ — получим
2 6
81П(31П 81П ) • 81П = — 81П 1,
2 2 6 2
1 • 1 • 1
—81П1 Ф 81П —, значит, операция х не ассоциативна.
2 2
Задание 21
1. Ассоциативна ли операция х на множестве М, если:
а) М - ТУ, х х у - ху
б)М = Л^, хху = НОВ(х;у);
ъ) М - И, х х у = 2ху;
г) Л/= 2, ххд; = *-;/;
д) М = 2, хху = х2 +у2'
е) М- множество матриц Лтл размером ляхи, «х» -
операция сложения матриц.
'х >Л
, где х,уеК,
2. Пусть 5 полугруппа матриц
с операцией умножения. Найти в этой полугруппе левый и правый
нейтральные элементы, левый и правый обратные элементы.
3. На множестве М определена операция о по
правилу х о у = х Доказать, что (М, о) - полугруппа. Что можно
сказать о существовании нейтрального элемента? В каких случаях эта
полугруппа является группой?
4. На множестве М2, где М- некоторое множество,
определена операция о по правилу (хуу) о (г,/) = (х,1). Является ли М
87
полугруппой относительно этой операции? Существует ли в М2
нейтральный элемент?
5. Сколько элементов содержит полугруппа, состоящая из
всех степеней матрицы. Является ли эта полугруппа группой?
6. На множестве М нечетных функций задана операция
сложения. Является ли (М, +) группой?
7 Какие из указанных числовых множеств с операциями
являются группами:
а) (А, +), где А - одно из множеств N.2,(),Я,С;
б) (А, •), где А - одно из множеств М, 2, <2,#, С;
в) (А0,*) где А - одно из множеств М,2,(),К,С;
аД)=А\{0};
г)({-1;1}>-);
д)({-1Д;/' -/},•).
8. Какие из указанных множеств квадратных вещественных
матриц фиксированного порядка образуют группу:
а) множество симметрических матриц относительно
сложения; умножения;
б) множество невырожденных матриц относительно
сложения; умножения;
в) множество матриц с фиксированным определителем с1
относительно умножения;
г) множество диагональных матриц относительно
сложения; умножения;
д) множество диагональных матриц, все элементы
диагоналей которых отличны от нуля, относительно умножения;
е) множество верхних треугольных матриц относительно
умножения;
■ " , .Л
ж) множество ненулевых матриц вида
х у
■ух;
(х,у € К) относительно умножения;
з) множество ненулевых матриц вида
х ул
А ух.
, где Л
фиксированное вещественное число, относительно умножения.
г, тт , ах + Ъ
9 Доказать, что множество функции вида у ,
сх + с1
а,Ь,сД е К и ай-Ъс ^ 0, является группой относительно
операции композиции функций.
89
СПИСОК ЛИТЕРАТУРЫ
1. Ермаков В. И. Максименко М. Н. Методические
указания к выполнению практических занятий по математике. Основы
теории множеств. М.. Изд-во Рос. экон. акад., 2001.
2. Ермаков В. К Максименко М. Н. Декартовы
произведения: Лекция. М.. Изд-во Рос. экон. акад., 2003.
3. Мейер Д. Теория реляционных баз данных. М.. Мир,
1987
4. Яблонский СВ. Введение в дискретную математику. Т 1.
М.. Наука, 1979.
90
ПРАКТИКУМ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Составители: [ЕРМАКОВ Валерий Иванович!
ЕРОХИНА Татьяна Александровна
ЛОКУЬЩЕВСКИЙ Вячеслав Олегович
МАКСИМЕНКО Марианна Николаевна
ШЕМЕТКОВА Ольга Леонидовна
Редактор Л. Г Итберг
Оформление обложки О. В. Василевская
Подписано в печать 01.03.07 Формат 60x84 1/16.
Печать офсетная. Бумага офсетная.
Усл. печ. л. 5,75. Уч.-изд. л. 4,09. Тираж 300 экз. Заказ 60.
Издательство Российской экономической академии
имени Г В. Плеханова.
115998, Москва, Стремянный пер., 36.
Отпечатано в типографии РЭА им. Г В. Плеханова.
115998, Москва, ул. Зацепа, 4/14.