Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Булевы функции и булев куб

Булевы функции и булев куб


В дискретной математике большую роль играют конечные функции. Конечной функцией называют отображение одного конечного множества в другое. Важный класс таких функций образуют булевы функции.


Булева функция (от [math]n[/math] переменных) — это произвольное отображение вида


[math]f\colon \{0;1\}^n\to\{0;1\},[/math]
(6.1)

т.е. булева функция определена на множестве всех n-элементных (при [math]n\geqslant0[/math]) последовательностей (или n-компонентных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

С понятием булевой функции тесно связаны понятия булевой константы и булева переменного. (В литературе по теории булевых функций традиционно употребляется термин "булева переменная" (в женском роде).)


Булева константа — это индивидная константа с областью значений [math]\{0;1\}[/math]. Таким образом, существуют две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булева функция от 0 переменных (что вполне аналогично определению нульарной операции).


Булево переменное — это индивидное переменное с областью значений [math]\{0;1\}[/math], т.е. это переменное, которое может принимать только два значения: 0 и 1 (подобно тому, как действительное переменное принимает произвольное действительное значение, а комплексное переменное — произвольное комплексное значение). Тогда с использованием понятия булева переменного мы можем задать булеву функцию (6.1) записью [math]y=f(x_1,\ldots,x_n)[/math], в которой каждое булево переменное [math]x_i,~i=\overline{1,n}[/math], и функция / принимают два возможных значения: 0 и 1. Переменные [math]x_1,\ldots,x_n[/math] называют при этом переменными булевой функции [math]f[/math]. Фиксируя значение [math]\alpha_i\in\{0;1\}[/math] каждого переменного [math]x_i[/math], получаем кортеж [math]\widetilde{\alpha}= (\alpha_1, \ldots, \alpha_n)[/math] из множества [math]\{0;1\}^n[/math], называемый набором значений переменных [math]x_1,\ldots,x_n[/math], и соответствующее ему значение функции [math]f(\alpha_1, \ldots, \alpha_n)[/math], которое будет значением переменного [math]y[/math], сопоставленным заданным значениям переменных [math]x_1,\ldots,x_n[/math].


Подчеркнем, что, если специально не оговорено противное, в выражении [math]y=f(x_1,\ldots,x_n)[/math] все переменные предполагаются попарно различными, т.е. пробегающими каждое независимо от других множество [math]\{0;1\}[/math].


Понятию булевой функции можно придать иной смысл, понимая элементы множества [math]\{0;1\}[/math] как истинностные значения, а именно понимая единицу как "истину", а нуль как "ложь". Такие истинностные значения могут быть, как мы знаем, сопоставлены каждому высказыванию. Тогда булева функция есть некоторое правило, позволяющее каждому фиксированному набору истинностных значений, т.е. набору значений булевых переменных, сопоставить то или иное истинностное значение. Так может быть вычислено, например, истинностное значение сложного высказывания, составленного по определенным правилам из простых высказываний. Подобного рода сложные высказывания составляются с помощью логических операций: "или", "и", "если ..., то ..." и т.п. Указанная логическая интерпретация булевой функции позволяет понять, почему булево переменное часто называют логическим переменным (традиционный термин: "логическая переменная"), а булеву функцию — логической функцией (или функцией алгебры логики).


Кроме того, согласно определению, булева функция от [math]n[/math] переменных есть отображение n-й декартовой степени множества [math]\{0;1\}[/math] в множество [math]\{0;1\}[/math], т.е. не что иное, как n-арная операция на множестве [math]\{0;1\}[/math]. Тем самым логическая интерпретация булевой функции согласуется с ее алгебраической интерпретацией: булева функция есть операция (в алгебраическом смысле этого слова) на множестве истинностных значений. Тогда и понятие логической операции, которое было введено ранее, оказывается частным случаем общего понятия операции.


Будем обозначать через [math]\mathcal{P}_2[/math] множество всех булевых функций (для всех возможных значений [math]n[/math] числа переменных), а через [math]\mathcal{P}_{2,n}[/math] — множество всех булевых функций от [math]n[/math] переменных (для фиксированного [math]n[/math]). Из определения следует, что [math]\textstyle{\mathop{\mathcal{P}_2= \bigcup\limits_{n\geqslant0} \mathcal{P}_{2,n}}\limits^{\phantom{A}^{.}}}[/math].


Итак, областью определения любой булевой функции от [math]n[/math] переменных является множество [math]\{0;1\}^n[/math], т.е. булев куб размерности [math]n[/math]. Элементы булева куба [math]\{0;1\}^n[/math] называют n-мерными булевыми векторами (или наборами). Число всех элементов булева куба [math]\{0;1\}^n[/math] составляет [math]2^n[/math]. Элементы булева куба будем также называть его вершинами.


Булев куб [math]\{0;1\}^n[/math] является носителем булевой алгебры [math]\mathbb{B}^n[/math] (это же обозначение часто будем использовать и для соответствующего булева куба). Но в любой булевой алгебре [math]\mathcal{A}=(A,\lor,\land,\bold{0},\bold{1})[/math] определяется, как известно, естественное отношение порядка [math]\leqslant[/math] так, что для произвольных [math]a,b\in A[/math] соотношение [math]a\leqslant b[/math] выполняется тогда и только тогда, когда [math]a\lor b=b[/math] (или, что равносильно, [math]a\land b=a[/math]). Напомним, что булева алгебра [math]\mathbb{B}^n[/math] является не чем иным, как n-й декартовой степенью двухэлементной булевой алгебры [math]\mathbb{B}=(\{0;1\},\lor,\land,0,1)[/math].


Употребляются также термины: единичный куб размерности [math]n[/math], n-мерный единичный куб; вместо слова "куб" говорят также "гиперкуб".


Согласно общему принципу распространения отношения порядка на декартово произведение множествам. 4.5), для произвольных двух наборов [math]\widetilde{\alpha}= (\alpha_1,\ldots, \alpha_n)[/math] и [math]\widetilde{\beta}= (\beta_1,\ldots,\beta_n)[/math] из [math]\mathbb{B}^n[/math] имеет место [math]\widetilde{\alpha}\leqslant\widetilde{\beta}[/math] тогда и только тогда, когда [math]\alpha_i\leqslant\beta_i[/math] для каждого [math]i=\overline{1,n}[/math], то есть [math]\alpha_i\lor\beta_i=\beta_i[/math].


