## [Zeugenextraktion](/de/node/60864) Definition Der Prozess, aus einem Beweis, einer Widerlegung, einem Modell oder einer Solver-Trace einen konkreten Zeugen, Gegenbeispiel oder eine erfüllende Belegung zu erzeugen, sodass existenzielle Aussagen oder Erfüllbarkeitsresultate durch explizite Artefakte belegt werden. ## Prinzip Prinzip Durchlaufe das Beweisobjekt oder die Solver-Trace und übersetze abstrakte Herleitungen in konstruktive Daten, indem man existentielle Einführungsschritte, Modellkonstruktionen oder Komponenten eines Gegenmodells interpretiert; wahre Korrektheit, sodass der extrahierte Zeuge die ursprüngliche Formel tatsächlich erfüllt oder ihre Falschheit demonstriert. ## Demonstration Demonstration Aus einem SAT-Solver-Lauf, der eine erfüllende Belegung findet, gibt die Zeugenextraktion die boolesche Belegung (z. B. x1=true, x2=false) als konkreten Zeugen aus. Aus einem Beweis von ∃x P(x) in einem konstruktiven System berechnet die Extraktion einen spezifischen Term t und eine Herleitung von P(t). Aus einem SMT-Solver, der unsat mit einem Resolutionsbeweis zurückgibt, kann eine Counterexample-Guided-Refinement-Schleife ein Interpolant oder konkrete Belegung extrahieren, die zur Verfeinerung einer Abstraktion genutzt wird. ## Fehlanwendung Fehlanwendung Der Versuch, einen konstruktiven Zeugen aus einem klassischen Existenzbeweis zu extrahieren, der nicht-konstruktive Prinzipien verwendet, ohne konstruktive Rekonstruktion führt zu Fehlschlägen oder fragwürdigen Artefakten; das Extrahieren einer unvollständigen oder nicht verifizierten Belegung und deren Behandlung als Erfüllbarkeitsbeweis ist unsound. ## Konsequenz Konsequenz Zuverlässige Zeugenextraktion verwandelt abstrakte Solver-Ergebnisse in greifbare Artefakte zur unabhängigen Prüfung, für Zertifikate oder Programmsynthese; sie unterstützt Counterexample-Guided-Abstraction-Refinement und erhöht das Vertrauen durch unabhängige Validierung existenzieller Aussagen. ## Umkehrung Umkehrung Das Umgekehrte ist ein undurchsichtiger Beweis oder Solverausgang, der Existenz oder Erfüllbarkeit meldet, aber keinen konkreten Zeugen liefert (z. B. ein Black-Box-UNSAT-Oracle oder ein nicht-konstruktiver, menschlicher Beweis), was Reproduzierbarkeit und automatische Prüfung erschwert. ## Abgrenzung Abgrenzung Benötigt ein Beweisobjekt, ein Modell oder eine hinreichend detaillierte Solver-Trace, die konstruktive Informationen kodiert; schließt Aussagen von Solvërern aus, die nur Ja/Nein-Antworten ohne Trace liefern, statistische Ausgaben oder informelle Beweise ohne formale Struktur zur Extraktion. ## Semantische Spannung Semantische Spannung Es besteht Spannung zwischen der Extraktion minimaler Zeugen (kleinste oder einfachste) und kanonischer oder reproduzierbarer Zeugen; außerdem muss der Rechenaufwand der Extraktion gegen die Vollständigkeit des zurückgegebenen Zeugen abgewogen werden. ## Synthese Synthese Zeugenextraktion ist die disziplinierte Übersetzung von Beweis- oder Solverartefakten in explizite Beispiele (Belegungen, Terme, Gegenmodelle) durch Nutzung des konstruktiven Inhalts in Herleitungen oder Traces, wodurch verifizierbare Belege entstehen, dass existenzielle oder erfüllbarkeitsbezogene Aussagen realisiert sind.