Рассматриваются результаты исследований, предпринятых с целью нахождения вычислительной сложности для решения истинности формул арифметик Пресберга. Эта арифметика есть теория целых. Предложения Пресберга – есть формула из соотв. арифметик, которая не имеет свободных переменных и тем самым решаема на предмет установления истинности. Использовано доказательство автоматной корректности спецификации. Результаты исследований широко применимы в различных областях конструирования и в том числе при создании устройств ВС, коммуникационных протоколов, программ. При этом решена задача нахождения подкласса предложений, нахождения истинности которых оценивается на уровне нижней границы сложности. Библ. 19.