Методическая разработка темы "Теория множеств" для студентов 2 курса СПО
методическая разработка по теме

Методический комплект по разделу

"Теория множеств"

На изучение данного раздела отводится 14 часов  (8 часов - лекции, 6 часов - практические занятия).

Распределение часов по темам:

Тема 1.1. Алгебра множеств. ( 2 ч лекции + 2 ч п/з)

Множество. Пустое множество. Синглетон. Равенство множеств. Кардинальное число множества. Подмножества. Собственные и несобственные подмножества. Булеан множества. Предикат. Диаграммы Эйлера-Венна. Универсальное множество (универсум).

Объединение и пересечение множеств: коммутативность, ассоциативность, дистрибутивность. Дополнение множества. Законы Де Моргана. Разность множеств. Симметрическая разность множеств. Закон поглощения. Закон склеивания. Теоретико-множественные преобразования.

Тема 1.2. Бинарные отношения. ( 2 ч лекции + 2 ч п/з)

Понятие бинарного отношения. Бинарные отношения в множестве: симметрия, асимметрия, антисимметрия, транзитивность, рефлексивность, антирефлексивность, эквивалентность. Отношения строгого и нестрогого порядка.

Тема 1.3. Элементы комбинаторики. ( 4 ч лекции + 2 ч п/з)

Правило произведения. Комбинаторные конструкции (перестановки, сочетания, размещения). Алгоритмическое перечисление основных комбинаторных конструкций. Бином Ньютона.

Подстановки. Произведение подстановок и его свойства. Инверсия. Отображения.

Изучение раздела оканчивается контрольной работой.        

Общие понятия теории множеств.

Введение

Теория множеств — раздел математики, в котором изучаются общие свойства множеств. Теория множеств лежит в основе большинства математических дисциплин; она оказала глубокое влияние на понимание предмета самой математики. «Множества» окружают нас повсюду. Люди, студенты, звезды, понятия — все эти предметы, мыслимые вместе, образуют множества. Коллектив, созвездие, полк — это тоже множества людей или звезд.

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

Она значительно облегчает запись на различных языках программирования. Рассмотрение теории множеств дает ключ к дальнейшему более глубокому понимаю всех отраслей математики.

До второй половины 19-го века понятие "множества" не рассматривалось в качестве математического ("множество книг на полке", "множество человеческих добродетелей" и т. д всё это чисто бытовые обороты речи). Положение изменилось, когда немецкий математик Георг Кантор разработал свою программу стандартизации математики, в рамках которой любой математический объект должен был оказываться тем или иным "множеством".

        Понятие множества, элементы множества – первичные базисные неопределяемые понятия, на которых строится теория множеств. Понятие множества нельзя свести к каким-то более простым математическим объектам, но можно пояснить с помощью наглядных примеров.

1.1. Язык теории множеств.

Множество – это совокупность элементов, объединенных некоторым признаком, свойством: множество книг в библиотеке, множество студентов в группе.

Способы задания множества:

1. Перечислить все его элементы.

Например: множество, состоящее из четырех элементов .

2. Указать свойство, которым обладают все его элементы.

Например: множество натуральных чисел, меньших 20 можно задать следующим образом: .

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

 Например:

Если элемент  принадлежит множеству , используют запись , если не принадлежит, то .

Во множестве могут быть выделены подмножества. Если каждый элемент множества K принадлежит множеству М, множество К называют подмножеством множества М и обозначают .

Например:

1) множество всех книг данного автора в библиотеке, есть подмножество всех книг в библиотеке.

2) множество студентов, обучающихся на "4" и "5" в группе есть подмножество всех студентов группы.

3)  четных чисел меньших или равных 6, есть подмножество множества .

Пустое множество является подмножеством любого множества.

Если одновременно А ⊂ В и В ⊂ А, то говорят, что множества А и В равны, т.е. состоят из одних и тех же элементов. В этом случае принадлежность элемента множеству А необходима и достаточна для его принадлежности множеству В.

Булеаном множества М назовем множество всех его подмножеств.

Пример: Рассмотрим множество . Составим все подмножества множества М.

, , ,

, , , , , ,

, , , ,

.

Подмножества   и  являются несобственными подмножествами множества М, остальные – собственные подмножества. Всего мы нашли 16 различных подмножеств множества М. Это число равно .

В общем случае, для любого конечного множества, состоящего из n элементов, число возможных подмножеств равно .

Множество U, состоящее из всех возможных элементов, обладающих данным признаком, называется универсальным.

1.2. Классификация множеств.

