Wissensrepräsentation mit Logik

Wissensrepräsentation mit Logik ist eine Art der Wissensrepräsentation, die auf formaler Logik basiert. Zum Aufbau wissensbasierter Systeme müssen Objekte der realen Welt in einer Sprache repräsentiert werden, die ein Computer versteht, damit er mit diesem Wissen umgehen kann. So kann z. B. ein Experte sein Wissen über sein Fachgebiet formalisieren und für viele andere nutzbar machen (sog. Expertensystem). Ein logisches System ist eine hierzu geeignete formale Sprache.

Wissensrepräsentation mit Logik

Wissenbasiertes System

Verwendet man die klassische Logik als Repräsentation eines wissensbasierten Systems, spricht man von einem klassisch-logischen System.

Klassisch-logisches System

Ein solches logisches System lässt sich in zwei grundlegende Komponenten aufteilen. Die erste der beiden Komponenten eines klassisch-logischen Systems ist die sogenannte Inferenzrelation, um das menschliche Schließen zu modellieren. Die zweite Komponente besteht aus einer Repräsentationssprache, in der die Wissensbasis, der Kern des wissensbasierten Systems, formuliert werden kann. Die Aufgabe dieser Repräsentationssprache wird im klassisch-logischen System von den klassischen Logiken übernommen. Das bedeutet, dass das vorhandene Wissen in prädikatenlogischen Formeln kodiert wird. Das wichtigste Potential des auf diesen beiden Komponenten definierten klassisch-logischen Systems besteht jedoch in der Inferenz von Wissen selbst. Wird die Inferenzrelation entsprechend der logischen Repräsentationsprache definiert, so ergibt sich die Möglichkeit, Wissen zu inferieren, das bedeutet, aus bereits in dem System vorhandenem Wissen neues Wissen über die Inferenzrelation abzuleiten.

Inferenz im klassisch-logischen System

Aus der Einteilung der Inferenz in Deduktion, Induktion und Abduktion ergibt sich, dass sowohl Induktion, als auch Abduktion als Schlussfolgerungsmechanismen nicht notwendigerweise korrekt sind. Somit stellt Deduktion die einzig sichere Methode im Schluss dar (vgl. 3-Teilung der Inferenz nach Peirce (1839–1914)), weil das in diesem Fall abgeleitete Wissen immer wahr ist. Aufgrund dieser Eigenschaft benutzen logische Systeme die deduktive Instanz der Inferenz als Modellierung des logischen Folgerungsoperators. Eine korrekte Schrittfolge dieser Inferenzprozedur, in deren Verlauf neues Wissen B aus vorhandenem Wissen W abgeleitet wird, bezeichnet man auch als Beweis.

Mit Verwendung einer derartig deduktiven Inferenzkomponente wird es allerdings unmöglich, einmal als wahr abgeleitete Schlussfolgerungen wieder zu revidieren. Daher ist es in klassisch-logischen Systemen, die auf rein deduktiven Verfahren beruhen, unmöglich, nicht-monotones Schließen als fundamentales Merkmal menschlicher Inferenz korrekt zu modellieren.

Ein möglicher Lösungsansatz, der diesen Defekt im Inferenzmodell des logischen Systems beheben soll, besteht in der graduellen Abstufung der Korrektheit von Ableitungen. Diese Abstufung kann auf zwei Arten erreicht werden. Auf der einen Seite geschieht dies durch Verwendung von Wahrscheinlichkeiten. Indem Ableitungen über Prozentzahlen quantifiziert werden, erhält man eine probabilistische Logik in der graduelle Abstufungen durchaus möglich sind. Auf der anderen Seite wird die graduelle Abstufung von Schlussfolgerungen in Fuzzy-Logik durch die Verwendung von Gradzahlen zur Beschreibung vager Prädikate ermöglicht.

Aufbau eines logischen Systems

Grundkomponenten

• $\Sigma$ = Signatur
• Int($\Sigma$)= Menge aller Interpretationen über der Signatur $\Sigma$
• For($\Sigma$)= Menge aller Formeln über der Signatur $\Sigma$
• $\models _{\Sigma }$ = Erfüllungsrelation

Die Signatur Σ

Die mengentheoretische Intuition hinter dem Begriff der Signatur ist eine Menge aus Namen und Begriffen, durch die alle Elemente einer zu repräsentierenden Wissensbasis W formalisiert werden. Genauer gesagt handelt es sich bei den Elementen einer Signatur um Namen, die nach Prädikaten und Funktoren klassifiziert und nach ihrer Stelligkeit differenziert werden.

Aussagenlogische Signatur

