kleenscher Abschluss / Produkt von Mengen

04.11.2010, 15:14

Estorias

Auf diesen Beitrag antworten »

kleenscher Abschluss / Produkt von Mengen

Meine Frage:
Aufgabe: Seien Aund B zwei Mengen. Beweise oder widerlege folgende Aussagen:

a) $\begin{eqnarray*} (A^*B^*)^* = (A\cup B)^* \end{eqnarray*}$

b) $\begin{eqnarray*} A(A \backslash B) = A^2 \backslash (AB) \end{eqnarray*}$

Meine Ideen:
Zu a) Reicht es aus wenn ich A = {a} und B = {b} setze und anhand dieser beiden Mengen zeige, dass die Aussage falsch ist? Weil im Grunde müsste es ja reichen, wenn ich schon anhand eines Beispieles zeige, dass die Aussage falsch ist. (und daher auch nicht allgemeingültig ist)

Zu b) Da hatte ich auch mit einem simplen Beispiel angefangen und es stellte sich für dieses raus, dass die Aussage wahr ist.
Zum Beweis: Muss ich hier eine Induktion durchführen???

Vielen Dank

04.11.2010, 15:17

Paradiesvogel

Auf diesen Beitrag antworten »

halb ja
a) Wenn man etwas widerlegen will, reicht es, ein Gegenbeispiel zu finden, aber das muss dann auch ordentlich ausformuliert und nicht nur genannt werden. Zeige, dass es dafür nicht stimmt und gut.

b) vollständige Induktion geht nur bei natürlichen Zahlen

04.11.2010, 21:46

Estorias

Auf diesen Beitrag antworten »

RE: halb ja
also zu a) habe ich ein Gegenbeispiel gefunden und das anschaulich erklärt.

So könntet ihr mir dann bitte bei b) helfen?
Die vollständige Induktion habe ich nun verworfen.
Wenn ich micht nicht irre schreibt man zunächst:
$\begin{eqnarray*} A(A \backslash B) = A^2 \backslash (AB) <br /> \Leftrightarrow A(A \backslash B)\subseteq A^2 \backslash (AB) \wedge A(A \backslash B) \supseteq A^2 \backslash (AB) \end{eqnarray*}$

D.h. Ich muss zeigen dass das Element x sowohl Element von der rechten Seite als auch der linken Seite ist. ( siehe 2. Gleichung)

Dann dachte ich mir ich muss zunächst noch die leere Menge in Betracht ziehen (Fallunterscheidung). Da will ich nicht jetzt alles aufschreiben. Fazit hier war aber, dass die Aussage für A={} und/oder B={} auch wahr ist.

Ist der Anfang schon mal gut?
Wenn ja wie kann ich denn jetzt zeigen, dass x Element sowohl von der einen Menge als auch von der anderen Menge ist(linke und rechte Seite der Gleichung)?
Oder bin ich komplett auf dem Holzweg?

Danke

05.11.2010, 20:21

Estorias

Auf diesen Beitrag antworten »

RE: halb ja
Kann mir keiner helfen?? Man muss meiner Meinung nach das Distributivgesetz zeigen
Ich komm bloß nicht weiter.
Hier meine bisherige Berechnung:

$\begin{eqnarray*} A(A\backslash B) \Leftrightarrow x \in A \wedge y \in (A\backslash B) \Leftrightarrow x \in A \wedge (y \in A \wedge y \notin B) \end{eqnarray*}$

Nun muss ich das irgenwie so umformen, dass ich das Distributivgesetz anwenden muss.

Kann mir BITTE jemand helfen??

06.11.2010, 00:51

Paradiesvogel

Auf diesen Beitrag antworten »

Was meinst du?
Was meinst du denn mit?:

$\begin{eqnarray*} A(A/B) \end{eqnarray*}$

Meinst du: $\begin{eqnarray*} A \cup (A/B) \end{eqnarray*}$

oder: $\begin{eqnarray*} A \cap (A/B) \end{eqnarray*}$

Das ist ein recht großer Unterschied! ^^

06.11.2010, 12:48

Turtle

Auf diesen Beitrag antworten »

Beweis
Hallo Estorias, ich hab die Aufgabe auch grad gemacht und dein Ansatz ist gut. Mach es dir aber nicht so umständlich und vesuche A²/(AB) umzuformen.
Wenn du das dann hast kommst du auch auf $\begin{eqnarray*} x\in A\wedge (y\in A \wedge y\notin B) \end{eqnarray*}$ und hast den Beweis.

Gruß Turtle

Anzeige

06.11.2010, 14:12

Turtle

Auf diesen Beitrag antworten »

Nochmal
Hallo ich nochmal,
mich würde nun aber noch interessieren was du für ein Gegenbeispiel gefunden hast... ich bin der Meinung, dass die Aussage auch wahr ist und bewiesen werden müsste.

Gruß

