Formeln < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:31 Fr 20.04.2012 | | Autor: | durden88 |
| Aufgabe | | Geben Sie ein Beispiel einer Menge von vier Formeln, die nicht erfüllbar ist aber alle echten Teilmengen sind erfüllbar! |
Hallo liebe Leute,
also die Definition geht so: Eine Menge von Formeln [mm] \summe_{}^{} [/mm] ist endlich erfüllbar, falls jede endliche Teilmenge [mm] \summe_{}^{}´ [/mm] von [mm] \summe_{}^{} [/mm] erfüllt ist.
Weiter: Eine Formel [mm] \gamma [/mm] ist erfüllbar, falls [mm] \beta(\gamma)=1. [/mm] Eine Menge ist erfüllbar, falls [mm] \beta(\gamma)nicht \vee \gamma \in \summe_{}^{}.
[/mm]
In ner Übung wurde geschrieben:
[mm] [A_0,A_1,A_2,A_3] [/mm] nicht erfüllbar, Jede echte Teilmenge ist erfüllbar.
Wieso ist denn hier nicht erfüllbar? Wie geh ich denn da vor.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:51 Fr 20.04.2012 | | Autor: | tobit09 |
Hallo durden,
> Weiter: Eine Formel [mm]\gamma[/mm] ist erfüllbar, falls
> [mm]\beta(\gamma)=1.[/mm]
Da heißt es wohl: Eine Formel [mm] $\gamma$ [/mm] ist erfüllbar, falls es eine Belegung [mm] $\beta$ [/mm] gibt mit [mm] $\beta(\gamma)$=1.
[/mm]
> Eine Menge ist erfüllbar, falls
> [mm]\beta(\gamma)nicht \vee \gamma \in \summe_{}^{}.[/mm]
So wird die genaue Definition wohl kaum lauten.
Betrachte mal
[mm] $\Sigma=\{A_1\vee A_2,\;\;A_1\vee\neg A_2,\;\;\neg A_1\vee A_2,\;\;\neg A_1\vee\neg A_2\}$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:45 Fr 20.04.2012 | | Autor: | durden88 |
Ja da fehlen die Klammern oder?
Worum geht es denn allgemein in der Definition? Eine Belegung ist wenn es eine Formel gibt die Wahr ist bzw den Wert 1 hat nicht?
Bei deiner Summe haben alle den Wahrheitswert 1, bis auf die letzte oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:05 Fr 20.04.2012 | | Autor: | tobit09 |
> Ja da fehlen die Klammern oder?
Ja. (Häufig lässt man sie weg, wenn klar ist, welche Formel gemeint ist. Aber wenn ihr das nicht so vereinbart habt, sollten die Klammern gesetzt werden.)
> Worum geht es denn allgemein in der Definition? Eine
> Belegung ist wenn es eine Formel gibt die Wahr ist bzw den
> Wert 1 hat nicht?
Falls du die Definition einer Belegung suchst, solltest du in den Vorlesungsunterlagen nachschlagen. Es bringt nicht viel, wenn ich die mir bekannte Definition angebe und sie nicht zu eurer passt.
> Bei deiner Summe haben alle den Wahrheitswert 1, bis auf
> die letzte oder?
(Es handelt sich nicht um eine Summe, sondern um eine Formelmenge [mm] $\Sigma$ [/mm] ("Sigma").)
Kommt auf die Belegung an. Unter manchen Belegungen haben die einzelnen Formeln den Wahrheitswert 1, unter anderen Belegungen den Wahrheitswert 0.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:11 Fr 20.04.2012 | | Autor: | durden88 |
Ok jetzt hast du mir das Beispiel gegeben. Und es gibt mindestens drei zusammengesetzte Formel die den Wert 1 haben und eine 0
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:16 Fr 20.04.2012 | | Autor: | tobit09 |
> Ok jetzt hast du mir das Beispiel gegeben. Und es gibt
> mindestens drei zusammengesetzte Formel die den Wert 1
> haben und eine 0
Unter jeder Belegung haben in der Tat drei der vier Formeln Wahrheitswert 1 und eine Wahrheitswert 0.
Also kann [mm] $\Sigma$ [/mm] nicht erfüllbar sein.
Noch zu überlegen ist, dass jede echte Teilmenge erfüllbar ist.
Gehört ![[]](/images/popup.gif) das hier zu eurer Vorlesung?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:21 Fr 20.04.2012 | | Autor: | durden88 |
Nee, aber danke das kann mir bestimmt weiter helfen :)
Ja, die Teilaussagen sind auch nicht erfüllbar, da wir alleine 4 Negationen haben oder?
Jetzt ist aber 2 mal der gleiche Wert negiert. Ist er dann wieder wahr?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:28 Fr 20.04.2012 | | Autor: | tobit09 |
> Nee, aber danke das kann mir bestimmt weiter helfen :)
Habt ihr denn ein Skript im Internet? Dann könnte ich gezielter auf eure Version des Stoffes eingehen.
> Ja, die Teilaussagen sind auch nicht erfüllbar, da wir
> alleine 4 Negationen haben oder?
Doch, die echten Teilmengen von [mm] $\Sigma$ [/mm] sind erfüllbar.
> Jetzt ist aber 2 mal der gleiche Wert negiert. Ist er dann
> wieder wahr?
Welche Formel soll unter welcher Belegung wahr sein?
Nimm dir alle 3-elementigen Teilmengen von [mm] $\Sigma$ [/mm] und gib jeweils eine Belegung an, unter der die jeweilige 3-elementige Teilmenge von [mm] $\Sigma$ [/mm] wahr wird.
Überlege dir dann, dass, wenn schon alle 3-elementigen Teilmengen erfüllbar sind, erst recht die 0-,1- und 2-elementigen Teilmengen erfüllbar sind.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:51 Fr 20.04.2012 | | Autor: | durden88 |
Das Skript ist leider nur bei moodle online, kannst aber auch vielleicht hier hochstellen?
Irgendwie ist bei mir dieser springende Punkt noch nicht da. Das heißt, ich definiere zuerst einmal was erfüllbar sein soll und was nicht?
Beispiel:
[mm] E=[A_0,A_1,A_2,A_3] [/mm] ist nicht erfüllbar, aber jede echte Teilmenge schon. Wieso ist E denn nicht erfüllbar?
Ich verstehe das ganze Prinzip nicht, ist das eine Herleitung zu den Wahrheitstabellen? Die kann ich z.B. perfekt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:44 Fr 20.04.2012 | | Autor: | tobit09 |
> Irgendwie ist bei mir dieser springende Punkt noch nicht
> da. Das heißt, ich definiere zuerst einmal was erfüllbar
> sein soll und was nicht?
>
> Beispiel:
>
> [mm]E=[A_0,A_1,A_2,A_3][/mm] ist nicht erfüllbar, aber jede echte
> Teilmenge schon. Wieso ist E denn nicht erfüllbar?
Ich kenne die Notation mit den eckigen Klammern leider nicht. Ist [mm] $E=\{A_0,A_1,A_2,A_3\}$ [/mm] gemeint? Dann ist E erfüllbar.
Eine Formelmenge E heißt erfüllbar, falls es eine Belegung [mm] \beta [/mm] gibt, die alle Formeln aus E gleichzeitig wahr macht, d.h. die [mm] $\beta(\gamma)=1$ [/mm] für alle [mm] $\gamma\in [/mm] E$ erfüllt.
Obiges E ist erfüllbar, wie eine beliebige Belegung [mm] $\beta$ [/mm] mit [mm] $\beta(A_0)=\beta(A_1)=\beta(A_2)=\beta(A_3)=1$ [/mm] bezeugt.
> Ich verstehe das ganze Prinzip nicht, ist das eine
> Herleitung zu den Wahrheitstabellen? Die kann ich z.B.
> perfekt.
Um zu prüfen, ob eine ENDLICHE Formelmenge [mm] $\Sigma=\{\gamma_1,\ldots,\gamma_n\}$ [/mm] erfüllbar ist, kannst du eine Wahrheitstabelle für [mm] $\gamma_1$ [/mm] bis [mm] $\gamma_n$ [/mm] anlegen. Daran kannst du dann ablesen, ob eine Belegung existiert, die alle [mm] $\gamma_1$ [/mm] bis [mm] $\gamma_n$ [/mm] gleichzeitig wahr macht.
|
|
|
|
