De Morganen legeak

Logika proposizionalean eta Booleren aljebran De Morganen legeak bi transformazio arau dira, biak izanda inferentzia arau baliodunak. Augustus De Morganengatik izendatzen dira, XIX. mendeko britainiar matematikaria. Arauek aukera ematen dute konjuntzioak eta disjuntzioak bestearen arabera adierazteko ukapenen bidez.

Euskaraz arauak horrela adierazi daitezke:

 Konjuntzioaren ukapena ukapenen disjuntzioa da.
 Disjuntzioaren ukapena ukapenen konjuntzioa da.

edo bestela esanda:

 ez (A eta B) = (ez A) edo (ez B)
 ez (A edo B) = (ez A) eta (ez B)

Multzo-teorian eta Booleren aljebran horrela adierazten dira:

non

  eta  multzoak dira.
   multzoaren osagarria da.
  bildura da.
  ebakidura da.

Lenguai formalean horrela adierazi ahal dira P eta Q proposizioen bidez:

non

 ¬ ukapenaren eragile logikoa da (EZ)
  konjuntzioaren eragile logikoa da (ETA)
   disjuntzioaren eragile logikoa da (EDO)
 ⇔ "baldin eta soilik baldin" esanahia du

Froga informala

Disjuntzio baten ukapena 
Disjuntzio bati aplikatzerakoan, hurrengo baieztapena hartu: "gezurra da A edo B-tako bat egia dela", honela idazten dena: 

Ez A ez B egia ez direla ezarri dugunez, orduan A ez da egia eta B ez da egia, honela idatz daitekeena:

A edo B egia izango balira, orduan A eta B-ren disjuntzioa egia izango litzateke, bere ukapena gezurra eginez. Euskaraz esanda, logika hau jarraitzen du: "bi gauza egiazkoak direla gezurra denez, horietako batek gutxienez faltsua izan behar du. "

Kontrako norabidean lan eginez, bigarren adierazpenak dio A gezurra dela eta B gezurra dela (edo, beste modu batera esanda "ez B" eta "ez A" egia direla). Hau jakinda, A eta B-ren disjuntzioa gezurra da ere bai. Disjuntzio honen ukapena egia izan behar da orduan, eta bere emaitza lehenengo baieztapenaren berdina da.

Konjuntzio baten ukapena 
De Morganen teorema konjuntzio bati aplikatzea disjuntzio bati aplikatzearen oso antzekoa da, bai forman bai arrazoiketan. Hurrengo baieztapena kontsidera dezagun, "gezurra da A eta B biak egiazkoak direla", hau da:

Baieztapen hau egia izateko A eta B biak faltsuak izan behar dira, edo biak egiazkoak balira, A eta B-ren konkuntzioa egia izango litzateke, bere ukapena gezurra eginez. Hortaz, A eta B bietako bat edo gehiago gezurra izan behar da (edo, beste modu batera esanda, "ez A" eta "ez B" bietako bat eso gehiago egia izan behar da). Hau modu honetan idatz daiteke: 

Euskaraz esanda, honek logika hau jarraitzen du "gezurra denez bi gauza egia direla, gutxienez bietako bat gezurra izan behar da".

Kontrako norabideari erreparatuz, bigarren adierazpenak dio gutxienez "ez A" edo "ez B" bietako batek egia izan behar dela, edo gutxienez bietako bat gezurra izan behar dela. Bat gutxienez gezurra izan behar denez, orduan bere konjuntzioa gezurra izango litzateke. Konjuntzio horren ukapena egiteak egiazko adierazpen batekin uzten gaitu, eta hau hasierako adierazpenaren berdina da.

Froga formala 
Orain erabiliko dugu  -ren osagarria adierazteko.  dela frogatzeko, bi pausutan frogatu behar da:

Lehengo pausua: 
 dela frogatu behar da.

Hartuko dugu , hortaz . Definizioz,  denez, orduan  edo  izan behar da:

 bada, orduan , eta hortaz . 

 bada, orduan , eta hortaz .

Hau orokorrean egia denez edozein , orduan , eta hortaz .

Bigarren pausua: 
 dela frogatzea falta da. 

