www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Aussagenlogik" - Formeln
Formeln < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Formeln: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Formeln: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Formeln: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Formeln: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                
Bezug
Formeln: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                        
Bezug
Formeln: Antwort
Status: (Antwort) fertig Status 
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 []das hier zu eurer Vorlesung?

Bezug
                                                
Bezug
Formeln: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                        
Bezug
Formeln: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                                
Bezug
Formeln: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                                                        
Bezug
Formeln: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]