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

Булев куб, или Булеан:
Уникальная комбинаторная конструкция и её приложения №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], некоторые утверждения и доказательства публикуются впервые.

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


Об авторе
Гашков Сергей Борисович
Доктор физико-математических наук, профессор. Профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова. Автор и соавтор книг "Примени математику", "Арифметика. Алгоритмы. Сложность вычислений", "Системы счисления и их применения", "Современная элементарная алгебра", "Элементарное введение в эллиптическую криптографию" (М.: URSS; в 2 кн.), "Криптографические методы защиты информации", "Занимательная компьютерная арифметика" (М.: URSS; в 2 кн.), "Геометрические неравенства: Путеводитель в задачах и теоремах" (М.: URSS), "Алгоритмические основы эллиптической криптографии", "Дискретная математика: Учебник и практикум для академического бакалавриата"; "Обыкновенные дроби: От Древнего Египта до наших дней" (М.: URSS), "Булев куб, или булеан: Уникальная комбинаторная конструкция и ее приложения" (М.: URSS).