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