Логіка є розділом математики, і її частиною є теорія множин. Закони де Моргана – це два постулати про взаємодію між множинами. Ці закони записують попередні в Арістотеля та Вільяма Оккама. Август Де Морган жив між 1806 і 1871 роками і був першим, хто включив закони, які він постулював, у формальну структуру математичної логіки.
Оператори в теорії множин
Перш ніж перейти до постулатів Де Моргана, давайте розглянемо деякі визначення теорії множин.
Якщо є будь-які два набори елементів, які ми будемо називати A і B, то перетин цих двох наборів є набором елементів, спільних для обох наборів. Перетин двох множин позначається символом ∩ і є іншою множиною, яку ми можемо назвати 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]. У цьому всесвіті ми визначаємо дві множини A і B. A — це множина чисел 1, 2 і 3; A = [1,2,3]. YB — множина чисел 2, 3 і 4; B = [2,3,4]. Перший закон де Моргана буде застосовуватися наступним чином.
A = [1,2,3]; B = [2,3,4]
Перший закон де Моргана: (A∩B) C = A C UB C
(A∩B) C
A∩B = [1,2,3]∩[2,3,4] = [2,3]
(A∩B) C = [2,3] C = [0,1,4,5]
A C UB C
A C = [1,2,3] C = [0,4,5]
B C = [2,3,4] C = [0,1,5]
A C UB C = [0,4,5]U[0,1,5] = [0,1,4,5]
Результат застосування операторів з обох сторін рівності показує, що перший закон Де Моргана перевірений. Подивимося застосування прикладу до другого постулату.
Другий закон де Моргана: (AUB) C = A C ∩ B C
(AUB) C
AUB = [1,2,3]U[2,3,4] = [1,2,3,4]
(AUB) C = [1,2,3,4] C = [0,5]
A C ∩ B C
A C = [1,2,3] C = [0,4,5]
B C = [2,3,4] C = [0,1,5]
A C ∩ B C = [0,4,5]∩[0,1,5] = [0,5]
Як і у випадку з першим постулатом, у наведеному прикладі також діє другий закон Де Моргана.
Джерела
А. Г. Гамільтон. Логіка для математиків. Editorial Paraninfo, Мадрид, 1981.
Карлос Іворра Кастільо. Логіка і теорія множин . Перевірено листопад 2021 р
