XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 60
Текст из файла (страница 60)
Тогда и понятие логической операции, которое было введено ранее (см. 1.1), оказывается частным случаем общего понятия операции (см. 2,1). Будем обозначать через Р2 множество всех булевых функций (для всех возможных значений н числа переменных), а через Рт, — множество всех булевых функций от и переменных (для фиксированного н).
Из определения следует, что п>о Итак, областью определения любой булевой функции от н переменных является множество (О, Ц", т.е. булев куб' раэмерносгаи н. Элементы булеза куба (О, Ц" называют и-мерными булевыми векторами (или наборами). Число всех элементов булева куба (О, Ц" составляет 2п.
Элементы булеза куба будем также называть его вершинами. Булез куб (О, Ц" является носишелем булевой алгебры В" (зто же обозначение часто будем использовать и для соответствующего булеза куба). Но в любой булевой алгебре А= = (А, Ч, Л, О, 1) определяется, как известно, естественное о~ино~иение порядка < так, что для произвольных а, Ь е А соотношение а < 6 выполняется тогда и только тогда, когда а Ч 6 = 6 (или, что равносильно, а Л 6 = а). Напомним (см.
3.4), что булеза алгебра В" является не чем иным, как и-й декаршовой стиененью двуяэлеменшной булевой алгебры В = ((О, Ц, Ч, Л, О, Ц. "Употребллютсл также термины: единичный нуб розмернос1пп н, и-мерный едимвпныб куб; вместо сюва „куб" говорит также „гиперкуб". 378 б. БУЛЕВЫ ФУНКЦИИ Согласно общему принципу распространения отношения порядка на денартпово произведение множестпв (см. 4.5), для произвольных двух наборов а = (аы ..., а„) и ф = (,оы ..., Д,) из В" имеет место Н ((,о тогда и только тогда, когда ои < Д для каждого е = 1, и, т.е.
а< Ч Д = Д. Другими словами, а < р' тогда и только тогда, когда а; =,6; или а; = О, а Д = 1 для каждого 1 = 1, и. Если существует хотя бы одно 1, для которого выполняется а; = О, 8; = 1, то имеет место строгое неравенство а <,о. В частности, если существует ровно одно такое 1, то набор ~3 доминируеш над набором а, так как ясно, что в этом случае нельзя найти такой набор у, что а < у <~3. Пример 6.1. В булевом кубе В4 (О, О, 1, 1) < (1, О, 1, 1) < (1, 1, 1, 1), причем второй из этих наборов доминирует над первым, а третий — над вторым (но, естественно, третий уже не доминирует над первым, а лишь строго больше его).
Наборы же (О, 1, О, 1) и (1, О, 1, 1) — несравнимые эяеменгпы, так как первая компонента второго набора больше первой компоненты первого набора, но зато вторая компонента первого набора больше второй компоненты второго набора. Подчеркнем также, что описанное сравнение наборов возможно только для фиксированной размерности и никак нельзя сравнивать наборы разных размерностей. Рассмотренное отношение порядка на В" будем называть брлевмм порядком. Булез куб как упорядоченное мноэсесшво, можно изобразить в виде диаграммы Хассе.
На рис. 6.1 приведены диаграммы Хассе для булевых кубов размерностей от О до 4. Другой способ наглядного изображения булева куба основан на том, что диаграмма Хассе любого конечного упорядоченного множества А может быть задана в виде ориеншированной сегпи, так что дуга из вершины, сопоставленной элементу я Е А, 6.1. Понятие булевой функции. Булев куб 379 о 1=0 110 10 011 100 001 00 н~2 1111 000 и=3 Шо 1100 0011 0001 0000 Рве. 6.1 ведет в вершину, сопоставленную элементу у е А, тогда и только тогда, когда у доминирует над х и каждый уровень сети состоит из вершин, сопоставленных попарно несравнимым элементам множества А (т.е. элементам некоторой антицепи в А). Входы сети сопоставлены минимальньиц а выходы — максимальным элеменшам А.
Каждый уровень представляющей булез куб В" сети состоит из всех вершин, соответствующих наборам, у которых ровно к (О < к < и) компонент отличны от нуля (множество всех таких наборов для фиксированного й называют Й-слоем булеза куба В ). 380 6. БУЛЕВЫ ФУНКЦИИ Сеть, служащую изображением булеза куба размерности и, будем называть булевой и-сетпью или просто булевой сетиью, если упоминание о размерности опускается. Так как булез куб имеет наименьший элеменот — нулевой набор и наибольший элеменот — единичный набор, то каждая булеза сеть имеет единственный вход (помеченный нулевым набором) и единственный выход (помеченный единичным набором). На рис. 6.2 приведено изображение булеза куба В4 в виде сети.
2-слой Рис. В.з Помимо булеза порядка полезно также ввести на булевом кубе другое отношение порядка, которое мы будем называть лексикографическим иорлдком, используя обозначение -<. Пусть ст, ~3 Е В" (для произвольного фиксированного и). По определению, а -С,В, если и и 2н-т ~ '~ ~)у 2н-т (6.2) б.1. Понятие булевой функпни. Буден куб 661 Каждая иэ сумм в неравенстве (6.2) есть не что иное, как представление некоторого натурального числа (включал и нуль) в двоичной системе счисления (при числе разрядов, равных фиксированной размерности и).
На каждый булез вектор можно смотреть как на такое представление (двоичный код) натурального числа, и лексикографический порядок на булевом кубе В" есть не что иное, как есгпесшвенный числовой порядок на подмножестве (О, 1, ..., 2" 1) множества М0 (0) (при условии, что числа заданы в двоичной системе счисления)'. Заметим, что отношение лексикографического порядка является, в отличие от булеза порядка, отношением линейного порядка.
Пример 6.2. Набор (1, О, 1) как двоичный код числа 5 = = 1 2~+ О. 21+ 1. 20 лексикографически больше набора (О, 1, 1), служащего двоичным кодом числа 3, но при этом указанные наборы не сравнимы по отношению булеза порядка. Однако лексикографический порядок при изучении булевых кубов играет вспомогательную роль. В частности, при изобра женин булевых кубов (в виде диаграмм Хассе или в виде сети) принято располагать вершины каждого Й-слоя в лексикографическом порядке (по возрастанию — слева направо или сверху вниз). Везде в дальнейшем, рассуждая о булевом кубе как об упорядоченном множестве, мы имеем в виду булез порядок.
Гранью булева куба размерности п — Й, где и — размерность булеза куба, называют множество наборов, имеющих не менее Й одинаковых компонент. Грань размерности и — Й в В" будет определена, если фиксировать Й номеров 1 ( 11 « ... 1ь ( и и Й констант п1, ..., бь иэ множества (О, 1). Тогда грань, обозначаемая как В",",'„';;е'", есть множество всех таких а Е В", что а;, = б1, ..., сц, = бе. При этом кортеж номеров (11, ..., 1ь) называют какравлекм- Более строго: упорядоченное множество (В", с) ееоморФно подмножеству (О, 1,..., 2" 1) С МО(0) с естестненшем числовым порндком. 382 б.
БУЛЕБЫ ФУНКЦИИ ем еранп В,",',""""». Если число и — й, определяющее размерность грани, равно 1 (т.е. Й = и — 1), то такую грань называют ребром 6плева куба Вв. Таким образом, ребро — это множество, состоящее из двух наборов, один из которых доминирует над другим (в смысле булеза порядка). Другими словами, эти два набора отличаются друг от друга значением единственной компоненты. Для ребра булеза куба будем использовать обозначение (а, Д, полагая, что второй набор доминирует над первым. Любая вершина булева куба считается гранью размерности О. Можно показать, что число всех граней размерности и — й составляет 2" С».
Пример 6.3. В четырехмерном булевом кубе В4 направление трехмерной грани задается фиксированием одного из номеров от 1 до 4 и фиксированием значения соответствующей компоненты наборов, принадлежащих этой грани. На рис. 6.1 выделены ребра грани Ве' . Эта грань состоит из вось- 4,1 ми наборов: (О, О, О, 0), (О, О, О, 1), (О, О, 1, 0), (О, О, 1, 1), (О, 1, О, 0), (О, 1, О, 1), (О, 1, 1, 0), (О, 1, 1, 1). На рис. 6.1 выделены все ребра булева куба В3, имеющие направление (1, 2). 1'рани булеза куба, имеющие одно и то же направление, называют параллельными. Две параллельные грани В~,',',.",,'д~" и В"„"',.';,'," называют сосед44ил4и, если один из наборов (о1, ..., ~ть) 1г- Й ) и (у1, ..., 73) доминирует над другим.
На рис. 6.1 грани Ве' и В ' сосеДние, Равно как и гРани (РебРа) Ве'е' и Ве'1' . Но 3,1,2 3,1,2 ребра В1'е' и Во*1' не являются соседними. 3,1,2 3,1,2 Нетрудно догадаться, что каждая грань размерности и- и булева куба В" сама является булевым кубом размерности и — й и содержит, следовательно, 2" " вершин. Точнее говоря, эта грань вместе с оп1кошением порядка, индуцировавным булевьп4 383 6.2. Таблицы булевых фувллий порядком на В", будет упорядоченным множеством, изоморфным булеву кубу В" " (с булевым порядком на нем). Поэтому часто грани булеза куба называют его подкубами.
В то же время булез куб В" юоморфно вкладывается (несколькими способами) в булев куб большей размерности, а именно булев куб В" вкладывается (как грань) в булез куб В" +", к ) 1, столькими способами, сколько существует разных и-мерных граней в кубе размерности н + к, т.е. 2". С„"+ь способами. Так, одномерный куб В вкладывается в двумерный Вз четырьмя способами — как одна из его четырех одномерных граней (т.е. как одно иэ его четырех ребер, см. рис. 6.1).
Договоримся впредь записывать конкретные наборы (элементы булеза куба соответствующей размерности) без скобок и запятых, т.е. будем писать не (О, 1, О, 1), а 0101 (если, конечно, это не ведет к недоразумениям). В заключение найдем мошносшь множесшва всех булевых функций от п переменных для фиксированного и. Поскольку каждая булеза функция отображает множество из 2" элементов в двухэлементное множество, а мощность множества всех отображений из и-элементного множества в тп-элементное равна, как известно, т", то мощность множества Рз„равна 2~ . В частности, при н = 0 получаем две булевы константы: 0 и 1.
Замечание 6.1. Поскольку булева функция от и переменных является в то же время и н-аркой операцией на множестве (О, Ц, то при и = 0 получаем нульарную операцию. Ясно, что на множестве 10, Ц существуют две нульарные операции: 0 и 1, которые есть не что иное, как нуль и единица двухзлементной булевой алгебры. 6.2. Таблицы булевых функций Буяева функция ош в переменныя может быть задана таблицей, состоящей ю двух столбцов и 2" строк.
В первом столбце перечисляются все наборы из В" в лексикографиче- 384 б. БУЛЕВЫ ФУНКЦИИ оком порядке, а во втором — значения функции на наборах. Форма таблицы произвольной булевой функции приведена ниже (табл. 6.1). Таблица 6.1 В (Й+ 1)-й строке таблицы расположен набор аь ж (аьд...аь,„), являющийся двоичным кодом числа й (при О < й < 2" — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
