- Что такое законы де Моргана?
- - Не (stem:[A] или stem:[B]) — это то же самое, что не stem:[A] и не stem:[B]
- stem:[(A cap B)' = A' cup B']
- stem:[(A cup B)' = A' cap B']
- Сколько студентов планируют посетить обе игры? +
- stem:[200-58=142]
- Найдем, сколько целых чисел от stem:[1] до stem:[1000] включительно не являются ни кратными stem:[2], ни кратными stem:[5].
- stem:[(A cup B)' = 1000 - 600 = 400]
- - stem:[(A cup B)' = A' cap B']
- - stem:[~(A*B) = ~A+~B]
// source_path[42182/800-de_morgan/README.adoc] image::https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImZkYWY1MjY3ODRkODg1OGMwYmE1NDM2MTAyZmQwY2UyLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=48dc3e79a5c506eabe36c8fbadfae8a917ab118c5c879aba9ca6bc6fc9072c4c[]
Законы де Моргана описывают, как математические утверждения и понятия связаны через их противоположности. В теории множеств законы де Моргана связывают пересечение и объединение множеств через их дополнения.
Если мы хотим упростить операции с множествами, то мы используем законы де Моргана. В этом уроке мы познакомимся с утверждениями законов де Моргана, их применением и примерами.
:stem:
Что такое законы де Моргана?
Закон де Моргана описывает взаимосвязь между тремя фундаментальными операциями над множествами:
- Дополнением множеств
- Объединением множеств
- Пересечением множеств
В зависимости от взаимосвязи между объединением и пересечением множеств, существует два типа закона де Моргана. Буквально их можно представить так:
====
- Не (stem:[A] и stem:[B]) — это то же самое, что Не stem:[A] или Не stem:[B]
- Не (stem:[A] или stem:[B]) — это то же самое, что не stem:[A] и не stem:[B]
Для множеств закон де Моргана — это просто наблюдения о связи между множествами и их дополнениями. Простой способ визуализации этих правил — диаграммы Венна.
Переходим к первому закону.
Закон пересечения де Моргана
На диаграмме два множества: stem:[A] и stem:[B]. Мы объединяем их дополнения: на диаграмме это объединение охватывает все пространство, кроме пересечения двух множеств.
Напомним, что дополнение обозначается значком stem:['].
Так закон де Моргана для дополнения пересечения двух множеств можно обозначить на схеме:
Дополнение пересечения множеств stem:[A] и stem:[B] — это все пространство на диаграмме, кроме пересечения stem:[A] и stem:[B].
Оно равно объединению stem:[A'] и stem:[B']:
====
stem:[(A cap B)' = A' cup B']
Перейдем к второму закону.
Закон объединения де Моргана
Теперь мы объединяем не дополнения, а сами множества stem:[A] и stem:[B] и смотрим на пересечение их дополнений.
На диаграмме Венна это пересечение охватывает все пространство, кроме объединения двух множеств. Как в первом случае, только наоборот. Отсюда следует закон де Моргана для дополнения объединения двух множеств:
====
stem:[(A cup B)' = A' cap B']
Как и в предыдущем случае, этот закон можно описать такой формулой и показать на диаграмме:
Как работают законы де Моргана
Рассмотрим закон де Моргана на простом примере. Возьмем такое условие задачи:
====
В ходе недавнего опроса студентов спрашивали, планируют ли они пойти на баскетбольный или футбольный матч. +
Всего было опрошено stem:[200] человек. +
stem:[58] учащихся заявили, что они пропустят хотя бы одну из игр. В это число входят и студенты, которые планируют пропустить обе игры. +
Сколько студентов планируют посетить обе игры? +
Применим закон объединения де Моргана:
==== stem:[58] студентов пропустят хотя бы одну из игр — это можно интерпретировать как «stem:[58] студентов пропустят баскетбольную игру или пропустят футбольную игру». +
По закону де Моргана, это множество из stem:[58] студентов является дополнением множества студентов, которые посетят обе игры. +
Таким образом, вычислим количество студентов, которые посетят обе игры: +
stem:[200-58=142]
Другой пример:
====
Найдем, сколько целых чисел от stem:[1] до stem:[1000] включительно не являются ни кратными stem:[2], ни кратными stem:[5].
Применим закон де Моргана:
==== По условию:
- stem:[A] — множество целых чисел от stem:[1] до stem:[1000], которые кратны stem:[2]
- stem:[B] — множество целых чисел от stem:[1] до stem:[1000], которые кратны stem:[5]
Вопрос состоит в том, чтобы найти stem:[(A' cap B')].
По законам де Моргана нам надо найти stem:[(A cup B)']:
- stem:[1000 divide 2 = 500] целых чисел от stem:[1] до stem:[1000], которые делятся на stem:[2]. Это наше множество stem:[A]
- stem:[1000 divide 5 = 200] целых чисел от stem:[1] до stem:[1000], которые делятся на stem:[5]. Это наше множество stem:[B]
- stem:[1000 divide (2 times 5) = 100] целых чисел от stem:[1] до stem:[1000], которые кратны и stem:[2], и stem:[5]
Теперь мы можем найти количество целых чисел от stem:[1] до stem:[1000], которые кратны stem:[2] или stem:[5]: +
stem:[(A cup B) = 500 + 200 - 100 = 600] +
Следовательно, количество целых чисел от stem:[1] до stem:[1000], которые не кратны ни stem:[2] ни stem:[5]:
stem:[(A cup B)' = 1000 - 600 = 400]
Формула закона де Моргана
Закрепим, что законы де Моргана используется в теории множеств и в булевой алгебре.
Используя эти законы, можно установить связь между объединением и пересечением через дополнение.
Ниже мы разберем различные формы формул в теории множеств:
====
- stem:[(A cap B)' = A' cup B']
- stem:[(A cup B)' = A' cap B']
Также различные формы формул есть в булевой алгебре:
====
- stem:[~(A+B) = ~A*~B]
- stem:[~(A*B) = ~A+~B]
Применение законов де Моргана
Законы де Моргана используются как в элементарной, так и в булевой алгебре. Они помогают сократить сложные выражения, и поэтому широко используются в большинстве инженерных отраслей для создания аппаратуры и упрощения операций.
Рассмотрим такие примеры:
- Применение закона де Моргана можно увидеть в электронной технике для разработки логических вентилей. С помощью этого закона уравнения могут быть построены с использованием только stem:NAND или stem:NOR. Это приводит к удешевлению аппаратуры
- Законы де Моргана используются в программировании. Они помогают упростить логические выражения, записанные в коде — тем самым уменьшают количество строк и помогают оптимизировать код. Кроме того, эти законы значительно упрощают и ускоряют проверку некоторых кодов, например на SAS
Самостоятельная работа
// source_path[42182/800-de_morgan/self_study.adoc]
Задача №1:
:stem:
Докажите первый закон де Моргана при таком условии:
- stem:[A = {3, 5}] +
- stem:[B = {5, 7, 9}] +
- stem:[U = {1, 3, 5, 7, 9, 11}] +
.Нажмите, чтобы увидеть ответ [%collapsible]
==== Согласно второму закону де Моргана, stem:[(A cup B)' = A' cap B']. + + Таким образом: +
- stem:[(A cup B) = {3, 5, 7, 9}] +
- stem:[(A cup B)' = {1, 11}] +
- stem:[A' = {1, 7, 9, 11}] +
- stem:[B' = {1, 3, 11}] +
- stem:[A' cap B' = {1, 11}]
====
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
