Понятие булевой функции. Булев куб

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

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

f: {0, 1}_n → {0, 1},     (6.1)

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

С понятием булевой функции тесно связаны понятия булевой константы и булева переменного*.

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

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

Булево переменное - это uндuвuдное переменное с областью значений {0, 1}, т.е. это переменное, которое может принимать только два значения: 0 и 1 (подобно тому, как действительное переменное принимает произвольное действительное значение, а комплексное переменное - произвольное комплексное значение). Тогда с использованием понятия булева переменного мы можем задать булеву функцию (6.1) записью у = f(x₁, ... ,x_n), в которой каждое булево переменное x_i, i = 1,n, и функция f принимают два возможных значения: 0 и 1. Переменные x₁, ... ,x_n называют при этом переменными булевой фунпцuu f. Фиксируя значение α_i ∈ {0, 1} каждого переменного x_i, получаем кортеж α˜ = (α₁, ... , α_n) из множества {0, 1}ⁿ, называемый набором значений переменных x₁, ... ,x_n, и соответствующее ему значение функции f(α₁, ... , α_n), которое будет значением переменного у, сопоставленным заданным значениям переменных x₁, ... ,x_n.

Подчеркнем, что, если специально не оговорено противное, в выражении у = f(x₁, ... ,x_n) все переменные предполагаются попарно различными, т.е. пробегающими каждое независимо от других множество {0, 1}.

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

* Традиционный термин: "логическая переменная".

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

Будем обозначать через Р множество всех булевых функций (для всех возможных значений n числа переменных), а через Р_2,n - множество всех булевых функций от n переменных (для фиксированного n).

Из определения следует, что

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

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

Булев куб {0, 1}ⁿ является носuтелем булевой алгебры Bⁿ (это же обозначение часто будем использовать и для соответствующего булева куба). Но в любой булевой алгебре А = (А, ∨, ∧, 0, 1) определяется, как известно, естественное отношенuе порядка ≤ так, что для произвольных а, b ∈ А соотношение а ≤ b выполняется тог да и только тогда, когда а ∨ b = b (или, что равносильно, а ∧ b = а). Напомним (см. 3.4), что булева алгебра Bⁿ является не чем иным, как n-й декартовой степенью двухэлементной булевой алгебры B = ({0, 1}, ∨, ∧, 0, 1). Согласно общему принципу распространения отношения порядка на декартово произведение множеств (см. 4.5), для произвольных двух наборов α˜ = (α₁, ... , α_n) и β˜ = (β₁, ... , β_n) из Bⁿ имеет место α˜ ≤ β˜. тогда и только тогда, когда α_i ≤ β_i для каждого i = 1,n, т.е. α_i ∨ β_i = β_i.

Другими словами, α˜ ≤ β˜ тогда и только тогда, когда α_i = β_i или α_i = 0, а β_i = 1 для каждого i = 1,n. Если существует хотя бы одно i, для которого выполняется α_i = 0, а β_i = 1, то имеет место строгое неравенство α˜ < β˜. В частности, если существует ровно одно такое i, то набор β˜ доминирует над набором α˜, так как ясно, что в этом случае нельзя найти такой набор γ˜, что α˜ < γ˜ < β˜.

Пример 6.1. В булевом кубе B⁴

(0, 0, 1, 1) < (1, 0, 1, 1) < (1, 1, 1, 1),

причем второй из этих наборов доминирует над первым, а третий - над вторым (но, естественно, третий уже не доминирует над первым, а лишь строго больше его). Наборы же (0, 1, 0, 1) и (1, 0, 1, 1) - несравнимые элементы, так как первая компонента второго набора больше первой компоненты первого набора, но зато вторая компонента первого набора больше второй компоненты второго набора. Подчеркнем также, что описанное сравнение наборов возможно только для фиксированной размерности и никак нельзя сравнивать наборы разных размерностей. #

Рассмотренное отношение порядка на Bⁿ будем называть булевым порядком.

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

Другой способ наглядного изображения булева куба основан на том, что диаграмма Хассе любого конечного упорядоченного множества А может быть задана в виде ориентированной сети, так что дуга из вершины, сопоставленной элементу х ∈ А,

ведет в вершину, сопоставленную элементу у ∈ А, тогда и только тогда, когда у доминирует над х и каждый уровень сети состоит из вершин, сопоставленных попарно несравнимым элементам множества А (т.е. элементам некоторой антицепи в А). Входы сети сопоставлены минимальным, а выходы - максимальным элементам А.

Каждый уровень представляющей булев куб Bⁿ сети состоит из всех вершин, соответствующих наборам, у которых ровно k (0 ≤ k ≤ n) компонент отличны от нуля (множество всех таких наборов для фиксированного k называют k-слоем булева куба Bⁿ).

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

На рис. 6.2 приведено изображение булева куба B⁴ в виде сети.

