Законы де Моргана - De Morgans laws

Законы Де Моргана представлены Диаграммы Венна. В каждом случае результирующий набор представляет собой набор всех точек любого оттенка синего.

В логика высказываний и Булева алгебра, Законы де Моргана^[1][2][3] - это пара правил преобразования, которые оба действительный правила вывода. Они названы в честь Огастес Де Морган, британский математик 19 века. Правила допускают выражение союзы и дизъюнкции чисто по отношению друг к другу через отрицание.

Правила могут быть выражены на английском языке как:

отрицание дизъюнкции - это соединение отрицаний; и

отрицание союза есть дизъюнкция отрицаний;

или же

то дополнять объединения двух множеств совпадает с пересечением их дополнений; и

дополнение пересечения двух множеств совпадает с объединением их дополнений.

или же

not (A или B) = не A и не B; и

not (A и B) = не A или не B

В теория множеств и Булева алгебра, они записываются формально как

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

куда

• А и B наборы,
• А является дополнением к A,
• ∩ это пересечение, и
• ∪ это союз.

В формальный язык, правила записываются как

${\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),}$

и

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$

куда

• п и Q - предложения,
• ${\displaystyle \neg }$ - логический оператор отрицания (НЕ),
• ${\displaystyle \land }$ является логическим оператором конъюнкции (И),
• ${\displaystyle \lor }$ - логический оператор дизъюнкции (ИЛИ),
• ${\displaystyle \iff }$ это металогический значение символа "можно заменить на логическое доказательство с".

Применение правил включает упрощение логического выражения в компьютерные программы и цифровые схемы. Законы Де Моргана являются примером более общей концепции математическая двойственность.

Формальное обозначение

В отрицание союза правило может быть записано в последовательный обозначение:

${\displaystyle \neg (P\land Q)\vdash (\neg P\lor \neg Q)}$,

и

${\displaystyle (\neg P\lor \neg Q)\vdash \neg (P\land Q)}$.

В отрицание дизъюнкции правило можно записать как:

${\displaystyle \neg (P\lor Q)\vdash (\neg P\land \neg Q)}$,

и

${\displaystyle (\neg P\land \neg Q)\vdash \neg (P\lor Q)}$.

В форма правила: отрицание союза

${\displaystyle {\frac {\neg (P\land Q)}{\therefore \neg P\lor \neg Q}}}$

${\displaystyle {\frac {\neg P\lor \neg Q}{\therefore \neg (P\land Q)}}}$

и отрицание дизъюнкции

${\displaystyle {\frac {\neg (P\lor Q)}{\therefore \neg P\land \neg Q}}}$

${\displaystyle {\frac {\neg P\land \neg Q}{\therefore \neg (P\lor Q)}}}$

и выражается как функционал истины тавтология или же теорема логики высказываний:

${\displaystyle {\begin{aligned}\neg (P\land Q)&\to (\neg P\lor \neg Q),\\(\neg P\lor \neg Q)&\to \neg (P\land Q),\\\neg (P\lor Q)&\to (\neg P\land \neg Q),\\(\neg P\land \neg Q)&\to \neg (P\lor Q),\end{aligned}}}$

куда ${\displaystyle P}$ и ${\displaystyle Q}$ суждения, выраженные в некоторой формальной системе.

Форма замены

Законы Де Моргана обычно показаны в компактной форме выше, с отрицанием выхода слева и отрицанием входов справа. Более четкую форму замены можно сформулировать так:

${\displaystyle {\begin{aligned}(P\land Q)&\Longleftrightarrow \neg (\neg P\lor \neg Q),\\(P\lor Q)&\Longleftrightarrow \neg (\neg P\land \neg Q).\end{aligned}}}$

Это подчеркивает необходимость инвертировать входы и выходы, а также изменять оператор при выполнении подстановки.

В законах есть важный пробел по отношению к (${\displaystyle \neg (\neg p)\iff p}$) закон двойного отрицания. ${\displaystyle \mathbb {L} }$, чтобы стать формальной логической системой: ${\displaystyle \ p,q,r,....,\emptyset \in \mathbb {L} \ }$ Последовательность сообщает символы, которые определены правильно сформированными в первом порядке. В той же системе есть эти соединения: ${\displaystyle C_{|j}:x\ |\ x\in set::\{\land ,\lor ,\iff ,\vdash \}}$. Очевидно, ${\displaystyle C_{|j}=set,\ x\in C_{|j}}$ действительно знание, то есть хотя бы один ${\displaystyle x}$ соединение, которое -${\displaystyle T}$ число - в таблице истинности, основное утверждение ${\displaystyle x}$- равно атомарному контексту существования ${\displaystyle x}$, конечно, согласно ${\displaystyle \forall x:(\mathbb {L} \vDash \forall c\subsetneq C_{|j},\ x\in c)}$ знание. Мы рассматривали теорию эквивалентности, логика делает. На этом этапе законы Де Моргана показывают восходящий или нисходящий эффект, атомарный контекст ${\displaystyle x}$. ^[4]

