Zum Inhalt springen

Formale Sprachen Logik Einführung Kapitel 4

Wollen wir etwas ausdrücken, benötigen wir eine Sprache.

Diese muss selbstverständlich ausdrucksstark genug sein, um unser (teilweise unvollständiges) Wissen über die Welt ausdrücken zu können.
Natürliche Sprachen, so wie Deutsch oder Englisch, sind sicherlich ausdrucksstark, entwickelten sich jedoch aus einem Bedürfnis der Kommunikation und wurden als solches nicht zur Repräsentation eindeutiger Aussagen geschaffen.
Die Interpretation einer natürlichsprachigen Aussage ist oft mehrdeutig oder von implizitem Wissen abhängig.

Beispiel – Mehrdeutigkeit natürlicher Sprache

  • Angenommen jemand sagt „Nasse Strassen und Dächer …“ – meint er, dass sowohl Straßen, als auch Dächer nass sind?
  • Der Ausspruch „Schau!“ wird nur aus dem Kontext verstanden.

Da wir uns für die eindeutige Repräsentation von Fakten in mechanischen Systemen und daraus resultierende mechanische Schlussfolgerungen interessieren, benötigen wir die Exaktheit einer formalen Sprache.

Bevor wir näher auf die Definition einer formalen Sprache eingehen,

  • müssen wir uns zunächst mit dem, für den Nicht-Theoretiker im ersten Augenblick oft befremdlichen Konzept der Trennung von Form (Syntax) und Bedeutung (Semantik) beschäftigen,
  • und definieren, was Atome und Junktoren sind.

Syntax vs. Semantik

(Logik Einführung Kapitel 4.1)

„Die Schönheit liegt im Auge des Betrachters“

Als Menschen sind wir gewohnt, jeden Satz zu interpretieren und so mit seiner Bedeutung zu hantieren. Als Kinder lernen wir, gewissen Gegebenheiten und Bedeutungen Worte zuzuweisen – den Worten unserer natürlichen Sprache wohnt die Bedeutung implizit inne.

In einem mechanischen System ist dies natürlich nicht so – Fakten lassen sich formalisieren und darstellen, ihre Bedeutung lässt sich von einem Computer jedoch nicht erfassen.
D.h. jeder mechanische Folgerungsmechanismus muss auf einer formalen Repräsentation der Daten erfolgen, bei der Worte ad hoc keine Bedeutung haben – wollen wir automatisiert Schlüsse generieren, müssen wir entsprechende abstrakte Regeln für abstrakte Daten definieren.

Beispiel – Syntax vs. Semantik: Wumpus-Welt

Grundlage ist die mögliche Wumpus-Welt aus der Spiel-Spezifikation.

Wir spüren einen Luftzug auf Feld [C,3] und folgern daraus, dass sich auf den Feldern [B,3], [D,3], [C,2] oder [C,4] eine Fallgrube befinden kann.

Ein mechanisches System kann jedoch weder mit einem Luftzug noch mit einer Fallgrube oder gar mit umliegenden Feldern etwas anfangen.
Um automatisiert Schlussfolgerungen zu ziehen, brauchen wir eine formale Sprache, die die Gegebenheiten und Regeln ausdrücken kann.


Wir könnten also z.B. unser Wissen wie folgt darstellen

  • Luftzug(C,3)

und folgende Regel definieren:

  • WENN (Luftzug(C,3))
    DANN (Fallgrube(B,3)
    ODER Fallgrube(D,3)
    ODER Fallgrube(C,2)
    ODER Fallgrube(C,4))

Wir könnten allerdings genauso gut z.B. folgende Darstellung wählen:

  • L-C_3
  • L-C_3 -> F-B_3 | F-D_3 | F-C_2 | F-C_4

Haben wir eine Darstellung der Sätze definiert, müssen wir wiederum formal festlegen, was diese Darstellung bedeutet.

