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:

$\overline{A\cup B}=\bar{A}\cap \bar{B}$

$\overline{A\cap B}=\bar{A}\cup \bar{B}$

non

• $A$ eta $B$ multzoak dira.
• $\bar{A}$ $A$ multzoaren osagarria da.
• $\cup$ bildura da.
• $\cap$ ebakidura da.

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

$\mathrm{\neg }(P\wedge Q)⟺(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$

$\mathrm{\neg }(P\vee Q)⟺(\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$

non

• ¬ ukapenaren eragile logikoa da (EZ)
• $\wedge$ konjuntzioaren eragile logikoa da (ETA)
• $\vee$ 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:

$\mathrm{\neg }(A\vee B)$

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

$(\mathrm{\neg }A)\wedge (\mathrm{\neg }B)$

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:

$\mathrm{\neg }(A\wedge B)$

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:

$(\mathrm{\neg }A)\vee (\mathrm{\neg }B)$

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 $A^c$ $A$-ren osagarria adierazteko. $(A\cap B{)}^c=A^c\cup B^c$ dela frogatzeko, bi pausutan frogatu behar da:

Lehengo pausua:

$(A\cap B{)}^c\subseteq A^c\cup B^c$ dela frogatu behar da.

Hartuko dugu $x\in (A\cap B{)}^c$, hortaz $x\in ̸A\cap B$. Definizioz, $A\cap B=\{x|x\in A\text{ eta }x\in B\}$ denez, orduan $x\in ̸A$ edo $x\in ̸B$ izan behar da:

$x\in ̸A$ bada, orduan $x\in A^c$, eta hortaz $x\in A^c\cup B^c$.

$x\in ̸B$ bada, orduan $x\in B^c$, eta hortaz $x\in A^c\cup B^c$.

Hau orokorrean egia denez edozein $x\in (A\cap B{)}^c$, orduan $\mathrm{\forall }x\in (A\cap B{)}^c,x\in A^c\cup B^c$, eta hortaz $(A\cap B{)}^c\subseteq A^c\cup B^c$.

Bigarren pausua:

$(A\cap B{)}^c\supseteq A^c\cup B^c$ dela frogatzea falta da.

Honetarako absurdura eramanez suposatu behar da $x\in A^c\cup B^c$, baina $x\in ̸(A\cap B{)}^c$.

$x\in ̸(A\cap B{)}^c$ denez, orduan $x\in A\cap B$ $⟹$ $x\in A$ eta $x\in B$ $⟹$ $x\in ̸A^c$ eta $x\in ̸B^c$ $⟹$ $x\in ̸A^c\cup B^c$.

Azken adierazpen hau kontraesan bat da, hipotesia $x\in A^c\cup B^c$ baitzen.

Hortaz, $\mathrm{\forall }x\in A^c\cup B^c,x\in (A\cap B{)}^c$, eta $A^c\cup B^c\subseteq (A\cap B{)}^c$.

Ondorioa:

$A^c\cup B^c\subseteq (A\cap B{)}^c$ eta $(A\cap B{)}^c\subseteq A^c\cup B^c$ direnez, orduan egia da $(A\cap B{)}^c=A^c\cup B^c$.

De Morganen beste legea, $(A\cup B{)}^c=A^c\cap B^c$, modu oso antzekoan frogatzen da.

Notazio formala

Konjuntzioaren ukazioaren araua ondorengo notazioan idatz daiteke:

$\mathrm{\neg }(P\wedge Q)⊢(\mathrm{\neg }P\vee \mathrm{\neg }Q)$

Disjuntzioa ukatzeko araua modu honetan idatz daiteke:

$\mathrm{\neg }(P\vee Q)⊢(\mathrm{\neg }P\wedge \mathrm{\neg }Q)$

Erregela moduan: konjuntzioaren ukapena

$\frac{\mathrm{\neg }(P\wedge Q)}{\therefore \mathrm{\neg }P\vee \mathrm{\neg }Q}$

eta disjuntzioaren ukapena

$\frac{\mathrm{\neg }(P\vee Q)}{\therefore \mathrm{\neg }P\wedge \mathrm{\neg }Q}$

Eta egiazko tautologia edo logika proposizionalaren teorema gisa adierazten da:

$\mathrm{\neg }(P\wedge Q)\to (\mathrm{\neg }P\vee \mathrm{\neg }Q)$

$\mathrm{\neg }(P\vee Q)\to (\mathrm{\neg }P\wedge \mathrm{\neg }Q)$

non P eta Q donde $P$, y $Q$ 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.

$\frac{P\wedge Q}{\mathrm{\neg }(\mathrm{\neg }P\vee \mathrm{\neg }Q)}$

Disjuntzioa

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

$\frac{P\vee Q}{\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q)}$

Operadoreen ukazioak juntagailu eta disjuntzioetan

P ukatuarekin konjuntzioa

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

$\frac{\mathrm{\neg }P\wedge Q}{\mathrm{\neg }(P\vee \mathrm{\neg }Q)}$

Q ukatuarekin konjuntzioa

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

$\frac{P\wedge \mathrm{\neg }Q}{\mathrm{\neg }(\mathrm{\neg }P\vee Q)}$

Ukatutako P zein Q -ren konjuntzioa

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

$\frac{\mathrm{\neg }P\wedge \mathrm{\neg }Q}{\mathrm{\neg }(P\vee Q)}$

P ukatuarekin disjuntzioa

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

$\frac{\mathrm{\neg }P\vee Q}{\mathrm{\neg }(P\wedge \mathrm{\neg }Q)}$

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

$\frac{\mathrm{\neg }(P\vee Q)}{\mathrm{\neg }(\mathrm{\neg }P\to Q)}$

Q ukatuarekin disjuntzioa

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

$\frac{P\vee \mathrm{\neg }Q}{\mathrm{\neg }(\mathrm{\neg }P\wedge Q)}$

Ukatutako P zein Q -ren disjuntzioa

Ukatutako P eta Q proposamenen disjuntzioa P eta Q disjuntzioaren konjuntzioaren baliokidea da.

$\frac{\mathrm{\neg }P\vee \mathrm{\neg }Q}{\mathrm{\neg }(P\wedge Q)}$

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:

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

non:

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

Forma orokortuak honako hau da :

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

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 :

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

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

non :

• $\cdot$ ETA logikoa den
• $+$ EDO logikoa den
• Goiko barra goiko barraren azpian dagoenaren EZ logikoa den