Anzeige:
Anzeige:

IRC-Coding

Stern inaktivStern inaktivStern inaktivStern inaktivStern inaktiv

Im Laufe der Zeit wurden sehr viele Logiken für die unterschiedlichsten Anwendungsgebiete definiert.
In diesem Kapitel wollen wir einige der bekanntesten beispielhaft anführen. 

Zu den Klassischen Logiken zählen z.B.

  • die Aussagenlogik
  • und die Prädikatenlogik.


Beispiele Nichtklassischer Logiken sind z.B.

  • Mehrwertige Logiken
  • Modallogiken
  • und Nichtmonotone Logiken.

 

Aussagenlogik

(Logik Einführung Kapitel 9.1)

Die Aussagenlogik ist eine sehr einfache klassische Logik. Sie ist sehr intuitiv, weil sie sich an die natürliche Sprache anlehnt. 
Aussagen werden üblicherweise mittels der Operatoren

  • UND
  • ODER
  • WENN ... DANN
  • GENAU DANN WENN

verknüpft, und über einen einstelligen Operator

  • NICHT

verneint. 

Sie nicht sehr ausdrucksstark, da die Atome keine innere Struktur besitzen.

Beispiel - Mögliche Sätze in der Aussagenlogik

In der Aussagenlogik werden u.a. Sätze der folgenden Form untersucht:
  • die_sonne_scheint UND wir_gehen_schimmen
  • WENN rex_bellt DANN rex_ist_ein_hund
  • zahl_durch_3_teilbar GENAU DANN WENN ziffernsumme_durch_3_teilbar

Beispiel - Die Wumpus-Welt in der Aussagenlogik

Betrachten wir wieder die Wumpus-Welt. 

Innerhalb der Aussagenlogik könnten wir z.B. ausdrücken, dass
  • WENN (NICHT GestankB1)
    DANN (NICHT WumpusA1
    UND NICHT WumpusB2
    UND NICHT WumpusB1
    UND NICHT WumpusC1)

Die Tatsache, dass sich kein Wumpus in einem benachbarten Feld befinden kann, wenn kein Gestank wahrnehmbar ist, bedarf allerdings solch einer Regel für jedes Spielfeld:
  • WENN (NICHT GestankC1)
    DANN (NICHT WumpusB1
    UND NICHT WumpusC1
    UND NICHT WumpusD1
    UND NICHT WumpusC2)
  • WENN (NICHT GestankA1)
    DANN (NICHT WumpusA1
    UND NICHT WumpusB1
    UND NICHT WumpusA2)
  • etc.

Insgesamt wären also allein für diese Spielregel 16 Formeln notwendig.
 
 

Prädikatenlogik

(Logik Einführung Kapitel 9.2)
 
 
Die Prädikatenlogik ist ebenfalls eine klassische Logik.
Sie kann als Erweiterung der Aussagenlogik betrachtet werden. 

Hier hier ist zusätzlich eine innere Struktur und eine Quantifizierung der Atome möglich. 

Zusätzlich zu den aussagenlogischen Elementen haben wir in der Prädikatenlogik
  • Variablen
  • Konstanten
  • n-äre Funktionen auf Variablen und Konstanten
  • Prädikate (als n-äre Relationen zwischen Objekten) auf Variablen, Konstanten und Funktionen
  • Quantoren (Operatoren, die sich auf die Variablen beziehen) 'FÜR_ALLE' und 'ES_EXISTIERT_MINDESTENS_EIN'
zur Verfügung. 

Innerhalb der Prädikatenlogik lässt sich ein großer Bereich von Sätzen formalisieren und auf ihre Gültigkeit prüfen.
Sie spielt in der Mathematik, Informatik und Linguistik eine große Rolle und wird oft bei Expertensystemen und in der künstlichen Intelligenz eingesetzt.
Eine bekannte Form der angewandten Prädikatenlogik ist z.B. die Programmiersprache Prolog.

Beispiel - Mögliche Sätze in der Prädikatenlogik

In der Aussagenlogik werden u.a. Sätze der folgenden Form untersucht:
  • FÜR_ALLE x: WENN bellt(x) DANN hund(x)
  • bellt(Rex)

Daraus können wir schließen, dass
  • hund(Rex)

Beispiel - Die Wumpus-Welt in der Prädikatenlogik

In der Prädikatenlogik können wir die 16 Sätze, die wir in der Aussagenlogik benötigen um das Nichtvorhandensein eines Gestankes in Bezug zur möglichen Position des Wumpus zu setzen, mittels einem einzigen Satz ausdrücken (wobei a und b Variablen sind):
  • WENN (NICHT Gestank(a,b))
    DANN (NICHT Wumpus(a,b) 
    UND NICHT Wumpus(minus(a),b)
    UND NICHT Wumpus(plus(a),b)
    UND NICHT Wumpus(a,minus(b))
    UND NICHT Wumpus(a,plus(b)))

 