Основной характеристикой множеств является количество элементов, содержащихся в этом множестве.

Множество, содержащее конечное число элементов называется конечным. Множество, не являющееся конечным, называется бесконечным. Количество элементов конечного множества называют его мощностью. Если множество не содержит элементов, то оно называется пустым и обозначается .

Два множества А и В называются эквивалентными, или, равномощными, если между их элементами можно установить взаимно-однозначное соответствие.

Пример: Рассмотрим множества, состоящие из букв слов:

;        ;        ;        .

Множества А, В и С имеют равные мощности: , а мощность множества D меньше . При этом множества А и В равны, а множества А и С – эквивалентны.

Эталоном для сравнения множеств служит натуральный ряд чисел. Поэтому все числовые последовательности, содержащие различные элементы, эквивалентны натуральному ряду чисел, что видно по их индексам.

        Бесконечное множество, эквивалентное множеству натуральных чисел, называется счетным. Говорят, что все элементы счетного множества пронумерованы. В противном случае бесконечное множество будет несчетным. В 1878 году Георг Кантор доказал, что множество точек расположенных на отрезке от 0 до 1 несчетно.

1.3. Изображение множеств.

        Множества изображаются при помощи диаграмм Эйлера-Венна (кругов на плоскости). Элементы множества изображаются точками, внутри круга, если они принадлежат данному множеству и вне его, если не принадлежат.

, .

1.4.  Операции над множествами.

        Основными операциями над множествами являются операции пересечение, объединение, разность, симметрическая разность и  дополнение.

1. Пересечением множеств А и В называется множество , состоящее из элементов, которые принадлежат одновременно как множеству А так и множеству В.

Пример: Если , , то .

При помощи диаграмм Эйлера-Венна пересечение множеств изображается следующим образом:

2. Объединением множеств А и В называется множество , состоящее из элементов, которые принадлежат или множеству А или множеству В.

Пример: Если , , то .

При помощи диаграмм Эйлера-Венна объединение множеств изображается следующим образом:

3. Разностью  множеств А и В называется множество , состоящее из элементов множества А, которые не принадлежат  множеству В.

Пример: Если , , то .

При помощи диаграмм Эйлера-Венна разность множеств изображается следующим образом:

По диаграмме видно, что  можно заменить на .

4.  Симметрической разностью  А и В называется множество , состоящее из элементов множеств А или В, но не принадлежащих этим множествам одновременно.

Пример: Если , , то .

При помощи диаграмм Эйлера-Венна симметрическая разность множеств изображается следующим образом:

5. Дополнением множества А до множества U называется множество , состоящее из элементов множества U, которые не принадлежат множеству А.

При помощи диаграмм Эйлера-Венна дополнение множества изображается следующим образом:

1.5. Свойства операций.

Операции над множествами обладают рядом свойств, похожих на свойства операций сложения и умножения чисел.

Используя эти операции можно выражать одни множества через другие, при этом сначала выполняется операция дополнения, затем пересечения и только затем операции объединения и разности. Для изменения порядка в выражении используют скобки.

Пример. Доказать справедливость следующего равенства и проверить результат на диаграмме Эйлера-Венна: .

Решение. Преобразуем по очереди левую и правую части данного равенства:

1) . Заменили разность на пересечение с дополнением.

2)

. 

Использовали переход от разности к пересечению, закон де Моргана, свойство дистрибутивности, свойство и .

После преобразования видно, что левая и правая части равенств одинаковые, следовательно, равенство доказано.

Проверим равенство на диаграмме Эйлера-Венна.

1.6. Формула включений и исключений.

Найдем сколько элементов содержится в множестве А ∪ В. Основная формула нахождения числа элементов суммы двух множеств

n(А ∪ В) = n(А) + n(В) – n(А ∩ В).

Действительно, n(А ∪ В) — это сумма числа элементов множеств А и В, но при подсчете элементы, принадлежащие А ∩ В учитывались дважды. С помощью данной формулы можно получить формулы для определения числа элементов суммы любого числа множеств. Например для трих множеств она выглядит следующим образом:

n(А ∪ В ∪ С) = n(А) + n(В) + n(С) – n(А ∩ В) –  n(В ∩ С) – n(А ∩ C) + n(А ∩ В ∩ С).

        Данная формула используется для решения различных задач.

Пример. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

Решение.

Обозначим через А — множество школьников, знающих анг-ийский язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.

Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,

n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.

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

n(A ∪ N ∪ F) = n(A) + n(N) + n(F) =

= n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =

= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.

Следовательно, не знают ни одного иностранного языка: 100 – 80 = 20 школьников.