06.11.2010, 14:45

Estorias

Auf diesen Beitrag antworten »

RE: Gegenbeispiel
Hallo Turtle,

Tja, dann liege ich wohl falsch mit dem Gegenbeispiel, weil ein anderer meinte auch er hätte einen Beweis.

Hier mein Gegenbeispiel:
Sei A = {a} und B ={b}
$\begin{eqnarray*} A^* = \cup A^i ; n= 1 \end{eqnarray*}$

Unter dem Vereinigungssymbol steht noch n ist größer gleich 0. Ist also die Definiton vom Kleeneschen Abschluss (wusste die LateX-Schreibweise nicht) Habe dann willkürlich n=1 gesetzt.
Dann folgt daraus:
$\begin{eqnarray*} A^* = A^0 \cup A^1 = \{\epsilon; a\} \\ B^* = B^0 \cup B^1 = \{\epsilon; b\} \\ A^* \cdot B^* = \{ab\} \\ (A^* \cdot B^*)^* =(A^* B^*)^0 \cup (A^* B^*)^1 = \{\epsilon, ab\} \\ A \cup B = \{a,b\} \\ (A \cup B)^* = (A \cup B)^0 \cup (A \cup B)^1 = \{\epsilon,a,b\} \end{eqnarray*}$

und nochmal zum zweiten:
Da komme ich nur bis zu:
$\begin{eqnarray*} A^2/(AB) \\ \Leftrightarrow x\in A^2 \wedge y \notin AB \\ \Leftrightarrow x \in A \wedge y \in A \wedge xy \notin AB \end{eqnarray*}$

Wie kann ich denn die letzte Zeile auflösen?

Ich bin leider nicht so ein begnadeter Beweisfinder.

06.11.2010, 14:48

kiste

Auf diesen Beitrag antworten »

Du hast den Stern nicht wirklich verstanden. Es wird über alle n>=0 vereinigt. Du darfst n nicht irgendwie setzen

06.11.2010, 14:51

Estorias

Auf diesen Beitrag antworten »

RE: Was meinst du?
Hallo Paradiesvogel,

ich meine so wie ich es geschrieben habe ^^

Das Produkt von Mengen, d.h. die Elemente der jeweiligen Mengen werden konkateniert (hintereinandergeschrieben) . Ist so ähnlich wie das kartesische Produkt.

06.11.2010, 14:51

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Paradiesvogel
Was meinst du denn mit?:

$\begin{eqnarray*} A(A/B) \end{eqnarray*}$

Meinst du: $\begin{eqnarray*} A \cup (A/B) \end{eqnarray*}$

oder: $\begin{eqnarray*} A \cap (A/B) \end{eqnarray*}$

Sieht danach aus, dass er letzteres meint.

Während bei der reellen Multiplikation das Weglassen des Malzeichens $\begin{eqnarray*} \cdot \end{eqnarray*}$ allgemein üblich ist, kenne ich das Weglassen von $\begin{eqnarray*} \cap \end{eqnarray*}$ bei Mengendurchschnitten eher nicht. Aber wenn man es vorher so vereinbart, warum nicht. Augenzwinkern

Augenzwinkern

06.11.2010, 14:52

Estorias

Auf diesen Beitrag antworten »

Darf ich nicht? Hm... ok. Also ist das Ding immer (meistens) unendlich.
Ich dachte man könnte für das n auch was einsetzten... Damn !

06.11.2010, 14:56

kiste

Auf diesen Beitrag antworten »

Ja, ist A nicht-leer so ist $\begin{eqnarray*} A^* \end{eqnarray*}$ unendlich groß Augenzwinkern

Augenzwinkern

An den Rest: Hier geht es um formale Sprachen, nicht um Mengenlehre.

Dein Beweis zum zweiten passt nicht. Fange so an:
$\begin{eqnarray*} w\in A^2\backslash AB \Leftrightarrow \exists x,y\in A: w=xy \land w\not\in AB \end{eqnarray*}$

06.11.2010, 15:10

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von kiste
An den Rest: Hier geht es um formale Sprachen, nicht um Mengenlehre.

Danke für die Klarstellung - aus dem Eröffnungsposting ging das nämlich mit keinem Wort hervor - da war nur von Mengen die Rede, und wurde Mengensymbolik verwendet (die Überschrift habe ich leider erst später gelesen), Paradiesvogel ging es wohl ähnlich.

Das war's jetzt auch mit der Störung - bin weg.

06.11.2010, 15:20

Turtle

Auf diesen Beitrag antworten »

Mom, bin beim editieren Big Laugh

Big Laugh

06.11.2010, 15:52

Cugu

Auf diesen Beitrag antworten »

zu b)
$\begin{eqnarray*} A=\{a,cb,ac\} \end{eqnarray*}$ und $\begin{eqnarray*} B=\{b\} \end{eqnarray*}$
Das sieht mir nach einem geeigneten Kandidaten für ein Gegenbeispiel aus.

