Гашков С.Б. Булев куб, или Булеан:
Уникальная комбинаторная конструкция и её приложения. №261

---

Предисловие				4
Глава 1. Булеан и комбинаторика				7
1.1. Многомерный куб и его портреты				7
1.2. Булев куб и тождества с биномиальными коэффициентами				11
1.3. О множествах и операциях над ними				18
1.4. Разные лики булева куба. Куб как частично упорядоченное множество				22
1.4.1. Семейство Шпернера				23
1.4.2. Цепи Анселя				26
1.4.3. Куб как новогодняя елка				30
1.5. Куб как граф				33
1.5.1. Гамильтоновы циклы на кубе и коды Грея				39
1.5.2. Циклы де Бреeйна				42
1.6. Куб как группа и линейное пространство				43
1.7. Кубы, дизайны и разностные множества				52
1.8. Куб как метрическое пространство				57
1.8.1. Разбиение куба на шары и сферы				57
1.8.2. Навигация в булевом кубе: поиск вершины по расстояниям до данных вершин				58
1.9. Булев куб в поисках фальшивых монет				61
1.10. Булев куб и коммуникационная сложность				67
1.10.1. (n-[log2 n]+2)-битный 2-раундовый протокол, с помощью которого Алиса узнает позицию, различающую ее набор от набора Боба				68
1.10.2. (n+2)-битный 3-раундовый протокол, в котором обе стороны определяют позицию, различающую их наборы				69
1.11. Изопериметрическая задача в булевом кубе				70
1.11.1. Расстояния между подмножествами булева куба				78
1.12. Движения булева куба				80
1.13. Протыкающие множества граней куба				83
1.14. Куб как булева алгебра и булево кольцо				90
1.14.1. Куб как поле				96
1.15. Частично упорядоченные множества и диаграммы Хассе				97
1.16. Еще несколько теорем о семействах конечных множеств				105
1.17. Булеан, множества Сидона и дизъюнктные коды				109
1.18. Проблема Турана				114
1.18.1. Тройки Штейнера				116
1.19. Булев куб как булева решетка				121
Глава 2. Булеан и булевы функции				126
2.1. Булевы функции и дизъюнктивные нормальные формы				126
2.2. Карты Карно				128
2.2.1. Булевы кубы против карт Карно				136
2.3. Алгоритм построения сокращенной ДНФ				137
2.4. Минимальные, кратчайшие и тупиковые ДНФ				141
2.5. Максимальная длина сокращенной ДНФ у функции n переменных				146
2.6. Монотонные функции и монотонные ДНФ				154
2.7. Пример функции с большим числом тупиковых ДНФ				161
2.8. Локальные алгоритмы упрощения ДНФ				164
2.9. Змея в ящике				168
2.10. Градиентный алгоритм построения минимальной ДНФ				171
2.10.1. Задача на покрытие и градиентный алгоритм ее решения				172
2.11. Многочлены Жегалкина				176
2.12. Веса булевых функций и расстояния между ними				182
2.13. Булевы функции и их подфункции				191
2.14. Операция суперпозиции и замкнутые классы				199
2.14.1. Класс линейных функций				202
2.14.2. Класс монотонных функций				208
2.14.3. Класс самодвойственных функций				211
2.14.4. Классы сохранения констант				213
2.15. Эквивалентные преобразования формул				215
2.16. Контактные схемы				218
2.17. Разделительное контактное дерево				218
2.17.1. Неразделительная схема Лупанова				221
2.18. Метод Шеннона реализации булевых функций контактными схемами				222
2.19. Метод каскадов				226
2.20. Самокорректирующиеся схемы				229
2.21. Параллельно-последовательные контактные схемы				231
2.21.1. Нижние оценки сложности. Метод Храпченко				232
2.22. Нижние оценки сложности реализации булевых функций контактными схемами				237
2.23. Схемы из функциональных элементов				242
2.23.1. Схемная реализация сумматора однобитных чисел				244
2.24. Булевы функции, схемы и формулы				250
2.24.1. Интересные свойства мультиплексорной функции				253
2.24.2. Формулы для функций с малым числом единиц				257
2.24.3. Отступление об аддитивных цепочках				260
2.24.4. Схемы для симметрических функций				261
2.24.5. Инверсионная сложность булевых функций				275
2.25. Мультиплеры				278
2.26. Сложность перестановок				290
2.27. Тупиковые и минимальные тесты для таблиц и схем				299
2.27.1. Алгоритм построения тестов				303
2.27.2. Диагностические тесты для контактных схем				306
2.28. Эквивалентные преобразования контактных схем				308
Глава 3. Кубы и коды				316
3.1. Несколько олимпиадных задач				316
3.2. Что такое коды?				319
3.2.1. Границы для кодов с большими расстояниями				322
3.2.2. Матрицы Адамара				324
3.2.3. Эквидистантные и равновесные коды				326
3.3. Простейший пример кода, исправляющего одну ошибку				328
3.4. Коды Хемминга				334
3.4.1. q-ичные коды Хемминга				335
3.5. Коды Рида—Маллера				336
Литература				342

---

Булев куб (более точно: двоичный многомерный куб) — главное действующее лицо в этой книге — это имеющая геометрические корни комбинаторная конструкция, у которой множество применений в различных разделах дискретной математики. Чисто геометрические вопросы, связанные с многомерным кубом, рассматриваться здесь не будут. Интересующегося ими читателя можно отослать к книге [7]. Зато приложениям булева куба (или булеана, как сейчас стало модно называть одну из его ипостасей) к «геометрическим» интерпретациям различных задач из комбинаторики конечных множеств, конструктивной комбинаторики (проектирование так называемых комбинаторных дизайнов, разностных множеств, булевых матриц с различными свойствами и т. д.), перечислительной комбинаторики (доказательство комбинаторных тождеств), теории кодирования, теории графов будет уделено много внимания.

Булев куб связан так или иначе с таким большим количеством задач, что полное и подробное их изложение рискует превратиться в многотомный курс дискретной математики (преподнесенный, конечно, под определенным углом зрения). Например, в этот курс можно включить том, посвященный теории кодирования, в которой почти все разделы имеют связь с булевым кубом. Автор стремился этого избежать, поэтому в книгу были включены только сравнительно простые темы и изложены они на элементарном уровне, насколько это возможно. Например, нигде не используется асимптотическая формула Стирлинга для факториала, вместо нее применяются элементарно доказываемые неравенства. Однако некоторые доказательства достаточно длинны.

Множества вершин булева куба естественно связаны с булевыми функциями (сокращенно б. ф.), т. е. функциям, чьи аргументы и значения равны только нулям и единицам. Названы они в честь британского математика

Джорджа Буля (и впоследствии дали имя и булеву кубу), официальное их длинное название — функции алгебры логики. Конечно, написать книгу о булевом кубе не коснувшись темы булевых функций невозможно. Тема эта обширна, и из нее пришлось выбрать только некоторые вопросы, в основном связанные с комбинаторными свойствами б. ф., в частности, с их реализацией (вычислением) различными типами логических схем.

Много внимания уделяется задаче минимизации так называемых дизъюнктивных нормальных форм (сокращенно ДНФ), т. е. задаче о сложности реализации булевых функций ДНФ, которую можно рассматривать как комбинаторную задачу о нахождении минимального покрытия данного множества вершин куба его подкубами (интервалами). ДовольноПредисловие 7 подробно изучается сложность реализации б. ф. так называемыми контактными схемами, схемами из функциональных элементов и их частным случаем — формулами. Контактные схемы являются математической моделью электрических релейных устройств, независимо предложенной в 30-е годы 20 в. Шенноном (США), Шестаковым (СССР) и Накасимой (Япония). Сейчас релейные схемы нигде не встречаются, их давно заменили сначала тоже громоздкие (но существенно более быстрые) ламповые, потом меньшего размера (и еще более быстрые) транзисторные, а сейчас — миниатюрные микросхемы (чипы) на кремниевых кристаллах (VLSI — сверхбольшие интегральные схемы). Их математической моделью всегда служили и служат сейчас схемы из функциональных элементов, если не вдаваться в устройство отдельных ячеек VLSI, реализующих булевы функции (но для моделирования самих этих ячеек можно использовать контактные схемы). Тем не менее контактные схемы сохранили свой интерес для математики (потому, что значительно отличаются от функциональных схем, хотя и служат той же цели), но на страницы учебников стали попадать реже. Именно поэтому им в этой книге уделяется даже больше внимания, чем функциональным схемам. Например, рассматриваются тонкие вопросы об эквивалентных преобразованиях контактных схем.

Тематика сложности реализации булевых функций обширна, и в книге она излагается с неизбежностью фрагментарно. При этом приводятся не наилучшие известные результаты, а те, которые проще доказать. Желающие познакомиться с ними отсылаются к книгам [19, 24], (к сожалению, обе издавались давно и уже малодоступны для широкого читателя), или к хорошим учебниками дискретной математики (например [32]). Однако нашлось немного места для изложения некоторых вопросов о тестировании логических схем (т. е. об обнаружении и поиске неисправностей в них), которые тоже связаны с булевыми матрицами и булевыми кубами.

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

Значительная часть теории кодирования посвящена как раз таким кодам.

Часто их изучение является естественным следующим шагом после изучения двоичных кодов. Но они связаны уже не булевым, а многозначным кубом. Такое обобщение булева куба существует и даже иногда упоминается и в других разделах книги. Однако его подробное рассмотрение не вписывается в эту книгу, и без того достаточно объемную, поэтому во многих случаях, когда можно было упомянуть о многозначных обобщениях, автор предпочел молчать. Например, не упоминалось обобщение булевых функций — функции многозначной логики и т. д. Одна из причин в том, что полноценных обобщений булева куба и булевой функции, сохраняющих все их хорошие свойства, нет. Все обобщения какие-то из свойств теряют, и приобретают новые, которых не было в двоичном случае. Возникающие при этом задачи часто усложняются и имеют совсем не ана-8 Предисловие логичное решение, как в двоичном случае, а иногда и вовсе не решены.

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

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

В книге много задач, от несложных до довольно трудных, и поэтому она сочетает в себе и учебник (по стилю изложения местами похожий на научно-популярную книгу), и задачник. Часть из них заимствована из известных задачников [6, 14], часть взята из сборников олимпиадных задач (тогда обычно указывается, когда и на какой олимпиаде они были, например ВМО означает — Всесоюзную, а ныне Всероссийскую, IMO — международную олимпиады), иногда по-другому сформулированных, часть представляет из себя известные теоретические факты, которые представлены в форме задач с целью большей компактности изложения, но есть и оригинальные задачи. К большинству задач даны указания, а иногда и полные решения. Сложные задачи отмечены звездочкой, особо сложные — двумя звездочками.

Часть материала основана на [13, 16, 24, 27, 34, 36], некоторые утверждения и доказательства публикуются впервые.

В подготовке книги автор существенно опирался на конспект лекций О. Б. Лупанова «Элементы математической кибернетики».

---