Эту же задачу можно решить с помощью диаграммы Эйлера–Венна

Так как 3 языка знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7,

немецкий и французский — 8 – 3 = 5 школьников.

Только английский знают 42 – (2 + 3 + 7) = 30, только немецкий — 30 – (2 + 3 + 5) = 20,

только французский — 28 – (3 + 5 + 7) = 13 школьников.

Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

Упражнения.

1. Задайте перечислением элементов множество, заданное характеристическим свойством:

а) ,       б) ,

в) ,               г) .

2. Дано множество М:

а) ,    б) ,     в)

г) ,        д)      е) .

1)  Приведите по три примеров элементов каждого множества.

2) Укажите каким из множеств принадлежат числа 3, 4, 5, 13, 25, , , .

3) Укажите каким из множеств не принадлежат эти числа. Запишите эти утверждения символически.

3. В данном множестве все элементы, кроме одного, обладают некоторым свойством. Опишите это свойство и найдите элемент, не обладающий им.

а) {сумма; разность; множитель; частное};

б) {4; 16; 22; 27; 30; 34};

в) {1; 15; 16; 25; 64; 121};

г) {синий; красный; круглый; бежевый; зеленый};

д) {4; 6; 12; 81; 441; 1113};

е) {Обь; Иртыш; Волга; Байкал; Ангара; Амур};

   ж) {шар; пирамида; параллелограмм; цилиндр; конус}. 

4. Составьте цепочки включений, так чтобы каждое следующее множество содержало предыдущее.

а) А — множество всех позвоночных;

В — множество всех животных;

С — множество всех волков;

D — множество всех млекопитающих;

Е — множество всех хищных млекопитающих.

б) А — множество всех трапеций;

В — множество всех прямоугольников;

С — множество всех четырехугольников;

D — множество всех квадратов;

Е — множество всех параллелограммов;

F — множество всех многоугольников.

      5. На множестве U всех букв русского алфавита заданы множества:

, , .

Найдите следующие множества, укажите их мощность  и изобразите их диаграммами Эйлера-Венна:

а) ,                 б) ,                         в) ,

г) ,         д) ,         е) .

      6. Докажите законы поглощения, де Моргана, склеивания и Порецкого, используя диаграммы Эйлера-Венна.

     7. Используя свойства операций, упростите выражения и проверьте правильность с помощью диаграмм Эйлера-Венна:

а) ,

б) ,

в) ,

г) ,

д) ,

е) .

8. С помощью диаграмм Эйлера-Венна решите следующие задачи:

1. Лекции по экономике посещают 20 студентов, по математике – 30. Найти число студентов, посещающих лекции по экономике или математике, если:

а) лекции проходят в одно и то же время.

в) лекции проходят в разные часы и 10 студентов слушают оба курса.

2. В ящике лежат 120 деталей, из них на автомате №1 обработано 82 штуки, на автомате №2 – 23, а на автомате №3 – 42 штуки. 18 деталей было обработано на автоматах №1 и №2, 17 деталей на автоматах №1 и №3 и 15 – на автоматах №2 и №3. 10 деталей прошли обработку на всех трех автоматах. Сколько деталей не обработано ни на одном из автоматов?

3. Управление имеет 150 предприятий, из них 80 выпускают продукцию А, 60 продукцию В и 50 продукцию С. Продукцию А и В выпускают 20 предприятий, продукцию В и С – 30 предприятий, продукцию А и С – 10. Сколько предприятий управления не выпускают ни одного из указанных видов продукции, если все виды продукции А, В и С выпускают 5 предприятий.

4. Среди 100 студентов института иностранными языками занимались: немецким – 30 человек, французским – 42 человека, испанским – 28, испанским и немецким – 8 человек, немецким и французским – 5 человек, испанским и французским – 10; три студента изучали все три языка. Сколько студентов изучали французский язык? Сколько студентов не изучали ни одного из иностранных языков?

5. В отчете об обследовании 100 студентов сообщалось, что количество студентов, изучающих немецкий, французский и английский язык таково: все три языка изучают 5 человек, немецкий и английский – 10, французский и английский – 8, немецкий и французский – 20, английский язык – 30 человек, немецкий – 23, французский – 50. инспектор, представивший этот отчет, был уволен. Почему?

6. Исследование заболеваний раком показало, что доля курильщиков среди тех, кто болен раком легких, больше доли курильщиков, не больных этим заболеванием. Доказать, что процент курильщиков, болеющих раком легких, больше, чем процент некурящих, больных раком легких.