Помимо булева порядка полезно также ввести на булевом кубе другое отношение порядка, которое мы будем называть лексикографическим порядком, используя обозначение ⪯. Пусть α˜, β˜ ∈ Bⁿ (для произвольного фиксированного n). По определению, α˜ ⪯ β˜, если

Каждая из сумм в неравенстве (6.2) есть не что иное, как представление некоторого натурального числа (включая и нуль) в двоичной системе счисления (при числе разрядов, равных фиксированной размерности n). На каждый булев вектор можно смотреть как на такое представление (двоичный код) натурального числа, и лексикографический порядок на булевом кубе Bⁿ есть не что иное, как естественный числовой nорядок на подмножестве {0, 1, ... , 2^n-1} множества ℕ ∪ {0} (при условии, что числа заданы в двоичной системе счисления)*.

* Более строго: упорядоченное множество (Bⁿ, ⪯) изоморфно подмножеству {0, 1, ... , 2^n-1} ⊂ ℕ ∪ {0} с естественным числовым порядком.

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

Пример 6.2. Набор (1, 0, 1) как двоичный код числа 5 = = 1 · 2² +0 · 2¹ + 1 · 2⁰ лексикографически больше набора (0, 1, 1), служащего двоичным кодом числа 3, но при этом указанные наборы не сравнимы по отношению булева порядка. #

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

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

Грань размерности n - k в Bⁿ будет определена, если фиксировать k номеров 1 ≤ i₁ ≤ ... ≤ i_k ≤ n и k констант σ₁,...,σ_k из множества {0, 1}. Тогда грань, обозначаемая как B^{n,i₁,...,i_kσ₁,...,σ_k} , есть множество всех таких α ∈ Bⁿ, что α_i1 = σ₁,...,σ_ik = σ_k. При этом кортеж номеров (i₁, ..., i_k) называют направлением грани B^{n,i₁,...,i_kσ₁,...,σ_k} . Если число n -k, определяющее размерность грани, равно 1 (т.е. k = n -1), то такую грань называют ребром булева куба Bⁿ . Таким образом, ребро - это множество, состоящее из двух наборов, один из которых доминирует над другим (в смысле булева порядка). Другими словами, эти два набора отличаются друг от друга значением единственной компоненты. Для ребра булева куба будем использовать обозначение [а, ,8], полагая, что второй набор доминирует над первым. Любая вершина булева куба считается гранью размерности 0.

Можно показать, что число всех граней размерности n - k составляет 2^k · C^kn .

Пример 6.3. В четырехмерном булевом кубе В⁴ направление трехмерной грани задается фиксированием одного из номеров от 1 до 4 и фиксированием значения соответствующей компоненты наборов, принадлежащих этой грани. На рис. 6.1 выделены ребра грани В^4,10 . Эта грань состоит из восьми наборов:

(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),

(0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1).

На рис. 6.1 выделены все ребра булева куба В³, имеющие направление (1, 2). #

Грани булева куба, имеющие одно и то же направление, называют параллельными. Две параллельные грани В^{n,i₁,...,i_kσ₁,...,σ_k} и В^{n,i₁,...,i_kγ₁,...,γ_k} называют соседними, если один из наборов (σ₁, ..., σ_k) и (γ₁, ..., γ_k) доминирует над другим. На рис. 6.1 грани B^4,10 и B^4,11 соседние, равно как и грани (ребра) B^3,1,20,0 и B^3,1,20,1 . Но ребра B^3,1,21,0 и B^3,1,20,1 не являются соседними.

Нетрудно догадаться, что каждая грань размерности n - k булева куба Вⁿ сама является булевым кубом размерности n - k и содержит, следовательно, 2^n-k вершин. Точнее говоря, эта грань вместе с отношением порядка, ииндуцuрованным булевым порядком на Вⁿ, будет упорядоченным множеством, и изоморфным булеву кубу В^n-k (с булевым порядком на нем). Поэтому часто грани булева куба называют его подкубами.

В то же время булев куб Вⁿ изоморфно вкладывается (несколькими способами) в булев куб большей размерности, а именно булев куб Вⁿ вкладывается (как грань) в булев куб В^n+k, k ≥ 1, столькими способами, сколько существует разных n-мерных граней в кубе размерности n + k, т.е. 2^k · C^kn+k     способами. Так, одномерный куб B вкладывается в двумерный B² четырьмя способами - как одна из его четырех одномерных граней (т.е. как одно из его четырех ребер, см. рис. 6.1).

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

В заключение найдем мощность множества всех булевых функций от n переменных для фиксированного n. Поскольку каждая булева функция отображает множество из 2ⁿ элементов в двухэлементное множество, а мощность множества всех отображений из n-элементного множества в m-элементное равна, как известно, mⁿ, то мощность множества P_2,n равна 2²ⁿ. В частности, при n = 0 получаем две булевы константы: 0 и 1.

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