Logik-Basierte Sprachverarbeitung - Cheatsheet

Aussagenlogik und ihre Prinzipien

Definition:

Aussagenlogik untersucht die formale Struktur von Aussagen mittels logischer Operatoren.

Details:

• Aussagen (\textit{propositionale Variable}): entweder wahr (\textit{True}) oder falsch (\textit{False})
• Logische Operatoren: \textit{und} (\textbf{\textit{AND}}: \texttt{∧}), \textit{oder} (\textbf{\textit{OR}}: \texttt{∨}), \textit{nicht} (\textbf{\textit{NOT}}: \texttt{¬}), \textit{impliziert} (\textbf{\textit{Implikation}}: \texttt{→}), \textit{äquivalent} (\textbf{\textit{Äquivalenz}}: \texttt{↔})
• Wahrheitstafeln zur Bestimmung von Wahrheitswerten
• Gesetze der Aussagenlogik: \textit{Identitätsgesetz}, \textit{Negationsgesetz}, \textit{Idempotenzgesetz}, \textit{Domination}, \textit{Double Negation}, \textit{Kommutativität}, \textit{Assoziativität}, \textit{Distributivität}, \textit{De Morgan’sche Gesetze}
• \textbf{Beispiel:} Wahrheitstabelle für \textit{A ∧ B}

  A	B	A ∧ B
  Wahr	Wahr	Wahr
  Wahr	Falsch	Falsch
  Falsch	Wahr	Falsch
  Falsch	Falsch	Falsch

Prädikatenlogik und Quantoren

Definition:

Formale Sprache für mathematische Aussagen und Argumente; ermöglicht die Verwendung von Variablen und Quantoren zur Darstellung von Aussagen über Objekte.

Details:

• Quantoren: Existenz- (\exists) und Allquantor (\forall)
• Syntax: Aussagen, Prädikate, Quantoren
• Beispiel für Aussagenlogik: \(P(a) \wedge Q(a)) \rightarrow R(a)\)
• Beispiel für Prädikatenlogik: \(\forall x (P(x) \rightarrow Q(x))\)
• Prädikate: Funktionen, die auf Objekte angewendet werden (z.B. P(x))
• Variablen: Plaatshaber für Objekte (z.B. x)

Syntax und Semantik von Prolog

Definition:

Syntax und Semantik von Prolog behandeln, wie Prolog-Programme strukturiert und interpretiert werden.

Details:

• Fakten: Basiswissen \textit{klauselinduktiv} - \texttt{fakt.}
• Regeln: Wenn-Dann-Aussagen - \texttt{kopf :- körper.}
• Abfragen: Zielsetzungen/Retrieval - \texttt{?- abfrage.}
• Syntax: Terme, Variablen, Listen (head/tail \texttt{[X|Y]}), Prädikate
• Semantik: Herbrand-Universum und Modelltheorie, Resolventen, Bestandteile wie Atom, Klausel
• Resolution: \texttt{Modus Ponens}, Suchstrategien (Tiefensuche u. Breitensuche)
• Unifikation: \texttt{=>} Algorithmus, Variablenzuweisungen

Unifikation und Backtracking in Prolog

Definition:

Unifikation: Lösen von Gleichungssystemen zwischen Termen. Backtracking: systematisches Durchsuchen eines Suchraums nach Lösungen durch Zurückgehen zu vorherigen Entscheidungspunkten bei Fehlschlägen

Details:

• Unifikation: Prüfen, ob Terme gleich gemacht werden können (\textit{Matcher-Prozess})
• Backtracking: Nach Fehlschlag bei einer Regel wird zur letzten Entscheidung zurückgegangen und alternative Lösungen werden versucht
• Unifikationsalgorithmus: Verwendet Substitutionen um Variablen zu ersetzen
• Substitutionen: \(x = y / x \leftarrow y\)
• Ziel: Finden einer allgemeinen Substitution, die alle Terme gleich macht
• Falls Unifikation fehlschlägt, wird Backtracking-Mechanismus verwendet
• Backtracking erlaubt das Testen alternativer Regeln und Fakten in Prolog-Programmen

Grundlegende Begriffe und Strukturen semantischer Netze

Definition:

Semantische Netze: Wissensrepräsentation mittels Knoten (Konzepte) und Kanten (Beziehungen).

Details:

• Knoten: Stellen Begriffe/Konzepte dar
• Kanten: Darstellen von Beziehungen zwischen Knoten
• Gerichtete Kanten: Beziehungen haben eine Richtung (z.B. 'ist-ein')
• Unterschiedliche Typen von Kanten: Attributive Kanten, relationale Kanten
• Beispiel: \texttt{[Auto] --{hat Farbe}--> [Rot]}
• Funktionalität: Ermöglicht Inferenz durch Pfadsuche und Beziehungserkennung
• Anwendung: NLP, Wissensdatenbanken

Resolutionsverfahren und deren Anwendung

Definition:

Das Resolutionsverfahren ist ein automatisches Beweisverfahren in der Prädikatenlogik.

Details:

• Basis: Herleitung Widerspruch durch Konversion zu Klauseln und Anwendung der Resolutionsregel.
• Resolutionsregel: \(C \lor L, eg L \lor D\) ergibt \(C \lor D\).
• Anwendungen in der Logik-Basierten Sprachverarbeitung: Bestimmung der logischen Konsistenz, Herleitung von Antworten aus Wissensbasen, maschinelles Beweisen.
• Vorteile: Allgemeinheit und Vollständigkeit in der Aussagenlogik und Prädikatenlogik.
• Nachteile: Potenzieller hoher Ressourcenverbrauch (Rechenaufwand).

SAT-Solver und logische Entscheidungsprobleme

Definition:

Prozeduren zur Bestimmung der Erfüllbarkeit boolescher Formeln (SAT) und Lösung von Entscheidungsproblemen der Aussagenlogik.

Details:

• SAT: Boolesche Formel in konjunktiver Normalform (CNF)
• Logische Entscheidungsprobleme: Erfüllbarkeit (SAT), Validität, Tautologie, Widerspruch
• DPLL-Algorithmus: Basisallee für viele SAT-Solver
• Modernere SAT-Solver: CDCL (Conflict-Driven Clause Learning)
• Anwendungen: Hardware-Verifizierung, Software-Fehlererkennung, Planung und Scheduling
• Komplexität: NP-vollständig

Logik-basierte semantische Analyse in der natürlichen Sprachverarbeitung

Definition:

Logik-basierte semantische Analyse nutzt formale Logiken zur Analyse und Interpretation der Bedeutung von natürlichen Sprachäußerungen.

Details:

• Verwendet symbolische Logik (z.B. Prädikatenlogik) zur Repräsentation von Bedeutungen
• Ermöglicht Schlussfolgerungen und Validierung semantischer Konsistenz
• Schlüsselkomponenten: Syntax, Semantik und logische Inferenz
• Wichtige Formalismen: Lambda-Kalkül, Montague-Semantik
• Anwendung in Wissensrepräsentation, Informationsabruf, Maschinellem Verstehen