7. При обследовании читательских вкусов студентов оказалось, что 60% студентов читают журнал А, 50% - журнал В, 50% журнал С, 30% - журналы А и В, 20% - журналы В и С, 40% - журналы А и С, 10% - журналы А, В и С. Сколько процентов студентов

1) не читают ни одного из журналов

2) читают два журнала

3)читают не менее двух журналов?

8. На одной из кафедр университета работают тридцать человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семь – немецкий, шесть – французский. Пять человек знают английский и немецкий, четыре – английский и французский, три – немецкий и французский. Сколько человек

1)знают все три языка

2) знают два языка

3) знают только английский язык?

9. На курсах иностранных языков (английский, французский, немецкий языки) учатся 300 человек. Сколько человек изучают каждый из указанных языков и сколько человек изучают 2 языка одновременно, если известно, что:

1) слушатели, изучающие английский язык, не изучают немецкого.

2) число слушателей, изучающие английский или французский язык, равно 230 и равно числу слушателей, изучающих французский или немецкий язык.
3) число слушателей, изучающих английский или немецкий языки, равно 250, а число слушателей, изучающих английский и французский языки равно 60?

Лекция № 2.

Бинарные отношения.

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

        Исследователя окружающего мира интересуют различные свойства объектов: свойства, относящиеся к отдельным объектам (например, "быть женщиной", "иметь форму правильного пятиугольника", "быть сделанным из металла", "быть зеленым", "иметь низкую теплопроводность") и свойства, характеризующие связи между несколькими объектами (например, свойства "быть родственниками" и "быть больше" относятся к парам объектов, свойство "находиться между" - к тройкам объектов, свойство "располагаться в вершинах квадрата" - к четверкам объектов). Такие свойства принято называть отношениями. При этом свойства отдельных объектов называются унарными отношениями, свойства, относящиеся к парам объектов, - бинарными отношениями, свойства, относящиеся к наборам из n объектов, - n-арными отношениями. Ниже мы ограничимся рассмотрением лишь бинарных отношений.

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется - геометрический аспект теории бинарных отношений есть попросту теория графов.

2. Кортежи.

Пусть А – конечное множество, состоящее из n элементов, f:  - функция, задающая порядок на А, т.е. правило, по которому каждому элементу множества А ставится в соответствие натуральное число от 1 до n, причем одному числу из соответствует один элемент из А.

Пару назовем упорядоченным множеством, или перестановкой, из n элементов.

Кортежем длины n из элементов множества А называется упорядоченная последовательность элементов этого множества.

Пусть А – конечное множество, элементами которого являются некоторые символы, например цифры, буквы, знаки препинания. Такие множества принято называть алфавитом над заданным множеством. Алфавит есть кортеж попарно различимых символов, называемых буквами алфавита. Элементы множества  принято называть словами длины n.

Например. Шестизначный телефонный номер является словом длины 6 над алфавитом цифр .

        Рассмотрим множество В, состоящее из двух элементов 0 и 1. Кортежи длины m из этих элементов обозначим . Тогда . Такие кортежи называют векторами. Они имеют широкое применение в дискретной математике и не только.

 Кортежи из 0 и 1 могут быть сообщениями, передаваемыми по некоторому каналу связи с помощью импульсов, каждый из которых принимает одно из двух значений, например азбука Морзе. Практический прикладной характер кортежей проявляется при использовании штриховых кодов, которые широко применяются для сообщении информации о характеристики объекта. Например, штрих-кодом снабжены все товары в магазине.

3. Декартовы произведения.

Декартовым произведением множеств X и Y называется множество  всех упорядоченных пар (x, y) таких, что x X, yY.

Пример. Найти декартово произведение множеств  и .

Решение. Декартово произведение равно .

Декартово произведение множества на себя называется декартовым квадратом и обозначается .

Пример. Определить декартов квадрат множества  .

Решение. .

Найдем число элементов декартова произведения множеств.

Пусть n(X) = m; n(Y) = k. Тогда n(X × Y) = m k.

Действительно, пусть X = {х1; х2; ...; хm}, Y = {у1; у2; ...; уk}.

Составим таблицу, в которой запишем все элементы декартова произведения.

Декартовым произведением множеств X1; X2; ...; Xm называется множество всевозможных упорядоченных наборов α = (х1, х2, ..., хm) из m чисел, причем х1 ∈ X1, х2 ∈ X2, хm ∈ Xm. Обозначается декартово произведение X1 × X2 × ... × Xm.

X1 × X2 × ... × Xm = {(х1, х2, ..., хm) | хi ∈ Xi (i = 1, ...., m)}.

