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

Шаблон:Правила трансформације У математичкој логици и Буловој алгебри, Де Морганови закони представљају пар трансформацијских правила. Правила дозвољавају да се изрази конјункције и дисјункције могу мењати један у други уз помоћ негације.

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

Негација конјункције представља дисјункцију негација. Негација дисјункције предстаља конјункцију негација.

или неформално:

"не (A и B)" је исто што и "(не A) или (не B)"

такође и,

"не (A или B)" је исто што и "(не A) и (не B)"

Правила могу бити изражена у формалном језику , са две истинитосне променљиве P и Q као:

$\neg (P\land Q)\iff (\neg P)\lor (\neg Q)$

$\neg (P\lor Q)\iff (\neg P)\land (\neg Q)$

где је:

• ¬ оператор негације (НЕ)
• $\land$ оператор конјункције (И)
• $\lor$ оператор дисјункције (ИЛИ)
• ⇔ релација еквиваленције (АККО)

Ова правила имају широку примену у поједностављивању логичких израза у рачунарским програмима, као и у дигиталним колима. Де Морганови закони су општи пример појма дуалности у математици.

Формални запис

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

$\neg (P\land Q)\vdash (\neg P\lor \neg Q)$

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

$\neg (P\lor Q)\vdash (\neg P\land \neg Q)$

У правлиној форми: негације конјункције

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

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

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

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

$\neg (P\land Q)\to (\neg P\lor \neg Q)$

$\neg (P\lor Q)\to (\neg P\land \neg Q)$

где $P$ и $Q$ представљају логичке променљиве изражене у формалном запису.

Форма замене

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

$(P\land Q)\equiv \neg (\neg P\lor \neg Q)$

$(P\lor Q)\equiv \neg (\neg P\land \neg Q)$

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

У теорији скупова и Буловој алгебри

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

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

где је:

• Шаблон:Overline негација од A
• ∩ пресек скупова(И)
• ∪ унија скупова (ИЛИ)

Или у уопштеној формули:

${\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}}}$

Где I представља бесконачан бројач. У одређеном запису, Де Морганове законе је најлакше памтити помоћу мнемоника „Пробиј линију, промени знак“.

Инжењерство

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

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

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

где је:

• $\cdot$ логичко И
• $+$ логичко ИЛИ
• Шаблон:Overline комплемент, логичко НЕ.

Историја

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

Неформални доказ

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

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

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

$\neg (A\lor B)$

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

$(\neg A)\wedge (\neg B)$

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

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

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

Примена Де Моргановог закона на конјункцију је веома слична са претходном. Обе форме су тривијалне. Разматраћемо следећу тврдњу: "Није тачно да су и А и В тачни искази", што математички можемо записати:

$\neg (A\land B)$

Да би ова тврдња била тачна, потребно је да и А и Б буду нетачни, односно бар један од њих мора бити нетачан, што може бити записано:

$(\neg A)\lor (\neg B)$

Односно, на нашем језику "Уколико није тачно да су две стварни тачне, онда бар једна од њих није тачна“.

Доказ у супротном смеру је такође тривијалан, други израз представља да бар један исказ није тачан. Уколико бар један није тачан, лако се може закључити да њихова конјункција такође није тачна.

Формални доказ

Да би доказали да важи $(A\cap B)^{c}=A^{c}\cup B^{c}$, прво морамо доказати да важи $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$, a затим $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$.

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

Да би доказали у супротном смеру, претпостављамо да $\exists x\in A^{c}\cup B^{c}$, такво да $x\not \in (A\cap B)^{c}$. Онда $x\in A\cap B$. Пратећи то $x\in A$ и $x\in B$. Следи $x\not \in A^{c}$ и $x\not \in B^{c}$. Али онда $x\not \in A^{c}\cup B^{c}$, је у контрадикцији са хипотезом $x\in A^{c}\cup B^{c}$. Стога, $\forall x\in A^{c}\cup B^{c},x\in (A\cap B)^{c}$, и $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$.

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

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

Екстензије

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

Дефинишимо двоструку вредност било које исказне операције P(p, q, ...) у зависности од елементарних предлога p, q, ... да буде операција ${\mbox{P}}^{d}$ дефинисана као

${\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).$

$\forall x\,P(x)\equiv \neg \exists x\,\neg P(x),$

$\exists x\,P(x)\equiv \neg \forall x\,\neg P(x).$

ТоДа би повезали ове квантификаторе са Моргановим законима, поставимо модел са малим бројем елемената у његовом домену D, као нпр.

D = {a, b, c}.

онда

$\forall x\,P(x)\equiv P(a)\land P(b)\land P(c)$

и

$\exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).\,$

Али, користећи Де Морганове законе

$P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))$

и

$P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),$

проверавамо квалификаторске двојности у моделу.

Онда квантификаторске двојности могу бити проширене дубље у модалну логику, повезујући квадратне(обавезне) и ромбасте(могуће) операције.

$\Box p\equiv \neg \Diamond \neg p,$

$\Diamond p\equiv \neg \Box \neg p.\,$

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

Види још

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

Литература

• Шаблон:Citation. See Section 2.5.
• Шаблон:Citation. See Chapter 2.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. In 3 volumes. (Vol.1:. ISBN 978-0-444-70261-6., Vol.2:. ISBN 978-0-444-87152-7., Vol.3:. ISBN 978-0-444-87153-4.)
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.

Спољашње везе

• Шаблон:Springer
• Булова алгебра (енглески)
• Математика Булове алгебре (енглески)
• Булова алгебра и бинарна логика (српски)