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
|
|
|
|
|
|
|
Home 
Merkblatt