Каждый набор α = (х1, х2, ..., хm), называется кортежем длины m, составленным из элементов множеств X1; X2; ...; Xm.

Если X1 = X2 = ... = Xm, то есть дано декартово произведение X × X × ... × X = Xm, то α = (х1, х2, ..., хm) называется кортежем длины m, составленным из элементов множества X. Элемент хi называется i-ой компонентой кортежа.

Легко подсчитать, что число элементов декартова произведения X1 × X2 × ... × Xm равно n(X1 × X2 × ... × Xm) = n(X1)·n(X2) ...·n(Xm).

Свое название декартово произведение получило в честь выдающегося французского математика и философа Рене Декарта (1596 – 1650), являющегося автором метода координат. На плоскости двумерные кортежи – это пары вида (x; y), в пространстве – трехмерные кортежи в виде тройки в виде тройки чисел (x; y; z), где элементами кортежа являются соответствующие координаты точки.

4. Соответствия между множествами.

Соответствием между множествами X и Y (или соответствием из X в Y) называется любое подмножество декартова произведения .

Поскольку соответствие – это подмножество, то его можно задать как любое множество, т.е. либо перечислив все пары элементов, находящихся в данном соответствии, либо указав характеристическое свойство элементов этого подмножества. Например, соответствие между множествами X={1, 2, 4, 6} и Y={3, 5} можно задать:

1) при помощи предложения с двумя переменными: a при условии, что aX, bY;

2) перечислив пары чисел, принадлежащих подмножеству декартова произведения XY: {(1, 3),(1, 5), (2, 3), (2, 5), (4, 5)}. К этому способу задания относят также задание соответствия при помощи графа  и графика.

Графом в математике называется конечная совокупность точек, называемых вершинами графа; некоторые из них соединены друг с другом линиями, которые называются ребрами графа. График соответствия представляет собой изображение множества XY в виде точек на координатной плоскости. Представление соответствия в виде графа и графика позволяет изображать его в тех ситуациях, когда в заданном соответствии находится бесконечное множество пар чисел.

Например: А = {1, 2, 3}, B = {1, 2, 3, 4, 5, 6}.

        Пусть задано соответствие R между множествами Х и У, т.е. R: , , . Для некоторого элемента а из множества Х поставлен в соответствие некоторый элемент в множества У. Тогда элемент в называется образом элемента а, а элемент а – прообразов элемента в.

Может случиться, что из данной точки не выходит ни одна стрелка, например, b. Тогда образ элемента b пуст.

Множество Х называют областью отправления соответствия R, множество У – областью прибытия.

Совокупность всех элементов из Х, имеющих непустые образы, называют множеством определения соответствия R. Множество всех элементов из У, имеющих непустой полный прообраз, называют множеством значений соответствия R.

5. Отношения. Бинарные отношения.

Если множества X и Y совпадают, то соответствие между множествами X и Y называют бинарным отношением на множестве X.

Например, отношение = {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел.

Хорошо известными примерами отношений из школьного курса математики являются:

• на множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты";
• на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают";
• на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".

Факт принадлежности кортежа (x, y) соответствию , часто обозначают с помощью так называемой инфиксной формы записи: xay. Типичными примерами таких записей из курса математики являются: x > y, a = b, 84, m||l, a b и т. п.

Отношения могут задаваться формулами:

• формулы

y = x2 +5x - 6 или x+y<10

задают бинарные отношения на множестве действительных чисел;

• формула

x + y = любовь,

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

Задание отношений в виде формул достаточно широко распространено. Об этом свидетельствуют многочисленные надписи на деревьях заборах или стенах домов типа:

"Вася + Маша = любовь", увековечивающие принадлежность конкретной пары (Вася, Маша) отношению "любовь".

Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {a, b, c, d, e}.

Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX - горизонтальная ось, а OY - вертикальная ось) и на каждой отметим точки, представляющие элементы множества X .

