HomeruЧто такое законы Де Моргана?

Что такое законы Де Моргана?

Логика — это раздел математики, частью которого является теория множеств. Законы де Моргана — это два постулата о взаимодействии множеств. Эти законы записывают предшественников у Аристотеля и Уильяма Оккама. Август Де Морган жил между 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 г.