TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 93

From VoWi
Jump to navigation Jump to search

Beweisen Sie die folgenden Beziehung mit Hilfe von Elementtafeln oder geben Sie ein konkretes Gegenbeispiel an:

 (A \triangle B)' \qquad = \qquad A' \triangle B'

Hilfreiches

Mengen-Differenz
Mengen-Differenz

A - B - A\B
e - e - ne
e - ne - e
ne - e - ne
ne - ne - ne


e .... ist Element
ne .... ist kein Element

=)

Erklärungen

 (A \triangle B) = (A \setminus B) \cup (B \setminus A)

symetrische Differenz der Mengen A und B. Das Ergebnis beinhaltet sämtliche Elemente die nur in A und die nur in B enthalten sind.

 A' = (G \setminus A)

Komplement der Menge A (bezüglich einer Grundmenge G), es beinhaltet nur Elemente die in G enthalten sind, aber nicht in A.

Lösungsvorschlag von Soymilk-Drinker

Lösung durch Gegenbeispiel

Wir benötigen die Mengen A, B und zusätzlich G (Grundmenge damit das Komplement gerechnet werden kann)

 A = \{1, 2\}

 B = \{2, 3\}

 G = \{1, 2, 3, 4\}

linke Seite:

 A \triangle B = \{1, 3\}

 (A \triangle B)' = \{2, 4\}

rechte Seite:

 A' = \{3, 4\}

 B' = \{1, 4\}

 A' \triangle B' = \{1, 3\}

Deutung:

Auf der linken Seite kommt als Ergebnis die Menge  \{2, 4\} , auf der rechten Seite  \{1, 3\} . Beide sind eindeutig verschieden, daher kann die Beziehung  (A \triangle B)' = A' \triangle B' nicht richtig sein.

Lösung mit Elementtafel

Elementtafeln sind sehr ähnlich wie Wahrheitstafeln, man füllt jedoch anstelle von Wahrheitswerten "Elementwerte" ein (also  \in oder oder  \notin ) und löst das ganze dann Stück für Stück.

symetrische Differenz und Komplement in der Elementtafel

 A \triangle B

Die symetrische Differenz beinhaltet nur die Elemente welche entweder in A oder in B sind, aber nicht in beidem. In der Elementtafel bekommt man als Ergebnis also dann  \in wenn einer der Werte  \in und der andere  \notin ist. Ansonsten ist das Ergebnis  \notin .

 A'

Das Komplement beinhaltet nur Elemente die nicht in A enthalfen sind. Daher werden alle Elemente die vorher  \in waren zu  \notin und umgekehrt. Das Komplement wirkt also wie die Negation bei logischen Ausdrücken.

linke Seite

A B \  A \triangle B  (A \triangle B)'
 \in  \in \  \notin  \in
 \in  \notin \  \in  \notin
 \notin  \in \  \in  \notin
 \notin  \notin \  \notin  \in

Erklärung:

In der ersten Zeile haben wir A  \in und B  \in . Das lässt sich auch so lesen dass diese Zeile für alle Elemente steht die  \in A sind und die  \in B sind. Bilden wir nun von diesen Elementen die symetrische Differenz so erhalten wir als Ergebnis  \notin - Das ist wohl verständlich, denn bei der symetrischen Differenz fallen ja alle Elemente weg die gleichzeitig in A und in B sind, und genau dafür steht diese Zeile ja. Danach bilden wir noch das Komplement und erhalten als Ergebnis  \in , auch das sollte verständlich sein denn beim Komplement erhalten wir alle Elemente die vorher nicht im Ausdruck waren und alle die im Ausdruck waren fallen weg, also eine Umkehrung der Werte.

In der zweiten und dritten Zeile haben wir einen Wert mit  \in und einen mit  \notin , diese Zeilen stehen also für die Elemente die in einer von beiden Mengen enthalten sind und in der anderen nicht. Bei der symetrischen Differenz erhalten wir somit  \in , denn man erhält hierbei ja genau die Elemente die in einem enthalten sind und im anderen nicht. Das Ergebnis des Komplements ist somit dann  \notin .

In der vierten Zeile haben wir beide male  \notin stehen, die Zeile steht also für die Elemente die weder in A noch in B sind. Bei der symetrischen Differenz kommt als Ergebnis  \notin , was vorher nicht drin war ist nachher auch nicht drinn. Das Komplement dreht das ganze wieder um und liefert  \in als Ergebnis.

rechte Seite

A B \  A'  B'  A' \triangle B'
 \in  \in \  \notin  \notin  \notin
 \in  \notin \  \notin  \in  \in
 \notin  \in \  \in  \notin  \in
 \notin  \notin \  \in  \in  \notin

Lösung

Man sieht in den beiden Elementtafeln (in der jeweils letzten Spalte) dass die Ergebnisse völlig verschieden sind. Daher ist gezeigt dass  (A \triangle B)' = A' \triangle B' eindeutig falsch sein muss.

Lösungsvorschlag von mnemetz

Unser geschätzer Soymilk-Drinker hat wieder eine sehr intuitive Lösung gepostet - ich versuche zu der Lösung etwas Erweiterndes bzw. Erhellendes beizutragen, und zwar mit dem Versuch einer Verallgemeinerung bzw. der Darstellung durch VENN-Diagramme.

Nachsatz: Vielen Dank an Soymilk-Drinker, für die Elementtael-Lösung! --Mnemetz 11:45, 26. Nov 2005 (CET)

Widerspruch durch Umformen zeigen

Die Angabe ist:  (A \triangle B)' \qquad = \qquad A' \triangle B'

Nehmen wir uns mal die linke Seite vor:

 (A \triangle B)' formen wir um zu (Kenntnis der Definition der symm. Differenz wird vorausgesetzt!)

((A \backslash B) \cup (B \backslash A))'

Und dabei belassen wir es einmal.

Nun nehmen wir uns die rechte Seite vor, die wir wiederum umformen:

A' \triangle B' = (B \backslash A) \triangle (A \backslash B) = ((B \backslash A) \backslash (A \backslash B)) \cup ((A \backslash B) \backslash (B \backslash A)) = (B \backslash A) \cup (A \backslash B) = A \triangle B

Der Widerspruch ist offensichtlich!

Widerspruch durch VENN-Diagramme aufzeigen

Eine weitere Idee bestünde darin, den Widerspruch durch VENN-Diagramme aufzuzeigen!

Venn-Diagramme linke Seite

(sequenziell angeordnet)

Bsp13 ls1.png

Bsp13 ls2.png

Bsp13 ls3.png

Venn-Diagramme rechte Seite

(sequenziell angeordnet)

Bsp13 rs1.png

Bsp13 rs2.png

Deutung

Widerspruch ist offensichtlich!

Anti-Gittenberger-Strategie ;-)

Beim Gittenberger schlage ich folgende Vorgehensweise vor:

  1. #Widerspruch_durch_VENN-Diagramme_aufzeigen - Begründung: Mittels einer visuellen Darstellung kann man sehr schnell feststellen, ob ein Widerspruch vorliegt (nicht disjunkte Mengen zur Illustration auswählen!)
  2. #Lösung_durch Gegenbeispiel - nun sagt man, man hat ein konkretes Gegenbeispiel parat => Ungleichheit ist erwiesen
  3. Falls weiter gebohrt wird, sollte man auf #Lösung_mit_Elementtafel hinweisen oder auf die Möglichkeit, den #Widerspruch durch Umformen zeigen zu können.