Содержание к диссертации
Введение
1 Автоматное замыкание 27
1.1 Основные определения 27
1.2 Автоматное замыкание 29
1.3 Описание автоматно замкнутых классов 30
2 Обобщенные формулы 37
2.1 Определение обобщенных формул 37
2.2 Соотношение между обобщенным и автоматным замыканиями 43
2.3 Свойства обобщенных формул 44
2.4 Реализация функций из класса 01
2.4.1 Пары наборов 54
2.4.2 Отношение частичного порядка на множестве наборов 59
2.4.3 Различные допустимые последовательности 66
2.4.4 Доказательства основных утверждений 73
2.5 Реализация функций из классов 0 и 1 77
3 Универсальные автоматы 82
3.1 Определения и различные постановки задачи 82
3.1.1 Неинициальный автомат 83
3.1.2 Инициальный автомат с многократной подачей наборов 85
3.1.3 Инициальный автомат с однократной подачей наборов 86
3.2 Булев автомат с двумя константными состояниями 87
3.2.1 Свойства автоматов из множества V2() 88
3.2.2 Верхняя оценка числа функций, реализуемых квазиуниверсальным автоматом из V2() 94
3.2.3 Условия квазиуниверсальности автомата из V2() 101
3.3 Булев автомат с тремя константными состояниями 106
3.3.1 Примеры и оценка снизу 107
3.3.2 Оценка сверху, первый случай 113
3.3.3 Оценка сверху, второй случай 123
3.3.4 Условия квазиуниверсальности автомата c тремя константными состояниями 128
3.4 Булев автомат с константными состояниями, 3 164
3.4.1 Свойства автоматов с состояниями 165
3.4.2 Оценка сверху для автоматов из множества V1() 167
3.4.3 Пример автомата с 2 + 2 состояниями, реализующего все булевы функции кроме констант 170
Заключение 173
Литература
- Автоматное замыкание
- Свойства обобщенных формул
- Инициальный автомат с однократной подачей наборов
- Булев автомат с тремя константными состояниями
- Условия квазиуниверсальности автомата c тремя константными состояниями
Автоматное замыкание
Пусть {0,1}п — множество всех наборов = (1,2,... ,п), таких что і, 2, . . . , п {0,1}, І назовем -ой компонентой набора , где 1, 1 . Пусть — счетное множество переменных, элементы множества обозначаются символами i,i, i,..., = 1,2,...; нижние индексы иногда опускаются. Обозначим через набор переменных (і,2,...,п), где \, і, . . . , п Є . Пусть (п) — отображение множества {0,1}п в {0,1}, 1, и пусть функция (n)(), задает это отображение. Функция (n(i, 2, . . ., п) называется -местной булевой функцией (или функцией алгебры логики), а — -местным функциональным символом, соответствующим этой функции. Множество всех функций алгебры логики обозначается через . Через i() обозначается множество всех булевых функций от фиксированных переменных
Под булевым автоматом будем понимать автомат = (, ,,,) c произвольным числом входов, одним выходом, входным алфавитом = {0,1}, выходным алфавитом = {0,1}, алфавитом состояний , функцией перехода и функцией выхода (основные понятия теории автоматов см., например, в [28,30,62]). Пусть — число входов автомата . Без ограничения общности будем полагать, что входы автомата занумерованы от 1 до , и на -й вход автомата подается значение булевой переменной {. Тем самым можно считать, что в каждый момент времени на вход автомата подается некоторый двоич ный набор значений переменных \,2, . . . ,п, и для любого фиксированного состояния Є функция выхода (, i, 2, . . ., п) является булевой функцией от переменных i, 2, . . ., п. Пусть Л С 2, булев автомат будем называть автоматом над Л, если для любого состояния автомата функция выхода (, i,2, . . . , п) содержится в Л. Заметим, что функции рассматриваются с точностью до несущественных переменных и переименования переменных.
Пусть qi = ({0,1}, {0,1}, , , , \) — инициальный булев автомат с начальным состоянием \ и входами. Пусть = (5і, З2, . . . , 2«) — упорядоченная последовательность всех двоичных наборов длины , 1 (далее — последовательность подаваемых наборов). Будем говорить, что автомат qi с последовательностью реализует булеву функцию (i,2,...,n), если при последовательной подаче на вход qi наборов из в первые 2П моментов времени, в каждый момент = 1,2,...,2П на выходе qi выдается значение (3t). Будем также говорить, что qi реализует функцию , если для некоторой последовательности наборов автомат qi с последовательностью реализует .
Аналогичные определения можно ввести для неинициального автомата. Пусть = ({0,1}, {0,1}, , , ) — неинициальный булев автомат с входами. Пусть Є , обозначим через q инициальный булев автомат, являющийся автоматом с начальным состоянием . Пусть = (Зі, З2, . . . , 2«) — последовательность подаваемых наборов. Будем говорить, что автомат с последовательностью реализует булеву функцию (i,2,...,n), если существует такое состояние Є , что функция реализуется автоматом q с последовательностью . Будем также говорить, что реализует функцию , если для некоторой последовательности подаваемых наборов автомат с последовательностью реализует . 1.2 Автоматное замыкание
В данной главе изучаются вопросы, связанные с автоматным замыканием множеств булевых функций. Дадим необходимые определения.
Автоматные функции, реализуемые булевыми автоматами, будем называть двоичными автоматными функциями. Другими словами, автоматная функция является двоичной, если входным и выходным алфавитом для этой функции является алфавит {0,1}. Пусть Л С Р2, двоичную автоматную функцию h(xi,X2, хп) будем называть функцией над Л, если h реализуется некоторым инициальным булевым автоматом над Л. Пусть Vqi — некоторый инициальный булев автомат, реализующий двоичную автоматную функцию /г, и С — некоторая последовательность подаваемых наборов. Будем говорить, что функция h с последовательностью подаваемых наборов С реализует булеву функцию f(xi, Х2, хп), если / реализуется автоматом Vqi с последовательностью подаваемых наборов С. Будем также говорить, что функция h реализует булеву функцию /, если для некоторой последовательности наборов С функция h с последовательностью С реализует /.
Для автоматных функций можно стандартным образом определить понятие автоматной формулы, т.е. формулы над системой автоматных функций (см. например, [30,62]). Пусть дано некоторое конечное множество булевых функций Л. Введем следующее понятие автоматной формулы над Л индуктивным образом.
Свойства обобщенных формул
Аналогичное утверждение можно доказать для функций из класса То. Будем обозначать через То множество всех обобщенных формул F над Л = {/l( i, #2, Xm), /2( 1, Ж2, Xm), . . . fk{Xl, X2, Xm)}, где fi(xi, X2, xm) Є To, 1 і к с правилом смены, удовлетворяющим условиям ga{fi) = fj тогда и только тогда, когда 9a{fj) = fi и 9a{fi) = /г, если й т 0, где G = {дап9а2 i9a2m}- Верна следующая лемма.
Лемма 2.3.2. Пусть обобщенная формула F принадлежит множеству То, В = (5?i,5?2,... ,5?fc) — квазипоследовательность подаваемых наборов, такая, что наборы дц и дц+\ равны, Ф(Е,В) = (Фі, Ф2,... , Ф/г+і)- Тогда V(B)\ai = f(B)\ai+1 U Фі = Фі-\-2 г Доказательство. Доказательство будем вести индукцией по глубине начальной формулы.
База. Рассмотрим обобщенную формулу с глубиной начальной формулы равной 1. В этом случае в формулах Ф и Ф +і имеется только один функциональный символ. Рассмотрим два случая. Пусть 5 = 0. Тогда, в силу условия gaifi) = fj тогда и только тогда, когда g%(fj) = fi на правило смены, функциональный символ формул ФІ и ФІ+І либо не изменится, либо изменится дважды, значит, будет верно равенство ФІ = Ф +2.
Кроме того, поскольку все функций из Л принадлежат классу То и на внешний функциональный символ дважды подается набор 0, то верно равенство F(B)\a. = f(B)\ai+1 = 0. Пусть теперь а ф 0. Тогда, в силу условия gaifi) = fi, если а Ф 0 на правило смены, функциональный символ формул ФІ и ФІ+І не изменится, следовательно верно равенство ФІ = ФІ+І = ФІ+2. Поскольку на внешний функциональный символ два г г жды подается один и тот же набор, то F(_B) = F(B)\ai+1. Переход. Пусть лемма доказана для обобщенных формул с глубиной начальных формул не более г, докажем для обобщенных формул с глубиной начальных формул равной г + 1. На внешний функциональный символ формул ФІ и Фі+і подаются одинаковые наборы в силу предположения индукции. Возможны два случая. Пусть на внешний функциональный символ формул ФІ и Фі+і подается набор 0. Поскольку все функций из Л принадлежат классу То и на внешний функциональный символ дважды подается набор 0, то верно равенство F(_B) = f(B)\ai+1 = 0. В силу условия gaifi) = fj тогда и только тогда, когда ga(fj) = fi на правило смены, внешний функциональный символ формул ФІ и Фі+і либо не изменится, либо изменится дважды, применяя предположение индукции, получаем равенство ФІ = ФІ-\-2. Пусть теперь на внешний функциональный символ г подается набор отличный от 0. Тогда, в силу условия g ifi) = /«, если а Ф 0 на правило смены, внешний функциональный символ формул Ф и Фі+і не изменится, применяя предположение индукции, получаем равен ства ФІ = ФІ+І = ФІ+2. Поскольку на внешний функциональный символ дважды подается один и тот же набор, то F(_B) = F(B)\% . Лемма доказана. И Воспользовавшись принципом двойственности для обобщенных формул (утверждение 2.3.3), можно сформулировать следующую лемму, являющуюся двойственной к лемме 2.3.2. Множество всех обобщенных формул F над Л = {/l( i, #2, Хт), /2( 1, Х2, Хт), . . . fk{Xl, Х2, Хт)}, где fi(xi, Х2, хт) Є Ті, 1 і к с правилом смены, удовлетворяющим условиям ga{fi) = fj тогда и только тогда, когда 9a{fj) = fi и 9a{fi) = ft, если а Ф 1, где G = {$ZLXI 9a.ii 19a2m}i будем обозначать через %\. Верна следующая лемма.
Лемма 2.3.3. Пусть обобщенная формула F принадлежит множеству %\, В = (o?i, о?2,..., 5?/г) — квазипоследовательность подаваемых наборов, такая, что наборы дц и дц+\ равны, Ф(Е,В) = (Фі, Ф2,... , Ф/г+і). Тогда V(B)\ai = f(B)\ai+1 U Фі = Фі-\-2 г Если справедливо включение Л С М, то верно следующее утверждение. Утверждение 2.3.5. Пусть обобщенная формула F над Л принадлежит множеству Тої (То, 2-і); справедливо включение Л С М, и В = (5?і, 5?2, , о?/;) — квазипоследовательность подаваемых наборов, такая, что верно дц 5?І+І. Тогда F( )a F(B)\ai+1 Доказательство. Пусть $(F, В) = (Фі, Ф2,..., Ф/г+і), где А; — длина квазипоследовательности В. В силу леммы 2.3.1 (2.3.2, 2.3.3) верно равенство Ф«+і(5?) = Фі(а). Поскольку все функции из Л принадлежат классу М, то все функции, реализуемые формулами Ф , где 1 j к + 1 монотонны. В частности, монотонна функция, реализуемая формулой Ф +ь А значит, в силу неравенства Оіі йї+і, верно неравенство F(-B)5j = Ф%\ %) = ФІ+І{(%І) ФІ+І{( І+І) = F(_B)йі 11 Утверждение доказано. И Это свойство обобщенных формул назовем монотонностью обобщенных формул.
Следствие 2.3.1. Пусть обобщенная формула F над Л принадлежит множеству Тої ( о, l), справедливо включение Л С М, и С — последовательность подаваемых наборов, такая, в ней существуют два сравнимых подряд идущих набора. Тогда значение F с последовательностью подаваемых наборов С на большем из этих наборов не меньше значения F с последовательностью подаваемых наборов С на меньшем из них.
Рассмотрим все такие булевы функции / Є Р2{п), что для любых двух наборов а, (З Є {0,1}п если набор а имеет в лексикографическом порядке меньший номер, чем набор /3, то верно неравенство /(5?) /(/3), п 1. Множество всех таких булевых функций при всевозможных п 1 обозначим через . Множество обобщенных формул F над , таких, что в них каждая переменная из множества всех переменных F входит ровно один раз, обозначим через О. Определим индуктивно лексикографический порядок вхождения переменных в формулу Ф(жі, Х2, Хп).
Свойства обобщенных формул
Функциональные символы формулы вида Ч/yXlj, Хп) І2іп_1 {Хі1 -Н-Іп-2 V «2 1 -"«1 V n-1 in J J ) будем иногда называть просто по номерам, т. е. к-ъш функциональным символом формулы Ф(жі, Х2 хп) является функциональный символ Нік: где 1 к п.
Теорема 2.4.1. Для любого п 1, любой функции д(хі,Х2, хп) из класса Тої П О00, любой обобщенной формулы F из $v существует такая допустимая последовательность С, что обобщенная формула F с последовательностью С реализует функцию д(х\,Х2, хп) и Ф\ = Ф2+ъ гоЛе г Ф(Р, С) = (Фі, Ф2, , Ф2«+і). Доказательство. Без ограничения общности можно считать, что верно неравенство д(хі,Х2,,хп) Х\. Рассмотрим все наборы длины п из множества 02. Пусть М — множество всех двоичных наборов длины п из множества Or?, на которых функция g(xi, Х2, хп) принимает значение 1. Заметим, что набор 0 не принадлежит множеству М. Положим т = \М\. Из утверждения 2.4.1 следует, что существует такая допустимая последовательность В = (/Зі, $2і @2п) из множества О(М), что $2п-\ = 1, @2п = 0 и обобщенная формула F с последовательностью В реализует функцию /v( i, Х2, хп). Пусть (F, ) = ( f, Ф-f,... , Ф +1). Заметим, что f3r = (1, 0,0,..., 0), где г = 2n_1 + т — 1.
Построим новую последовательность D = (7ь72? 72п) всех наборов длины п. Положим 7« = А для всех 1 і 2n_1 + m — 2 и 2n_1 + т і 2п — 2, /2п-1+т-і = 0, 72n-i = 1, 72 = (1, 0,0,..., 0). Пусть Ф(Р,1)) = (Ф;Р, Ф , , Ф +1). По построению F(D) . = 1 при 1 і 2n_1 + т — 2 и формула Ф _і+т(жі,Ж2,..., жп) отличается от формулы Ф -1+т(жі, Ж2,... , хп) только внешним функциональным символом, для формулы Ф. -ііто это — конъюнкция.
Если внешний функциональный символ формул Ф при 2n_1 +m i 2n — 2 является конъюнкцией, то верно равенство F(D) . = 0 при 2n_1 + т і 2п — 2. Докажем, что внешний функциональный символ формул Ф при 2п 1 + т г 2п — 2 является конъюнкцией. По построению выполнены равенства F( )b = 1 и наборы Д; принадлежат множеству OVz при 2n_1+m і 2n — 2, следовательно, на внешний функциональный символ всех формул Фf при 2n_1 +m i 2n — 2 подается набор (0,1) и, следовательно, у всех формул Фf при 2n_1+m і 2п — 1 внешним функциональным символом является дизъюнкция. Напомним, что формула Ф -\\jjJyX\i %2і і %п) отличается от формулы Ф -1, то(жь х2,, хп) только внешним функциональным символом и верно равенство 7« = А при 2n_1 + т і 2п — 2, а значит на внешний функциональный символ всех формул Ф при 2n_1 +m i 2n — 2 подается набор (0,1) и, следовательно, внешний функциональный символ формул Ф при 2n_1 +m i 2n — 1 является конъюнкцией.
Теперь покажем, что верно равенство F(Z))(i,o,o,...,o) = 1, для этого достаточно показать, что внешний функциональный символ формулы Ф является дизъюнкцией. Действительно, внешний функциональный символ формулы 2п-\ является конъюнкцией и верно равенство 72-1 = 1, значит, внешний функциональный символ формулы Ф является дизъюнкцией. Из вышеизложенного следует, что если положить С = D, то обобщенная формула F с по следовательностью С принимает значение 0 на всех наборах множества OVz не лежащих в М и значение 1 на всех наборах множества М U /2П.
Осталось показать, что верно равенство Ф +і = Фі = Ф„(жі,Ж2?,х г г Поскольку 72 = (1,0,0,... ,0), то на внешний функциональный символ формулы Ф п подается набор (1,0) и, т. к. внешний функциональный символ формулы Ф является дизъюнкцией, то внешний функциональный символ формулы Ф +і тоже является дизъюнкцией. Заметим, что функциональные символы сп — 2-го по 1-й формул Ф , где 2 г 2п + 1, зависят от начальной формулы Ф;Р и разрядов со 2-го по п-й наборов из последовательности D подаваемых наборов. Разряды с 2-го по n-й наборов последовательности D совпадают с разрядами с 2-го по n-й наборов последовательности , а значит функциональные символы с п—2-го по 1-й формул Ф совпадают с функциональными символами с п — 2-го по 1-й формул Фf, где 2 і 2п + 1. Из утверждения 2.4.1 следует равенство Фf = Фуг+і = Ф (жі,Ж2,... ,хп). Следовательно, выполнены равенства Г Г 2"+і = Ф +і = f = Фп(жъ х2) , %п) = Ф;Р. Теорема доказана.
Булев автомат с тремя константными состояниями
Доказательство. Если верно хотя бы одно из неравенств 1 4 U К\ 2п — п — 1 или \А U Е\ 2п — п — 1, то утверждение верно в силу следствия 3.3.1. Пусть \А U К\ 2п — п и \А U Е\ 2п — п. Если \В U Т\ 3, то доказываемое утверждение верно в силу утверждения 3.3.11. Пусть \В U Т\ 2. Учитывая, что А П К = 0, оценим мощность множества К П Е: \К П Е\ = \А U К\ — \А\ — \K\E\ \А U К\ — \А\ — {0,1}п\(А U Е)\ 2п — п — 2п — (2П — (2п — п)) = 2п — 2 п. Обозначим через & множество всех функций из 2( ), принимающих значение 1 на всех наборах множества {0 1}п\(К П Е). Поскольку A U М С {0,1}п\(К П Е1), то функции из & принимают значение 1 на всех наборах множества A U М. Тем самым для любой функции /из верно \Af\ =0 и М9 = 0. Пусть С = (/Зі, / 2,... , / 2") — последовательность всех двоичных наборов длины п, такая, что автомат V с последовательностью С реализует функцию / из (5. Тогда при последовательной подаче наборов последовательности С на входы автомата У, автомат V перейдет из 1-состояния в одно из 0-состояний ровно \(В U Т)\\ раз, а из 0-состояний в 1-состояние не менее _ \(К В)0А\ раз. Число переходов из 0-состояний в 1-состояние либо совпадает с числом переходов из 1-состояния в 0-состояния, либо на единицу больше этого числа. Следовательно, \{К П Е)г\ 2 (\(В UT)\\ + 1) + 1. В силу условия \BUT\ 2 имеем \(КГ\Е)г\ 7. Следовательно, автомат V не может реализовать функции из (5, принимающие значение 0 больше, чем на семи наборах множества КГ\Е. Оценим число а функций из (5, которые не может реализовать автомат V:
Заметим, что верны следующие эквивалентности 22" 1-2-п"1 2п Т 1 - 2 п - 1 п 2п 1 3 п + 1. Последнее неравенство выполнено при всех п 6. Следовательно, а 2П, поэтому Р(У) 22 — 2П. Утверждение доказано. И Утверждение 3.3.13. Если п б и автомат V из множества З (п) таков, что \К П Т\ = 0, mo \P(V)\ 22 — 2П.
Доказательство. Если \B\JT\ 3, то доказываемое утверждение верно в силу утверждения 3.3.11. Пусть UT 2. Если ЛиііГ 2n—п —1, то доказываемое утверждение верно в силу следствия 3.3.1. Пусть ЛиііГ 2П — п — 1. Если \А\ 2П_1, то доказываемое утверждение верно в силу утверждения 3.3.12. Пусть \А\ 2п 1. Заметим, что \Т\ \В U Т\ 2. Обозначим через множество всех функций из Р2{п), таких, что они принимают значение 1 на всех наборах множества К и значение 0 на всех наборах множества Т. Пусть С = (/Зі, / 2,..., 02") — последовательность всех двоичных наборов длины п, такая, что автомат V с последовательностью С реализует функцию / из &. В силу условий \К \ = \Tj\ = 0, автомат V не переходит в 0-состояние отличное от начального. При последовательной подаче наборов последовательности С на входы автомата У, автомат перейдет из начального 0-состояния в 1-состояние ровно \Af\ раз и из 1-состояния в начальное 0-состояние ровно \В\\ раз. Число переходов из 0-состояний в 1-состояние либо совпадает с числом переходов из 1-состояния в 0-состояния, либо на единицу больше этого числа. Значит, верно одно из равенств \АА — 1 = \В\\ или \АА = \В\\. Поскольку \В\ \BUT\ 2, то верно неравенство \АА 3. Следовательно, автомат V не может реализовать функции из (5, принимающие значение 0 больше, чем на трех наборах множества А. Учитывая, что п б, \Т\ 2 и \А\ 2п 1 32, оценим число а функций из (5, которые не могут быть реализованы автоматом V: Следовательно, Р(У) 22 — 2п. Утверждение доказано. И Следствие 3.3.5. Если п 6 и автомат V из множества Ю (п) таков, что \Т\ = 0, то \Р(у)\ 22 — 2П.
Утверждение 3.3.14. Если п 1 и автомат V из множества Ю (п) таков, что \В U Т\ = 2, то \P(V)\ 22 — 2П.
Доказательство. Если \К П Т\ = 0, то доказываемое утверждение верно в силу утверждения 3.3.13. Пусть \К П Т\ = 0. Обозначим через & множество всех функций из Р2(п), таких, что они принимают значение 1 на обоих наборах множества BUT. Если функция /из & может быть реализована автоматом У, то в силу утверждения 5 верно неравенствo \(А U Е)А \(В U Т)\\ = 2. Следовательно, автомат V не может реализовать функции из (5, принимающие значение 0 меньше, чем на двух наборах из {0,1}п. Оценим число а функций из (5, которые не может реализовать автомат V: а С2п_2 + С2п_2 = 1 + 2п — 2 = 2П — 1. Покажем, что автомат V не может реализовать по крайней мере еще одну функ цию из Р2(п). Поскольку ІСПТ = 0, можно рассмотреть произвольный набор а из К Г\Т. Заметим, что если функция, реализуемая автоматом У, принимает значение 0 на наборе о?, то такая функция должна принимать значение 0 на хотя бы еще одном наборе. Значит, автомат V не может реализовать такую булеву функцию д, которая принимает значение 0 только наборе а. Отметим также, что, поскольку й Є BUT, то д ф &. Следовательно, автомат V не мо жет реализовать по крайней мере 2П булевых функций, т. е. верно неравенство -Р("Ю1 — 22" — 2П.
Условия квазиуниверсальности автомата c тремя константными состояниями
Утверждение 3.4.5. Любой инициальный булев автомат с константными состояниями не может реализовать по крайней мере две функции алгебры логики.
Доказательство. Пусть дан инициальный булев автомат с константными состояниями и входами, 1. Без ограничения общности будем предполагать, что в начальном состоянии автомата функцией выхода является константа 0. Такой автомат заведомо не может реализовать булеву константу 1, поскольку выдает значение 0 по крайней мере на одном входном наборе. Рассмотрим множество ( наборов, при подаче которых автомат переходит из начального 0-состояния в одно из 1-состояний. Если это множество совпадает с множеством {0,1}п, то автомат не может реализовать булеву константу 0, поскольку выдает значение 1 по крайней мере на одном входном наборе (втором наборе подаваемой последовательности), следовательно, утверждение доказано. Пусть теперь существует набор й, не содержащийся в (. В таком случае автомат не может реализовать булеву функцию, принимающую значение 0 только на наборе а и значение 1 на всех других наборах. Утверждение доказано. I Приведем пример инициального булевого автомата Vau с 2п + 2 константными состояниями, реализующего все булевы функции из Р2{п) кроме констант. Обозначим через Vau автомат с двумя О-состояниями, одно из которых является начальным, и 2П 1-состояниями, имеющий следующую функцию переходов. Пусть 5?i, OL I, 5?2« — некоторая последовательность всех наборов из {0,1}п. Опишем функцию переходов автомата Уац. Автомат Vau переходит из начального 0-состояния в г-ое 1-состояние при подаче набора дц и из і-ого 1-состояния в 0-состояние, не являющееся начальным, при подаче набора дц+\, где дц Є {0,1}п, і Є {1, 2, 2n}, 5?2«+i = OL\. При подаче на вход автомата Vau, находящегося в г-ом 1-состоянии, любого набора, кроме набора 5 +1, автомат остается в том же состоянии. При подаче на вход автомата Vau, находящегося в 0-состоянии, не являющемся начальным, любого набора автомат остается в том же состоянии. Диаграмма переходов автомата Vau схематично изображена на рис. 5. В кружочках написаны символы, соответствующие функции выхода в этом состо-яниии, а на стрелках — наборы, при подаче которых на вход автомата автомат из состояния, из которого идет стрелка, переходит в состояние, на которое указывает стрелка. Звездочкой помечено начальное состояние автомата.
Доказательство. Пусть / — некоторая булева функция из множества 2( )\{0,1}. Поскольку / = 0,1, то существует такое і, 1 і 2П, что верны равенства: f(pn) = 1 и /(5j-i) = 0, где мы считаем OLQ равным 5?2«. Построим последовательность подаваемых наборов С, такую, что автомат Vau с последо вательностью С реализует функцию /. Первым набором последовательности С является набор дц-\. Затем идут все наборы, на которых / принимает значе ние 1, кроме набора дц. Потом идет набор дц. Затем подаются все наборы, на которых функция / принимает значение 0, кроме набора дц-\. Автомат Vau с такой последовательностью подаваемых наборов С реализует функцию /. Утверждение доказано. И Из утверждений 3.4.5 и 3.4.6 можно извлечь следующие следствия. Следствие 3.4.5. Для любого п 1 и любого к 1 верно неравенство Pk(n) 22 - 2. Следствие 3.4.6. Для любого п 1 и любого т 2п + 2 вернорт(п) = 22-2.
В диссертации введены понятия автоматного замыкания и обобщенного замыкания множества булевых функций. Показано, что обобщенные формулы являются в выразительном плане ослабленным вариантом автоматных формул. Получено описание всех автоматно замкнутых классов булевых функций. Исследована проблема реализации булевых функций обобщенными формулами специального вида, а именно, обобщенными «-формулами (то есть такими формулами, в которых каждая подформула имеет не более одной подформулы, отличной от символа переменной). Для замкнутых классов То, Ті и ТоТі найдены конечные системы булевых функций, полные в классе обобщенных а-формул. Показано, что для этих систем автоматное замыкание совпадает с замыканием в классе обобщенных формул.
Исследован частный случай операции автоматного замыкания с точки зрения «выразительной силы» этой операции: рассмотрена задача о реализации булевых функций от п переменных булевыми автоматами с константными состояниями и с п входами, то есть такими автоматами с входным и выходным алфавитами {0,1}, у которых в каждом состоянии функция выхода — это одна из функций 0(жі, #2,..., хп) или 1(жі, Х2, хп), при условии возможности произвольного порядка подачи наборов значений входных переменных на входы автомата. Получено точное значение максимальной мощности множества булевых функций, которые могут быть реализованы одним инициальным булевым автоматом с двумя или тремя константными состояниями. Получена точная оценка максимального числа булевых функций от п фиксированных переменных, реализуемых инициальным булевым автоматом с произвольным количеством константных состояний, где п 1.
В то же время, изучение выразительной силы обобщенных формул произвольного вида остается открытым для дальнейших исследований. Перспективной для дальнейших исследований представляется задача об описании автоматно замкнутых и обобщенно замкнутых классов функций многозначной логики.
Также следует отметить ряд нерешенных задач, связанных с изучением свойств универсальных и квазиуниверсальных автоматов: получение оценок мощности множеств функций, реализуемых одним автоматом с произвольным числом константных состояний, описание квазиуниверсальных автоматов с произвольным числом состояний, оценка минимального числа состояний автомата, реализующего максимально возможное число (22-2) булевых функций. Кроме того, представляет интерес решение аналогичных задач для автоматов, в состояниях которых реализуются булевы функции, отличные от констант.