Доказательства тождественности формул

Лекция № 2. законы и тождества алгебры множеств

Продолжительность: 2 часа (90 мин.)

3.1 Ключевые вопросы

· Основные законы и тождества алгебры множеств

· Семейства множеств

· Доказательства

· Вопросы для контроля

Текст лекции

Основные законы и тождества алгебры множеств

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

Ассоциативный закон

1) (X Y) Z = X (Y Z) = X Y Z;

2) (X Y) Z = X (Y Z) = X Y Z.

Коммутативный закон

3) X Y = Y X; 4) X Y = Y X.

Закон идемпотентности (повторения)

5) X X = X; 6) X X = X.

Дистрибутивный закон

7) (X Y) Z = (X Z) ( Y Z);

8) (X Y) Z = (X Z) (Y Z) (нет в обычной алгебре).

Законы универсального U и пустого множеств

(законы нуля и единицы 0, U 1)

9) X = X; 10) X = ;

11) X U = U; 12) X U = X;

13) = U; 14) = .

Законы исключенного третьего и противоречия

15) X = U; 16) X = .

Законы де Моргана

17) 18) .

Закон двойного отрицания

19) = X.

Если имеет место включение (множество А является подмножеством множества В,см. рис. 1.1), то

и ,

и .

Законы 5) и 6) можно записать и так

X X X X … = X, X X X X … = X,

что позволяет при выполнении операций объединения и пересечения обходиться без коэффициентов и показателей степеней.

При работе с множествами могут оказаться полезными тождества, приведенные ниже. Однако они требуют доказательства. Доказать их можно, используя основные законы (свойства операций пересечения, объединения и дополнения) и приемы, рассмотренные в п. 3.2.3

Дистрибутивный закон пересечения относительно разности

.

Дистрибутивный закон пересечения относительно симметрической разности

.

Дистрибутивный закон разности относительно пересечения

Дистрибутивный закон разности относительно объединения

.

Дистрибутивные законы объединения и пересечения относительно разности

X\(Y Z) = (X\Y) (X\Z);

X\(Y Z) = (X\Y) (X\Z).

Представление пересечения и объединения через разность

X Z = X\(X\Z);

X Y= (X\Y) (Y\X) (X Y) = (X\Y) (Y\X) X\(X\Y).

Законы нуля и единицы для разности

(X \Y) (X Y) = ; X \ = X \U = ;

\X = ; U\X = ; X \X = U.

Законы поглощения

Закон склеивания

.

Свойства симметрической разности

,

,

,

,

,

.

Доказательства тождественности формул

Наиболее часто в теории множеств возникает необходимость доказательства равенства соотношений типа Х = Y.

Доказательство можно проводить путем рассуждений с применением законов и тождеств алгебры множеств, построением диаграмм Эйлера–Венна или на примерах конкретных множеств, составленных, например, из алфавитно–цифровых символов (последние два способа приведены в примере 2 п. 2.2.5 Лекции №1).

Ниже, в примерах, доказательства соотношений типа X = Y, где Х и Y – множества, основаны на использовании определений I и II равенства двух множеств.

В соответствии с определением I для равенства двух множеств требуется совпадение их элементов. Поэтому сначала доказывается, что для произвольного элемента а из того, что , следует, что , затем доказывается, что если ,то . Таким образом, элементы множеств X и Y совпадают и, следовательно, по определению I Х = Y.

В соответствии с определением II Х = Y,если и . Поэтому для доказательства равенства двух множеств требуется показать справедливость включений и .

Пример 1.Доказать справедливость соотношения

.

Предположим, что произвольный элемент , т.е. что . Это значит, что и , значит и .

Следовательно, .

Пусть теперь некоторый элемент , т.е. и . Это значит, что и , т.е. .

Следовательно, .

Таким образом, доказано, что .

Пример 2.Докажем по другому справедливость соотношения

.

Пусть имеем

U ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {0, 1, 3, 7}, B = {2, 3, 4, 6, 7}.

Определим левую часть:

= {0, 1, 3, 7} {2, 3, 4, 6, 7} = {0, 1, 2, 3, 4, 6, 7},

= U\( ) =

= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\{0, 1, 2, 3, 4, 6, 7} = {5, 8, 9}.

Определим правую часть:

= U\A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\{0, 1, 3, 7} = {2, 4, 5, 6, 8, 9},

= U\B ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\{2, 3, 4, 6, 7} = {0, 1, 5, 8, 9},

= {2, 4, 5, 6, 8, 9} {0, 1, 5, 8, 9} = {5, 8, 9}.

Как видим, левая часть равна правой, следовательно, соотношение справедливо.

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

Пример 3.Доказать справедливость соотношения

(A\B)\C = A\(B C).

Используем соотношение .

Левая часть

(A\B)\C = \С = .

Правая часть

A\(B C) =

Как видим, левая часть равна правой, следовательно, соотношение справедливо.

Пример 4. Доказать справедливость соотношения

.

Это свойство дистрибутивности слева объединения относительно пересечения .

Такое доказательство может быть выполнено с помощью диаграмм Эйлера–Венна (см. пример 2, п. 1.3). Здесь для этих целей используем один из приемов доказательства равенства двух множеств.

В соответствии с первым определением равенства множеств множества равны, если их элементы совпадают. Это означает, что Х = Y, если из того, что , следует ,и из того, что , следует .

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

