Presburger-Arithmetik

Die Presburger-Arithmetik ist eine in der Prädikatenlogik erster Stufe formulierte mathematische Theorie der natürlichen Zahlen mit Addition. Sie ist benannt nach Mojżesz Presburger, der sie im Jahre 1929 einführte.[1] Die Signatur der Presburger-Arithmetik enthält nur Addition, nicht jedoch die Multiplikation. Zum Axiomensystem gehört auch ein Axiomenschema der vollständigen Induktion.

Die Presburger-Arithmetik ist erheblich schwächer als die Peano-Arithmetik, in der sowohl Addition als auch Multiplikation formalisiert werden. Im Gegensatz zur Peano-Arithmetik ist die Presburger-Arithmetik eine entscheidbare Theorie, d. h., es lässt sich für jede in der Sprache der Presburger-Arithmetik formulierte Aussage effektiv entscheiden, ob sie aus den Axiomen der Theorie beweisbar ist oder nicht. Allerdings ist die asymptotische Laufzeit eines entsprechenden Algorithmus laut einer Arbeit von Fischer und Rabin doppelt exponentiell.[2]

Definition

Die Sprache der Presburger-Arithmetik enthält Konstanten 0 und 1 sowie eine binäre Operation +, die als Addition zu interpretieren ist. In dieser Sprache lauten die Axiome der Presburger-Arithmetik wie folgt:

1. ${\displaystyle 0+1=1}$
2. ${\displaystyle \forall x\colon \neg (x+1=0)}$
3. ${\displaystyle \forall x,y\colon (x+1=y+1\rightarrow x=y)}$
4. ${\displaystyle \forall x\colon x+0=x}$
5. ${\displaystyle \forall x,y\colon (x+y)+1=x+(y+1)}$
6. Sei ${\displaystyle P(x,y_{1},\ldots ,y_{k})}$ eine Formel in der Sprache der Presburger-Arithmetik mit freien Variablen ${\displaystyle x,y_{1},\ldots ,y_{k}}$. Dann ist folgende Aussage ein Axiom:

${\displaystyle \forall y_{1},\ldots ,y_{k}\colon ((P(0,y_{1},\ldots ,y_{k})\land \forall x\colon (P(x,y_{1},\ldots ,y_{k})\rightarrow P(x+1,y_{1},\ldots ,y_{k})))\rightarrow \forall x\colon P(x,y_{1},\ldots ,y_{k}))}$

Letzteres i​st ein Axiomenschema d​er vollständigen Induktion u​nd steht für unendlich v​iele Einzelaxiome. Diese d​em Schema (6) entsprechenden Axiome lassen s​ich nicht d​urch endlich v​iele Axiome ersetzen, s​o dass d​ie Presburger-Arithmetik insgesamt n​icht endlich axiomatisierbar ist.

Beschreibung

Die Presburger-Arithmetik kann Konzepte wie Teilbarkeit oder Primzahlen nicht formalisieren, geschweige denn die Multiplikation, denn dann müsste die Presburger-Arithmetik wie die Peano-Arithmetik unvollständig und unentscheidbar sein. Individuelle Instanzen der Teilbarkeit können aber durchaus formalisiert werden, etwa „${\displaystyle x}$ ist gerade“ durch ${\displaystyle G(x):\Leftrightarrow \exists z\colon z+z=x}$; hiermit ausdrückbare wahre Aussagen wie

${\displaystyle \forall x,y\colon (G(x)\land G(y)\rightarrow G(x+y))}$

(„Die Summe zweier gerader Zahlen ist gerade“)

sind d​ann beweisbare Sätze.

Eigenschaften

Mojżesz Presburger w​ies folgende Eigenschaften seiner Arithmetik nach:[1]

• Konsistenz: Es gibt keine in ihrer Sprache formulierte Aussage ${\displaystyle P}$, für die sowohl ${\displaystyle P}$ als auch ${\displaystyle \neg P}$ aus den Axiomen hergeleitet werden kann.
• Vollständigkeit: Für jede in der Sprache der Presburger-Arithmetik formulierte Aussage ${\displaystyle P}$ ist entweder ${\displaystyle P}$ oder die Verneinung ${\displaystyle \neg P}$ aus den Axiomen herleitbar.
• Entscheidbarkeit: Es gibt einen Algorithmus, der zu jeder gegebenen Aussage der Presburger-Arithmetik entscheiden kann, ob sie wahr oder falsch ist.

Die Entscheidbarkeit d​er Presburger-Arithmetik lässt s​ich durch Quantorenelimination u​nd die Betrachtung arithmetischer Kongruenzen nachweisen.[3]

Die Peano-Arithmetik, also Presburger-Arithmetik zuzüglich Multiplikation, ist dagegen nicht entscheidbar. Gemäß Gödels Unvollständigkeitssatz ist sie auch unvollständig und ihre Konsistenz nicht (intern) beweisbar.

