Логика — это раздел математики, частью которого является теория множеств. Законы де Моргана — это два постулата о взаимодействии множеств. Эти законы записывают предшественников у Аристотеля и Уильяма Оккама. Август Де Морган жил между 1806 и 1871 годами и первым включил постулированные им законы в формальную структуру математической логики.
Операторы в теории множеств
Прежде чем перейти к постулатам Де Моргана, давайте рассмотрим некоторые определения теории множеств.
Если существуют любые два набора элементов, которые мы будем называть А и В, то пересечение этих двух множеств есть множество элементов, общих для обоих множеств. Пересечение двух множеств обозначается символом ∩ и является еще одним множеством, которое мы можем назвать C; C = A ∩ B, а C — множество элементов, встречающихся как в группе A, так и в группе B. Точно так же объединение двух множеств A и B — это новое множество, содержащее все элементы A и B, и оно отмечено знаком символ U. Множество C, объединение A и B, C = AUB, представляет собой множество, интегрированное со всеми элементами A и B. Третье определение, которое мы должны помнить, — это дополнение множества: если у нас есть некоторая вселенная элементов и множество A этой вселенной, дополнением A является множество элементов этой вселенной, которые не принадлежат множеству A. Дополняющее множество A обозначается как A C .
Эти три оператора между множествами можно обобщить на операцию между несколькими множествами, то есть на пересечение, объединение и дополнение нескольких множеств. Давайте рассмотрим простой пример. На следующем рисунке показана диаграмма Венна из трех наборов: птицы, представленные попугаем, страусом, уткой и пингвином; живые существа, которые летают, представленные попугаем, уткой, бабочкой и летучей рыбой, и живые существа, которые плавают, представленные уткой, пингвином, летучей рыбой и китом. Утка — это пересечение трех множеств: совокупность птиц и летающих живых существ состоит из страуса, попугая, бабочки, утки, пингвина и летучей рыбы. А дополнением живых существ, которые летают и плавают, является множество, которое содержит страус.
Диаграмма Венна из трех множеств.
Законы де Моргана
Теперь мы можем увидеть постулаты законов Де Моргана. Первый постулат гласит, что дополнение множества пересечения двух множеств A и B равно множеству объединения дополнения A и дополнения B. Используя операторы, определенные в предыдущем абзаце, можно записать первый закон Де Моргана следующим образом:
(A ∩ B) C = A C UB C
Второй закон де Моргана постулирует, что дополнение множества объединения A и B равно пересечению дополнительного множества A с дополнительным множеством B, и это отмечено следующим образом:
(AUB) C = A C ∩ B C
Давайте посмотрим пример. Рассмотрим набор целых чисел от 0 до 5. Он обозначается как [0,1,2,3,4,5]. В этой вселенной мы определяем два множества А и В. А — это множество чисел 1, 2 и 3; А = [1,2,3]. YB – набор чисел 2, 3 и 4; В = [2,3,4]. Первый закон де Моргана будет применяться следующим образом.
А = [1,2,3]; В = [2,3,4]
Первый закон де Моргана: (A ∩ B) C = A C UB C
(А∩В) С
А∩В = [1,2,3]∩[2,3,4] = [2,3]
(А∩В) С = [2,3] С = [0,1,4,5]
А С УБ С
А С = [1,2,3] С = [0,4,5]
В С = [2,3,4] С = [0,1,5]
A C UB C = [0,4,5]U[0,1,5] = [0,1,4,5]
Результат применения операторов в обеих частях равенства показывает, что первый закон Де Моргана верифицируется. Давайте посмотрим на применение примера ко второму постулату.
Второй закон де Моргана: (AUB) C = A C ∩ B C
(АУБ) С
АУБ = [1,2,3]U[2,3,4] = [1,2,3,4]
(АУБ) С = [1,2,3,4] С = [0,5]
А С ∩ В С
А С = [1,2,3] С = [0,4,5]
В С = [2,3,4] С = [0,1,5]
А С ∩ В С = [0,4,5] ∩ [0,1,5] = [0,5]
Как и в случае с первым постулатом, в данном примере также действует второй закон Де Моргана.
Источники
АГ Гамильтон. Логика для математиков. Редакция Paraninfo, Мадрид, 1981.
Карлос Иворра Кастильо. Логика и теория множеств . По состоянию на ноябрь 2021 г.
