KI II

Ein Symbol ist eine atomare, eindeutige Textzeichenkette (z. B. A, B), die nicht weiter zerlegt wird und für eine Aussage über die Welt steht.

Eine Interpretation weist jedem verwendeten Symbol einen Wahrheitswert in {0,1} zu, wobei 1 für „wahr“ und 0 für „falsch“ steht.

Eine Formel ist entweder ein einzelnes Symbol oder durch die Junktoren ¬, ∧, ∨ aus bereits existierenden Formeln gebildet.

Syntax beschreibt, wie Formeln formal aufgebaut sind, Semantik beschreibt, wie diesen Formeln Bedeutungen bzw. Wahrheitswerte zugeordnet werden.

Eine Formel, die unter jeder möglichen Interpretation wahr ist. Bsp.: A ∨ ¬A (A ODER nicht A)

Eine Formel, die unter keiner Interpretation wahr ist; sie ist immer falsch.

Bsp.: A ∧ ¬A (A UND nicht A)

Eine Formel ist erfüllbar, wenn es mindestens eine Interpretation gibt, unter der sie wahr ist.

Aus α folgt β, wenn jede Interpretation, die α wahr macht, auch β wahr macht.

Eine logische Äquivalenz liegt vor, wenn zwei logische Ausdrücke den gleichen Wahrheitswert besitzen.

Sind zwei Formeln γ0​ und γ1​ logisch äquivalent, dann bleibt jede Formel α logisch äquivalent, wenn man ein oder mehrere Vorkommen von γ0​ in α durch γ1​ ersetzt.

Sie listet für alle möglichen Belegungen der Symbole die resultierenden Wahrheitswerte einer Formel auf.

Um zu prüfen, ob eine Formel tautologisch, erfüllbar oder unerfüllbar ist und um logische Äquivalenzen zu erkennen.

Ein Literal ist ein Symbol oder dessen Negation, z. B. A oder ¬A.

Eine Disjunktion (ODER-Verknüpfung) von Literalen, z. B. (A ∨ ¬B ∨ C).

Eine Konjunktion (UND) von Klauseln, z. B. (A ∨ B) ∧ (¬C ∨ D).

Eine Disjunktion (ODER) von Konjunktionen von Literalen, z. B. (A ∧ B) ∨ (¬C ∧ D).

Eine Formel in Klausenform wird als Menge von Klauseln geschrieben, wobei jede Klausel eine Menge von Literalen ist. Dabei entspricht die innere Menge einer Disjunktion (∨), die äußere Menge einer Konjunktion (∧).

Bsp.: {{A, B}, {C, ¬A}} ≙ (A ∨ B) ∧ (C ∨ ¬A)

1. Negationen nach innen schieben (De-Morgan-Regeln), bis sie nur noch vor Atomen stehen.

2. Rekursiv Unterformeln in KNF überführen.

3. Distributivgesetze anwenden, um Disjunktionen über Konjunktionen zu verteilen.

4. Assoziativität und Kommutativität nutzen, um die Formel als Konjunktion von Disjunktionen zu schreiben.

5. Vereinfachen, z. B. doppelte Literale entfernen.

Eine Klausel mit höchstens einem positiven Literal (z. B. ¬A ∨ ¬B ∨ C).

Eine Konjunktion von Hornklauseln.

Für Hornformeln gibt es effiziente (polynomielle) Algorithmen zur Erfüllbarkeitsprüfung.

(¬A ∨ ¬B ∨ C) entspricht (A ∧ B) → C.

Der Algorithmus prüft, ob eine Hornformel erfüllbar ist.

Er markiert zunächst alle Fakten, die direkt wahr sind. Wenn alle Voraussetzungen einer Regel wahr sind, wird auch deren Konsequenz wahr gemacht. Führt dies zu einem Widerspruch, ist die Formel unerfüllbar. Sonst ergibt die Markierung ein Modell.

Wenn alle Prämissen einer Klausel erfüllt sind, deren Konsequenz 0 (bzw. Widerspruch) ist – also ein Konflikt auftaucht.

Aus α → β,α folgt β.

Aus α → β,¬β folgt ¬α.

