プレスバーガー算術プレスバーガー算術(英: Presburger arithmetic)とは加法を含む自然数に関する一階述語論理体系である。 モイジェシュ・プレスバーガーにより1929年に導入された。 プレスバーガー算術のシグネチャには加法と等号のみが含まれ乗法は省かれる。 公理には数学的帰納法の公理図式を含む。 プレスバーガー算術は加法と乗法両方含むペアノ算術より弱い体系である。ペアノ算術とは異なりプレスバーガー算術は決定可能である。 これはプレスバーガー算術の言語で書かれた任意の閉論理式がプレスバーガー算術の公理で証明可能かどうかを判定するアルゴリズムが存在することを意味する。 この決定問題の計算複雑性は漸近的に二重指数関数であることがFischer & Rabin (1974)で示されている。 概説プレスバーガー算術の言語は0と1、加法と解釈される二項関数+からなる。公理は以下の論理式を全称閉包したものである。
(5) は数学的帰納法の公理図式であり、無限個の公理を表している。 (5) は有限の公理で置き換えることができないためプレスバーガー算術は有限公理化不可能である。 プレスバーガー算術は因数分解に関する規則や素数のような概念を形式化できない。 一般的に乗法に関する自然数の概念は不完全性と決定不可能性につながることからプレスバーガー算術では定義することはできない。 しかし、個々の論理式としては形式化可能である。例えば次は証明可能である。"任意のxに対して、あるyが存在し : (y + y = x) ∨ (y + y + 1 = x)" これは、すべての自然数は偶数もしくは奇数のどちらかであることを意味する。 性質モイジェシュ・プレスバーガーはプレスバーガー算術に関して以下を証明した。
応用関連項目参考文献
外部リンク
|
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia