Слабоповторные булевы функции в предэлементарных базисах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

! На правах рукописи

Шаранхаев Иван Константинович

Слабоповторные булевы функции в предэлементарных базисах

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск - 2003

Работа выполнена на кафедре дискретной математики и информатики Иркутского государственного университета

Научный руководитель:

доктор физико-математических наук, профессор H.A. Перязев.

Официальные оппоненты:

доктор физико-математических наук, профессор Ю.Д. Корольков;

кандидат физико-математических наук А.И. Гайдуков.

Ведущая организация:

Красноярский государственный университет.

Защита состоится 10 октября 2003 г. в 14 часов на заседании диссертационного совета Д 212.074.01 в Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (бульвар Гагарина, 24).

Автореферат разослан 1 сентября 2003 г.

Ученый секретарь л диссертационного совета, уЛу/ю&Г'----'

к.ф.-м.н., доцент / М.А. Аргучинцева.

<3

Общая характеристика работы

Актуальность темы. Теория дискретных функций образует одно из главных направлений исследований в дискретной математике. Простейшим и в то же время важнейшим классом таких функций является класс булевых функций. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций, которое в теории булевых функций называют термальным или формульным.

Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств. Поэтому неудивителен интерес, проявляемый к термальным представлениям. Существенным в изучении таких представлений явился результат Э. Поста 1 об описании всех порожденных с помощью суперпозиции классов булевых функций, так называемых замкнутых классов булевых функций.

Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. Основной результат в этом направлении принадлежит О. Б. Лу-панову 2 . Им была получена асимптотическая оценка сложности термальных представлений булевых функций над произвольными полными базисами, согласно которой почти все булевы функции имеют сложность 2"/log п. Однако следует отметить, что несмотря на это, все известные до сих пор эффективно задаваемые последовательности булевых функций имеют лишь полиномиальные оценки сложности.

При изучении вопросов сложности представлений булевых функций термами возникают такие понятия как бесповторность и сла-боповторность булевых функций. Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается не более одного раза, изу-

1 Post Е. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — Vol. 43, № 4. - P. 163-185. Post E. L. Two - valued iterative systema of mathematical logic / E. L. Post // Annals of Math. Studies. — 1941. — № 5.

2 Лупанов О. Б. О сложности реализаций функций алгебры логики формулами / О. В. Лупанов // Проблемы кибернетики. — М.: Физматгиз, 1960. — Вып. 3. — С. 61-80. Лупанов О. Б. Асимптотические оценки сложности управляющих систем / О. В. Лупанов. — М.: Изд-во Моск. ун-та, 1984. — 137 с.

! ' л H -Ч •« ЛЬ JГЕКА

чались еще с 50-х годов прошлого века, когда в работе А. В. Кузнецова 3 было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Повторные булевы функции в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В, называются слабоповторными в базисе В. Из результата Н. А. Перязева 4 следует, что все неразделимые булевы функции есть слабоповторные функции в некотором базисе.

Кроме того, добавление к базису бесповторной в нем функции не улучшает его в смысле сложности представлений функций термами, а слабоповторной делает улучшение базиса минимальным, что позволяет эффективно сравнивать базисы по сложности термальных представлений 5. Отметим также, что такое расширение базиса существенно увеличивает число бесповторных булевых функций 6.

Полное описание слабоповторных функций над некоторым базисом может быть полезным при исследовании свойств данного базиса. Например, существует метод 7, использующий описание слабоповторных функций, который позволяет достаточно легко доказывать критерии бесповторности для произвольных базисов.

Изучение слабоповторных булевых функций в различных бази-

3Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики / А. В. Кузнецов // Труды Математического института им. В. А. Стеклова. — М.: Изд-во АН СССР, 1958. — Т. 51. — С. 186225.

4Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах / Н. А. Перязев // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1995. — 15 с.

5Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами / Б. А. Субботовская // Докл. АН СССР. — 1963. — Т. 149, № 4. — С. 784-787. Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов / Д. Ю. Черухин // Математические вопросы кибернетики. — 1999. -Вып. 8. - С. 77-122.

®Зубков О. В. Соотношение количества бесповторных булевых функций в различных базисах / О. В. Зубков // Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. - С. 61-66.

7Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах / К. Д. Кириченко // Оптимизация, управление, интеллект. — Иркутск, 2000. - Вып. 4. — С. 93-101.

