Hva er De Morgan's lover?

Matematisk statistikk krever noen ganger bruk av settteori. De Morgan's lover er to uttalelser som beskriver samspillet mellom forskjellige setteorien. Lovene er som for alle to sett EN og B:

1. (EN ∩ B)^C = EN^C U B^C.
2. (EN U B)^C = EN^C ∩ B^C.

Etter å ha forklart hva hver av disse påstandene betyr, vil vi se på et eksempel på at hver av disse er brukt.

For å forstå hva De Morgan's Laws sier, må vi huske noen definisjoner av setteorien. Spesielt må vi vite om union og kryss av to sett og komplementet til et sett.

De Morgan's Laws forholder seg til samspillet mellom fagforeningen, krysset og komplementet. Husk det:

• Skjæringspunktet mellom settene EN og B består av alle elementer som er felles for begge EN og B. Krysset er betegnet med EN ∩ B.
• Forening av settene EN og B består av alle elementer som i begge EN eller B, inkludert elementene i begge settene. Krysset er betegnet med A U B.
• Komplementet til settet EN består av alle elementer som ikke er elementer av EN. Dette komplementet er betegnet med A^C.

Nå som vi har husket disse elementære operasjonene, vil vi se uttalelsen om De Morgan's Laws. For hvert par sett EN og B vi har:

1. (EN ∩ B)^C = EN^C U B^C
2. (EN U B)^C = EN^C ∩ B^C

Disse to utsagnene kan illustreres ved bruk av Venn-diagrammer. Som vi ser nedenfor, kan vi demonstrere ved å bruke et eksempel. For å demonstrere at disse uttalelsene er sanne, må vi bevise dem ved å bruke definisjoner av set teori operasjoner.

Tenk for eksempel settet med reelle tall fra 0 til 5. Vi skriver dette i intervallnotasjon [0, 5]. Innenfor dette settet har vi EN = [1, 3] og B = [2, 4]. Videre, etter anvendelse av våre elementære operasjoner, har vi:

• Komplementet EN^C = [0, 1) U (3, 5]
• Komplementet B^C = [0, 2) U (4, 5)
• Unionen EN U B = [1, 4]
• Krysset EN ∩ B = [2, 3]

Vi begynner med å beregne fagforeningen EN^C U B^C. Vi ser at foreningen til [0, 1) U (3, 5] med [0, 2) U (4, 5] er [0, 2) U (3, 5]. Krysset EN ∩ B er [2, 3]. Vi ser at komplementet til dette settet [2, 3] også er [0, 2) U (3, 5]. På denne måten har vi demonstrert det EN^C U B^C = (EN ∩ B)^C.

Nå ser vi krysset mellom [0, 1) U (3, 5] med [0, 2) U (4, 5] er [0, 1) U (4, 5]. Vi ser også at komplementet til [1, 4] også er [0, 1) U (4, 5]. På denne måten har vi demonstrert det EN^C ∩ B^C = (EN U B)^C.

Gjennom logikkens historie, mennesker som Aristoteles og William av Ockham har gitt uttalelser som tilsvarer De Morgan's Laws.

De Morgan's lover er oppkalt etter Augustus De Morgan, som levde fra 1806–1871. Selv om han ikke oppdaget disse lovene, var han den første som introduserte disse utsagnene formelt ved bruk av en matematisk formulering i proposisjonell logikk.