Решение проблемы классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты

• Автор: Бабин, Дмитрий Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 244 с. : ил.

Оглавление.
Введение
1. Алгоритмическая разрешимость полноты и А-полноты конечных систем а.-функций, содержащих полную систему истинностных функций
1.1. Основные понятия и леммы
1.2. Доказательство лемм 1.1,1
1.3. Доказательство лемм 1
1.4. Доказательство теорем 1
2. Алгоритмическая разрешимость полноты и А-полноты конечных систем автоматных функций, содержащих истин-ностную функцию хуУхгУуг
2.1. Основные леммы
2.2. Доказательство вспомогательных утверждений
2.3. Доказательство теорем 3
3. Алгоритмическая разрешимость полноты и А-полноты конечных систем автоматных функций, содержащих истинностную функцию х+у--г
3.1. Основные леммы
3.2. Доказательство лемм 3
3.3. Доказательство лемм 3
3.4. Доказательство лемм 3
4. Алгоритмическая неразрешимость проблемы полноты и А-полноты конечных систем автоматов с истинностной частью типа 0,5, Р, 77
4.1. Основные леммы
4.2. Доказательство лемм
Список литературы

Введение.
Понятие автомата относится к числу важнейших в математике. Оно возникло на стыке разных ее разделов, а также в технике, биологии и других областях. Содержательно автомат представляет собой устройство с входными и выходными каналами. На его входы последовательно поступает информация, которая перерабатывается им с учетом строения этой последовательности и выдается через выходные каналы. Эти устройства могут допускать соединение их каналов между собой. Отображение входных последовательностей в выходные называют автоматной функцией, а возможность получения новых таких отображений за счет соединения автоматов приводит к алгебре автоматных функций.
Первый толчок к возникновению теории автоматов дала работа Поста Э. 1921 года [1]. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций, которые были в дальнейшем методически переработаны и упрощены в книге Яблонского С.В., Кудрявцева В.Б., Гаврилова Г.П. ’’Функции алгебры логики и классы Поста” [2].
Сами автоматы и их алгебры начали исследоваться в тридцатые годы текущего столетия, но особенно активно в период с 50-х годов.
Основополагающую роль здесь сыграли работы Тьюринга, авторов знаменитого сборника ’’Автоматы” [3] Шеннона, Мура, Клини и других. Последующие работы но изучению алгебр автоматов велись под большим влиянием

известных статей A.B. Кузнецова [4,5] и С.В. Яблонского [6] по теории функций -знатной логики. Эти функции могут рассматриваться как автоматы без памяти, к которым применяются операции суперпозиции. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решетке замкнутых классов и другие, а также развитый аппарат сохранения предикатов как ключевой для решения этих задач, оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.
Основу результатов для функций /г-значной логики составляет подход A.B. Кузнецова, опирающийся на понятие предполного класса. Для конечно-порожденных систем таких функций семейство предполных классов образует критериальную систему; другими словами, произвольное множество является полным точно тогда, когда не является подмножеством ни одного предполного класса. Множество этих предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути С.В. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с
A.B. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значности. Затем усилиями многих исследователей [7-11] последовательно были открыты новые такие семейства, а заключительные построения провел Розенберг [12].

носительно суперпозиции, Дискретная математика, том 1, 1989, выпуск 4, с.86-91, Наука, Москва.
10.Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.
11.Бабин Д.Н., Вербальные подавтоматы, Seminar berichte Humbolt Universitet 1983,с.4-9.
12.Бабин Д.Н., Выразимость автоматов при использовании вербальных операций, Материалы всесоюзного семинара по дискретной математике Изд. МГУ 1986, с. 155-160.
13. Бабин Д.Н. Задача выразимости в некоторых классах автоматов Комбинаторно-алгебраические методы в прикладной математике, Горький 1985. с. 21-45.
14. Babin D.N., Verbal opération on automaton, FCT Springer Verlag 1987, c. 96-98.
15. Бабин Д.H., О суперпозициях ограниченно - детерминированных функций, Математические заметки, 1990 т.47 вып.З, с.3-10.
16. Бабин Д.Н., О суперпозициях в некоторых классах о.-д. функций, Логико-алгебраические конструкции, Тверь, 1992, с. 17-22.
18. Babin D.N. On completeness of the binary bounded determined functions with respect to superposition, Discrète mathematics and applications, VI,N4,1991, p.423-433.
Автор выражает благодарность академику АТН РФ Кудрявцеву В.Б. за постановку задачи и ценные указания.