Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 17 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

17
где S
М
– множество операций: пересечение, объединение, дополнение, раз-
ность.
Законы алгебры множеств
Для операций объединения, пересечения и дополнения выполняются
следующие законы:
1) коммутативности:
А ∪ В = В ∪ А; А ∩ В = В ∩ А;
2) ассоциативности:
А ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C,
A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C;
3) дистрибутивности:
а)
пересечения относительно объединения:
A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C );
б) объединение относительно пересечения:
A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C);
4) идемпотентности:
A ∪ A = A, A ∩ A = A;
5)действия с универсальным и пустым множествами:
A ∪ ∅ = A, A ∩ ∅ = ∅,
A ∪ E = E, A ∩ E = A;
A ∪ A = E, A ∩ ⎯A = ∅;
6) де Моргана:
ВАВА ∪=∩ ,
ВАВА ∩=∪ ;
7) двойного дополнения:
А
А = .
Доказательство законов можно выполнить графически или посредст-
вом последовательности утверждений типа “если Р, то Q”, которое записы-
вается как “P =>Q”.
Докажем закон дистрибутивности:
A
∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Графическое доказательство состоит в построении диаграмм Эйлера–
Венна для правой и левой частей (рис. 14). 
где SМ – множество операций: пересечение, объединение, дополнение, раз-
ность.
                      Законы алгебры множеств
     Для операций объединения, пересечения и дополнения выполняются
следующие законы:
     1) коммутативности:
           А ∪ В = В ∪ А; А ∩ В = В ∩ А;
     2) ассоциативности:
           А ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C,
           A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C;
     3) дистрибутивности:
           а) пересечения относительно объединения:
           A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C );
           б) объединение относительно пересечения:
           A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C);
     4) идемпотентности:
           A ∪ A = A, A ∩ A = A;
     5)действия с универсальным и пустым множествами:
           A ∪ ∅ = A, A ∩ ∅ = ∅,
           A ∪ E = E, A ∩ E = A;
           A ∪ A = E,        A ∩ ⎯A = ∅;
     6) де Моргана:
           А∩В = А∪В,
           А∪В = А∩В ;
     7) двойного дополнения:
            А = А.
      Доказательство законов можно выполнить графически или посредст-
вом последовательности утверждений типа “если Р, то Q”, которое записы-
вается как “P =>Q”.
      Докажем закон дистрибутивности:
                 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
      Графическое доказательство состоит в построении диаграмм Эйлера–
Венна для правой и левой частей (рис. 14).



                                 17

Страницы