Центральный Дом Знаний - Арифметика Пресбургера

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Арифметика Пресбургера

Арифметика Пресбургера, теория первого порядка описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения. Названа в честь польского математика Мозеса Пресбургера, который в 1929 году предложил соответствующую систему аксиом в логике первого порядка, а также показал её разрешимость. 

Язык арифметики Пресбургера включает константы 0, 1, одну операцию +, и предикат равенства =. Аксиомы имеют вид:

  1. ¬(0 = x + 1)

  2. x + 1 = y + 1 → x = y

  3. x + 0 = x

  4. (x + y) + 1 = x + (y + 1)

  5. (P(0) ∧ (P(x)→P(x + 1))) → P(y), где P — формула первого порядка включающая 0, 1, +, = и одну свободную переменную x.

Следует заметить, что (5) на самом деле не одна аксиома, а схема аксиом, представляющая бесконечное множество аксиом, по одной, для каждой формулы P. (5) является формализацией принципа математической индукции. Она не может быть эквивалентно заменена никакой конечной системой аксиом. Таким образом арифметика Пресбургера не является конечно аксиоматизируемой.

 Литература:

  • Cooper, D. C., 1972, "Theorem Proving in Arithmetic without Multiplication" in B. Meltzer and D. Michie, eds., Machine Intelligence. Edinburgh University Press: 91–100.

  • Ferrante, Jeanne, and Charles W. Rackoff, 1979. The Computational Complexity of Logical Theories. Lecture Notes in Mathematics 718. Springer-Verlag.

  • Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic." Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41.

  • G. Nelson and D. C. Oppen (Apr. 1978). «"A simplifier based on efficient decision algorithms"». Proc. 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages: 141–150.

  • Mojżesz Presburger, 1929, "Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt" in Comptes Rendus du I congrès de Mathématiciens des Pays Slaves. Warszawa: 92–101.

  • Pugh, William, 1991, "The Omega test: a fast and practical integer programming algorithm for dependence analysis,".

  • Reddy, C. R., and D. W. Loveland, 1978, "Presburger Arithmetic with Bounded Quantifier Alternation." ACM Symposium on Theory of Computing: 320–325.

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24