Z.B. die Symbolkette ODER könnte alle möglichen Bedeutungen annehmen

  • umgangssprachliches ‚oder‘ bedeuten, aber genauso gut auch
  • eine Abkürzung sein für ‚und nicht‘, oder vielleicht auch die Bedeutung eines
  • umgangssprachlichen ‚und‘ haben

Beispiel – Syntax vs. Semantik: elementare Algebra

Wir haben als Kinder unter zur Hilfenahme von Fingern, Bohnen etc. gelernt, bestimmten Zahlen bestimmte Bedeutungen zuzuweisen und auf diesen die Grundrechnungsarten auszuführen. Wir sind so mit ihnen Vertraut, dass es auf Anhieb oft schwer fällt, die Form von der Bedeutung zu trennen.

Für uns ist es im Allgemeinen ganz klar, was 1+1 bedeutet, nämlich 2, und jeder hat ein Gefühl dafür, was 2 ist. Das sich die Ziffer 2 jedoch (z.B. in einem mechanischen System) durch eine rein mechanische Anwendung von Transformationsregeln ergeben kann, bedingt ein Umdenken.


Abstrahiert man also das System der elementaren Algebra, um es innerhalb einer mechanischen Struktur auszudrücken, sind Zahlen abstrakte Symbolketten zusammengesetzt aus den

  • Ziffern 0-9.

Um Sätze zu bilden führen wir

  • Symbole für die Grundrechnungsarten (+,- etc.), und
  • einen Gleichungsoperator =

ein und legen fest, wie korrekte Sätze auszusehen haben.
Die Rechenregeln müssen als Umformungsregeln definiert werden, die rein mechanisch auf die Sätze angewendet werden.


Nehmen wir z.B. die gewohnte Addition her (die Formalisierung in diesem Beispiel stellt keinen Anspruch auf formale Korrektheit oder Vollständigkeit – wir wollen nur das Konzept der Abstraktion von Form und Bedeutung veranschaulichen):

Definieren wir folgende Regeln für die Addition zweier Ziffernfolgen (wobei ‚a‘ für eine beliebige Ziffer steht und ‚u‘ für den Übertrag):

  1. Sollte eine der beiden Ziffernfolgen kürzer sein, als die andere, füge dieser links so viele ‚0‘ hinzu, dass beide gleich lang sind
  2. Beginne mit den am weitesten rechts stehenden Ziffern der Ziffernfolgen und wende eine der folgenden Regeln an:
    0+a=a, 1+1=2, 1+2=3, …, 5+5={0, u}, … 9+9={8, u}
  3. Sollte ein Übertrag entstanden sein, merke dir dies für die nächste Runde
  4. Sollte ein Übertrag von der vorhergehenden Runde vorhanden sein, wende die entsprechende Regel auf die neue Ziffer und 1 an
  5. Schreibe die sich ergebende Ziffer an die linke Stelle der Ergebnisziffernfolge
  6. Reduziere die zu addierenden Ziffernfolgen jeweils um die rechteste Ziffer
  7. Wiederhole Schritt 2-6 solange, bis die Ziffernfolgen abgearbeitet sind
  8. Sollte ein Übertrag vorhanden sein, füge ‚1‘ an die linke Stelle der Ergebnisziffernfolge

Aus der Zeichenfolge ‚987+654‘ wird so durch rein mechanische Anwendung der Regeln die Zeichenfolge 1641.


Definieren wir jedoch andere Umformungsregeln für das Symbol ‚+‘ kommen wir zu ganz anderen Ergebnissen:

  • Definieren wir Regeln wie für die Subtraktion, entsteht aus der Zeichenfolge ‚987+654‘ die Zeichenfolge ‚333‘
  • Sagen wir, dass wir links beginnend abwechselnd jeweils eine Ziffer der beiden Ziffernfolgen aufschreiben wollen, kommen wir zum Ergebnis ‚968574‘

usw.


Die Bedeutung, also Interpretation, des Symbols ‚+‘, also der Summe, ist außer Reichweite eines formalen Systems.