с ах позволяет создать кяассификацию нера ^де жмых булевых функций, которая может быть использована как в 1 еоретических, так и в практических целях.

Цели работы:

• изучение свойств бесповторных и слабоповторных булевых функций в предэлементарных базисах;

• получение полного описания слабоповторных булевых функций в серии предэлементарных немонотонных базисов;

• получение полного описания слабоповторных булевых функций в предэлементарных парасимметрических базисах.

Методы исследований. В диссертации используются методы теории булевых функций и комбинаторики.

Научная новизна. По отмеченным выше проблемам получены следующие результаты:

• доказан ряд новых свойств бесповторных булевых функций в предэлементарных базисах;

• получено полное описание слабоповторных булевых функций в серии предэлементарных немонотонных базисов;

• получено полное описание слабоповторных булевых функций в предэлементарном парасимметрическом базисе порядка 5;

• получено полное описание слабоповторных булевых функций в предэлементарном парасимметрическом базисе порядка 4.

Таким образом, завершено описание слабоповторных булевых функций во всех предэлементарных базисах.

Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Полученные в диссертации результаты имеют теоретическое значение для теории булевых функций. Полученные результаты могут применяться при исследовании проблем сравнения базисов по сложности представлений булевых функций термами, при получении критериев бесповторно-сти в некоторых базисах.

Апробация работы. Результаты диссертации были представлены на XII Байкальской международной конференции "Методы оптимизации и их приложения"(Иркутск, 2001), XIII Международной конференции "Проблемы теоретической кибернетики" (Казань, 2002), IV Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002), II Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), а также неоднократно докладывались на семинарах Иркутского государственного университета и Иркутского государственного педагогического университета.

Публикации. По теме диссертации опубликовано 6 научных работ [1-6], отражающих основное содержание диссертации.

Структура и объем работы. Диссертация изложена на 134 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 55 наименований, включая работы диссертанта.

Содержание работы

Во введении дается обоснование актуальности темы исследований.

В первой главе определяются основные понятия и терминология, принятая при изложении результатов (первый параграф), а также делается обзор основных результатов по проблемам, рассматриваемым в диссертации, в том числе полученных автором (второй параграф).

Учитывая, что терминология в теории булевых функций не является устоявшейся, приведем несколько определений, необходимых для дальнейшего изложения.

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

Функция / называется бесповторной в базисе В, если ее можно представить в этом базисе термом, в котором каждая переменная встречается не более одного раза. В противном случае / называется повторной в В.

Функция / называется слабоповторной в базисе В, если любая остаточная подфункция функции / является бесповторной, а сама / повторна в базисе В.

Базис {0,1, V, —} будем называть элементарным и обозначать Во; а. базис {0,1,ф, •, V, —} полным бинарным базисом и обозначать

Всякий базис В0 и {<?}, где д - слабоповторная в В0, будем называть предэлементарным.

Всякий базис Во1){д}, где д = х 1 . .-хпУх1 ■.. ,-хп для п > 2 будем называть предэлементарным симметрическим базисом порядка п.

Всякий базис Во и {<?}, где д = £1(3:2 V ... V хп) V Хг ■ ... • хп для п > 3 будем называть предэлементарным монотонным базисом порядка п.

Всякий базис где д = ^(хгУжз-.. .-агп) •• • • ДЛЯ

п > 3 будем называть предэлементарным немонотонным базисом порядка 7г.

Базис В0и{5}, где д = х\(х24X3)^X3X4 будем называть предэлементарным парасимметрическим базисом порядка 4.

Базис Вои{д}, где д = Х\{х2УхзхА)\/хь{хз\/Х2Хз) будем называть предэлементарным парасимметрическим базисом порядка 5.

Введем обозначение

В1.

