Статья в сборнике "Математические вопросы кибернетики" №7, Москва, 1998
Авторы:Шоломов Л.А.
Представление и исследование порядковых моделей выбора средствами логики первого порядка
Аннотация:
Функция выбора C на Rn сопоставляет каждому X⊆Rn выбранное множество C(X)⊆X. Она называется порядковой, если для любого строго монотонно отображения ψ: Rn→Rn и всякого X⊆Rn) выполнено C(ψ(X))=ψ(C(X)). В статье предложен и изучен метод формализации порядковых функций выбора на Rn средствами логики первого порядка. Исследованы на формализуемость все встречающиеся в научной литературе порядковые модели выбора по бинарному отношению. Для большинства из них (22 из 28) указаны формализации, для остальных корректно доказана неформализуемость. Рассмотрены операции над функциями выбора (параллельная и последовательная композиция, ветвление, обращение, ограниченная обратная связь) и для каждой из них указано соответствующее преобразование формализаций. Это позволяет формализовать сложные иерархические модели порядкового выбора. Исследован на алгоритмическую разрешимость, NP-трудность и полиномиальность ряд задач, связанных с построением, упрощением и минимизацией формализаций, где под сложностью формализации понимается число кванторов в предваренной форме.
Ключевые слова:
функция выбора, порядковый выбор, логика первого порядка, формализация порядкового выбора, преобразования формализаций, сложность формализации
