Классификация автоматных базисов Поста по разрешимости свойств полноты и А-полноты, Бабин Д.Н., 2009

Классификация автоматных базисов Поста по разрешимости свойств полноты и А-полноты, Бабин Д.Н., 2009.

   Рассматриваются базисы вида Ф U v где Ф некоторый замкнутый класс булевых функций, заданный своим конечным базисом, а v конечная система автоматных функций. Описаны все классы Поста Ф, для которых разрешима проблема полноты и, соответственно, А-полноты базиса Ф U v. Приведены аналогичные результаты для многозначных логик.
Для студентов, аспирантов и научных сотрудников, специализирующихся в области математической кибернетики и дискретной математики.




Основные леммы.
Известно что, для конечных систем автоматов проблемы полноты [15] и А - полноты [17] алгоритмически неразрешимы. Сформулируем эти факты в виде лемм.

Лемма 2.1.
Не существует алгоритма, по конечному множеству v С Ра решающего вопрос, верно ли, что [v] = Ра.

Лемма 2.2.
Не существует алгоритма, по конечному множеству v С Ра решающего вопрос, верно ли, что [v]а = Ра.

Замечание 2.1.
Если проблема Ф-полноты (Ф- А -полноты) алгоритмически неразрешима для Ф = F1, то она также неразрешима для всякого замкнутого класса F2 С F1, и двойственного к F1 замкнутого класса F1.

ОГЛАВЛЕНИЕ.
Глава 1. Алгоритмическая разрешимость полноты и А-полноты конечных систем а.-функций, содержащих полную систему истинностных функций.
§1.1. Основные понятия и леммы.
§1.2. Доказательство лемм 1.1, 1.2, 1.3.
§1.3. Доказательство лемм 1.4, 1.5.
§1.4. Доказательство теорем 1, 2.
Глава 2. Алгоритмическая неразрешимость проблемы полноты и А-полноты конечных систем автоматов с истинностной частью типа O, S, P, F3.
§2.1. Основные леммы.
§2.2. Доказательство лемм.
Глава 3. О классификации базисов в Pk по разрешимости полноты для автоматов.
§3.1. Основные леммы и доказательство теорем.
§3.2. Доказательство лемм 3.1, 3.2.
§3.3. Доказательство лемм 3.3 - 3.6.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Классификация автоматных базисов Поста по разрешимости свойств полноты и А-полноты, Бабин Д.Н., 2009 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Бабин