АЛГЕБРА И ЛОГИКА

Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.

Рассматривается совместная логика задач и высказываний QHC, введённая С. А. Мелиховым, а также интуиционистская модальная логика QH4. Рассмотрено погружение этих логик в классическую логику предикатов первого порядка. Установлен аналог теоремы Лёвенгейма-Сколема о счётной элементарной подмодели для логик QHC и QH4.

Изучаются семейства PI, состоящие из перестановок натурального ряда ω, степени которых принадлежат идеалу тьюринговых степеней I, и их скачки P′I. Для любого счётного тьюрингова идеала I приводятся описания спектров степеней семейств PI и их скачков P′I. Для некоторых идеалов I, порождённых в. п. степенями, определяются спектры семейств PI.

Рассматривается класс обобщённых дифференцирований, возникающий в связи с задачей присоединения единицы к алгебре с обобщённым дифференцированием, а также поиска обёртывающих для алгебр Новикова-Пуассона. Приводятся условия существования локализации алгебры с тернарным дифференцированием, а также условия, при которых по алгебре с тернарным дифференцированием можно построить алгебру Новикова-Пуассона и Йорданову супералгебру. И наконец, показывается, как простота алгебры с обобщённым дифференцированием по Брешару связана с простотой соответствующей алгебры Новикова.

Ранее К. Дошен и М. Божич ввели четыре независимые интуиционистские модальные логики - по одной для каждого из четырёх типов модальных операторов: необходимости N, возможности P, невозможности Im и не-необходимости Un. Эти логики обозначаются HKM, где M∈{N,P,Un,Im}. Интерес к тому, чтобы рассматривать четыре типа модальных операторов по отдельности, связан именно с тем, что над интуиционистской логикой они не могут быть сведены друг к другу. Здесь изучаются расширения логик HKM, у которых есть нормальные напарники. Оказывается, что нормальные напарники есть у всех расширений логик HKN и HKUn. Для расширений HKP и HKIm получен критерий существования нормальных напарников, который заключается в присутствии некоторого модального закона двойного отрицания. Также показывается, как добавление этого закона влияет на выразительные возможности логики. Особый интерес представляет результат о том, что расширения HKP и HKIm имеют нормальных напарников, только если они дефинициально эквивалентны расширениям HKN и HKUn соответственно. Этот результат является ещё одним примером различия в поведении четырёх типов модальных операторов над интуиционистской логикой.