Пусть .

Из определения операции объединения следует, что элемент а принадлежит объединению множеств А и , если он принадлежит хотя бы одному из них (или, что очевидно, тому и другому). Таким образом, или , при этом возможны следующие случаи:

1.1. а принадлежит множеству А и а не принадлежит пересечению множеств :

и .

Последнее условие выполняется, если а не принадлежит В,или С, или им обоим (это является лишним);

1.2. и , т.е. ;

1.3. и , т.е. .

Рассмотрим каждый из этих случаев.

1.1. Так как ,то а принадлежит объединению множества А с любым множеством, в том числе и . Следовательно, а принадлежит и их пересечению:

.

1.2. Так как , ,то и ,следовательно, .

1.3. Так как ,то этого достаточно, чтобы и , следовательно, .

Таким образом, в любом из рассмотренных случаев из того, что , следует, что .

2. Покажем теперь справедливость второго условия определения I равенства множеств: если произвольный элемент а не принадлежит левой части соотношения , то он не принадлежит и правой части данного соотношения .

Пусть теперь: .

Элемент а не принадлежит объединению двух множеств, если он не принадлежит ни одному их них. Тогда А и ,т.е. возможны следующие случаи:

2.1. ;

2.2. ;

2.3. .

Рассмотрим каждый из этих случаев:

2.1. Так как , то , следовательно,

.

2.2. Так как ,то ,следовательно,

.

2.3. Так как , то этого достаточно, чтобы , следовательно, .

Как видим, в любом из этих случаев из того, что , следует, что .

Таким образом, множества и совпадают и по определению равенства множеств

,

что и требовалось доказать.

Пример 5.Доказать справедливость соотношения

.

Это свойство дистрибутивности справа пересечения относительно объединения .

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

Множества Х = Y, если и .

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

Пусть . Тогда

и

( или ) и ( )

( и ) или ( и )

или

.

Таким образом, .

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

Пусть . Тогда

или

( и ) или ( и )

( или ) и

( и

Следовательно, .

Таким образом, ,

что и требовалось доказать.

Семейства множеств

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

Если C = U, то имеем полное семейство.

Если C = U и , то совокупность множеств X_a образует систему классов эквивалентности (см. п. 3.6).

Над множествами, принадлежащими семействам, можно выполнять операции объединения и пересечения по обычным правилам.

Символическая запись, например объединения совокупности множеств, имеет вид

а пересечение некоторого числа множеств обозначают так

В первом варианте объединяются или пересекаются множества, принадлежащие универсальному множеству U.

Во втором варианте объединяются или пересекаютcя множества A₁, A₂, A₃,…, A_n.

В третьем варианте объединяется или пересекаетcя бесконечное число множеств A₁, A₂, A₃,…

В четвертом варианте объединяются или пересекаютcя множества, индекс которых принадлежит счетному множеству I (I = {1, 2, 3, …, n}).

Для операций пересечения и объединения справедливо

Здесь Y – некоторое подмножество множества U.

Пусть множества семейства формируются последовательным добавлением элементов. Если с некоторого k Х_k+1 = Х_k, то

.

Операция разности – бинарная, поэтому для семейств множеств она выполняется по следующим правилам

Прямое произведение семейства множеств X₁, X₂, …, X_n - это множество элементов вида ( ), где

Обозначается оно так

или так

{( )| }.

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

Произведение множеств – операция некоммутативная – переставлять множества в произведении нельзя.

Если X₁ = X₂ = X₃ =…= X_n = X, то Xⁿ называется n–й степеньюмножества Х, причем X ⁿ = .

Мощность множества равна произведению мощностей множеств сомножителей

| | = .

Для степени множества X получаем |X ⁿ| = |X|ⁿ.

Для произведения множеств справедливы следующие свойства

,

.

Пусть дано семейство множеств А₁, А₂,…, А_n и пусть требуется определить мощность их объединения А₁ А₂ … А_n.

В первом приближении можно принять за эту мощность сумму мощностей множеств семейства

.

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

А_i А_{j ,}

то принадлежащие этому пересечению элементы будут учтены дважды.

Исключение “лишних” элементов производится на основе принципа включений и исключений по формуле

По этой формуле для двух множеств получаем

Для трех множеств будем иметь

Вопросы для контроля

1. Какие “булевские” операции над множествами Вы знаете? Приведите примеры.

2. Какие операции, кроме “булевских”, применяют в теории множеств?

3. Поясните операцию перемножения множеств. Чему равна мощность произведения множеств?

4. Приведите основные законы “булевой” алгебры множеств.

5. Что такое булеан, как он строится и обозначается? Чему равна его мощность? Чему равно объединение и пересечение множеств, входящих в булеан?

6. Как выполняются операции объединения и пересечения над множествами А и В, если В является подмножеством А?

7. Что такое – семейство множеств? Как обозначаются операции объединения и пересечения множеств семейства? Каковы свойства этих операций?

8. На основе какого принципа (и как) производится определение мощности объединения множеств? Пересечения множеств?

9. Дайте определение равенству двух множеств.

10. Какие способы применяют для доказательства равенства двух выражений алгебры множеств? Приведите примеры.

Не нашли, что искали? Воспользуйтесь поиском по сайту: