| dbo:abstract
|
- Presburgerova aritmetika je jeden z axiomatických systémů formální teorie aritmetiky. Je podstatně slabší než Peanova aritmetika, zejména proto, že v jazyce neobsahuje symbol pro násobení. Pojmenována je po polském matematikovi , který tuto axiomatiku publikoval v roce 1929. (cs)
- 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. (de)
- Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction. Presburger arithmetic is much weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Presburger arithmetic is a decidable theory. This means it is possible to algorithmically determine, for any sentence in the language of Presburger arithmetic, whether that sentence is provable from the axioms of Presburger arithmetic. The asymptotic running-time computational complexity of this algorithm is at least doubly exponential, however, as shown by . (en)
- En logique mathématique, l'arithmétique de Presburger est la théorie du premier ordre des nombres entiers naturels munis de l'addition. Elle a été introduite en 1929 par Mojżesz Presburger. Il s'agit de l'arithmétique de Peano sans la multiplication, c’est-à-dire avec seulement l'addition, en plus du zéro et de l'opération successeur. Contrairement à l'arithmétique de Peano, l'arithmétique de Presburger est décidable. Cela signifie qu'il existe un algorithme qui détermine si un énoncé du langage de l'arithmétique de Presburger est démontrable à partir des axiomes de l'arithmétique de Presburger. (fr)
- Aritmetica di Presburger è la teoria del primo ordine dei numeri naturali con l'aggiunta introdotta nel 1929 da Mojżesz Presburger, da cui prende il nome. La firma dell'aritmetica Presburger contiene solo l'operazione di addizione e l'uguaglianza, omettendo completamente l'operazione di moltiplicazione. Gli assiomi includono uno schema di induzione. L'aritmetica di Presburger è meno potente dell'aritmetica di Peano, che include sia le operazioni di addizione che di moltiplicazione. Diversamente dall'aritmetica di Peano, l'aritmetica di Presburger è una teoria decidibile. (it)
- プレスバーガー算術(英: Presburger arithmetic)とは加法を含む自然数に関する一階述語論理体系である。により1929年に導入された。プレスバーガー算術のには加法と等号のみが含まれ乗法は省かれる。公理には数学的帰納法の公理型を含む。 プレスバーガー算術は加法と乗法両方含むペアノ算術より弱い体系である。ペアノ算術とは異なりプレスバーガー算術は決定可能である。これはプレスバーガー算術の言語で書かれた任意の閉論理式がプレスバーガー算術の公理で証明可能かどうかを判定するアルゴリズムが存在することを意味する。この決定問題の計算複雑性は漸近的に二重指数関数であることがで示されている。 (ja)
- Arytmetyka Presburgera jest układem aksjomatycznym liczb naturalnych z dodawaniem. Nazywana jest także arytmetyką Peana bez mnożenia. Język arytmetyki Presburgera zawiera 0 i 1, binarną funkcję + określaną jako dodawanie oraz relację równości. Główne aksjomaty arytmetyki: 1.
* ¬(0 = x + 1) 2.
* x + 1 = y + 1 → x = y 3.
* x + 0 = x 4.
* (x + y) + 1 = x + (y + 1) 5.
* Niech P(x) będzie formułą w języku Presburgera i niech dana będzie określona zmienna x. Wtedy następująca formuła jest aksjomatem:(P(0) ∧ ∀x(P(x) → P(x + 1))) → P(y). Ostatni aksjomat określany jest schematem indukcji reprezentującym nieskończoną liczbę aksjomatów.W roku 1929 Mojżesz Presburger udowodnił, że arytmetyka ta jest rozstrzygalna. Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić czy dana odpowiedź na pytanie stawiane przez problem jest poprawna. Presburger udowodnił także, że taka arytmetyka jest niesprzeczna i zupełna (istnieje dowód T lub negacji T).Arytmetyka Presburgera przydaje się do rozstrzygalności problemów, choć czas działania zgrubnego algorytmu jest niejasny. Czas najlepszych algorytmów jest potrójnie wykładniczy. Niech n będzie długością twierdzenia w arytmetyce Presburgera; Fischer i Rabin (1974) udowodnili, że każdy algorytm sprawdzający prawdziwość twierdzenia musi wykonać w pesymistycznym przypadku co najmniej kroków dla pewnej stałej c > 0. (pl)
- A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma. Tem esse nome em honra de Mojżesz Presburger, o qual a apresentou em 1929. A assinatura da aritmética de Presburguer contém apenas a operação de adição e equalização, suprimindo a operação de multiplicação totalmente. Isso inclui o esquema de indução. A Aritmética de Presburger é muito mais fraca do que a aritmética de Peano, que inclui tanto a operação de adição quanto a de multiplicação. Ao contrário da aritmética de Peano, a aritmética de Presburger é uma teoria decidível. Isto significa que é possível efetivamente determinar, por qualquer sentença na linguagem da aritmética Presburger, se essa frase é dedutível dos axiomas da aritmética de Presburger. O tempo de funcionamento assintótico complexidade computacional deste problema de decisão é duplamente exponencial, como mostrado por Fischer e Rabin (1974). (pt)
- Арифметика Пресбургера — это теория первого порядка, описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения. Названа в честь польского математика Мойжеша Пресбургера, который в 1929 году предложил соответствующую систему аксиом в логике первого порядка, а также показал её разрешимость. (ru)
- Арифметика Пресcбургера — це теорія першого порядку яка описує натуральні числа з додаванням, але на відміну від арифметики Пеано, виключає висловлювання щодо множення. Названа в честь польського математика , котрий в 1929 році запропонував відповідну систему аксіом в логіці першого порядку, а також показав її . У цьому розділі ми описуємо вирази безлічі [1] [Архівовано 24 вересня 2015 у Wayback Machine.] в . Відзначимо відразу ж, що з такою сигнатурою елімінація кванторів неможлива. Справді, формула [2] [Архівовано 24 вересня 2015 у Wayback Machine.], справжня для парних Х , не є еквівалентною ніякої бескванторной формули. Тому нам потрібно, перш ніж проводити елімінацію кванторів, розширити сигнатуру. Наведений приклад формули підказує, яке розширення нам необхідно. Розглянемо рахункове сімейство двомісних предикатних символів 2″′, 3″′, 4″′,.... Символ С″′ буде інтерпретуватися як рівність по модулю С. Іншими словами, формула Х буде істинною в нашій інтерпретації, якщо порівняти з по модулю (залишки по модулю рівні; кратно). Важливо мати на увазі, що індекс в не є змінною: у нас не триміснийпредикат, а рахункове сімейство двомісних предикатів. Таке розширення не міняє класу виразність предикатів, оскільки, наприклад, можна виразити як [3] [Архівовано 24 вересня 2015 у Wayback Machine.]. Зате після цього всяка формула еквівалентна бескванторной, як показує наступна теорема (звана теоремою про елімінації кванторів в Арифметика Прессбургера). (uk)
|
| rdfs:comment
|
- Presburgerova aritmetika je jeden z axiomatických systémů formální teorie aritmetiky. Je podstatně slabší než Peanova aritmetika, zejména proto, že v jazyce neobsahuje symbol pro násobení. Pojmenována je po polském matematikovi , který tuto axiomatiku publikoval v roce 1929. (cs)
- En logique mathématique, l'arithmétique de Presburger est la théorie du premier ordre des nombres entiers naturels munis de l'addition. Elle a été introduite en 1929 par Mojżesz Presburger. Il s'agit de l'arithmétique de Peano sans la multiplication, c’est-à-dire avec seulement l'addition, en plus du zéro et de l'opération successeur. Contrairement à l'arithmétique de Peano, l'arithmétique de Presburger est décidable. Cela signifie qu'il existe un algorithme qui détermine si un énoncé du langage de l'arithmétique de Presburger est démontrable à partir des axiomes de l'arithmétique de Presburger. (fr)
- Aritmetica di Presburger è la teoria del primo ordine dei numeri naturali con l'aggiunta introdotta nel 1929 da Mojżesz Presburger, da cui prende il nome. La firma dell'aritmetica Presburger contiene solo l'operazione di addizione e l'uguaglianza, omettendo completamente l'operazione di moltiplicazione. Gli assiomi includono uno schema di induzione. L'aritmetica di Presburger è meno potente dell'aritmetica di Peano, che include sia le operazioni di addizione che di moltiplicazione. Diversamente dall'aritmetica di Peano, l'aritmetica di Presburger è una teoria decidibile. (it)
- プレスバーガー算術(英: Presburger arithmetic)とは加法を含む自然数に関する一階述語論理体系である。により1929年に導入された。プレスバーガー算術のには加法と等号のみが含まれ乗法は省かれる。公理には数学的帰納法の公理型を含む。 プレスバーガー算術は加法と乗法両方含むペアノ算術より弱い体系である。ペアノ算術とは異なりプレスバーガー算術は決定可能である。これはプレスバーガー算術の言語で書かれた任意の閉論理式がプレスバーガー算術の公理で証明可能かどうかを判定するアルゴリズムが存在することを意味する。この決定問題の計算複雑性は漸近的に二重指数関数であることがで示されている。 (ja)
- Арифметика Пресбургера — это теория первого порядка, описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения. Названа в честь польского математика Мойжеша Пресбургера, который в 1929 году предложил соответствующую систему аксиом в логике первого порядка, а также показал её разрешимость. (ru)
- 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. (de)
- Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction. (en)
- A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma. Tem esse nome em honra de Mojżesz Presburger, o qual a apresentou em 1929. A assinatura da aritmética de Presburguer contém apenas a operação de adição e equalização, suprimindo a operação de multiplicação totalmente. Isso inclui o esquema de indução. (pt)
- Arytmetyka Presburgera jest układem aksjomatycznym liczb naturalnych z dodawaniem. Nazywana jest także arytmetyką Peana bez mnożenia. Język arytmetyki Presburgera zawiera 0 i 1, binarną funkcję + określaną jako dodawanie oraz relację równości. Główne aksjomaty arytmetyki: 1.
* ¬(0 = x + 1) 2.
* x + 1 = y + 1 → x = y 3.
* x + 0 = x 4.
* (x + y) + 1 = x + (y + 1) 5.
* Niech P(x) będzie formułą w języku Presburgera i niech dana będzie określona zmienna x. Wtedy następująca formuła jest aksjomatem:(P(0) ∧ ∀x(P(x) → P(x + 1))) → P(y). (pl)
- Арифметика Пресcбургера — це теорія першого порядку яка описує натуральні числа з додаванням, але на відміну від арифметики Пеано, виключає висловлювання щодо множення. Названа в честь польського математика , котрий в 1929 році запропонував відповідну систему аксіом в логіці першого порядку, а також показав її . Важливо мати на увазі, що індекс в не є змінною: у нас не триміснийпредикат, а рахункове сімейство двомісних предикатів. (uk)
|