Weil ein sehr umfangreiches, explizites Weltwissen gebraucht wird, um alle relevanten Schlussfolgerungen ziehen zu können.

• Deduktives Schließen leitet sichere Schlussfolgerungen aus gegebenem Wissen ab.

• Monotones Schließen bedeutet, dass neues Wissen frühere Schlussfolgerungen nicht ungültig macht.

• Nicht-monotones Schließen erlaubt, dass neue Informationen alte Annahmen zurücknehmen.

• Induktives Schließen verallgemeinert aus Beobachtungen, liefert aber keine logische Sicherheit.

Aus zwei Klauseln, die ein Literal und sein Negiertes enthalten, kann man eine neue Klausel ohne diese beiden Literale ableiten.

Aus (A ∨ C) und (¬A ∨ D) folgt (C ∨ D).

Wenn eine Menge von Klauseln unerfüllbar ist, dann kann man durch wiederholte Resolution irgendwann die leere Klausel ableiten.

Sie steht für einen Widerspruch; ihr Auftreten zeigt, dass die ursprüngliche Formelmenge unerfüllbar ist.

Man zeigt, dass α ∧ ¬β unerfüllbar ist, indem man mit Resolution einen Widerspruch (□) herleitet.

Aus beobachteten Symptomen (Abweichungen) auf zugrundeliegende Fehlerursachen zu schließen.

Ein System ist ein Tripel (SD,COMPS,OBS), wobei:

• SD die logische Beschreibung des Systemverhaltens ist,

• COMPS die endliche Menge der Systemkomponenten darstellt,

• OBS die beobachteten Fakten über das System enthält.

Eine Menge von Komponenten ∆, für die angenommen wird, dass sie abnormal sind, so dass SD ∪ OBS ∪ (D(∆, COMPS - ∆)) konsistent ist.

1. Anomalieerkennung

2. Diagnose (Fehlersuche/-lokalisierung)

3. Reparatur

Eine festgestellte Abweichung zwischen dem beobachteten Verhalten eines Systems und dem erwarteten (modellierten) Verhalten.

• Beim phenomenological approach wird das beobachtete Systemverhalten (z. B. Sensordaten, Energieverbrauch) direkt als normal oder anomal klassifiziert.

• Beim model-based approach wird das normale Verhalten mithilfe eines Modells simuliert und mit den realen Messungen verglichen; weichen diese stark ab, wird eine Anomalie erkannt.

Ein System ist eine Kombination aus miteinander wechselwirkenden und voneinander abhängigen Komponenten, die zusammen eine einheitliche Gesamtheit bilden und einen eindeutig beschreibbaren Zweck erfüllen.

• Fault: eigentliche Ursache (z. B. defektes Bauteil)

• Failure: beobachtetes Fehlverhalten des Systems

• Symptom: messbare Abweichung (z. B. falscher Messwert).

Ein Fehler, bei dem ein Signal dauerhaft auf 0 oder 1 „hängenbleibt“ – das Verhalten ändert sich nach Auftreten des Fehlers nicht mehr.

Ein Fehler, der zeitweise auftritt und wieder verschwindet.

Ein schleichender Fehler, der sich langsam entwickelt und oft besser durch zeitbasierte / statistische Verfahren erkannt wird als durch Logik allein.

• ein (korrektes) Modell des Systems sagt das Normalverhalten vorher

• Abweichungen zwischen Modell und Realität werden genutzt, um Fehlerursachen abzuleiten

Sie enthält logische Formeln, die das Verhalten der Komponenten im Normalfall modellieren.

Für die Menge aller betrachteten Komponenten im System.

Für die Menge der Beobachtungen (Messwerte, Symptome).

• beschreibt nur das korrekte Normalverhalten eines Systems

• keine expliziten Fehlermodelle

Form:

¬AB(c1) ∧ … ∧ ¬AB(cn) → Φ

• AB(c) = Komponente ist abnormal

• ¬AB(c) = Annahme: Komponente ist gesund

• Φ = korrektes Verhalten

Merksatz: „WFM sagt nur, was gilt, wenn alles gesund ist.