So wie das Ergebnis der abstrakten Ableitung zu 100% von unserer Definition der Regeln abhängig ist, liegt und auch die Interpretation des Ergebnisses ganz bei uns: das Ergebnis kann z.B.

  • für eine Anzahl stehen – also z.B. 7 Äpfel
  • eine Bewertung ausdrücken – also z.B. 100 Punkte ist super
  • unsere Zukunft voraussagen – also z.B. Wenn das Ergebnis 333 ist, haben wir Glück

Wir haben also einerseits die Bedeutung der Sätze, andererseits eine formale Repräsentation mit der wir arbeiten.
Dieser Trennung von Form und Bedeutung entsprechen die zwei grundlegenden Aspekte jeder Sprache von Syntax und Semantik.

Syntax vs. Semantik

(Logik Einführung Kapitel 4.1)

„Die Schönheit liegt im Auge des Betrachters“

Als Menschen sind wir gewohnt, jeden Satz zu interpretieren und so mit seiner Bedeutung zu hantieren. Als Kinder lernen wir, gewissen Gegebenheiten und Bedeutungen Worte zuzuweisen – den Worten unserer natürlichen Sprache wohnt die Bedeutung implizit inne.

In einem mechanischen System ist dies natürlich nicht so – Fakten lassen sich formalisieren und darstellen, ihre Bedeutung lässt sich von einem Computer jedoch nicht erfassen.
D.h. jeder mechanische Folgerungsmechanismus muss auf einer formalen Repräsentation der Daten erfolgen, bei der Worte ad hoc keine Bedeutung haben – wollen wir automatisiert Schlüsse generieren, müssen wir entsprechende abstrakte Regeln für abstrakte Daten definieren.

Beispiel – Syntax vs. Semantik: Wumpus-Welt

Grundlage ist die mögliche Wumpus-Welt aus der Spiel-Spezifikation.

Wir spüren einen Luftzug auf Feld [C,3] und folgern daraus, dass sich auf den Feldern [B,3], [D,3], [C,2] oder [C,4] eine Fallgrube befinden kann.

Ein mechanisches System kann jedoch weder mit einem Luftzug noch mit einer Fallgrube oder gar mit umliegenden Feldern etwas anfangen.
Um automatisiert Schlussfolgerungen zu ziehen, brauchen wir eine formale Sprache, die die Gegebenheiten und Regeln ausdrücken kann.


Wir könnten also z.B. unser Wissen wie folgt darstellen

  • Luftzug(C,3)

und folgende Regel definieren:

  • WENN (Luftzug(C,3))
    DANN (Fallgrube(B,3)
    ODER Fallgrube(D,3)
    ODER Fallgrube(C,2)
    ODER Fallgrube(C,4))

Wir könnten allerdings genauso gut z.B. folgende Darstellung wählen:

  • L-C_3
  • L-C_3 -> F-B_3 | F-D_3 | F-C_2 | F-C_4

Haben wir eine Darstellung der Sätze definiert, müssen wir wiederum formal festlegen, was diese Darstellung bedeutet.

Z.B. die Symbolkette ODER könnte alle möglichen Bedeutungen annehmen

  • umgangssprachliches ‚oder‘ bedeuten, aber genauso gut auch
  • eine Abkürzung sein für ‚und nicht‘, oder vielleicht auch die Bedeutung eines
  • umgangssprachlichen ‚und‘ haben

Beispiel – Syntax vs. Semantik: elementare Algebra

Wir haben als Kinder unter zur Hilfenahme von Fingern, Bohnen etc. gelernt, bestimmten Zahlen bestimmte Bedeutungen zuzuweisen und auf diesen die Grundrechnungsarten auszuführen. Wir sind so mit ihnen Vertraut, dass es auf Anhieb oft schwer fällt, die Form von der Bedeutung zu trennen.

