3.2. Булев куб и его свойства
Булев вектор может применяться для моделирования операций на конечных множествах. Пусть – некоторое универсальное множество в рамках решаемой задачи. Элементы множества для удобства помечены числовыми индексами. Если , то множеству А ставится в соответствие n— мерный булев вектор , в котором , если и в противном случае. Такая строка бит называется характеристическим вектором множества А. При этом, операции на множествах имитируются соответствующими логическими операциями на характеристических векторах. Для размерности n операции над векторами производятся покоординатно. Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение. Между множеством всех подмножеств множества U и булевым кубом , где можно установить взаимнооднозначное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный. Пример. Пусть , и . Характеристическими векторами множеств А, В, , и соответственно будут: . Полученные векторы позволяют легко выписать элементы множеств: . Номером булевого вектора называется число его двоичного представления. Например, булев вектор а из предыдущего примера имеет номер 10101. Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (т.е. они отличаются только одной координатой). Булев куб размерности 1 
Рис. 9 Булев куб размерности 2 
Рис. 10 Булев куб размерности 3 
Рис. 11
3.3. Понятие отношения
- Списком, т.е. перечислением тех пар элементов, для которых это отношение выполнено. Например, если A=a,b,c> и B=x,y>, то R=<(a,x),(a,y),(b,y),(c,x)>.
- Матрицей [R] размерности , элементы которой т.е. строки этой матрицы помечаются элементами из A, а столбцы – элементами из B, а на пересечении строки ai со столбцом bi стоит единица (1), если aRb; и нуль (0), — в противном случае. Тогда для выше приведенного примера имеем матрицу
- Г рафиком на координатной плоскости, горизонтальная и вертикальная оси которой представляют элементы множеств А и В соответственно.
- Графом, в котором элементы множеств А и В изображаются точками на плоскости. Причем эти точки обозначаются теми же символами, что и соответствующие элементы. Точки a и b соединяются направленным отрезком от a к b, если aRb. Например, для предыдущего случая отношение R изображается ориентированным графом.
30.04.2022 939.5 Кб 3 Учебник 290.docx
30.04.2022 940.91 Кб 5 Учебник 291.docx
30.04.2022 943.57 Кб 2 Учебник 292.docx
30.04.2022 945.26 Кб 2 Учебник 293.docx
30.04.2022 947.08 Кб 1 Учебник 294.docx
30.04.2022 988.26 Кб 13 Учебник 295.docx
30.04.2022 990.58 Кб 7 Учебник 296.docx
30.04.2022 999.52 Кб 4 Учебник 297.docx
30.04.2022 1 Mб 3 Учебник 298.docx
30.04.2022 1 Mб 5 Учебник 299.docx
30.04.2022 18.93 Кб 1 Учебник 3.docx
Ограничение
Для продолжения скачивания необходимо пройти капчу:
Что такое булев куб
Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. №3 Кн.1. Изд. стереотип.
Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Твердый переплет
Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. №4 Кн.2. Изд. стереотип.
Болотов А.А., Гашков С.Б., Фролов А.Б. Твердый переплет
Арифметика. Алгоритмы. Сложность вычислений. Учебное пособие для вузов. (Сборник задач). Изд. 3, испр.
Гашков С.Б., Чубариков В.Н. Твердый переплет Букинист. Состояние: 4+ .
Предзаказ! 61.9 EUR
Дискретная математика. Учебник и практикум для спо. Изд. 3, испр. и доп.
Гашков С.Б., Фролов А.Б. Твердый переплет
Примени математику
Сергеев И.Н., Олехник С.Н., Гашков С.Б. Мягкая обложка Букинист. Состояние: 4+ .
Знакомство с теорией вычислений
Гашков С.Б. Твердый переплет
Центры тяжести и геометрия
Гашков С.Б. Мягкая обложка
Введение в конструктивную комбинаторику: Оригинальные конструкции современной комбинаторики. Дизайны, двоичные матрицы с экстремальными свойствами, графы с экстремальными свойствами, ортогональные массивы и латинские квадраты, алфавитные и групповые коды. № 340
Гашков С.Б. Мягкая обложка
Предзаказ! 8 EUR
Квадратный трехчлен в задачах
Гашков С.Б. Мягкая обложка
Системы счисления и их применение. Изд. 2, испр., доп.
Гашков С.Б. Мягкая обложка
Числа и функции
Гашков С.Б. Твердый переплет
Элементарная комбинаторика. №339
Гашков С.Б. Мягкая обложка
Показать ещё.
Содержание
| Предисловие | 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], некоторые утверждения и доказательства публикуются впервые.
В подготовке книги автор существенно опирался на конспект лекций О. Б. Лупанова «Элементы математической кибернетики».
31049.jpg» alt=»photo» /> Гашков Сергей Борисович
Доктор физико-математических наук, профессор. Профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова. Автор и соавтор книг «Примени математику», «Арифметика. Алгоритмы. Сложность вычислений», «Системы счисления и их применения», «Современная элементарная алгебра», «Элементарное введение в эллиптическую криптографию» (М.: URSS; в 2 кн.), «Криптографические методы защиты информации», «Занимательная компьютерная арифметика» (М.: URSS; в 2 кн.), «Геометрические неравенства: Путеводитель в задачах и теоремах» (М.: URSS), «Алгоритмические основы эллиптической криптографии», «Дискретная математика: Учебник и практикум для академического бакалавриата», «Обыкновенные дроби: От Древнего Египта до наших дней» (М.: URSS), «Булев куб, или Булеан: Уникальная комбинаторная конструкция и ее приложения» (М.: URSS), «Введение в конструктивную комбинаторику» (М.: URSS), «Элементарная комбинаторика» (М.: URSS).
Доставка Boxberry до 4000 пунктов выдачи заказов
URSS. 2024. 248 с. Мягкая обложка . 14.9 EUR Новинка недели!
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные. (Подробнее)
2023. 416 с. Твердый переплет . 19.9 EUR Новинка недели!
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые. (Подробнее)
2022. 560 с. Твердый переплет . 35.9 EUR
После мирового финансово-экономического кризиса 2008-2009 гг. интерес в мире и в России к теоретическому наследию Карла Маркса и классической политической экономии резко возрос, но современной, отвечающей на вызовы экономики XXI века учебной литературы ничтожно мало.
Учебник впервые на. (Подробнее)
Кларк Кристофер. Сомнамбулы: Как Европа пришла к войне в 1914 году
2023. 696 с. Твердый переплет в суперобложке . 21.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает. (Подробнее)
Сипачёва О.В. Начала общей топологии
2024. 432 с. Твердый переплет . 14.9 EUR
Общая, или теоретико-множественная, топология лежит в основе всех прочих разделов топологии и занимается изучением абстрактных топологических пространств (т. е. множеств, снабжённых самой общей структурой, позволяющей определить понятия предельной точки и непрерывности) –– объектов неизмеримо более. (Подробнее)
URSS. 2023. 208 с. Твердый переплет . 15.9 EUR
В монографии рассматривается вопрос внешнеполитической стратегии США в отношении Палестины и государства Израиль после Второй мировой войны. С 1917 года палестинский вопрос вошел во внешнеполитическую повестку в связи с публикацией Декларации Бальфура — документа, посвященного созданию. (Подробнее)
URSS. 2024. 208 с. Мягкая обложка . 14.9 EUR
В книге представлены результаты исследований по актуальным проблемам психологии личности, намечены возможные пути изучения нарушений мотивационной сферы, проанализированы такие особенности психической деятельности, как подконтрольность поведения, механизмы целеполагания и другие. Авторы рассматривают. (Подробнее)
Казанцева А. Откуда берутся дети?
2023. 352 с. Твердый переплет . 14.9 EUR
Новорожденные котята умеют ползать, косатки — плавать, слонята — ходить. Человеческий детеныш появляется на свет неприспособленным и в первый год жизни требует огромных ресурсов.
Вырастить здорового и счастливого человека — и при этом не лишиться карьеры, благополучия и душевного равновесия — колоссальная. (Подробнее)
Дементьев А.В. Политическая история Испании ХХ–XXI веков. Изд. 2, испр. и сущ. доп.
URSS. 2023. 280 с. Мягкая обложка . 15.9 EUR
Книга посвящена различным аспектам истории Испании XX–XXI вв. (1900–2018 гг.): политическому, институциональному и социально-экономическому развитию, национально-региональным отношениям, баскскому терроризму, каталонскому радикальному национализму, основным направлениям внешней политики.
Киссинджер Генри. Мировой порядок
2022. 512 с. Твердый переплет . 25.9 EUR
Генри Киссинджер — американский государственный деятель, дипломат и эксперт в области международной политики, занимал должности советника американского президента по национальной безопасности в 1969 — 1975 годах и государственного секретаря США с 1973 по 1977 год. Лауреат Нобелевской премии. (Подробнее)
Булев куб, или Булеан: Уникальная комбинаторная конструкция и ее приложения. Гашков С.Б.
Книга является введением в некоторые вопросы дискретной математики и комбинаторики, связанные с функциями алгебры логики и двоичным многомерным кубом (эти функции часто называют также булевыми, а куб — булевым, или булеаном). Рассказывается о применениях булеана в теории дискретных функций, булевой алгебре, теории кодирования и о том, как он появляется в различных вопросах экстремальной комбинаторики и теории графов. В книге много задач, в большинстве снабженных указаниями или полными решениями. Ее можно использовать как дополнительное чтение при изучении курсов дискретной математики и информатики. Большая ее часть доступна школьникам, интересующимся математикой.
Булевы функции и булев куб
В дискретной математике большую роль играют конечные функции. Конечной функцией называют отображение одного конечного множества в другое. Важный класс таких функций образуют булевы функции.
Булева функция (от переменных) — это произвольное отображение вида
т.е. булева функция определена на множестве всех n-элементных (при ) последовательностей (или n-компонентных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.
С понятием булевой функции тесно связаны понятия булевой константы и булева переменного. (В литературе по теории булевых функций традиционно употребляется термин «булева переменная» (в женском роде).)
Булева константа — это индивидная константа с областью значений . Таким образом, существуют две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булева функция от 0 переменных (что вполне аналогично определению нульарной операции).
Булево переменное — это индивидное переменное с областью значений , т.е. это переменное, которое может принимать только два значения: 0 и 1 (подобно тому, как действительное переменное принимает произвольное действительное значение, а комплексное переменное — произвольное комплексное значение). Тогда с использованием понятия булева переменного мы можем задать булеву функцию (6.1) записью , в которой каждое булево переменное , и функция / принимают два возможных значения: 0 и 1. Переменные называют при этом переменными булевой функции . Фиксируя значение каждого переменного , получаем кортеж из множества , называемый набором значений переменных , и соответствующее ему значение функции , которое будет значением переменного , сопоставленным заданным значениям переменных .
Подчеркнем, что, если специально не оговорено противное, в выражении все переменные предполагаются попарно различными, т.е. пробегающими каждое независимо от других множество .
Понятию булевой функции можно придать иной смысл, понимая элементы множества как истинностные значения, а именно понимая единицу как «истину», а нуль как «ложь». Такие истинностные значения могут быть, как мы знаем, сопоставлены каждому высказыванию. Тогда булева функция есть некоторое правило, позволяющее каждому фиксированному набору истинностных значений, т.е. набору значений булевых переменных, сопоставить то или иное истинностное значение. Так может быть вычислено, например, истинностное значение сложного высказывания, составленного по определенным правилам из простых высказываний. Подобного рода сложные высказывания составляются с помощью логических операций: «или», «и», «если . то . » и т.п. Указанная логическая интерпретация булевой функции позволяет понять, почему булево переменное часто называют логическим переменным (традиционный термин: «логическая переменная»), а булеву функцию — логической функцией (или функцией алгебры логики).
Кроме того, согласно определению, булева функция от переменных есть отображение n-й декартовой степени множества в множество , т.е. не что иное, как n-арная операция на множестве . Тем самым логическая интерпретация булевой функции согласуется с ее алгебраической интерпретацией: булева функция есть операция (в алгебраическом смысле этого слова) на множестве истинностных значений. Тогда и понятие логической операции, которое было введено ранее, оказывается частным случаем общего понятия операции.
Будем обозначать через множество всех булевых функций (для всех возможных значений числа переменных), а через — множество всех булевых функций от переменных (для фиксированного ). Из определения следует, что .
Итак, областью определения любой булевой функции от переменных является множество , т.е. булев куб размерности . Элементы булева куба называют n-мерными булевыми векторами (или наборами). Число всех элементов булева куба составляет является носителем булевой алгебры (это же обозначение часто будем использовать и для соответствующего булева куба). Но в любой булевой алгебре определяется, как известно, естественное отношение порядка так, что для произвольных соотношение выполняется тогда и только тогда, когда .
Употребляются также термины: единичный куб размерности , n-мерный единичный куб; вместо слова «куб» говорят также «гиперкуб».
Согласно общему принципу распространения отношения порядка на декартово произведение множествам. 4.5), для произвольных двух наборов и из имеет место тогда и только тогда, когда для каждого , то есть .
Другими словами, тогда и только тогда, когда или , а для каждого . Если существует хотя бы одно , то имеет место строгое неравенство . В частности, если существует ровно одно такое доминирует над набором , так как ясно, что в этом случае нельзя найти такой набор , что .
Пример 6.1. В булевом кубе причем второй из этих наборов доминирует над первым, а третий — над вторым (но, естественно, третий уже не доминирует над первым, а лишь строго больше его). Наборы же и — несравнимые элементы, так как первая компонента второго набора больше первой компоненты первого набора, но зато вторая компонента первого набора больше второй компоненты второго набора. Подчеркнем также, что описанное сравнение наборов возможно только для фиксированной размерности и никак нельзя сравнивать наборы разных размерностей.
Булевый порядок
Рассмотренное отношение порядка на
Другой способ наглядного изображения булева куба основан на том, что диаграмма Хассе любого конечного упорядоченного множества , тогда и только тогда, когда доминирует над компонент отличны от нуля (множество всех таких наборов для фиксированного , будем называть булевой n-сетъю или просто булевой сетью, если упоминание о размерности опускается. Так как булев куб имеет наименьший элемент — нулевой набор и наибольший элемент — единичный набор, то каждая булева сеть имеет единственный вход (помеченный нулевым набором) и единственный выход (помеченный единичным набором).
На рис. 6.2 приведено изображение булева куба
Помимо булева порядка полезно также ввести на булевом кубе другое отношение порядка, которое мы будем называть лексикографическим порядком, используя обозначение (для произвольного фиксированного ). По определению,
Каждая из сумм в неравенстве (6.2) есть не что иное, как представление некоторого натурального числа (включая и нуль) в двоичной системе счисления (при числе разрядов, равных фиксированной размерности ). На каждый булев вектор можно смотреть как на такое представление (двоичный код) натурального числа, и лексикографический порядок на булевом кубе множества (при условии, что числа заданы в двоичной системе счисления). Более строго: упорядоченное множество изоморфно подмножеству с естественным числовым порядком.
Заметим, что отношение лексикографического порядка является, в отличие от булева порядка, отношением линейного порядка.
Пример 6.2. Набор как двоичный код числа лексикографически больше набора , служащего двоичным кодом числа 3, но при этом указанные наборы не сравнимы по отношению булева порядка.
Однако лексикографический порядок при изучении булевых кубов играет вспомогательную роль. В частности, при изображении булевых кубов (в виде диаграмм Хассе или в виде сети) принято располагать вершины каждого k-слоя в лексикографическом порядке (по возрастанию — слева направо или сверху вниз). Везде в дальнейшем, рассуждая о булевом кубе как об упорядоченном множестве, мы имеем в виду булев порядок.
Грань булева куба
Гранью булева куба размерности — размерность булева куба, называют множество наборов, имеющих не менее и из множества . Тогда грань, обозначаемая как , есть множество всех таких . При этом кортеж номеров называют направление ем грани . Если число , полагая, что второй набор доминирует над первым. Любая вершина булева куба считается гранью размерности 0.
Можно показать, что число всех граней размерности .
Пример 6.3. В четырехмерном булевом кубе . Эта грань состоит из восьми наборов:
На рис. 6.1 выделены все ребра булева куба
Грани булева куба, имеющие одно и то же направление, называют параллельными. Две параллельные грани и называют соседними, если один из наборов и доминирует над другим. На рис. 6.1 грани и соседние, равно как и грани (ребра) и . Но ребра и не являются соседними.
Нетрудно догадаться, что каждая грань размерности , столькими способами, сколько существует разных n-мерных граней в кубе размерности способами. Так, одномерный куб четырьмя способами — как одна из его четырех одномерных граней (т.е. как одно из его четырех ребер, см. рис. 6.1).
Договоримся впредь записывать конкретные наборы (элементы булева куба соответствующей размерности) без скобок и запятых, т.е. будем писать не , а переменных для фиксированного . Поскольку каждая булева функция отображает множество из равна Замечание 6.1. Поскольку булева функция от переменных является в то же время и n-арной операцией на множестве , то при существуют две нульарные операции: 0 и 1, которые есть не что иное, как нуль и единица двухэлементной булевой алгебры.