• „ADDER/MULTIPLIER definieren Idealverhalten unter Gesundheit.“

ADDER(x) → [¬AB(x) → out = in1 + in2]

MULTIPLIER(x) → [¬AB(x) → out = in1 × in2]

• ADDER(x), MULTIPLIER(x) = Typ der Komponente

• Verhalten gilt nur unter der Annahme ¬AB(x) (nicht abnormal)

• Wichtig:

  • bei AB(x) → keine Festlegung des Verhaltens

  • kein typisches Fehlverhalten modelliert

• Diagnoseidee: Beobachtung widerspricht Gleichung

  • ¬AB(x) nicht haltbar

  • x potenziell defekt

„Component c ist abnormal“ – also defekt oder nicht im Normalzustand.

Eine Diagnose, bei der keine echte Teilmenge der Komponentenmenge ebenfalls eine Diagnose ist.

Weil Übermengen von Diagnosen (mit zusätzlichen Fehlerkomponenten) weniger informativ sind und es potentiell exponentiell viele Diagnosen gibt.

Eine Menge von Komponenten, die nicht alle gleichzeitig „OK“ sein können, weil SD ∧ OBS ∧ „alle OK“ widersprüchlich ist.

Ein Konflikt, bei dem keine echte Teilmenge ebenfalls ein Konflikt ist.

Minimale Diagnosen sind minimale Treffermengen (Hitting Sets) der minimalen Konfliktmengen.

Eine Menge von Komponenten, die jede Konfliktmenge mindestens an einer Stelle „trifft“, d. h. mindestens eine Komponente aus jeder Konfliktmenge enthält.

Weil es im Allgemeinen ein NP-schweres Set-Covering-Problem ist und die Anzahl der Diagnosen exponentiell mit der Zahl der Konflikte wachsen kann.

Aussagenlogik kann nur atomare Fakten modellieren. Prädikatenlogik erlaubt Aussagen über Objekte, deren Beziehungen und Mengen von Objekten mittels Prädikaten, Variablen und Quantoren.

Aus Termen (Variablen, Konstanten, Funktionen), Prädikaten, Junktoren, Quantoren sowie daraus gebildeten atomaren und zusammengesetzten Sätzen.

Terme bezeichnen Objekte, Prädikate Eigenschaften oder Relationen über Objekte, Funktionen ordnen Objekten eindeutig andere Objekte zu.

Ein Prädikat, angewendet auf Terme, z. B. DUCK(Donald).

Er sagt aus: „Für alle Objekte x gilt …“.

Er sagt aus: „Es gibt mindestens ein Objekt x, für das … gilt“.

Eine Zuordnung, die Variablen auf Objekte, Funktionen auf Abbildungen und Prädikate auf Relationen über einem Universum U abbildet.

Wenn sie unter einer gegebenen Interpretation und Variablenbelegung gemäß den Semantikregeln (für Prädikate, Junktoren und Quantoren) den Wahrheitswert wahr erhält.

Gebundene Variablen stehen im Wirkungsbereich eines Quantors, freie Variablen nicht. Formeln mit freien Variablen sind keine abgeschlossenen Aussagen.

Zum Beispiel: ∀x (DUCK(x) → SWIM(x)).

Ein Modell ist eine Interpretation, unter der alle Formeln der Theorie wahr sind. Es beschreibt eine konkrete Struktur, in der die Theorie erfüllt ist.

Eine Formel ist in Prenex-Normalform, wenn alle Quantoren am Anfang stehen und der quantorenfreie Rest keine weiteren Quantoren enthält.

Eine Formel ist in Skolem-Normalform, wenn sie keine Existenzquantoren mehr enthält. Existenzvariablen werden durch Skolemfunktionen ersetzt, wobei die Erfüllbarkeit erhalten bleibt.

Eine neue Funktionssymbol-Einführung, mit der ein existenzquantifizierter Term ersetzt wird, z. B. ∃y wird durch f(x1,…,xn) ersetzt.

Sie erhält die Erfüllbarkeit: Die resultierende Formel ist erfüllbar genau dann, wenn es die ursprüngliche ist.

