Aussagenlogik: unerfüllbare KNF Resolutionswiderlegung

24.11.2015, 00:58	ILackLogic	Auf diesen Beitrag antworten »
Aussagenlogik: unerfüllbare KNF Resolutionswiderlegung Hallo zusammen Ich benötige Hilfe bei den folgenden zwei Aufgaben: 1. Sei $\begin{eqnarray} \varphi \end{eqnarray}$ in KNF und unerfüllbar. Zeigen sie, dass es eine Resolutionswiderlegung von $\begin{eqnarray} \varphi \end{eqnarray}$ gibt mit höchstens $\begin{eqnarray} 2^n-1 \end{eqnarray}$ Schritten. 2. Sei $\begin{eqnarray} \varphi \end{eqnarray}$ in H-Form und unerfüllbar. Zeigen sie, dass es eine Resolutionswiderlegung von $\begin{eqnarray} \varphi \end{eqnarray}$ gibt mit höchstens n vielen Schritten. So mein Ansatz zu 1) Da $\begin{eqnarray} \varphi \end{eqnarray}$ n Variablen hat, gibt es auch $\begin{eqnarray} \{ L_1,... L_n \} \end{eqnarray}$ Literale. Wähle nun ein Literal $\begin{eqnarray} L_i \end{eqnarray}$ , so dass in der KNF mindestens ein Paar $\begin{eqnarray} c_j \end{eqnarray}$ , $\begin{eqnarray} c_k \end{eqnarray}$ gibt mit $\begin{eqnarray} L_i \in c_j \end{eqnarray}$ und $\begin{eqnarray} \bar{L_i} \in c_k \end{eqnarray}$ . Mindestens ein solches Paar muss sich finden lassen, da laut Aufgabe $\begin{eqnarray} \varphi \end{eqnarray}$ ja unerfüllbar sein soll. So jetzt bilde ich für alle solche Paare, die ich finde, die Resultionsableitung. Das wäre dann der erste Schritt der Resolutionswiderlegung. In den Klauseln, die sich jetzt neu gebildet haben tritt sowohl $\begin{eqnarray} L_i \end{eqnarray}$ als auch $\begin{eqnarray} \bar{L_i} \end{eqnarray}$ nicht mehr auf. Falls das Literal noch in Klauseln auftritt, die nicht abgeleitet wurden, so können diese vernachlässigt werden, da sich nicht mehr zur leeren Klausel abgeleitet werden können. So im nächsten Schritt würde ich jetzt einfach ein neues Literal wählen, das die gleichen Vorraussetzung wie im ersten Schritt erfüllt... Dann müsste ich ja aber nach n Ableitungsschritten schon fertig sein Und in der zweiten Aufgabe würde ich ja dann genau das gleiche machen... Also irgendwas läuft bei mir da falsch Könnte mir vielleicht jemand einen Schubser auf die richtige Spur geben? Vielen Dank im Vorraus

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »