Aus erfüllbar wird eine Belegung
Prüft KALKÜL, ob eine Handlung die Regel R in einem Zustand S einhält, fragt es den Löser nach einer Belegung für S ∧ ¬R. Antwortet er unerfüllbar, ist die Regel bewiesen. Antwortet er erfüllbar, liefert er zugleich, was die Frage bejaht: eine Belegung, also für jede Variable einen Wert, bei dem alle Voraussetzungen gelten und die Regel nicht. Das ist das Gegenbeispiel. Es ist kein Hinweis, dass etwas schiefgehen könnte, sondern ein Zustand, in dem es schiefgeht.
Die Werte sind exakt. Über linearer Arithmetik rechnet der Löser mit rationalen Zahlen ohne Rundung, ein Wert steht als Bruch und nicht als Näherung. KALKÜL übernimmt die Belegung in dieser Form und rechnet erst für die Anzeige in Dezimalzahlen um, mit dem Hinweis, dass die Anzeige gerundet ist.
Die Belegung enthält alle Größen, die in den Voraussetzungen vorkommen, auch jene, die den Bruch nicht verursachen. Welche das sind, zeigt der Abschnitt über das kleinste Gegenbeispiel.
Nachprüfen durch Einsetzen
Ein erfüllbar vom Löser muss man nicht glauben. KALKÜL setzt die Belegung selbst in die Voraussetzungen und in die Regel ein und wertet beide in exakter Bruchrechnung aus, mit einem kleinen Programm, das mit dem Löser nichts teilt. Gelten die Voraussetzungen und bricht die Regel, ist das Gegenbeispiel bestätigt. Gilt die Regel dagegen, wird das Ergebnis des Lösers verworfen und als Fehler gemeldet. Ein Nein folgt daraus nicht.
Dieselbe Prüfung kann jede Dritte nachvollziehen. Sie braucht die Regel in der Fassung des Nachweises, den Zustand und die Belegung, keinen Löser und keinen Zugang zu KALKÜL. Das unterscheidet das Gegenbeispiel vom Beweis: Eine Belegung prüft man durch Einsetzen, für einen Beweis braucht man ein Prüfprogramm für Beweise.
sat
x = 1/4 Größe des Zustands
u = 3/4 Stellgröße der Handlung
f = falsch keine Freigabe
Voraussetzungen x ≥ 0 und u ≤ 1 gelten
Regel nicht f → x − u ≥ 0
wahr → 1/4 − 3/4 ≥ 0
−1/2 ≥ 0 falsch
Gegenbeispiel bestätigtOhne Löser nachgerechnet
Die Belegung des Lösers wird in Voraussetzungen und Regel eingesetzt. Bricht die Regel, ist das Gegenbeispiel bestätigt. Gilt sie, wird das Ergebnis des Lösers verworfen.
- Ablauf von Belegung bis Gegenbeispiel: Einsetzen, Auswerten, Bestätigt, Verworfen.
- Einsetzen zu Auswerten.
- Auswerten Regel bricht Bestätigt.
- Auswerten Regel gilt Verworfen.
Das kleinste verständliche Gegenbeispiel
Ein Löser liefert irgendeine Belegung, die genügt. Für die, die sie lesen müssen, ist das oft unbrauchbar: Es stehen viele Größen darin, von denen nur zwei den Bruch erklären. KALKÜL sucht darum die Belegung, die dem Vorschlag am nächsten liegt. Dafür dient die Optimierung, die der Löser mitbringt: Er minimiert den Abstand der Werte zum vorgeschlagenen Zustand unter der Bedingung, dass die Regel bricht.
Größen, die für den Bruch gleichgültig sind, behalten dabei ihren Wert aus dem Vorschlag. Als Unterschied bleibt, was den Bruch verursacht, und das Gegenbeispiel sagt in einer Zeile, welche Größe um wie viel zu weit geht.
Gelten mehrere Regeln, prüft KALKÜL jede einzeln und nicht nur ihre Verknüpfung. Das Ergebnis nennt alle gebrochenen Regeln mit Wortlaut, Fundstelle und Version, je mit einem eigenen Gegenbeispiel. Wer abgewiesen wird, sieht nicht nur, dass es nicht geht, sondern an welcher Vorschrift.
Bei Intervallen ein Kasten, kein Punkt
Rechnet KALKÜL mit Unsicherheit, ist das Gegenbeispiel kein einzelner Zustand, sondern ein Kasten aus Intervallen, in dem jeder Zustand die Regel bricht. Das ist stärker als ein Punkt, denn es zeigt, dass der Bruch nicht an einer unglücklichen Messung hängt. Die Zerlegung hält nach der Ebene an, in der sie einen solchen Kasten findet, und bestimmt näherungsweise den ersten Zeitpunkt, an dem ein möglicher Zustand die Regel bricht. So arbeitet der Demonstrator.
Bleibt ein Kasten übrig, der weder ganz erlaubt noch ganz verboten ist, ist das kein Gegenbeispiel. Das Ergebnis lautet dann unentschieden, und unentschieden heißt: keine Freigabe.
Das Gegenbeispiel als Kasten
Der Vorschlag mit seiner Unsicherheit als Band, nach rechts die Zeit. Die Zerlegung findet einen Kasten ganz unter der Untergrenze; dort hält sie an und nennt den ersten Zeitpunkt. Der zweite Vorschlag bleibt innerhalb der Grenzen.
- Regel Obergrenze (obergrenze).
- Regel Untergrenze (untergrenze).
- Vorschlag als Band um eine Mittellinie.
- Zerlegung bis Tiefe 3: geprüfte Kästen als Linie, offene schraffiert.
- Gegenbeispiel an Regel Gegenbeispiel, erster Zeitpunkt markiert.
- Zweiter Vorschlag, innerhalb aller Schranken.
Vom Nein zum nächsten Vorschlag
Das Gegenbeispiel ist die Eingabe der nächsten Runde. Ein Agent, der eine Handlung vorgeschlagen hat, erhält die gebrochene Regel und die Richtung des Bruchs zurück und schlägt etwas anderes vor. KALKÜL prüft den neuen Vorschlag mit denselben Regeln. Die Zahl der Runden ist begrenzt; danach geht der Fall mit allen Gegenbeispielen an eine Person.
Der Rückweg unterliegt den Rechten wie jeder andere. Enthält die Belegung Werte, die der Agent nicht lesen darf, kommen sie nicht in seinen Kontext: Er erhält die Regel und die Richtung des Bruchs, die Belegung bleibt beim Nachweis. Wo die Frage nicht Ja oder Nein lautet, sondern nach dem besten erlaubten Plan fragt, rechnet KALKÜL mit Optimierung statt mit Wiederholung.
Ein Nein ist belegt, ein Unentschieden nicht
Das Gegenbeispiel gehört zum Nachweis: Datensatz, kanonische Form, Prüfwert, Signatur, Zeitstempel. Damit ist auch das Nein prüfbar, so wie das Ja. Wer eine Handlung abgelehnt bekommt, kann die Ablehnung vor einer Stelle belegen, die KALKÜL nicht vertraut.
Eine Antwort ohne Belegung wird nie als Nein ausgegeben. Läuft der Löser in die Zeitgrenze oder bleibt eine Zerlegung offen, lautet das Ergebnis unentschieden. Das ist ein eigener Zustand mit eigener Folge: keine Freigabe, aber auch kein Vorwurf an die Handlung. Wer Nein sagt, muss es zeigen können.
Eckdaten
- Ergebnis erfüllbar
- Belegung als Gegenbeispiel; exakte rationale Werte, kein Gleitkomma
- Prüfung
- Einsetzen in exakter Bruchrechnung ohne Löser; Abweichung ist ein Fehler und kein Nein
- Nähe
- Optimierung im Löser: kleinster Abstand zum Vorschlag, gleichgültige Größen bleiben
- Mehrere Regeln
- jede einzeln; Wortlaut, Fundstelle und Version je gebrochener Regel
- Intervalle
- Kasten, in dem jeder Zustand die Regel bricht; erster Zeitpunkt des Bruchs
- Unentschieden
- eigenes Ergebnis ohne Gegenbeispiel; keine Freigabe
- Rückweg
- Regel und Richtung des Bruchs an den Agenten; die Belegung nur im Rahmen seiner Rechte
- Nachweis
- das Gegenbeispiel ist Teil des signierten Datensatzes
Weiter
- KALKÜL · TechnikRegelnWie KALKÜL Regeln als Formeln mit einem SMT-Löser prüft: unerfüllbare Negation ist ein Nachweis, erfüllbare ein Gegenbeispiel, alles andere kein Ja.
- KALKÜL · TechnikIntervalleWie KALKÜL nichtlineare Bedingungen und Messunsicherheit mit Intervallen und einer Zerlegung in Boxen entscheidet, und warum unentschieden kein Ja ist.
- KALKÜL · TechnikNachweisWie KALKÜL Eingaben, Regelversion und Ergebnis mit SHA-256 festschreibt, mit Ed25519 signiert und mit einem Zeitstempel nach RFC 3161 belegt.
- KALKÜL · TechnikOptimierungWie KALKÜL aus Regeln und Ziel ein Optimierungsproblem baut, mit Schranke löst und den Plan vor der Freigabe exakt gegen dieselben Regeln prüft.
- KALKÜL · TechnikSzenarienWie KALKÜL Varianten als Szenarien auf einem Zweig rechnet, ihre Annahmen als Intervalle führt und erst die gewählte nach Freigabe wirken lässt.
- ProduktKALKÜLHandlungen vorab rechnen, gegen Regeln prüfen und belegen
Welche Ablehnung muss bei Ihnen jemand begründen können? Diese Regel schreiben wir mit Ihnen so, dass das Nein eine Belegung trägt.