Kapitel 4 - Logik erster Ordnung
Welche Eigenschaften definieren die Logik erster Ordnung?
Nach der Logik erster Ordnung besteht die Welt aus Objekten, d.h. Dingen, die
individuelle Identitäten und Eigenschaften haben, welche die Objekte
differenzieren. Zwischen Objekten können Relationen bestehen.
Einige der Relationen können Funktionen sein.
Wie sind Sätze in der Logik erster Ordnung aufgebaut?
Es gibt wie in der Aussagenlogik Sätze, welche die Welt repräsentieren.
Sätze bestehen aus Thermen und
Prädikatsymbolen.
Terme können funktionale Ausdrücke, Variablen oder
Konstanten sein.
Aus einfachen Sätzen werden durch Junktoren und Quantoren komplexe
Sätze gebaut.
Welche Bestandteile gehören zum Symbolvorrat der Logik erster Ordnung?
- Konstantensymbole
- Prädikatsymbole
- Funktionssymbole
- Terme
- Atomare Sätze
- Zusammengesetzte Sätze
-
Quantoren
Universelle Quantifizierung mit dem Allquantor
Existentielle Quantifizierung
Geschachtelte Quantoren
- Quantoren und Negation
- Gleichheit
Welche Merkmale haben Konstantensymbole?
Durch Interpretation wird festgelegt, auf welches Objekt in der Welt sich ein
Konstantensymbol bezieht. Jedes Konstantensymbol benennt genau ein Objekt. Aber
nicht alle Objekte der Welt müssen aber Namen haben und Mehrfachbenennungen sind
zugelassen.
Welche Merkmale definieren Prädikatsymbole?
Durch Interpretation wird festgelegt, auf welche Relation in der Welt sich ein
Prädikatsymbol bezieht. Eine Relation ist eine Menge von Tupeln von Objekten, die
die Relation erfüllen.
Welche Merkmale definieren Funktionssymbole?
Funktionssymboel werden durch Interpretation auf spezielle Relationen
abgebildet, die in einer bestimmten Stelle (üblicherweise die Letzte) eindeutig
sind. Eine n-stellige Funktion kann durch eine Menge von (n+1) Tupeln definiert
werden. Die letzte Stelle eines solchen Tupels stellt den Wert der Funktion unter
den ersten n Stellen dar.
Welche Merkmale definieren Terme?
Ein Term ist ein logischer Ausdruck der sich auf ein Objekt
in der Modellwelt bezieht. Somit sind auch Konstanten- und Variablensymbole Terme.
Außer Konstantensymbolen sind Ausdrücke, gebildet aus einem Funktionssymbol und
einer in Klammern eingeschlossenen Folge von Termen, wieder Terme. Ein Term der
keine Variablen enthält, heißt Grundterm.
Welche Merkmale definieren Atomare Sätze (Atome)?
Atomare Sätze bestehen aus einem Prädikatsymbol gefolgt von einer in Klammern
eingeschlossenen Liste von Termen. Ein atomarer Satz beschreibt einen Fakt, dessen
Bedeutung entweder true oder false ist. Ein atomarer Satz ist
wahr, wenn die Relation, auf die sich das Prädikatsymbol bezieht, zwischen den
Objekten gilt, auf denen sich die Terme beziehen.
Welche Merkmale definieren Zusammengesetzte Sätze?
Mittels Junktoren können aus Sätzen komplexere Sätze gebildet
werden. Die Teilsätze können zusammengesetzt oder auch atomar
sein. Die Semantik zusammengesetzter Sätze sind Wahrheitswerte und sind analog zur
Aussagenlogik definiert.
Welche Quantorenarten gibt es und wie sind diese definiert?
Universelle Quantifizierung über den Allquantor
- Katzen sind Säugetiere
- = Alle Katzen sind Säugetiere
- V x Katze(x) => Säugetier(x)
Existentielle Quantifizierung
- Zur Repräsentation natürlich sprachlicher Sätze, die Aussagen über einige
Objekte aus einer Menge machen
- Micky hat eine Schwester, die eine Katze ist
Es gibt x Schwester (x, Micky) & Katze (x); die Auflösung wird disjunktiv
verknüpft
Geschachtelte Quantoren
- Gleichartige Quantoren werden abkürzend zusammengefaßt
- Kommen Allquatoren und Existenzquatoren gemischt vor, dann ist Reihenfolge
wichtig
Quantoren und Negation
- Anwendung der De Morganschen Regeln
Welche Merkmale definieren die Gleichheit?
Das Gleichheitszeichen kann als eine Art spezielles Prädikat verwendet werden.
Sind t1 und t2 Terme, dann ist t1 = t2 ein Satz.
Beschreiben Sie zwei Anwendungsbereiche für die Logik erster Ordnung!
Die Verwandtschaftsdomäne
In der Verwandtschaftsdomäne gibt es
-
Objekte: Personen
-
Einstellige Prädikate: Männlich, Weiblich
-
Zweistellige Prädikate: Elternteil, Geschwister, Bruder, Kind,
Enkel
-
Funktionen: Mutter,Vater
Sätze in einer Wissensbasis werden als Axiome betrachtet.
Mittels Definitionen kann man aus diesen Axiomen neue Konzepte erzeugen und neue
Axiome ableiten. Beim Aufbau einer Wissensbasis gibt es zwei Probleme
- Reichen die Axiome und Definitionen zur Beschreibung einer Domäne aus?
- Ist die Domände durch die Axiome und Definitionen überspezifiziert?
Die Mengendomäne
In der Mengendomäne gibt es
-
Konstanten: LeereMenge
-
Prädikate: Element,Teilmenge,Menge
-
Funktionen: Durchschnitt, Vereinigung, Einfügen
Es gibt acht Axiome, welche die Eigenschaften einer Menge definieren Fragen
und Antworten:
- Axiome und Fakten einer Domäne werden mittels Tell in die Knowledge Base
eingefügt. (Zusicherungen)
- Mittels Ask können dann logische Konsequenzen aus den Sätzen abgefragt
werden. (Fragen oder Ziele)
Repräsentation von Veränderungen in der Welt
Was sind Diachronische Regeln?
Diachronische Regeln, sind Regeln, welche beschreiben, wie sich eine Welt
verändert oder auch nicht verändert.
Was beschreibt ein Situationskalkül?
Die Welt wird als eine Folge von Situationen betrachtet. Jede Situation stellt
einen "Schnappschuß" des Zustandes der Welt zu dem Augenblick dar. Eine Situation
wird aus einer anderen durch Aktionen erstellt kann benannt werden.
Um den Wechsel einer Situation zur nächsten zu beschreiben, wird eine Funktion
benutzt:
- Ergebnis(Aktion, Situation)
- Ihr Wert ist eine neue Situation
- Die Situation entsteht, wenn die Aktion auf die Situation angewendet wird
Aktionen, welche eine Wirkung auf die Folgesituation haben sind
Wirkungsaxiome.
Axiome, welche Sicherstellen, dass eine Wirkung über mehrere Situationen erhalten
bleibt, sind Frameaxiome. Wirkungsaxiome und Frameaxiome zusammen,
beschreiben vollständig, wie sich eine Welt aufgrund der Aktionen des Agenten
entwickelt.
Wofür benötigt ein Agent eine Ortsbestimmung?
" Am Beispiel der Wumpus Welt ist die Ortsbestimmung besonders wichtig " Der
Agent muss wissen, in welche Richtung er blickt o Hier einfach durch einen Winkel
definiert " Der Agent benötigt eine einfache Landkarte, um aus einer Richtung und
einer Ortsangabe eine neue Ortsangabe berechnen zu können
Ableiten verborgener Eigenschaften einer Welt
Worin unterscheiden sich Kausale Regeln und Diagnostische Regeln?
Synchrone Regeln setzen verschiedene Eigenschaften desselben Weltzustandes in
Relation.
Kausale Regeln
Geben die Richtung einer angenommenen Kausalität in einer Welt wieder.
Systeme, die mit kausalen Regeln schlußfolgern, heißen modellbasierte
Schlußfolgerungssysteme.
Diagnostische Regeln
Leiten das Vorhandensein verborgener Eigenschaften direkt aus den
Wahrnehmungen ab. Man kann aber keine so aussagekräftigen Schlüsse ziehen, wie das
bei Kausalen Regeln der Fall ist.
Was sind Präferenzen zwischen Aktionen bei Zielbasierte Agenten?
Die Wünschbarkeit von Aktionen wird durch bestimmt Prädikate
beschrieben. Prädikate können sein Gut, Mittel, Riskant oder Tödlich.
Die Auswahl einer Aktion erfolgt gemäß der Reihenfolge, welche die Prädikate auf
Grund ihrer Semantik haben. Regeln dieser Art heißen
Aktions-Wert-Regeln.
Mit welchen drei Methoden lassen sich Aktionsfolgen bestimmen?
Inferenz
Mit geeigneten Axiomen kann man mit ASK eine Aktionsfolge aus der Wissensbasis
ableiten. Für größere Welten wäre aber der Rechenaufwand zu groß.
Suchen
Mit Best-First-Suche kann ein Pfad zum Ziel bestimmt werden. Dazu muss Wissen
in eine Menge geeigneter Operatoren und Zustandsrepräsentationen umgeformt werden.
Planen
Erfolgt mit speziellen Schlußfolgerungssystemen, die entworfen wurden, über
Aktionen zu folgern.
Inferenzen in der Logik erster Ordnung
Welche drei zusätzlichen Inferenzregeln gibt es in der Logik erster Ordnung?
- Allquator - Beseitigung (für alle...)
- Existenzquantor - Beseitigung (Es gibt...)
- Existenzquantor - Einführung
Was wissen sie über den verallgemeinerten Modus Ponens und die Unifikation?
Der Modus ponems enthält die n+1 Prämissen und die Konklusion der
Substitution. Vor Anwendung werden alle Sätze in die kanonische Form (Hornsätze)
umgewandelt.
Sind entweder atomare Sätze oder Implikationen mit einer Konjunktion atomarer Sätze
auf der linken und einem einzelnen atomaren Satz auf der anderen Seite. Einfügen in
die Wissensbasis werden alle Sätze in Hornsätze umgewandelt durch Anwendung der
Inferenzregeln:
- Existenzquantor-Beseitigung
- Und-Beseitigung
- Weglassen der Allquatoren
Nachteil ist aber, dass nicht alle Sätze in Hornsätze überführbar sind
Unifikation
Es wird angenommen, dass es eine Prozedur UNIFY gibt, die zwei atomare Sätze p
und q zu einer Substitution überführt, die die beiden Eingabesätze identisch macht.
Konflikte durch doppelte Variablennamen werden durch Umbenennung aufgelöst. Falls
ein Unifikator für q und p exisitert, soll UNIFY immer den allgemeinsten Unfikator
liefern.
Was macht die Vorwärts- und Rückwärtsverkettung und wozu braucht man sie?
Es gibt einen Satz und man möchte diese über die Wissensbasis vergleichen.
Vorwärtsverkettung
- Üblicherweise durch hinzufügen eines meist atomaren Satzes zur KB
- Als Teil der Tell-Funktion realisierbar
- Es werden alle Implikationen betrachtet
- Gelten auch die übrigen Teile der Antezedenzien dieser Implikation kann das
Sukzedenz der Implikation zur Wissensbasis zugefügt werden
Rückwärtsverkettung
Hiermit ist es möglich, alle Antworten auf eine Frage an eine KB zu bekommen.
Realisiert wird dies über über die ASK-Funktion. Die Rückwärtsverkettung arbeitet
folgendermaßen:
- Prüft zunächst, ob die Antworten auf die Frage direkt von der KB geliefert
werden kann
- Dann wird nach allen Implikationen gesucht, deren Sukzedenz
mit der Frage unifizierbar sind
- Dann wird versucht, die Antezedenzien dieser Implikation
wiederrum durch Rückwärtsverkettung zu beweisen (Konjunkte werden hintereinander
bewiesen)
- Im Laufe dieser Schritte werden Substitutionen aufgebaut,
die ausgegeben werden
Resolution: Eine vollständige Inferenzprozedur
Was wissen Sie über die Inferenzregel Resolution?
Diese Inferenzregel ist eine Resolution-Regel in erweiterter Form. Es wird
erlaubt, dass Disjunktionen mehrere Elemente enthalten. Sie wird auf Sätze der
Logik erster Ordnung erweitert:
- Es muß unifiziert werden
- Substitutionen der Ausgangssätze werden abgeleitet
- Die Resolution Regel ist eine Erweiterung des Modus Ponens
- Die implikative Normalform ist eine Erweiterung der Hornform (linke Seite
stimmt mit Hornform überein, aber auf rechter Seite ist Disjunktion von Atomen
erlaubt)
- Der Modus Ponens ist ein Spezialfall der Resolution-Regel in implikativer
Form, welcher aber kein vollständiges Beweissystem wie die verallgemeinerte
Resolution Regel ist
Welche acht Schritte sind zur Umformung in die implikative Normalform notwendig?
- Beseitigung der Implikationen
- Negationen nach innen ziehen
- Umbenennung von Variablen
- Quantoren nach außen ziehen
- Skolemisierung (Entfernen der Existenzquantoren)
- Distribution von Konjunktion über Disjunktion (Distributivgesetz)
- Abflachen eingebetteter Strukturen (Assoziativgesetz)
- Umwandlung von Disjunktionen in Implikationen
Welche zwei Möglichkeiten gibt es zur Behandlung der Gleichheit?
Eine Möglichkeit ist die Axiomisierung, (Eigenschaften als
Äquivalenzrelation).
Zweite Möglichkeit ist spezielle Inferenzregel Demodulation.
Welche vier Resolution-Strategien gibt es?
Unit-Präferenz
Führe, wenn möglich einen Inferenzschritt mit einer Klausel, die nur aus einem
Literal besteht durch.
Set of support
Wähle eine Teilmenge "Set of support" der Sätze aus, und wende die Resolution
Regel immer auf einen Satz an aus "Set of support" und einen anderen an und füge
das Ergebnis in "Set of support" ein.
Input Resolution und Linear Resolution
Wähle die Sätze zur Problembeschreibung als Eingabe und wende die Resolution
Regel immer auf einen Satz aus dieser Menge und einem anderen an. Linear Resolution
ist vollständig und ist eine Verallgemeinerung der Input Resolution.
Subsumption
Entfernt alle Sätze, die von einem Satz in der Wissensbasis subsumiert werden,
d.h. aus diesem Satz logisch folgen. Dadurch kann Suchraum so klein wie nur möglich
gehalten werden.
|
|
|
Kapitel 1
|
Intelligente Agenten
|
|
Agententypen, Eigenschaften einer Agentenumgebung, Problemformulierung,
Problemtypen, Zustandsraum
|
|
Kapitel 2
|
Lösen durch Suchen
|
|
Knoten, Rand, allgemeiner Suchalgorithmus, blinde Suchverfahren, heuristische
Suchfunktionen, Optimierung
|
|
Kapitel 3
|
Schlußfolgern
|
|
Wissensbasis, Inferenzmaschine, autonom, Wissensrepräsentation, Konsequenz,
Inferenzen, Aussagenlogik
|
|
Kapitel 4
|
Logik 1. Ordnung
|
|
Eigenschaften und Bestandteile, Symbole und Sätze,Ortsbestimmung, Ableiten,
Vorwärts- und Rückwärtsverkettung
|
|
Kapitel 5
|
Planen
|
|
Repräsentationen, Ziele und Aktionen, Situationsraum, Planraum, Kausale Kanten,
Promotion, Demotion
|
|
Kapitel 6
|
Handeln
|
|
Bedingtes Planen, Ausführungsüberwachung, Unsicherheit, Evidenz,
Wahrscheinlichkeitsaxiome, Bayessche Regel
|
|
Kapitel 7
|
Beobachten
|
|
Modell lernender Agenten, Performanzelement, Lernelement, Kritik, Problemgenerator,
induktives Lernen
|
|
Kapitel 8
|
Neuronale Netze
|
|
Struktur, Begriffe, Rechenelemente, Perzeptron, Anwendungen
|
|
|
Quelle: Die Ausarbeitung basiert auf dem Skript von Prof. Dr.
Werner Dilger
|
|
|
|
|
Merkblatt