Основные понятия

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

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

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

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

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

Говорят, что набор предшествует набору (или не больше ), и обозначают p , если a_i£b_i для всех i=1,..,n. Наборы и называются сравнимыми, если p или p . В противном случае наборы называются несравнимыми. Говорят, что набор непосредственно предшествует набору , если p и r( , )=1.Отношение предшествования p является частичным порядком на множестве . На рис. 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 переменных имеет следующий вид:

Лемма 1.| |= .

Булева функция также может быть задана с помощью вектора значений на всевозможных наборах значений переменных, упорядоченных по их номерам: a_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) называется существенной, если найдутся такие значения a₁,a₂,…,a_i-1,a_i+1,…,a_n-1,a_n, что

f(a₁,a₂,…,a_i-1,0,a_i+1,…,a_n-1,a_n)¹f(a₁,a₂,…,a_i-1,1,a_i+1,…,a_n-1,a_n)

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

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

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

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

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

Функции тождественный ноль и тождественная единица не имеют существенных переменных. Функция отрицания Ø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.

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

Ø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₂), если реализуемые этими формулами булевы функции равны.

Основные эквивалентности:

Законы коммутативностиx*y=y*x, где *Î{&,Ú,Å,~,|,¯}.

Законы ассоциативности (x*y)*z=x*(y*z), где *Î{&,Ú,Å,~}.

Законы дистрибутивностиx(yÚz)=xyÚxz, (xÚy)(xÚz)=xÚyz.

Законы идемпотентности x&x=x, xÚx=x,

Правила де МорганаØ(x&y)=ØxÚØy, Ø(xÚy)=Øx&Øy.

Правила поглощенияxÚxy=x, x(xÚy)=x.

Правила склеиванияxKÚØxK=K, xK₁ÚØxK₂=xK₁ÚØxK₂ÚK₁K₂
(K, K₁,K₂ – произвольные конъюнкции).

В силу коммутативности и ассоциативности связок &, Ú, Å справедливы следующие равенства

;

;

.

Задачи

1.Найти номер и вес двоичного набора

1.1.(011011);

1.2.(010101);

1.3.(110110);

1.4.(101010);

1.5.(101101);

1.6.(101100);

1.7.(010111);

1.8.(011001);

1.9.(101110);

1.10.(110010).

2.Найти двоичный набор длины 8, номер которого равен

2.1.123;

2.2.117;

2.3.105;

2.4.113;

2.5.100;

2.6.97;

2.7.88;

2.8.110;

2.9.91;

2.10.108.

3.На множестве наборов A из B⁵ указать естественный частичный порядок p. Выяснить, есть ли в множестве A соседние и противоположные наборы, и, если они имеются, выписать их.

3.1.A={(00001),(00011),(00100),(01001),(10011),(11001),(11110)};

3.2.A={(00101),(01000),(01100),(10000),(10101),(11010),(11100)};

3.3.A={(00000),(01011),(10100),(10110),(11000),(11101),(11111)};

3.4.A={(00010),(01010),(01101),(01110),(10010),(10111),(11101)};

3.5.A={(00110),(00111),(01010),(01111),(10001),(11001),(11011)};

3.6.A={(00001),(00100),(00101),(01011),(01110),(10001),(11011)};

3.7.A={(00000),(00111),(01101),(10000),(10101),(11000),(11111)};

3.8.A={(00010),(00011),(01001),(01111),(10000),(10111),(11100)};

3.9.A={(01000),(01100),(10011),(10100),(10110),(10111),(11010)};

3.10.A={(00110),(01001),(01010),(10010),(10110),(11001),(11011)}.

4.Построить таблицы функций, реализуемых формулами:

4.1. ;

4.2. ;

4.3. ;

4.4. ;

4.5. ;

4.6. ;

4.7. ;

4.8. ;

4.9. ;

4.10. .

5.Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы A и B:

5.1.A= , B= ;

5.2.A= , B= ;

5.3.A= , B= ;

5.4.A= , B= ;

5.5.A= , B= ;

5.6.A= , B= ;

5.7.A= , B= ;

5.8.A= , B= ;

5.9.A= , B= ;

5.10.A= , B= .

6.Используя основные эквивалентности, доказать эквивалентность формул A и B:

6.1.A= , B= ;

6.2.A= , B= ;

6.3.A= , B= ;

6.4.A= , B= ;

6.5.A= , B= ;

6.6.A= , B= ;

6.7.A= , B= ;

6.8.A= , B= ;

6.9.A= , B= ;

6.10.A= , B= .

7.Указать все фиктивные переменные функции f:

7.1.a_f=(1011010110110101);

7.2.a_f=(0101111101011111);

7.3.a_f=(1100110000110011);

7.4.a_f=(0011110000111100);

7.5.a_f=(0110110110110111);

7.6.a_f=(0111011110101010);

7.7.a_f=(1100110001100101);

7.8.a_f=(1100110000111100);

7.9.a_f=(1000110110001101);

7.10.a_f=(0011001110111011);

8.Указать все существенные переменные функции f:

8.1. ;

8.2. ;

8.3. ;

8.4. ;

8.5.

8.6. ;

8.7. ;

8.8. ;

8.9. ;

8.10. .