wobei wir die Funktionen 'minus' und 'plus' entsprechend definieren müssen.
 
 

Mehrwertige Logiken

(Logik Einführung Kapitel 9.3)
 
Mehrwertige Logiken zählen zu den nichtklassischen Logiken und werden z.B. zur Simulation verschiedener Zustände in der Hardwareentwicklung, zur Hardwarebeschreibung, in der Automatisierungs- und Automobiltechnik oder zum Umgang mit unvollständigem Wissen (z.B. Datenbanken) eingesetzt. 

Die wohl bekannteste mehrwertige Logik ist die Fuzzy-Logik, die auf der boolschen Logik (eine 2-wertige Logik mit den Operatoren UND, ODER, NICHT) aufbaut, aber unendlich viele Werte (dargestellt als reelle Zahl zwischen 0 und 1) für den Grad der Wahrheit besitzt. 

Die Fuzzy-Logik wurde entwickelt, um unscharfes (menschliches) Wissen darzustellen. 
Ihre Basis bilden so genannte unscharfe Mengen - Mengen in denen ein Element neben "enthalten" und "nicht enthalten" auch z.B. "ein wenig enthalten" sein kann. Die Zugehörigkeit zu einer Menge wird meist durch eine so genannte Fuzzyfunktion definiert. 

Sie wird hauptsachlich bei der Steuerung von Maschinen (auch "gewöhnlichen" Haushaltsgeräten) und Robotern eingesetzt.

Beispiel - Fuzzyfunktion für das Alter eines Menschen

Angenommen wir haben
  • Personendaten mit einer Angabe des Alters
und wollen diese Personen
  • unscharf definierten Altersgruppen
wie
  • "noch jung"
  • "alt"
zuordnen. 

Dies könnten wir durch die folgende Fuzzyfunktion ausdrücken:
 

Jedes Dreieck definiert eine der Altersgruppen - es umfasst einen Bereich von mehreren Jahren und bestimmt den Grad der Zugehörigkeit zu der jeweiligen Altersgruppe.
Eine Person mit 45 Jahren wäre so zu 75% noch jung und bereits zu 25% mittleren Alters.

Beispiel - Die Wumpus-Welt in einer mehrwertigen Logik

Betrachten wir wieder die Wumpus-Welt. 

In einer mehrwertigen Logik wäre es nicht nur möglich auszudrücken, dass
  • auf einem Feld ein Luftzug spürbar ist oder nicht
sondern auch
  • verschiedene Grade des Luftzuges
zu differenzieren. 

Ein leichter Luftzug könnte z.B. bedeuten, dass die Fallgrube noch einige Felder weit entfernt ist.
 

Modallogiken

(Logik Einführung Kapitel 9.4)
 
Modallogiken sind nichtklassischen Logiken

Sie enthalten, zusätzlich zu den Elementen der Prädikatenlogik, Operatoren mit denen Modalitäten wie z.B. "möglich", "notwendig", "immer (in der Zukunft)", oder "manchmal/irgendwann (in der Zukunft)" ausgedrückt werden können.

Beispiel - Mögliche modallogische Aussagen

Neben Sätzen wie
  • "Es regnet"
kann auch mit Sätzen der Form
  • "Irgendwann wird es regnen"
  • "Möglicherweise wird es regnen"
umgegangen werden.

Beispiel - Die Wumpus-Welt in einer Modallogik

Grundlage ist wieder die Wumpus-Welt. 

Wird auf Feld [B,1] ein Luftzug wahrgenommen, könnten wir in einer Modallogik ausdrücken, dass
  • "Möglicherweise befindet sich eine Fallgrube auf Feld [C,1]"
 
 

Nichtmonotone Logiken

(Logik Einführung Kapitel 9.5)
 
Nichtmonotonen Logiken zählen ebenfalls zu den nichtklassischen Logiken.

Ihnen fehlt die Eigenschaft der Monotonie. 
Dies bedeutet, dass generierte Erkenntnisse zu einem späteren Zeitpunkt (nach Hinzukommen neuen Wissens) revidiert werden können.
Hierzu verwendet man meist so genannte Default-Schlüsse. Ein Default-Schluss ist so lange gültig, bis er durch einen klassischen Schluss widerlegt wird.

Beispiel - Kann Tux fliegen?

In einer nichtmonotonen Logik wäre z.B. folgendes möglich: 

Haben wir die Voraussetzung
  • Tux ist ein Vogel
und eine Begründung
  • Vögel können normalerweise fliegen
