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

Правила де Моргана — властивість булевих алгебр, що дозволяє виразити одну з двоїстих операцій $\ \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$	$\lnot q$	$(\lnot p)\lor (\lnot q)$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	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$	$\lnot q$	$(\lnot p)\land (\lnot q)$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

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

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

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

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

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

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

$\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), який застосував формальну версію правил до класичної логіки висловлювань. Формуляція де Моргана створена на основі логіки, започаткованої Джорджем Булем. Схожі спостереження були зроблені Арістотелем, відомим грецьким логіком. Закони де Моргана можуть бути підтверджені просто і навіть здатися тривіальними. Тим не менше, ці закони є корисними в створенні значимих висновків в доказах і результатах дедуктивного міркування.

Див. також

• Булева алгебра
• Алгебра множин
• Алгебра логіки

Посилання

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