Logisches Programieren?
Kann mir Jemand erklären, was genau hier gemacht wird?
1 Antwort
Das ist ein sogenannter Beweis durch Widerlegung, wie der Titel der ?ich nehme an Folie? schon sagt.
Grob gesagt ist das eine Methode der logischen Beweisführung in der Aussagenlogik.
Im Prinzip wird dabei eine Aussage durch die Widerlegung ihrer Negation bewiesen.
In deinem Beispiel mit dem p und dem q wird gezeigt bzw. demonstriert, dass aus einer gegebenen Menge von Aussagen, in diesem Fall
{p, q}durch das Hinzufügen der Negation von
p ∧ qund anschließende Umformungen und Anwendungen des (ich glaube) Resolutionsprinzips letztendlich ein Widerspruch erzeugt wird. Der Widerspruch zeigt dann so gesehen, dass die ursprüngliche Negation der zu beweisenden Aussage nicht haltbar ist und bewiesen wird, dass
{p, q}tatsächlich
p ∧ qimpliziert.
Okay, verstehe. Machen wir das mal Schritt für Schritt.
Ausgangspunkt ist die Menge {p, q} und die Frage, ob daraus p ∧ q folgt.
Es wird die Negation von p ∧ q, also ¬(p ∧ q), zu der Menge hinzugefügt.
Die Aussage ¬(p ∧ q) in ¬p ∨ ¬q umgeformt. Ich glaube das Gesetz hieß Morgansche Gesetz oder sowas.
Anschließend wird durch Resolutionsregel, p mit ¬p ∨ ¬q gelöst. Daraus folgt ¬q, da p die ¬p in der Disjunktion eliminiert.
Danach wird q aus der ursprünglichen Menge mit ¬q aufgelöst. Der Schritt führt zu einem Widerspruch, da q und ¬q nicht gleichzeitig wahr sein können.
Ein Widerspruch, in deinem Bildchen dargestellt als {false}, zeigt, dass die ursprüngliche Aussage (also die Negation von p ∧ q) nicht aufrechterhalten werden kann, was bedeutet, dass die ursprüngliche Menge {p, q} tatsächlich p ∧ q impliziert.
Ich würde raten dass es so ist: Zur Menge hinzufügen was gelten muss, damit die Aussage gelten kann.
"Resolve p and ~p v ~q":
p & (~p v ~q)
= (p & ~p) v (p & ~q)
= (false v (p & ~q)
= (p & ~ q)
= {p, ~q}
und p war ja schon in der Menge
Edit: Ah, jetzt hat iSc0field ja eh geantwortet
Das habe ich verstanden, aber was mich verwirrt, bzw ich nicht verstehe, ist was genau schritt für schritt gemacht wird.
Also, dass -(p A q) zu -p V -q wird ist mir klar, aber warum danach noch ein -q dazukommt und die restlichen Schritte, verstehe ich nicht.