Honetarako absurdura eramanez suposatu behar da , baina . 

 denez, orduan    eta    eta   .

Azken adierazpen hau kontraesan bat da, hipotesia  baitzen. 

Hortaz, , eta .

Ondorioa: 
 eta  direnez, orduan egia da .

De Morganen beste legea, , modu oso antzekoan frogatzen da.

Notazio formala 
Konjuntzioaren ukazioaren araua ondorengo notazioan idatz daiteke:

 

Disjuntzioa ukatzeko araua modu honetan idatz daiteke:

 

Erregela moduan: konjuntzioaren ukapena

 

eta disjuntzioaren ukapena

 

Eta egiazko tautologia edo logika proposizionalaren teorema gisa adierazten da:

 
 

non P eta Q donde , y  sistema formalen batean adierazitako proposamenak diren.

Ordezkatzeko modua 
Normalean, De Morganen legeak modu trinkoan agertzen dira goian aurkitzen diren bezala, ezkerreko irteera eta eskuineko sarrerarena ukatuz. Nahiz eta konjuntziorako eta disjuntziorako ordezkapen-modu argiago bat behean agertzen dena izan, hau da :

Konjuntzioa 
Bi proposizioren konjuntzioa ukatutako terminoen disjuntzioa ukatzearen baliokidea da.

Disjuntzioa 
Bi proposamenen disjuntzioa P ukatuta eta Q ukatuta dauden konjuntzioa ukatzearen baliokidea da.

Operadoreen ukazioak juntagailu eta disjuntzioetan

P ukatuarekin konjuntzioa 
Ukatutako P proposamenaren eta Q preposizioaren konjuntzioa P disjuntzioa ukatzearen eta Q ukatzearen baliokidea da.

 

Q ukatuarekin konjuntzioa

P proposamenaren eta ukatutako Q preposizioaren uztarketa P eta Q ukapenaren disjuntzioa ukatzearen baliokidea da.

 

Ukatutako P zein Q -ren konjuntzioa

Ukatutako P eta Q proposamenen konjuntzioa< P eta Q disjuntzioa ukatzearen baliokidea da.

 

P ukatuarekin disjuntzioa

Ukatutako P proposamenaren disjuntzioa eta Q preposizioa P konjuntzioaren ukazioaren eta Q ukazioaren baliokideak dira.

 

Forma hori P terminoa ukatzearen eta Q terminoa ukatzearen baliokidea ere bada.

 

Q ukatuarekin disjuntzioa

P proposamenaren disjuntzioa eta Q preposizio ukatua P eta Q ukapenaren konjuntzioa ukatzearen baliokideak dira.

Ukatutako P zein Q -ren disjuntzioa 
Ukatutako P eta Q proposamenen disjuntzioa P eta Q disjuntzioaren konjuntzioaren baliokidea da.

 

Horrek agerian uzten du sarreretan eta irteeretan esku hartzeko beharra, bai eta operadorea aldatzeko beharra ere, ordezkapen bat eginez.

Multzoen teoria eta Boole-ren aljebra 
Multzoen teoria eta Boole-ren aljebran, maiz "lotura eta intersekzioa trukatzea osagarriaren azpian" gisa adierazi ohi da, formalki honela adieraz daitekeena:

 
 

non:

  A-ren ukapena den (goiko lerroa ukatzen diren gaien gainean idatzita dago)
 https://wikimedia.org/api/rest_v1/media/math/render/svg/9d4e886e6f5a28a33e073fb108440c152ecfe2d3 ebaketa operadorea den (ETA)
  bilketa operadorea den (EDO)

Forma orokortuak honako hau da :

non I Multzo indexatua den, agian ez zenbakigarria.

De Morgan-en legeak arau nemoteknikoa-ren bitartez gogoratu daitezke, honako hau diona : "Lerroa hautsi, zeinua aldatu".

Ingenieritza 
Ingenieritza elektroniko eta informatikan, De Morganen legeak modu honetan idatzi ohi dira : 

 

non :

  ETA logikoa den
  EDO logikoa den
 Goiko barra goiko barraren azpian dagoenaren EZ logikoa den

Erreferentziak

Kanpo estekak 

Logika matematikoa
Dualtasun-teoriak