Für uns ist es im Allgemeinen ganz klar, was 1+1 bedeutet, nämlich 2, und jeder hat ein Gefühl dafür, was 2 ist. Das sich die Ziffer 2 jedoch (z.B. in einem mechanischen System) durch eine rein mechanische Anwendung von Transformationsregeln ergeben kann, bedingt ein Umdenken.


Abstrahiert man also das System der elementaren Algebra, um es innerhalb einer mechanischen Struktur auszudrücken, sind Zahlen abstrakte Symbolketten zusammengesetzt aus den

  • Ziffern 0-9.

Um Sätze zu bilden führen wir

  • Symbole für die Grundrechnungsarten (+,- etc.), und
  • einen Gleichungsoperator =

ein und legen fest, wie korrekte Sätze auszusehen haben.
Die Rechenregeln müssen als Umformungsregeln definiert werden, die rein mechanisch auf die Sätze angewendet werden.


Nehmen wir z.B. die gewohnte Addition her (die Formalisierung in diesem Beispiel stellt keinen Anspruch auf formale Korrektheit oder Vollständigkeit – wir wollen nur das Konzept der Abstraktion von Form und Bedeutung veranschaulichen):

Definieren wir folgende Regeln für die Addition zweier Ziffernfolgen (wobei ‚a‘ für eine beliebige Ziffer steht und ‚u‘ für den Übertrag):

  1. Sollte eine der beiden Ziffernfolgen kürzer sein, als die andere, füge dieser links so viele ‚0‘ hinzu, dass beide gleich lang sind
  2. Beginne mit den am weitesten rechts stehenden Ziffern der Ziffernfolgen und wende eine der folgenden Regeln an:
    0+a=a, 1+1=2, 1+2=3, …, 5+5={0, u}, … 9+9={8, u}
  3. Sollte ein Übertrag entstanden sein, merke dir dies für die nächste Runde
  4. Sollte ein Übertrag von der vorhergehenden Runde vorhanden sein, wende die entsprechende Regel auf die neue Ziffer und 1 an
  5. Schreibe die sich ergebende Ziffer an die linke Stelle der Ergebnisziffernfolge
  6. Reduziere die zu addierenden Ziffernfolgen jeweils um die rechteste Ziffer
  7. Wiederhole Schritt 2-6 solange, bis die Ziffernfolgen abgearbeitet sind
  8. Sollte ein Übertrag vorhanden sein, füge ‚1‘ an die linke Stelle der Ergebnisziffernfolge

Aus der Zeichenfolge ‚987+654‘ wird so durch rein mechanische Anwendung der Regeln die Zeichenfolge 1641.


Definieren wir jedoch andere Umformungsregeln für das Symbol ‚+‘ kommen wir zu ganz anderen Ergebnissen:

  • Definieren wir Regeln wie für die Subtraktion, entsteht aus der Zeichenfolge ‚987+654‘ die Zeichenfolge ‚333‘
  • Sagen wir, dass wir links beginnend abwechselnd jeweils eine Ziffer der beiden Ziffernfolgen aufschreiben wollen, kommen wir zum Ergebnis ‚968574‘

usw.


Die Bedeutung, also Interpretation, des Symbols ‚+‘, also der Summe, ist außer Reichweite eines formalen Systems.

So wie das Ergebnis der abstrakten Ableitung zu 100% von unserer Definition der Regeln abhängig ist, liegt und auch die Interpretation des Ergebnisses ganz bei uns: das Ergebnis kann z.B.

  • für eine Anzahl stehen – also z.B. 7 Äpfel
  • eine Bewertung ausdrücken – also z.B. 100 Punkte ist super
  • unsere Zukunft voraussagen – also z.B. Wenn das Ergebnis 333 ist, haben wir Glück

Wir haben also einerseits die Bedeutung der Sätze, andererseits eine formale Repräsentation mit der wir arbeiten.
Dieser Trennung von Form und Bedeutung entsprechen die zwei grundlegenden Aspekte jeder Sprache von Syntax und Semantik.