Logik KLAUSUR Flashcards
(22 cards)
Definition Aussagenlogik
In der Aussagenlogik werden, wie der Name schon sagt, Aussagen über logische Operatoren verknüpft.
Syntax Aussagenlogik
(Regeln, wie es strukturiert wird) Mengen OP, E und (w, f) seien paarweise disjunkt E heißt Signatur und seine Elemente sind die Aussagenvariablen Menge der Aussagelogischen Formeln wird rekursiv definiert Aussagenvariablen, w und f, A und B sind (atomare) Formeln
Operatoren & Symbole Aussagenlogik
w: wahr f: falsch -A: nicht A - Negation A^B: A und B - Konjunktion AvB: A oder B - Disjunktion A -> B: wenn A dann B - Implikation AB: A genau dann, wenn B - Äquivalenz es ist erlaubt, unendlich viele Formeln zu erzeugen
Semantik Aussagenlogik
( Zuordnung von Bedeutung zum syntaktischen Gebilde) Den Aussagevariablen müssen Wahrheitswerte zugeordnet werden, die Zuständen der Welt entsprechen. Def. Eine Abbildung I: E -> (w, f), die jeder Aussagevariablen einen Wahrheitswert zuordnet, heißt Belegung oder Interpretation oder auch Welt. Jede Aussagevariable kann zwei Wahrheitswerte annehmen
Wahrheitswerte für komplexe Formeln bestimmen (Aussagenlogik)
Rangfolge der logischen Operatoren müssen angegeben werden. Falls Ausdrücke geklammert sind, ist immer zuerst der Term in der Klammer auszuwerten. Bei ungeklammerten Formeln sind die Prioritäten wie folgt geordnet, beginnend mit der stärksten Bindung: -, ^, v, ->,
Semantische Äquivalenz (Aussagenlogik)
Die semantische Äquivalenz wird vor allem dazu dienen, in der Metasprache, das heißt der natürlichen Sprache, über die Objektsprache, nämlich die Logik, zu reden. Die Aussage „A = B“(Gleichzeichen mit 3 Strichen) etwa besagt, dass die beiden Formeln A und B semantisch äquivalent sind. Die Aussage „A B“ hingegen ist ein syntaktisches Objekt der formalen Sprache der Aussagenlogik.
Klassen für Formeln (Aussagenlogik)
Eine Formel heißt: erfüllbar, falls sie bei mindestens einer Belegung wahr ist. allgemeingültig oder wahr, falls sie bei allen Belegungen wahr ist. Wahre Formeln heißen auch Tautologien. unerfüllbar, falls sie bei keiner Belegung wahr ist. Jede erfüllende Belegung einer Formel heißt Modell der Formel.
Allgemeingültige Äquivalenzen (Aussagenlogik)
Nachteile Beweisverfahren (Aussagenlogik)
- im Worst Case sehr lange Rechenzeit
- Die Rechenzeit wächst also exponentiell mit der Zahl der Variablen.
- Somit ist dieses Verfahren für große Variablenanzahl zumindest im Worst-Case nicht an- wendbar.
Fundamentale Eigenschaften von Kalkülen (Aussagenlogik)
Um sicherzustellen, dass ein Kalkül keine Fehler macht, definieren wir zwei fun- damentale Eigenschaften von Kalkülen.
KNF - Konjunktive Normalform (Aussagenlogik)
Eine Formel ist in konjunktiver Normalform genau dann, wenn sie aus eine Konjunktion von Klauseln besteht.
Eine Klausel K besteht aus Disjunktion von Literalen.
Ein Literal schließlich ist eine Variable oder negierte Variable.
Jede aussagenlogische Formel lässt sich in eine äquivalente konjunktive Normalform transformieren
Resolutionskalkül zum Beweis der Unerfüllbarkeit von Formel (Aussagenlogik)
Der Resolutionskalkül zum Beweis der Unerfüllbarkeit von Formeln in konjunktiver Normalform ist korrekt und vollständig. Das heißt, für jede unerfüllbare Formel kann man mit Resolution die leere Klausel herleiten und umgekehrt.
Resolution Vorteile gegenüber anderen Kalkülen (Aussagenlogik)
- besitzt die Resolution nur zwei Inferenzregeln,
- und sie arbeitet auf Formeln in konjunktiver Normalform. Dies macht die Implementierung einfacher.
- Reduktion der Anzahl von Möglichkeiten für die Anwendung von Inferenzregeln in jedem Schritt beim Beweisen, wodurch dann der Suchraum reduziert und die Rechenzeit verringert wird.
Vorgehensweise beim Lösen eines Logikrätsels (Aussagenlogik)
- Formalisierung
- Transformation in Normalisierung
- Beweis
Definition Hornklausel
Vorteil Hornklausel
Diese Klauseln haben den Vorteil, dass sie nur einen Schluss zulassen und daher deutlich einfacher zu interpretieren sind. Viele Zusammenhänge lassen sich mit derartigen Klauseln beschreiben.
Modus Ponens
Wird in der Logik als Schlussregel verwendet.
Er erlaubt es, aus zwei Aussagen der Form (Wenn A, dann B) und (A) (den beiden Prämissen der Schlussfigur) eine Aussage der Form B (die Konklusion der Schlussfigur) herzuleiten.
Wird auch Implikationsbeseitigung genannt.
Backward chaining & SLD-Resolution
Ein Kalkül zu verwenden, der mit der Anfrage startet und rückwärts arbeitet, bis die Fakten erreicht sind.
Für das backward chaining auf Hornklauseln wird SLD-Resolution verwendet. SLD steht für „Selection rule driven linear resolution for definite clauses“. Am obigen Bei- spiel, ergänzt durch die negierte Anfrage .Skifahren -> f )
SLD-Resolution spielt in der Praxis eine wichtige Rolle, denn Programme in der Lo- gikprogrammiersprache Prolog bestehen aus prädikatenlogischen Hornklauseln, und ihre Abarbeitung erfolgt mittels SLD-Resolution
Linear Resolution
Bedeutet, dass immer mit der gerade aktuell hergeleiteten Klausel weitergearbeitet wird. Dies führt zu einer starken Reduktion des Suchraumes.
Wahrheitstafel vs Semantische Bäume
Wahrheitstafel: stellt einen Algorithmus dar, der für jede Formel nach endlicher Zeit alle Modelle bestimmt. Damit sind die Mengen der unerfüllbaren, der erfüllbaren und der allgemeingültigen Formeln entscheidbar. Die Rechenzeit der Wahrheitstafelmethode für die Erfüllbarkeit wächst im Worst-Case exponentiell mit der Zahl n der Variablen.
Semantische Bäume: vermeidet die Betrachtung von Variablen, die in Klauseln nicht vorkommen, und spart daher in vielen Fällen Rechenzeit, aber im Worst-Case ist sie ebenfalls exponentiell.
Für die Entscheidung zwischen den beiden Verfahren kann man daher als Faustregel angeben, dass bei vielen Klauseln mit wenigen Variablen die Wahrheitstafelmethode vorzuziehen ist und bei we- nigen Klauseln mit vielen Variablen die Resolution voraussichtlich schneller zum Ziel kommen wird.
Anwendung Aussagenlogische Beweiser
Verifikation digitaler Schaltungen oder die Generie- rung von Testmustern zum Test von Mikroporzessoren in der Fertigung
In der KI kommt die Aussagenlogik bei einfachen Anwendungen zum Einsatz.
Komplexere logische Zusammenhän- ge können mit der Prädikatenlogik wesentlich eleganter ausgedrückt werden.
Limitierung McCulloch and Pitts Neuronal Model
- nicht sehr realstisch, da echte Neuronen viel komplexer sind
- es kann keine lineare Summierungen von Neuronen geben
- Auffälligster Unterschied: reale Neuronen haben nicht nur eine einzelne Ausgangssituation sondern einen spike train, also eine Folge von Impulsen.
- Neuronen werden nicht sequentiell nach einer Computeruhr aktualisiert, sondern aktualisieren sich zufällig (asynchron)
