De Morgans lagar

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 april 2022; kontroller kräver 4 redigeringar .

Morgens lagar (Morgens regler ) är logiska regler som kopplar ihop par av logiska operationer med hjälp av logisk negation . Uppkallad efter den skotske matematikern Augustus de Morgan . Kortfattat låter de så här:

Negationen av en konjunktion är disjunktionen av negationerna. Negationen av en disjunktion är en konjunktion av negationer.

Definition

Augustus de Morgan observerade ursprungligen att följande relationer gäller i klassisk propositionell logik :

inte (a och b) = (inte a) eller (inte b) inte (a eller b) = (inte a) och (inte b)

Symboliskt kan detta skrivas så här:

{\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \ neg {b}\end{matris}}

000eller på annat sätt:000

{\begin{matrix}\overline {(a\wedge b)}=\overline {a}\vee \overline {b}\\\overline {(a\vee b)}=\overline {a}\wedge \ överlinje {b}\end{matris}}

I mängdlära :

{\begin{matrix}\overline {A\cap B}=\overline {A}\cup \overline {B}\\\overline {A\cup B}=\overline {A}\cap \overline {B} \end{matris}}

000eller på annat sätt:000

{\begin{matrix}(A\cap B)^{C}=A^{C}\cup B^{C},\\(A\cup B)^{C}=A^{C}\cap B^{C}.\end{matris}}

Dessa regler är också giltiga för flera element (familjer):

\overline {\bigcap _{{i\in I}}A_{i}}=\bigcup _{{i\in I}}\overline {A_{i}}

00 000och .00 000

\overline {\bigcup _{{i\in I}}A_{i}}=\bigcap _{{i\in I}}\overline {A_{i}}

I predikatkalkyl :

\neg \förall x\,P(x)\equiv \exists x\,\neg P(x),

\neg \exists x\,P(x)\equiv \forall x\,\neg P(x).

Konsekvenser:

Med hjälp av De Morgans lagar kan man uttrycka en konjunktion i termer av en disjunktion och tre negationer. Disjunktionen kan uttryckas på liknande sätt:

a\kil b=\neg (\neg {a}\vee \neg {b})

a\vee b=\neg (\neg {a}\kil \neg {b})

I form av ett teorem :

Om det finns en bedömning som uttrycks genom operationen av logisk multiplikation av två eller flera element, det vill säga operationen "och" :, för att hitta inversen av hela bedömningen, är det nödvändigt att hitta inversen av varje element och kombinera dem med operationen av logisk addition , det vill säga operationen "eller » : . Lagen fungerar på liknande sätt i motsatt riktning: . ${\displaystyle {(A\wedge B)))$ ${\displaystyle {\neg (A\wedge B)))$ $(\neg {A}\vee \neg {B})$ $\neg (A\vee B)=(\neg {A}\wedge \neg {B})$

Applikation

De Morgans lagar gäller inom viktiga områden som diskret matematik , elektroteknik , fysik och datavetenskap ; till exempel används de för att optimera digitala kretsar genom att ersätta vissa logiska element med andra.

Historik

Den motsägelsefulla motsatsen till en disjunktiv dom är en konjunktiv dom som består av motstridiga motsatser till delar av en disjunktiv dom.

Originaltext (engelska)[ visaDölj] Den motsägelsefulla motsatsen till en disjunktiv proposition är en konjunktiv proposition sammansatt av motsägelserna i delarna av disjunktiv proposition. — William av Ockham , Summa Logicae

Se även

Formel för inkludering-uteslutning

Länkar

Weisstein, Eric W. De Morgans lagar på Wolfram MathWorld .

Logikens lagar

Lagar

Main	Identitetens lag motsägelsens lag Lagen om den uteslutna mitten Lagen om dubbel negation Pierces lag Lagen om tillräckligt skäl
De Morgans lagar Lagar för deduktivt resonemang Clavius lag

Lagars principer och egenskaper

Explosionsprincip
Monotonicity of entailment
Idempotens av attraktion
Kommutativitet av konjunktion
Indelningsprincipen