matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikKlauselmenge und Resolventenve
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Mathematik" - Klauselmenge und Resolventenve
Klauselmenge und Resolventenve < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Klauselmenge und Resolventenve: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:29 So 17.09.2006
Autor: Binky

Aufgabe
Die Klauselmenge M sei definiert durch M{K1,K2,K3} mit K1{A,B,C} [mm] K2{\neg A, \neg B} K3{\neg C} [/mm]
Beantworten mit ja bzw. nein

1.Die Klauselmenge M ist erfüllbar.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
3. K1 und K2 haben mindestens zwei Resolventen.
4. K1 und K2 haben mindestens eine Tautologie als Resolvente.

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Hallo, bei dieser Frage weiß ich einfach nicht weiter und finde leider auch kein gescheites Material zu Resolventen und Tautologie.

Könnte mir jemand das Resolventenverfahren erklären bzw. kurz anreißen um mir auf die Sprünge zu helfen? Ich sollte es eigentlich schon einmal in der Vorlesung gehört haben aber ich steh mal wieder aufm Schlauch.

Gruß

Alex

        
Bezug
Klauselmenge und Resolventenve: Antwort
Status: (Antwort) fertig Status 
Datum: 09:58 Mo 18.09.2006
Autor: mathiash

Hallo und guten Morgen,

in Standard-Lehrbüchern der Logik und Theoretischen Informatik wird das Verfahren erklärt,
hinreichend informativ ist auch der Eintrag bei Wikipedia.

Wir haben allgemein eine Menge von Klauseln [mm] \{C_1,\ldots , C_m\} [/mm] gegeben und fragen nach der simultanen Erfüllbarkeit dieser.
Wenn ein Literal L in [mm] C_i [/mm] ist und [mm] \overline{L}\in C_j, [/mm] so gilt

[mm] (C_i\wedge C_j)\longrightarrow C_R [/mm]

für die Klausel [mm] C_R:= (C_i\cup C_j)\setminus\{L,\overline{L}\} [/mm]

[mm] C_R [/mm] heisst Resolvente von [mm] C_i, C_j. [/mm]

Wenn also  [mm] C_1\wedge\ldots \wedge C_m [/mm] erfüllbar ist, so auch die Formel   [mm] C_1\wedge\ldots\wedge C_m\wedge \bigwedge_{C\in Res(C_1,\ldots , C_m)\} [/mm]

wobei

[mm] Res(C_1,\ldots [/mm] , [mm] C_m) [/mm] die Menge aller Resolventen in obigem Sinne ist.

Man kann nun das Resolventenbildungsverfahren iterieren. Erhält man dabei irgendwann die leere Klausel, so ist die ursprüngliche Formel nicht erfüllbar.

Gruss,

Mathias


Bezug
                
Bezug
Klauselmenge und Resolventenve: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:52 Mo 18.09.2006
Autor: Binky

Hallo,

tut mir wirklich leid aber z.B. den Wiki Artikel habe ich auch gefunden. Könntest du mir diese Aussagen mal an Beispielen verdeutlichen?

Gruß

Binky

Bezug
                        
Bezug
Klauselmenge und Resolventenve: Antwort
Status: (Antwort) fertig Status 
Datum: 17:07 Mo 18.09.2006
Autor: mathiash

Hallo Binky,

es sei  [mm] C_1= A\vee [/mm] B [mm] \vee [/mm] C

und [mm] C_2 [/mm] = [mm] \neg A\vee D\vee [/mm] E,

dann ist die Resolvente der beiden gegeben durch

[mm] B\vee C\vee D\vee [/mm] E

Du siehst hier an dem Beispiel: Egal, welchen Wahrheitswert A bekommt, kann es nicht gleichzeitig [mm] C_1 [/mm] und [mm] C_2 [/mm] erfüllen, sondern wird genau eine
der beiden Klauseln erfüllen. Die andere muss dann durch eine der anderen in ihr vorkommenden Variablen erfüllt werden.

Wird umgekehrt die Resolvente erfüllt, so wird also durch die entsprechende Belegung mindestens eine der beiden Klauseln erfüllt, und die andere kann
dann in jedem Fall durch geeignete Belegung von A wahr gemacht werden.

Gruss,

Mathias

Bezug
                                
Bezug
Klauselmenge und Resolventenve: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:32 Mo 18.09.2006
Autor: Binky

Aufgabe
Die Klauselmenge M sei definiert durch M{K1,K2,K3} mit K1{A,B,C}
Beantworten mit ja bzw. nein

1.Die Klauselmenge M ist erfüllbar.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
3. K1 und K2 haben mindestens zwei Resolventen.
4. K1 und K2 haben mindestens eine Tautologie als Resolvente.

Danke schon mal,

wenn ich das nun richtig verstanden habe, würde ich die Fragen so beantworten:

