WikiDer > Законы де Моргана - Википедия

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

В логика высказываний и Булева алгебра, Законы де Моргана^[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}}}$

куда

• А и 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 земля 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 ( нег П земля нег Q) vdash neg (П лор Q)}$.

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

${ displaystyle { frac { neg (P land Q)} { следовательно neg P lor neg Q}}}$

${ displaystyle { frac { neg P lor neg Q} { следовательно neg (P land Q)}}}$

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

${ displaystyle { frac { neg (P lor Q)} { поэтому neg P land neg Q}}}$

${ displaystyle { frac { neg P land neg Q} {, следовательно, neg (P lor Q)}}}$

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

${ Displaystyle { begin {align} 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 {align}}}$

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

Форма замены

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

${ displaystyle { begin {align} (P land Q) & Longleftrightarrow neg ( neg P lor neg Q), (P lor Q) & Longleftrightarrow neg ( neg P land neg Q). end {выровнен}}}$

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

В законах есть важный пробел по отношению к (${ Displaystyle neg ( neg p) iff p}$) закон двойного отрицания. ${ Displaystyle mathbb {L}}$, чтобы стать формальной логической системой: ${ displaystyle p, q, r, ...., emptyset in mathbb {L} }$ Последовательность сообщает символы, которые определены правильно сформированными в первом порядке. В той же системе есть эти соединения: ${ Displaystyle C_ {| j}: x | x в наборе :: { land, lor, iff, vdash }}$. Очевидно, ${ Displaystyle C_ {| j} = набор, 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 {align} { overline {A cup B}} & = { overline {A}} cap { overline {B}}, { overline {A cap B}} & = { overline {A}} cup { overline {B}}, end {align}}}$

куда:

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

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

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

${ displaystyle { begin {align} { 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 {выравнивается} }}$

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

В устоявшихся обозначениях законы Де Моргана можно запомнить с помощью мнемонический «разорвать черту, поменять знак».^[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) клин ( 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. Доказательство того, что ${ displaystyle (A cap B) ^ { complement} = A ^ { complement} чашка B ^ { complement}}$ выполняется в 2 этапа путем доказательства обоих ${ Displaystyle (А крышка В) ^ { комплемент} подстек А ^ { дополнение} чашка В ^ { комплемент}}$ и ${ Displaystyle А ^ { комплемент} чашка В ^ { комплемент} substeq (А крышка В) ^ { комплемент}}$.

Часть 1

Позволять ${ Displaystyle х в (А крышка В) ^ { комплемент}}$. Потом, ${ displaystyle x not in A cap B}$.

Потому что ${ Displaystyle А крышка В = {, у | у в А клин у в В , }}$, должно быть так, что ${ Displaystyle х not in A}$ или же ${ Displaystyle х not in B}$.

Если ${ Displaystyle х not in A}$, тогда ${ Displaystyle х в А ^ { дополнение}}$, так ${ Displaystyle х в А ^ { комплемент} чашка В ^ { комплемент}}$.

Аналогично, если ${ Displaystyle х not in B}$, тогда ${ Displaystyle х в В ^ { дополнение}}$, так ${ Displaystyle х в А ^ { комплемент} чашка В ^ { комплемент}}$.

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

то есть, ${ Displaystyle (A cap B) ^ { complement} substeq A ^ { complement} чашка B ^ { complement}}$.

Часть 2

Чтобы доказать обратное направление, пусть ${ Displaystyle х в А ^ { комплемент} чашка В ^ { комплемент}}$, и от противного полагаем ${ Displaystyle х не в (A cap B) ^ { complement}}$.

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

из этого следует, что ${ displaystyle x in A}$ и ${ displaystyle x in B}$, и поэтому ${ Displaystyle х не в А ^ { дополнение}}$ и ${ Displaystyle х не в В ^ { дополнение}}$.

Однако это означает ${ Displaystyle х не в А ^ { комплемент} чашка В ^ { комплемент}}$, что противоречит гипотезе о том, что ${ Displaystyle х в А ^ { комплемент} чашка В ^ { комплемент}}$,

следовательно, предположение ${ Displaystyle х не в (A cap B) ^ { complement}}$ не должно быть так, а это означает, что ${ Displaystyle х в (А крышка В) ^ { комплемент}}$.

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

то есть, ${ Displaystyle А ^ { комплемент} чашка В ^ { комплемент} substeq (А крышка В) ^ { комплемент}}$.

Вывод

Если ${ Displaystyle А ^ { комплемент} чашка В ^ { комплемент} substeq (А крышка В) ^ { комплемент}}$ и ${ Displaystyle (А крышка В) ^ { комплемент} подстек А ^ { дополнение} чашка В ^ { комплемент}}$, тогда ${ displaystyle (A cap B) ^ { complement} = A ^ { complement} чашка B ^ { complement}}$; это завершает доказательство закона Де Моргана.

Другой закон Де Моргана, ${ Displaystyle (A чашка 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 х , п (х) эквив нег [ существует х , нег Р (х)]}$

${ Displaystyle существует х , п (х) эквив нег [ forall х , нег Р (х)]}$

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

D = {а, б, c}.

потом

${ Displaystyle forall х , п (х) эквив Р (а) земля Р (б) земля Р (с)}$

и

${ Displaystyle существует Икс , Р (Икс) Эквив Р (а) лор Р (б) лор Р (с).}$

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

${ Displaystyle P (a) земля P (b) земля P (c) эквив neg ( neg P (a) lor neg P (b) lor neg P (c))}$

и

${ Displaystyle П (а) лор П (б) лор Р (с) эквив нег ( нег Р (а) земля нег Р (б) земля нег Р (с)),}$

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

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

${ Displaystyle Коробка п эквив Нег Алмаз Нег р,}$

${ Displaystyle Бриллиант п эквив Нег Коробка Нег р.}$

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

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

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

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

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

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