Практикум по дискретной математике (стр. 2 )

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

Решение. M = =`MА È`MВ.

В этом можно убедиться с помощью диаграмм Эйлера-Венна (рис. 2).

MA Ç MB
`МA	`МB	`MА È`MВ

Рис. 2

Для любых подмножеств А, В и С универсального множества U выполняются следующие тождества (основные тождества алгебры множеств):

1. А È В = В È А (коммутативность È).	1¢. А Ç В = В Ç А (коммутативность Ç).
2. А È (В È С) = (А È В) È С (ассоциативность È).	2¢. А Ç (В Ç С) = (А Ç В) Ç С (ассоциативность Ç).
3. А È (В Ç С) = (А È В) Ç (А È С) (дистрибутивность È относительно Ç).	3¢. А Ç (В È С) = (А Ç В) È (А Ç С) (дистрибутивность Ç относительно È).
4. А È Æ = А (свойство нуля).	4¢. А Ç Æ = Æ.
5. А È`А = U (свойство дополнения).	5¢. А Ç`А = Æ.
6. А È А = А.	6¢. А Ç А = А.
7. А È U = U (свойство единицы).	7¢. А Ç U = А.
8. =`А Ç`В (закон де Моргана).	8¢. =`А È`В (закон де Моргана).
9. А È (А Ç В) = А (закон поглощения).	9¢. А Ç (А È В) = А (закон поглощения).
10. = А (инволюция).
11. А \ В = А Ç

Примеры. 1. Рассмотрим предположение о том, что произвольные множества A и B попарно эквивалентны: 1) A Ì B; 2) A Ç B = A; 3) A È B = B.

Решение. Докажем, что из первого предположения следует второе. Действительно, так как A Ç B Ì A, то достаточно показать, что в этом случае A Ì A Ç B. Но если х Î A, то х Î B, т. к. A Ì B и, следовательно, х Î A Ç B.

Докажем, что из второго предположения следует третье. Так как A Ç B = A, то A È B = (A Ç B) È B. По закону поглощения (см. тождество 9) B È (A Ç B) = B. Отсюда, используя закон коммутативности, получаем A È B = B.

Докажем, что из третьего предположения следует первое. Так как A Ì A È B, а по условию третьего предположения A È B = B, то А Ì В.

Задания

Для аудиторных занятий

1.Записать множество М целых чисел х, которые делятся на три и находятся в интервале 3 £ х £ 15. Записать двумя способами.

2.Записать множество А целых чисел х, которые делятся на 2 и на 3 и находятся в интервале 20 £ х £ 25. Записать двумя способами.

3.Принадлежит ли х множеству М, если:

а) М = {2, 6, 8, …, 50}; х = 35;

б) М = {2, 3, 4, 6, 8, 9, 10, …, 100}; х = 23;

в) М = {-2, 2, -4, 4, …, 120}; х = -30.

Записать приведенные множества с указанием свойств их элементов.

4.Доказать неравенство: {{1, 2}, { 2, 3}} ¹ {1, 2, 3}.

5.Какие из следующих выражений являются истинными и какие ложными:

а) Æ Î {{Æ}}; б) 1 Î {{1, 2}}; в) {1, 2} Î {{1, 2}}; г) {1, 2} Î {{1, 2}, {1, 3}, 1, 2}.

6. Привести примеры таких множеств А, В, С, чтобы были истинными следующие высказывания:

а) А Î В Ù В Î С Ù А Ï С;

б) А Î В Ù В Î С Ù А Î С.

7. Какие из следующих множеств конечны и какие бесконечны:

а) {x Î Rçx2 - 5x + 4 = 0};

б) {x Î Nçx2 - 5x + 4 > 0};

в) {x Î Nçx2 / 24}.

8. Равны ли множества:

а) {x Î Rçx2 - 2x – 2 = 0} и {x Î Qçx2 - 2x – 2 = 0};

б) {x Î Zç4/x Ù 15/x} и {x Î Zç4/x Ù 15/x}{x Î Zç20/x Ù 30/x}.

9. Перечислить элементы следующих множеств:

а) {x Î Rçx2 - 3x + 2 = 0};

б) {x Î Rçx2 + 1 = 0};

в) множество всех корней уравнения x2 + 6x + 9 = 0.

10. Перечислить все элементы каждого из следующих множеств:

