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

Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

Отрицание конъюнкции есть не что иное, как дизъюнкция отрицаний.

Отрицание дизъюнкции есть не что иное, как конъюнкция отрицаний.

Определение

Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:

не (a и b) = (не a) или (не b)

не (a или b) = (не a) и (не b)

В математике это выглядит так:

<math>\begin{matrix}

\neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\ \neg {(a \vee b)} = \neg{a} \wedge \neg{b} \end{matrix}</math> 000 или по-другому: 000 <math>\begin{matrix} \overline{(a \wedge b)} = \overline{a} \vee \overline{b} \\ \overline{(a \vee b)} = \overline{a} \wedge \overline{b} \end{matrix}</math>

В теории множеств:

<math>\begin{matrix}

\overline{A \cap B} = \overline{A} \cup \overline{B} \\ \overline{A \cup B} = \overline{A} \cap \overline{B} \end{matrix}</math> 000 или по-другому: 000 <math>\begin{matrix} (A\cap B)^C=A^C\cup B^C, \\ (A\cup B)^C=A^C\cap B^C. \end{matrix}</math>

Эти правила также действительны для множества элементов (семейств):

<math>\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}</math> 00000 и 00000 <math>\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}</math>.

В исчислении предикатов:

<math>\neg \forall x \, P(x) \equiv \exists x \, \neg P(x),</math>

<math>\neg \exists x \, P(x) \equiv \forall x \, \neg P(x).</math>

Следствия:

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

<math>a \wedge b = \neg(\neg{a} \vee \neg{b})</math>

<math> a \vee b = \neg(\neg{a} \wedge \neg{b})</math>

В виде теоремы:

Если существует суждение, выраженное операцией логического умножения двух или более элементов, т.е. операцией «и»: <math>{(A\wedge B)}</math>, то для того, чтобы найти обратное <math>{\neg(A \wedge B)}</math> от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, т.е. операцией «или»: <math>(\neg{A} \vee \neg{B})</math>. Закон работает аналогично в обратном направлении: <math>\neg( A \vee B) = (\neg{A} \wedge \neg{B})</math>.

Применение

Законы де Моргана применяются в таких важных областях как дискретная математика, электротехника, физика и информатика; например, используются для оптимизации цифровых схем посредством замены одних логических элементов другими.

История

• «Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения (The contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition)» (Уильям Оккам, Summa Logicae).

Ссылки

• Weisstein, Eric W. [mathworld.wolfram.com/deMorgansLaws.html Законы де Моргана] (англ.) на сайте Wolfram MathWorld.

Отрывок, характеризующий Законы де Моргана

Другая еще сильнейшая волна взмыла по народу, и, добежав до передних рядов, волна эта сдвинула переднии, шатая, поднесла к самым ступеням крыльца. Высокий малый, с окаменелым выражением лица и с остановившейся поднятой рукой, стоял рядом с Верещагиным.
– Руби! – прошептал почти офицер драгунам, и один из солдат вдруг с исказившимся злобой лицом ударил Верещагина тупым палашом по голове.
«А!» – коротко и удивленно вскрикнул Верещагин, испуганно оглядываясь и как будто не понимая, зачем это было с ним сделано. Такой же стон удивления и ужаса пробежал по толпе.
«О господи!» – послышалось чье то печальное восклицание.
Но вслед за восклицанием удивления, вырвавшимся У Верещагина, он жалобно вскрикнул от боли, и этот крик погубил его. Та натянутая до высшей степени преграда человеческого чувства, которая держала еще толпу, прорвалось мгновенно. Преступление было начато, необходимо было довершить его. Жалобный стон упрека был заглушен грозным и гневным ревом толпы. Как последний седьмой вал, разбивающий корабли, взмыла из задних рядов эта последняя неудержимая волна, донеслась до передних, сбила их и поглотила все. Ударивший драгун хотел повторить свой удар. Верещагин с криком ужаса, заслонясь руками, бросился к народу. Высокий малый, на которого он наткнулся, вцепился руками в тонкую шею Верещагина и с диким криком, с ним вместе, упал под ноги навалившегося ревущего народа.
Одни били и рвали Верещагина, другие высокого малого. И крики задавленных людей и тех, которые старались спасти высокого малого, только возбуждали ярость толпы. Долго драгуны не могли освободить окровавленного, до полусмерти избитого фабричного. И долго, несмотря на всю горячечную поспешность, с которою толпа старалась довершить раз начатое дело, те люди, которые били, душили и рвали Верещагина, не могли убить его; но толпа давила их со всех сторон, с ними в середине, как одна масса, колыхалась из стороны в сторону и не давала им возможности ни добить, ни бросить его.
«Топором то бей, что ли?.. задавили… Изменщик, Христа продал!.. жив… живущ… по делам вору мука. Запором то!.. Али жив?»
Только когда уже перестала бороться жертва и вскрики ее заменились равномерным протяжным хрипеньем, толпа стала торопливо перемещаться около лежащего, окровавленного трупа. Каждый подходил, взглядывал на то, что было сделано, и с ужасом, упреком и удивлением теснился назад.
«О господи, народ то что зверь, где же живому быть!» – слышалось в толпе. – И малый то молодой… должно, из купцов, то то народ!.. сказывают, не тот… как же не тот… О господи… Другого избили, говорят, чуть жив… Эх, народ… Кто греха не боится… – говорили теперь те же люди, с болезненно жалостным выражением глядя на мертвое тело с посиневшим, измазанным кровью и пылью лицом и с разрубленной длинной тонкой шеей.