3.2.3. Самодвойственные функции
О
пределение.
Для функции f(x1,x2,…,xn)
функция называется двойственной к
ней.
О
бозначим
двойственную функцию как f*.
Пример. Для функции (ху) двойственной будет функция (ху) = x v y.
Можно показать, что двойственной функцией к f* будет функция f,
значит для ху двойственной будет ху.
Двойственной к х будет функция, равная х, двойственной к 0 будет 1.
Определение. Функция называется самодвойственной, если она равна своей двойственной.
Переменная x служит примером самодвойственной функции, так же как и функция инверсии переменной.
Свойства самодвойственных функций.
Самодвойственная функция полностью определяется своим видом на верхней половине таблицы истинности. Действительно, если, например, значение функции на набореТаблица 3.1
х
у
f1
f2
f3
f4
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
1
0
1
1
1
1
0
0
<1, 2, …, n> равно 0, то значение функции на инверсном наборе <1,2, …,n> должно быть равно 1.Из первого свойства вытекает, что число различных функций от n переменных равно 2m, где m=2n-1.
Построим все функции от двух переменных. Их будет 4 в соответствии с возможными значениями на верхней половине таблицы: 00,01,10,11. Эти функции приведены в табл. 3.1. Как видно из таблицы, первые две функции совпадают с переменными, две последние – с инверсиями переменных. Отсюда следует свойство: самодвойственных функций, существенно зависящих ровно от двух переменных, нет.
СДНФ самодвойственной функции будет иметь ровно 2n-1 конъюнкций
Суперпозиция самодвойственных функций будет функциейсамодвойственной. Множество самодвойственных функций образуют класс, который принято обозначать как D. Базисом класса является функция трёх переменных {xy xz yz}.
3.2.4. Линейные функции
Рассмотрим класс функций, порождённых множеством F={xy, xy, 1}.
Из того, что x1=х, следует, что в данном базисе реализуется инверсия, которая вместе с конъюнкцией даёт возможность построить любую функцию. Значит, данный базис порождает класс всех функций – класс С.
Сравним таблицы функции сложения по модулю два и дизъюнкции (табл.3.2)
Таблица 3.2
а |
в |
ав |
ав |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Из таблицы видно, что аb = (а b) аb.
Если а и в такие, что имеет место равенство ав = 0, то такие переменные называются ортогональными. Для ортогональных переменных ав = (ав).
Если рассматривать СДНФ любой функции, то можно показать, что в ней любая пара конъюнкций ортогональна. Это приводит к следующему алгоритму построения записи функции в рассматриваемом базисе:
записать функцию в СДНФ;
заменить в СДНФ символы дизъюнкции на символы сложения по модулю два;
заменить все инверсии по формуле х = (х1);
раскрыть скобки, пользуясь свойством дистрибуции х(yz) = xyxz;
сделать сокращения, используя свойство хх = 0, х0= х.
В результате получается запись функции в форме, которую представим в общем виде как
f=C0 C1x1 C2x2 … Cnxn C(n+1)x1x2…Cmx1x2…xn, где С0, С1, С2,…Cm принимают значения 0 или 1.
Это представление называется полиномом Жегалкина, а алгебра с сигнатурой {xy, xy, 1} – алгеброй Жегалкина.
Пример. Построим полином Жегалкина для функции импликации. По её таблице запишем СДНФ этой функции:
ав =ав ав ав, после замены дизъюнкций на сложение по модулю два имеем: ав =ав ав ав = (а1)(в1)(а1)вав = =авав1аввав = ава1.
Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций.
Общий вид линейной функции f = C0 C1x1 C2x2 … Cnxn.
Таким образом, число различных линейных функций от не более чем n переменных определяется формулой N = 2n+1.
Суперпозиция линейных функций есть функция линейная, следовательно, множество линейных функций образует класс линейных функций, обозначаемый как L.
Базисом класса L служит множество {xy, 1}.