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

Aus VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Version vom 7. März 2019, 16:53 Uhr von Gittenborg (Diskussion | Beiträge) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 98 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 98 und überschrieb dabei eine Weiterleitung: verschie…)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

Beweisen oder widerlegen Sie die folgenden Identitäten für Mengen:

 (A \times B) \cup (B \times A) = (A \cup B) \times (B \cup A)

Lösungsvorschlag von Axel[Bearbeiten]

Beiweise/Wiederlege: (A \times B) \cup (B \times A) = (A \cup B) \times (A \cup B)

Sei a Element von A und a kein Element von B. Dann ist wegen a Element von A a auch Element (A \cup B), also (a,a) Element von (A \cup B) \times (A \cup B). Wegen a kein Element B ist aber (a,a) kein Element von (A \times B) und auch kein Element von (B \times A), also auch kein Element von (A \times B) \cup (B \times A).

Damit ist (A \cup B) \times (A \cup B) keine Teilmenge von (A \times B) \cup (B \times A) , womit die Annahme wiederlegt ist.

Lösungsvorschlag von Georg Schiesser[Bearbeiten]

( A \cup B ) \times ( A \cup B ) =

( A \times ( A \cup B ) )  \cup  ( B \times ( A \cup B ) ) =

( A \times A ) \cup ( A \times B ) \cup ( B \times A ) \cup ( B \times B )

siehe: http://de.wikipedia.org/wiki/Kartesisches_Produkt

und dann sieht man, dass:

( A \times A ) \cup ( B \times B )

zuviel ist. gilt also nur, wenn:

A = B

Lösungsvorschlag von Johannes[Bearbeiten]

Johannes schlug vor, die Möglichkeiten aufzuzeichnen und so die Identität visuell zu "widerlegen" oder zu "bestätigen".

Seien A = B so ist die Bestätigung trivial.

Seien A und B "nebeneinander" so sieht man:

20AB.png

Seien A und B ineinander verschränkt_

20AuB.png

Lösungsvorschlag von Jensi[Bearbeiten]

ist umstritten --> Es ist wichtig zu beachten, dass das die geordneten Paare des Kreuzprodukts nicht Kommutativ sind. Die Reihenfolge darf nicht vertauscht werden obwohl das logische "und" schon Kommutativ ist. Daher ist der Beweis falsch.

Die Mengenoperationen \times und \cup sind wie folgt definiert:

A \times B = \{ \langle x, y \rangle \  | \  x \in A \land y \in B \}

A \cup B = \{ x \  | \  x \in A \lor x \in B \}

Daher kann man die linke und rechte Seite der Identität folgendermaßen beschreiben:

Linke Seite:


\begin{array}{rcll}
(A \times B) \cup (B \times A) & = & \{ z \  | \  z \in (A \times B) \lor z \in (B \times A) \} &| z :=  \langle x, y \rangle \\
& = & \{ \langle x, y \rangle \  | \   \langle x, y \rangle \in (A \times B) \lor  \langle x, y \rangle \in (B \times A) \} \\
& = & \{ \langle x, y \rangle \  | \   (x \in A \land y \in B) \lor (x \in B \land y \in A) \}
\end{array}

Der Übersichtlichkeit halber definieren wir Terme:


\begin{array}{rcl}
a & := & x \in A \\
b & := & y \in B \\
c & := & x \in B \\
d & := & y \in A
\end{array}

So können wir die linke Seite anschreiben als:

(A \times B) \cup (B \times A) = \{ \langle x, y \rangle \  | \   (a \land b) \lor (c \land d) \}

Rechte Seite:


\begin{array}{rcl}
(A \cup B) \times (A \cup B) & = & \{ \langle x, y \rangle \  | \  x \in (A \cup B) \land y \in (A \cup B) \} \\
& = & \{ \langle x, y \rangle \  | \  (x \in A \lor x \in B) \land (y \in A \lor y \in B) \}
\end{array}