06.11.2010, 15:54

Estorias

Auf diesen Beitrag antworten »

Hallo ist es dann richtig wenn ich deine Gleichung wie folgt umforme:
$\begin{eqnarray*} \exists x,y \in A : w = xy \wedge x \notin AB \\ \Leftrightarrow \exists x,y \in A : w = xy \wedge x \notin A \wedge y \notin B \end{eqnarray*}$

06.11.2010, 16:03

Estorias

Auf diesen Beitrag antworten »

@Cugu
$\begin{eqnarray*} A = \{a, cb , ac\} ; B= \{b\} \\ AB = \{ab, cbb, acb\} \\ A\backslash B = A \\ A(A\backslash B) =\{aa, acb , aac , cba , cbcb , cbac , aca ,accb, acac\} = A ^2 \\ <br /> A^2\backslash (AB) = A^2 \end{eqnarray*}$

06.11.2010, 16:10

Cugu

Auf diesen Beitrag antworten »

Guck mal, ob du ein Element findest, das sowohl in $\begin{eqnarray*} A^2=A(A\setminus B) \end{eqnarray*}$ als auch in $\begin{eqnarray*} AB \end{eqnarray*}$ liegt!
Daraus würde $\begin{eqnarray*} A^2\setminus (AB) \neq A^2 \end{eqnarray*}$ folgen!

06.11.2010, 16:15

Estorias

Auf diesen Beitrag antworten »

ay sieht ja beinahe so aus als hättest du recht.
Das Element {acb} taucht in beiden auf

06.11.2010, 17:27

Turtle

Auf diesen Beitrag antworten »

formale sprache
Hallo kiste,

worin besteht bei dem Beweis genau der Unterschied zwischen ner formalen Sprache und ner Menge? Was hindert mich genau daran die Sprache als Menge von Worten zu betrachten und somit dann über die Mengenlehre zu beweisen, dass es sich 2 gleiche Mengen handelt.

Gruß

07.11.2010, 09:40

kiste

Auf diesen Beitrag antworten »

Aufpassen. Ihr bescheißt euch gerade selbst beim Beweis.

Ihr dürft nicht einfach das Alphabet vertauschen mit den Wörtern.
Von mir aus nennt einen Buchstaben cb. Dann ist das aber auch ein Buchstabe.
D.h. es ist a(cb) nicht dasselbe wie (ac)b

@Turtle:
Nichts, aber du hast noch eine zusätzliche Struktur dass die Elemente Wörter über deinem Alphabet sind

07.11.2010, 10:22

Estorias

Auf diesen Beitrag antworten »

ja is mir gestern abend auch noch mal aufgefallen

Kann jemand vielleicht noch Starthilfe für Aufgabe a geben?

07.11.2010, 10:42

kiste

Auf diesen Beitrag antworten »

Schreib einfach mal die Definition einer Seite aus

07.11.2010, 13:51

Cugu

Auf diesen Beitrag antworten »

Zitat:

Original von kiste
Aufpassen. Ihr bescheißt euch gerade selbst beim Beweis.

Ihr dürft nicht einfach das Alphabet vertauschen mit den Wörtern.
Von mir aus nennt einen Buchstaben cb. Dann ist das aber auch ein Buchstabe.
D.h. es ist a(cb) nicht dasselbe wie (ac)b

Wieso kann man nicht als Alphabet $\begin{eqnarray*} \{a,b,c\} \end{eqnarray*}$ nehmen und obige Mengen betrachten?

07.11.2010, 14:02

kiste

Auf diesen Beitrag antworten »

Mhh stimmt...
Dann ist mir die Aufgabenstellung zu ungenau. Es steht nicht dran was für Mengen gemeint sind. Also ob man sie als Mengen von Wörtern über einem gemeinsamen Alphabet sehen darf, oder ob man streng nach Definition(? kommt auf die Definition an) das Alphabet ersteinmal disjunkt nimmt.
Je nach Interpretation kann die Aussage dann wahr oder falsch sein Augenzwinkern

Augenzwinkern

07.11.2010, 14:33

G26

Auf diesen Beitrag antworten »

zu b.)
Was ist wenn a={a;b} und b={b;c}
Dann geht der Beweis nicht auf weil A(A\B) in dem Fall nicht A^2

07.11.2010, 17:17

Cugu

Auf diesen Beitrag antworten »

Welcher Beweis?

Fakt ist, wenn man $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ als Teilmengen einer freien Gruppe ansehen darf (deren Erzeuger das Alphabet bilden), dann ist die Aussage falsch.

Wenn $\begin{eqnarray*} A,B \end{eqnarray*}$ hingegen Teilmengen von Alphabeten sein müssen, also nur Buchstaben als Elemente enthalten, stimmt sie natürlich.

In der Aufgabe selbst wird das nicht geklärt...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »