Правила де Моргана Названо на честь
Ауґустус де Морган Досліджується в
логіка Формула
¬
(
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 }
Допустиме правило в
класична логіка Підтримується Вікіпроєктом
Вікіпедія:Проєкт:Математика
Закони де Моргана у вигляді діаграм Венна . У випадках 1 та 2, результовна множина у відтінках синього кольору. Логічна схема правил де Моргана Правила де Моргана — властивість булевих алгебр , що дозволяє виразити одну з двоїстих операцій
∨
,
∧
{\displaystyle \ \lor ,\land }
унарну операцію
¬
{\displaystyle \ \lnot }
Використовуються у алгебрі множин (в теорії множин ) та алгебрі логіки (в численні висловлень ). Названі на честь британського математика і логіка Аугустуса де Моргана .
Нехай
(
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
)
∨
(
¬
q
)
{\displaystyle (\lnot p)\lor (\lnot q)}
¬
p
{\displaystyle \lnot p}
¬
q
{\displaystyle \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
¬
(
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
)
∧
(
¬
q
)
{\displaystyle (\lnot p)\land (\lnot q)}
¬
p
{\displaystyle \lnot p}
¬
q
{\displaystyle \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
{\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}}
об'єднання , перетину та доповнення множин.
Використавши третю множину і операцію різниці множин , це можна переписати як.
C
−
(
A
∪
B
)
=
(
C
−
A
)
∩
(
C
−
B
)
,
{\displaystyle C-(A\cup B)=(C-A)\cap (C-B),}
C
−
(
A
∩
B
)
=
(
C
−
A
)
∪
(
C
−
B
)
{\displaystyle C-(A\cap B)=(C-A)\cup (C-B)}
Також виконуються і узагальнені правила
(
⋃
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}}}
A
∩
B
{\displaystyle A\cap B}
Розподіл простору в А та В
A
¯
∪
B
¯
{\displaystyle {\overline {A}}\cup {\overline {B}}}
A
∩
B
¯
{\displaystyle {\overline {A\cap B}}}
Правила названі на честь британського математика Ауґустуса де Моргана (1806—1871) , який застосував формальну версію правил до класичної логіки висловлювань. Формуляція де Моргана створена на основі логіки, започаткованої Джорджем Булем . Схожі спостереження були зроблені Арістотелем , відомим грецьким логіком. Закони де Моргана можуть бути підтверджені просто і навіть здатися тривіальними. Тим не менше, ці закони є корисними в створенні значимих висновків в доказах і результатах дедуктивного міркування.