а) {xçx Í{ 1}}; в) {xçx Í {1, 2, 3}};

б) {xçx Í {1, 2}}; г) {xçx Í Æ}.

Для самостоятельной работы

1.  Перечислить элементы следующих множеств:

а) множество четных чисел от 0 до 20 включительно;

б) множество всех двузначных чисел, делящихся на 5 и не делящихся на 10;

в) множество всех последовательностей, содержащих все числа 1, 2, 3, 4, 5 и только эти числа, в которых четные и нечетные числа чередуются.

2.  Равны ли множества:

а) {2, 4, 5} и {2, 4, 2, 5}; б) {1, 2} и {{1, 2}}; в) {1, 2, 3} и {3, 1, 2, 1}};

г) {1, 2, 3} и {{1}, {2},{3}}.

3.  Перечислить подмножества следующих множеств:

а) {{1, 2}, {3}, 4}; б) {{5, 2}}; в) {{2}, {6}, {3} }; г) {{4, 6}, {1}, 1}.

4.  Вставить между множествами символ Î или Ì так, чтобы получилось истинное высказывание:

а) {1} {1, {1, 2}}; б) Æ {Æ}; в) Æ {{Æ}}; г) {1, 2} {1, 2, {1, 2}}.

5.  Найти А È В, А Ç В, А \ В, В \ А,`А,`В:

а) А = {1, 2, 3}, В = {2, 3, 5, 4}, U = {1, 2, …, 9};

б) А = {х ׀х делится на 2}, В = {х ׀х делится на 3}, U = N.

6.  Доказать следующие тождества:

а) (А Ç В) È (А Ç`В) = (А È В) Ç (А È`В);	е) А Ç В = А Ç (А È В);
б) (А È В) Ç А = А Ç В;	ж) (А È В) \ (А Ç В) = (А \ В) È (В \ А);
в) (А \ В) \ С = (А \ С) \(В \ С);	з) (А \ В) È (А \`В) = (А È В) \ (А Ç В);
г) А \ (В È С) = (А \ В) \ С;	и) (А \`В) È (В \`А) = (А È В) \ (А Ç В);
д) А \ В = А Ç`В;	к) А \ (В È С) = (А \ В) Ç (А \ С).

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

а) (А È В) Ç С = А È (В Ç С);	в) (А \ В) È С = (А È С) \ (В È С);
б) (А \ В) È В = А;	г) (А Ç`В) È (В Ç`А) Ì В.

8.  Найти мощность множеств, мощность их булеанов и |А È В| – мощность объединения множеств:

а) А = {4, 5, 6}, В = {4, 5, 6, 7, 8}; б) А = {1, 3, 5, 6}, В = {4, 5, 6, 7};

в) А = {3, 5, 7}, В = {2, 5, 6, 7, 9}; г) А = {1, 2, 3, 5}, В = {2, 4, 5, 6, 7}.

9. Вставить между множествами символ Î или Í так, чтобы получилось истинное высказывание:

а) {1} {1, {1, 2}}; г) Æ {1, 2, {1}, {Æ}};

б) {1, 2} {1, 2, {1},{2}}; д) Æ {{Æ}};

в) {1, 2} {1, 2,{1, 2}}; е) Æ {Æ}.

10. Привести пример множеств A, B, C, таких, чтобы выполнялись условия:

а) A Î B, B ÏC, A Í C;

б) A Î B, A Ï C, C Í B;

в) A Í B, B Î C, A Ï C.

Литература

1. Куликов, задач по алгебре и теории чисел / , , А. А Фомин. – М.: Просвещение, 1993. – 288 с.

2. Ерусалимский, математика. Теория, задачи, приложения: учеб. пособие для вузов / . – М.: Вузовская книга, 2008. – 288 с.

3. Новиков, математика для программистов: учебник для вузов / . – СПб.: Питер, 2001. – 304 с.

2. Практическое занятие № 2

Тема: «Бинарные отношения»

Цель занятия:

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

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какие способы задания бинарного отношения вы знаете?

Что является областью определения бинарного отношения r?

Что является областью значений бинарного отношения r?

Какое отношение r называется рефлексивным на множестве X?

Какое отношение r называется симметричным на множестве X?

Главная диагональ матрицы какого отношения содержит только единицы?

Для какого отношения r всегда выполняется условие r = r – 1?

Для какого отношения r всегда выполняется условие r r Í r.

