Что такое булев куб
Перейти к содержимому

Что такое булев куб

  • автор:

3.2. Булев куб и его свойства

Булев вектор может применяться для моделирования операций на конечных множествах. Пусть – некоторое универсальное множество в рамках решаемой задачи. Элементы множества для удобства помечены числовыми индексами. Если , то множеству А ставится в соответствие n— мерный булев вектор , в котором , если и в противном случае. Такая строка бит называется характеристическим вектором множества А. При этом, операции на множествах имитируются соответствующими логическими операциями на характеристических векторах.

Для размерности n операции над векторами производятся покоординатно. Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Между множеством всех подмножеств множества U и булевым кубом , где можно установить взаимнооднозначное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

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

Номером булевого вектора называется число его двоичного представления. Например, булев вектор а из предыдущего примера имеет номер 10101.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (т.е. они отличаются только одной координатой).

Булев куб размерности 1

Булев куб размерности 2

Булев куб размерности 3

3.3. Понятие отношения

Для выражения взаимодействий и связей между элементами множеств в математике используется понятие отношения.

n – местным (n – арным) отношением R на множествах называется любое подмножество прямого произведения этих множеств, то есть . Другими словами, элементы этих множеств связаны отношением R тогда и только тогда, когда n упорядоченных чисел .

Отношение называется n – местным на множестве А.

При отношение R задает фиксированный элемент множества А. При отношение R представляет собой подмножество множества А и называется унарным отношением или свойством. При отношение R называется бинарным или соответствием. При отношение тернарное и т. д.

В математике чаще всего используются бинарные отношение (соответствия). В дальнейшем рассматриваются в основном только такие отношения и при этом слово “бинарные” опускается.

Пусть А и В – два множества. Соответствием или (бинарным) отношением из множества А в множество В называется подмножество R прямого произведения , т.е. . Если aA, bB, находятся в отношении, то пишут: (a,b)R или R(a,b), а также в инфиксной форме aRb. При этом говорят, что b соответствует a при соответствии R или b находится в отношении R с a. Если R=, то отношение называют пустым. Отношение называют полным. Для любого множества А определяется тождественное отношение — .

Принадлежность элементов а и b отношению R наглядно можно представить в следующем виде

Областью определения (DomR) соответствия R, называется множество элементов aA, для каждого из которых, найдется хотя бы один элемент bB, такой, что aRb.

Областью значения (ImR) соответствия R называется множество элементов bB, для каждого из которых, найдется хотя бы один элемент aA, такой, что aRb.

Соответствие R называется всюду определенным, если DomR=A, в противном случае – частично определенным. Соответствие называется сюръективным, если ImR=B.

Для каждого aA, множество элементов bB таких, что aRb называется образом элемента aA относительно R и обозначается imRa.

Прообразом элемента bB относительно R, называется множество элементов aA, таких, что aRb. Прообраз обозначается: coimRb

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

Отношения, определенные на конечных множествах , могут быть заданы:

  1. Списком, т.е. перечислением тех пар элементов, для которых это отношение выполнено. Например, если A=a,b,c> и B=x,y>, то R=<(a,x),(a,y),(b,y),(c,x)>.
  2. Матрицей [R] размерности , элементы которой т.е. строки этой матрицы помечаются элементами из A, а столбцы – элементами из B, а на пересечении строки ai со столбцом bi стоит единица (1), если aRb; и нуль (0), — в противном случае. Тогда для выше приведенного примера имеем матрицу

Глава 1

Глава 1. Булевы функции 1.1. Булев куб Константы 0 и 1 называются булевыми константами. Упорядоченные наборы из нулей и единиц будем называть двоичными или булевыми наборами. Символы 0 и 1, входящие в двоичный набор, называются разрядами набора. Число разрядов набора называется его длиной. Разряды каждого набора длины n нумеруются целыми числами от 1 до n слева направо: крайний левый разряд получает номер 1, крайний правый — номер n . Множество всех булевых наборов длины n называется булевым кубом размерности n и обозначается символом B n . Название булев куб возникло благодаря геометрической интерпретации множества B n . Если наборы из этого множества рассматривать как элементы действительного n — мерного пространства B n , то нетрудно убедиться, что они будут расположены в вершинах единичного куба. Поэтому часто булевы наборы называются также вершинами n -мерного единичного куба. Номером и весом набора u = ( u 1 . u n ) из B n называются величины