Теория множеств и булева алгебра

В теории множеств и Булева алгебра, его часто называют «взаимообмен объединением и пересечением при дополнении»,^[5] что формально можно выразить как:

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

куда:

• А отрицание A, над чертой написано выше условий, которые необходимо отрицать,
• ∩ это пересечение оператор (И),
• ∪ это союз оператор (ИЛИ).

Бесконечные союзы и пересечения

Обобщенная форма

${\displaystyle {\begin{aligned}{\overline {\bigcap _{i\in I}A_{i}}}&\equiv \bigcup _{i\in I}{\overline {A_{i}}},\\{\overline {\bigcup _{i\in I}A_{i}}}&\equiv \bigcap _{i\in I}{\overline {A_{i}}},\end{aligned}}}$

куда я - это некоторый, возможно, неисчислимый набор индексации.

В устоявшихся обозначениях законы Де Моргана можно запомнить с помощью мнемонический «разорвать черту, поменять знак».^[6]

Инженерное дело

В электрические и компьютерная инженерия, Законы Де Моргана обычно записываются как:

${\displaystyle {\overline {A\cdot B}}\equiv {\overline {A}}+{\overline {B}}}$

и

${\displaystyle {\overline {A+B}}\equiv {\overline {A}}\cdot {\overline {B}},}$

куда:

• ${\displaystyle \cdot }$ это логическое И,
• ${\displaystyle +}$ это логическое ИЛИ,
• то надбавка является логическим НЕ того, что находится под чертой сверху.

Текстовый поиск

Законы Де Моргана обычно применяются к поиску текста с использованием логических операторов AND, OR и NOT. Рассмотрим комплект документов, содержащих слова «легковые автомобили» и «грузовики». Законы Де Моргана гласят, что в результате этих двух поисков будет возвращен один и тот же набор документов:

Искать A: НЕ (автомобили ИЛИ грузовики)

Поиск B: (НЕ автомобили) И (НЕ грузовики)

Пакет документов, содержащий «легковые автомобили» или «грузовики», может быть представлен четырьмя документами:

Документ 1: содержит только слово «автомобили».

Документ 2: содержит только «грузовики».

Документ 3: содержит как «легковые автомобили», так и «грузовики».

Документ 4: Не содержит ни «легковых автомобилей», ни «грузовиков».

Чтобы оценить Поиск A, очевидно, что поиск «(автомобили ИЛИ грузовики)» попадет в Документы 1, 2 и 3. Таким образом, отрицание этого поиска (то есть Поиск A) затронет все остальное, то есть Документ 4.

При оценке поиска B поиск «(НЕ автомобили)» будет попадать в документы, которые не содержат «автомобили», то есть в Документах 2 и 4. Аналогичным образом поиск «(НЕ грузовые автомобили)» попадет в Документы 1 и 4. Применение Оператор AND для этих двух поисков (который является поиском B) затронет документы, общие для этих двух поисков, то есть Документ 4.

Аналогичная оценка может быть применена, чтобы показать, что следующие два поиска вернут один и тот же набор документов (документы 1, 2, 4):

Искать C: НЕ (легковые и грузовые автомобили),

Найдите D: (НЕ автомобили) ИЛИ (НЕ грузовики).

История

Законы названы в честь Огастес Де Морган (1806–1871),^[7] кто представил формальную версию законов классической логика высказываний. На формулировку Де Моргана повлияла алгебраизация логики, предпринятая Джордж Буль, которая позже закрепила претензию Де Моргана на находку. Тем не менее подобное наблюдение было сделано Аристотель, и был известен греческим и средневековым логикам.^[8] Например, в 14 веке Уильям Оккам записал слова, которые возникнут после зачитывания законов.^[9] Жан Буридан, в его Summulae de Dialectica, также описывает правила преобразования, соответствующие законам Де Моргана.^[10] Тем не менее, Де Моргану приписывают формулировку законов в терминах современной формальной логики и включение их в язык логики. Законы Де Моргана можно легко доказать, и они могут даже показаться тривиальными.^[11] Тем не менее, эти законы помогают делать обоснованные выводы в доказательствах и дедуктивных аргументах.

