Abschließende Betrachtung von Logiken
(Logik Einführung Kapitel 8)
Grundsätzlich besteht eine Logik aus einer
- Syntax (meist im Rahmen eines Kalküls definiert), durch die die formale Sprache definiert wird
- und einer dazugehörigen Semantik, die den abstrakten Zeichenfolgen wiederum Bedeutung zuweist.
Für verschiedene Problemstellung lassen sich verschiedene Logiken aufbauen.
In diesem Kapitel wollen wir einige wichtige Konzepte und Fragestellungen zur Klassifizierung anführen,
bemerken, dass ein und dieselbe Logik durch unterschiedliche Kalküle definiert werden kann,
und Fragen zu Einsatzmöglichkeiten von Logiken stellen.
Klassifizierung von Logiken
(Logik Einführung Kapitel 8.1)
Je nach Anwendung/Problemstellung lassen sich unterschiedliche Logiken aufbauen.
Die Klassifizierung des logischen Systems hängt u.a. von folgenden Fragen ab:
- Für wie viele mögliche Bewertungen interessieren wir uns?
Haben wir eine Logik mit m (wobei m eine endliche Zahl ist) Wahrheitswerten, sprechen wir von einer m-wertigen Logik.
- Bleibt eine einmal bewiesene Aussage immer gültig, oder kann sie durch neu hinzukommendes Wissen revidiert werden?
Die Monotonie ist eine Eigenschaft von Logiken, die besagt, dass eine Aussage, die aus einer Menge von Annahmen folgt, auch dann noch folgt, wenn weitere Annahmen hinzukommen.
- Extensionalität: Ist die Bewertung einer zusammengesetzten Aussage eindeutig durch die Bewertung ihrer Teilaussagen bestimmt?
- 2-wertig und
- extensional
sprechen wir von einer klassischen Logik.
Für klassische Logiken gilt die Monotonieeigenschaft.
Zu den klassischen Logiken gehören z.B. die Aussagenlogik und die Prädikatenlogik.
Gilt mindestens eine der oben genannten Eigenschaften nicht, sprechen wir von einer nichtklassischen Logik.
- Gilt das Prinzip der Zweiwertigkeit nicht, sagen wir, die Logik ist mehrwertig.
- Fällt das Prinzip der Extensionalität weg, entsteht eine intentionale Logik, wie z.B. die Modallogik.
- Fehlt die Eigenschaft der Monotonie, sprechen wir von einer nichtmonotonen Logik.
Unterschiedliche Kalküle, gleiche Logik
(Logik Einführung Kapitel 8.2)
„Viele Wege führen nach Rom“
Für ein und dieselbe Logik lassen sich unterschiedliche Kalküle definieren:
- Es ist möglich, dass wir in 2 Kalkülen unterschiedliche Junktoren zur Verfügung haben, die Kalküle aber dennoch die gleiche Logik definieren, da sich, wie wir sehen werden, einzelne Junktoren durch Kombinationen anderer Junktoren ausdrücken lassen.
- Die mögliche Struktur von Formeln kann „beliebig“ gewählt werden.
Beispiel – Unterschiedliche Formeln für die gleiche Aussage
Betrachten wir folgene Aussage aus der Wumpus-Welt:- „Auf Feld [A,2] ist ein Gestank wahrnehmbar und der Wumpus befindet sich auf Feld [A,3]“
Dies könnten wir u.A. durch folgende Formeln darstellen:
- Gestank(A,2) UND Wumpus(A,3)
- G-A2 & W-A3
- A&B
- &(Gestank(A,2), Wumpus(A,3))
- Unterschiedliche Kombinationen von Axiomen und Schlussregeln können zu gleichen Ergebnissen führen.
Mögliche Anzahl der Junktoren
(Logik Einführung Kapitel 8.2.1)
n-stellige Junktoren haben n Argumente.
Jedes dieser Argumente kann m Wahrheitswerte annehmen – d.h. für jeden Junktor gibt es mn mögliche Werte-Kombinationen.
Weiters kann jede dieser Kombinationen m mögliche Gesamtbewertungen annehmen – d.h. es gibt mmn verschiedene Gesamtkombinationen.
Beispiel – Einige extensionale 2-stellige Junktoren einer 2-wertigen Logik
Für eine klassische Logik existieren auf Grund ihrer 2-wertigkeit
- 221=4 1-stellige, und
- 222=16 2-stellige
extensionale Junktoren.
Wir wollen einige der möglichen 2-stelligen Junktoren anhand der Wumpus-Welt mit Wahrheitstabellen anführen.
Für die beiden Argumente
- Wumpus(A,3)
- Gestank(A,2)
gibt es 22=4 mögliche Werte-Kombinationen, d.h. die Argumente können folgende Werte annehmen:
Wumpus(A,3) Gestank(A,2) 1 falsch falsch 2 falsch wahr 3 wahr falsch 4 wahr wahr Jeder dieser Kombinationen können wir wiederum einen von den 2 möglichen Werten als Ergebnis zuweisen, also z.B.
(° steht für einen beliebigen Junktor)
Wumpus(A,3) Gestank(A,2) Wumpus(A,3)°Gestank(A,2) falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr Das würde einer UND-Verknüpfung entsprechen
Wumpus(A,3) Gestank(A,2) Wumpus(A,3)°Gestank(A,2) falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr Das würde einer ODER-Verknüpfung entsprechen
Wumpus(A,3) Gestank(A,2) Wumpus(A,3)°Gestank(A,2) falsch falsch wahr falsch wahr falsch wahr falsch falsch wahr wahr wahr Das würde einer GENAU_DANN_WENN-Verknüpfung entsprechen
Insgesamt können wir so 16 unterschiedliche Junktoren definieren.
Funktionale Vollständigkeit
(Logik Einführung Kapitel 8.2.2)
Beispiel – Ersetzung von Junktoren durch andere
Betrachten wir folgende Junktoren aus der Wumpus-Welt.
Um Platz zu sparen, schreiben wir
- W für Wumpus(A,3)
- G für Gestank(A,2)
W G W UND G falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr allgemein:
γ δ γ UND δ falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr
W G W ODER G falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr allgemein:
γ δ γ ODER δ falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr
W NICHT W falsch wahr wahr falsch allgemein:
γ NICHT γ falsch wahr wahr falsch Die folgende Tabelle zeigt, dass wir die UND-Verknüpfung durch eine Kombination der ODER-Verknüpfung und der Verneinung ausdrücken können:
W G W UND G NICHT W NICHT G (NICHT W)ODER(NICHT G) NICHT((NICHT W)ODER(NICHT G)) falsch falsch falsch wahr wahr wahr falsch falsch wahr falsch wahr falsch wahr falsch wahr falsch falsch falsch wahr wahr falsch wahr wahr wahr falsch falsch falsch wahr
Beispiel – Funktional vollständige Junktorenmenge
Die Menge, bestehend aus folgenden Junktoren aus dem obigen Beispiel:
- ODER
- NICHT
ist funktional vollständig bezüglich der Menge, bestehend aus folgenden Junktoren:
- UND
- ODER
- NICHT
Unterscheidungsmerkmale – Einsatzmöglichkeiten eines Kalküls
(Logik Einführung Kapitel 8.3)
Betrachten wir einen Kalkül, gibt es einige Fragen, deren Beantwortung essenziell für den möglichen Einsatz in automatischen Beweisern sein kann. Die wesentlichen Unterscheidungsmerkmale für die Algorithmen, die durch die Schlussregeln und Axiome definiert werden, sind:
- Korrektheit
Lassen sich nur semantisch gültige Sätze ableiten? - Vollständigkeit
Lassen sich alle semantisch gültigen Sätze ableiten? - Gültigkeit vs. Erfüllbarkeit
Erinnern wir uns an die Zusammenhänge zwischen Gültigkeit und Erfüllbarkeit: Eine Formel ist genau dann gültig, wenn das Gegenteil der Formel unerfüllbar ist. Ist also das Gegenteil der Formel erfüllbar, so kann die Formel nicht gültig sein – ist das Gegenteil unerfüllbar, so muss die Formel gültig sein.
Es gilt also:Eine vollständige und korrekte Prozedur um die Erfüllbarkeit einer Formel zu bestimmen reicht aus, um die Gültigkeit einer Formel zu bestimmen. Das Vorgehen, ein Gültigkeitsproblem in ein Erfüllbarkeitsproblem zu übersetzen, wird als „Reduktion auf Erfüllbarkeit“ bezeichnet. - Direkter vs. indirekter Beweis
Ein Beweis wird als direkt bezeichnet, wenn er eine Ableitung einer Aussage aus einer Menge von Prämissen ist.
Ein indirekter Beweis (auch „Reductio ad absurdum“) ist eine Ableitung, die das Gegenteil der zu beweisenden Aussage zu einem Widerspruch führt.D.h. in einem direkten Beweis formen wir eine Menge an Voraussetzungen so lange um, bis wir das Ergebnis erhalten.
Bei einem indirekten Beweis nehmen wir das Gegenteil der zu beweisenden Aussage an. Widerspricht diese den Voraussetzungen, so muss sie ungültig und somit die Annahme gültig sein.Beispiel – Direkter vs. indirekter Beweis
Angenommen, wir wollen zeigen, dass nicht alle Menschen Römer sind.- In einem direkten Beweis formen wir die unser Wissen so lange um, bis wir die Annahme erhalten.
- Für den indirekten Beweis nehmen wir das Gegenteil an – also, dass alle Menschen Römer sind.
Daraus folgt, dass Sokrates Römer ist.
Nachdem wir allerdings wissen, dass Sokrates Grieche ist, und er weiters nicht Römer und Grieche sein kann, führt diese Annahme zu einem Widerspruch. Das Gegenteil der Annahme muss also gültig sein.
- Analytizität des Beweisverfahrens
Analytizität bedeutet, dass die Gültigkeit eines Satzes allein durch seine Teilaussagen (ohne Hinzufügen weiterer Formeln) gezeigt wird – d.h. dem Beweis werden durch Regelanwendungen nur Bestandteile der ursprünglichen Aussage hinzugefügt. - Don’t-care-Indeterminismus des Beweisverfahrens
Der Don’t-care-Indeterminismus (auch „Beweiskonfluenz“ genannt) besagt, dass die Reihenfolge der Anwendungen der Schlussregeln für das Ergebnis der Ableitung egal ist. - Komplexität des Beweisverfahrens
Grundlegende Fragen zur Komplexität sind u.A. folgende:- Mit welcher Komplexität des kürzesten Beweises in Relation zur Komplexität der zu beweisenden Formel ist bei der Berechnung einer Lösung zu rechnen? Besitzen einfache Formeln einfache Beweise?
- Welche Komplexität hat ein Beweis im schlimmsten Fall?
- Wie viel Speicherplatz wird benötigt? D.h. Ist immer entscheidbar, ob ein Schluss gültig ist?
- Terminiert das Verfahren immer?