Де Морганови закони

Правилото негација на конјункција може да биде напишано на следниот начин:

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

додека правилото негација на дисјункција може да биде напишано како:

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

Во правилен облик:негација на конјункција

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

инегација на дисјункција

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

Искажано преку исказна формула:

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

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

каде ${\displaystyle P}$ и ${\displaystyle Q}$ претставуваат логички променливи изразени во формален запис.

Форма на замена

Де Моргановите закони обично се прикажуваат во компактен облик, со негација на комплетната лева страна, односно со негирање на влезот на десната страна. Појасен образец за замена може да се запише како:

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

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

Ваквиот запис нагласува дека при заменана конјуктивна во дисјунктивна форма, односно обратно, потребно е да се инвертира излезот, сите влезови, како и да се променат операторите.

Во теорија на множества и Булова алгебра

Во теоријата на множества и Буловата алгебра, често се наидува на унија и пресек под комплемент, каде исто така имаат примена Де Моргановите закони, што може да се запише како:

• ${\displaystyle {\overline {A\cup B}}\equiv {\overline {A}}\cap {\overline {B}}}$
• ${\displaystyle {\overline {A\cap B}}\equiv {\overline {A}}\cup {\overline {B}}}$

каде:

• A е негација од A
• ∩ е пресек на множества (И)
• ∪ унија на множества (ИЛИ)

Или воопштено:

${\displaystyle {\overline {\bigcap _{i\in I}A_{i}}}\equiv \bigcup _{i\in I}{\overline {A_{i}}}}$

${\displaystyle {\overline {\bigcup _{i\in I}A_{i}}}\equiv \bigcap _{i\in I}{\overline {A_{i}}}}$

Каде I претставува бесконечен бројач

Инженерство

Во електротехниката, Де Моргановите закони обично се запишуваат како:

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

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

каде:

• ${\displaystyle \cdot }$ е логичко И
• ${\displaystyle +}$ е логичко ИЛИ
• надвлечена линија е комплемент, логичко НЕ.

Законите го добиле името по Огастес де Морган (1806—1871) кој ја вовел официјалната верзија на законот за класична пропозиционална логика. На Де Моргановата формулација влијаела и алгебразацијата на логиката која ја извел Џорџ Бул, која подоцна го зацврстила Де Моргановото тврдење. Иако слично запазување имал Аристотел и им била позната на Грците и средновековните логичари, на Де Морган му била дадена заслугата за формално наведување на законите и нивно воведување во јазикот на логиката. Де Моргановиот закон може лесно да се докаже и може дури да изгледа тривијално. Сепак, овие закони се од помош при донесување исправни заклучоци во доказите и дедуктивните аргументи.

Де Моргановите закони може да се применуваат на комплетен израз негација на дисјункција или негација на конјункција, како и на некој негов дел.

Негација на дисјункција

Во случај на примена на Де Моргановиот закон на дисјункција, ќе го разгледаме следново тврдење: „Не е точно дека А или Б се точни искази“, што може да се запише како:

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

Во тој случај утврдено е дека вистиносниот исказ А или Б не е точен, што значи дека ни А не е точно, ни Б не е точно, што може да се запише како:

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

Ако еден од А или Б е вистинит, нивната дисјункција исто така би била вистинита, што би ја правело оваа негација неточна. Презентирано на говорен јазик, соодветната логика би била „Ако две нешта се неточни, исто така е неточно дека некоја од нив е точна.“

Гледано во спротивна насока, другиот израз ни тврди дека ниту еден од исказите А и Б не се точно, што значи дека не е точна ниту нивната дисјункција. Како во првиот израз е напишана негација на дисјункција, следи дека доказот е успешен.

Негација на конјункција

Примената на Де Моргановиот закон на конјункција е многу слична со претходната. Обете форми се тривијални.Ќе го разгледаме следното тврдење: „Не е точно дека А и Б се точни искази“ што математички може да се запише како:

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

За да ова тврдење биде точно, потребно е А и Б да бидат неточни, односно барем еден од нив мора да биде неточен, што може да биде запишано како:

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

