Автор Тема: Лекция 8. Операции над множествами  (Прочитано 1125 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« : Ноябрь 16, 2017, 08:10:42 pm »
Лекция 8. Операции над множествами


В предыдущей лекции мы рассмотрели отношения между множествами - включение и равенство. Теперь рассмотрим основные операции над множествами - дополнение, пересечение и объединение. Они определяются через операции логики высказываний. Дадим определения этих операций и докажем их важнейшие свойства.

***

Пусть \(  \large M  \) и \(  \large N  \) - произвольные множества.

Замечание 8.1. Поскольку любое множество является подмножеством универсального множества, по умолчанию будем считать, что \(  \large M \subseteq \mathbb{U}  \), \(  \large N \subseteq \mathbb{U}  \).

Определение 8.1. Дополнением множества \(  \large M  \) называется множество, которое содержит те и только те элементы, которые не содержит множество \(  \large M  \).

Замечание 8.2. Дополнение множества \(  \large M  \) обозначается через \(  \large \overline{M}  \).

Замечание 8.3. Итак, согласно определению,

\(  \large \overline{M} = \{ x \colon x \not \in M \}  \).

Определение 8.2. Пересечением множеств \(  \large M   \) и \(  \large N  \) называется множество, содержащее те и только те элементы, которые содержат множества \(  \large M  \) и \(  \large N  \).

Замечание 8.4. Пересечение множеств \(  \large M   \) и \(  \large N  \) обозначается через \(  \large M \cap N  \). Если речь идёт о пересечении нескольких множеств \(  \large M_1,M_2, \ldots, M_n  \), то используется обозначение \(  \large \bigcap\limits_{k=1}^n M_k  \), заменяющее запись \(  \large M_1 \cap M_2 \cap \ldots \cap M_n  \).

Замечание 8.5. Итак, согласно определению,

\(  \large M \cap N =\{x \colon x \in M \wedge x \in N \}  \).

Определение 8.3. Объединением множеств \(  \large M   \) и \(  \large N  \) называется множество, содержащее те и только те элементы, которые содержит хотя бы одно из множеств \(  \large M  \) и \(  \large N  \).

Замечание 8.6. Объединение множеств \(  \large M   \) и \(  \large N  \) обозначается через \(  \large M \cup N  \). Для объединения нескольких множеств \(  \large M_1,M_2, \ldots, M_n  \) используется обозначение \(  \large \bigcup\limits_{k=1}^n M_k  \), которое заменяет запись \(  \large M_1 \cup M_2 \cup \ldots \cup M_n  \).

Замечание 8.7. Итак, в силу определения,

\(  \large M \cup N =\{x \colon x \in M \vee x \in N \}  \).

Замечание 8.8. Диаграммы Эйлера-Венна для дополнения, пересечения и объединения можно посмотреть на рисунке 1. Квадрат символизирует универсальное множество, а красным выделены дополнение, пересечение и объединение соответственно.

Пример 8.1. Даны множества \(  \large M_1=\{ 1,2, 3,4\}  \), \(  \large M_2=\{4,5,6,7,8 \}  \) и \(  \large M_3=\{8,9 \}  \), \(  \large \mathbb{U}=\{1,2, \ldots, 10 \}  \) (универсальное множество). Найдём \(  \large M_1 \cap M_2  \), \(  \large M_2 \cup M_3  \) и \(  \large \overline{M_1}   \). Пересечением множеств \(  \large M_1  \) и \(  \large M_2  \) является множество таких элементов, которые принадлежат обоим множествам. Сравнивая эти множества, понимаем, что сразу двум множествам принадлежит только число \(  \large 4  \). Значит,

\(  \large M_1 \cap M_2= \{ 4 \}  \).

Объединением множеств \(  \large M_2  \) и \(  \large M_3  \) является множество, которое состоит из элементов, принадлежащих первому множеству или второму множеству. Таких элементов шесть: \(  \large 4,5,6,7,8,9  \). Следовательно,

\(  \large M_2 \cup M_3= \{4,5,6,7,8,9 \}  \).

Дополнением множества \(  \large M_1  \) является множество, которое содержит элементы (универсального множества), которые не содержит множество \(  \large M_1  \). Это \(  \large 5,6,7,8,9,10  \). Значит,

\(  \large \overline{M_1}= \{5,6,7,8,9,10 \}  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #1 : Ноябрь 17, 2017, 01:14:35 pm »
В теории множеств имеют место аналоги закона двойного отрицания, закона противоречия и закона исключённого третьего, правил действий с логическими константами (тождества с пустым и универсальным множествами), законы поглощения и законы де Моргана. Пересечение и объединение множеств обладают свойствами идемпотентности, коммутативности, ассоциативности, они дистрибутивны друг относительно друга. Аналогия с законами алгебры высказываний не случайна: данные операции над множествами определяются через операции над высказываниями. Поэтому и свойства операций над множествами являются "двойниками" соответствующих свойств операций алгебры высказываний.

***

Замечание 8.9. Тождеством в теории множеств мы будем называть равенство, которое выполняется для любых множеств. Равенство не является тождеством, если найдутся такие множества, что оно неверно.

Замечание 8.10. Доказательства основных тождеств теории множеств, содержащих дополнение, пересечение и объединение, сводятся к применению определений равенства множеств, дополнения, пересечения и объединения, а также основных законов классической логики высказываний. Ниже докажем несколько тождеств. Остальные просто сформулируем.

Теорема 8.1. Дополнение дополнения множества \(  \large M  \) равно множеству \(  \large M  \) (закон инволюции).

Доказательство. Пусть \(  \large M  \) - произвольное множество. Согласно определению дополнения,

\(  \large \overline{\overline{M}} =\{ x \colon \overline{x \not \in M} \} \).

Учитывая закон двойного отрицания,

\(  \large \overline{x \not \in M}  \)

тогда и только тогда, когда

\(  \large x \in M  \).

Значит, согласно определению равенства множеств,

\(  \large \overline{\overline{M}}=M  \).

Теорема доказана.

Замечание 8.11. Теоретико-множественный закон инволюции является аналогом пропозиционального закона двойного отрицания.

Теорема 8.2. Объединение множества \(  \large M  \) и его дополнения равно универсальному множеству.

Доказательство. Пусть \(  \large M  \) - произвольное множество. Согласно определению объединения и дополнения,

\(  \large M \cup \overline{M} = \{  x \colon x \in M \vee x \not \in M \}  \).

Учитывая закон исключённого третьего, мы можем заменить

\(  \large x  \in M \vee x \not \in M \)

на

\(  \large x \in \mathbb{U}  \).

Это высказывание истинно для любого элемента \(  \large x  \), согласно определению универсального множества. Значит, по определению равенства множеств

\(  \large M \cup \overline{M} = \mathbb{U}  \).

Теорема доказана.

Замечание 8.12. Закон, сформулированный и доказанный выше, является аналогом закона исключённого третьего в алгебре высказываний.

Теорема 8.3. Пересечение множества \(  \large M  \) и его дополнения равно пустому множеству.

Замечание 8.13. Сформулированный выше закон есть аналог пропозиционального закона противоречия.

Теорема 8.4. Дополнение пересечения множеств \(  \large M  \) и \(  \large N  \) равно объединению дополнений этих множеств (первый закон де Моргана).

Доказательство. Пусть \(  \large M  \) - произвольное множество. В силу определений дополнения и пересечения множеств

\(  \large \overline{M \cap N} =\{ x \colon \overline{x \in M \wedge x \in N} \} \).

Используем закон отрицания конъюнкции. Согласно этому закону,

\(  \large \overline{x \in M \wedge x \in N}  \)

тогда и только тогда, когда

\(  \large x \not \in M  \vee x \not \in N  \).

А согласно определениям дополнения и объединения, это равносильно

\(  \large \overline{M} \cup \overline{N}  \).


В силу определения равенства множеств,

\(  \large \overline{M \cap N}  = \overline{M} \cup \overline{N} \).

Теорема доказана.

Теорема 8.5. Дополнение объединения множеств \(  \large M  \) и \(  \large N  \) равно пересечению дополнений этих множеств (второй закон де Моргана).

Теорема 8.6. Пересечение множества \(  \large M  \) с объединением множеств \(  \large M  \) и \(  \large N  \) равно множеству \(  \large M  \) (первый закон поглощения).

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

\(  \large M \cap (M \cup N) = \{x \colon x \in M \wedge (x \in M \vee x \in N) \}  \).

Учитывая первый пропозициональный закон поглощения,

\(  \large x \in M \wedge (x \in M \vee x \in N)   \),

если и только если

\(  \large x \in M  \).

В силу определения равенства множеств, это и означает, что

\(  \large M \cap (M \cup N)=M  \).

Теорема доказана.

Теорема 8.7. Объединение множества \(  \large M  \) с пересечением множеств \(  \large M  \) и \(  \large N  \) равно множеству \(  \large M  \) (второй закон поглощения).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #2 : Ноябрь 17, 2017, 01:33:46 pm »
Теорема 8.8. Пересечение множеств идемпотентно.

Доказательство. Согласно определению пересечения,

\(  \large M \cap M=\{ x \colon x \in M \wedge x \in M \}  \).

Учитывая идемпотентность конъюнкции,

\(  \large x \in M \wedge x \in M  \)

тогда и только тогда, когда

\(  \large x \in M  \).


В силу определения равенства множеств, это и означает, что

\(  \large M \cap M =M  \).

Теорема доказана.

Теорема 8.9. Объединение множеств идемпотентно.

Теорема 8.10. Пересечение множеств коммутативно.

Доказательство. Согласно определению пересечения,

\(  \large M \cap N=\{ x \colon x \in M \wedge x \in N \}  \).

Учитывая коммутативность конъюнкции,

\(  \large x \in M \wedge x \in N  \)

тогда и только тогда, когда

\(  \large x \in N \wedge x \in M  \).

Учитывая определение равенства множеств, делаем вывод, что

\(  \large M \cap N =N \cap M  \).

Теорема доказана.

Теорема 8.11. Объединение множеств коммутативно.

Теорема 8.12. Пересечение множеств ассоциативно.

Доказательство. Согласно определению пересечения,

\(  \large (M \cap N) \cap K=\{ x \colon (x \in M \wedge x \in N ) \wedge x \in K \}  \).

Учитывая ассоциативность конъюнкции,

\(  \large (x \in M \wedge x \in N) \wedge x \in K  \)

тогда и только тогда, когда

\(  \large x \in M \wedge (x \in N \wedge x \in K)  \).

В силу определения равенства множеств, это и означает, что

\(  \large (M \cap N) \cap K =M \cap ( N \cap K)  \).

Теорема доказана.

Теорема 8.13. Объединение множеств ассоциативно.

Теорема 8.14. Пересечение множеств дистрибутивно относительно объединения множеств.

Доказательство. Используя определения пересечения и объединения, заключаем, что

\(  \large M \cap (N \cup K) = \{ x \colon x \in M \wedge (x \in N \vee x \in K)  \).

Используем дистрибутивность конъюнкции относительно дизъюнкции. Это свойство позволяет утверждать, что

\(  \large  x \in M \wedge (x \in N \vee x \in K)  \)

тогда и только тогда, когда

\(  \large (x \in M \wedge x \in N)  \vee (x \in M \wedge x \in K)  \).

Согласно определению равенства множеств, это означает, что

\(  \large M \cap (N \cup K)= (M \cap N) \cup (M \cap K)  \).

Теорема доказана.

Теорема 8.15. Объединение множеств дистрибутивно относительно пересечения множеств.

Теорема 8.16. Пересечение множества \(  \large M  \) и универсального множества равно множеству \(  \large M  \).

Теорема 8.17. Пересечение множества \(  \large M  \) и пустого множества равно пустому множеству.

Теорема 8.18. Объединение множества \(  \large M  \) и универсального множества равно универсальному множеству.

Теорема 8.19. Объединение множества \(  \large M  \) и пустого множества равно множеству \(  \large M  \).

Замечание 8.14. Теоремы аналогичны правилам действий с логическими константами логики высказываний.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #3 : Ноябрь 17, 2017, 02:29:59 pm »
Между отношениями включения и равенства, операциями пересечения и объединения есть интересные взаимосвязи. Оказывается факт включения одного множества в другое равносилен равенству пересечения (объединения) этих множеств первому (второму) множеству. Доказательство одного из этих фактов представлено ниже.

***

Задача 8.1. Пусть \(  \large M  \) и \(  \large N  \) - какие угодно множества. Доказать, что множество \(  \large M  \) является подмножеством множества \(  \large N  \) тогда и только тогда, когда пересечение множеств \(  \large M  \) и \(  \large N  \) равно множеству \(  \large M  \).

Решение. Пусть \(  \large x  \) - произвольный элемент. Согласно определению равенства множеств, \(  \large M \cap N=M  \) тогда и только тогда, когда истинно высказывание

\(  \large x \in M \cap N \leftrightarrow x \in M  \).

Учитывая определение пересечения,

\(  \large x \in M \cap N \leftrightarrow x \in M \simeq (x \in M \wedge x \in N) \leftrightarrow x \in M  \).

Выразим эквиваленцию через импликацию и конъюнкцию:

\(  \large (x \in M \wedge x \in N) \leftrightarrow x \in M \simeq ((x \in M \wedge x \in M) \to x \in M) \wedge (x \in M \to (x \in M \wedge x \in N))  \).

Теперь выразим импликацию через дизъюнкцию и отрицание:

\(  \large ((x \in M \wedge x \in M) \to x \in M) \wedge (x \in M \to (x \in M \wedge x \in N)) \simeq (\overline{(x \in M \wedge x \in N)} \vee x \in M) \wedge (x \not \in M \vee (x \in M \wedge x \in N))  \).

Используем закон отрицания конъюнкции:

\(  \large (\overline{(x \in M \wedge x \in N)} \vee x \in M) \wedge (x \not \in M \vee (x \in M \wedge x \in N)) \simeq (x \not \in M \vee x \not \in N \vee x \in M) \wedge (x \not \in M \vee (x \in M \wedge x \in N))   \).

Применим закон дистрибутивности дизъюнкции относительно конъюнкции:

\(  \large (x \not \in M \vee x \not \in N \vee x \in M) \wedge (x \not \in M \vee (x \in M \wedge x \in N))  \simeq (x \not \in M \vee x \not \in N \vee x \in M) \wedge (x \not \in M \vee x \in M ) \wedge( x \not \in M \vee x \in N))   \).

Сокращаем высказывание, используя закон поглощения:

\(  \large (x \not \in M \vee x \not \in N \vee x \in M) \wedge (x \not \in M \vee x \in M ) \wedge( x \not \in M \vee x \in N))  \simeq (x \not \in M \vee x \in M ) \wedge ( x \not \in M \vee x \in N))  \).