Wir ersetzen wieder durch die früher definierten Terme a, b, c, d und formen den logischen Ausdruck zwecks besserer Vergleichbarkeit mit der linken Seite durch Ausdistribuieren in die disjunktive Normalform um (der Ausdruck für die linke Seite ist bereits in disjunktiver Normalform):


\begin{array}{rcl}
(A \cup B) \times (A \cup B) & = & \{ \langle x, y \rangle \  | \  (a \lor c) \land (d \lor b) \} \\
& = & \{ \langle x, y \rangle \  | \  (a \land b) \lor (a \land d) \lor (b \land c) \lor (c \land d) \}
\end{array}

Die Mengen sind nun identisch, wenn die logischen Ausdrücke, die sie definieren, die gleiche Bedeutung haben:


\begin{array}{rcl}
\underbrace{(a \land b) \lor (c \land d)}_{\textrm{linke Seite}} & = & \underbrace{(a \land b) \lor (a \land d) \lor (b \land c) \lor (c \land d) }_{\textrm{rechte Seite}} \\
(a \land b) \lor (c \land d) & = & (a \land b) \lor (c \land d) \lor (a \land d) \lor (c \land b) \qquad (*)\\
\end{array}

Wir können die Terme etwas umordnen:


(a \land b) \lor (c \land d) = (a \land b) \lor (c \land d) \lor (a \land d) \lor (c \land b)

Man sieht, daß die ersten zwei Terme jeder Seite gleich und damit logisch äquivalent sind. Die letzten beiden Terme der rechten Seite unterscheiden sich von den ersten beiden durch die Variablen b und d. Setzen wir nun die Variable d := b, so erhalten wir:


(a \land b) \lor (c \land b) = (a \land b) \lor (c \land b) \lor (a \land b) \lor (c \land b)

Da x \lor x = x gilt, gilt auch (a \land b) \lor (a \land b) = (a \land b). Analoges gilt für (c \land b):


(a \land b) \lor (c \land b) = (a \land b) \lor (c \land b)

Das bedeutet, daß (*) genau dann gilt, wenn b = d. Sehen wir uns die Definition der Terme an:


\begin{array}{rcl}
b & = & d \\
y \in B & = & y \in A
\end{array}

Die letzte Beziehung gilt genau dann für alle y aus A und B, wenn A = B:

Wenn y \in B \Rightarrow y \in A \  \forall y \in B gilt, so gilt B \subseteq A. Auch umgekehrt muß aufgrund der Symmetrie y \in A \Rightarrow y \in B \  \forall y \in A und damit A \subseteq B gelten. Aus A \subseteq B \land B \subseteq A folgt A = B.

(Warnung: Ich bin selbst nicht 100%ig überzeugt von diesem Beweis. Intuitiv muß das gelten, aber formal finde ich das nicht ganz sauber.)

Beispiel

Nehmen wir als Beispiel die Grundmengen A = \{ 1 \} und B = \{ a, b \}:


(A \times B) \cup (B \times A) = \{ \langle 1, a \rangle, \langle 1, b \rangle \} \  \cup \  \{ \langle a, 1 \rangle, \langle b, 1 \rangle \}
= \{ \langle 1, a \rangle, \langle 1, b \rangle , \langle a, 1 \rangle, \langle b, 1 \rangle \}


(A \cup B) \times (A \cup B) = \{ \{ 1, a, b \} \times \{ 1, a, b \} \}
= \{ \langle 1, 1 \rangle, \langle 1, a \rangle, \langle 1, b \rangle, \langle a, 1 \rangle, \langle a, a \rangle, \langle a, b \rangle, \langle b, 1 \rangle, \langle b, a \rangle, \langle b, b \rangle \}

Ein weiteres Beispiel für den Fall A = B = \{ a, b \}:


(A \times A) \cup (A \times A) = A \times A = \{ \langle a, a \rangle, \langle a, b \rangle, \langle b, a \rangle, \langle b, b \rangle \}


(A \cup A) \times (A \cup A) = A \times A = \{ \langle a, a \rangle, \langle a, b \rangle, \langle b, a \rangle, \langle b, b \rangle \}