Неофициальное доказательство

Теорема Де Моргана может быть применена к отрицанию дизъюнкция или отрицание соединение полностью или частично в формуле.

Отрицание дизъюнкции

В случае его применения к дизъюнкции рассмотрим следующее утверждение: «неверно, что либо A, либо B истинны», которое записывается как:

${\displaystyle \neg (A\lor B).}$

При этом установлено, что ни один A и B верны, тогда должно следовать, что оба A не верны и B не соответствует действительности, что можно записать прямо как:

${\displaystyle (\neg A)\wedge (\neg B).}$

Если либо A, либо B мы true, тогда дизъюнкция A и B будет истинной, а его отрицание будет ложным. Представленный на английском языке, это следует логике, что «поскольку две вещи ложны, также неверно, что любая из них истинна».

Работая в противоположном направлении, второе выражение утверждает, что A ложно, а B ложно (или, что то же самое, что «не A» и «не B» истинны). Зная это, дизъюнкция A и B также должна быть ложной. Таким образом, отрицание указанной дизъюнкции должно быть истинным, и результат идентичен первому утверждению.

Отрицание союза

Применение теоремы Де Моргана к конъюнкции очень похоже на ее применение к дизъюнкции как по форме, так и по обоснованию. Рассмотрим следующее утверждение: «неверно, что A и B истинны», которое записывается как:

${\displaystyle \neg (A\land B).}$

Для того, чтобы это утверждение было истинным, один или оба из A или B должны быть ложными, поскольку, если бы они оба были истинными, тогда соединение A и B было бы истинным, что делает его отрицание ложным. Таким образом, один (как минимум) или более из A и B должны быть ложными (или, что то же самое, одно или несколько из «не A» и «not B» должны быть истинными). Это можно записать прямо как,

${\displaystyle (\neg A)\lor (\neg B).}$

Представленный на английском языке, это следует логике, что «поскольку неверно, что две вещи обе истинны, по крайней мере одна из них должна быть ложной».

Снова работая в противоположном направлении, второе выражение утверждает, что по крайней мере одно из «не А» и «не В» должно быть истинным, или, что то же самое, что хотя бы одно из А и В должно быть ложным. Поскольку хотя бы один из них должен быть ложным, их соединение также будет ложным. Таким образом, отрицание указанной конъюнкции приводит к истинному выражению, и это выражение идентично первому утверждению.

Формальное доказательство

Здесь мы используем ${\displaystyle A^{\complement }}$для обозначения дополнения к A. Доказательство того, что ${\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}$ выполняется в 2 этапа путем доказательства обоих ${\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }}$ и ${\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }}$.

Часть 1

Позволять ${\displaystyle x\in (A\cap B)^{\complement }}$. Потом, ${\displaystyle x\not \in A\cap B}$.

Потому что ${\displaystyle A\cap B=\{\,y\ |\ y\in A\wedge y\in B\,\}}$, должно быть так, что ${\displaystyle x\not \in A}$ или же ${\displaystyle x\not \in B}$.

Если ${\displaystyle x\not \in A}$, тогда ${\displaystyle x\in A^{\complement }}$, так ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$.

Аналогично, если ${\displaystyle x\not \in B}$, тогда ${\displaystyle x\in B^{\complement }}$, так ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$.

Таким образом, ${\displaystyle \forall x(x\in (A\cap B)^{\complement }\rightarrow x\in A^{\complement }\cup B^{\complement })}$;

то есть, ${\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }}$.

Часть 2

Чтобы доказать обратное направление, пусть ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$, и от противного полагаем ${\displaystyle x\not \in (A\cap B)^{\complement }}$.

При таком предположении должно быть так, что ${\displaystyle x\in A\cap B}$,

из этого следует, что ${\displaystyle x\in A}$ и ${\displaystyle x\in B}$, и поэтому ${\displaystyle x\not \in A^{\complement }}$ и ${\displaystyle x\not \in B^{\complement }}$.

Однако это означает ${\displaystyle x\not \in A^{\complement }\cup B^{\complement }}$, что противоречит гипотезе о том, что ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$,

следовательно, предположение ${\displaystyle x\not \in (A\cap B)^{\complement }}$ не должно быть так, а это означает, что ${\displaystyle x\in (A\cap B)^{\complement }}$.

Следовательно, ${\displaystyle \forall x(x\in A^{\complement }\cup B^{\complement }\rightarrow x\in (A\cap B)^{\complement })}$,

