Шта су Де Морганови закони?

Математичка статистика понекад захтева употребу теорије скупова. Де Морганови закони су две изјаве које описују интеракције између различитих операција теорије скупова. Закони су такви за било која два скупа А и Б:

1. (А ∩ Б)^Ц = А^Ц У Б^Ц.
2. (А У Б)^Ц = А^Ц ∩ Б^Ц.

Након што објаснимо шта свака од тих изјава значи, погледаћемо пример сваке употребљене.

Да бисмо разумели шта Де Морганови закони кажу, морамо се сетити неких дефиниција операција теорије скупова. Конкретно, морамо знати за то унија и раскрсница од два сета и комплета комплета.

Де Морганови закони односе се на интеракцију уније, пресеке и комплемента. Сећам се да:

• Пресек скупова А и Б састоји се од свих елемената који су заједнички обема А и Б. Пресјек је означен са А ∩ Б.
• Уједињење скупова А и Б састоји се од свих елемената који се налазе у било ком А или Б, укључујући елементе у оба скупа. Пресјек је означен са А У Б.
• Допуна комплета А састоји се од свих елемената који нису елементи А. Овај комплемент је означен са А^Ц.

Сада када смо се присетили тих елементарних операција, видећемо изјаву Де Морганових закона. За сваки пар сетова А и Б имамо:

1. (А ∩ Б)^Ц = А^Ц У Б^Ц
2. (А У Б)^Ц = А^Ц ∩ Б^Ц

Ове две изјаве могу се илустровати употребом Веннових дијаграма. Као што се види у наставку, можемо демонстрирати на примјеру. Да бисмо показали да су ове изјаве тачне, морамо доказати их коришћењем дефиниција операција теорије скупова.

На пример, размотрите скуп реални бројеви од 0 до 5. То пишемо у интервалној нотацији [0, 5]. Унутар овог скупа имамо А = [1, 3] и Б = [2, 4]. Надаље, након примјене наших основних операција, имамо:

• Комплемент А^Ц = [0, 1) У (3, 5]
• Комплемент Б^Ц = [0, 2) У (4, 5]
• Синдикат А У Б = [1, 4]
• Раскрсница А ∩ Б = [2, 3]

Започињемо израчунавањем уније А^Ц У Б^Ц. Видимо да је унија [0, 1) У (3, 5] са [0, 2) У (4, 5] једнака [0, 2) У (3, 5]. Раскрсница А ∩ Б је [2, 3]. Видимо да је комплемент овог скупа [2, 3] такође [0, 2) У (3, 5]. На овај начин смо то и показали А^Ц У Б^Ц = (А ∩ Б)^Ц.

Сада видимо пресек [0, 1) У (3, 5] са [0, 2) У (4, 5] је [0, 1) У (4, 5]. Такође видимо да је комплемент [1, 4] такође [0, 1) У (4, 5]. На овај начин смо то и показали А^Ц ∩ Б^Ц = (А У Б)^Ц.

Кроз историју логике људи попут Аристотел и Виллиам из Оцкхама дали су изјаве еквивалентне Де Моргановим законима.

Де Морганови закони названи су по Августу Де Моргану, који је живео од 1806-1871. Иако није открио ове законе, био је први који је формално увео ове изјаве користећи математичку формулацију у логици предлога.