Булевы функции Основные понятия

Набор (₁,₂,…,_n), где _i{0,1}, 1in, называется булевым или двоичным набором (вектором) длины n. Элементы набора называют компонентами или координатами. Кратко набор (₁,₂,…,_n) обозначают или . Весом или нормой |||| набора называют число его координат, равных единице, т.е. .

Множество всех двоичных наборов длины n образует n-мерный булев (или двоичный) куб, который также называют n-мерным единичным кубом и обычно обозначают или . Наборы (₁,₂,…,_n) называют вершинами куба . Множество всех вершин куба, имеющих вес k, называется k-м слоем куба (обозначение ). Каждому двоичному набору можно сопоставить число – номер набора. Набор является двоичным разложением своего номера .

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

Н

рис. 1

аборы и из называются соседними, если (,)=1, и противоположными, если (,)=n.

Говорят, что набор предшествует набору (или не больше ), и обозначают , если _i_i для всех i=1,..,n. Наборы и называются сравнимыми, если или. В противном случае наборы называются несравнимыми. Говорят, что набор непосредственно предшествует набору , если  и (,)=1.Отношение предшествования  является частичным порядком на множестве . На рис. 1 приведены диаграммы частично упорядоченных множеств B²,B³,B⁴.

1. Номер набора (0,1,0) из B³ равен 2, вес – 1, соседними для него являются наборы (1,1,0), (0,1,1), (0,0,0), противоположным – набор (1,0,1). Наборы (0,0,0) и (1,1,1) сравнимы с набором (0,1,0), а набор (1,0,0) – несравним.

Отображение f:{0,1} называется булевой функцией от n переменных. Функция, принимающая только два значения – 0 и 1, называется предикатом (при этом переменные могут принадлежать множествам произвольной природы). Набор символов переменных булевой функции f(x₁,x₂,..,x_n) будем обозначать или . Обозначим через множество всех булевых функций, а через – множество всех булевых функций от n переменных.

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

Таблица значений булевой функции f от n переменных имеет следующий вид:

x1 x2 … xn-1 xn	f(x1,x2,…,xn-1,xn)
0 0 … 0 0	f(0,0,…,0,0)
0 0 … 0 1	f(0,0,…,0,1)
0 0 … 1 0	f(0,0,…,1,0)
0 0 … 1 1	f(0,0,…,1,1)
…	…
1 2 … n-1 n	f(1,2,…,n-1,n)
…	…
1 1 … 1 1	f(1,1,…,1,1)

1. ||=.

Булева функция также может быть задана с помощью вектора значений на всевозможных наборах значений переменных, упорядоченных по их номерам: _f=(f(0,0,…,0,0), f(0,0,…,0,1), …, f(1,1,…,1,1)).

Переменная x_i булевой функции f(x₁,x₂,…,x_n-1,x_n) называется существенной, если найдутся такие значения ₁,₂,…,_i-1,_i+1,…,_n-1,_n, что

f(₁,₂,…,_i-1,0,_i+1,…,_n-1,_n)f(₁,₂,…,_i-1,1,_i+1,…,_n-1,_n)

Если переменная x_i не является существенной, то ее называют фиктивной или несущественной для данной функции.

2. Рассмотрим функцию f от трех переменных, заданную таблицей значений

x1 x2 x3	f
0 0 0	0
0 0 1	1
0 1 0	0
0 1 1	1
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	0

Векторная запись этой функции – f()=(01011010). Переменные x₁ и x₃ являются для нее существенными (т.к. f(0,0,0)f(1,0,0), f(0,1,0)f(0,1,1)), а x₂ – фиктивной.

Функции f и g называют равными, если одну из них можно получить из другой путем изъятия или добавления несущественных переменных.

Булевы функции, заданные приведенными ниже таблицами, будут считаться элементарными.

	тождественный 0	тождественная 1	отрицание x	коъюнкция	дизюнкция	сложение по mod2	эквивалентность	импликация	штрих Шеффера	стрелка Пирса
x y	0	1	x	xy	xy	xy	xy	xy	x|y	xy
0 0	0	1	1	0	0	0	1	1	1	1
0 1	0	1	1	0	1	1	0	1	1	0
1 0	0	1	0	0	1	1	0	0	1	0
1 1	0	1	0	1	1	0	1	1	0	0

Функции тождественный ноль и тождественная единица не имеют существенных переменных. Функция отрицания x переменной x (читается «не x») может обозначаться . Функция конъюнкции xy (читается «x и y») может обозначаться min(x,y), xy или xy, xy. Функция дизъюнкции xy (читается «x или y») может обозначаться max(x,y). Часто эту функцию называют логическим сложением. Функцию сложения по mod2 xy (читается «x плюс y») иногда называют разделяющим или. Функция эквивалентности или эквиваленции x~y (читается «x эквивалентно y») может обозначаться xy или xy. Функцию импликации xy (читается «из x следует y») часто называют логическим следованием. Функция штрих Шеффера x|y в технической литературе называется «не-и» или антиконъюнкцией (читается «x и y не совместны»). Функция стрелка Пирса xy в технической литературе называется «не-или» или антидизъюнкцией (читается «ни x, ни y»).

С

Рисунок 1

имволы &,,,~,,|,, участвующие в обозначениях элементарных функций, называют логическими связками. Зафиксируем приоритет введенных связок как показано на рис.1.

Перечислим свойства элементарных функций:

0=1, 1=0, (x)=x, x1=1x=x, x0=0x=x, x0=0x=xx=0, x1=1x=x, 1x=x1=xx=1, 0x=x0=x, xy=xy, x|y=(xy) =xy1, xy=(xy)=xyxy1, xy=(xy)=xy1=xyxy, xy=xyxy, xy=xyxy.

Пусть Б. Дадим определение формулы над базисом Б.

Базис индукции. Любая функция из Б является формулой над Б.

Индуктивный переход. Если A₁,…A_m – формулы или символы переменных, а f(x₁,…x_m)Б, то суперпозиция f(A₁,…A_m) тоже является формулой над Б.

3. (xy)(xy)z – формула над Б={,,}.

Запись A[f₁,…,f_k], где f₁,…,f_kБ, будет означать, что формула A над Б получена из базисных функций f₁,…,f_n. Запись A(x₁,…,x_n) будет означать, что формула A построена на множестве переменных x₁,…x_n. Формулы, используемые при построении формулы A, называются ее подформулами.

Пусть даны формулы A[f₁,…,f_k] и B[g₁,…,g_k], говорят, что формулы A и B имеют одинаковое строение, если B можно получить из A с помощью подстановки .

4. Формулы над {,} и над {,} имеют одинаковое строение.

Далее строение формулы будет обозначаться буквой S и каждая формула A будет однозначно определяться строением S и упорядоченным набором функций f₁,…,f_k. Запись  A=S[f₁,…,f_k].

Если формула A(x₁,…x_n) совпадает с базисной функцией f(x₁,…x_n), то говорят, что формула A(x₁,…,x_n) реализует функцию f(x₁,…x_n) и записывают A(x₁,…x_n)=f(x₁,…x_n). Пусть A(x₁,…x_n)=f(A₁,…,A_m), где fБ, а A₁,…A_m – либо символы переменных, либо формулы над Б. Тогда каждая A_i реализует некоторую функцию f_i из P₂. Тогда формула A реализует функцию f₀=f(f₁,…,f_m). Функция f₀ при этом называется суперпозицией функций f,f₁,…,f_m, а процесс получения функции f₀  операцией суперпозиции.

Две формулы A₁ и A₂ над Б называют эквивалентными (обозначение A₁=A₂), если реализуемые этими формулами булевы функции равны.