## [Herbrand-Methode](/de/node/60032) Definition Eine beweistheoretische Technik, die die Erfüllbarkeit erster Ordnung auf propositionale Erfüllbarkeit reduziert, indem sie endliche (oder effektiv aufzählbare) Mengen von ground-Instanzen — Herbrand‑Expansionen — aus dem Herbrand‑Universum konstruiert. ## Prinzip Prinzip Ersetze quantifizierte Formeln durch geeignet instanziierte ground‑Instanzen aus dem Herbrand‑Universum und prüfe die propositionale Erfüllbarkeit der erhaltenen endlichen Approximationen; eine propositionale Unverträglichkeit spiegelt unter Standardreduktionen die erste‑Ordnung‑Unverträglichkeit wider. ## Demonstration Demonstration Um die Unverträglichkeit von ∀x ∃y R(x,y) ∧ ∀x ¬R(x,c) zu zeigen, generiere Herbrand‑Instanzen mit ground‑Termen {c, f(c), …} und suche eine endliche widersprüchliche Menge; erscheint ein propositionaler Widerspruch unter den Instanzen, ist die ursprüngliche erste‑Ordnung‑Menge unvereinbar. ## Fehlanwendung Fehlanwendung Irrtümlich anzunehmen, dass stets eine einzelne endliche Herbrand‑Expansion ausreicht, ohne systematische Suche oder Achtung der zunehmenden Termkomplexität; vorzeitiges Abbrechen der Suche kann zu falschen Schlüssen über Erfüllbarkeit führen. ## Konsequenz Konsequenz Wandelt ein erste‑Ordnung‑Erfüllbarkeitsproblem in eine (potenziell unendliche) Familie von propositionalen Problemen, die von automatischen Theorembeweisern bearbeitet werden können; eine gefundene endliche unvereinbare Expansion liefert eine konkrete Widerlegung in der ersten Ordnung. ## Umkehrung Umkehrung Die Umkehrung ist, quantifizierte Aussagen aus propositionalen Instanziierungen wieder aufzubauen und damit die Muster quantorischer Abhängigkeiten offenzulegen; die Methode plättet Quantoren zu konkreten Termen, die Umkehr stellt die abstrakten Bindungen wieder her. ## Abgrenzung Abgrenzung Wirksam in der klassischen Prädikatenlogik erster Ordnung und zentral für automatisches Beweisen; sie entscheidet die Erfüllbarkeit nicht allgemein, da die benötigte Expansion unbeschränkt sein kann und sie mit Suchstrategien, Unifikation und Fairness kombiniert werden muss. ## Semantische Spannung Semantische Spannung Spannung zwischen propositionaler Entscheidbarkeit (endliche Suche pro Expansion) und erster‑Ordnung‑Unentscheidbarkeit (potenziell unendliche Expansionen) sowie zwischen konkreten ground‑Zeugen und abstrakten quantifizierten Aussagen. ## Synthese Synthese Die Herbrand‑Methode führt systematisch ground‑Instanzen aus dem Herbrand‑Universum auf, um erste‑Ordnung‑Probleme in propositionale Prüfungen zu überführen: Sie bildet eine konstruktive Brücke für Widerlegungen und automatische Beweissuche, benötigt aber disziplinierte Suchkontrolle zur Beherrschung potenziell unendlicher Expansionen.