so können wir mit einem Default-Schluss
  • Tux kann fliegen
schließen. 

Erhalten wir die zusätzlichen Informationen
  • Tux ist ein Pinguin
  • Pinguine können nicht fliegen
schließen wir daraus klassisch, dass
  • Tux kann nicht fliegen

Die zusätzliche Information führt also zu einer Revidierung des Default-Schlusses.

Beispiel - Die Wumpus-Welt in einer Nichtmonotonen Logik

Grundlage ist wieder die Wumpus-Welt. 

In einer nichtmonotonen Logik wäre es möglich, aus der Tatsache, dass
  • auf Feld [B,1] ein Luftzug wahrgenommen wird
mittels eines Default-Schlusses zu schließen, dass sich
  • sowohl auf Feld [C,1],
  • als auch auf Feld [B,2]
Fallgruben befinden. 

Erhalten wir die zusätzlichen Informationen
  • Kein Luftzug auf Feld [A,2]
schließen wir daraus klassisch, dass
  • Keine Fallgrube auf Feld [B,2]

Durch den Schluss wird der Default-Schluss revidiert.
Stern inaktivStern inaktivStern inaktivStern inaktivStern inaktiv

Im Laufe der Zeit wurden sehr viele Logiken für die unterschiedlichsten Anwendungsgebiete definiert.
In diesem Kapitel wollen wir einige der bekanntesten beispielhaft anführen. 

Zu den Klassischen Logiken zählen z.B.

  • die Aussagenlogik
  • und die Prädikatenlogik.


Beispiele Nichtklassischer Logiken sind z.B.

  • Mehrwertige Logiken
  • Modallogiken
  • und Nichtmonotone Logiken.

 

Aussagenlogik

(Logik Einführung Kapitel 9.1)

Die Aussagenlogik ist eine sehr einfache klassische Logik. Sie ist sehr intuitiv, weil sie sich an die natürliche Sprache anlehnt. 
Aussagen werden üblicherweise mittels der Operatoren

  • UND
  • ODER
  • WENN ... DANN
  • GENAU DANN WENN

verknüpft, und über einen einstelligen Operator

  • NICHT

verneint. 

Sie nicht sehr ausdrucksstark, da die Atome keine innere Struktur besitzen.

Beispiel - Mögliche Sätze in der Aussagenlogik

In der Aussagenlogik werden u.a. Sätze der folgenden Form untersucht:
  • die_sonne_scheint UND wir_gehen_schimmen
  • WENN rex_bellt DANN rex_ist_ein_hund
  • zahl_durch_3_teilbar GENAU DANN WENN ziffernsumme_durch_3_teilbar

Beispiel - Die Wumpus-Welt in der Aussagenlogik

Betrachten wir wieder die Wumpus-Welt. 

Innerhalb der Aussagenlogik könnten wir z.B. ausdrücken, dass
  • WENN (NICHT GestankB1)
    DANN (NICHT WumpusA1
    UND NICHT WumpusB2
    UND NICHT WumpusB1
    UND NICHT WumpusC1)

Die Tatsache, dass sich kein Wumpus in einem benachbarten Feld befinden kann, wenn kein Gestank wahrnehmbar ist, bedarf allerdings solch einer Regel für jedes Spielfeld:
  • WENN (NICHT GestankC1)
    DANN (NICHT WumpusB1
    UND NICHT WumpusC1
    UND NICHT WumpusD1
    UND NICHT WumpusC2)
  • WENN (NICHT GestankA1)
    DANN (NICHT WumpusA1
    UND NICHT WumpusB1
    UND NICHT WumpusA2)
  • etc.

Insgesamt wären also allein für diese Spielregel 16 Formeln notwendig.
 
 

Prädikatenlogik

(Logik Einführung Kapitel 9.2)
 
 
Die Prädikatenlogik ist ebenfalls eine klassische Logik.
Sie kann als Erweiterung der Aussagenlogik betrachtet werden. 

Hier hier ist zusätzlich eine innere Struktur und eine Quantifizierung der Atome möglich. 

Zusätzlich zu den aussagenlogischen Elementen haben wir in der Prädikatenlogik
  • Variablen
  • Konstanten
  • n-äre Funktionen auf Variablen und Konstanten
  • Prädikate (als n-äre Relationen zwischen Objekten) auf Variablen, Konstanten und Funktionen
  • Quantoren (Operatoren, die sich auf die Variablen beziehen) 'FÜR_ALLE' und 'ES_EXISTIERT_MINDESTENS_EIN'
zur Verfügung. 