Signaturen in der Aussagenlogik enthalten als Elemente nullstellige Namen oder Bezeichner, die auch als Aussagenvariablen bezeichnet werden.

Beispiel: $\Sigma _{AL}=\{Schnee,schneit,Sonne,kalt\}$

Prädikatenlogische Signatur

Signaturen in der Prädikatenlogik 1. Stufe beinhalten null- und mehrstellige Funktoren und Prädikate. Somit kann eine Signatur in der Prädikatenlogik als Tupel betrachtet werden, wobei git:

$\Sigma$=(Func, Pred)

Mit

• Func = Menge von null- oder mehrstelligen Funktoren nullstellige Funktoren werden als Konstanten bezeichnet
• Pred = Menge von null- oder mehrstelligen Prädikaten

Aufgrund der Tatsache, dass die Aussagenlogik eine echte Teilmenge der Prädikatenlogik 1. Stufe ist, enthält die Menge aller prädikatenlogischen Signaturen ebenso die Menge aller aussagenlogischen Signaturen als echte Teilmenge. Daraus folgt, dass die Aussagenvariablen durch nullstellige Prädikate modelliert werden können. Diese können atomare Formeln, also die Atome der Aussagenlogik darstellen.

Beispiel: $\Sigma _{PL1}=\{Schneewegschaufeln(x,y),Mann,Gehweg,Kinder,Einfahrt\}$

Die Menge der Interpretationen Int(Σ)

Die wichtigste Eigenschaft einer Interpretation innerhalb des logischen Systems besteht darin, dass sie, zusammen mit der Erfüllungsrelation, die Verbindung zwischen der Syntax (in Form der Signatur $\Sigma$) der Repräsentationssprache und der Semantik von Aussagen herstellt, indem sie die Namen der Signatur zu Objekten einer Wissensbasis W zuweist.

Interpretation in der Aussagenlogik

Bei der Interpretation einer aussagenlogischer Signatur wird jeder Aussagenvariable aus der Signatur $\Sigma$ ein Wahrheitswert zugeordnet. Diese Zuordnung erfolgt durch eine Interpretation $\sigma$ für die gilt:

$\sigma \in Int(\Sigma )=\Sigma \longrightarrow \{0,1\}$

Dabei bezeichnet die Menge Int($\Sigma$) die Menge aller Funktionen von einer gegebenen Signatur $\Sigma$ nach $\{0,1\}$. Diese $\sigma$-Interpretation einer Signatur $\Sigma$ wird auch Belegung genannt, weil durch diese Funktion jeder Aussagenvariable mit einem Wahrheitswert belegt wird.

Interpretation in der Prädikatenlogik

In der PL1 lässt sich der Aufbau einer Interpretation wie folgt beschreiben:

$I=(U_{I},Func_{I},Pred_{I})$

wobei gilt:

• $U_{I}$ = nichtleere Trägermenge (englisch carrier set) mit allen Objekten einer Interpretation
• $Func_{I}$ = Funktionsmenge:

$\{f_{I}:\underbrace {U_{I}\times \dots \times U_{I}} _{n-mal}\rightarrow U_{I}|f\in Func\;mit\;Stelligkeit\;n\in N\}$

• $Pred_{I}$ = Menge von Relationen:

$\{p_{I}\subseteq \underbrace {U_{I}\times \dots \times U_{I}} _{n-mal}\rightarrow U_{I}|p\in Pred\;mit\;Stelligkeit\;n\in N\}$

Eine Interpretation I in PL1 bildet Funktoren und Prädikaten der Signatur auf Objekte der zu repräsentierenden Welt über dem Universum U gemäß folgender Tabelle ab:

Nullstellige Funktoren	Elemente aus U
Ein- oder mehrstellige Funktoren	Funktionen
Nullstellige Prädikate	Belegung mit Wahrheitswert
Einstellige Prädikate	Teilmenge von U
Mehrstellige Prädikate	Relationen R $\subseteq \underbrace {U\times \dots \times U} _{Stelligkeit\;n}$

Beispiel:

Seien Signatur $\Sigma =(\{eins^{0},plus^{2}\},\{gleich^{2}\})$ mit $p^{i}$ = p, mit Stelligkeit i und Interpretation

$(N,\{+\in N\times N\rightarrow N\},\{\{(n,m)\in N\times N|n=m\}\})$

gegeben. So gilt:

I(eins)	$1\in N=U$
I(plus)	$+\in N\times N\rightarrow N$
I(gleich)	$\{(n,m)\in N\times N|n=m\}=\{(0,0),(1,1),\dots \}$

Die Menge der Formeln For(Σ)