{

х, если а — О, х, если <т = 1.

и > •

гдр (?'ь... , гп) •- некоторая перестановка чис<м от 1 до п.

Функции / и д называются обоб1це.пно однотипными, если / однотипна к д или д. Очевидно, что отношения однотипности и обобщенной однотипности являются отношениями эквивалентности.

Вторая глава диссертации посвящена описанию слабоповторных булевых функций в предэлементарных немонотонных базисах.

Первым шагом в описании слабоповторных функций над конкретными базисами был результат, полученный В.А.Стеценко, об описании всех обобщенных типов функций, слабоповторных в базисе

Теорема 8 Следующая система булевых функций является полной системой представителей классов эквивалентности по отношению обобщенной однотипности для булевых функций, слабоповторных в элементарном базисе Во■

Для одного из предэлементарных симметрических базисов, а именно для базиса В\, описание слабоповторных функций было получено Н. А. Перязевым 9.

Затем К. Д. Кириченко 10 дал описание слабоповторных булевых функций в предэлементарных симметрических и монотонных базисах.

В третьем параграфе доказывается ряд вспомогательных утверждений, которые используются при дальнейшем изложении. Приведены свойства бесповторных булевых функций в предэлементарных базисах.

8Стеценко В. А. О предплохих базисах в Р? / В. А. Стеценко // Математические вопросы кибернетики. — 1992. —Вып. 4. — С. 139-177.

9Перязев Н. А. Слабоповторные булевы функции в бинарном базисе / Н. А. Перязев // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 4. — Иркутск, 1998. — 12 с.

10Кириченко К. Д. Слабоповторные булевы функции в некоторых предэлементарных базисах / К. Д. Кириченко // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 13. — Иркутск, 2000. — 60 с.

В0.

хх(х2 V х3) V Х3Х4;

х!(х2 V Х3Х4) V £5(2:3 Ух2Х4);

(®2 V .. . V Хп) V ®2 • - ■ • • ®П> Х1(Х2 V х3 •... • хп) V х2 ■ Х3 ■. II •...■!„ V®!

П > 3; * ^ ^

п > 2.

В четвертом параграфе получено полное описание слабоповторных булевых функций в серии предэлементарных немонотонных базисов.

Теорема 1. Следующая система булевых функций является полной системой представителей классов эквивалентности по отношению обобщенной однотипности для функций, слабоповторных в предэлементарном немонотонном базисе В = Вои{#}, где функция д(хгхп) = XI (х2 V ... V хп) V х2$з ■... • хп и п > 3:

хх(х2 V х3) V ж3х4;

х\ (х2 V 2:30:4) V х5(х3 V 0:22:4);

£1(2:2 V ... V хк) V х2 •... • Хк, А: > 3;

хг(х2Ч х3 ■... ■ Хк)У х2 ■ х3 ■... ■ хк, к > 3, к ф га;

Х\ •... • хк V XI ■... ■ хк, к> 2;

£1д(х2,... ,£„+1) Уо^яг^з Vx4 ■... ■ хп+1); х\д{х2,..., жп+1) V хх х2х3;

х1д(х2,х3,х4) V х1д(х2,х3,х4), при п - 3;

х\д{х2, хз,х4) У х\х2Х3Х1, при п = 3;

х1х2д(хз,х4,х5,хб)у хг(х2\/х4)хзх5х6, при п = 4; х1х2д(хз,х4,хц,хе) V хх(х4 V (х2х3 V при п = 4.

Третья глава диссертации посвящена описанию слабоповторных булевых функций в предэлементарных парасимметрических базисах. Результаты этой главы завершают описание слабоповторных булевых функций во всех предэлементарных базисах.

В пятом параграфе получено полное описание слабоповторных булевых функций в предэлементарном парасимметрическом базисе порядка 5.

Теорема 2. Следующая система булевых функций является полной системой представителей классов эквивалентности по отношению обобщенной однотипности для функций, слабоповторных в предэлементарном парасимметрическом базисе В = Во1){д}, где д(х 1,х2,хз,х4,х5) - хх{х2 V Х3Х4) V х5(хз V х2х4):

Х1_{Х2У х3)У хзх4-,

хх{х2 V ... Vхп) V х2 •... • хп, п > 3;

£1(2:2 V 2:3 •... • хп) V х2 ■ х3 ■... -хп, п> 3;

XI ■... ■ хп V XI •... - х„, п> 2;

х\д{х2, х3) Х4, х5,х6) Ух1х5(х2х4 V х3х6);

Х1х2д{хз,х4,х5,х6,х7) V £1(2:4 V х5(х6Ух7(х2 V £3))).

В шестом параграфе получено полное описание слабоповторных булевых функций в предэлементарном иарасимметрическом базисе порядка 4.

Теорема 3. Следующая система булевых функций является полной системой представителей классов эквивалентности по отношению обобщенной однотипности для функций, слабоповторных в предэлементарном иарасимметрическом базисе В = Вой {д}, где д(х!,х2,хз,я4) = хх{х2 Ух3)Ух3х4:

Х1{Х2УХ3Х4) Ух5(х3 Увд); £1(^2 V ... V хп) V Х2 ■... • хп, тг > 3;

хх(х2 Vх3 ■... •хп) У Х2 -х3 ■... -хп, П> 3;

Хг ■... ■ хп V х% •... • хп, п > 2;

х1д(х2,х3,х4,х5) Vхгд(х3,х2,х5,х4); х1д(х2,х3,х4,х5)\/х1х3х5(х2 Ух4)\ Х1д{х2,х3,хА,хь) V хх(х2х3 V х4х5); Х19{Х2, Х3, Х4, Х5) V Х1Х3(Х2 V х4х5); х1х2д(хз,х4,х5,х6) V х!д(х2х3,х4,х5,х6).

Основные результаты диссертации

На защиту выносятся следующие результаты.

1. Получено полное описание слабоповторных булевых функций в серии предэлементарных немонотонных базисов.

2. Получено полное описание слабоповторных булевых функций в иарасимметрическом базисе порядка 5.

3. Получено полное описание слабоповторных булевых функций в иарасимметрическом базисе порядка 4.

Работы автора по теме диссертации

[1] Шаранхаев И. К. Слабоповторные булевы функции в одном предэлементарном базисе / И. К. Шаранхаев // Труды ХП Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 151-155.

|2] Шаранхаев И. К. О слабоповторных булевых функциях / И. К. Шаранхаев / / XIII Международная конференция по проблемам теоретической кибернетики. Тезисы докл. — Казань, 2002. — Часть 2. - С. 195.

[3] Шаранхаев И. К. О слабоповторных булевых функциях в одном базисе / И. К. Шаранхаев // Материалы конференции «Дискретный анализ и исследование операций». — Новосибирск,

2002. - С. 139.

[4] Шаранхаев И. К. Слабоповторные булевы функции в предэле-ментарных немонотонных базисах / И. К. Шаранхаев // Труды Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. — Иркутск,

2003. - С. 87-90.

[5] Шаранхаев И. К. О слабоповторных булевых функциях в одном предэлементарном базисе / И. К. Шаранхаев // Дискретный анализ и исследование операций. — 2003. — Серия 1. — Т. 10, № 2. - С. 79-101.

[6] Шаранхаев И. К. Слабоповторные булевы функции в некоторых базисах / И. К. Шаранхаев // Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 17. — Иркутск, 2003. - 64 с.

Редакционно-издательский отдел ''//. Иркутского государственного университета Лицензия ЛР N020592 от 9.07.97г. 664000, Иркутск, бульвар Гагарина, 36

Подписано в печать 15/08/2003 г. Формат бумаги 60x84 1/16. Объем 0,7 п.л. Заказ 10. Тираж 100 экз.

Отпечатано в ОКИС ЦНИТ ИГУ 664003, Иркутск, б. Гагарина, 20

* 13436

Введение

Глава 1. Основные понятия и результаты

§ 1. Основные понятия и терминология.

§ 2. Обзор результатов по слабоповторным и бесповторным булевым функциям.

Глава 2. Слабоповторные булевы функции в предэлементар-ных немонотонных базисах

§ 3. Свойства бесповторных булевых функций в предэлементарных базисах.

§ 4. Слабоповторные булевы функции в серии предэлементарных немонотонных базисов.

Глава 3. Слабоповторные булевы функции в предэлементар-ных парасимметрических базисах

§ 5. Слабо повторные булевы функции в предэлементарном парасимметрическом базисе порядка 5.

§ 6. Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 4.

Теория дискретных функций образует одно из главных направлений исследований в дискретной математике. Простейшим и в то же время важнейшим классом таких функций является класс булевых функций. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций, которое в теории булевых функций называют термальным или формульным.

Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств [6, 7, 46, 47]. Поэтому неудивителен интерес, проявляемый к термальным представлениям [1, 16, 27, 36, 37, 39]. Существенным в изучении таких представлений явился результат Э. Поста об описании всех порожденных с помощью суперпозиции классов булевых функций, так называемых замкнутых классов булевых функций [43, 44]. Первоначальное доказательство этого результата было упрощено и изложено в более доступной форме [19, 20, 38].

Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. С одной стороны, имеем асимптотическую оценку сложности термальных представлений булевых функций над произвольными полными базисами. О. Б. Лупановым доказано [18], что почти все булевы функции имеют сложность 2n/log п. С другой стороны, при получении эффективных нижних оценок сложности возникают определенные трудности [17, 33, 49]. На сегодняшний день все известные эффективно заданные последовательности булевых функций имеют лишь полиномиальные оценки сложности [3, 21, 31, 32, 40, 41, 42, 45]. Таким образом, можно сказать, что исследования в этом направлении еще далеки от завершающей стадии.

При изучении вопросов сложности представлений булевых функций термами возникают такие понятия как бесповторность и слабоповтор-ность булевых функций. Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается не более одного раза, изучались еще с 50-х годов прошлого века, когда в работе А. В. Кузнецова [15] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Повторные булевы функции в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В, называются слабоповторными в базисе В. Из результата Н. А. Перязева [25] следует, что все неразделимые булевы функции есть слабоповторные функции в некотором базисе.

Кроме того, добавление к базису бесповторной в нем функции не улучшает его в смысле сложности представлений функций термами, а слабоповторной делает улучшение базиса минимальным, что позволяет эффективно сравнивать базисы по сложности термальных представлений [35]. Отметим также, что такое расширение базиса существенно увеличивает число бесповторных булевых функций [10].

Бесповторные булевы функции интересны как функции наименьшей сложности, и это прекрасно объясняет тот факт, что при проектировании микропроцессоров используются в большей части бесповторные функции в базисе из конъюнкции, дизъюнкции и отрицания [4]. Важность изучения бесповторных функций подтверждает и указанный выше результат А. В. Кузнецова, из которого следует, что по многим вопросам изучение всех булевых функций сводится к изучению неразделимых функций.

Полное описание слабоповторных функций над некоторым базисом может быть полезным при исследовании свойств данного базиса. Например, в работе К. Д. Кириченко [И] описан метод, использующий описание слабоповторных функций, который позволяет достаточно легко доказывать критерии бесповторности для произвольных базисов.

Изучение слабоповторных булевых функций в различных базисах позволяет создать классификацию неразделимых булевых функций, которая может быть использована как в теоретических, так и в практических целях.

О. Б. Лупановым замечено (результат сформулирован в [30]), что элементарный базис bq ={V, —,0,1} является самым плохим по сложности реализаций функций термами. Слабоповторные булевы функции в этом базисе в терминах обобщенной однотипности были найдены В. А. Стеценко, им же было доказано, что предплохие базисы имеют следующий вид 5oU {/}, где / - слабоповторная функция в Во [28, 29, 48]. В обратную сторону это утверждение доказано Д. Ю. Черухиным [34]. Таким образом, все базисы, описанные В. А. Стеценко, являются предэле-ментарными.

Следующий шаг в этом направлении был сделан Н.А. Перязевым [26], описавшим слабоповторные булевы функции в предэлементарном базисе В\ ={©, V, •, —, 0,1}. Затем К. Д. Кириченко дал описание всех слабоповторных булевых функций для двух серий предэлементарных базисов [13].

Во второй и третьей главах данной диссертации автор завершает описание слабоповторных булевых функций в предэлементарных базисах, рассмотрев парасимметрические и серию немонотонных базисов, тем самым поставив точку в описании базисов, непосредственно предшествующих предэлементарным.

Диссертация состоит из введения, трех глав, разбитых на 6 параграфов, заключения и списка литературы.

Заключение

На защиту выносятся следующие результаты.

1. Получено полное описание слабоповторных булевых функций в серии предэлементарных немонотонных базисов.

2. Получено полное описание слабоповторных булевых функций в ria-расимметрическом базисе порядка 5.

3. Получено полное описание слабоповторных булевых функций в па-расимметрическом базисе порядка 4.

Автор выражает искреннюю благодарность своему научному руководителю Н.А. Перязеву, а также всем участникам семинара «Дискретная математика и математическая информатика».

1. Дискретная математика и математические вопросы кибернетики, ■f» Под редакцией Яблонского С. В. и Лупанова О. Б. — М.: Наука,1974, Т. 1. - 312 с.

2. Избранные вопросы теории булевых функций / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков, О. В. Зубков, К. Д. Кириченко, В. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева; Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

3. Андреев А. Е. Об одном методе получения более чем квадратичных оценок сложности тг схем / А. Е. Андреев // Вестник МГУ, — 1987. - Серия 1. - Матем. Мех. - №1. - С. 70-73.

4. Артюхов В. Л., Копейкин В. Л., Шалыто А. А. Настраиваемые модули для управляющих логических устройств / В. Л. Артюхов, В. Л.

5. Копейкин, А. А. Шалыто. —Ленинград: Энергоиздат, 1981. — 166 с.

6. Бохманн Д., Постхоф X. Двоичные динамические системы / Д. Бох-манн, X. Постхоф. — М.: Энергоатомиздат, 1986. — 401 с.

7. Глушков В. И. Введение в кибернетику / В. И. Глушков. — Киев: Изд-во АН УССР, 1964. 324 с.

8. Глушков Р. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств / Р. М. Глушков, Ю. В. Капитонова, А. Т. Мищенко. — Киев: Наукова думка, 1987. — 264 с.

9. Гурвич В. А. О бесповторных булевых функциях / В. А. Гурвич // Успехи мат. наук. 1977. - Т. 32, № 1. - С. 183-184.

10. Гурвич В. А. Критерий бесповторности функций алгебры логики / В. А. Гурвич // Докл. АН СССР. 1991. - Т. 318, № 3. - С. 532-537.ч

11. Зубков О. В. Соотношение количества бесповторных булевых функций в различных базисах / О. В. Зубков // Дискретная математика:

12. Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 61-66.

13. Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах / К. Д. Кириченко // Оптимизация, управление, интеллект. — Иркутск, 2000. — Вып 4. — С. 93-101.

14. Кириченко К. Д. Критерий бесповторности функции алгебры логики в бинарном базисе / К. Д. Кириченко // Международная конференция "Логика и приложения". — Новосибирск, 2000. — С. 57-58.

15. К. Д. Кириченко Слабоповторные булевы функции в некоторых предэлементарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 13. — Иркутск, 2000. — 60 с.

16. Кириченко К. Д. Слабоповторные булевы функции в небинарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 14. — Иркутск, 2000. — 20 с.

17. Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики / А. В. Кузнецов // Труды Математического института им. В. А. Стеклова. — М.: Изд-во АН СССР, 1958. Т. 51. - С. 186-225.

18. Лупанов О. Б. О сложности реализаций функций алгебры логики формулами / О. Б. Лупанов // Проблемы кибернетики. Вып. 3. — М.: Физматгиз, 1960. С. 61-80.

19. Лупанов О. Б. О методах получения оценок сложности и вычисления индивидуальных функций / О. Б. Лупанов // Дискретный анализ. Вып. 25. Новосибирск, 1974. — С. 3-18.

20. Лупанов О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. — М.: Изд-во Моск. ун-та, 1984.

21. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций / С. С. Марченков, А. Б. Угольников. — М.: Изд-во ИПМ АН СССР, 19900. 147 с.

22. Марченков С. С. Замкнутые классы булевых функций / С. С. Марченков. — М.: Физматлит, 2000. — 128 с.

23. Нигматуллин Р. Г. Сложность булевых функций / Р. Г. Нигматул-лин. М.: Наука, 1991. — 240 с.

24. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Фундаментальные проблемы математики и механики. Математика. — М.: Изд-во МГУ, 1994. — С. 320.

25. Перязев Н. А. Реализация булевых функций бесповторными формулами в некоторых базисах / Н. А. Перязев // Сб. Алгебра, логика и приложения. — Иркутск, 1994. — С. 143-154.

26. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Дискретная математика. — 1995. — Т. 7. — № 3. С. 61-68.

27. Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1995. — 15 с.

28. Перязев Н. А. Слабоповторные булевы функции в бинарном базисе / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 4. — Иркутск, 1998. — 12 с.

29. Перязев Н. А. Основы теории булевых функций / Н. А. Перязев. — М.: Физматлит, 1999. — 112 с.

30. Стеценко В. А. Об одном необходимом признаке для предмакси-мальных базисов в Р2 / В. А. Стеценко // Докл. АН СССР. — 1990. — Т. 315. С. 1304-1307.

31. Стеценко В. А. О предплохих базисах в Р2 / В. А. Стеценко // Математические вопросы кибернетики. — 1992. —Вып. 4. — С. 139— 177.

32. Р 30. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами / Б. А. Субботовская // Докл. АН СССР. 1963. - Т. 149, № 4. - С. 784-787.

33. Храпченко В. М. О сложности реализации линейной функции в классе 7г схем / В. М. Храпченко // Математические заметки. —1971. Т. 9, № 1. - С. 35-40.

34. Храпченко В. М. О сложности реализации симметрических функций формулами / В. М. Храпченко // Математические заметки. —1972. Т. 11, № 1. - С. 109-120.

35. Храпченко В. М. Нижние оценки сложности схем из функциональных элементов / В. М. Храпченко // Кибернетич. сб. Новая серия.1' Вып. 21. М.: Мир, 1984. - С. 3-54.

36. Черухин Д. Ю. О предплохих булевых базисах / Д. Ю. Черухин // Дискретная математика. 1999. - Т. 11. - № 4. — С. 118-160.

37. Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов / Д. Ю. Черухин // Математические вопросы кибернетики. — 1999. -Вып. 8. С. 77-122.

38. Шеннон К. Э. Работы по теории информации и кибернетике / К. Э. Шеннон. М.: ИЛ., 1963. - 829 с.

39. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов. / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

40. Fischer М., Meyer A. R., Paterson М. S. О(nlogn) lower bounds on length of Boolean formulas / M. Fischer, A. R. Meyer, M. S. Paterson // SIAM J. Comput. — 1962. — V. 11. —No 3. — P. 416-427.

41. Fischer M., Meyer A. R., Paterson M. S. Lower bounds on the size of Boolean formulas, preliminary report / M. Fischer, A. R. Meyer, M. S. Paterson // Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque. — 1975. — P. 37-44.

42. Hodes L., Specker E. Lengths of formulas and elimination of quantifiers / L. Hodes, E. Specker // Contributions to mathematical logic. — Amsterdam, 1968. — P. 175-188.

43. Post E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — V. 43. —No 4. — P. 163185.

44. Post E. L. Two valued iterative systema of mathematical logic / E. L. Post // Annals of Math. Studies. - 1941. —No 5.

45. Pudlak P. Bounds for Hodes Specker theorem / P. Pudlak // Lecture Notes in Computer Science 171, Springer - Verlag. — 1984. — P. 421— 445.

46. Shannon С. E. A symbolic analysis of relay and switching circuits / С. E. Shannon // Trans. AIEE. — 1938. — V. 57. P. 713-723.

47. Shannon С. E. The synthesis of two terminal switching circuits / С. E. Shannon // Bell. System. Techn. J. — 1949. — V. 28. — P. 5998.

48. Stetsenko V. On almost bad Boolean bases / V. Stetsenko // Theoretical Computer Science. — 1994. — V. 136. — P. 419-469.

49. Wegener I. The Complexity of Boolean function / I. Wegener // Wiley Teubner Series in Computer Science, Wiley - Teubner. — 1987.

50. Работы автора по теме диссертации

51. Шаранхаев И. К. Слабоповторные булевы функции в одном предэле-ментарном базисе / И. К. Шаранхаев // Дискретная математика: Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 151-155.

52. Шаранхаев И. К. О слабоповторных булевых функциях / И. К. Шаранхаев // XIII Международная конференция по проблемам теоретической кибернетики. Тезисы докл. — Казань, 2002. — Часть 2. — С. 195.

53. Шаранхаев И. К. О слабоповторных булевых функциях в одном базисе / И. К. Шаранхаев // Материалы конференции «Дискретный анализ и исследование операций». — Новосибирск, 2002. — С. 139.

54. Шаранхаев И. К. Слабоповторные булевы функции в предэле-ментарных немонотонных базисах / И. К. Шаранхаев // Труды Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. — Иркутск, 2003. — С. 87-90.

55. Шаранхаев И. К. О слабоповторных булевых функциях в одном предэлементарном базисе / И. К. Шаранхаев // Дискретный анализ и исследование операций. — Новосибирск, 2003. — Серия 1. — Т. 10. — № 2. С. 79-101.

56. Шаранхаев И. К. Слабоповторные булевы функции в некоторых базисах / И. К. Шаранхаев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 17. — Иркутск, 2003. — 64 с.