プレスバーガー算術
プレスバーガー算術(英: Presburger arithmetic)とは加法を含む自然数に関する一階述語論理体系である。 モイジェシュ・プレスバーガーにより1929年に導入された。 プレスバーガー算術のシグネチャには加法と等号のみが含まれ乗法は省かれる。 公理には数学的帰納法の公理型を含む。
プレスバーガー算術は加法と乗法両方含むペアノ算術より弱い体系である。ペアノ算術とは異なりプレスバーガー算術は決定可能である。 これはプレスバーガー算術の言語で書かれた任意の閉論理式がプレスバーガー算術の公理で証明可能かどうかを判定するアルゴリズムが存在することを意味する。 この決定問題の計算複雑性は漸近的に二重指数関数であることがFischer & Rabin (1974)で示されている。