Другими словами, [math]\widetilde{\alpha}\leqslant\widetilde{\beta}[/math] тогда и только тогда, когда [math]\alpha_i=\beta_i[/math] или [math]\alpha_i=0[/math], а [math]\beta_i=1[/math] для каждого [math]i=\overline{1,n}[/math]. Если существует хотя бы одно [math]i[/math], для которого выполняется [math]\alpha_i=0,\,\beta_i=1[/math], то имеет место строгое неравенство [math]\widetilde{\alpha}<\widetilde{\beta}[/math]. В частности, если существует ровно одно такое [math]i[/math], то набор [math]\widetilde{\beta}[/math] доминирует над набором [math]\widetilde{\alpha}[/math], так как ясно, что в этом случае нельзя найти такой набор [math]\widetilde{\gamma}[/math], что [math]\widetilde{\alpha}< \widetilde{\gamma}< \widetilde{\beta}[/math].


Пример 6.1. В булевом кубе [math]\mathbb{B}^4[/math] имеем [math](0,0,1,1)< (1,0,1,1)< (1,1,1,1)[/math] причем второй из этих наборов доминирует над первым, а третий — над вторым (но, естественно, третий уже не доминирует над первым, а лишь строго больше его). Наборы же [math](0, 1,0, 1)[/math] и [math](1, 0, 1, 1)[/math] — несравнимые элементы, так как первая компонента второго набора больше первой компоненты первого набора, но зато вторая компонента первого набора больше второй компоненты второго набора. Подчеркнем также, что описанное сравнение наборов возможно только для фиксированной размерности и никак нельзя сравнивать наборы разных размерностей.




Булевый порядок


Рассмотренное отношение порядка на [math]\mathbb{B}^n[/math] будем называть булевым порядком.


Булев куб как упорядоченное множество, можно изобразить в виде диаграммы Хассе. На рис. 6.1 приведены диаграммы Хассе для булевых кубов размерностей от 0 до 4.


Диаграммы Хассе для булевых кубов размерностей от 0 до 4

Другой способ наглядного изображения булева куба основан на том, что диаграмма Хассе любого конечного упорядоченного множества [math]A[/math] может быть задана в виде ориентированной сети, так что дуга из вершины, сопоставленной элементу [math]x\in A[/math], ведет в вершину, сопоставленную элементу [math]{ y\in A}[/math], тогда и только тогда, когда [math]y[/math] доминирует над [math]x[/math] и каждый уровень сети состоит из вершин, сопоставленных попарно несравнимым элементам множества [math]A[/math] (т.е. элементам некоторой антицепи в [math]A[/math]). Входы сети сопоставлены минимальным, а выходы — максимальным элементам [math]A[/math].