Innerhalb der Prädikatenlogik lässt sich ein großer Bereich von Sätzen formalisieren und auf ihre Gültigkeit prüfen.
Sie spielt in der Mathematik, Informatik und Linguistik eine große Rolle und wird oft bei Expertensystemen und in der künstlichen Intelligenz eingesetzt.
Eine bekannte Form der angewandten Prädikatenlogik ist z.B. die Programmiersprache Prolog.

Beispiel - Mögliche Sätze in der Prädikatenlogik

In der Aussagenlogik werden u.a. Sätze der folgenden Form untersucht:
  • FÜR_ALLE x: WENN bellt(x) DANN hund(x)
  • bellt(Rex)

Daraus können wir schließen, dass
  • hund(Rex)

Beispiel - Die Wumpus-Welt in der Prädikatenlogik

In der Prädikatenlogik können wir die 16 Sätze, die wir in der Aussagenlogik benötigen um das Nichtvorhandensein eines Gestankes in Bezug zur möglichen Position des Wumpus zu setzen, mittels einem einzigen Satz ausdrücken (wobei a und b Variablen sind):
  • WENN (NICHT Gestank(a,b))
    DANN (NICHT Wumpus(a,b) 
    UND NICHT Wumpus(minus(a),b)
    UND NICHT Wumpus(plus(a),b)
    UND NICHT Wumpus(a,minus(b))
    UND NICHT Wumpus(a,plus(b)))

 

wobei wir die Funktionen 'minus' und 'plus' entsprechend definieren müssen.
 
 

Mehrwertige Logiken

(Logik Einführung Kapitel 9.3)
 
Mehrwertige Logiken zählen zu den nichtklassischen Logiken und werden z.B. zur Simulation verschiedener Zustände in der Hardwareentwicklung, zur Hardwarebeschreibung, in der Automatisierungs- und Automobiltechnik oder zum Umgang mit unvollständigem Wissen (z.B. Datenbanken) eingesetzt. 

Die wohl bekannteste mehrwertige Logik ist die Fuzzy-Logik, die auf der boolschen Logik (eine 2-wertige Logik mit den Operatoren UND, ODER, NICHT) aufbaut, aber unendlich viele Werte (dargestellt als reelle Zahl zwischen 0 und 1) für den Grad der Wahrheit besitzt. 

Die Fuzzy-Logik wurde entwickelt, um unscharfes (menschliches) Wissen darzustellen. 
Ihre Basis bilden so genannte unscharfe Mengen - Mengen in denen ein Element neben "enthalten" und "nicht enthalten" auch z.B. "ein wenig enthalten" sein kann. Die Zugehörigkeit zu einer Menge wird meist durch eine so genannte Fuzzyfunktion definiert. 

Sie wird hauptsachlich bei der Steuerung von Maschinen (auch "gewöhnlichen" Haushaltsgeräten) und Robotern eingesetzt.

Beispiel - Fuzzyfunktion für das Alter eines Menschen

Angenommen wir haben
  • Personendaten mit einer Angabe des Alters
und wollen diese Personen
  • unscharf definierten Altersgruppen
wie
  • "noch jung"
  • "alt"
zuordnen. 

Dies könnten wir durch die folgende Fuzzyfunktion ausdrücken:
 

Jedes Dreieck definiert eine der Altersgruppen - es umfasst einen Bereich von mehreren Jahren und bestimmt den Grad der Zugehörigkeit zu der jeweiligen Altersgruppe.
Eine Person mit 45 Jahren wäre so zu 75% noch jung und bereits zu 25% mittleren Alters.

Beispiel - Die Wumpus-Welt in einer mehrwertigen Logik

Betrachten wir wieder die Wumpus-Welt. 

In einer mehrwertigen Logik wäre es nicht nur möglich auszudrücken, dass
  • auf einem Feld ein Luftzug spürbar ist oder nicht
sondern auch
  • verschiedene Grade des Luftzuges
zu differenzieren. 

Ein leichter Luftzug könnte z.B. bedeuten, dass die Fallgrube noch einige Felder weit entfernt ist.
 
 
Stern inaktivStern inaktivStern inaktivStern inaktivStern inaktiv

Beweis & Schluss  Logik Einführung Kapitel 7

 

Ist die Syntax und Semantik einer Sprache definiert, haben wir die Möglichkeit innerhalb unseres Systems Wissen darzustellen oder Annahmen zu tätigen und zu interpretieren. 

Aber kommen wir zu unserem eigentlichen Ziel: dem automatisierten Generieren neuer Sätze und damit neuen Wissens

Wir werden zunächst das semantische Konzept des logischen Schlusses (auch "Schlussfolgerung" genannt) erläutern, 
und dann beschreiben, wie wir dieses durch das syntaktische Konzept des logischen Beweises (auch "Ableitung" genannt) abbilden, und so durch mechanische Systeme handhabbar machen können.
 

