Unendliche Formelmenge < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:58 Di 27.11.2012 | | Autor: | starki |
| Aufgabe | | Seien [mm] \Delta [/mm] eine unendliche Formelmengen und [mm] \phi [/mm] eine aussagenlogische Formel, sodass [mm] \Delta \vdash \phi [/mm] [da müssten jetzt zwei Striche sein, weiß aber nicht wie ich das hinschreiben sollte]. Zeigen Sie, dass eine endliche Teilmenge [mm] \Delta' \subset \Delta [/mm] gibt, so dass [mm] \Delta' \vdash \phi [/mm] [hier wieder zwei Striche und nicht nur eins]. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe erst einmal nur ne Frage zu der Aufgabe:
Wenn es heißt: [mm] \Delta \vdash \phi, [/mm] dann kann ich ja davon ausgehen, dass jede Belegeung, die jede Formel in [mm] \Delta [/mm] wahr machen würde, auch [mm] \phi [/mm] wahr machen würde?
Ich bin mir diesbezüglich noch nicht ganz sicher.
Ich haber bisher nur eine Idee, wie man das dann beweisen könnte: [mm] \Delta [/mm] ist ja eine unendliche Menge. Und jede Belegung, die jede Formel in [mm] \Delta [/mm] wahr machen würde, würde auf jeden Fall dann [mm] \phi [/mm] wahr machen. D.h. es reicht, eine (nichtleere) Teilmenge [mm] \Delta' [/mm] aus der unendlichen Menge [mm] \Delta [/mm] zu nehmen, dann würde genauso gelten:
[mm] \Delta' \vdash \phi, [/mm] da ja auch hier gilt: bei jeder Belegung, die jede Formel in [mm] \Delta' [/mm] wahr machen würde, auch unbedingt [mm] \phi [/mm] wahr macht.
Wäre mein Beweis richtig? Wie kann ich sowas am besten formal aufschreiben?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:53 Di 27.11.2012 | | Autor: | tobit09 |
Hallo starki und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Wenn es heißt: [mm]\Delta \vdash \phi,[/mm] dann kann ich ja davon
> ausgehen, dass jede Belegeung, die jede Formel in [mm]\Delta[/mm]
> wahr machen würde, auch [mm]\phi[/mm] wahr machen würde?
Ja, so definiert man das üblicherweise.
> Ich haber bisher nur eine Idee, wie man das dann beweisen
> könnte: [mm]\Delta[/mm] ist ja eine unendliche Menge. Und jede
> Belegung, die jede Formel in [mm]\Delta[/mm] wahr machen würde,
> würde auf jeden Fall dann [mm]\phi[/mm] wahr machen. D.h. es
> reicht, eine (nichtleere) Teilmenge [mm]\Delta'[/mm] aus der
> unendlichen Menge [mm]\Delta[/mm] zu nehmen, dann würde genauso
> gelten:
> [mm]\Delta' \vdash \phi,[/mm] da ja auch hier gilt: bei jeder
> Belegung, die jede Formel in [mm]\Delta'[/mm] wahr machen würde,
> auch unbedingt [mm]\phi[/mm] wahr macht.
Warum gibt es so ein [mm] $\Delta'$? [/mm] Genau das ist zu zeigen.
Hattet ihr den Kompaktheitssatz der Aussagenlogik? Wenn ja: In welcher Formulierung?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:58 Di 27.11.2012 | | Autor: | starki |
Ne, leider hatten wir den Kompaktheitssatz noch nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:04 Di 27.11.2012 | | Autor: | tobit09 |
> Ne, leider hatten wir den Kompaktheitssatz noch nicht.
Auch nicht unter dem Namen Endlichkeitssatz?
Ihr wisst also noch nicht, dass jede endlich erfüllbare Formelmenge erfüllbar ist?
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 09:15 Di 27.11.2012 | | Autor: | starki |
Also nicht das ich wüsste. Habe mir mal nochmal das Skript angeschaut (http://home.mathematik.uni-freiburg.de/ziegler/skripte/lfi.pdf), dort stand nichts drin, genauso wenig wie auf den Übungsblättern oder auf dem Geschreibsel des Professors (http://home.mathematik.uni-freiburg.de/ziegler/veranstaltungen/ws12-LfI.html)
EDIT: Also das Einzige was ich weiß, wäre, dass eine Formelmenge erfüllbar ist, wenn es eine Belegung gibt, für die jede Formel in der Formelmenge erfüllbar ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:43 Di 27.11.2012 | | Autor: | tobit09 |
> Also nicht das ich wüsste. Habe mir mal nochmal das Skript
> angeschaut
> (http://home.mathematik.uni-freiburg.de/ziegler/skripte/lfi.pdf),
> dort stand nichts drin, genauso wenig wie auf den
> Übungsblättern oder auf dem Geschreibsel des Professors
> (http://home.mathematik.uni-freiburg.de/ziegler/veranstaltungen/ws12-LfI.html)
Danke für die Links! Der Kompaktheitssatz der Aussagenlogik kommt in Kapitel 1.6 dran, aber anscheindend ist die Vorlesung noch nicht soweit.
Ich vermute, dass die Aufgabe nur versehentlich vor dem Kompaktheitssatz gestellt wurde. Denn aus dem Kompaktheitssatz lässt sie sich leicht folgern. Auch der Kompaktheitssatz lässt sich leicht aus dieser Aufgabe folgern. Und ein selbstständiger Beweis des Kompaktheitssatzes ohne Lösungshinweise ist aus meiner Sicht ein bisschen viel verlangt für eine gewöhnliche Übungsaufgabe.
Ich würde an deiner Stelle versuchen, kurzfristig Kontakt zum Ersteller der Übungsaufgaben aufzunehmen und nachzufragen, ob ihr die Aufgabe wirklich ohne Kenntnis des Kompaktheitssatzes lösen sollt.
Wenn du möchtest, kann ich dir auch Hinweise geben, wie du die Aufgabe trotzdem lösen kannst. Das würde allerdings sehr aufwendig.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:42 Di 27.11.2012 | | Autor: | starki |
Es wäre nicht das erste Mal, dass wir eine Aufgabe bekommen, was der Professor noch nicht in der Vorlesung vorgestellt hat ... von daher gehe ich davon aus, dass wir den Satz anwenden können.
Ich würde dann folgendes hinschreiben (ich hoffe, dass ich da nicht so falsch liege):
[mm] \Delta [/mm] ist eine unendliche Formelmenge und es gilt: [mm] \Delta \vdash \phi.
[/mm]
Angenommen, es gibt eine Belegung A, die für [mm] \Delta [/mm] erfüllbar ist, d.h. jede Formel in [mm] \Delta [/mm] wird durch diese Belegung wahr. Dann gibt es laut dem Kompaktheitssatz auch eine endliche Teilmenge [mm] \Delta', [/mm] für die gilt: [mm] \Delta' \vdash \phi.
[/mm]
Stimmt das? Kann man das auch etwas formaler schreiben oder reicht das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:12 Di 27.11.2012 | | Autor: | tobit09 |
> [mm]\Delta[/mm] ist eine unendliche Formelmenge und es gilt: [mm]\Delta \vdash \phi.[/mm]
>
> Angenommen, es gibt eine Belegung A, die für [mm]\Delta[/mm]
> erfüllbar ist, d.h. jede Formel in [mm]\Delta[/mm] wird durch diese
> Belegung wahr.
Wenn du zunächst unter dieser Annahme argumentierst, müsstest du anschließend noch den Fall behandeln, dass [mm] $\Delta$ [/mm] nicht erfüllbar ist. Einen Vorteil dieser Fallunterscheidung sehe ich nicht.
> Dann gibt es laut dem Kompaktheitssatz auch
> eine endliche Teilmenge [mm]\Delta',[/mm] für die gilt: [mm]\Delta' \vdash \phi.[/mm]
Warum?
Der Kompaktheitssatz sagt (in Kontraposition formuliert): Jede nicht erfüllbare Formelmenge besitzt eine endliche Teilmenge, die schon nicht erfüllbar ist.
Zeige: [mm] $\Delta\vdash \phi$ [/mm] impliziert, dass [mm] $\Delta\cup\{\neg\phi\}$ [/mm] nicht erfüllbar ist.
Wende dann den Kompaktheitssatz auf [mm] $\Delta\cup\{\neg\phi\}$ [/mm] an.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:45 Di 27.11.2012 | | Autor: | starki |
Ich habs mal so versucht, wie du mir geraten hast:
[mm] \Delta \vdash \phi.d.h. [/mm] jede Belegung A, die jede Formel in [mm] \Delta [/mm] wahr macht, macht auch [mm] \phi [/mm] wahr. Würde jedoch gelten [mm] \Delta \cup [/mm] { [mm] \neg \phi [/mm] }, dann wäre [mm] \Delta \cup [/mm] { [mm] \neg \phi [/mm] } nicht erfüllbar, d.h. es gäbe keine Belegung, die alle Formeln wahr macht. Laut Kompaktheitssatz hat jeder nicht erfüllbare Formelmenge eine endliche Teilmenge, die schon nicht erfüllbar ist. => [mm] \Delta [/mm] hat eine endliche Menge [mm] \Delta', [/mm] für die gilt: [mm] \Delta' \vdash \phi.
[/mm]
Wie sieht es nun mit der Lösung aus?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:23 Di 27.11.2012 | | Autor: | tobit09 |
> [mm]\Delta \vdash \phi.d.h.[/mm] jede Belegung A, die jede Formel in
> [mm]\Delta[/mm] wahr macht, macht auch [mm]\phi[/mm] wahr. Würde jedoch
> gelten [mm]\Delta \cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
$\{$ [mm]\neg \phi[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
$\}$,
Was meinst du damit, dass eine Formelmenge "gilt"?
> dann wäre [mm]\Delta \cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
$\{$
> [mm]\neg \phi[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
$\}$ nicht erfüllbar, d.h. es gäbe keine Belegung,
> die alle Formeln wahr macht.
$\Delta\cup\{\neg\phi\}$ IST nicht erfüllbar.
Denn angenommen, diese Formelmenge wäre erfüllbar. Dann gäbe es eine Belegung, die jede Formel aus $\Delta$ und die Formel $\neg\phi$ wahr macht. Also kann diese Belegung die Formel $\phi$ nicht wahr machen. Widerspruch zu $\Delta\vdash\phi$.
> Laut Kompaktheitssatz hat
> jeder nicht erfüllbare Formelmenge eine endliche
> Teilmenge, die schon nicht erfüllbar ist. => [mm]\Delta[/mm] hat
> eine endliche Menge [mm]\Delta',[/mm] für die gilt: [mm]\Delta' \vdash \phi.[/mm]
Warum?
Der Kompaktheitssatz liefert, dass [mm] $\Delta\cup\{\neg\phi\}$ [/mm] eine endliche Teilmenge [mm] $\Delta''$ [/mm] besitzt, die schon nicht erfüllbar ist.
Betrachte nun [mm] $\Delta':=\Delta''\cap\Delta$. [/mm] Dies ist eine endliche Teilmenge von [mm] $\Delta$.
[/mm]
Hilfsbehauptung: Es gilt [mm] $\Delta''\subseteq\Delta'\cup\{\neg\phi\}$.
[/mm]
Sei dazu [mm] $\psi\in\Delta''$. [/mm] Wegen [mm] $\Delta''\subseteq\Delta\cup\{\neg\phi\}$ [/mm] gilt dann [mm] $\psi\in\Delta$ [/mm] oder [mm] $\psi\in\{\neg\phi\}$. [/mm] Im letzteren Fall ist [mm] $\psi\in\Delta'\cup\{\neg\phi\}$. [/mm] Im ersteren Fall ist wegen [mm] $\psi\in\Delta''\cap\Delta=\Delta'$ [/mm] ebenfalls [mm] $\psi\in\Delta'\cup\{\neg\phi\}$. [/mm] Damit ist die Hilfsbehauptung gezeigt.
Behauptung: [mm] $\Delta'\vdash\phi$.
[/mm]
Sei also $B$ eine Belegung, die [mm] $\Delta'$ [/mm] wahr macht. Zu zeigen ist, dass $B$ auch [mm] $\phi$ [/mm] wahr macht.
Angenommen $B$ macht [mm] $\phi$ [/mm] nicht wahr. Was sagt das über $B$ und [mm] $\neg\phi$ [/mm] sowie damit über $B$ und [mm] $\Delta'\cup\{\neg\phi\}$ [/mm] aus? Was sagt das wiederum gemäß der Hilfsbehauptung über $B$ und [mm] $\Delta''$ [/mm] aus? Leite so einen Widerspruch her.
|
|
|
|
