Äquivalenzrelation < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi Leute,
Bei folgender Aufgabe geht es darum zu zeigen, daß [mm] $R_L$ [/mm] eine Äquivalenzrelation ist. Allerdings bin ich mir bei der Transitivität nicht sicher.
Sei also [mm] $\Sigma^{\star}$ [/mm] die Menge aller möglichen Wörter über dem endlichen Eingabealphabet [mm] $\Sigma$. [/mm] Sei [m]L \subseteq \Sigma^{\star}[/m] und seien [m]x,\,y \in \Sigma^{\star}[/m] beliebig. Dann definieren wir [m]x\;R_L\;y :\gdw \forall z \in \Sigma^{\star}:\;\left(xz \in L \gdw yz \in L\right)[/m].
Umgangssprachlich bedeutet dies also, daß zwei Zeichenketten eines endlichen Eingabealphabets genau dann [m]R_L-\text{äquivalent}[/m] sind, wenn beim gleichzeitigen Anhängen einer beliebigen Zeichenkette aus [m]\Sigma^{\star}[/m] an beide Zeichenketten, Zeichenketten entstehen, die entweder beide zur Sprache L gehören oder aber beide nicht zur Sprache L gehören.
Lösungsansatz:
Reflexivität:
Sei $x [mm] \in \Sigma^{\star}$ [/mm] beliebig. Durch Anhängen einer beliebigen Zeichenkette aus [m]\Sigma^{\star}[/m] an x, erhalten wir eine Zeichenkette, die entweder in L oder nicht in L ist. Dies ist also eine wahre oder falsche Aussage, die wir mit A bezeichnen. Dann gilt nach Booleschen Gesetzen:
[m]A \Leftrightarrow A \equiv AA + \bar A\bar A \equiv A + \bar A \equiv {\text{WAHR}}[/m], somit ist [mm] $R_L$ [/mm] in diesem Falle immer erfüllt.
Symmetrie:
Ein Äquivalenzpfeil wirkt in beide Richtungen, woraus eigentlich sofort die Symmetrie von [mm] $R_L$ [/mm] folgt, weil diese ja einen solchen Pfeil verwendet.
Transitivität:
Zu zeigen ist: [m]\forall a,b,c \in \Sigma ^{\star} :\left( {\left( {a\;R_L \;b} \right) \wedge \left( {b\;R_L \;c} \right)} \right) \Rightarrow \left( {a\;R_L \;c} \right)[/m]. Seien a, b und c beliebig. Dann überprüfen wir den Wahrheitsgehalt folgender Aussage: [m]\begin{gathered}
\left( {a\;R_L \;b} \right) \wedge \left( {b\;R_L \;c} \right) \Rightarrow \left( {a\;R_L \;c} \right) \equiv \forall d \in \Sigma ^{\star} :\left( {\underbrace {ad \in L}_A \Leftrightarrow \underbrace {bd \in L}_B} \right) \wedge \left( {\underbrace {bd \in L}_B \Leftrightarrow \underbrace {cd \in L}_C} \right) \Rightarrow \left( {\underbrace {ad \in L}_A \Leftrightarrow \underbrace {cd \in L}_C} \right) \hfill \\
\equiv \forall d \in \Sigma ^{\star} :\left( {A \Leftrightarrow B} \right) \wedge \left( {B \Leftrightarrow C} \right) \Rightarrow \left( {A \Leftrightarrow C} \right) \hfill \\
\end{gathered}[/m]
Nach Booleschen Gesetzen gilt:
[m]\begin{gathered}
\forall d \in \Sigma ^{\star} :\left( {A \Leftrightarrow B} \right) \wedge \left( {B \Leftrightarrow C} \right) \Rightarrow \left( {A \Leftrightarrow C} \right) \hfill \\
\equiv \left( {AB + \bar A\bar B} \right)\left( {BC + \bar B\bar C} \right) \Rightarrow \left( {AC + \bar A\bar C} \right) \hfill \\
\equiv \left( {ABC + \bar A\bar B\bar C} \right) \Rightarrow \left( {AC + \bar A\bar C} \right) \hfill \\
\equiv \overline {\left( {ABC + \bar A\bar B\bar C} \right)} + \left( {AC + \bar A\bar C} \right) \equiv \overline {ABC} \overline {\bar A\bar B\bar C} + AC + \bar A\bar C \hfill \\
\equiv \left( {\bar A + \bar B + \bar C} \right)\left( {A + B + C} \right) + AC + \bar A\bar C \hfill \\
\equiv \bar AB + \bar AC + A\bar B + \bar BC + A\bar C + B\bar C + AC + \bar A\bar C \hfill \\
\equiv \bar AB + \bar AC + \bar A\bar C + A\bar B + \bar BC + A\bar C + B\bar C + AC \hfill \\
\equiv \bar A\left( {B + \left( {C + \bar C} \right)} \right) + A\bar B + \bar BC + A\bar C + B\bar C + AC \hfill \\
\equiv \bar A\left( {B + {\text{WAHR}}} \right) + A\bar B + \bar BC + A\bar C + B\bar C + AC \hfill \\
\equiv \bar A + A\bar B + \bar BC + A\bar C + B\bar C + AC \hfill \\
\equiv A\bar B + A\bar C + AC + \bar A + \bar BC + B\bar C \hfill \\
\equiv A\left( {\bar B + \bar C + C} \right) + \bar A + \bar BC + B\bar C \equiv A + \bar A + \bar BC + B\bar C \hfill \\
\equiv {\text{WAHR}} + \bar BC + B\bar C \equiv {\text{WAHR}} \hfill \\
\end{gathered}[/m]
Und damit wäre doch auch die Transitivität bewiesen oder nicht? Was mich allerdings etwas stört, ist, daß ich bei diesem Beweis von der Annahme ausgegangen bin. Ich beruhige mich aber damit, daß ich doch (jetzt wo ich den Weg kenne) genauso gut von hinten anfangen könnte:
[m]\forall d \in \Sigma ^{\star} :{\text{WAHR}} \equiv \ldots \equiv \left( {A \Leftrightarrow B} \right) \wedge \left( {B \Leftrightarrow C} \right) \Rightarrow \left( {A \Leftrightarrow C} \right)[/m] und dann bin ich also doch nicht von der Annahme ausgegangen. Also ist mein Beweis richtig, oder nicht?
Danke!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:50 Mo 28.02.2005 | | Autor: | Lizard |
Hallo,
> Was mich allerdings etwas stört, ist, daß ich bei
> diesem Beweis von der Annahme ausgegangen bin. Ich beruhige
> mich aber damit, daß ich doch (jetzt wo ich den Weg kenne)
> genauso gut von hinten anfangen könnte
Also, nachdem ich mich jetzt davon überzeugt habe, daß alle deine Umformungen Äquivalenzumformungen sind, würde ich dir da Recht geben. Probleme würdest du nur bekommen, wenn du irgendwo eine Implikation erzeugt hättest (d.h. eine Umformung verwendet hättest, die nur in eine Richtung gültig ist). Das sehe ich in dem Beweis nirgendwo, und würde so für dessen Richtigkeit plädieren. Ist aber sicher besser, wenn du ihn dann auch "von hinten nach vorne" aufschreibst ;)
Ansonsten, schön formatiertes Posting. Mehr davon!
|
|
|
| |
|
Hallo Lizard,
Danke für deine Antwort! Leider zweifele ich immer noch, ob ich den Beweis in einer solchen Form führen darf, weil ich ja auch aus einer falschen Aussage etwas Wahres folgern kann. Ich habe bisher das Gefühl, daß ich die Aussage durch sich selbst "bewiesen" habe. Deshalb habe ich jetzt die Frage auch in der Newsgroup de.sci.informatik.misc ![[]](/images/popup.gif) gestellt.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:34 Di 01.03.2005 | | Autor: | Lizard |
Hallo,
natürlich kannst du aus einer Implikation beliebiges folgern, wenn die Prämisse nicht wahr ist, ich kann dein Unbehagen also verstehen. Du musst dir aber darüber klar werden, daß es in deinem Beweis zwei verschiedene Arten von Implikationen geben kann:
1) Die, vor der du Angst hast. Dies wäre eine Implikation im "Beweisfluss", d.h. wenn du dir den Beweis als Abfolge von Umformungen von Aussagen [mm] $A_1$ [/mm] bis [mm] $A_n$ [/mm] vorstellst, bekommst du so etwas:
[mm] $A_1 \gdw A_2 \gdw [/mm] ... [mm] \gdw A_i \Rightarrow A_{i+1} \gdw [/mm] ... [mm] \gdw A_n$. [/mm] Hier wäre es nun unzulässig, von [mm] $A_n$ [/mm] auf [mm] $A_1$ [/mm] zu schließen, da du ja in der Mitte eine Implikation stehen hast.
2) Eine Implikation, die in einer der Aussagen steht. Damit bekommst du keine Probleme, denn du schließt überhaupt nicht von der Konklusion auf die Prämisse, sondern betrachtest die Implikation einfach als eindeutig festlegbaren Wahrheitswert (was ja sicherlich nicht falsch ist).
Also: Meiner Meinung nach ist hier Fall 2) gegeben, da du ja eine Implikation beweisen sollst, also zeigen sollst: Die mit dieser Implikation gegebene Aussage ist wahr. Dabei interessiert uns gar nicht, ob die Prämisse immer erfüllt ist (und es würde ja auch anschaulich gar keinen Sinn ergeben, wenn das so wäre). Fall 1) hatte ich in meinem alten Post ausgeschlossen, alle deine Umformungen sind Äquivalenzumformungen (denke ich jedenfalls).
Naja, ich bin natürlich trotzdem auch gespannt auf eine Zweitmeinung. Ich verfolge das dann allerdings in meinem Newsreader, Google-Link ist also höchstens für die bessere Nachvollziehbarkeit durch die Nachwelt nötig ;)
|
|
|
|
