0 Daumen
489 Aufrufe

ich habe zwei aussagenlogische Formeln gegeben und soll über eine Resolution beweisen dass die semantische Folgerung gilt (Beta folgt semantisch aus alpha).

α = (A ∧ ¬B ∧ ¬C ∧ (B ∨ C) ∧ (¬A ∨ C) ∧ (¬A ∨ B)) ∨ (¬A ∧ B ∧ ¬C)

β = ¬A ∧ B

Problem/Ansatz:

Ich habe Alpha in KNF überführt:

alpha = (A v B) ∧ (A v ¬C) ∧ (¬B v ¬A) ∧ (¬B v ¬C) ∧ ¬C ∧ (¬C v ¬A) ∧ (B v C v ¬A) ∧ (B v C) ∧ (B v C v ¬C) ∧ (¬A v C v ¬C) ∧ (¬A v B) ∧ (¬A v B v ¬C)

Danach habe ich Beta negiert und folgendes erhalten:

beta = (A v ¬B)

Nun können wir eine Resolution machen: ich habe mich hierbei an der Klausel "(¬A v B)" aus alpha und der Klausel "(A v ¬B)" aus beta bedient. Diese heben sich ja direkt gegenseitig auf, wodurch ich die leere Resolvente erhalte...

Die leere Resolvente steht ja wie wir wissen für einen Widerspruch.

Da wir mit einer Resolution von alpha ∧ ¬(beta), die leere Resolvente erhalten, bedeutet dies dass Beta aus alpha semantisch folgt...

Habe ich bei der Überführung von alpha in die KNF einen Fehler gemacht ? Wie sieht mein Resolutionsverfahren aus? Kann ich mich einfach beliebiger Klauseln oder auch einzelnen Atomen bedienen und einfach beide resolvieren oder muss ich alle Klauseln benutzen ?


Vielen Dank im Voraus


MfG :)

Tossi93

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Aloha :)

Mit der Überführung in eine KNF machst du dir unnötig arbeit, du sollst ja eigentlich nur \(\alpha\) und \(\beta\) vergleichen. Ich schlage daher, vor \(\alpha\) zu vereinfachen. Um Klammern zu sparen, schreibe ich im Folgenden \(\cdot\) statt \(\land\) und \(+\) statt \(\lor\) und es gelte Punkt-vor-Strichrechnung:

$$\alpha = (A ∧ ¬B ∧ ¬C ∧ (B ∨ C) ∧ (¬A ∨ C) ∧ (¬A ∨ B)) ∨ (¬A ∧ B ∧ ¬C)$$$$\phantom{\alpha}= A\,\overline B\,\overline C\, (B + C)(\overline A + C)(\overline A + B) + \overline A\,B\,\overline C$$$$\phantom{\alpha}= (\underbrace{A\,\overline B\,\overline C\,B}_{=0, \text{ weil } \overline B\,B=0} + \underbrace{A\,\overline B\,\overline C\,C}_{{=0, \text{ weil } \overline C\,C=0}})(\overline A + C)(\overline A + B) + \overline A\,B\,\overline C$$$$\phantom{\alpha}=\underbrace{ 0\cdot(\overline A + C)(\overline A + B)}_{=0}+ \overline A\,B\,\overline C$$Wir haben also:$$\alpha=\overline A\,B\,\overline C\quad;\quad \beta=A+\overline B$$

Wir prüfen, ob die Implilkation gilt:$$\alpha=1\implies A=0 \land B=1 \land C=0\implies\beta =0+\overline 1=0$$Da man aus etwas Wahrem immer nur etwas Wahres folgern kann, gilt \(\alpha\;\cancel\Longrightarrow\;\beta\).

Avatar von 148 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
2 Antworten
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community