Правила де Моргана

Правила де Моргана
Закони де Моргана у вигляді діаграм Венна. У випадках 1 та 2, результовна множина у відтінках синього кольору.
Галузь науки	логіка
Відкрив	Ауґустус де Морган
Формула	$\neg (P\land Q)\vdash (\neg P\lor \neg Q).$ $\neg (P\lor Q)\vdash (\neg P\land \neg Q).$
Позначення в формулі	пропозиційна формула ($P$) пропозиційна формула ($Q$) кон'юнкція ($\land$) логічне заперечення ($\lnot$) диз'юнкція ($\lor$) дедукція ($\vdash$)

Логічна схема правил де Моргана

Правила де Моргана — властивість булевих алгебр, що дозволяє виразити одну з двоїстих операцій $\ \lor ,\land$ через іншу і унарну операцію $\ \lnot$ доповнення (заперечення).

Використовуються у алгебрі множин (в теорії множин) та алгебрі логіки (в численні висловлень). Названі на честь британського математика і логіка Аугустуса де Моргана.

Твердження

Для булевої алгебри

Нехай $(B,\lor ,\land ,-,0,1)$ є деяка булева алгебра, тоді для $a,b\in B$ справджується:

${\overline {a\lor b}}={\overline {a}}\land {\overline {b}};$

${\overline {a\land b}}={\overline {a}}\lor {\overline {b}}$

Мають місце також узагальнені правила де Моргана:

${\overline {\left(\lor _{i\in I}~a_{i}\right)}}=\land _{i\in I}~{\overline {a_{i}}}$,

${\overline {\left(\land _{i\in I}~a_{i}\right)}}=\lor _{i\in I}~{\overline {a_{i}}}$.

Для алгебри логіки

$\lnot (p\land q)\iff (\lnot p\lor \lnot q)$,

$\lnot (p\lor q)\iff (\lnot p\land \lnot q)$;

В обох цих формулах $\lor$ — логічна диз'юнкція,$\land$ — логічна кон'юнкція,$\lnot$ — логічне заперечення (негація), p, q — деякі логічні висловлення.

Істинність даних правил можна підтвердити за допомогою таблиць істинності

$\lnot (p\land q)\iff (\lnot p)\lor (\lnot q)$
$p$	$q$	$p\land q$	$\lnot (p\land q)$	$(\lnot p)\lor (\lnot q)$	$\lnot p$	$\lnot q$
0	0	0	1	1	1	1
0	1	0	1	1	1	0
1	0	0	1	1	0	1
1	1	1	0	0	0	0

$\lnot (p\lor q)\iff (\lnot p)\land (\lnot q)$
$p$	$q$	$p\lor q$	$\lnot (p\lor q)$	$(\lnot p)\land (\lnot q)$	$\lnot p$	$\lnot q$
0	0	0	1	1	1	1
0	1	1	0	0	1	0
1	0	1	0	0	0	1
1	1	1	0	0	0	0

Для алгебри множин

Нехай $X$ — деяка множина і $A,B\subset X$ — її підмножини. Тоді виконується:

$(A\cup B)^{c}=A^{c}\cap B^{c}$,

$(A\cap B)^{c}=A^{c}\cup B^{c}$

де $\cup ,\cap ,A^{c}$ — стандартні позначення для об'єднання, перетину та доповнення множин.

Використавши третю множину і операцію різниці множин, це можна переписати як.

$C-(A\cup B)=(C-A)\cap (C-B),$

$C-(A\cap B)=(C-A)\cup (C-B)$

Також виконуються і узагальнені правила

$\left(\bigcup _{i\in I}~A_{i}\right)^{c}=\bigcap _{i\in I}~A_{i}^{c}.$,

$\left(\bigcap _{i\in I}~A_{i}\right)^{c}=\bigcup _{i\in I}~A_{i}^{c}.$,

де $I\subset \mathbb {N}$

Доведення в теорії

Правила засновані на відношеннях

${\overline {A}}\cup {\overline {B}}={\overline {A\cap B}}$,

які графічно представлені ілюстраціями нижче. Дано дві множини A і В, які є підмножинами Ω (універсуму). Діаграма 1 показує їх розташування відносно одна до одної. У діаграмі 2 показано, як формується ${\overline {A}}\cup {\overline {B}}$. У діаграмі 3 на прикладі $A\cap B$ можна побачити що обидві множини рівні.

Розподіл простору в А та В	${\overline {A}}\cup {\overline {B}}$	${\overline {A\cap B}}$

Історія

Правила названі на честь британського математика Ауґустуса де Моргана (1806—1871), який застосував формальну версію правил до класичної логіки висловлювань. Формуляція де Моргана створена на основі логіки, започаткованої Джорджем Булем. Схожі спостереження були зроблені Арістотелем, відомим грецьким логіком. Закони де Моргана можуть бути підтверджені просто і навіть здатися тривіальними. Тим не менше, ці закони є корисними в створенні значимих висновків в доказах і результатах дедуктивного міркування.

Джерела

• Г. Цейтлін. Елементи теорії булевих функцій. — Київ : Техніка, 1967. — 76 с.(укр.)
• Вітенько І. В. Математична логіка: Курс лекцій. — Ужгород : УжДУ, 1971. — 224 с.(укр.)
• Хромой В. Я. Збірник вправ і задач з математичної логіки. — Київ : Вища школа, 1978. — 160 с.(укр.)
• Дрозд Ю. А. (2005). Основи математичної логіки (PDF). Київ: ВПЦ "Київський університет". с. 96. (укр.)
• Безущак О. О., Ганюшкін О. Г. Математична логіка: Навчальний посібник. — Київ : ВПЦ "Київський університет", 2023. — 143 с.(укр.)
• Ляшко І. І., Боярчук О. К., Гай Я. Г., Головач Г. П. Математичний аналіз в прикладах і задачах. — 2026. — 2538 с.(укр.)
• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Weisstein, Eric W. Правила де Моргана(англ.) на сайті Wolfram MathWorld.
• Правила де Моргана на PlanetMath.(англ.)