Теоретические обоснования

Вернемся к свойствам (1) – (19) операций над множествами. Все они представляют собой утверждения о равенстве двух множеств. Стандартный способ доказательства равенства двух множеств состоит в доказательстве двух включений:и.

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

В качестве примера докажем один из дистрибутивных законов:

.

1) Пусть - произвольный элемент из. Тогда по определению операцииимееми. Во втором случае из определения операциивыводим, чтоили. Если, то с учетом того, что, получаем. Если, то с учетом того, что, получаем. Таким образом, или . Следовательно, по определению операции имеем. Тем самым установлено, что.

2) Пусть - произвольный элемент из. Тогда по определению операцииимеемили. В первом случае из определения операциивыводим, чтои. Во втором случае -и. Таким образом,или, значит,. Кроме того, в обоих случаях. Следовательно, согласно определению операции, имеем. Тем самым установлено, что.

Действуя по такой же схеме, можно доказать и другие свойства операций над множествами (советуем проделать это самостоятельно).

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

Теорема 1.1 (о свойствах классов эквивалентности). Пусть - отношение эквивалентности на множестве. Тогда

1. ;

2. ;

3..

Доказательство.1. - отношение эквивалентности, следовательно,является рефлексивным, т.е.выполняется .Но тогдаи, значит,.

2. Пусть , т.е.. Тогдаи, откудаи, и, следовательно, в силу симметричностии, и, наконец, посколькутранзитивно, получим.

Возьмем любой элемент множества, тогда. Так каки, то в силу транзитивности, т.е.. Таким образом,.

Аналогично получим . Следовательно,.

3. Докажите это утверждение самостоятельно. ■

Задачи повышенной сложности

1.1. При голосовании в городскую думу в бюллетене в списке из трех кандидатов требовалось оставить не более одного. При подведении итогов оказалось, что кандидатовивычеркнули 60% избирателей, кандидатови- 80% избирателей, а кандидатови- 70% избирателей. Какой процент избирателей проголосовал против всех кандидатов и какой кандидат набрал наибольшее число голосов?

1.2.Сколько бинарных отношений можно определить на множестве изэлементов?

1.3.На множествезадано бинарное отношение. Какими свойствами обладает это бинарное отношение? Является ли оно отношением эквивалентности? порядка? В том случае, если- отношение эквивалентности, указать разбиение множествана классы эквивалентности .

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

1.5.Привести пример рефлексивного, транзитивного, но не симметричного бинарного отношения на множестве из четырех элементов.

1.6.Привести пример рефлексивного, симметричного, но не транзитивного бинарного отношения на множестве из четырех элементов.

1.7.Привести пример транзитивного, симметричного, но не рефлексивного бинарного отношения на множестве из четырех элементов.

1.8.Пусть- конечное множество. Сопоставим каждому бинарному отношениюнаматрицу размера, называемуюматрицей отношения, в которой на пересечении-й строки и-го столбца стоит 1, если, и 0 - в противном случае. Определить, что представляет собой матрица отношенийв случае, если:

а) рефлексивно;

б) симметрично;

в) антисимметрично.

1.9.Пусть- конечное множество. Определим на булеанебинарное отношение:(здесь,). Является ли отношениеотношением эквивалентности? отношением частичного (линейного) порядка?

1.10.Доказать, что если бинарное отношение одновременно симметрично и антисимметрично, то оно транзитивно.