Воспользуемся законом исключённого третьего и правилом действий с константой \(  \large 1  \). Имеем:

\(  \large  (x \not \in M \vee x \in M ) \wedge( x \not \in M \vee x \in N)) \simeq ( x \not \in M \vee x \in N)   \).

Вернёмся к импликации:

\(  \large ( x \not \in M \vee x \in N) \simeq (x \in M \to x \in N)  \).

А это высказывание, согласно определению включения, равносильно \(  \large M \subseteq N  \).

Замечание 8.15. Совершенно аналогично можно доказать, что множество \(  \large M  \) является подмножеством множества \(  \large N  \), если и только если объединение множеств \(  \large M  \) и \(  \large N  \) равно множеству \(  \large M  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #4 : Ноябрь 17, 2017, 02:56:27 pm »
Дополнение, пересечение и объединение мы определили через отрицание, конъюнкцию и дизъюнкцию.  Ещё две операции над множествами - разность и симметрическую разность - мы определим через введённые ранее операции. Кроме того, докажем простейшие свойства двух новых теоретико-множественных операций.

***

Определение 8.4. Разностью множеств \(  \large M  \) и \(  \large N  \) называется пересечение множества \(  \large M  \) и дополнения множества \(  \large N  \).
 
Замечание 8.16. Разность множеств\(  \large M  \) и \(  \large N  \) обозначается через \(  \large M \setminus N  \).

Замечание 8.17. Итак, по определению
 
\(  \large M \setminus N =  M \cap \overline{N}  \).

Определение 8.5. Симметрической разностью множеств \(  \large M  \) и \(  \large N  \) называется объединение разности множеств \(  \large M  \) и \(  \large N  \) и разности множеств \(  \large N  \) и \(  \large M  \).

Замечание 8.18. Симметрическая разность множеств \(  \large M  \) и \(  \large N  \) обозначается через \(  \large M \triangle N  \).

Замечание 8.19. Итак, согласно определению,

\(  \large M \triangle N= (M \setminus N ) \cup (N \setminus M)  \).

Замечание 8.20. Диаграммы Эйлера-Венна для разности и симметической разности можно посмотреть на рисунке 2.

Пример 8.2. Даны множества \(  \large M_1=\{1,3,5 \}  \) и \(  \large M_2=\{4,5,6,7,9\}  \), причём \(  \large \mathbb{U}=\{1,2, \ldots, 10 \}  \). Найдём разность множеств \(  \large M_1  \) и \(  \large M_2  \), симметрическую разность множеств \(  \large  M_2  \) и \(  \large M_1 \). Сначала найдём дополнение множества \(  \large  M_2 \). Имеем: \(  \large \overline{M_2}=\{ 1,2,3,8,10\}  \). Теперь вычислим пересечение множеств \(  \large M_1  \) и \(  \large \overline{M_2}  \): \(  \large M_1 \cap \overline{M_2}=\{1,3 \}  \). Значит,

\(  \large M_1 \setminus M_2= M_1 \cap \overline{M_2}=\{1,3 \}  \).

Поскольку симметрическая разность есть объединение двух разностей, а одна из этих разностей вычислена выше, найдём \(  \large M_2 \setminus M_1  \). Имеем: \(  \large M_2 \setminus M_1= M_2 \cap \overline{M_1}= \{6,7,9\}  \). Следовательно,

\(  \large M_1 \triangle M_2 = (M_1 \setminus M_2) \cup (M_2 \setminus M_1)=\{1,3,6,7,9 \}  \).

Замечание 8.21. Используя доказанные ранее свойства операций над множествами и определения разности и симметрической разности, можно доказать, что симметрическая разность коммутативна, ассоциативна, но не обладает свойством идемпотентности, а разность не коммутативна, не ассоциативна и не идемпотентна. Однако эти свойства нам не понадобятся, поскольку в ходе решения задач мы всегда будем выражать разность и симметрическую разность через основные операции теории множеств - дополнение, пересечение и объединение.

Замечание 8.22. Подобно тому, как мы говорили об алгебре высказываний, можно говорить об алгебре множеств. Выражения, где буквами обозначены произвольные множества, по сути являются формулами этой алгебры, а тождества, равенства с произвольными множествами, - её равносильностями, законами алгебры множеств. Учитывая важность основных теоретико-множественных тождеств, перечислим их ниже.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #5 : Ноябрь 17, 2017, 02:57:53 pm »
Основные тождества теории множеств

1. \(  \large \overline{\overline{M}}=M  \)

2. \(  \large M \cup \overline{M} = \mathbb{U}  \)

3.  \(  \large M \cap \overline{M} = \not \circ \)

4. \(  \large M \cap (M \cup N)=M \)

5. \(  \large M \cup (M \cap N)=M  \)

6. \(  \large \overline{M \cap N} = \overline{M} \cup \overline{N}  \)

7. \(  \large \overline{M \cup N} = \overline{M} \cap \overline{N}  \)

8. \(  \large M \cap M =M  \)

9. \(  \large M \cup M=M  \)

10. \(  \large M \cap N = N \cap M  \)

11. \(  \large M \cup N = N \cup M  \)

12. \(  \large M \cap (N \cap K) =(M \cap N) \cap K  \)

13. \(  \large M \cup (N \cup K) =(M \cup N) \cup K  \)

14. \(  \large M \cap (N \cup K) = (M \cap N) \cup (M \cap K)  \)

15. \(  \large M \cup (N \cap K) = (M \cup N) \cap (M \cup K)  \)

16.  \(  \large M \cup \mathbb{U} = \mathbb{U}  \)

17.  \(  \large M \cap \mathbb{U} = M  \)

18. \(  \large M \cup \not \circ =M  \)

19. \(  \large M \cap \not \circ = \not \circ  \)

20. \(  \large M \setminus N = M \cap \overline{N}  \)

21. \(  \large M \triangle N= (M \setminus N) \cup (N \setminus M)  \)
 
Сказали спасибо: Alexey, Fedor1995, tom

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #6 : Ноябрь 17, 2017, 03:01:01 pm »
Основные законы алгебры множеств применяются при решении многих задач как в самой теории множеств, так и за её пределами. Мы рассмотрим задачи на упрощение выражений с множествами, доказательство теоретико-множественных тождеств, проверку равенства множеств и доказательство пустоты множества. Кроме того, рассмотрим задачи на доказательство, проверку и упрощение включений множеств. В последних трёх типах задач используются определения включения и операций над множествами, а также основные законы логики высказываний.

***

Задача 8.2. Упростить выражение с множествами:

\(  \large M \cap (M \cup N) \cap (\overline{M \cap N}) \).

Решение. Используем закон поглощения:

\(  \large M \cap (M \cup N) \cap (\overline{M \cap N})= M \cap (\overline{M \cap N})  \).

Применим закон де Моргана:

\(  \large M \cap (\overline{M \cap N}) =M \cap (\overline{M} \cup \overline{N})  \).

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

\(  \large M \cap (\overline{M} \cup \overline{N})= (M \cap \overline{M}) \cup (M \cap \overline{N})  \).

Используем теоретико-множественный аналог логического закона противоречия:

\(  \large (M \cap \overline{M}) \cup (M \cap \overline{N})= \not \circ \cup (M \cap \overline{N})  \).

Вспомним одно из тождеств с пустым множеством:

\(  \large \not \circ \cup (M \cap \overline{N})=M \cap \overline{N}  \).

Выразим пересечение одного множества и дополнения другого множества через разность этих множеств:

\(  \large M \cap \overline{N}= M \setminus N  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #7 : Ноябрь 17, 2017, 03:03:30 pm »
Задача 8.3. Доказать тождество множеств:

\(  \large M \setminus (M \setminus N)=M \cap N \).

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

\(  \large  M \setminus (M \setminus N) = M \cap (\overline{M \cap \overline{N}}) \).

Используем один из теоретико-множественных законов де Моргана и закон инволюции:

\(  \large M \cap (\overline{M \cap \overline{N}})= M \cap (\overline{M} \cup N)  \).

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

\(  \large M \cap (\overline{M} \cup N) = (M \cap \overline{M}) \cup (M \cap N)  \).

Используем тот факт, что пересечение любого множества со своим дополнением является пустым множеством:

\(  \large (M \cap \overline{M}) \cup (M \cap N)= \not \circ \cup (M \cap N)  \).

Применим одно из тождеств с пустым множеством:

\(  \large \not \circ \cup (M \cap N)= M \cap N  \).

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #8 : Ноябрь 18, 2017, 04:29:40 pm »
Задача 8.4. Проверить, выполняется ли равенство для любых множеств \(  \large M  \) и \(  \large N  \):

\(  \large M \cup (N \setminus \overline{M}) = (M \cap \overline{N}) \setminus \overline{M}  \).

Решение. Упростим обе части равенства. Начнём с левой. Избавимся от разности:

\(  \large M \cup (N \setminus \overline{M})= M \cup (N \cap \overline{\overline{M}})  \).

После этого воспользуемся законом инволюции и одним из теоретико-множественных законов поглощения:

\(  \large M \cup (N \cap \overline{\overline{M}})= M \cup (M \cap N) = M  \).

Переходим к тождественным преобразованиям правой части равенства. Выразим разность через пересечение и дополнение:

\(  \large (M \cap \overline{N}) \setminus \overline{M} = (M \cap \overline{N}) \cap \overline{\overline{M}}  \).

Применим закон инволюции и идемпотентность пересечения:

\(  \large  (M \cap \overline{N}) \cap \overline{\overline{M}}= M \cap \overline{N} \cap M = M \cap \overline{N}  \).

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

\(  \large M=M \cap \overline{N}   \).

Пусть, например,

\(  \large M=\{1,2 \}, N=\{1,2, 3 \}, \mathbb{U}=\{1,2, \ldots, 10 \}  \).

Тогда

\(  \large \overline{N}=\{4,5, \ldots, 10 \}  \).

Значит,

\(  \large M \cap \overline{N}=\not \circ \not =M  \).

Итак, равенство не является тождеством.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #9 : Ноябрь 18, 2017, 04:30:18 pm »
Задача 8.5. Доказать, что множество пусто:

\(  \large  ( M \cap N) \setminus (N \cup (K \setminus \overline{M}))  \).

Решение. Будем использовать основные законы алгебры множеств. Сначала избавимся от разности:

\(  \large ( M \cap N) \setminus (N \cup (K \setminus \overline{M}))= M \cap N \cap (\overline{N \cup (K \cap \overline{M})})  \).

Затем применим оба закона де Моргана для множеств и закон инволюции:

\(  \large M \cap N \cap (\overline{N \cup (K \cap \overline{M})})=M \cap N \cap \overline{N } \cap (\overline{K} \cup M)  \).

Используем аналог пропозиционального закона противоречия:

\(  \large M \cap N \cap \overline{N } \cap (\overline{K} \cup M) = M \cap \not \circ \cap (\overline{K} \cup M)  \).

Завершаем доказательство, применяя правило \(  \large M \cap \not \circ = \not \circ  \). Имеем:

\(  \large M \cap \not \circ \cap (\overline{K} \cup M) = \not \circ  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #10 : Ноябрь 18, 2017, 04:34:34 pm »
Задача 8.6. Доказать, что для любых множеств \(  \large M  \) и \(  \large N  \) выполняется включение:

\(  \large M \setminus N \subseteq M   \).

Решение. Пусть \(  \large  M  \) и \(  \large N  \) - произвольные множества, \(  \large x  \) - какой угодно элемент. Тогда, в силу определения включения, множество \(  \large M \setminus N  \) является подмножеством множества \(  \large M  \) тогда и только тогда, когда

\(  \large x \in M \setminus N  \to x \in M \).

Упростим посылку импликации, выразив разность через пересечение и дополнение:

\(  \large x \in M \setminus N  \to x \in M \simeq x \in M \cap \overline{N} \to x \in M  \).

Используем определение пересечения и дополнения:

\(  \large x \in M \cap \overline{N} \to x \in M \simeq (x \in M \wedge x \not \in N) \to x \in M  \).

Избавимся от импликации:

\(  \large (x \in M \wedge x \not \in N) \to x \in M \simeq (\overline{x \in M \wedge x \not \in N}) \to x \in M  \).

Используем закон отрицания конъюнкции и закон двойного отрицания:

\(  \large (\overline{x \in M \wedge x \not \in N}) \to x \in M \simeq x \not \in M \vee x \in N \vee x \in M  \).

Наконец, применим закон исключённого третьего и один из правил действия с константами логики высказываний:

\(  \large x \not \in M \vee x \in N \vee x \in M \simeq x \in N \vee 1 \simeq 1  \).

Итак, высказывание \(  \large x \in M \setminus N \to x \in N  \) истинно, каким бы ни был элемент \(  \large x  \). Значит, \(  \large M \setminus N \subseteq M  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 8. Операции над множествами
« Ответ #11 : Ноябрь 19, 2017, 07:38:46 pm »
Задача 8.7. Проверить, выполняется ли включение для произвольных множеств \(  \large M  \) и \(  \large N  \):

\(  \large M \cup N \subseteq M \setminus N \).

Решение. Пусть \(  \large M  \) и \(  \large N  \) - любые множества. Следовательно, учитывая определение включения,

\(  \large M \cup N \subseteq M \setminus N \),

если и только если высказывание

\(  \large x \in (M \cup N) \to x \in (M \setminus N)  \)

истинно, каким бы ни был элемент \(  \large x  \).

Упростим данное высказывание, используя определения операций над множествами. Имеем:

\(  \large x \in (M \cup N) \to x \in (M \cap \overline{N}) \simeq (x \in M \vee x \in N) \to (x \in M \wedge x \not \in N)  \).

После этого избавимся от импликации:

\(  \large (x \in M \vee x \in N) \to (x \in M \wedge x \not \in N) \simeq (\overline{x \in M \vee x \in N}) \vee (x \in M \wedge x \not \in N)  \).

Применим закон отрицания конъюнкции:

\(  \large (\overline{x \in M \vee x \in N}) \vee (x \in M \wedge x \not \in N) \simeq ( x \not \in M \wedge x \not \in N) \vee (x \in M \wedge x \not \in N)  \).

Вынесем \(  \large x \not \in N  \) за скобки, используя дистрибутивный закон:

\(  \large ( x \not \in M \wedge x \not \in N) \vee (x \in M \wedge x \not \in N) \simeq x \not \in N \wedge (x \not \in M \vee x \in M)  \).

Используем закон исключённого третьего и правило действий с константой единица:

\(  \large x \not \in N \wedge (x \not \in M \vee x \in M)  \simeq x \not \in N \wedge 1 \simeq x \not \in N  \).

Полученное высказывание может быть и ложным. Пусть, например, \(  \large M  \) - какое угодно множество, \(  \large N=\{1,2, \ldots, ,10 \}  \), \(  \large \mathbb{U}=\{ 1,2, \ldots, 10 \}  \). Тогда высказывание \(  \large x \not \in N  \) ложно. Включение не выполняется для произвольных множеств \(  \large M  \) и \(  \large N  \), поскольку нашлись такие множества, что оно неверно.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 8. Операции над множествами
« Ответ #12 : Февраль 16, 2018, 04:31:02 pm »
Задача 8.8. Упростить включение:

\(  \large M \cap N \subseteq (\overline{M} \cup N) \cap K  \).

Решение. Пусть \(  \large x  \) - произвольный элемент. Тогда, в силу определения включения множеств, пересечения, объединения и дополнения, множество \(  \large M \cap N   \) является подмножеством множества \(  \large (\overline{M} \cup N) \cap K  \), если и только если истинно высказывание

\(  \large (x \in M \wedge x \in N ) \to (( x \not \in M \vee x \in N ) \wedge x \in K) \).

Задача об упрощении включения заключается в упрощении данного высказывания при сохранении им формы импликации. Сначала избавимся от импликации:

\(  \large (x \in M \wedge x \in N ) \to (( x \not \in M \vee x \in N ) \wedge x \in K) \simeq x \not \in M \vee x \not \in N \vee (( x \not \in M \vee x \in N ) \wedge x \in K)  \).

Воспользуемся дистрибутивностью конъюнкции относительно дизъюнкции:

\(  \large x \not \in M \vee x \not \in N \vee (( x \not \in M \vee x \in N ) \wedge x \in K) \simeq x \not \in M \vee x \not \in N \vee (x \not \in M \wedge x \in K) \vee (x \in N \wedge x \in K)  \).

Поглощаем конъюнкцию дизъюнкцией:

\(  \large x \not \in M \vee x \not \in N \vee  (x \not \in M \wedge x \in K) \vee (x \in N \wedge x \in K)    \simeq x \not \in M \vee x \not \in N \vee (x \in N \wedge x \in K)  \).

Дизъюнкция дистрибутивна относительно конъюнкции. Раскроем скобки:

\(  \large x \not \in M \vee x \not \in N \vee (x \in N \wedge x \in K) \simeq ( x \not \in M \vee x \not \in N \vee x \in N) \wedge (x \not \in M \vee x \not \in N \vee x \in K)  \).

Используем закон исключённого третьего и правило действий с логической единицей:

\(  \large  ( x \not \in M \vee x \not \in N \vee x \in N) \wedge (x \not \in M \vee x \not \in N \vee x \in K) \simeq x \not \in M \vee x \not \in N \vee x \in K  \).

Чтобы вернуться к импликативной форме, воспользуемся законом отрицания конъюнкции и правилом \(  \large \overline{P} \vee Q \simeq P \to Q  \). Имеем:

\(  \large x \not \in M \vee x \not \in N \vee x \in K \simeq (x  \in M \wedge x  \in N ) \to x \in K   \).

Учитывая, определения включения и пересечения множеств, данное высказывание истинно тогда и только тогда, когда множество \(  \large M \cap
 N \) есть подмножество множества \(  \large K  \). Итак, исходное включение равносильно

\(  \large M \cap N \subseteq K  \).