0 Daumen
418 Aufrufe

Aufgabe:

Für beliebige formale Sprachen L, Li, Lk ⊆ A∗ definieren wir das sogenannte Komplement Lc von L, sowie die binäre Operation ∩c : P(A∗) ×P(A∗) →P(A∗) als:
Lc := A* \ L                      Li c Lk := (Li ∩ Lk)c

Beweisen Sie:
• L1 ∩ L2 = (Lc1 ∪ Lc2 )c
• L1 ∪ L2 = (Lc1 ∪ Lc2 )c


Problem/Ansatz:

Man soll da mit dem Distributivgesetz argumentieren. Ich finde da aber keinen Beweisansatz.

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Beweis des ersten Teils: \(L_1 \cap L_2 = (L_1^c \cup L_2^c)^c\)

Um diesen Teil zu beweisen, zeigen wir die Gleichheit durch die Überprüfung der beiden Inklusionen:

1. \(L_1 \cap L_2 \subseteq (L_1^c \cup L_2^c)^c\)
2. \((L_1^c \cup L_2^c)^c \subseteq L_1 \cap L_2\)

1. Schritt: \(L_1 \cap L_2 \subseteq (L_1^c \cup L_2^c)^c\)

Nehmen wir ein Element \(x\) aus \(L_1 \cap L_2\), dann gilt, dass \(x \in L_1\) und \(x \in L_2\). Das bedeutet, dass \(x\) nicht in dem Komplement von \(L_1\) oder \(L_2\) sein kann, d.h., \(x \notin L_1^c\) und \(x \notin L_2^c\). Weil \(x\) in keinem der beiden Komplemente ist, ist es auch nicht in der Vereinigung der Komplemente, was bedeutet \(x \notin (L_1^c \cup L_2^c)\). Wenn \(x\) nicht in \((L_1^c \cup L_2^c)\) ist, muss es im Komplement dieser Vereinigung sein, also \(x \in (L_1^c \cup L_2^c)^c\). Das bestätigt die erste Inklusion.

2. Schritt: \((L_1^c \cup L_2^c)^c \subseteq L_1 \cap L_2\)

Nehmen wir ein Element \(x\) aus \((L_1^c \cup L_2^c)^c\), was bedeutet, dass \(x \notin L_1^c \cup L_2^c\). Das impliziert, dass \(x\) nicht in \(L_1^c\) und nicht in \(L_2^c\), da es nicht in deren Vereinigung ist. Wenn \(x\) nicht im Komplement von \(L_1\) und \(L_2\) ist, dann muss \(x\) in \(L_1\) und \(L_2\) sein, also \(x \in L_1\) und \(x \in L_2\), was bedeutet, dass \(x \in L_1 \cap L_2\). Das bestätigt die zweite Inklusion und schließt den Beweis für diesen Teil ab.

Beweis des zweiten Teils: \(L_1 \cup L_2 = (L_1^c \cup L_2^c)^c\)

Hier scheint es einen Fehler in der Aufgabenstellung zu geben, da die angegebene Behauptung \(L_1 \cup L_2 = (L_1^c \cup L_2^c)^c\) nicht korrekt ist. Stattdessen sollte die zu beweisende Gleichheit \(L_1 \cup L_2 = (L_1^c \cap L_2^c)^c\) lauten, was dem De Morgan'schen Gesetz entspricht. Wir beweisen somit die korrigierte Behauptung:

1. \(L_1 \cup L_2 \subseteq (L_1^c \cap L_2^c)^c\)
2. \((L_1^c \cap L_2^c)^c \subseteq L_1 \cup L_2\)

1. Schritt: \(L_1 \cup L_2 \subseteq (L_1^c \cap L_2^c)^c\)

Nehmen wir ein Element \(x\) aus \(L_1 \cup L_2\). Das bedeutet, dass \(x\) entweder in \(L_1\) oder in \(L_2\) oder in beiden ist. Demnach kann \(x\) nicht gleichzeitig im Komplement von \(L_1\) und \(L_2\) sein, was impliziert \(x \notin L_1^c\) oder \(x \notin L_2^c\), und folglich ist \(x\) nicht in deren Schnitt, also \(x \notin (L_1^c \cap L_2^c)\). Wenn \(x\) nicht im Schnitt der Komplemente ist, liegt es im Komplement des Schnitts: \(x \in (L_1^c \cap L_2^c)^c\).

2. Schritt: \((L_1^c \cap L_2^c)^c \subseteq L_1 \cup L_2\)

Wenn ein Element \(x\) in \((L_1^c \cap L_2^c)^c\) enthalten ist, bedeutet dies, dass \(x \notin (L_1^c \cap L_2^c)\), also kann \(x\) nicht gleichzeitig in \(L_1^c\) und in \(L_2^c\) sein. Das heißt, \(x\) muss in \(L_1\) oder in \(L_2\) (oder in beiden) sein, also \(x \in L_1 \cup L_2\).

Damit sind beide Inklusionen für die richtig formulierte Behauptung gezeigt, und der Beweis für die Gleichheit \(L_1 \cup L_2 = (L_1^c \cap L_2^c)^c\) ist vollständig.
Avatar von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community