2. Дать определение следующих понятий:

– бинарное отношение;

– композиция отношений.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

2.1. Бинарные отношения. Прямое произведение множеств

Бинарным отношением r называется множество упорядоченных пар. Если r есть некоторое отношение и пара (х, у) принадлежит этому отношению, то употребляется запись (х, у)Î r или хrу. Элементы х и у называются координатами или компонентами (объектами) отношения r. Если х и у компоненты (объекты), то через (х, у) обозначают упорядоченную пару. Равенство упорядоченных пар определяется следующим образом: (а, b) = (с, d) := а = с и b = d (:= – операция присваивания).

Областью определения бинарного отношения r называется множество Dr = {x׀существует такое у, что хrу}. Областью значений бинарного отношения r называется множество Rr = {y׀существует такое x, что хrу}.

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

Кроме того, бинарное отношение может быть задано матрицей бинарного отношения. Пусть А = {a1, a2, …, an} – конечное множество. Матрица бинарного отношения C есть квадратная матрица порядка n, элементы которой cij определяются следующим образом:

cij =

Пример. А = {1, 2, 3, 4}. Зададим бинарное отношение r тремя перечисленными способами.

1. r = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} – отношение задано перечислением всех упорядоченных пар.

2. r = {( ai, aj) çai < aj; ai, aj Î А} – отношение задано указанием свойства "меньше" на множестве А.

3. – отношение задано матрицей отношения C.

Пусть даны два множества Х и У. Прямым (декартовым) произведением двух множеств Х и У называется совокупность всех упорядоченных пар (х, у), таких, что х Î Х и у Î У. Обозначается прямое произведение множеств Х и У через Х × У: Х × У := {(х, у)| х Î Х и у ÎУ}.

Каждое отношение r есть подмножество прямого произведения некоторых множеств Х и У, таких, что Dr Í Х и Rr Í У, то есть r Ì Х ´ У. Если Х = У, то говорят, что r есть отношение на множестве Х, и тогда r Ì Х2.

Примеры. 1. Пусть Х = {1, 2, 3}, У = {0, 1}. Тогда

Х ´ У = {(1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)};

У ´ Х = {(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3)}.