n u 2 n i n
u , u u .
i 1 1 i 1 i
Номера наборов задают на множестве B n отношение линейного

порядка ≤. Будем говорить, что набор u не больше набора v , если | u | ≤ | v |. Порядок, определяемый отношением ≤, называется лексикографическим . Множество всех наборов длины n и веса k образует k -й слой куба B n , обозначаемый через B k n . Число наборов в k -м слое n -мерного единичного куба равно числу сочетаний из n элементов по k — столькими способами среди n разрядов произвольного набора можно выбрать k разрядов, равных единице. Следовательно,

n n n !
B k
n k ! k !
k
Расстоянием Хемминга между вершинами u и v куба B n
называется число d u, v n u v
, равное количеству несовпадающих
i 1 i i

разрядов u и v . Нетрудно показать, что расстояние d является метрикой, т.е. d – положительная симметрическая функция двух аргументов, принимающая значение нуль тогда и только тогда, когда два ее аргумента совпадают, и для которой справедливо неравенство треугольника: d( u , v ) ≤ d( u , w ) + d( w , v ) для любых трех наборов u , v и w из B n . Наборы u и v называются соседними , если d (u , v )=1. Если d ( u , v )= n , то наборы называются противоположными . Соседние наборы различаются между собой только в одном разряде, противоположные наборы — во всех разрядах. Пример 1.1.1. В трехмерном булевом кубе B 3 рассмотрим четыре набора u 1 = (000), u 2 = (100), u 3 = (110) и u 4 = (111). Для номеров и весов этих наборов справедливы равенства: | u 1 | = 0, | u 2 | = 4, | u 3 | = 6, | u 4 | = 7, || u 1 || = 0, || u 2 || = 1, || u 3 || =2, || u 4 || = 3. Попарные расстояния между рассматриваемыми наборами равны d ( u 1 , u 2 ) = 1, d ( u 1 , u 3 ) = 2, d ( u 1 , u 4 ) = 3, d ( u 2 , u 3 ) = 1, d ( u 2 , u 4 ) = 2, d ( u 3 , u 4 ) = 1. Следовательно, наборы u 1 и u 4 — противоположные, а u i и u i+1 при i = 1,2,3 — соседние. Пары соседних вершин булева куба называются ребрами . Если u , v — соседние вершины, различающиеся в i – м разряде, то говорят, что ребро ( u , v ) проходит в i — м направлении и соединяет эти вершины. Пусть i 1 , … , i n-k -попарно различные натуральные числа, не превосходящие n, u 1 , … , u n-k -булевы константы. Множество < v ε B n | v i = u j , j = 1,2, … ,n-k>называется k — мерной гранью куба B n . Легко видеть, что k — мерная грань n — мерного булева куба содержит 2 k различных вершин. Пусть u ε B n . Шаром радиуса k с центром в наборе u называется множество B n, k ( u ) состоящее из всех таких v ε B n , что d ( u , v ) ≤ k . Сферой радиуса k с центром в наборе u называется множество S n,k ( u ) состоящее из всех таких v ε B n , что d ( u , v ) = k . Легко видеть, что k — й

слой B k n является сферой радиуса k с центром в нулевом наборе и сферой радиуса n — k с центром в единичном наборе. Непосредственно из определений сферы и шара следует, что для любого u ε B n и любого k= 0, 1,…, n

S u n , B u k n
n , k .
n , k
k i 0 i

