普雷斯堡爾算術是自然數加法的一階理論，為紀念1929年提出的莫伊澤斯-普雷斯堡爾而命名。普雷斯堡爾算術的簽名只包含加法運算和平等，完全省略了乘法運算。該公理包括一個歸納的模式。普雷斯堡爾算術比佩阿諾算術弱得多，佩阿諾算術包括加法和乘法運算。與皮亞諾算術不同，普雷斯堡爾算術是一種可解理論。這意味著，對于普氏算術語言中的任何句子，可以通過算法確定該句子是否可以從普氏算術的公理中得到證明。然而，正如Fischer&Rabin(1974)所顯示的，這種算法的漸進運行時間的計算復雜性至少是雙指數的。

Presburger算術的語言包含常數0和1以及二進制函數+，被解釋為加法。在這種語言中，Presburger算術的公理是以下的普遍封閉。?(0=x+1)x+1=y+1→x=yx+0=xx+(y+1)=(x+y)+1讓P(x)是Presburger算術語言中的一個一階公式，有一個自由變量x（可能還有其他自由變量）。那么下面的公式是一個公理：(P(0)∧?x(P(x)→P(x+1))→?yP(y)。(5)是一個歸納法的公理模式，代表無限多的公理。這些不能被任何有限數量的公理所取代，也就是說，在一階邏輯中，Presburger算術是不能被有限公理化的。普雷斯堡爾算術可以被看作是一個具有平等性的一階理論，它恰恰包含了上述公理的所有后果。或者，它可以被定義為那些在預定解釋中為真的句子的集合：非負整數與常數0、1的結構，以及非負整數的加法。Presburger算術被設計為完整和可解的。因此，它不能將諸如可分性或首要性等概念形式化，或者更廣泛地說，任何導致變量乘法的數字概念。然而，它可以制定可分性的個別實例；例如，它證明對于所有的x，存在y:(y+y=x)∨(y+y+1=x)。這說明每個數字都是偶數或奇數。

莫伊茲-普雷斯堡爾證明普雷斯堡爾算術是。一致。在普雷斯堡爾算術中，沒有任何語句可以從公理中推導出來，而其否定也可以推導出來。完整。對于普雷斯堡爾算術語言中的每一條語句，要么可以從公理中推導出它，要么可以推導出它的否定。可解碼。存在一種算法來決定普雷斯堡爾算術中的任何給定語句是定理還是非定理。普雷斯堡爾算術的可解性可以用量子消除法來證明，并輔以算術同構的推理。用來證明量詞消除算法的步驟可以用來定義遞歸公理化，它不一定包含歸納的公理模式。相比之下，作為對Entscheidungsproblem的否定答案的結果，Peano算術，也就是用乘法增強的Presburger算術，是不可解的。根據哥德爾不完全性定理，Peano算術是不完全的，它的一致性在內部是無法證明的（但見Gentzen的一致性證明）。

普雷斯堡爾算術的決策問題是計算復雜性理論和計算中一個有趣的例子。假設n是Presburger算術中一個語句的長度。然后Fischer&Rabin(1974)證明，在最壞的情況下，該語句在一階邏輯中的證明的長度至少有{displaystyle2{2{cn}}}，對于某個常數c>0來說。因此，他們對Presburger算術的決策算法的運行時間至少是指數級的。Fischer和Rabin還證明，對于任何合理的公理化（在他們的論文中精確定義），都存在長度為n的定理，其證明的長度是雙指數的。直觀地說，這表明計算機程序所能證明的東西是有計算限制的。費舍爾和拉賓的工作還意味著，只要輸入量小于相對較大的界限，就可以用Presburger算術來定義正確計算任何算法的公式。界限可以增加，但只能通過使用新的公式。另一方面，Oppen(1978)證明了PresburgerArithmetic的決策程序的三重指數上界。Berman(1980)使用交替的復雜度等級證明了一個更嚴格的復雜度界限。Presburger算術（PA）中的真語句集對于TimeAlternations(22nO(1),n)來說是完整的。因此，其復雜度介于雙指數非決定性時間（2-NEXP）和雙指數