Das Entscheidungsproblem für die Presburger-Arithmetik ist ein interessantes Beispiel der Komplexitätstheorie. Sei ${\displaystyle n}$ die Länge einer Aussage der Presburger-Arithmetik. Dann hat der Entscheidungsalgorithmus für die Presburger-Arithmetik laut einer Arbeit von Fischer und Rabin[2] mindestens doppelt-exponentielle Laufzeit, d. h., im worst case beträgt die Laufzeit mindestens ${\displaystyle 2^{2^{cn}}}$ für eine gewisse positive Konstante ${\displaystyle c}$. Andererseits gibt es eine dreifach-exponentielle obere Abschätzung für die Laufzeit.[4] Es handelt sich also um ein Entscheidungsproblem, das nachweislich nicht in exponentieller (geschweige denn polynomieller) Zeit gelöst werden kann. Fischer und Rabin zeigten auch, dass für jede (in einem von ihnen präzisierten Sinne) vernünftige Axiomatisierung Sätze beliebiger Länge existieren, deren kürzester Beweis von doppelt-exponentieller Länge ist. Intuitiv bedeutet dies, dass es praktische Grenzen für Computerbeweise gibt. Aus der Arbeit von Fischer und Rabin ergibt sich ferner, dass mit der Presburger-Arithmetik Formeln definiert werden können, die einen beliebigen Algorithmus korrekt nachbilden, solange die Eingaben gewisse – verhältnismäßig hohe – Grenzen nicht überschreiten. Diese Grenzen können durch den Übergang zu anderen Formeln jeweils noch erhöht werden.

Anwendungen

Es existieren auch tatsächlich Computerbeweissysteme, die Algorithmen zur Entscheidung von Formeln in Presburger-Arithmetik gebrauchen. Beispielsweise enthält Coq Beweistaktiken in dieser Richtung. Die doppelt-exponentielle Komplexität begrenzt zwar die praktische Einsetzbarkeit für komplizierte Formeln, jedoch tritt dieses Verhalten nur bei verschachtelten Quantoren auf: Oppen und Nelson[5] beschreiben ein auf dem Simplex-Verfahren beruhendes automatisches Beweissystem für eine erweiterte Presburger-Arithmetik ohne verschachtelte Quantoren. Die Worst-case-Laufzeit des Simplexverfahrens ist (einfach) exponentiell. Tatsächlich wird exponentielle Laufzeit sogar nur für speziell konstruierte Fälle beobachtet, während es in Alltagsfällen erheblich effizienter arbeitet. Hierdurch ist dieser Ansatz durchaus für den praktischen Einsatz geeignet.

Die Presburger-Arithmetik lässt sich um die Multiplikation mit Konstanten erweitern, da es sich hierbei um wiederholte Addition handelt. In der Programmiertechnik betrifft dies beispielsweise die Berechnung von Feldindizes. Dieser Ansatz ist Grundlage von mindestens fünf Systemen für den Korrektheitsbeweis von Computerprogrammen, angefangen beim Stanford Pascal Verifier aus den späten 1970er Jahren bis hin zu Microsofts Spec# von 2005.

Literatur

• David C. Cooper: Theorem Proving in Arithmetic without Multiplication. In: Bernhard Meltzer, Donald Michie (Hrsg.): Machine Intelligence. Band 7. Edinburgh University Press, Edinburgh 1972, ISBN 978-0-470-60110-5, S. 91–99.
• Jeanne Ferrante, Charles W. Rackoff: The Computational Complexity of Logical Theories (= Lecture Notes in Mathematics. Nr. 718). Springer-Verlag, 1979, ISBN 3-540-09501-2, doi:10.1007/BFb0062837.
• William Pugh: The Omega test. a fast and practical integer programming algorithm for dependence analysis. In: Proceedings of the 1991 ACM/IEEE conference on Supercomputing. 1991, ISBN 0-89791-459-7, doi:10.1145/125826.125848.
• Cattamanchi Ramalinga Reddy, Donald W. Loveland: Presburger Arithmetic with Bounded Quantifier Alternation. In: ACM Symposium on Theory of Computing. 1978, S. 320–325, doi:10.1145/800133.804361.
• Paul Young: Gödel theorems, exponential difficulty and undecidability of arithmetic theories. An exposition. In: Anil Nerode, Richard A. Shore (Hrsg.): Recursion Theory (= Proceedings of symposia in pure mathematics). Band 42. American Mathematical Society, 1985, ISBN 0-8218-1447-8, S. 503–522.

Weblinks

• Philipp Rümmer: Princess, ein Computerbeweissystem für Presburger-Arithmetik (englisch).

Einzelnachweise

1. Mojżesz Presburger: Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes Rendus du I congrès de Mathématiciens des Pays Slaves. Warschau 1929, S. 92–101.
2. Michael J. Fischer, Michael O. Rabin: Super-Exponential Complexity of Presburger Arithmetic. In: Proceedings of the SIAM-AMS Symposium in Applied Mathematics. Band 7, 1974, S. 27–41 (mit.edu [PostScript; abgerufen am 26. Februar 2012]). Super-Exponential Complexity of Presburger Arithmetic (Memento des Originals vom 15. September 2006 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
3. Herbert B. Enderton: A mathematical introduction to logic. 2. Auflage. Academic Press, Boston 2001, ISBN 0-12-238452-0, S. 188.
4. Derek C. Oppen: A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic. In: J. Comput. Syst. Sci. Band 16, Nr. 3, 1978, S. 323–332, doi:10.1016/0022-0000(78)90021-1.
5. Greg Nelson, Derek C. Oppen: A simplifier based on efficient decision algorithms. In: Proc. 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. April 1978, S. 141–150, doi:10.1145/512760.512775.