Zum Inhalt springen

KALKÜL · Technik im Detail

Ein Nein kommt mit der Belegung, die die Regel bricht.

Wie KALKÜL zu jedem Nein eine Belegung liefert, die die Regel bricht, sie durch Einsetzen ohne Löser nachprüft und daraus den nächsten Vorschlag ableitet.

Ein Nein ohne Begründung kann man nur glauben oder bestreiten. KALKÜL liefert zu jedem Nein die Belegung, die die Regel bricht: Werte für alle Größen des Zustands und der Handlung. Wer zweifelt, setzt sie in die Regel ein und rechnet selbst. Aus ihr entsteht auch der nächste Vorschlag. So ist das Gegenbeispiel ausgelegt; der Demonstrator zeigt es als Kasten, der ganz jenseits einer Grenze liegt.

Diese Seite beschreibt die Bauweise des Systems. Gebaut sind der Prototyp von Freigabe und Protokoll und der Demonstrator von KALKÜL; den ganzen Stand finden Sie unter Was heute steht.

Auf dieser Seite
  1. 01Aus erfüllbar wird eine Belegung
  2. 02Nachprüfen durch Einsetzen
  3. 03Das kleinste verständliche Gegenbeispiel
  4. 04Bei Intervallen ein Kasten, kein Punkt
  5. 05Vom Nein zum nächsten Vorschlag
  6. 06Ein Nein ist belegt, ein Unentschieden nicht
  7. 07Eckdaten
  8. 08Weiter

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ätigt
Prüfung einer Belegung durch Einsetzen, schematisch. Namen und Werte sind Platzhalter; gerechnet wird in Brüchen.

Ohne 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.

Gegenbeispiel in KALKÜL: Belegung, Einsetzen, Auswerten, bestätigt oder verworfenDie 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.Regel brichtRegel giltBELEGUNGGEGENBEISPIELEINSETZENAUSWERTENBESTÄTIGTVERWORFEN
  • Ablauf von Belegung bis Gegenbeispiel: Einsetzen, Auswerten, Bestätigt, Verworfen.
  • Einsetzen zu Auswerten.
  • Auswerten Regel bricht Bestätigt.
  • Auswerten Regel gilt Verworfen.
ABLAUF · WEGE OHNE MENGEN

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.

Gegenbeispiel in KALKÜL: Vorschlag mit Band, Zerlegung, Kasten jenseits der Grenze, zweiter VorschlagDer 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.GRÖSSEZEITOBERGRENZEUNTERGRENZEERSTER ZEITPUNKTGEGENBEISPIEL
  • 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.
RECHENRAUM · SCHRANKEN STATT WERTE

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

Welche Ablehnung muss bei Ihnen jemand begründen können? Diese Regel schreiben wir mit Ihnen so, dass das Nein eine Belegung trägt.