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

Из Википедије, слободне енциклопедије

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

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

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

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

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

такође и,

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

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

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

где је:

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

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

Формални запис[уреди]

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

\neg(P \and Q) \vdash (\neg P \or \neg Q)

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

\neg(P \or Q) \vdash (\neg P \and \neg Q)

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

\frac{\neg (P \and Q)}{\therefore \neg P \or \neg Q}

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

\frac{\neg (P \or Q)}{\therefore \neg P \and \neg Q}

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

\neg (P \and Q) \to (\neg P \or \neg Q)
\neg (P \or Q) \to (\neg P \and \neg Q)

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

Форма замене[уреди]

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

(P \and Q) \equiv \neg (\neg P \or \neg Q)
(P \or Q) \equiv \neg (\neg P \and \neg Q)

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

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

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

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

где је:

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

\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 ed.), 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.
  • Dahn B. I. (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 .
  • Halmos Paul (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 .
  • Huntington E. V. (1933), „New sets of independent postulates for the algebra of logic“, Transactions of the American Mathematical Society (American Mathematical Society) 35 (1): 274-304, DOI:10.2307/1989325, JSTOR 1989325 .
  • Huntington E. V. (1933), „Boolean algebra: A correction“, Transactions of the American Mathematical Society (American Mathematical Society) 35 (2): 557-558, DOI:10.2307/1989783, JSTOR 1989783 .
  • Mendelson Elliott (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, ed. (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 .
  • Sikorski Roman (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag .
  • Stoll R. R. (1963), Set Theory and Logic, W. H. Freeman, Reprinted by Dover Publications, 1979., ISBN 978-0-486-63829-4 .

Спољашње везе[уреди]