De Morganovi zakoni

U matematičkoj logici i Bulovoj algebri, De Morganovi zakoni predstavljaju par transformacijskih pravila. Pravila dozvoljavaju da se izrazi konjunkcije i disjunkcije mogu menjati jedan u drugi uz pomoć negacije.

Pravila mogu biti predstavljena u našem jeziku kao:

Negacija konjunkcije predstavlja disjunkciju negacija. Negacija disjunkcije predstalja konjunkciju negacija.

ili neformalno:

"ne (A i B)" je isto što i "(ne A) ili (ne B)"

takođe i,

"ne (A ili B)" je isto što i "(ne A) i (ne B)"

Pravila mogu biti izražena u formalnom jeziku , sa dve istinitosne promenljive P i Q kao:

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

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

gde je:

• ¬ operator negacije (NE)
• $\land$ operator konjunkcije (I)
• $\lor$ operator disjunkcije (ILI)
• ⇔ relacija ekvivalencije (AKKO)

Ova pravila imaju široku primenu u pojednostavljivanju logičkih izraza u računarskim programima, kao i u digitalnim kolima. De Morganovi zakoni su opšti primer pojma dualnosti u matematici.

Formalni zapis

Pravilo negacije konjunkcije može biti napisano na sledeći način:

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

dok pravilo negacije disjunkcije može biti napisano kao:

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

U pravlinoj formi: negacije konjunkcije

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

i negacije disjunkcije

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

Iskazano preko iskazne formule:

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

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

gde $P$ i $Q$ predstavljaju logičke promenljive izražene u formalnom zapisu.

Forma zamene

De Morganovi zakoni se obično prikazuju u kompaktnom obliku, sa negacijom kompletne leve strane, odnosno negiranjem ulaza na desnoj strani. Jasniji obrazac za zamenu se može zapisati:

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

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

Ovakav zapis naglašava da je pri zameni iz konjunktivne u disjunktivnu formu, odnosno obrnuto, potrebno inverovati izlaz, sve ulaze, kao i promeniti opeatore.

U teoriji skupova i Bulovoj algebri

U teoriji skupova i Bulovoj algebri, često se nailazi na uniju i presek pod komplementom, gde takođe imaju promenu De Morganovi zakoni, što se može zapisati:

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

gde je:

• A negacija od A
• ∩ presek skupova(I)
• ∪ unija skupova (ILI)

Ili u uopštenoj formuli:

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

Gde I predstavlja beskonačan brojač. U određenom zapisu, De Morganove zakone je najlakše pamtiti pomoću mnemonika „Probij liniju, promeni znak“.

Inženjerstvo

U elektrotehnici, De Morganovi zakoni se obično zapisuju:

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

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

gde je:

• $\cdot$ logičko I
• $+$ logičko ILI
• nadvučena linija komplement, logičko NE.

Istorija

Zakon je dobio ime po Ogastasu De Morganu (1806—1871) koji je uveo zvaničnu verziju zakona o klasičnoj propozicionalnoj logici. Na De Morganovu formulaciju je uticala algebarizacija logike koju je izveo Džordž Bul, koja je kasnije učvrstila De Morganovu tvrdnju. Iako je slično zapažanje imao Aristotel i bila je poznata Grcima i srednjovekovnim logičarima, De Morganu je data zasluga za formalno navođenje zakona i njihovo uvođenje u jezik logike. De Morganov zakon se može lako dokazati, i može čak izgledati trivijalno. Ipak, ovi zakoni su od pomoći u donošenju ispravnih zaključaka u dokazima i deduktivnim argumentima.

Neformalni dokaz

De Morganovi zakoni mogu biti primenjeni na kompletan izraz negacije disjunkcije ili negacije konjunkcije, kao i na neki deo njega.

Negacija disjunkcije

U slučaju primene De Morganovog zakona na disjunkciju, razmotrimo sledeću tvrdnju: „Nije tačno da su A ili B tačni iskazi“, što možemo zapisati :

$\neg (A\lor B)$

U tom slučaju utvrđeno je da istinitnosni iskaz A ili B nije tačan, što znači da ni A nije tačno, ni B nije tačno, što može biti zapisano:

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

Da je jedan od A ili B istina, njihova disjunkcija bi takođe bila istinita, što bi činilo ovu negaciju netačnom. Prezentovano na govornom jeziku, prateća logika bi bila „Ako su dve stvari netačne, takođe je netačno da je neka od njih tačna.“

