HomeukЩо таке закони Де Моргана?

Що таке закони Де Моргана?

Логіка є розділом математики, і її частиною є теорія множин. Закони де Моргана – це два постулати про взаємодію між множинами. Ці закони записують попередні в Арістотеля та Вільяма Оккама. Август Де Морган жив між 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 р