Logik und Beweise: die Regeln, nach denen KI schließt

Aussagen, Junktoren und Wahrheitstabellen, die Falle mit der Implikation, Quantoren und Arten von Beweisen — und warum XOR die ersten neuronalen Netze stoppte.

14 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 7 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Jede Definition in dieser Reihe ist eine logische Aussage, und jedes „also“ danach ist ein Stück eines Beweises. Logik sind die Spielregeln: Sie sagt, wann eine Aussage wahr ist und wie man aus wahren Aussagen korrekt weitere ableitet. Und in der künstlichen Intelligenz kommt sie zweimal vor — als Sprache, in der man über Algorithmen spricht, und als eigenes Fachgebiet, aus dem die ersten „denkenden“ Programme hervorgingen.

Die Symbole ¬, ∧, ∨, ⇒, ∀ und ∃ sind uns zum ersten Mal im Teil über mathematische Notation begegnet. Hier erfährst du, wie genau sie funktionieren, wo man bei ihnen am häufigsten Fehler macht und wie man aus ihnen einen Beweis zusammensetzt.

1. Aussagen und Wahrheitswerte

Definition — Aussage

Eine Aussage ist eine Behauptung, bei der es sinnvoll ist zu sagen, ob sie wahr oder falsch ist. Ihr Wahrheitswert ist 1 (wahr) oder 0 (falsch).

Aus einfachen Aussagen P, Q, … werden mit logischen Junktoren zusammengesetzte Aussagen gebildet. Der Wahrheitswert einer zusammengesetzten Aussage hängt nur von den Wahrheitswerten ihrer Teile ab.

2. Junktoren und Wahrheitstabellen

Wie ein Junktor funktioniert, zeigt am besten eine Wahrheitstabelle: für jede Kombination der Werte von P und Q eine Zeile. Zwei Variablen haben 2 · 2 = 4 Kombinationen, n Variablen 2ⁿ.

• Die Negation ¬P kehrt den Wert um.
• Die Konjunktion P ∧ Q („und“) gilt nur, wenn beide Teile gelten.
• Die Disjunktion P ∨ Q („oder“) gilt, wenn mindestens einer gilt — auch beide.
• Die Implikation P ⇒ Q („wenn, dann“) gilt nur in einem einzigen Fall nicht: P gilt und Q nicht.
• Die Äquivalenz P ⇔ Q gilt, wenn beide Teile denselben Wert haben.
• Das exklusive Oder P ⊕ Q (XOR) gilt, wenn genau einer von beiden gilt.

3. Implikation: die häufigste Falle

Definition — Umkehrung und Kontraposition

Zur Implikation P ⇒ Q ist die Umkehrung Q ⇒ P und die Kontraposition ¬Q ⇒ ¬P.

Satz. Eine Implikation ist äquivalent zu ihrer Kontraposition, aber nicht zu ihrer Umkehrung.

Die Tabelle zeigt es ohne Diskussion: Die Spalten der Implikation und der Kontraposition sind gleich, die Umkehrung unterscheidet sich in zwei Zeilen.

Die zweite Falle ist die erste Zeile mit P = 0: Wenn die Voraussetzung nicht gilt, ist die Implikation wahr, egal was Q ist. „Wenn 7 gerade ist, bin ich der Papst“ ist eine wahre Aussage. Das klingt seltsam, ergibt aber Sinn — eine Implikation verspricht nur etwas über die Situation, in der P gilt, und dieses Versprechen lässt sich nicht brechen, wenn P nicht gilt.

4. Tautologien und äquivalente Aussagen

Definition — Tautologie, Kontradiktion, Äquivalenz

Eine Tautologie ist eine zusammengesetzte Aussage, die bei jeder Belegung der Variablen wahr ist (z. B. P ∨ ¬P). Eine Kontradiktion ist immer falsch (P ∧ ¬P).

Die Aussagen A und B sind logisch äquivalent, A ≡ B, wenn A ⇔ B eine Tautologie ist — sie haben dieselbe Spalte in der Wahrheitstabelle.

So lassen sich die De Morganschen Gesetze aus dem Teil über Mengen überprüfen: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Die Spalten sind gleich:

Eine Tautologie mit einer Tabelle zu prüfen ist zuverlässig, aber für n Variablen bedeutet das 2ⁿ Zeilen. Bei 300 Variablen sind das mehr Zeilen, als es Atome im Universum gibt. Die Frage, ob sich eine Aussage überhaupt erfüllen lässt (das SAT-Problem), ist eines der berühmtesten schweren Probleme der Informatik.

5. Warum XOR die ersten neuronalen Netze stoppte

Zeichnen wir die vier Kombinationen von P und Q als Punkte in der Ebene und färben sie nach dem Ergebnis. Bei „und“ wie bei „oder“ lassen sich die grünen Punkte mit einer einzigen Geraden von den orangen trennen. Bei XOR geht das nicht — die grünen Punkte liegen auf der einen Diagonale und die orangen auf der anderen:

P ∧ Q

P ∨ Q

P ⊕ Q

Das Perzeptron, das einfachste neuronale Netz, kann Punkte nur durch eine Gerade trennen. Im Jahr 1969 zeigten Minsky und Papert, dass es deshalb nicht einmal eine so einfache Funktion wie XOR bewältigt, und das Interesse an neuronalen Netzen ließ für Jahre nach. Die Lösung ist, eine Schicht hinzuzufügen: XOR lässt sich aus einfacheren Funktionen zusammensetzen, (P ∨ Q) ∧ ¬(P ∧ Q), und ein zweischichtiges Netz schafft das. Hier beginnt die Geschichte des Deep Learning.

6. Prädikate und Quantoren