Die Menge der Formeln über eine Signatur $\Sigma$ ist ein wesentlicher Bestandteil eines logischen Systems. Formeln bilden die syntaktische Repräsentation von Objekten der zu repräsentierenden Welt W, von Aussagen über diese Objekte, sowie von Sachverhalten, mit denen die Welt W beschrieben wird. Eine wesentliche Eigenschaft der Formeln eines logischen Systems ist ihre Wohlformuliertheit (englisch well-formed formula). For($\Sigma$) enthält alle Formeln, die sich entsprechend der vorgegebenen Grammatik für Formeln aus den Elementen der Signatur $\Sigma$ bilden lassen. Genau für diese Formeln gilt die Eigenschaft der Wohlformuliertheit.

Formeln in Aussagenlogik

Handelt es sich bei der Signatur um eine rein aussagenlogische Signatur, d. h. die Signatur enthält ausschließlich Aussagevariablen (= nullstellige Prädikate), so bilden diese selbst bereits atomare aussagenlogische Formeln, die sogenannten Literale. Die Menge For($\Sigma$) umfasst bei einer aussagenlogischen Signatur somit die Signatur selbst und alle komplexeren Formen, die entsprechend der Grammatik für Formeln durch logische Verknüpfungen gebildet werden können.

Beispiel:

Sei eine Signatur $\Sigma$ = {Mo,Di,Mi,Do,Fr,Sa,So} gegeben. So können z. B. die folgenden Formeln gebildet werden:

$\neg Mo\Rightarrow Di$
$\neg Mo\wedge \neg Di\wedge \neg Mi\wedge \neg Do\wedge \neg Fr\Rightarrow Sa\wedge So$
$Mo\vee Di\vee Mi\vee Do\vee Fr\Rightarrow Sa\vee So$

Formeln in Prädikatenlogik

Neben den im vorangegangenen Abschnitt aufgeführten aussagenlogischen Formeln For($\Sigma _{AL}$) können Formeln in der prädikatenlogischen Formelmenge For($\Sigma$) ebenso Variablen und Quantifizierungen über diese Variablen enthalten. Enthält eine Signatur $\Sigma$ das einstellige Prädikat P(x), so enthält die Formelmenge For($\Sigma$) das Prädikat selbst, sowie existentielle und universelle Quantifizierung der Aussage P über die Individuenvariable x

Beispiel:

Sei eine Signatur Beispiel: = {Vater(x,y), Großvater(x,y)} gegeben und seien x, y, z Variablen, so lässt sich daraus die folgende Formel ableiten: $\forall x.\forall y.\forall z:$Vater(x,y)$\wedge$ Vater(y,z)$\Rightarrow$Großvater(x,z)

Sei ferner eine Signatur $\Sigma$={loves(x,y)} gegeben, wobei x, y Variablen für Personen bezeichnen. So lassen sich folgende Sätze durch prädikatenlogische Formeln über dieser Signatur formulieren:

Everybody loves somebody	$\forall x.\exists y:loves(x,y)$
Somebody loves somebody	$\exists x.\exists y:loves(x,y)$
Everybody loves everybody	$\forall x.\forall y:loves(x,y)$
Nobody loves everybody	$\neg (\exists x.\forall y:loves(x,y))$
Somebody loves nobody	$\exists x.\forall y:\neg loves(x,y)$

Die Erfüllungsrelation

Zusammen mit der Interpretation einer Signatur stellt die Erfüllungsrelation die Verbindung zwischen den syntaktisch durch Formeln repräsentierten Objekten einer Welt W und deren Semantik in W dar. Eine Erfüllungsrelation gibt an, wann eine Formel in einer Interpretation gilt und ob eine Formel in einer Interpretation wahr oder falsch ist. Da diese Relation eine der Grundkomponenten des logischen Systems ist, stellt jedes logische System eine solche Erfüllungsrelation (satisfaction relation) bereit:

$\models _{\Sigma }\subseteq Int(\Sigma )\times For(\Sigma )$

Beispiel:

Sei $I_{1}$eine Interpretation, A ein Literal und gelte $I_{1}$(A) = 1, dann gilt $I_{1}\models _{\Sigma _{AL}}A$.

Überträgt man die Erfüllungsrelation auf eine Relation zwischen Formeln, so erhält man die logische Folgerung:

$\models _{\Sigma }\subseteq For(\Sigma )\times For(\Sigma )$
$F\models _{\Sigma }G\Leftrightarrow \forall I\in \Sigma \longrightarrow \{0,1\}:I\models _{\Sigma }F\Rightarrow I\models _{\Sigma }G$

Dabei wird $F\models _{\Sigma }G$gelesen als "aus F folgt logisch G" oder "G folgt logisch aus F".