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

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

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

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

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

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

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

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

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.