Entscheidbare Menge < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:40 Mo 30.06.2008 | | Autor: | Parkan |
| Aufgabe | Zeigen Sie durch drei einfache Konstruktionen unter Rückgriff auf die Definition von Entscheidbare
Menge, dass die Familie Rec der entscheidbaren Mengen eine boolesche Mengenalgebra ist. Beweisen Sie für Sprachen L1,L2 [mm] \in \IZ [/mm] * (<-Sigma Stern) folgenden drei Aussagen: (Dabei
sollen mindestens zwei der drei Beweise durch direkten Rückgriff auf die Definition erfolgen!)
Für L1 [mm] \in [/mm] Rec und L2 [mm] \in [/mm] Rec gilt auch L1 [mm] \cup [/mm] L2 [mm] \in [/mm] Rec;
Für L1 [mm] \in [/mm] Rec und L2 [mm] \in [/mm] Rec gilt auch L1 [mm] \cap [/mm] L2 [mm] \in [/mm] Rec;
Für L1 [mm] \in [/mm] Rec gilt auch [mm] \IZ [/mm] * (<- Sigma Stern) \ L1 [mm] \in [/mm] Rec
|
Hallo
Ich Sitze wieder an einer Aufgabe die für mich unüberwindbar scheint.
Meine Frage ist hier, wie die Definition für Entscheidbare Mengen ist. Ein Ansatz wie ich die 3 Sätze nach der Definition Konstruire und Beweise wäre mir ebenfalls sehr sehr hilfreich.
Ich weis das hier im Forum mehr Eigeninitiative gefordert wird. Aber bei der Aufgabe habe ich leider garkeine Ideen.
Danke trozdem für jeden der mir Tipps gibt.
EDIT: Hier erstmal das was ich versucht habe. Ich denk aber das es als Beweis nicht reicht.
Aus der Definition ergibt sich.
Alle endlichen Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen sind entscheidbar.
Zu jeder entscheidbare Menge ist auch sein Komplement entscheidbar. Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.
Ist L1 Entscheidbar und L2 entscheidbar so gilt nach der Definition dann auch L1⋃L2.
Ist L1 Entscheidbar und L2 entscheidbar so gilt nach der Definition dann auch L1⋂L2
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:25 Mi 02.07.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