Definition — Prädikat und Quantoren

Ein Prädikat P(x) ist eine Aussage mit einer Variablen: Für jedes x aus einer gegebenen Menge wird es zu einer Aussage („x ist gerade“).

∀x ∈ M : P(x) ist wahr, wenn P(x) für alle x ∈ M gilt. ∃x ∈ M : P(x) ist wahr, wenn es für mindestens eines gilt.

Auf die Reihenfolge verschiedener Quantoren kommt es an: ∀x ∃y : P(x, y) bedeutet im Allgemeinen nicht dasselbe wie ∃y ∀x : P(x, y).

Definitionen in der KI sind voller Quantoren. Die zulässige Heuristik aus dem Teil über Suche ist „∀n : h(n) ≤ h*(n)“ — und um sie zu widerlegen, genügt ein einziger Zustand, in dem die Schätzung zu hoch liegt.

7. Was ein Beweis ist

Definition — Beweis und Modus ponens

Ein Beweis einer Behauptung T ist eine endliche Folge von Aussagen, die mit T endet und in der jede Aussage entweder eine Voraussetzung ist (ein Axiom, ein früher bewiesener Satz) oder aus den vorherigen nach einer Schlussregel folgt.

Die grundlegende Schlussregel ist der Modus ponens: Aus P und P ⇒ Q folgt Q. Die Regel ist korrekt, weil (P ∧ (P ⇒ Q)) ⇒ Q eine Tautologie ist.

8. Arten von Beweisen

Direkter Beweis

Aus den Voraussetzungen gelangen wir Schritt für Schritt zur Behauptung. Behauptung: Die Summe zweier gerader Zahlen ist gerade. Beweis: Die geraden Zahlen sind 2a und 2b für ganze a, b. Ihre Summe ist 2a + 2b = 2(a + b), also das Doppelte einer ganzen Zahl — eine gerade Zahl. ∎

Beweis durch Kontraposition und durch Widerspruch

Statt P ⇒ Q beweisen wir das äquivalente ¬Q ⇒ ¬P — oder wir nehmen an, dass die Behauptung nicht gilt, und gelangen zu einem Unsinn. Behauptung: Es gibt unendlich viele Primzahlen. Beweis durch Widerspruch (Euklid): Gäbe es nur endlich viele, p₁, …, p_k, so nehmen wir N = p₁ · … · p_k + 1. Kein p_i teilt N — es bleibt immer der Rest 1. N hat also einen Primteiler, der in der Liste fehlt. Widerspruch. ∎

Gegenbeispiel

Eine „für alle“-Behauptung wird durch ein einziges Beispiel widerlegt. „Jede ungerade Zahl größer als 1 ist eine Primzahl“ gilt für 3, 5 und 7 — und scheitert an 9 = 3 · 3. Drei Beispiele beweisen nichts, ein Gegenbeispiel widerlegt.

Vollständige Induktion

Definition — Prinzip der vollständigen Induktion

Gilt P(1) (Induktionsanfang) und gilt für jedes n ≥ 1 P(n) ⇒ P(n + 1) (Induktionsschritt), dann gilt P(n) für alle n ∈ ℕ.

Behauptung: 1 + 2 + … + n = n(n + 1)/2. Anfang: Für n = 1 steht links 1 und rechts 1 · 2/2 = 1. Schritt: Gilt die Formel für n, dann ist 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, und das ist die Formel für n + 1. ∎ Dasselbe Ergebnis zeigt auch das Bild: Zwei Treppen aus Punkten ergeben zusammen ein Rechteck n × (n + 1).

Mit Induktion beweist man in der Informatik die Korrektheit von Algorithmen: „nach k Schleifendurchläufen gilt …“. So beweist man zum Beispiel, dass UCS die Zustände in nicht fallender Reihenfolge der Kosten expandiert — und deshalb den günstigsten Weg findet.

9. Logik in der künstlichen Intelligenz

• Symbolische KI — die ersten Systeme künstlicher Intelligenz waren logisch: Wissen als „Wenn–dann“-Regeln aufgeschrieben und Schließen mit Modus ponens. Darauf beruhten die Expertensysteme der Achtzigerjahre.
• SAT-Solver lösen die Aufgabe „lässt sich diese Aussage erfüllen?“ für Millionen von Variablen — sie planen, verifizieren Hardware und finden Fehler in Programmen.
• Verifikation von KI — mit Logik beweist man Eigenschaften von Systemen: dass ein Autopilot nie zwei widersprüchliche Befehle gibt oder dass ein neuronales Netz seine Entscheidung nicht wegen unsichtbaren Rauschens ändert.
• Sprachmodelle und Beweise — heutige Modelle können Beweise schreiben, und diese werden dann mit formalen Werkzeugen geprüft, die jeden Schritt mechanisch verifizieren.

10. Zusammenfassung

• Eine Aussage ist wahr oder falsch; die Junktoren ¬ ∧ ∨ ⇒ ⇔ ⊕ sind durch eine Wahrheitstabelle genau definiert.
• Eine Implikation ist äquivalent zu ihrer Kontraposition, nicht zu ihrer Umkehrung — und mit falscher Voraussetzung ist sie immer wahr.
• XOR lässt sich nicht durch eine einzige Gerade trennen, und deshalb braucht ein neuronales Netz mehr Schichten.
• Auf die Reihenfolge der Quantoren kommt es an; eine „für alle“-Behauptung widerlegt ein einziges Gegenbeispiel.
• Ein Beweis ist eine Kette überprüfbarer Schritte: direkt, durch Kontraposition, durch Widerspruch oder durch Induktion.

Siehst du das anders? Schreib an support@coden-app.com.