Mahnazmezon

Hur man bevisar De Morgans lagar

Vetenskap
Share

I matematisk statistik och sannolikhet är det viktigt att känna till setteori. Uppsättningsteoriens elementära operationer har kopplingar till vissa regler vid beräkningen av sannolikheter. Interaktioner mellan dessa elementära uppsättningar av union, skärningspunkt och komplement förklaras av två uttalanden som kallas De Morgan's Laws. Efter att ha angett dessa lagar kommer vi att se hur vi kan bevisa dem.

Uttalande om De Morgan's Laws

De Morgan's Laws avser samverkan mellan facket, skärningspunkten och komplementen. Minnas det:

  • Korsningen mellan uppsättningarna EN och B består av alla element som är gemensamma för båda EN och B. Korsningen betecknas med EN ∩ B.
  • Föreningen mellan uppsättningarna EN och B består av alla element som i endera EN eller B, inklusive elementen i båda uppsättningarna. Korsningen betecknas av A U B.
  • Komplementet av uppsättningen EN består av alla element som inte är delar av EN. Detta komplement betecknas av AC.

Nu när vi har erinrat om dessa elementära operationer kommer vi att se uttalandet om De Morgan's Laws. För varje par uppsättningar EN och B

  1. (EN ∩ B)C = ENC U BC.
  2. (EN U B)C = ENC ∩ BC.

Översikt över bevisstrategi

Innan vi hoppar in i beviset kommer vi att tänka på hur vi kan bevisa uttalandena ovan. Vi försöker visa att två uppsättningar är lika med varandra. Hur detta görs i ett matematiskt bevis är genom proceduren för dubbel inkludering. Beskrivningen av denna metod för bevis är:

  1. Visa att uppsättningen på vänster sida av vårt likhetstecken är en delmängd av uppsättningen till höger.
  2. Upprepa processen i motsatt riktning och visa att apparaten till höger är en delmängd av apparaten till vänster.
  3. Dessa två steg tillåter oss att säga att uppsättningarna i själva verket är lika med varandra. De består av alla samma element.

Bevis för en av lagarna

Vi kommer att se hur vi kan bevisa den första av De Morgan's lagar ovan. Vi börjar med att visa att (EN ∩ B)C är en delmängd av ENC U BC.

  1. Antag först det x är ett element av (EN ∩ B)C.
  2. Detta innebär att x är inte en del av (EN ∩ B).
  3. Eftersom skärningspunkten är uppsättningen av alla element som är gemensamma för båda EN och B, föregående steg betyder det x kan inte vara en del av båda EN och B.
  4. Detta innebär att x är måste vara ett element i minst en av uppsättningarna ENC eller BC.
  5. Per definition betyder detta det x är en del av ENC U BC
  6. Vi har visat önskad deluppsättning.

Vårt bevis är nu halvvägs gjort. För att slutföra det visar vi motsatt inkludering av delmängden. Mer specifikt måste vi visa ENC U BC är en delmängd av (EN ∩ B)C.

  1. Vi börjar med ett element x i uppsättningen ENC U BC.
  2. Detta innebär att x är en del av ENC eller det x är en del av BC.
  3. Således x är inte ett element i minst en av uppsättningarna EN eller B.
  4. Så x kan inte vara en del av båda EN och B. Detta innebär att x är ett element av (EN ∩ B)C.
  5. Vi har visat önskad deluppsättning.

Bevis för den andra lagen

Beviset på det andra uttalandet är mycket likt det bevis som vi har beskrivit ovan. Allt som måste göras är att visa en delmängd inkludering av uppsättningar på båda sidor av likhetstecknet.

Vetenskap
×