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

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

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

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

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

"не (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}}$

где је:

• A негација од 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$ логичко И
• $+$ логичко ИЛИ
• надвучена линија комплемент, логичко НЕ.

Историја

Закон је добио име по Огастасу Де Моргану (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.\,$

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

Види још

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

Литература

• Brown Stephen, Vranesic Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd изд.), McGraw-Hill, ISBN 978-0-07-249938-4 . See Section 2.5.
• Cori Rene, Lascar Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3 . See Chapter 2.
• I., Dahn B. (1998), „Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem”, Journal of Algebra, 208 (2): 526—532, doi:10.1006/jabr.1998.7467 .
• Givant Steven, Paul Halmos (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer Science Business Media, ISBN 978-0-387-40293-2 .
• Paul, Halmos (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0 .
• Halmos Paul, Steven Givant (1998), Logic as Algebra, Dolciani Mathematical Expositions, 21, Mathematical Association of America, ISBN 978-0-88385-327-6 .
• V., Huntington E. (1933), „New sets of independent postulates for the algebra of logic”, Transactions of the American Mathematical Society, American Mathematical Society, 35 (1): 274—304, JSTOR 1989325, doi:10.2307/1989325 .
• V., Huntington E. (1933), „Boolean algebra: A correction”, Transactions of the American Mathematical Society, American Mathematical Society, 35 (2): 557—558, JSTOR 1989783, doi:10.2307/1989783 .
• Elliott, Mendelson (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw-Hill, ISBN 978-0-07-041460-0 .
• Monk J. Donald, R. Bonnet, ур. (1989), Handbook of Boolean Algebras, Elsevier, ISBN 978-0-444-87291-3 . 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.)
• Padmanabhan Ranganathan, Rudeanu Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6 .
• Roman, Sikorski (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag .
• R., Stoll R. (1963), Set Theory and Logic, W. H. Freeman, Reprinted by Dover Publications, 1979., ISBN 978-0-486-63829-4 .

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

• Hazewinkel Michiel, ур. (2001). „Duality principle”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Булова алгебра (енглески)
• Математика Булове алгебре (енглески)
• Булова алгебра и бинарна логика (српски)