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

Извор: Wikipedija
Пређи на навигацију Пређи на претрагу

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

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

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

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

"не (А и Б)" је исто што и "(не А) или (не Б)"

такође и,

"не (А или Б)" је исто што и "(не А) и (не Б)"

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

где је:

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

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

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

[уреди | уреди извор]

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

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

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

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

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

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

Форма замене

[уреди | уреди извор]

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

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

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

[уреди | уреди извор]

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

где је:

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

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

Инжењерство

[уреди | уреди извор]

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

.
.

где је:

  • логичко I
  • логичко ИЛИ
  • надвучена линија комплемент, логичко НЕ.

Историја

[уреди | уреди извор]

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

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

[уреди | уреди извор]

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

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

[уреди | уреди извор]

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

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

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

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

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

[уреди | уреди извор]

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

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

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

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

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

[уреди | уреди извор]

Да би доказали да важи , прво морамо доказати да важи , а затим .

Нека је . Онда , зато што , онда или . или . Ако , онда , из тог следи . Ако , онда , следи . Пошто је ово тачно за произвољно , онда , дакле следи .

Да би доказали у супротном смеру, претпостављамо да , такво да . Онда . Пратећи то и . Следи и . Али онда , је у контрадикцији са хипотезом . Стога, , и .

Пошто и , следи , што финализује доказ Де Моргановог закона.

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

Екстензије

[уреди | уреди извор]

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

Дефинишимо двоструку вредност било које исказне операције П(п, q, ...) у зависности од елементарних предлога п, q, ... да буде операција дефинисана као

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

D = {а, б, ц}.

онда

и

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

и

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

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

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

Повезано

[уреди | уреди извор]

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

[уреди | уреди извор]