Gledano u suprotnom smeru, drugi izraz nam tvrdi da ni jedan od iskaza A i V nisu tačni, što znači da nije tačna ni njihova disjunkcija. Kako je negacija disjunkcije napisana u prvom izrazu sledi da je dokaz uspešan.

Negacija konjunkcije

Primena De Morganovog zakona na konjunkciju je veoma slična sa prethodnom. Obe forme su trivijalne. Razmatraćemo sledeću tvrdnju: "Nije tačno da su i A i V tačni iskazi", što matematički možemo zapisati:

$\neg (A\land B)$

Da bi ova tvrdnja bila tačna, potrebno je da i A i B budu netačni, odnosno bar jedan od njih mora biti netačan, što može biti zapisano:

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

Odnosno, na našem jeziku "Ukoliko nije tačno da su dve stvarni tačne, onda bar jedna od njih nije tačna“.

Dokaz u suprotnom smeru je takođe trivijalan, drugi izraz predstavlja da bar jedan iskaz nije tačan. Ukoliko bar jedan nije tačan, lako se može zaključiti da njihova konjunkcija takođe nije tačna.

Formalni dokaz

Da bi dokazali da važi $(A\cap B)^{c}=A^{c}\cup B^{c}$, prvo moramo dokazati da važi $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$, a zatim $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$.

Neka je $x\in (A\cap B)^{c}$. Onda $x\not \in A\cap B$, zato što $A\cap B=\{y|y\in A{\text{ and }}y\in B\}$, onda ili $x\not \in A$. ili $x\not \in B$. Ako $x\not \in A$, onda $x\in A^{c}$, iz tog sledi $x\in A^{c}\cup B^{c}$. Ako $x\not \in B$, onda $x\in B^{c}$, sledi $x\in A^{c}\cup B^{c}$. Pošto je ovo tačno za proizvoljno $x\in (A\cap B)^{c}$, onda $\forall x\in (A\cap B)^{c},x\in A^{c}\cup B^{c}$, dakle sledi $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$.

Da bi dokazali u suprotnom smeru, pretpostavljamo da $\exists x\in A^{c}\cup B^{c}$, takvo da $x\not \in (A\cap B)^{c}$. Onda $x\in A\cap B$. Prateći to $x\in A$ i $x\in B$. Sledi $x\not \in A^{c}$ i $x\not \in B^{c}$. Ali onda $x\not \in A^{c}\cup B^{c}$, je u kontradikciji sa hipotezom $x\in A^{c}\cup B^{c}$. Stoga, $\forall x\in A^{c}\cup B^{c},x\in (A\cap B)^{c}$, i $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$.

Pošto $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ i $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$, sledi $(A\cap B)^{c}=A^{c}\cup B^{c}$, što finalizuje dokaz De Morganovog zakona.

Drugi De Morganov zakon, odnosno, da važi $(A\cup B)^{c}=A^{c}\cap B^{c}$, se dokazuje na sličan način.

Ekstenzije

Sama činjenica da svaki izraz ima svoj dualni izraz, umnogome proširuje iskaznu logiku. Postojanje negacije normalne forme umnogome pojednostavljuje kompleksnost, a samim tim i cenu, jednog digitalnog kola. Takođe, velika olakšanja nalaze i programeri koji dualni izraz koriste da pojednostave često previše komplikovane logičke uslove. Često se koriste i u proračunima u osnovnoj teoriji verovatnoće.

Definišimo dvostruku vrednost bilo koje iskazne operacije P(p, q, ...) u zavisnosti od elementarnih predloga p, q, ... da bude operacija ${\mbox{P}}^{d}$ definisana kao

${\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).$

ToDa bi povezali ove kvantifikatore sa Morganovim zakonima, postavimo model sa malim brojem elemenata u njegovom domenu D, kao npr.

D = {a, b, c}.

onda

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

i

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

Ali, koristeći De Morganove zakone

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

i

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

proveravamo kvalifikatorske dvojnosti u modelu.

Onda kvantifikatorske dvojnosti mogu biti proširene dublje u modalnu logiku, povezujući kvadratne(obavezne) i rombaste(moguće) operacije.

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

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

U ovoj aplikaciji za aletičke modalitete mogućnosti i obaveznosti, Aristotel je posmatrao ovaj slučaj i u slučaju normalne modalne logike, veza ovih modalnih operacija sa kvantifikatorima može biti razumljiva tako što se postave modeli koristeći Kripkovu semantiku.

Povezano

• Izomorfizam (matematika)

Spoljašnje veze

• Bulova algebra i binarna logika (srpski)