Терминология и обозначения.

 

 

Диаграмма Венна – Эйлера.

Используется для графической иллюстрации.

Определение: Множество  называется универсальным для данной задачи, если все рассматриваемые в этой задаче множества являются его подмножествами.

Диаграммы Эйлера 1-го типа:

                       

                                     

 

Диаграммы Венна 2-го типа:

для 1-го множества:

 

для 2-х множеств:                                

 

для 3-х множеств:

 

Пример                      

	______

 

                         

Законы алгебры множеств.

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

 

1. Закон коммутативности

1)

2)

2. Закон ассоциативности

1)

2)

3. Закон дистрибутивности

1)

2)

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

 

1 способ (с помощью диаграмм)

 

	____ ____	____ ____
	____ ____

 

2 способ (поэлементное)

1)

2)  или

                                                     

4. Взаимодействие с самим множеством и его дополнением

                   1)

2)

3)

4)

5. Свойства нуля и единицы

1)

2)

3)

4)

Равенства алгебры множеств, полученное из другого заменой

называются двойственными               

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

1)

2)

 7. Дополнение к  и

1)  

2)

  8. Закон двойного дополнения

                  

 9. Признаки  и

                   1) Если для то

                   2) Если для то

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

1)

2)

11. Признак дополнения

            Если  то  (или )

             

 

12. Свойства операций разности

                   \

                   1) \

                   2) \

                   3) \

                   4) \

Все рассмотренные законы двойственны.

Операцию пересечения считаем более сильной, чем другие. Это означает, что при отсутствии скобок она выполняется первой. Например, формула  эквивалентна .

 

Кардинальные операции.

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

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

Элементы пары  и  называется координатами.

Опред.: Множество  называется прямым произведением n множеств.

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

Опред.: декартов квадрат

          декартова  степень.

Свойства прямого произведения

1.

2.  или

 или .

 

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

Опред.: Бинарным отношением (двуместным) из множества  в множество называется  произвольное подмножество прямого произведения .

, если , то  называется отношением на .

Если , то говорят, что элементы  и  находятся в отношении .

Примеры: : «быть равным» на

           : «быть параллельным» на множестве прямых

Представление бинарных отношений.

1) В виде ориентированного графа , где – множество вершин,

– множество дуг.

Пример:

 

2) В виде матриц