Пример 1.1.2. Рассмотрим трехмерный булев куб B 3 , изображенный на расположенном слева рис. 1.1.1. Этот куб содержит восемь вершин, образующих в нем четыре слоя. Нулевой слой B 0 3 состоит из единственной вершины (000). Первый слой B 1 3 содержит три вершины: (100), (010) и (001). Второй слой B 2 3 также содержит три вершины: (110), (101) и (011). И, наконец, третий слой B 3 3 куба состоит из одной вершины (111). В кубе 12 ребер, изображенных на рисунке отрезками, соединяющими вершины. В каждом из трех направлений проходит по четыре ребра. В B 3 содержится шесть двумерных граней, содержащих по четыре вершины. Вершины одной из этих граней отмечены на рисунке черными кружками. Легко видеть, что номера отмеченных вершин принадлежат множеству <1,3,5,7>. Шар B 3,1 (010) состоит из вершины (010) и трех вершин, соединенных с ней ребрами: (000), (110) и (011). Три последние вершины образуют сферу S 3,1 (010). 2. Подмножество G = < g ѐ1 , …, g m >булева куба B n называется двоичным кодом с кодовым расстоянием d , если для любых двух его элементов g i и g j расстояние между ними не меньше d . Говорят, что код G исправляет t ошибок, если его кодовое расстояние не меньше чем 2 t +1. Заметим, что если вокруг каждого элемента g кода G с расстоянием 2 t +1 построить шар радиуса t с центром в этом элементе, то шары с центрами в разных элементах не будут пересекаться Действительно, если некоторый набор v

принадлежит пересечению шаров с центрами в элементах g i и g j , то это
означает, что d ( v , g i ) t и d ( v , g j ) t . Но тогда в силу неравенства

треугольника d ( g i , g j ) d ( v , g i ) + d( v , g j ) 2 t . Противоречие. Пример 1.1.3. Снова рассмотрим трѐхмерный булев куб B 3 . В нѐм любые две противоположные вершины образуют код с расстоянием три,

например, . Кодами с расстоянием два являются множество всех наборов чѐтного веса и множество всех наборов нечѐтного веса. Обозначим через m(n , d ) максимально возможное число элементов в двоичном коде длины n, кодовое расстояние которого равно d . Для кодов с нечѐтным кодовым расстоянием имеет место следующий результат. Теорема 1.1.1. Справедливы неравенства

2 n 2 n
m ( n , 2 t 1) .
2 t n t n
i 1 i i 1 i

Доказательство. Верхняя оценка величины m ( n, 2t+ 1) легко следует из замечания, сделанного перед формулировкой теоремы. Рассмотрим в B n произвольный код G с расстоянием 2 t+ 1, и построим вокруг каждого его элемента шар радиуса t . Так как эти шары не пересекаются, и каждый шар

состоит ровно из t n наборов, то все шары вместе содержат
i 1 i
G t n и, поэтому,
наборов. С другой стороны шары лежат в B n
i 1 i t n
содержат не более 2 n наборов. Следовательно, G
2 n .
i 1 i
Для доказательства нижней оценки опишем индуктивную процедуру

построения в B n кода G с расстоянием 2 t +1. Первый элемент кода выберем произвольно, вокруг выбранного элемента построим шар радиуса 2 t. В качестве второго элемента кода возьмѐм произвольный набор, не принадлежащий построенному шару. Очевидно, что расстояние между выбранными наборами не меньше 2 t +1. Вокруг второго элемента также построим шар радиуса 2 t . Теперь допустим, что выбраны k элементов, попарные расстояния между которыми не меньше 2 t +1, и вокруг каждого выбранного элемента построен шар радиуса 2 t. Если

2 t n 2 n ,
k (1.1.1)
i 1 i
то можно выбрать очередной ( k +1)-й элемент, не принадлежащий

построенным шарам, и, следовательно, находящийся на расстоянии не меньшем 2 t +1 от каждого из выбранных ранее элементов. Легко видеть, что построение кода можно продолжать до тех пор пока справедливо

неравенство (1.1.1). В тот момент, когда это неравенство впервые

нарушится, код G будет состоять из k элементов, и для k будет
k n n 2 n .
i 1
справедливо неравенство i Теорема доказана.

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

2 nlog 2 n средних слоев. Более точно, имеет место следующее
утверждение.
Теорема 1.1.2. При n справедливо асимптотическое
равенство
n / 2
nlog 2 n
B n ~ B n = 2 n .
k n / 2 k
nlog 2 n

Доказательство. Оценим число наборов, вес которых отличается от n 2 более, чем на t единиц:

B n n n / 2 k 2 n
k : n / 2 k t k k : n / 2 k t k k : n / 2 k t n / 2 k 2 k
1 n k 2 n 1 n k 2 n .
t 2 k : t 2 k
n / 2 k t 2 k 0 2 k

(1.1.2) Найдем сумму, стоящую в правой части неравенства (1.1.2). Легко видеть, что

n n n 2
k
k 0 k 2

Булев куб

По определению, булев куб размерности n есть множество В n =1,x2,…,xn>|xk=0,1; k=1,2,…,n>. Элементы (точки) булева куба принять записывать в виде последовательности нулей и единиц, без запятых и скобок: x1x2…xn.

ê Булев куб является частично упорядоченным множеством:

a ´ b Ç аi ≤ bi для всех i=1,n.

ê Вектора 0 = (0, …,0) и 1 = (1,…,1) являются наименьшим и наибольшим элементами куба.

ê Этот порядок будем называть булевым порядком.

ê Булев куб с таким упорядочиванием является полной дистрибутивной решёткой.

ê Полная дистрибутивная решётка в то же время является и алгеброй типа .

Алгеброй Буля называется алгебра, операции которой удовлетворяют следующим свойствам:

Идемпотентность aÙa = a aÚa = a
Коммутативность aÙb = bÙa aÚb = bÚa
Ассоциативность aÙ(bÙc) = (aÙb)Ùc aÚ(bÚc) = (aÚb) Úc
Дистрибутивность aÙ(bÚc) = (aÙb)Ú(aÙc) aÚ(bÙc) = (aÚb)Ù(aÚc)
Законы нуля aÙ0 = 0 aÚ0 = a
Законы единицы aÙ1 = 1 aÚ1 = 1
Свойства отрицания aÙ(a) = 0 aÚ(a) = 1
Инволютивность (a) = a
Законы де Моргана (aÙb) = (a)Ú(b) (aÚb) = (a) Ù(b)
Законы поглощения aÙ(aÚb) = a aÚ(aÙb) = a
Законы склеивания (aÚb)Ù(aÚb) = a (aÙb)Ú(aÙb) = a
Двойственность 0 = 1 1 = 0

ê Простейшая алгебра Буля B = (B; Ú, Ù,) имеет носителем двухэлементное множество B=, , .

ê n–мерный булев куб является алгеброй B n = (B n ; Ú, Ù,, 0,1).

ê n–мерный булев куб является полной дистрибутивной решёткой.

ê Алгебру B n можно интерпретировать как векторное пространство над полем (B; Ú, Ù).

ê Алгебра B n изоморфна алгебре (2 U ;Ç,È,¯,Æ,U) с n–элементным множеством U.

Точки булева куба представляются последовательностью (словом) длины n. Интерпретация этого слова как двоичного числа является нумерацией и, следовательно, задаёт на кубе линейный порядок, отличный от булева. Будем его называть числовым порядком.

n-мерный булев куб состоит из 2 n элементов. Конечное число точек всегда можно изобразить на плоскости – т.е. булев куб произвольной размерности можно изображать графически.

n=0 n=1. – Двухэлементное множество, диаграмма Хассе которого имеет вид:

n=2. Булев квадрат имеет четыре элемента, изображаемые диаграммой:

n=3. Трёхмерный булев куб изображается следующим образом:

n=4. Четырёхмерный куб можно изобразить следующим образом:

Этот же куб часто изображают в виде ориентированной сети. Линии сети соединяют элементы куба, находящиеся в отношении доминирования, а каждый слой (уровень) сети состоит из элементов антицепи.

Грани булева куба.

Если в определении булева куба, т.е. множества всех двоичных векторов длины n, зафиксировать некоторую компоненту, скажем, k-ую, мы получим множество из 2 n-1 элементов, которое будет изоморфно кубу размерности n–1. Это множество называется подкубом, или гранью, размерности n–1.

