Правила де Моргана — властивість булевих алгебр , що дозволяє виразити одну з двоїстих операцій
∨
,
∧
{\displaystyle \ \lor ,\land }
через іншу і унарну операцію
¬
{\displaystyle \ \lnot }
доповнення (заперечення). Особливо часто використовуються у алгебрі множин і алгебрі логіки , що є прикладами булевої алгебри. Названі на честь британського математика і логіка Ауґустуса де Моргана .
Правила де Моргана Названо на честь
Ауґустус де Морган Досліджується в
логіка Формула
¬
(
P
∧
Q
)
⊢
(
¬
P
∨
¬
Q
)
.
{\displaystyle \neg (P\land Q)\vdash (\neg P\lor \neg Q).}
і
¬
(
P
∨
Q
)
⊢
(
¬
P
∧
¬
Q
)
.
{\displaystyle \neg (P\lor Q)\vdash (\neg P\land \neg Q).}
Позначення у формулі
P
{\displaystyle P}
,
Q
{\displaystyle Q}
,
∧
{\displaystyle \land }
,
¬
{\displaystyle \lnot }
,
∨
{\displaystyle \lor }
і
⊢
{\displaystyle \vdash }
Допустиме правило в
Класична логіка Підтримується Вікіпроєктом
Вікіпедія:Проєкт:Математика
Логічна схема правил де Моргана Закони де Моргана, представлені за допомогою діаграм Венна . В обох випадках, результовна множина - це множина всіх точок будь-якого відтінку синього.
Твердження
ред.
Для булевої алгебри
ред.
Нехай
(
B
,
∨
,
∧
,
−
,
0
,
1
)
{\displaystyle (B,\lor ,\land ,-,0,1)}
є деяка булева алгебра, тоді для
a
,
b
∈
B
{\displaystyle a,b\in B}
справджується:
(
a
∨
b
)
¯
=
a
¯
∧
b
¯
;
{\displaystyle {\overline {(a\lor b)}}={\overline {a}}\land {\overline {b}};}
(
a
∧
b
)
¯
=
a
¯
∨
b
¯
{\displaystyle {\overline {(a\land b)}}={\overline {a}}\lor {\overline {b}}}
Мають місце також узагальнені правила де Моргана :
(
∨
i
∈
I
a
i
)
¯
=
∧
i
∈
I
a
i
¯
{\displaystyle {\overline {\left(\lor _{i\in I}~a_{i}\right)}}=\land _{i\in I}~{\overline {a_{i}}}}
,
(
∧
i
∈
I
a
i
)
¯
=
∨
i
∈
I
a
i
¯
{\displaystyle {\overline {\left(\land _{i\in I}~a_{i}\right)}}=\lor _{i\in I}~{\overline {a_{i}}}}
.Для алгебри логіки
ред.
Перше правило де Моргана :
¬
(
p
∧
q
)
⟺
(
¬
p
∨
¬
q
)
{\displaystyle \lnot (p\land q)\iff (\lnot p\lor \lnot q)}
,Друге правило де Моргана
¬
(
p
∨
q
)
⟺
(
¬
p
∧
¬
q
)
{\displaystyle \lnot (p\lor q)\iff (\lnot p\land \lnot q)}
;В обох цих формулах
∨
{\displaystyle \lor }
— логічна диз'юнкція ,
∧
{\displaystyle \land }
— логічна кон'юнкція ,
¬
{\displaystyle \lnot }
— логічне заперечення (негація), p, q — деякі логічні висловлення.
Істинність даних правил можна підтвердити за допомогою таблиць істинності
¬
(
p
∧
q
)
⟺
(
¬
p
)
∨
(
¬
q
)
{\displaystyle \lnot (p\land q)\iff (\lnot p)\lor (\lnot q)}
p
{\displaystyle p}
q
{\displaystyle q}
p
∧
q
{\displaystyle p\land q}
¬
(
p
∧
q
)
{\displaystyle \lnot (p\land q)}
¬
p
{\displaystyle \lnot p}
¬
q
{\displaystyle \lnot q}
(
¬
p
)
∨
(
¬
q
)
{\displaystyle (\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
¬
(
p
∨
q
)
⟺
(
¬
p
)
∧
(
¬
q
)
{\displaystyle \lnot (p\lor q)\iff (\lnot p)\land (\lnot q)}
p
{\displaystyle p}
q
{\displaystyle q}
p
∨
q
{\displaystyle p\lor q}
¬
(
p
∨
q
)
{\displaystyle \lnot (p\lor q)}
¬
p
{\displaystyle \lnot p}
¬
q
{\displaystyle \lnot q}
(
¬
p
)
∧
(
¬
q
)
{\displaystyle (\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
{\displaystyle X}
— деяка множина і
A
,
B
⊂
X
{\displaystyle A,B\subset X}
— її підмножини. Тоді виконується:
(
A
∪
B
)
c
=
A
c
∩
B
c
{\displaystyle (A\cup B)^{c}=A^{c}\cap B^{c}}
,
(
A
∩
B
)
c
=
A
c
∪
B
c
{\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}
де
∪
,
∩
,
A
c
{\displaystyle \cup ,\cap ,A^{c}}
— стандартні позначення для об'єднання множин , перетину та доповнення множин .
Також виконуються і узагальнені правила
(
⋃
i
∈
I
A
i
)
c
=
⋂
i
∈
I
A
i
c
.
{\displaystyle \left(\bigcup _{i\in I}~A_{i}\right)^{c}=\bigcap _{i\in I}~A_{i}^{c}.}
,
(
⋂
i
∈
I
A
i
)
c
=
⋃
i
∈
I
A
i
c
.
{\displaystyle \left(\bigcap _{i\in I}~A_{i}\right)^{c}=\bigcup _{i\in I}~A_{i}^{c}.}
,де
I
⊂
N
{\displaystyle I\subset \mathbb {N} }
Доведення в теорії
ред.
Правила засновані на відношеннях
A
¯
∪
B
¯
=
A
∩
B
¯
{\displaystyle {\overline {A}}\cup {\overline {B}}={\overline {A\cap B}}}
,які графічно представлені ілюстраціями нижче.
Дано дві множини A і В, які є підмножинами Ω (універсуму). Діаграма 1 показує їх розташування відносно одна до одної. У діаграмі 2 показано, як формується
A
¯
∪
B
¯
{\displaystyle {\overline {A}}\cup {\overline {B}}}
. У діаграмі 3 на прикладі
A
∩
B
{\displaystyle A\cap B}
можна побачити що обидві множини рівні.
Розподіл простору в А та В
A
¯
∪
B
¯
{\displaystyle {\overline {A}}\cup {\overline {B}}}
A
∩
B
¯
{\displaystyle {\overline {A\cap B}}}
Правила де Моргана були названі на честь британського математика Ауґустуса де Моргана (1806—1871) , який застосував формальну версію правил до класичної логіки висловлювань. Формуляція де Моргана створена на основі логіки, започаткованої Джорджем Булем . Схожі спостереження були зроблені Арістотелем , відомим грецьким логіком. Закони де Моргана можуть бути підтверджені просто і навіть здатися тривіальними. Тим не менше, ці закони є корисними в створенні значимих висновків в доказах і результатах дедуктивного міркування.
Див. також
ред.