Считая метки a, b, c, d, e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x, y) такими, что (x, y) . На рисунке  изображено множество точек, соответствующее отношению= {(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.

Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношения  дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y. Граф бинарного отношения  изображен на рисунке 3.

Для бинарных отношений, определенных на конечных множествах, часто используется матричный способ задания. Пусть на некотором конечном множестве X задано отношение . Упорядочим каким-либо образом элементы множества X = {x1, x2, ..., xn} и определим матрицу отношения A = [aij] следующим образом:

Таким образом, матрица отношения , представленного графом на предыдущем рисунке, имеет вид

Часто матрицу отношения называют булевой, чтобы подчеркнуть, что ее элементами являются только нули и единицы.

6. Свойства отношений.

Очевидно, что произвольные бинарные отношения изучать в общем плане не особенно интересно, о них можно сказать очень мало. Однако если отношения удовлетворяют некоторым дополнительным условиям, относительно них можно делать более содержательные утверждения. В этом разделе мы рассмотрим некоторые из основных свойств бинарных отношений.

1. Бинарное отношение  на множестве X называется рефлексивным, если для любого элемента aX выполняется условие a  a.

Если отношение представлено с помощью графа, то рефлексивность этого отношения означает, что в каждой вершине графа обязательно имеется петля.

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

Например: отношение "быть не больше".

2. Бинарное отношение  на X называется антирефлексивным, если ни для одного aX не выполняется условие a  a.

Например: отношения "быть больше" или "быть меньше".

3. Бинарное отношение  на множестве X называется симметричным, если из a  b следует b  a.

Примерами симметричных отношений являются:

• отношение перпендикулярности на множестве прямых;
• отношение касания на множестве окружностей;
• отношение "быть похожим" на множестве людей;
• отношение "иметь одинаковый пол" на множестве животных.

Отношение "x брат y" на множестве всех людей не является симметричным. В то же время отношение "x брат y" на множестве мужчин симметричным является.

4. Бинарное отношение на множестве X называется антисимметричным, если для любых различных элементов a и b условия a  b и b  a не выполняются одновременно.

Например, отношение "делится" на множестве натуральных чисел является антисимметричным, так как из  и  следует, что a = b. Однако на множестве целых чисел отношение "делится" антисимметричным не является, так как  и , но .

Отношения "выше", "тяжелее", "старше" антисимметричны на множестве людей. Отношение "быть сестрой" на множестве всех людей антисимметричным не является.

В графе антисимметричного отношения две различные вершины могут быть соединены не более чем одной дугой.

5. Бинарное отношение на множестве X называется асимметричным, если для любых  элементов a и b условия a  b и b  a не выполняются одновременно:

6. Бинарное отношение a на множестве X называется транзитивным, если для любых трех элементов a, b, c X из ab и bc следует ac.

Примерами транзитивных отношений служат:

• отношение "делится" на множестве действительных чисел;
• отношение "больше" на множестве действительных чисел;
• отношение "старше" на множестве людей игрушек;
• отношение "иметь одинаковый цвет" на множестве детских игрушек;
• отношение "быть потомком" на множестве людей.

Феодальное отношение "быть вассалом" не является транзитивным. Это в частности подчеркивается в некоторых учебниках истории: "вассал моего вассала не мой вассал".

Отношение "быть похожим" на множестве людей не обладает свойством транзитивности.

Для произвольного отношения  можно найти минимальное транзитивное отношение

такое, что . Минимальность отношения понимается в том смысле, что для любого транзитивного отношения  из  следует . Таким отношением является транзитивное замыкание отношения .

7. Бинарное отношение a на множестве X называется антитранзитивным, если отношение не обладает свойством транзитивности.

Например: "быть перпендикулярным" на множестве прямых плоскости.

8. Бинарное отношение  на множестве X называется связным, если для любых двух различных элементов a и b имеет место ab, либо ba:

Примером связного отношения является отношение "больше" на множестве действительных чисел. Отношение "делится" на множестве целых чисел связным не является.

7. Отношение эквивалентности.

Важным видом бинарного отношения является отношение эквивалентности.

Бинарное отношение  на множестве X называется отношением эквивалентности на X, если  рефлексивно, симметрично и транзитивно.

Отношение эквивалентности часто обозначают символами ~,.

Примерами отношения эквивалентности служат:

• отношение тождества IX = {(a, a)|aX} на непустом множестве X;
• отношение параллельности на множестве прямых плоскости;
• отношение подобия на множестве фигур плоскости;
• отношение равносильности на множестве уравнений;
• отношение "иметь одинаковые остатки при делении на фиксированное натуральное число m" на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m);
• отношение "принадлежать одному виду" на множестве животных;
• отношение "быть родственниками" на множестве людей;
• отношение "быть одного роста" на множестве людей;
• отношение "жить в одном доме" на множестве людей.

Отношения "жить на одной улице", "быть похожими" на множестве людей отношениями эквивалентности не являются, так как не обладают свойством транзитивности.

Из перечисленных выше свойств бинарных отношений следует, что пересечение отношений эквивалентности является отношением эквивалентности.

8. Отношения порядка.

Порядок играет огромную роль в нашей жизни. Люди на протяжении всей истории пытались упорядочить отношения между собой, окружающие явления. Без порядка невозможно представить жизнь человека. Попробуйте представить общество, в котором царит анархия или словарь, в котором слова расположены хаотично. Но что такое порядок? С некоторыми упорядочениями мы настолько свыклись, что часто их просто не осознаем, как, например, грамматический порядок слов в предложении.

Упорядоченное множество с небольшим числом элементов наглядно представляется ориентированным графом. При этом элементам множества M сопоставляются вершины графа (обозначаются на рисунке точками), а элементам отношения a - дуги (линии со стрелками).

Так, например, на рисунке  приведен ориентированный граф, представляющий отношение = {(a, a), (a, b), (a, c), (b, c)} на множестве M = {a, b, c, d}.

Задать порядок на множестве можно различными способами. Так, например, в таблице приведено три способа упорядочения четырех стран.

На рисунке  приведены ориентированные графы, представляющие отношения "делится" и "меньше" на множестве M = {1, 2, 3, 4} натуральных чисел.

Отношение  на множестве называется отношением частичного порядка, если оно обладает следующими свойствами:

1. рефлексивность,
2. антисимметричность,
3. транзитивность.

Множество, на котором введено отношение частичного порядка, называется частично упорядоченным. Обычно отношение порядка обозначают знаком . Если для двух элементов x и y выполняется , то говорят, что x "предшествует" y.

Например: Рассмотрим отношение "старше" на множестве людей. Очевидно, что оно транзитивно и антисимметрично, и, следовательно, является отношением порядка. Иерархия животных, построенная по этапам эволюции, является отношением порядка.

Отношение  на множестве называется отношением полного порядка, если оно обладает следующими свойствами:

1. антирефлексивность,
2. антисимметричность,
3. транзитивность.

Множество, на котором введено отношение полного порядка, называется строго упорядоченным. Обычно отношение порядка обозначают знаком <.

Упражнения.

1. Найдите декартовы произведения множеств:

а)  и ,        б)  и .

