Алгоритмические проблемы логики
Жетекшінің аты-жөні, тегі: Перетятькин М.Г.
Work head: С.А.Бадаев
: Ин-т теорет. и прикл. мат.
Инвентарлық номер: 0298РК00729
Тіркелген номер: 0197РК00342
негізгі сөздер: логика, алгоритмические, проблемы, классы, Ершова, теоремы, оценки, семантические, классы,
Описаны некоторые алгоритмические и структурные свойства моделей классической логики предикатов, а также свойства вычислимых семейств рекурсивно перечислимых множеств и классов конструктивных моделей. Показано, что обобщенные алгебры Лиденбаума над декартовым списком свойств изоморфны между собой для исчислений предикатов любых двух конечных богатых сигнатур. Доказаны существование универсальных нумераций относительно классов Ершова, теорема о невозможности аналога теоремы Райса четвертого уровня для семантических классов предложений. Получены точные оценки иерархии семантических классов предложений специального вида и алгоритмической сложности относительных классов предложений при известной сложности теории.