Пусть r есть отношение на множестве Х. Введем понятия: обратное отношение: r-1 = {(х, у)| (у, х) Î r}; дополнение отношения: `r = {(х, у)| (х, у)Ïr}; тождественное отношение: I = {(х, x)| х Î x }. Композицией отношений r1 и r2 называется отношение r1Оr2 = {(х, z)| существует у такое, что (х, у) Î r1 и (у, z)Î r2}. Для любых бинарных отношений выполняются следующие свойства: 1) (r-1)-1 = r; 2) r2Оr1 = r1 -1Оr2 -1.

Пример. r = {<x, y> çy = }. s = {<x, y> çy = }.

s r = {<x, z> çсуществует такое y, что <x, y> Î r и < y, z> Îs} = {<x, z> çсуществует такое y, что y = и z = } = {<x, z> ç z = }.

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

Отношение r называется рефлексивным на множестве X, если для любого x Î X выполняется xrx. Из определения следует, что всякий элемент (x, x) Î r.

Пример. 1. Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <2, 2>, <3, 1>, <3, 3>}. Отношение r рефлексивно. Если X – конечное множество, то главная диагональ матрицы рефлексивного отношения содержит только единицы. Для данного примера

2. Пусть X – множество действительных чисел и r – отношение равенства. Это отношение рефлексивно, т. к. каждое число равно самому себе.

Отношение r называется симметричным на множестве X, если для любых x, y Î X из xry следует yr x. Очевидно, что r симметрично тогда и только тогда, когда r = r–1.

Пример. 1. Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <3, 1>, <3, 3>}. Отношение r симметрично. Если X – конечное множество, то матрица симметричного отношения симметрична относительно главной диагонали. Тогда .

2. Пусть X – множество действительных чисел и r – отношение равенства. Это отношение симметрично, т. к. если x равно y, то и y равно x.

Отношение r называется транзитивным на множестве X, если для любых x, y, z Î X из xry и yrz следует xrz. Одновременное выполнение условий xry, yrz, xrz означает, что пара <x, z> принадлежит композиции r r. Поэтому для транзитивности r необходимо и достаточно, чтобы множество r r являлось подмножеством r, т. е. r r Í r.

Пример. Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <2, 3>, <1, 3>}. Отношение r транзитивно, т. к. наряду с парами <x, y> и <y, z> имеется пара <x, z>. Например, наряду с парами <1, 2> и <2, 3> имеется пара <1, 3>.

Задания

Для аудиторных занятий

1. Перечислить элементы множеств А ´ В, В ´ А:

а) А = {1, 2}, В = {3, 4, 5};

б) А = {1}, В = {1, 2, 3}.

2. Пусть А, В ÍС. Доказать, что А ´ В = (А ´ С) Ç (С ´ В).

3. Пусть А, В, С, D – непустые множества. Доказать следующие тождества:

а) (А Ç В) ´ (С Ç D) = (А ´ С) Ç (В ´ D);

б) (В È С) ´ А = (В ´ А) È (С ´ А).

4. Доказать, что для любых непустых множеств А, В, С из равенства (А ´ В) È (В ´ А) = С ´ С следует, что А = В = С.

5. Перечислить все элементы бинарного отношения r:

а) хrу Û х < у;	на множестве А = {1, 2, 3, 4};
б) хrу Û х / у;	на множестве А = {2, 5, 10}.

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

а) хrу Û х £ у;	д) хrу Û х2 = у;
б) хrу Û х = у;	е) хrу Û х2 = у2;
в) хrу Û х < у;	ж) хrу Û х + у = 1;
г) хrу Û у2 = х;	з) хrу Û у =

7. Для бинарного отношения r между элементами множеств А и В найти область определения Dr и область значений Rr: А = {1, 2, 3, 4, 5}, В = {{1}, {1, 2}, 3, 4, 5}.

8. Найти r-1, rОr, r-1Оr, rОr-1 отношений:

а) r = {(x, y)| х, у ÎR и х + у ≤ 0};	г) хrу Û х2 + x = у2 + y, х, у Î R;
б) хrу Û х2 = у, х, у Î R;	д) хrу Û х2 = у2, х, у Î R;
в) хrу Û х у > 1, х, у ÎR;	е) хrу Û х + у = 1, х, у Î R.

9. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}. Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

10. Привести пример отношения нетранзитивного, нерефлексивного и несимметричного.

Для самостоятельной работы

1. Перечислить элементы множеств А ´ В, В ´ А:

а) А = {1}, В = {1, 2, 3};

б) А = Æ, В ={ 1, 2, 3, 4}.

2. Пусть А = {и, л}. Перечислить элементы множеств А2, А3.

3. Определить упорядоченную пару áa, bñ как множество {{a}, {a, b}}. Доказать, что áa, bñ = ác, dñ тогда и только тогда, когда a = c и b = d.

4. Пусть на плоскости задана декартова система координат. Изобразить на плоскости следующие множества:

а) [a, b] ´ [c, d], где a, b, c, d Î R и a < b, c < d;

б) [a, b]2.

5. Доказать, что подмножество С множества А ´ В является прямым произведением некоторого подмножества А1 множества А и подмножества В1 множества В тогда и только тогда, когда для любых пар áa, bñ , ác, dñ из С пары áa, bñ , ác, dñ также принадлежат С.

6. Перечислить все элементы бинарного отношения r и нарисовать его график:

а) хrу Û у = х + 1;

на множестве А = {1, 2, …, 10}.

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

а) хrу Û х ≥ у;	в) хrу Û х3 = у;
б) хrу Û х = у;	г) хrу Û х2 = у2.

8. Какими свойствами обладают следующие бинарные отношения (рефлексивность, симметричность, транзитивность), заданные на R?

а) хrу Û х > у;	в) хrу Û х + у = 1;
б) хrу Û у3 = х;	г) хrу Û у = sin x.

9.  Привести пример отношения транзитивного, рефлексивного и симметричного.

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

Отношения определены на множестве R:
а) хrу Û х2 = у2;	в) хrу Û у = |х|;
б) хrу Û х2 + у2 = 1;	г) хrу Û х2 + x = у2 + y.
Отношения определены на множестве Z:
а) хrу Û х £ у + 1;	б) хrу Û 3/(х – у).
Отношения определены на множестве всех прямых плоскости:
а) хrу Û х параллельна у;	б) хrу Û х пересекается с у.

Литература

1.  Куликов, задач по алгебре и теории чисел / , , А. А Фомин. – М.: Просвещение, 1993. – 288 с.