Каждый уровень представляющей булев куб [math]\mathbb{B}^n[/math] сети состоит из всех вершин, соответствующих наборам, у которых ровно [math]k~(0\leqslant k\leqslant n)[/math] компонент отличны от нуля (множество всех таких наборов для фиксированного [math]k[/math] называют k-слоем булева куба [math]\mathbb{B}^n[/math]).


Сеть, служащую изображением булева куба размерности [math]n[/math], будем называть булевой n-сетъю или просто булевой сетью, если упоминание о размерности опускается. Так как булев куб имеет наименьший элемент — нулевой набор и наибольший элемент — единичный набор, то каждая булева сеть имеет единственный вход (помеченный нулевым набором) и единственный выход (помеченный единичным набором).


На рис. 6.2 приведено изображение булева куба [math]\mathbb{B}^4[/math] в виде сети.


Изображение булева куба B4 в виде сети

Помимо булева порядка полезно также ввести на булевом кубе другое отношение порядка, которое мы будем называть лексикографическим порядком, используя обозначение [math]\preceq[/math].


Пусть [math]\widetilde{\alpha},\widetilde{\beta}\in \mathbb{B}^n[/math] (для произвольного фиксированного [math]n[/math]). По определению, [math]\widetilde{\alpha}\preceq \widetilde{\beta}[/math], если


[math]\sum\limits_{i=1}^{n}(\alpha_i\cdot2^{n-i})\leqslant \sum\limits_{i=1}^{n} (\beta_i\cdot2^{n-i}).[/math]
(6.2)

Каждая из сумм в неравенстве (6.2) есть не что иное, как представление некоторого натурального числа (включая и нуль) в двоичной системе счисления (при числе разрядов, равных фиксированной размерности [math]n[/math]). На каждый булев вектор можно смотреть как на такое представление (двоичный код) натурального числа, и лексикографический порядок на булевом кубе [math]\mathbb{B}^n[/math] есть не что иное, как естественный числовой порядок на подмножестве [math]\{0,1,\ldots,2^{n-1}\}[/math] множества [math]\mathbb{N}\cup\{0\}[/math] (при условии, что числа заданы в двоичной системе счисления). Более строго: упорядоченное множество [math](\mathbb{B}^n,\preceq)[/math] изоморфно подмножеству [math]\{0,1,\ldots,2^{n-1}\}\subset \mathbb{N}\cup\{0\}[/math] с естественным числовым порядком.


Заметим, что отношение лексикографического порядка является, в отличие от булева порядка, отношением линейного порядка.


Пример 6.2. Набор [math]{ (1, 0,1)}[/math] как двоичный код числа [math]5=1\cdot2^1+ 0\cdot2^1+1\cdot2^0[/math] лексикографически больше набора [math](0,1,1)[/math], служащего двоичным кодом числа 3, но при этом указанные наборы не сравнимы по отношению булева порядка.


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




Грань булева куба


Гранью булева куба размерности [math]n-k[/math], где [math]n[/math] — размерность булева куба, называют множество наборов, имеющих не менее [math]k[/math] одинаковых компонент.


Грань размерности [math]n-k[/math] в [math]\mathbb{B}^n[/math] будет определена, если фиксировать [math]k[/math] номеров [math]1\leqslant i_1\leqslant\ldots\leqslant i_k\leqslant n[/math] и [math]k[/math] констант [math]\sigma_1,\ldots,\sigma_k[/math] из множества [math]\{0;1\}[/math]. Тогда грань, обозначаемая как [math]\mathbb{B}_{\sigma_1,\ldots,\sigma_k}^{n,i_1,\ldots,i_k}[/math], есть множество всех таких [math]\alpha\in \mathbb{B}^n[/math], что [math]\alpha_{i_1}= \sigma_1, \ldots,\alpha_{i_k}\sigma_k[/math]. При этом кортеж номеров [math](i_1,\ldots,i_k)[/math] называют направление ем грани [math]\mathbb{B}_{\sigma_1, \ldots,\sigma_k}^{n,i_1, \ldots,i_k}[/math]. Если число [math]n-k[/math], определяющее размерность грани, равно 1 (т.е. [math]k=n-1[/math]), то такую грань называют ребром булева куба [math]\mathbb{B}^n[/math]. Таким образом, ребро — это множество, состоящее из двух наборов, один из которых доминирует над другим (в смысле булева порядка). Другими словами, эти два набора отличаются друг от друга значением единственной компоненты. Для ребра булева куба будем использовать обозначение [math][\widetilde{\alpha},\widetilde{\beta}][/math], полагая, что второй набор доминирует над первым. Любая вершина булева куба считается гранью размерности 0.


