Файл: Булевы функции.doc

В результате МДНФ имеет вид:

---

2.2.3. Полные системы булевых функций

Определение. Система булевых функций f₁,f₂, …, f_n называется полной, если любая булева функция может быть выражена через функции f₁,f₂, …, f_n с помощью суперпозиций.

Пример 42.

Исходя из определения полной системы булевых функций, следует, что система {, , } является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.

Дадим определение суперпозиции функций.

Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1 (или элементарной суперпозицией) функций f₁, f₂, …, f_m, если f может быть получена одним из следующих способов:

1. переименованием некоторой переменной x_j какой-нибудь функции f_i, т. е. f=f_i(x₁, …, x_j-1, y, x_j+1, …, x_k1), где y может совпасть с любой переменной;

2. подстановкой некоторой функции f_l (1 l m) вместо какой-либо переменной x_j любой из функций fiK⁰, т. е. f=f_i(x₁, …, x_j-1, f_l(x₁, x₂, …, x_k1), x_j+1, ..., x_ki).

Определение. Суперпозиции ранга 1 образуют класс функций К¹. Класс функций, получающихся из функций класса К^r-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функций K^r суперпозиций ранга r. Суперпозициями функций из К⁰ называются функции, входящие в какой-либо из классов K^r.

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

---

Пример 43.

1. Четыре булевы функции одной переменной (f₁ = 00, f₂ = 11, f₃ = 01, f₄ = 10) образуют замкнутый класс.

2. Булевы функции f₁ = x и образуют замкнутый класс.

Теорема. Класс T₀={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.

Теорема. Класс T₁={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.

2.2.3.1. Двойственные функции

Определение. Двойственной для функции f(x₁, x₂, …, x_n) называется функция

Пример 44.

Построить функцию, двойственную данной:

1. f = x  y;

2. f = x y.

Решение.

1.

2.

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

Утверждение. Если функция f(x₁, x₂, …, x_n) самодвойственна, то функция тоже самодвойственна.

Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.

Противоположными называются те наборы, которые в сумме дают двоичный код числа (2ⁿ-1).

Пример 45.

Выяснить являются ли функции самодвойственными:

1. ;

2. f = 01110010.

Решение.

1. Строим таблицу истинности для данной функции (табл. 55):

Таблица 55

№	x	y	z
0	0	0	0	1	0	1	1
1	0	0	1	1	0	0	1
2	0	1	0	1	1	1	1
3	0	1	1	1	1	0	0
4	1	0	0	0	1	1	1
5	1	0	1	0	1	0	0
6	1	1	0	0	0	1	1
7	1	1	1	0	0	0	1

---

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.

2. Строим таблицу значений для функции f = 01110001 (табл. 56).

Таблица 56

№	x	y	z	f(x, y, z)
0	0	0	0	0
1	0	0	1	1
2	0	1	0	1
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	0
7	1	1	1	1

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.

Теорема. Класс S = {f | f = f*}самодвойственных функций замкнут относительно суперпозиций.

---

2.2.3.2. Линейные функции

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе <i₁, …, i_k> все а_ij (j = 1, …, k) различны, a_j  {0, 1}.

Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Пример 46.

Построить многочлен Жегалкина для функции f=10011110.

Решение.

Алгоритм построения многочлена Жегалкина:

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Слагаемые полинома Жегалкина	x1	x2	x3	f	g	Треугольник Паскаля
1	0	0	0	1
x3	0	0	1	0
x2	0	1	0	0
x2x3	0	1	1	1
x1	1	0	0	1
x1 x3	1	0	1	1
x1 x2	1	1	0	1
x1 x2 x3	1	1	1	0

---