Obermengenbeweis Kleene'sche Hülle

Question

Frage:

Es soll formal bewiesen werden, dass die folgende Gleichung richtig/falsch ist.

$$(A \cap B)^* \supseteq (A^*\cap B)^*$$

wobei gilt, dass sowohl A als auch B beliebige Teilmengen von $$\{0,1\}^*$$ sind.

Wie geht man einen solchen Beweis generell an? Ich kann mir nicht wirklich etwas unter der Schnittmenge $$(A \cap B)^*$$ vorstellen, da durch die Kleene'sche Hülle doch eine unendliche Menge gebildet wird.

Answer 1

Hallo,

Gleichung richtig/falsch ist.

Es handelt sich hier um Teilmengenbeziehungen.

Probiere doch mal diese Teilmengen aus:

\(A:=\{0,1\}\subseteq \{0,1\}^*,\quad B:=\{11\}\subseteq \{0,1\}^*\)

Die kleene'sche Hülle von \(\{0,1\}\) hat ja diese Gestalt:

\(\{0,1\}^*=\{\varepsilon,0,1,00,01,10,11,000,001,010,011,100,101,110,111,...\}\), wobei \(\varepsilon\) das leere Wort ist. Bilde nun skuzessive die Mengen, die in der Behauptung vorkommen, und schaue nach, ob diese Inklusion erfüllt ist.