Законы де Моргана

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

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

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

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

или же

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

или же

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

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

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

куда

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

На формальном языке правила записываются как

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

и

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

куда

• P и 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}}}$

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

В законах есть серьезный пробел по сравнению с законом двойного отрицания ( ). , чтобы стать формальной логической системой: последовательность сообщает символы, которые определены правильно сформированными в первом порядке. Та же система имеет те конъюнкции: . Очевидно, что это достоверное знание, тогда существует по крайней мере одно соединение, которое - число - в таблице истинности, базовое утверждение - равно атомарному контексту существования , конечно, в соответствии со знанием. Мы рассматривали теорию эквивалентности, логика делает. На этом этапе законы Де Моргана показывают восходящий или нисходящий эффект в атомарном контексте . ^[4]${\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}$

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

В теории множеств и булевой алгебре это часто определяется как «обмен объединением и пересечением при дополнении» ^[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 - это отрицание 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}}}$

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

В устоявшихся обозначениях законы Де Моргана можно запомнить с помощью мнемоники «разорви черту, поменяй знак». ^[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] Например, в XIV веке Вильгельм Оккам записал слова, которые должны были произойти после прочтения законов. ^[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 были истинными, то дизъюнкция A и B была бы истинной, что сделало бы его отрицание ложным. Представленный на английском языке, это следует логике, что «поскольку две вещи ложны, также неверно и то, что любая из них истинна».

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

Отрицание союза [ править ]

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

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

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

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

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

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

Формальное доказательство [ править ]

Здесь мы используем для обозначения дополнения к A. Доказательство, которое завершается в 2 шага путем доказательства обоих и . ${\displaystyle A^{\complement }}$${\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}$${\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 ( p , q , ...), зависящий от элементарных предложений p , 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 = { a , b , 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.}$

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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