Unifikation findet passende Substitutionen für Terme. Resolution nutzt diese, um aus Klauseln neue Klauseln abzuleiten und Widersprüche zu identifizieren.

• Um Resolution in der Prädikatenlogik anwenden zu können

• Macht Literale mit Variablen syntaktisch gleich

Wie?

• Berechnet eine Substitution θ

• Ersetzt Variablen durch Terme

• Gilt, wenn:

  subst(θ, α) = subst(θ, β)

• Falls unmöglich: keine Unifikation

• datengetriebenes Schließen

• startet mit gegebenen Fakten

• wendet Regeln an, deren lhs erfüllbar ist

• fügt die rhs als neue Fakten hinzu

• wiederholt, bis keine neuen Fakten entstehen

Eigenschaften:

• berechnet alle ableitbaren Fakten

• benötigt Unifikation

• kann ineffizient sein (viele irrelevante Ableitungen)

• zielgetriebenes Schließen

• startet mit einer Anfrage / Ziel

• sucht Regeln, deren rhs zum Ziel passt

• versucht, deren lhs zu beweisen

• rekursiv, oft mit Backtracking

Eigenschaften:

• leitet nur benötigte Fakten her

• ebenfalls Unifikation

• effizient für konkrete Anfragen

Planung ist das Finden einer Aktionssequenz, die einen gegebenen Startzustand in einen gewünschten Zielzustand überführt.

Ein Planungsproblem besteht aus:

• einem Zustandsraum S,

• einer Aktionsmenge A ⊆ S×S,

• einem Startzustand s0 ∈ S,

• einem Zielzustand sg ∈ S.

Eine Aktion ist ein Zustandsübergang l∼r. Wird sie im Zustand l ausgeführt, resultiert der Zustand r.

Eine endliche Sequenz von Aktionen, die s0 nach sg​ überführt, oder NONE, falls kein solcher Plan existiert.

Zustände werden auf Prädikate abgebildet, Aktionen auf logische Implikationen. Planung entspricht der logischen Ableitung von Zielprädikaten aus Startprädikaten.

PL1 ist Prädikatenlogik erster Stufe. Sie erlaubt strukturierte Zustandsbeschreibungen und logisches Schließen, ist jedoch strikt monoton.

Ein Schlussverfahren, bei dem neue Informationen bereits abgeleitete Aussagen nicht ungültig machen können.

Wenn durch Aktionen nur neue Fakten hinzugefügt werden und keine zuvor gültigen Fakten verloren gehen.

Weil PL1 keine Mechanismen besitzt, um das Zurücknehmen oder Invalidieren von Fakten auszudrücken.

Wenn Aktionen Zustände verändern, indem sie frühere Fakten ungültig machen (z. B. Ortswechsel von Objekten).

Es kann reale, dynamische Weltveränderungen nur dann modellieren, wenn sie monoton abstrahierbar sind.

Ein Plan ist ein Beweis dafür, dass der Zielzustand logisch aus dem Startzustand und den Aktionsregeln folgt.

Non-monotonic reasoning erlaubt, dass Aussagen, die in einem Zustand wahr sind, in späteren Zuständen falsch werden. Genau das ist bei Zustandsänderungen durch Aktionen erforderlich.

Wahrheitswerte von Prädikaten werden relativ zu einer Situation modelliert. Ein Prädikat gilt nicht absolut, sondern nur in einer bestimmten Situation S.

Als Sequenz von Situationen S1→S2→⋯→Sp​, wobei jede neue Situation durch die Ausführung einer Aktion entsteht.

• poss(action, S) beschreibt, ob eine Aktion in Situation S ausführbar ist.

• do(action, S) beschreibt die neue Situation, die aus der Ausführung der Aktion in S entsteht.

Es müssen explizit alle Effekte einer Aktion modelliert werden – sowohl positive als auch negative. Dies führt zu hohem Modellierungsaufwand und ist eng mit dem Frame-Problem verbunden.

Ein Prädikat, dessen Wahrheitswert von der Situation abhängt (z. B. holds(on(a,b), S)).

Man muss explizit angeben, welche Fakten von einer Situation zur nächsten unverändert bleiben – das kann zu sehr vielen Regeln führen.