Beweis de Morgan aus Axiomen < axiomatisch < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:21 Mi 24.10.2012 | | Autor: | iced |
| Aufgabe | A, B, X und Y seien Teilmengen einer Universalmenge U.
Beweisen Sie aus den Axiomen der Mengenoperationen, dass
( A [mm] \cup [/mm] B ) [mm] \cup [/mm] ( [mm] \overline{A} \cap \overline{B} [/mm] ) = U und
( A [mm] \cup [/mm] B ) [mm] \cap [/mm] ( [mm] \overline{A} \cap \overline{B} [/mm] ) = [mm] \emptyset. [/mm] |
Hallo zusammen,
ich habe die oben gestellte Aufgabe bekommen und komme einfach nicht weiter. Ich sitze seit Stunden an dieser Aufgabe und drehe mich nur im Kreis. Das Problem ist für mich, dass nur folgende Axiome verwendet werden dürfen:
- Indentitätsgesetze,
- Dominationsgesetze,
- Assoziativgesetze,
- Kommutativgesetze,
- Distributivgesetze.
Ich habe die Aufgabe von hinten aufgerollt und folgendes schon herausgefunden:
U
= ( A [mm] \cup [/mm] B ) [mm] \cup \overline{( A \cup B )} [/mm] (Dominationsgesetz)
[mm] \emptyset
[/mm]
= ( A [mm] \cup [/mm] B ) [mm] \cap \overline{( A \cup B )} [/mm] (Dominationsgesetz)
Daran sehe ich dass das de Morgansche Gesetz angewandt werden muss. Dieses muss allerdings bewiesen werden in eben dieser Aufgabe, da man in einem späteren Aufgabenteil genau das de Morgansche Gesetz folgern soll aus den vorherigen Aufgaben.
Ich habe jetzt schon 8-10 Stunden mit den Axiomen gespielt und komme einfach nicht auf die Lösung. Für Hilfe wäre ich sehr dankbar. Gibt es dabei irgendeinen Trick?
Gruß Pascal
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:44 Mi 24.10.2012 | | Autor: | tobit09 |
Hallo iced und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
Starte mal mit den Distributivgesetzen! (Evt. benötigst du auch Kommutativgesetze.)
Es gilt z.B.
[mm] $(A\cup B)\cup(\overline{A}\cap\overline{B})=((A\cup B)\cup\overline{A})\cap((A\cup B)\cup\overline{B})=\ldots$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:14 Do 25.10.2012 | | Autor: | iced |
Vielen Dank Tobias!
Ich bin jetzt mit Hilfe der Distributivgesetze und Kommutativgesetze auf U gekommen für den ersten Fall.
Allerdings habe ich vorausgesetzt, dass X [mm] \cup [/mm] U = U gilt. Dies lässt sich vermutlich auch mit Hilfe der Axiome beweisen?
Dann habe ich jetzt noch die Frage, wie man nun auf die Gesetze von de Morgan richtig folgert?
Danke schonmal im voraus.
Pascal
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:40 Do 25.10.2012 | | Autor: | tobit09 |
> Ich bin jetzt mit Hilfe der Distributivgesetze und
> Kommutativgesetze auf U gekommen für den ersten Fall.
> Allerdings habe ich vorausgesetzt, dass X [mm]\cup[/mm] U = U gilt.
> Dies lässt sich vermutlich auch mit Hilfe der Axiome
> beweisen?
Habe ich dich in der PN richtig verstanden, dass sich dies bereits erübrigt hat?
Übrigens ein komisches Vorgehen bei euch, dass ihr nur bereits bewiesene Rechengesetze benutzen dürft, anstatt neue direkt zu beweisen...
> Dann habe ich jetzt noch die Frage, wie man nun auf die
> Gesetze von de Morgan richtig folgert?
Es gilt folgender Zusammenhang:
Seien C und D Teilmengen einer Universalmenge U mit
1. [mm] $C\cup [/mm] D=U$ und
2. [mm] $C\cap D=\emptyset$.
[/mm]
Dann gilt [mm] $\overline{C}=D$.
[/mm]
Mit [mm] $C=A\cup [/mm] B$ und [mm] $D=\overline{A}\cap\overline{B}$ [/mm] folgt das erste de Morgansche Gesetz.
Zum Beweis von obigem Zusammenhang:
Zu zeigen ist [mm] $\overline{C}=D$. [/mm] Dazu genügt es, [mm] $\overline{C}\subseteq [/mm] D$ und [mm] $D\subseteq\overline{C}$ [/mm] zu zeigen.
Beweis von [mm] $\overline{C}\subseteq [/mm] D$:
Sei [mm] $u\in\overline{C}$. [/mm] Zu zeigen ist: [mm] $u\in [/mm] D$.
[mm] $u\in\overline{C}$ [/mm] bedeutet [mm] $u\in [/mm] U$ mit [mm] $u\not\in [/mm] C$.
Aus [mm] $u\in [/mm] U$ folgt mit 1. [mm] $u\in C\cup [/mm] D$, also [mm] $u\in [/mm] C$ oder [mm] $u\in [/mm] D$.
Wegen [mm] $u\not\in [/mm] C$ folgt [mm] $u\in [/mm] D$.
Beweis von [mm] $D\subseteq\overline{C}$:
[/mm]
Sei [mm] $u\in [/mm] D$. Zu zeigen ist: [mm] $u\in\overline{C}$.
[/mm]
Angenommen [mm] $u\not\in\overline{C}$.
[/mm]
Wegen [mm] $u\in [/mm] U$ somit nicht [mm] $u\not\in [/mm] C$, also [mm] $u\in [/mm] C$.
Also [mm] $u\in C\cap [/mm] D$, woraus mit 2. [mm] $u\in\emptyset$ [/mm] folgt.
Dies ist ein Widerspruch.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:38 Do 25.10.2012 | | Autor: | iced |
Vielen Dank!
> Habe ich dich in der PN richtig verstanden, dass sich dies
> bereits erübrigt hat?
Ja richtig, Teil 1 hat sich erledigt.
> Übrigens ein komisches Vorgehen bei euch, dass ihr nur
> bereits bewiesene Rechengesetze benutzen dürft, anstatt
> neue direkt zu beweisen...
Wir dürfen bestimmt neue beweisen, aber die müssen alle aus den Axiomen, die vorgegeben sind folgen.
> Seien C und D Teilmengen einer Universalmenge U mit
> 1. [mm]C\cup D=U[/mm] und
> 2. [mm]C\cap D=\emptyset[/mm].
> Dann gilt [mm]\overline{C}=D[/mm].
Diesen Teil habe ich bereits aus den Axiomen bewiesen, aber mir hat genau diese Idee gefehlt:
> Mit [mm]C=A\cup B[/mm] und [mm]D=\overline{A}\cap\overline{B}[/mm] folgt das
> erste de Morgansche Gesetz.
Danke dafür!
Jetzt soll ich noch das Involutionsgesetz folgern. Dies sollte doch auch mit
> Seien C und D Teilmengen einer Universalmenge U mit
> 1. [mm]C\cup D=U[/mm] und
> 2. [mm]C\cap D=\emptyset[/mm].
> Dann gilt [mm]\overline{C}=D[/mm].
gehen?
Genügt es, wenn ich schreibe:
Nach obigen Beweis gilt
A = [mm] \overline{B} [/mm] = [mm] \overline{\overline{A}}
[/mm]
für C = A und D = B bzw. C = [mm] \overline{B} [/mm] und D = [mm] \overline{\overline{A}}. [/mm] ?
Dann muss ich noch zwei Beweise machen, aber diesmal für Funktionen und ohne Axiome 
Viele Grüße
Pascal
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:57 Do 25.10.2012 | | Autor: | iced |
Kleine Korrektur:
Nach obigen Beweis gilt
A = [mm]\overline{B}[/mm] = [mm]\overline{\overline{A}}[/mm]
für C = A und D = B bzw. C = [mm]\overline{B}[/mm] und D = [mm] \overline{A} [/mm] .
Weiterhin viele Grüße
Pascal
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:33 Do 25.10.2012 | | Autor: | tobit09 |
> Jetzt soll ich noch das Involutionsgesetz folgern. Dies
> sollte doch auch mit
> > Seien C und D Teilmengen einer Universalmenge U mit
> > 1. [mm]C\cup D=U[/mm] und
> > 2. [mm]C\cap D=\emptyset[/mm].
> > Dann gilt [mm]\overline{C}=D[/mm].
> gehen?
>
> Genügt es, wenn ich schreibe:
(von dir korrigierte Version:)
> Nach obigen Beweis gilt
> A = [mm]\overline{B}[/mm] = [mm]\overline{\overline{A}}[/mm]
> für C = A und D = B bzw. C = [mm]\overline{B}[/mm] und D = [mm] \overline{A} [/mm] .
Ich kann dir irgendwie nicht folgen. Du willst offenbar [mm] $\overline{\overline{A}}=A$ [/mm] zeigen. Wo kommt jetzt B her?
Du könntest wie folgt argumentieren:
Wegen [mm] $\overline{A}\cup [/mm] A=U$ und [mm] $\overline{A}\cap A=\emptyset$ [/mm] folgt aus der obigen "C-D-Bemerkung" (du weißt schon, welche ich meine... ), dass [mm] $\overline{\overline{A}}=A$ [/mm] gilt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:46 Do 25.10.2012 | | Autor: | iced |
Ja so in etwa hatte ich das gemeint, nur wollte ich B als Zwischenmenge benutzen um auf [mm] \overline{\overline{A}} [/mm] zu schließen. Aber wenn das auch direkt so geht braucht man das ja nicht. Ich wusste nur nicht, dass das genügt.
Vielen Dank nochmal. Dann mache ich mal mit den anderen Beweisen weiter :-D Hoffe mal, dass sich mir die schneller erschließen.
Gruß Pascal
|
|
|
|