Der logische Schluss

(Logik Einführung Kapitel 7.1)
 
 
Durch die Semantik wird auch das semantische Konzept des logischen Schluss (oder auch "Schlussfolgerung", "logische Konsequenz") definiert. Eine Formel ist genau dann eine logische Konsequenz aus einer Menge von Formeln, wenn sie vernünftigerweise aus diesen folgt.

Beispiel - Die Nadel im Heuhaufen: logischer Schluss

Suchen wir die Nadel im Heuhaufen, besteht der logische Schluss darin, dass:
  • Wenn jemand die Nadel im Heuhaufen fallen gelassen hat, muss sie dort sein
also:
  • Die Nadel ist im Heuhaufen ist eine logische Konsequenz davon, dass jemand diese darin fallen gelassen hat.
bzw.
  • Aus der Tatsache, dass jemand die Nadel im Heuhaufen fallen gelassen hat folgt, dass sie dort sein muss
D.h.:
  • Eine Formel ist genau dann eine logische Konsequenz einer Formelmenge,
  • wenn alle Interpretationen, welche die Menge erfüllen,
  • auch die Formel erfüllen.
Dies können wir formal wie folgt ausdrücken: 

Wir sagen eine Formel γ folgt aus einer Menge von Formeln Γ, wenn alle Modelle von Γ auch Modelle von γ sind.
Wir sagen auch γ ist eine logische Konsequenz von Γ

Γ bezeichnen wir als Annahmen oder Prämissen,
γ als Konklusion

Führen wir den Folgerungsoperator |= ein, 
schreiben wir Γ|=γ
wenn γ eine logische Konsequenz aus Γ ist
und sagen dann auch Γ|=γ ist (semantisch) gültig

Die Behauptung, dass die Konklusion aus den Prämissen folgt, also Γ|=γ, bezeichnen wir als Argument.

D.h.:
  • Haben wir eine Formelmenge Γ
  • eine Formel γ
  • und ist γ immer (in allen Welten) erfüllbar, wenn (in denen) alle Formeln in Γ erfüllbar sind
  • sagen wir γ folgt aus Γ
  • und schreiben Γ|=γ

Beispiel - Logischer Schluss: Wumpus-Welt

Betrachten wir wieder die Wumpus-Welt. 

Angenommen wir wissen, dass
Prämisse 1 NICHT Gestank(A,1)
Prämisse 2 WENN (NICHT Gestank(A,1))
DANN (NICHT Wumpus(A,1) 
UND NICHT Wumpus(A,2)
UND NICHT Wumpus(B,1))