Можно показать, что число всех граней размерности [math]n-k[/math] составляет [math]2^k\cdot C_{n}^{k}[/math].


Пример 6.3. В четырехмерном булевом кубе [math]\mathbb{B}^4[/math] направление трехмерной грани задается фиксированием одного из номеров от 1 до 4 и фиксированием значения соответствующей компоненты наборов, принадлежащих этой грани. На рис. 6.1 выделены ребра грани [math]\mathbb{B}_{0}^{4;1}[/math]. Эта грань состоит из восьми наборов:


[math]\begin{array}{llll}(0,0,0,0)&\qquad (0,0,0,1)&\qquad (0,0,1,0)&\qquad (0,0,1,1),\\[2pt] (0,1,0,0)&\qquad (0,1,0,1)&\qquad (0,1,1,0)&\qquad (0,1,1,1). \end{array}[/math]

На рис. 6.1 выделены все ребра булева куба [math]\mathbb{B}^3[/math], имеющие направление (1, 2).




Грани булева куба, имеющие одно и то же направление, называют параллельными. Две параллельные грани [math]\mathbb{B}_{\sigma_1,\ldots,\sigma_k}^{n,i_1,\ldots,i_k}[/math] и [math]\mathbb{B}_{\gamma_1,\ldots,\gamma_k}^{n,i_1,\ldots,i_k}[/math] называют соседними, если один из наборов [math](\sigma_1,\ldots,\sigma_k)[/math] и [math](\gamma_1,\ldots,\gamma_k)[/math] доминирует над другим. На рис. 6.1 грани [math]\mathbb{B}_{0}^{4;1}[/math] и [math]\mathbb{B}_{1}^{4;1}[/math] соседние, равно как и грани (ребра) [math]\mathbb{B}_{0;0}^{3;1;2}[/math] и [math]\mathbb{B}_{0;1}^{3;1;2}[/math]. Но ребра [math]\mathbb{B}_{1;0}^{3;1;2}[/math] и [math]\mathbb{B}_{0;1}^{3;1;2}[/math] не являются соседними.


Нетрудно догадаться, что каждая грань размерности [math]n-k[/math] булева куба [math]\mathbb{B}^n[/math] сама является булевым кубом размерности [math]n-k[/math] и содержит, следовательно, [math]2^{n-k}[/math] вершин. Точнее говоря, эта грань вместе с отношением порядка, индуцированным булевым порядком на [math]\mathbb{B}^n[/math], будет упорядоченным множеством, изоморфным булеву кубу [math]\mathbb{B}^{n-k}[/math] (с булевым порядком на нем). Поэтому часто грани булева куба называют его подкубами.


В то же время булев куб [math]\mathbb{B}^n[/math] изоморфно вкладывается (несколькими способами) в булев куб большей размерности, а именно булев куб [math]\mathbb{B}^n[/math] вкладывается (как грань) в булев куб [math]\mathbb{B}^{n+ k},~ k \geqslant 1[/math], столькими способами, сколько существует разных n-мерных граней в кубе размерности [math]n+k[/math], то есть [math]2^k\cdot C_{n+k}^{k}[/math] способами. Так, одномерный куб [math]\mathbb{B}[/math] вкладывается в двумерный [math]\mathbb{B}^2[/math] четырьмя способами — как одна из его четырех одномерных граней (т.е. как одно из его четырех ребер, см. рис. 6.1).


Договоримся впредь записывать конкретные наборы (элементы булева куба соответствующей размерности) без скобок и запятых, т.е. будем писать не [math](0,1,0,1)[/math], а [math]0101[/math] (если, конечно, это не ведет к недоразумениям).


В заключение найдем мощность множества всех булевых функций от [math]n[/math] переменных для фиксированного [math]n[/math]. Поскольку каждая булева функция отображает множество из [math]2^n[/math] элементов в двухэлементное множество, а мощность множества всех отображений из n-элементного множества в m-элементное равна, как известно, [math]m^n[/math], то мощность множества [math]\mathcal{P}_{2,n}[/math] равна [math]2^{2^n}[/math]. В частности, при [math]n=0[/math] получаем две булевы константы: 0 и 1.


Замечание 6.1. Поскольку булева функция от [math]n[/math] переменных является в то же время и n-арной операцией на множестве [math]\{ 0, 1\}[/math], то при [math]n=0[/math] получаем нульарную операцию. Ясно, что на множестве [math]\{ 0, 1\}[/math] существуют две нульарные операции: 0 и 1, которые есть не что иное, как нуль и единица двухэлементной булевой алгебры.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved