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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Логічна схема правил де Моргана

Правила де Моргана — властивість булевих алгебр, що дозволяє виразити одну з двоїстих операцій \ \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 можна побачити що обидві множини рівні.

DeMorgan1.jpg DeMorgan2.jpg DeMorgan3.jpg
Розподіл простору в А та В \overline{A}\cup\overline{B} \overline{A\cap B}


Історія[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]