Daraus folgern wir vernünftigerweise z.B.
Konklusion NICHT Wumpus(A,2)
und schreiben
Argument {
NICHT Gestank(A,1), 
WENN (NICHT Gestank(A,1)) DANN (NICHT Wumpus(A,1) UND NICHT Wumpus(A,2) UND NICHT Wumpus(B,1))
|= NICHT Wumpus(A,2)

Dies ist vernünftig, weil es den Spezifikationen des Spieles und der Bedeutung der Aussagen entspricht:
wir wissen, dass es auf
  • Feld [A,1] nicht stinkt
und laut Spieldefinition
  • kann sich der Wumpus also weder auf dem Feld, noch auf einem direkt benachbarten Feld befinden.

In jeder Spielumgebung in der es auf Feld [A,1] nicht stinkt, kann sich der Wumpus also z.B. auch nicht auf Feld [A,2] befinden.
Jede Interpretation unter der
  • NICHT Gestank(A,1) wahr ist,
muss also auch
  • NICHT Wumpus(A,2) wahr sein.
D.h. jedes
  • Modell von NICHT Gestank(A,1)
ist auch ein
  • Modell von NICHT Wumpus(A,2)

Die Konklusion folgt also aus den Prämissen.
Das Argument ist (semantisch) gültig.
Eine Tautologie ist ein Satz, der sich ohne Verwendung von Prämissen folgern lässt, also für den |=γ gültig ist, da ihn alle Interpretationen erfüllen.
 
 
 

Der logische Beweis

(Logik Einführung Kapitel 7.2)
 
Die logische Inferenz (oder auch Ableitung) ist das syntaktische Pendant der logischen Konsequenz. 

Innerhalb einer Ableitung werden Formeln
  • mechanisch
  • nach festgelegten Regeln (die so genannten "Schlussregeln")
  • unter eventueller Miteinbeziehung vorgegebener Formeln (die so genannten "Axiome")
umgeformt, sodass neue Formeln entstehen.

In diesem Kapitel wollen wir definieren, was ein logische Schluss ist. Auf die Definition der Schlussregeln und Axiome wird in den nächsten Kapiteln näher eingegangen.

Beispiel - Die Nadel im Heuhaufen: logischer Beweis

Suchen wir die Nadel im Heuhaufen, besteht der logische Beweis darin, dass wir nach irgendeiner Methode so lange Halme abtragen, bis wir die Nadel finden.
Wir sagen eine Formel γ lässt sich aus einer Menge von Formeln Γ ableiten, wenn γ das Ergebnis einer endlichen Abfolge von Anwendungen von Umformungsregeln unter eventueller Miteinbeziehung bestimmter anderer Formeln (die Grundvoraussetzungen ausdrücken) auf Γ ist. 

Γ bezeichnen wir als Annahmen oder Prämissen,
γ als Konklusion,
die Umformungsregeln als Schlussregeln,
und die Grundvoraussetzungen als Axiome

Die Abfolge der Regeln bezeichnen wir als Beweis (oder auch Ableitung). 

Führen wir den Ableitungsoperator |-- ein, 
schreiben wir Γ|--γ
wenn γ aus Γ ableitbar ist.

D.h.:
  • Haben wir eine Formelmenge Γ
  • wenden wir die Umformungsregeln auf diesen endlich oft an, wobei wir bei jedem Schritt Grundvoraussetzungen hinzunehmen können
  • und kommen so zum Ergebnis γ
  • sagen wir γ lässt sich aus Γ ableiten
  • und schreiben Γ|--γ

Beispiel - Logischer Beweis: Wumpus-Welt

Lösen wir das das Beispiel aus dem Kapitel "Der logische Schluss" syntaktisch. 

Angenommen, wir wissen, dass
Prämisse NICHT Gestank(A,1)
Axiom WENN (NICHT Gestank(A,1))
DANN (NICHT Wumpus(A,1) 
UND NICHT Wumpus(A,2)
UND NICHT Wumpus(B,1))

Nehmen wir weiters an, wir haben eine Schlussregel 1, die besagt, dass
  • haben wir eine Formel der Gestalt
    • WENN γ DANN δ
    wobei γ und δ beliebige Formeln sind
und ist
  • γ gegeben
können wir
  • δ ableiten

Dann können wir in Schritt 1 unserer Inferenz aus der Prämisse unter Miteinbeziehung des Axiomes
Wissen 1 NICHT Wumpus(A,1) UND NICHT Wumpus(A,2) UND NICHT Wumpus(B,1)
ableiten. 

Angenommen, wir haben eine weitere Regel, Schlussregel 2, die besagt, dass
  • haben wir eine Formel der Gestalt
    • γ UND δ
können wir
  • γ ableiten
und
  • δ ableiten

Dann können wir in Schritt 2 unserer Inferenz aus dem Wissen 1
Wissen 2 NICHT Wumpus(A,1)
Wissen 3 NICHT Wumpus(A,2)
Wissen 4 NICHT Wumpus(B,1)
ableiten. 

D.h.
  • NICHT Gestank(A,1) |-- NICHT Wumpus(A,2)

So können wir aus der Wahrnehmung und den Grundvoraussetzungen (Spielregeln) automatisiert (ohne jegliches Wissen darüber, was Wumpus oder Gestank bedeuten) darauf schließen, dass sich der Wumpus nicht auf Feld [A,2] befinden kann. 

Die Schritte 1 und 2 bezeichnen wir als Beweis, und sagen 'NICHT Wumpus(A,2)' lässt sich aus 'NICHT Gestank(A,1)' ableiten



Haben wir die Spielregeln nicht als Axiome innerhalb unserer Logik definiert, müssen wir das Axiom als weitere Prämisse hinzufügen, und erhalten
  • {
    NICHT Gestank(A,1), 
    WENN (NICHT Gestank(A,1)) DANN (NICHT Wumpus(A,1) UND NICHT Wumpus(A,2) UND NICHT Wumpus(B,1))
    |-- NICHT Wumpus(A,2)

 

Axiome

(Logik Einführung Kapitel 7.2.1)

 

Unsere Problemstellung baut eventuell auf gewissen Grundannahmen auf, die wir als Voraussetzungen für unsere Ableitungen brauchen. 

Die Voraussetzungen unserer Problemstellung drücken wir als Formeln unserer Sprache aus, und fügen sie als so genannte Axiome (auch Anfangsregeln oder Annahmen genannt) unserem Kalkül hinzu.

Beispiel -

Betrachten wir wieder die Wumpus-Welt. 

Definieren wir einen spezifischen Kalkül für unsere Wumpus-Welt, so können wir die Spielregeln, also:
  • WENN (NICHT Gestank(A,1)) 
    DANN (NICHT Wumpus(A,1) 
    UND NICHT Wumpus(A,2)
    UND NICHT Wumpus(B,1))
  • WENN (NICHT Gestank(B,1)) 
    DANN (NICHT Wumpus(A,1) 
    UND NICHT Wumpus(B,2)
    UND NICHT Wumpus(B,1)
    UND NICHT Wumpus(C,1))
  • ...
  • WENN (Gestank(A2) 
    DANN (Wumpus(A,1)
    ODER Wumpus(A,2)
    ODER Wumpus(A,3)
    ODER Wumpus(B,2))
  • etc.
als Axiome betrachten. 

Da sich der Wumpus nicht auf Feld [A,1] befinden kann, fügen wir unserem Kalkül die Formel
  • NICHT Wumpus(A,1)

 

Schlussregeln

(Logik Einführung Kapitel 7.2.2)

Nun brauchen wir noch Regeln, die es uns erlauben, innerhalb unseres Systems Formeln mechanisch zu manipulieren um neue Formeln zu erhalten. 

Die so genannten Transformations- oder Schlussregeln definieren (Ableitungs-)Regeln, wie bestehende Formeln zu neuen Formeln umgeformt werden dürfen.

Beispiel -

Betrachten wir wieder die Wumpus-Welt. 

Haben wir z.B. die Formeln
  • WENN (NICHT Gestank(A,1)) 
    DANN (NICHT Wumpus(A,1) 
    UND NICHT Wumpus(A,2)
    UND NICHT Wumpus(B,1))
  • NICHT GestankA1
wollen wir daraus automatisiert schließen können, dass
  • NICHT Wumpus(A,1) UND NICHT Wumpus(A,2) UND NICHT Wumpus(B,1)
Dies soll allgemein für jede Formel der Gestalt WENN..DANN gelten. 

Da wir die Bedeutung der Aussagen verstehen, erscheint uns der Schluss klar. Ein Automat jedoch, der nur Symbole manipulieren kann benötigt hierfür jedoch eine Regel. 

Also fügen wir unserem Kalkül folgende Schlussregel hinzu:
  • Haben wir eine Formel der Gestalt
    • WENN γ DANN δ
    wobei γ und δ beliebige Formeln sind
und ist
  • γ gegeben
können wir
  • δ ableiten

D.h.
  • "Haben wir eine WENN..DANN-Formel, und ist die Voraussetzung gegeben, so können wir den Schluss zu unserem Wissen hinzufügen"
Diese Regel ist in vielen Logiken enthalten und wird als "Modus Ponens" oder auch "Implikations-Elimination" bezeichnet. 



Haben wir z.B. die Formel
  • NICHT Wumpus(A,2) UND NICHT Wumpus(B,1)
wollen wir auf jede einzelne Teilaussage schließen können, also z.B.
  • NICHT Wumpus(A,2)
Dies soll allgemein für alle UND-Verknüpften Formeln gelten. 

Wieder erscheint es uns klar, dass, wenn die Gesamtaussage gilt, auch all ihre Teilaussagen gelten müssen - doch wieder müssen wir dies mit einer Schlussregel definieren:
  • Haben wir eine Formel der Gestalt
    • γ UND δ
    wobei γ und δ beliebige Formeln sind
können wir
  • γ ableiten
und
  • δ ableiten

D.h.
  • "Sind 2 Teilaussagen durch UND verbunden, so können wir jede dieser Teilaussagen zu unserem Wissen hinzufügen"
Auch diese Regel ist in vielen Logiken enthalten und wird als 'Und-Elimination' bezeichnet. 



Haben wir z.B. die Formel
  • Wumpus(A,2) ODER Wumpus(B,1)
wissen aber bereits, dass eine dieser Teilaussage nicht gilt, also z.B.
  • NICHT Wumpus(A,2)
wollen wir auf die andere Teilaussage schließen können, also z.B.
  • Wumpus(B,1)
Dies soll allgemein für alle ODER-Verknüpften Formeln gelten. 

Das Konzept erscheint uns klar, da wir die Bedeutung kennen: gilt eine Teilaussage nicht, muss die andere Teilaussage gelten - doch wieder müssen wir dies mit einer Schlussregel definieren:
  • Haben wir eine Formel der Gestalt
    • γ ODER δ
    wobei γ und δ beliebige Formeln sind
und
  • NICHT γ
können wir
  • δ ableiten

D.h.
  • "Sind 2 Teilaussagen durch ODER verbunden, und gilt eine dieser Teilaussagen nicht, so können wir die andere Teilaussage zu unserem Wissen hinzufügen"
Auch diese Regel ist in vielen Logiken enthalten und wird als 'Einfacher Widerspruch' bezeichnet. 



So müssen wir nacheinander alle benötigten Regeln definieren, die es uns erlauben aus unserem Grundwissen und den zur Laufzeit generierten Informationen, weitere Schlüsse zu ziehen, und diese unserem Kalkül als Schlussregeln hinzufügen.

Den Transformationsregeln kommt natürlich keinerlei inhaltliche Bedeutung zu - sie sind ja rein formale Regeln, wie Zeichenketten umgeformt werden können. 
Wir werden diese Regeln jedoch sinnvoller Weise so definieren, dass umgeformte Sätze auch semantisch aus den Ausgangssätzen folgen.

 

als Axiom hinzu.
 
 
Da wir in der Logik ein semantisches Konzept der Schlussfolgerung formalisieren wollen, sind wir natürlich bestrebt, den semantischen Folgerungsoperator |= durch einen syntaktischen Ableitungsoperator |-- nachzubilden. 

Wir sagen
  • ein Kalkül ist korrekt, wenn sich nur semantisch gültige Sätze der zugrunde liegenden Logik ableiten lassen.
    D.h. wenn Γ|--γ gilt, gilt auch Γ|=γ.
     
  • ein Kalkül ist vollständig, wenn sich alle semantisch gültige Sätze der zugrunde liegenden Logik ableiten lassen.
    D.h. wenn Γ|=γ gilt, gilt auch Γ|--γ.

Ein Kalkül ist adäquat, wenn er vollständig und korrekt ist

Ist ein Kalkül adäquat, können in ihm genau alle gültigen Aussagen der zugrunde liegenden Logik abgeleitet werden. 

Selbstverständlich sind wir bestrebt, einen adäquaten Kalkül für unsere Problemstellung zu finden.
Wie Kurt Gödel jedoch in seinem Unvollständigkeitssatz bewiesen hat, ist es für alle Systeme, die so mächtig sind wie die Arithmetik, nicht mehr möglich solch einen Kalkül zu definieren. 

Außerdem ist zu bemerken, dass ein korrekter Kalkül immer widerspruchsfrei ist - denn wäre ein Widerspruch vorhanden bzw. ableitbar, wäre in weiterer Folge alles ableitbar und damit auch alle nichtgültigen Formeln.
 

Semantische Gültigkeit & logischer Beweis

(Logik Einführung Kapitel 7.4)
 
Innerhalb eines korrekten Kalküls lassen sich mittels logischer Inferenz also nur semantisch gültige Sätze ableiten. 

Wollen wir neben der Gültigkeit auch die
  • Erfüllbarkeit
  • Widerlegbarkeit
  • Unerfüllbarkeit
von Sätzen automatisiert zeigen, müssen wir uns an die Zusammenhänge erinnern:
 
  • Die Erfüllbarkeit eines Satzes können wir zeigen, indem wir zeigen, dass seine Negation keine Tautologie (also nicht ableitbar) ist.
     
  • Die Unerfüllbarkeit eines Satzes können wir zeigen, indem wir zeigen, dass seine Negation eine Tautologie (also ableitbar) ist.
     
  • Die Widerlegbarkeit eines Satzes können wir zeigen, indem wir zeigen, dass weder der Satz, noch sein Negat eine Tautologie (also beide nicht ableitbar) sind.

 

Stern inaktivStern inaktivStern inaktivStern inaktivStern inaktiv

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?

 

Ist eine Logik
  • 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 intensionale 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)
 
Allgemein gilt:
Jede m-wertige Logik hat mmn extensionale n-stellige Junktoren.
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)
 
 
Einzelne Junktoren lassen sich durch Kombinationen anderer Junktoren ersetzen.

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
Eine Menge von Junktoren heißt bezüglich einer anderen Menge von Junktoren funktional vollständig, wenn alle Junktoren der 2. Menge durch Junktoren der 1. Menge ausgedrückt werden können.

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 Gegentei 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 Berechung 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?

 

 

 

Stern inaktivStern inaktivStern inaktivStern inaktivStern inaktiv

Semantik

(Logik Einführung Kapitel 6)
 
Lassen sich unser Wissen und unsere Schlüsse formal repräsentieren, wollen wir diesen sinnentleerten Symbolfolgen wiederum Bedeutungen und somit Bewertungen zuweisen.

Die Semantik (Bedeutungslehre) beschäftigt sich mit der Bedeutung von sprachlichen Zeichen, Worten und Sätzen.

D.h. in der Semantik wird die Bedeutung/Bewertung der Sätze und damit ihr Gehalt oder Wahrheitswert in der Welt definiert. 
Wir brauchen also Regeln, die festlegen, welche Bedeutung eine Aussage in einer bestimmten Welt (zu einem bestimmten Zeitpunkt) hat.