Сотрудники :: Бабин Дмитрий Николаевич :: Публикации Бабина Д.Н.

О значении булевой части автоматного базиса для разрешимости задачи полноты

Бабин Д.Н.
Кафедра Математической теории интеллектуальных систем

Рассматривается задача полноты конечных систем автоматных функций относительно операций суперпозиции и обратной связи. В общем случае она алгоритмически неразрешима. Для булевых функций – автоматных функций без памяти,  эта задача решена Э. Постом. В докладе будут рассматриваться системы вида Ф È m, где Ф базис некоторого замкнутого класса булевых функций ( класса Поста ), а m конечная система автоматных функций. Полностью описаны базисы Ф, для которых разрешима проблема полноты произвольной системы автоматных функций вида ФÈm.

In this paper is  considered completeness problem of finite automata. In general, this problem is unsolvable. But, in case, when the system contains some Boolean functions, there exist an algorithm of solution of this problem. In this paper show the classification of Boolean functions, which respect the solvebility of complteness problem for automata.

Для базисов автоматных функций без памяти ( булевых функций ) проблема полноты относительно суперпозиции была решена Э. Постом [ 11 ]. При обобщении этой задачи на автоматные функции с памятью при использовании суперпозиции и обратной связи возникли cущественные трудности. Принципиальная невозможность решения этой задачи в общем случае была установлена в работе [ 6 ], где была показана континуальность всякой критериальной системы, а в работе [ 5 ] установлена ее алгоритмическая неразрешимость для конечных базисов автоматных функций. Тем не менее, для базисов, содержащих  все булевы функции, указанная задача алгоритмически разрешима [1]. Естественно исследовать  на  полноту системы Поста вида pÈm, где p- некоторый класс Поста, а m – конечная система автоматных функций. Возникает разделение классов Поста на "сильные" и "слабые" по их способности гарантировать  разрешимость полноты систем автоматных функций. В докладе приводится описание всех "сильных" и всех "слабых" классов Поста.

Мы будем использовать обозначения из [7,8]. Пусть E₂={0,1}, E множество всех сверхслов 

a(1)a(2)...,

где  a(j) Î E₂, j=1,2,.... Пусть

f: Eⁿ Þ E^m

-автоматная функция ( а. – функция), т.е она задается рекуррентно соотношениями,.

q(1)= q₁,

q(t+1)= j(q(t),a₁(t),...,a_n(t)),

b_j(t)= y_j(q(t), a₁(t),...,a_n(t)), j=1,...,m

где q Î Q={q₁,...,q_r}.

Параметр  q  называется состоянием а.- функции f, q₁ – ее начальным состоянием, вектор – буквы

a(t)=(a₁(t),...,a_n(t)), b(t)=(b₁(t),...,b_n(t))

называются входной и выходной буквами, а сверхслова

a(1)a(2)...,                                             b(1)b(2)...

- входным и выходным сверхсловами соответственно.

Класс всех а. – функций обозначим через P_a. В этом классе обычным образом введем операции  суперпозиции и обратной связи [7].  Пусть M Í P_a, обозначим через [ M ] множество всех а. – функций, получающихся из  M с помощью операций  суперпозиции и обратной связи. Множество  M  называется полным, если [ M ] = P_a.  Проблема полноты для P_a состоит в описании всех полных множеств  M.

Обозначим через P_a⁽¹⁾ - класс всех а. – функций с одним состояниeм. Автомвтные функции из P_a⁽¹⁾ называются истинностными и могут рассматриваться как булевы функции. Автоматная функция

B: Eⁿ Þ E^m

c    уравнениями

q(1) = 1,

q(t+1) = x(t),

b(t)= q(t).

называется а.-функцией задержки. В P_a имеются конечные полные системы. Известно, например, что [{ B , f_Sh }] = P_a, где f_Sh универсальная булевая функция Шеффера.

Замкнутые  классы булевых  функций полностью описаны Э. Постом [8,9]. Все они конечнопорожденные и образуют счетную решетку по включению. Автор показал в [ 1 ], что для верхнего элемента решетки – класса всех булевых функций P⁽¹⁾=[ f_Sh ] имеется алгоритм определения полноты системы M= f_ShÈm.

Пусть X множество всех классов Поста,  Sol  множество таких pÎ X, что для конечных m Ì P_a проблема полноты p È m разрешима, а UnSol  аналогичное множество с неразрешимой проблемой полноты. Назовем классы из Sol "сильными" классами Поста, а из UnSol, соответственно, - "слабыми".

Пусть

D₂ = [{ xy + xz + yz }] 

класс монотонных самодвойственных булевых функций, 

L₄ = [{ x + y + z }] 

класс линейных самодвойственных булевых функций, сохраняющих нули и единицы. Пусть

h(x₁, x₂, x₃, x₄)= x₁ x₂ Ú x₁ x₃ Ú x₁ x₄ Ú x₂ x₃ Ú x₂ x₄ Ú  x₃ x₄ ,

F =  [ { h(x₁, x₂, x₃, x₄), ùx Ú y } ] , и  F^/ -  двойственный к F.

Имеет место

Теорема.            pÎSol  Û  (p Ê D₂ ) Ú (p Ê L₄).

Доказательство теоремы  приведено в работах [1,2,3,4].

Из теоремы  получается вывод, что "сильные" классы Поста обязательно содержат либо функцию медиану xy + xz + yz, либо функцию x + y + z. Заметим, что всякий надкласс "сильного" класса является "сильным", а подкласс "слабого" - "слабым", двойственный к "сильному", относительно замены 0 на 1, будет "сильным", а к "слабому" – "слабым" классом Поста.

Следствие 1.              F , F^/ Î UnSol ;

Известно [ 8,9 ], что число классов, содержащихся либо в F^/ либо в F – бесконечно, а не содержащихся ни в F^/ ни в F – конечно, поэтому имеет место

Следствие 2.

Множество Sol конечно, множество UnSol бесконечно.

Литература.

1. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992 г., выпуск 4, с.41-56, Наука, Москва.

2.Бабин Д.Н.,  О разрешимости проблемы полноты для  специальных систем автоматных функций, Дискретная математика, том 8, 1996 г., выпуск 4, с.79-91, Наука, Москва.

3.Бабин Д.Н., Алгоритмическая разрешимость свойств полноты и А-полноты конечных систем автоматных функций с линейной истинностной частью, Интеллектуальные системы, том 3, 1998 г., с.51-69, Москва.

4.Бабин Д.Н., Конечность множества автоматных базисов Поста с разрешимой проблемой полноты. Дискретная математика, том 10, 1998 г., выпуск 3, с.57-64, Наука, Москва.

5. Кратко М.И., Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов, ДАН СССР, 1964, т.155, \No1, с.35–37;

6.Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами, ДАН СССР т.151,N3,1963, c.493-496.

7.Кудрявцев В.Б., Алешин С.В., Подколзин А.С., Введение в  теорию автоматов, М., Наука, 1985.

8.Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции  алгебры логики и классы Поста, М., Наука, 1966.

9.Post E. Two-valued iterative systems of mathematical logik, Printston,1941, C.121

Материалы конференции "Нейрокомпьютеры и их применение". Москва, 2000 г.

Наверх