то есть, ${\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }}$.

Вывод

Если ${\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }}$ и ${\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }}$, тогда ${\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}$; это завершает доказательство закона Де Моргана.

Другой закон Де Моргана, ${\displaystyle (A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }}$, доказывается аналогично.

Обобщение двойственности Де Моргана

Законы Де Моргана в виде схемы с логическими вентилями

В расширениях классической логики высказываний двойственность все еще сохраняется (то есть для любого логического оператора всегда можно найти его двойственный), поскольку при наличии тождеств, управляющих отрицанием, всегда можно ввести оператор, который является двойственным по Де Моргану к еще один. Это приводит к важному свойству логики, основанной на классическая логика, а именно наличие отрицание нормальных форм: любая формула эквивалентна другой формуле, где отрицание применяется только к нелогическим атомам формулы. Существование нормальных форм отрицания движет многими приложениями, например, в цифровая схема дизайн, где он используется для управления типами логические ворота, и в формальной логике, где нужно найти конъюнктивная нормальная форма и дизъюнктивная нормальная форма формулы. Компьютерные программисты используют их для упрощения или устранения сложных логические условия. Они также часто полезны при вычислениях в элементарных теория вероятности.

Определим двойственный к любому пропозициональному оператору P (п, q, ...) в зависимости от элементарных предложений п, q, ... быть оператором ${\displaystyle {\mbox{P}}^{d}}$ определяется

${\displaystyle {\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).}$

Расширение предикатов и модальной логики

Эта двойственность может быть обобщена на кванторы, например, универсальный квантор и экзистенциальный квантор двойные:

${\displaystyle \forall x\,P(x)\equiv \neg [\exists x\,\neg P(x)]}$

${\displaystyle \exists x\,P(x)\equiv \neg [\forall x\,\neg P(x)]}$

Чтобы связать эти количественные двойственности с законами Де Моргана, создайте модель с небольшим количеством элементов в своей области D, Такие как

D = {а, б, c}.

потом

${\displaystyle \forall x\,P(x)\equiv P(a)\land P(b)\land P(c)}$

и

${\displaystyle \exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).}$

Но, используя законы Де Моргана,

${\displaystyle P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))}$

и

${\displaystyle P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),}$

проверка двойственности кванторов в модели.

Затем кванторные двойственности могут быть расширены до модальная логика, связывая операторы прямоугольника ("обязательно") и ромба ("возможно"):

${\displaystyle \Box p\equiv \neg \Diamond \neg p,}$

${\displaystyle \Diamond p\equiv \neg \Box \neg p.}$

В своем приложении к алетические методы возможности и необходимости, Аристотель наблюдал этот случай, а в случае нормальная модальная логика, связь этих модальных операторов с количественной оценкой можно понять, настроив модели с использованием Семантика Крипке.

Смотрите также

• Изоморфизм - Оператор НЕ как изоморфизм между положительной и отрицательной логикой
• Список тем по булевой алгебре
• Список установленных идентичностей и отношений
• Позитивная логика

Рекомендации

1. Копи и Коэн^{[требуется полная цитата ]}
2. Херли, Патрик Дж. (2015), Краткое введение в логику (12-е изд.), Cengage Learning, ISBN  978-1-285-19654-1
3. Мур и Паркер^{[требуется полная цитата ]}
4. Хейс, Энди; Ву, Винсент. "Законы Де Моргана". https://brilliant.org/. Внешняя ссылка в | сайт = (помощь)
5. Булева алгебра Р. Л. Гудштейна. ISBN  0-486-45894-6
6. 2000 Решенные проблемы цифровой электроники С. П. Бали
7. Теоремы ДеМоргана на mtsu.edu
8. Бохенского История формальной логики
9. Уильям Оккам, Summa Logicae, часть II, разделы 32 и 33.
10. Жан Буридан, Summula de Dialectica. Пер. Дьюла Клима. Нью-Хейвен: издательство Йельского университета, 2001. См., В частности, трактат 1, главу 7, раздел 5. ISBN  0-300-08425-0
11. Огастес де Морган (1806–1871) В архиве 2010-07-15 на Wayback Machine Роберт Х. Орр

внешняя ссылка

• «Принцип двойственности», Энциклопедия математики, EMS Press, 2001 [1994]
• Вайсштейн, Эрик В. "Законы де Моргана". MathWorld.
• законы де Моргана в PlanetMath.
• Двойственность в логике и языке, Интернет-энциклопедия философии.