В логике высказываний и булевой алгебре , законы Де Морган [1] [2] [3] являются парой правил преобразования , которые являются как действующими правилами вывода . Они названы в честь Августа Де Моргана , британского математика 19 века. Правила позволяют выражать союзы и дизъюнкции исключительно в терминах друг друга через отрицание .
Правила могут быть выражены на английском языке как:
- отрицание дизъюнкции - это соединение отрицаний
- отрицание конъюнкции - дизъюнкция отрицаний
или же
- дополнение к объединению двух множеств совпадают с пересечением их комплементов
- дополнение пересечения двух множеств такое же, как объединение их дополнений
или же
- not (A или B) = не A и не B
- not (A и B) = не A или не B.
В теории множеств и булевой алгебре они формально записываются как
где
- а также наборы,
- является дополнением ,
- это пересечение , а
- это союз .
На формальном языке правила записываются как
а также
где
- P и Q суть предложения,
- - логический оператор отрицания (НЕ),
- является логическим оператором конъюнкции (И),
- - логический оператор дизъюнкции (ИЛИ),
- - металогический символ, означающий «в логическом доказательстве можно заменить на ».
Применения правил включают упрощение логических выражений в компьютерных программах и цифровых схемах. Законы Де Моргана являются примером более общей концепции математической двойственности .
Формальное обозначение
Отрицание конъюнкции правила может быть записано в секвенции записи:
- ,
а также
- .
Отрицание дизъюнкции правило можно записать в виде:
- ,
а также
- .
В форме правила : отрицание соединения
и отрицание дизъюнкции
и выражается как функциональная тавтология истинности или теорема логики высказываний:
где а также суждения, выраженные в некоторой формальной системе.
Форма замены
Законы Де Моргана обычно показаны в компактной форме выше, с отрицанием выхода слева и отрицанием входов справа. Более четкую форму замены можно сформулировать так:
Это подчеркивает необходимость инвертировать как входы, так и выходы, а также изменять оператор при выполнении подстановки.
В законах есть важный пробел по отношению к () закон двойного отрицания. , чтобы стать формальной логической системой: Последовательность сообщает символы, которые определены правильно сформированными в первом порядке. В той же системе есть такие союзы:. Очевидно, действительно знание, то есть хотя бы один соединение, которое - число - в таблице истинности, основное утверждение - равно атомарному контексту существования , конечно, согласно знание. Мы рассматривали теорию эквивалентности, логика делает. На этом этапе законы Де Моргана показывают восходящий или нисходящий эффект, атомарный контекст. [4]
Теория множеств и булева алгебра
В теории множеств и булевой алгебре это часто определяется как «обмен объединением и пересечением при дополнении» [5], который формально можно выразить как:
где:
- это отрицание , надчеркнутый над отрицательными терминами,
- - оператор пересечения (И),
- является оператором объединения (ИЛИ).
Бесконечные союзы и пересечения
Обобщенная форма
где I - некоторый, возможно, неисчислимый набор индексации.
В устоявшихся обозначениях законы Де Моргана можно запомнить с помощью мнемоники «разорви черту, поменяй знак». [6]
Инженерное дело
В электротехнике и компьютерной инженерии законы Де Моргана обычно записываются так:
а также
где:
- это логическое И,
- это логическое ИЛИ,
- черточка является логическим НЕ о том, что находится под чертой сверху.
Текстовый поиск
Законы Де Моргана обычно применяются к поиску текста с использованием логических операторов 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 истинно», которое записывается как:
Поскольку было установлено, что ни A, ни B не истинны, из этого должно следовать, что и A не истинно, и B не истинно, что может быть записано непосредственно как:
Если бы A или B были истинными, то дизъюнкция A и B была бы истинной, что сделало бы его отрицание ложным. Представленный на английском языке, это следует логике, что «поскольку две вещи ложны, также неверно и то, что любая из них истинна».
Работая в противоположном направлении, второе выражение утверждает, что A ложно, а B ложно (или, что то же самое, что «не A» и «не B» истинны). Зная это, дизъюнкция A и B также должна быть ложной. Таким образом, отрицание указанной дизъюнкции должно быть истинным, и результат идентичен первому утверждению.
Отрицание союза
Применение теоремы Де Моргана к конъюнкции очень похоже на ее применение к дизъюнкции как по форме, так и по обоснованию. Рассмотрим следующее утверждение: «неверно, что A и B истинны», которое записывается как:
Для того, чтобы это утверждение было истинным, один или оба из A или B должны быть ложными, поскольку, если бы они оба были истинными, тогда соединение A и B было бы истинным, что делает его отрицание ложным. Таким образом, один (по крайней мере) или несколько из A и B должны быть ложными (или, что то же самое, одно или несколько из «not A» и «not B» должны быть истинными). Это можно записать прямо как,
Представленный на английском языке, это следует логике, что «поскольку неверно, что две вещи обе верны, по крайней мере одна из них должна быть ложной».
Снова работая в противоположном направлении, второе выражение утверждает, что по крайней мере одно из «не А» и «не В» должно быть истинным, или, что то же самое, что хотя бы одно из А и В должно быть ложным. Поскольку хотя бы один из них должен быть ложным, их соединение также будет ложным. Таким образом, отрицание указанной конъюнкции приводит к истинному выражению, и это выражение идентично первому утверждению.
Формальное доказательство
Здесь мы используем для обозначения дополнения к A. Доказательство того, что выполняется в 2 этапа, доказывая оба а также .
Часть 1
Позволять . Потом,.
Так как , должно быть так, что или же .
Если , тогда , так .
Аналогично, если , тогда , так .
Таким образом, ;
это, .
Часть 2
Чтобы доказать обратное направление, пусть , и от противного полагаем .
При таком предположении должно быть так, что ,
из этого следует, что а также , и поэтому а также .
Однако это означает , что противоречит гипотезе о том, что ,
следовательно, предположение не должно быть так, а это означает, что .
Следовательно, ,
это, .
Заключение
Если а также , тогда ; на этом завершается доказательство закона Де Моргана.
Другой закон Де Моргана, , доказывается аналогично.
Обобщение двойственности Де Моргана
В расширениях классической логики высказываний двойственность все еще сохраняется (то есть для любого логического оператора всегда можно найти его двойственный), поскольку при наличии тождеств, управляющих отрицанием, всегда можно ввести оператор, который является двойственным по Де Моргану к оператору Другой. Это приводит к важному свойству логики, основанной на классической логике , а именно к существованию нормальных форм отрицания : любая формула эквивалентна другой формуле, где отрицание применяется только к нелогическим атомам формулы. Существование отрицания нормальных форм приводов много приложений, например , в цифровой схеме конструкции, где он используется для манипулирования типов логических вентилей , и в формальной логике, где это необходимо , чтобы найти конъюнктивную нормальную форму и дизъюнктивную нормальную форму о наличии формула. Компьютерные программисты используют их для упрощения или правильного отрицания сложных логических условий . Они также часто используются при вычислениях в элементарной теории вероятностей .
Пусть определяется двойственный оператор любого пропозиционального оператора P ( p , q , ...), зависящий от элементарных предложений p , q , ..., как оператор определяется
Расширение предикатов и модальной логики
Эта двойственность может быть обобщена на кванторы, так, например, универсальный квантор и экзистенциальный квантор двойственны:
Чтобы связать эти кванторные двойственности с законами Де Моргана, создайте модель с небольшим количеством элементов в ее области D , например
- D = { a , b , c }.
потом
а также
Но, используя законы Де Моргана,
а также
проверка двойственности кванторов в модели.
Затем двойственность кванторов может быть расширена до модальной логики , связывая операторы прямоугольника («обязательно») и ромба («возможно»):
Применительно к алетическим модальностям возможности и необходимости Аристотель наблюдал этот случай, а в случае нормальной модальной логики связь этих модальных операторов с количественной оценкой можно понять, установив модели с использованием семантики Крипке .
Смотрите также
- Изоморфизм - оператор НЕ как изоморфизм между положительной и отрицательной логикой
- Список тем по булевой алгебре
- Список установленных идентичностей и отношений
- Позитивная логика
Рекомендации
- ^ Копи и Коэн [ требуется полная ссылка ]
- ^ Херли, Патрик Дж. (2015), Краткое введение в логику (12-е изд.), Cengage Learning, ISBN 978-1-285-19654-1
- ^ Мур и Паркер [ требуется полная ссылка ]
- ^ Хейс, Энди; Ву, Винсент. «Законы Де Моргана» . https://brilliant.org/ . Внешняя ссылка в
|website=
( помощь ) - ^ Булева алгебра Р. Л. Гудштейна. ISBN 0-486-45894-6
- ^ 2000 Решенные проблемы цифровой электроники SP Bali
- ^ Теоремы ДеМоргана на mtsu.edu
- ^ Бохенской в истории формальной логики
- ^ Уильям Оккам, Summa Logicae , часть II, разделы 32 и 33.
- ^ Жан Буридан, Summula de Dialectica . Пер. Дьюла Клима. Нью-Хейвен: Издательство Йельского университета, 2001. См., В частности, Трактат 1, Глава 7, Раздел 5. ISBN 0-300-08425-0
- ↑ Огастес Де Морган (1806–1871). Архивировано 15 июля 2010 г. в Wayback Machine Робертом Х. Орром.
Внешние ссылки
- "Принцип двойственности" , Энциклопедия математики , EMS Press , 2001 [1994]
- Вайсштейн, Эрик В. «Законы де Моргана» . MathWorld .
- законы де Моргана в PlanetMath .
- Двойственность в логике и языке , Интернет-энциклопедия философии .