2.  Задайте следующие соответствия  для множеств хХ, у У, где Х={1, 2, 3, 4, 5};

 У={6, 7, 8, 9, 10, 11, 12}:

а) x делит y (без остатка),

б) x меньше y,

в) x равно y,

г) у-х=2

парами (х;у), а также при помощи координатной сетки.

3. Пусть M={1, 2, 3, 4, 5, 6}. Задать в явном виде (списком) и матрицей отношение , заданное на множестве , если  означает «быть строго меньше».

4.  Укажите рефлексивные отношения:

1) Таня - сестра Зины;

2) а

3) а=b, где а и b - натуральные числа;

4) треугольник а подобен треугольнику b;

5) площадь круга а больше площади круга b;

6) Иван написал письмо Петру;

7) выражения а и b имеют одно и то же значение в множестве числовых

выражений.

5.  Укажите антирефлексивные отношения:

1) а похож на b (в множестве людей);

2) в книге а в два раза больше страниц, чем в книге b;

3) фраза а имеет тот же смысл, что и фраза b;

4) Петров и Сидоров имеют одинаковый рост;

5) дорога а имеет ту же длину, что и дорога b;

6) Смирнов и Васильев живут на третьем этаже;

7) поезд а идет быстрее поезда b.

6.  Укажите симметричные отношения:

1) Таня – сестра Пети;

2) прямая А перпендикулярна прямой В;

3) город Томск расположен севернее города Новосибирска;

4) тетрадь находится в портфеле;

5) Зина – сестра Оли;

6) 25+10=15+20;

7) прямая А параллельна прямой B.

7.  Укажите асимметричные отношения:

1) я встретился со своим другом;

2) Иван пришел в гости к своему другу Петру;

3) дерево свалилось на дорогу;

4) Иванов проиграл в шахматы Петрову;

5) Андрей не проиграл в шашки Сергею;

6) Останкинская башня выше Эйфелевой башни;

7) Сидоров хорошо относится к Петрову;

8) масса бетонной плиты А не превышает массы стальной плиты B.

8.  Укажите антисимметричные отношения:

1) Иван узнал Петра;

2) лесоруб спилил дерево;

3) столяр изготовил оконную раму;

4) Иванов поздоровался с Орловым;

5) олень увидел в зарослях тигра;

6) число а не больше числа b, где а, b принадлежат {1, 2, 3, ..., 9}.

7) число 325 содержит столько же цифр, что и число 891.

9.  Укажите транзитивные отношения:

