Kapitel 2
Aussagenlogik
Jetzt beginnt der mathematische Teil der KI-Grundlagen. Aussagenlogik ist eine formale Sprache, mit der wir einfache Aussagen präzise beschreiben, verknßpfen und automatisch auswerten kÜnnen. Sie ist ein Fundament fßr symbolische KI, automatische Beweiser, Expertensysteme, digitale Schaltungsprßfung und später auch fßr stärkere Logiken wie die Prädikatenlogik.
Wichtig ist der rote Faden: Wir starten nicht direkt mit Beweisen. Zuerst klären wir, welche Formeln ßberhaupt erlaubt sind. Dann geben wir diesen Formeln Bedeutung. Danach schauen wir, wie aus Wissen neues Wissen folgt. Erst dann kommen Normalformen, Resolution, Hornklauseln und Komplexität.
Berechenbarkeit, Komplexität und Grenzen
Aussagenlogik ist entscheidbar
Die Wahrheitstafelmethode ist ein einfacher Algorithmus: Fßr jede Belegung wird der Wahrheitswert einer Formel berechnet. Dadurch kann man grundsätzlich entscheiden, ob eine Formel erfßllbar, unerfßllbar oder allgemeingßltig ist.
Entscheidbarkeit
Es gibt ein Verfahren, das nach endlicher Zeit eine Antwort liefert.
Aber entscheidbar heiĂt nicht automatisch schnell.
Warum Wahrheitstabellen teuer werden
Worst Case
Die Laufzeit wächst exponentiell mit der Zahl der Variablen.
Bei 10 Variablen sind es 1024 Belegungen. Bei 20 Variablen sind es schon 1.048.576 Belegungen. Bei 30 Variablen Ăźber eine Milliarde. Das ist die kombinatorische Explosion.
Resolution ist oft besser, aber nicht magisch
Resolution vermeidet oft das vollständige Durchprobieren aller Belegungen. Trotzdem kann auch Resolution im Worst Case exponentiell viele Klauseln erzeugen.
Faustregel
Das ist keine Garantie, aber eine praktische Orientierung.
3-SAT und NP-Vollständigkeit
Eine zentrale Frage ist: Gibt es allgemein viel schnellere Algorithmen fßr aussagenlogische Erfßllbarkeit? Fßr das 3-SAT-Problem ist bekannt, dass es NP-vollständig ist.
3-SAT
Schon diese eingeschränkte Variante ist NP-vollständig.
Das bedeutet nicht, dass jedes einzelne Problem praktisch unlĂśsbar ist. Es bedeutet aber: Im allgemeinen Fall darf man keine einfache polynomielle LĂśsung erwarten, solange das P/NP-Problem offen bleibt.
Hornklauseln sind gĂźnstiger
Fßr Hornklauseln ist die Situation besser. Dort kann die Erfßllbarkeit deutlich effizienter geprßft werden, weil die Struktur der Regeln viel eingeschränkter ist.
Hornklauseln
Diese Effizienz ist ein Grund, warum Hornklauseln in logiknahen Systemen so wichtig sind.
NOVA warnt
NOVA fragt: Warum ist mathematische Entscheidbarkeit nicht dasselbe wie praktische Nutzbarkeit?
Ein Verfahren kann garantiert enden, aber trotzdem bei groĂen Eingaben viel zu lange brauchen.
NOVA Energie-Log
RTX-Verbrauch
NOVA schätzt hier, wie viel GPU-Energie deine Bildanalyse- und CUDA-Läufe bisher ungefähr verbraucht haben.
Lade Energie-Daten...