1.Die Klauselmenge M ist erfüllbar.
Nein ist sie nicht.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
Ja, da jedes A,B,C durch [mm] \neg [/mm] A, [mm] \neg [/mm] B, [mm] \neg [/mm] C in der Klauselmenge zur leeren Klausel wird.
3. K1 und K2 haben mindestens zwei Resolventen.
Nein. Sie haben nur die gemeinsame Klauselmenge {C}
4. K1 und K2 haben mindestens eine Tautologie als Resolvente.
Ja, {C}, da C immer wahr ist (Tautologie)

Stimmt dieses soweit oder habe ich es dennoch falsch verstanden?

Gruß

Alex

Bezug
                                        
Bezug
Klauselmenge und Resolventenve: Antwort
Status: (Antwort) fertig Status 
Datum: 10:36 Di 19.09.2006
Autor: mathiash

Hallo und guten Morgen,



>  
> 1.Die Klauselmenge M ist erfüllbar.
>  Nein ist sie nicht.

Doch.

ZB  A=1, B=0, C=0 erfüllt [mm] K_1,K-2,K_3 [/mm]

(Beachte: Klauseln sind Disjunktionen, also Veroderungen von Literalen).


> 2. Die leere Klausel lässt sich aus M mit dem
> Resolventenverfahren ableiten.
> Ja, da jedes A,B,C durch [mm]\neg[/mm] A, [mm]\neg[/mm] B, [mm]\neg[/mm] C in der
> Klauselmenge zur leeren Klausel wird.

Die leere Klausel lässt sich nicht ableiten.

>  3. K1 und K2 haben mindestens zwei Resolventen.
> Nein. Sie haben nur die gemeinsame Klauselmenge {C}

Es ist doch [mm] K_1=A\vee B\vee [/mm] C, [mm] \: K_2= \neg A\vee \neg [/mm] B

damit sind  [mm] A\vee C\vee \neg [/mm] A und [mm] B\vee C\vee\neg [/mm] B

Resolventen ,

die sich aber sofort beide als zu der Klausel  1 äquivalent erweisen.

Gruss,

Mathias

>  4. K1 und K2 haben mindestens eine Tautologie als
> Resolvente.
>  Ja, {C}, da C immer wahr ist (Tautologie)
>  
> Stimmt dieses soweit oder habe ich es dennoch falsch
> verstanden?
>  
> Gruß
>  
> Alex

Bezug
                                                
Bezug
Klauselmenge und Resolventenve: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:18 Di 19.09.2006
Autor: Binky

Hallo,

also wird doch etwas schwieriger.

Ich habe also die Klauselmenge M { [mm] K_1,K_2,K_3 [/mm] } mit [mm] K_1 [/mm] { A,B,C } , [mm] K_2 [/mm] { [mm] \neg [/mm] A, [mm] \neg [/mm] B } und [mm] K_3 [/mm] mit { [mm] \neg [/mm] C }
Daraus kann ich doch die folgenden Klauseln bilden:

{C} aus {A,B,C} und { [mm] \neg [/mm] A, [mm] \neg [/mm] B }
{A,B} aus {A,B,C} und { [mm] \neg [/mm] C }
Und daraus doch jeweils auch die leere Klausel oder?

Habe dazu dieses Beispiel gefunden:
M= {{A,B, [mm] \neg [/mm] C }, { [mm] \neg [/mm] A}, {A,B,C}, {A, [mm] \neg [/mm] B }}

Daraus bilden sich die Klauseln:
{A,C} aus {A,B,C} und {A, [mm] \neg [/mm] B }
{A,B} aus {A,B, [mm] \neg [/mm] C} und {A,C}
{A} aus {A, [mm] \neg [/mm] B } und {A,B}

daher die leere Klausel aus {A} und { [mm] \neg [/mm] A}

Das ist doch soweit richtig zum Verständnis zur Klauselbildung oder?

Gruß
Alex

Bezug
                                                        
Bezug
Klauselmenge und Resolventenve: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:58 Mi 20.09.2006
Autor: Binky

Ich habs mitlerweile begriffen. Habe leider auch das Fach schaltwerke und rechnerorganisation und das darf man nicht vermischen.

die resolventen aus K1 und K2 sind also ( B, [mm] \neg [/mm] B , C) und (A, [mm] \neg [/mm] A, C)
das sagt auch gleichzeitig aus, dass es zwei tautologien zwischen K1 und K2 gibt.
Damit wären die Fragen 3 und 4 erledigt.

Es gibt noch eine weitere Resolvente (A,B) mit K1 und K3.

Wenn man sich dieses nun genau ansieht erkennt man auch dass M erfüllbar ist und sich nicht die leere Klausel für M aus dem Resolventenverfahren erzeugen lässt.

Danke noch mal für Mühe und Geduld mit mir.

Gruß

Binky

Bezug
                                                                
Bezug
Klauselmenge und Resolventenve: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:25 Do 21.09.2006
Autor: mathiash

Hallo Alex,

keine Ursache !  Na dann weiterhin frohes Lernen !

Gruss,

Mathias

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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]