|
Содержание
Предисловие
Булев куб связан так или иначе с таким большим количеством задач, что полное и подробное их изложение рискует превратиться в многотомный курс дискретной математики (преподнесенный, конечно, под определенным углом зрения). Например, в этот курс можно включить том, посвященный теории кодирования, в которой почти все разделы имеют связь с булевым кубом. Автор стремился этого избежать, поэтому в книгу были включены только сравнительно простые темы и изложены они на элементарном уровне, насколько это возможно. Например, нигде не используется асимптотическая формула Стирлинга для факториала, вместо нее применяются элементарно доказываемые неравенства. Однако некоторые доказательства достаточно длинны. Множества вершин булева куба естественно связаны с булевыми функциями (сокращенно б. ф.), т. е. функциям, чьи аргументы и значения равны только нулям и единицам. Названы они в честь британского математика Джорджа Буля (и впоследствии дали имя и булеву кубу), официальное их длинное название — функции алгебры логики. Конечно, написать книгу о булевом кубе не коснувшись темы булевых функций невозможно. Тема эта обширна, и из нее пришлось выбрать только некоторые вопросы, в основном связанные с комбинаторными свойствами б. ф., в частности, с их реализацией (вычислением) различными типами логических схем. Много внимания уделяется задаче минимизации так называемых дизъюнктивных нормальных форм (сокращенно ДНФ), т. е. задаче о сложности реализации булевых функций ДНФ, которую можно рассматривать как комбинаторную задачу о нахождении минимального покрытия данного множества вершин куба его подкубами (интервалами). ДовольноПредисловие 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), «Введение в конструктивную комбинаторику» (URSS), «Элементарная комбинаторика» (URSS).
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||