Mengenlehre (Beweis) < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweis für (S [mm] \Delta [/mm] T) [mm] \Delta [/mm] R = S [mm] \Delta [/mm] (T [mm] \Delta [/mm] R)
[Beweis für den Sachverhalt des Assoziativgesetzes für die symmetrische Differenz] |
Hallo an alle Mathecracks! =)
Soll diesen netten Beweis erbringen, dass das Assoziativgesetz für die symmetrische Differenz gilt.
(Voraussetzungen schreibe ich mal in grün und
Folgerungen in rot)
Zu allererst habe ich die Mengen definiert. (Also S,T und R eingeführt.)
--> Seien S,T,R beliebige Mengen.
Dann hab ich geguckt welche Definitionen ich anwenden muss. (Was mir allerdings gar nicht so leicht fällt...)
Ich liste die Definitionen, bei denen ich denke, dass sie benötigt werden mal auf:
Mengengleichheit:
Zwei Mengen M1 und M2 heißen gleich, genau dann wenn sie die gleichen Elmente enthalten. Mit anderen Worten:
1) Jedes Element von M1 ist Element von M2. UND
2) Jedes Element von M2 ist Element von M1.
Symmetrische Differenz:
S [mm] \Delta [/mm] T = [mm] \{x|(x \in S \wedge x \not\in T)\vee (x \not\in S \wedge x \in T)\}
[/mm]
= [mm] \{x| \mbox{entweder} x \in S \vee x \in T\}
[/mm]
So weit, so gut.
Nachdem ich die Mengen nun eingeführt habe muss ich doch dann zeigen, was nach welcher Definition zu beweisen ist.
--> Wir müssen nach der Definition der Mengengleichheit beweisen, dass
Jedes Element von (S [mm] \Delta [/mm] T) [mm] \Delta [/mm] R ist Element von S [mm] \Delta [/mm] (T [mm] \Delta [/mm] R) und
Jedes Elent von S [mm] \Delta [/mm] (T [mm] \Delta [/mm] R) ist Element von (S [mm] \Delta [/mm] T) [mm] \Delta [/mm] R
Doch jetzt bekomme ich langsam Probleme mit dem Beweis weiter zu machen... Ich habe ja jetzt gesagt mittels welcher Defintion ich das beweisen möchte.
Ist das richtig wenn ich dann so weiter mache:
--> Sei [mm] x\in [/mm] (S [mm] \Delta [/mm] T) [mm] \Delta [/mm] R beliebig. Wir müssen zeigen, dass [mm] x\in [/mm] S [mm] \Delta [/mm] (T [mm] \Delta [/mm] R) .
Aus [mm] x\in [/mm] (S [mm] \Delta [/mm] T) [mm] \Delta [/mm] R folgt nach der Definition der Symmetrischen Differenz, dass x [mm] \in [/mm] (S [mm] \wedge [/mm] x [mm] \not\in T)\vee [/mm] (x [mm] \not\in [/mm] S [mm] \wedge [/mm] x [mm] \in [/mm] T)
Wir müssen nun nach der Definition der Symmetrischen Differenz zeigen, dass x [mm] \in [/mm] (S [mm] \wedge [/mm] x [mm] \not\in T)\vee [/mm] (x [mm] \not\in [/mm] S [mm] \wedge [/mm] x [mm] \in [/mm] T) .
So und jetzt haben wir so verschiedene Regeln für den Schluss bekommen. Ich weiß allerdings nicht welche ich anwenden muss.
Die eine heißt "oder ein" und die andere "oder aus" [mm] \to [/mm] da muss man ne Fallunterscheidung machen.
Weiß also nicht wirklich wie ich das jetzt beweisen soll.
Wäre nett, wenn ihr mir dabei helfen könntet.
LG DarkAngel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:12 Mo 12.02.2007 | | Autor: | moudi |
Hallo DarkAngel
Du bist scho auf dem richtigen Weg, du musst nur konsequent zu Ende arbeiten.
Sei [mm] $x\in (A\Delta B)\Delta [/mm] C$, dann gilt daher
[mm]
(x\in (A\Delta B) \wedge x\notin C) \vee (x\notin (A\Delta B)\wedge x\in C)
\Bigl(\bigl((x\in A\wedge x\notin B)\vee (x\notin A\wedge x\in B)\bigr)\wedge x\notin C\Bigr)\vee(\neg(x\in A\Delta B)\wedge x\in C)
\Bigl(\bigl(x\in A\wedge x\notin B\wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\red{\neg\bigl((x\in A\wedge x\notin B)\vee(x\notin A\wedge x\in B)\bigr)}\wedge x\in C\Bigr)
[/mm]
Die Regeln der Negation anwenden.
[mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\bigl(\red{ (x\notin A\vee x\in B)\wedge(x\in A\vee x\notin B)}\bigr)\wedge x\in C\Bigr)
[/mm]
Hier wendet man das Distributivgesetz auf den roten Formelteil an.
[mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\bigl( \underbrace{(x\notin A\wedge x\in A)}_{F}\vee (x\notin A\wedge x\notin B)\vee(x\in B\wedge x\in A)\vee\underbrace{(x\in B\wedge x\notin B)}_{F}\bigr)\wedge x\in C\Bigr)
[/mm]
Die Konstanten F eliminieren.
[mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\red{\bigl((x\notin A\wedge x\notin B)\vee(x\in B\wedge x\in A)\bigr)\wedge x\in C}\Bigr)
[/mm]
Nochmals Distributivgesetz für den roten Formelteil.
[mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl((x\notin A\wedge x\notin B\wedge x\in C)\vee\red{(x\in B\wedge x\in A\wedge x\in C)}\Bigr)
[/mm]
Noch umordnen und überflüssige Klammern entfernen.
[mm]
\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)
\vee(x\notin A\wedge x\notin B\wedge x\in C)\vee(x\in A\wedge x\in B\wedge x\in C)
[/mm]
Du siehts, die Formel ist (wegen der Kommutativität von [mm] $\vee$ [/mm] und [mm] $\wedge$) [/mm] absolut symmetrisch in A,B,C. D.h. durch vertauschen von A,B,C in irgendeiner Reihenfolge, ändert sich die Formel nicht.
Wenn man noch gezeigt hat, dass die die symmetrische Differenz kommutativ ist, dann gilt natürlich [mm] $A\Delta(B\Delta C)=(B\Delta C)\Delta [/mm] A$ und man erhält für [mm] $x\in(B\Delta C)\Delta [/mm] A$, wegen der Symmetrie die gleich Formel.
Damit ist das Assoziativgesetz gezeigt.
mfG Moudi
|
|
|
| |
|
Hallo moudi!
Verstehe das mit der Negation nicht....
[mm] \Bigl(\bigl(x\in A\wedge x\notin B\wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr) [/mm]
[mm] \vee\Bigl(\red{\neg\bigl((x\in A\wedge x\notin B)\vee(x\notin A\wedge x\in B)\bigr)}\wedge x\in C\Bigr)
[/mm]
[/mm]
>
> Die Regeln der Negation anwenden.
Warum muss man das denn dann negieren?? Gibt es keine einfachere Lösung dazu (Venn-Diagramm oder Wertetabelle)?
>
> [mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\bigl(\red{ (x\notin A\vee x\in B)\wedge(x\in A\vee x\notin B)}\bigr)\wedge x\in C\Bigr)
[/mm]
>
> Hier wendet man das Distributivgesetz auf den roten
> Formelteil an.
>
> [mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\bigl( \underbrace{(x\notin A\wedge x\in A)}_{F}\vee (x\notin A\wedge x\notin B)\vee(x\in B\wedge x\in A)\vee\underbrace{(x\in B\wedge x\notin B)}_{F}\bigr)\wedge x\in C\Bigr)
[/mm]
>
> Die Konstanten F eliminieren.
Wie kann man die denn eliminieren und wie kommt man denn auf die Konstante F?
> [mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl(\red{\bigl((x\notin A\wedge x\notin B)\vee(x\in B\wedge x\in A)\bigr)\wedge x\in C}\Bigr)
[/mm]
>
> Nochmals Distributivgesetz für den roten Formelteil.
>
> [mm]
\Bigl(\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)\Bigr)
\vee\Bigl((x\notin A\wedge x\notin B\wedge x\in C)\vee\red{(x\in B\wedge x\in A\wedge x\in C)}\Bigr)
[/mm]
>
> Noch umordnen und überflüssige Klammern entfernen.
>
> [mm]
\bigl(x\in A \wedge x\notin B \wedge x\notin C\bigr)\vee(x\notin A\wedge x\in B\wedge x\notin C\bigr)
\vee(x\notin A\wedge x\notin B\wedge x\in C)\vee(x\in A\wedge x\in B\wedge x\in C)
[/mm]
>
> Du siehts, die Formel ist (wegen der Kommutativität von
> [mm]\vee[/mm] und [mm]\wedge[/mm]) absolut symmetrisch in A,B,C. D.h. durch
> vertauschen von A,B,C in irgendeiner Reihenfolge, ändert
> sich die Formel nicht.
>
> Wenn man noch gezeigt hat, dass die die symmetrische
> Differenz kommutativ ist, dann gilt natürlich
> [mm]A\Delta(B\Delta C)=(B\Delta C)\Delta A[/mm] und man erhält für
> [mm]x\in(B\Delta C)\Delta A[/mm], wegen der Symmetrie die gleich
> Formel.
> Damit ist das Assoziativgesetz gezeigt.
Oder könntest du mir sonst nochmal die Klammern und die Symmetrie darin erklären?
Wäre echt nett!
LG DarkAngel =)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:42 Mo 12.02.2007 | | Autor: | moudi |
Hallo Dark Angel
Die Aussage [mm] $x\notin [/mm] A$ ist doch einfach die Negation von [mm] $x\in [/mm] A$. Logisch gesehen ist [mm] $x\notin [/mm] A$ einfach eine Abkürzung für [mm] $\neg(x\in [/mm] A)$.
Die Regeln für die Negation sollten bekannt sein:
[mm] $\neg(\Phi\vee\Psi)=(\neg\Phi)\wedge(\neg\Psi)$ [/mm] und
[mm] $\neg(\Phi\wedge\Psi)=(\neg\Phi)\vee(\neg\Psi)$.
[/mm]
Die Aussage [mm] $\Phi\wedge \neg \Phi$ [/mm] ist doch eine falsche Aussage, egal was [mm] $\Phi$ [/mm] für eine Formel ist. Eine Falsche Aussage kann man durch die Konstane $F$ für (false) ersetzen, analog kann man eine immer wahre Aussage durch die Konstane $T$ für (true) ersetzen.
Für diese Konstanten gelten die folgenden (sich leicht zu überlegenden) Regeln:
[mm] $F\wedge \Phi=F$
[/mm]
[mm] $F\vee \Phi=\Phi$
[/mm]
[mm] $T\wedge\Phi=\Phi$
[/mm]
[mm] $T\vee\phi=T$.
[/mm]
Alternativ kannst du auch ein Venndiagramm für die Menge [mm] $A\Delta(B\Delta [/mm] C)$ hinmalen. Dann siehst du sofort, dass die Menge "symmetrisch" in A,B,C ist. Du hast mit der logischen Formulierung angefangen, die habe ich dann fortgesetzt.
mfG Moudi
|
|
|
|
