Математическая статистика иногда требует использования теории множеств. Законы Де Моргана – это два утверждения, которые описывают взаимодействие между различными операциями теории множеств. Законы таковы, что для любых двух наборов A и B:
- ( A ∩ B ) C = A C U B C .
- ( A U B ) C = A C ∩ B C.
После объяснения того, что означает каждое из этих утверждений, мы рассмотрим пример использования каждого из них.
Операции теории множеств
Чтобы понять, что говорят законы Де Моргана, мы должны вспомнить некоторые определения операций теории множеств. В частности, мы должны знать об объединении и пересечении двух множеств и дополнении множества.
Законы Де Моргана относятся к взаимодействию объединения, пересечения , и дополнение. Напомним, что:
- Пересечение множеств A и B состоит из всех элементов, общих для A и B . Пересечение обозначается A ∩ B .
- Объединение множеств A и B состоит из всех элементов в A или B , включая элементы в обоих наборах. Пересечение обозначается AU B.
- Дополнение множества A состоит из всех элементов, которые не являются элементами A . Это дополнение обозначается A C .
Теперь, когда мы вспомнили эти элементарные операции, мы будем см. изложение законов Де Моргана. Для каждой пары наборов A и B мы имеем:
- ( A ∩ B ) C = A C U BC
- ( A U B ) C = A C ∩ B C
Эти два утверждения можно проиллюстрировать с помощью диаграмм Венна. Как показано ниже, мы можем продемонстрировать это на примере. Чтобы продемонстрировать, что эти утверждения верны, мы должны доказать их, используя определения операций теории множеств.
Пример законов Де Моргана
Например, рассмотрим набор действительных чисел от 0 до 5. Мы запишем это в интервальной записи [0, 5]. В этом наборе мы имеем A = [1, 3] и B = [2, 4]. Кроме того, после применения наших элементарных операций мы имеем:
- Дополнение A C = [0, 1) U (3, 5]
- Дополнение B C = [ 0, 2) U (4, 5]
- Объединение A U B = [1, 4]
- Пересечение A ∩ B = [2, 3]
Начнем с вычисления объединения A C U B C . Мы видим, что объединение [0, 1) U (3, 5] с [0, 2) U (4, 5]] есть [0, 2) U (3, 5]. Пересечение A ∩ B равно [2, 3]. Мы видим, что дополнение этого множества [2, 3] также равно [0, 2) U ( 3, 5]. Таким образом, мы продемонстрировали, что A C U B C = ( A ∩ B ) C .
Теперь мы видим пересечение [0, 1) U (3, 5] с [0, 2) U (4, 5] – это [0, 1) U (4, 5]. Мы также видим, что дополнение к [1, 4] также есть [0, 1) U (4, 5]. Таким образом, мы продемонстрировали, что A C ∩ B C = ( A U B)C.
Именование законов Де Моргана
На протяжении всей истории логики такие люди, как Аристотель и Уильям Оккам, делали утверждения, эквивалентные законам Де Моргана.
Законы Де Моргана названы в честь Августа Де Моргана, жившего в 1806–1871 годах. Хотя он не открыл эти законы, он был первым, кто ввел эти утверждения формально, используя математическую формулировку в логике высказываний.