l) квадратный корень;                                 5) равно половине;

2) старше, чем;                                        6) является предком;

3) больше в три раза;                                 7) является матерью;

4) дружит;                                                 8) здоровается.

10. Укажите антитранзитивные отношения в упр.4 и 5.

11. Какими свойствами обладают следующие бинарные отношения, заданные на множестве натуральных чисел:

1) ab ⇔ a < b,

2) ab ⇔ a     b,

3) ab ⇔ a и b делятся на 5,

4) ab ⇔ a делится на b,

5) ab ⇔ a делит b,

6) ab ⇔ a + b = 10,

7) ab ⇔ a и b — нечетные числа,

8) ab ⇔ a = b ∨ a < b ∨ a > b,

9) ab ⇔ ab = ba ,

10) ab ⇔ b = a + 1.

11.  Укажите отношения эквивалентности:

1) быть попутчиком в одном вагоне пассажирского поезда;

2) а+b=100, где а, b{1, 2,..., 100};

3) а=b, где а, b{1, 4, 8, 9};

4) прямая а перпендикулярна прямой b;

5) треугольник а подобен треугольнику b;

6) Сидоров живет двумя этажами выше Михайлова;

7) а сердит на b.

12. Укажите отношения эквивалентности:

1) Иванов задал вопрос Петрову;

2) книга а имеет такую же цену, что и книга b;

3) Смирнов попрощался с Федоровым;

4) Саша позвал в гости Игоря;

5) Павлов и Васильев смотрят один и тот же фильм;

6) высота горы а равна высоте горы b;

7) Федоров и Иванов поступили в ПК 39 в одном и том же году.

13.  Укажите отношения эквивалентности:

1) солдат Петров идет в ногу с солдатом Ивановым в одном и том же

отряде;

2) Смирнов позвонил на работу Чичикову;

3) Павлов встретил на вокзале своего друга Васильева;

4) автомобиль «Москвич» едет по той же дороге, что и автомобиль

«Жигули»;

5) автомобиль а столкнулся с автомобилем b;

6) Иванов прочитал книгу, написанную Соколовым;

7) Юра прилетел в Москву одновременно с Борисом.

14. Укажите отношения строгого порядка:

1) Иванов выше Сидорова;

2) Лена – сестра Наташи;

3) отрезок a короче отрезка b;

4) отрезок a длиннее отрезка b на 2 см;

5) Васильев знает Петрова;

6) Иванов живет этажом выше Соколова;

7) спортсмен Семенов бежит непосредственно за Николаевым.

15. Укажите отношения строгого порядка:

1) число а непосредственно следует за числом b, где a, b {1, 2,…, 10};

2) число а на 4 больше числа b, где a, b{1, 2,..., 10};

3) между числами a и b находится точно одно число, где а, b{1, 2,..., 10});

4) число a равно числу b, где a, b{1, 2,..., 10};

5) число a следует за числом b, где a, b{1, 2,..., 10};

6) число a больше в два раза числа b, где a, b{1, 2,..., 20};

7) Саша старше Димы.

16.  Укажите отношения нестрогого порядка:

1) автомобиль a едет быстрее автомобиля b;

2) число a не меньше числа b, где a, bÎ{1, 2,..., 50};

3) числа a и b не равны числу 6, где a и b – натуральные числа;

4) число a без остатка делится на число b, где a, bÎ{1, 2, 3, 4, 5, 6};

5) a>5 и b>5, где a, bÎ{1, 2,..., 8};

6) Петров и Иванов – друзья;

7) угол a не больше угла b.

17.  Укажите отношения нестрогого порядка:

1) числа a и b не являются двузначными;

2) точка а на числовой оси находится левее точки b;

3) самолет a летит не быстрее самолета b;

4) расстояние между городами равно 100 км;

5) дом а не выше дома b;

6) отрезок а не короче отрезка b;

7) хорошее лучше плохого.

Литература

1. Шрейдер Ю. А. Равенство, сходство, порядок. - М.: Наука, 1971.

2. Розен В. В. Цель - оптимальность - решение (математические модели принятия оптимальных решений). - М.: Радио и связь, 1982.

3. Столяр А. А., Рогановский Н. М. Основы современной школьной математики. Ч. 1. Язык. Множества. Отношения. Функции. Математические структуры. - Минск: Нар. Асвета, 1975.

http://portal.tpu.ru/lyceum/innovacion/workroom/sets.pdf

http://dj-s-j-m.narod.ru/ucheba/dismat.pdf

http://uti.tpu.ru/edu/chairs/eno/dmbomy.pdf