На подкубе индуцируется частичный порядок.

Номер зафиксированной компоненты называется направлением грани. Всего можно зафиксировать n различных компонент – говорят об n способах вложения или о соответствующем числе граней.

Продолжая процедуру фиксации компонент куба k раз, получим грань (подкуб) размерности n–k, номера зафиксированных компонент 1≤i1< … k≤n, определяющие направление грани, и значения (σ1, …, σk) зафиксированных компонент из множества .

Грань размерности n–k – это множество наборов, имеющее не менее k одинаковых компонент. Грань данного куба задаётся: а) кортежем номеров (i1, …,ik) и б) значениями (σ1, …, σk).

Ребро – это грань размерности 1, т.е. подмножество куба, состоящее из двух элементов, один из которых доминирует над другим.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Что такое булев куб

Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. №3 Кн.1. Изд. стереотип.

Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Твердый переплет

Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. №4 Кн.2. Изд. стереотип.

Болотов А.А., Гашков С.Б., Фролов А.Б. Твердый переплет

Арифметика. Алгоритмы. Сложность вычислений. Учебное пособие для вузов. (Сборник задач). Изд. 3, испр.

Гашков С.Б., Чубариков В.Н. Твердый переплет Букинист. Состояние: 4+ .
Предзаказ! 61.9 EUR
Дискретная математика. Учебник и практикум для спо. Изд. 3, испр. и доп.
Гашков С.Б., Фролов А.Б. Твердый переплет
Примени математику
Сергеев И.Н., Олехник С.Н., Гашков С.Б. Мягкая обложка Букинист. Состояние: 4+ .
Знакомство с теорией вычислений
Гашков С.Б. Твердый переплет
Центры тяжести и геометрия
Гашков С.Б. Мягкая обложка

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

Гашков С.Б. Мягкая обложка
Предзаказ! 8 EUR
Квадратный трехчлен в задачах
Гашков С.Б. Мягкая обложка
Системы счисления и их применение. Изд. 2, испр., доп.
Гашков С.Б. Мягкая обложка
Числа и функции
Гашков С.Б. Твердый переплет
Элементарная комбинаторика
Гашков С.Б. Мягкая обложка
Показать ещё.
Содержание

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

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

photo

31049.jpg» alt=»photo» /> Гашков Сергей Борисович

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

Доставка Boxberry до 4000 пунктов выдачи заказов
URSS. 2024. 800 с. Мягкая обложка . 37.9 EUR

ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ)

11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший. (Подробнее)

Азарнова А.Н. ПСИХОЛОГИЧЕСКОЕ КОНСУЛЬТИРОВАНИЕ: Настольная книга для НАЧИНАЮЩИХ
URSS. 2023. 272 с. Мягкая обложка . 15.9 EUR

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

Кларк Кристофер. СОМНАМБУЛЫ: Как Европа пришла к войне в 1914 году
2023. 696 с. Твердый переплет в суперобложке . 89.9 EUR

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

URSS. 2024. 344 с. Мягкая обложка . 18.9 EUR

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

URSS. 2024. 704 с. Твердый переплет . 26.9 EUR

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

Лазуткин А.А. Военная стратегия в компьютерных играх и реальном мире. № 58
URSS. 2024. 576 с. Мягкая обложка . 23.9 EUR

Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире.

Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх. (Подробнее)

URSS. 2024. 248 с. Мягкая обложка . 14.9 EUR

В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные. (Подробнее)

URSS. 2024. 240 с. Твердый переплет . 23.9 EUR

Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана. (Подробнее)

2023. 416 с. Твердый переплет . 19.9 EUR

Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые. (Подробнее)

2022. 560 с. Твердый переплет . 35.9 EUR

После мирового финансово-экономического кризиса 2008-2009 гг. интерес в мире и в России к теоретическому наследию Карла Маркса и классической политической экономии резко возрос, но современной, отвечающей на вызовы экономики XXI века учебной литературы ничтожно мало.

Учебник впервые на. (Подробнее)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *