Определение.Двойственной для функции f(x1, x2, …, xn) называется функция
Пример 44.
Построить функцию, двойственную данной:
1. f = x Ú y;
2. f = x® y.
Решение.
1.
2.
Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция тоже самодвойственна.
Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
Противоположными называются те наборы, которые в сумме дают двоичный код числа (2n-1).
Пример 45.
Выяснить являются ли функции самодвойственными:
1. ;
2. f = 01110010.
Решение.
1. Строим таблицу истинности для данной функции (табл. 55):
Таблица 55
№
x
y
z
0
1
2
3
4
5
6
7
Так как наборы (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
1
2
3
4
5
6
7
Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.
Теорема. Класс S = {f | f = f*}самодвойственных функций замкнут относительно суперпозиций.
2.2.3.2. Линейные функции
Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).
Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе <i1, …, ik> все аij (j = 1, …, k) различны, aj Î {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
Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).
Таблица 58
Слагаемые полинома Жегалкина
x1
x2
x3
f
g
Треугольник Паскаля
1
0
0
0
1
1
f = 1 0 0 1 1 1 1 0
x3
0
0
1
0
1
1 0 1 0 0 0 1
x2
0
1
0
0
1
1 1 1 0 0 1
x2x3
0
1
1
1
0
0 0 1 0 1
x1
1
0
0
1
0
0 1 1 1
x1 x3
1
0
1
1
1
1 0 0
x1 x2
1
1
0
1
1
1 0
x1 x2 x3
1
1
1
0
1
1
Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.
Для данной функции многочлен Жегалкина имеет вид:
f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.
Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:
f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.
Булева функция из рассмотренного выше примера не является линейной.
Теорема. Класс L = {f | f = a0+a1x1+…+anxn, aiÎ{0, 1}} линейных функций замкнут относительно суперпозиций.