Односно, на говорен јазик „Доколку не е точно дека две нешта се точни, тогаш барем едно од нив не е точно“.

Доказот во спротивен правец е исто така тривијален, вториот израз претставува дека барем еден исказ не е точен. Доколку барем еден исказ не е точен, лесно може да се заклучи дека нивната конјункција исто така не е точна:

За да се докаже дека важи ${\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}$ , прво мора да се докаже дека важи ${\displaystyle (A\cap B)^{c}\subseteq A^{c}\cup B^{c}}$ , a потоа ${\displaystyle A^{c}\cup B^{c}\subseteq (A\cap B)^{c}}$ .

Нека е ${\displaystyle x\in (A\cap B)^{c}}$ . Тогаш ${\displaystyle x\not \in A\cap B}$ , затоа што ${\displaystyle A\cap B=\{y|y\in A{\text{ and }}y\in B\}}$ , тогаш или ${\displaystyle x\not \in A}$ . или ${\displaystyle x\not \in B}$ . Ако ${\displaystyle x\not \in A}$ , тогаш ${\displaystyle x\in A^{c}}$ , од што следи ${\displaystyle x\in A^{c}\cup B^{c}}$ . Ако ${\displaystyle x\not \in B}$ , тогаш ${\displaystyle x\in B^{c}}$ , следи ${\displaystyle x\in A^{c}\cup B^{c}}$ . Бидејќи ова е точно за произволно ${\displaystyle x\in (A\cap B)^{c}}$ , тогаш ${\displaystyle \forall x\in (A\cap B)^{c},x\in A^{c}\cup B^{c}}$ , значи следи ${\displaystyle (A\cap B)^{c}\subseteq A^{c}\cup B^{c}}$ .

За да се докаже во спротивна насока, се претпоставува дека ${\displaystyle \exists x\in A^{c}\cup B^{c}}$ , такво што ${\displaystyle x\not \in (A\cap B)^{c}}$ . Тогаш ${\displaystyle x\in A\cap B}$ . Следејќи го тоа ${\displaystyle x\in A}$ и ${\displaystyle x\in B}$ . Следи ${\displaystyle x\not \in A^{c}}$ и ${\displaystyle x\not \in B^{c}}$ . Но тогаш ${\displaystyle x\not \in A^{c}\cup B^{c}}$ , е во контрадикција со хипотезата ${\displaystyle x\in A^{c}\cup B^{c}}$ . Затоа, ${\displaystyle \forall x\in A^{c}\cup B^{c},x\in (A\cap B)^{c}}$ , и ${\displaystyle A^{c}\cup B^{c}\subseteq (A\cap B)^{c}}$ .

Бидејќи ${\displaystyle A^{c}\cup B^{c}\subseteq (A\cap B)^{c}}$ и ${\displaystyle (A\cap B)^{c}\subseteq A^{c}\cup B^{c}}$ , следи ${\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}$ , што го финализира доказот на Де Моргановиот закон.

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

Самиот факт дека секој израз има свој дуален израз, во голема мера ја проширува исказната логика. Постоењето на негација на нормалната форма во голема мера ја поедноставува комплексноста, а со самото тоа и цената, на дигиталните кола. Исто така, големи олеснувања наоѓаат и програмерите кои го користат дуалниот израз за да ги поедностават често премногу комплицираните логички услови. Често се користа и во пресметките во основната теорија на веројатност.

Нека дефинираме двократна вредност на која било исказна операција 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.\,}$

Во оваа апликација за алетички модалности за можност и неопходност, Аристотел го набљудувал овој случај и во случајот на нормална модална логика, врската на овие модални оператори со квантификацијата може да се разбере така што моделите се поставуваат користејќи Крипкова семантика.

• Изоморфизам (математика)

• Хацевинкел, Михил, уред. (2001), „Duality principle“, Математичка енциклопедија, Шпрингер, ISBN 978-1556080104
• Булова алгебра (англиски)
• Математика на Булова алгебра (англиски)