4.6.2. Самодвойственные функции

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

Обозначим двойственную функцию какf*.

Пример. Для функции (х×у) двойственной будет функция (`хÚ`у) =xÚy.

Можно показать, что двойственной функцией к f* будет функция f, значит для хÚу двойственной будет х×у.

Двойственной к х будет функция, равная х, двойственной к 0 будет 1.

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

Переменная х служит примером самодвойственной функции, так же как и функция инверсии переменной.

Свойства самодвойственных функций.

1. Самодвойственная функция полностью определяется своим видом на верхней половине таблицы истинности. Действительно, если, например, значение функции на наборе <a₁, a₂, …, a_n> равно 0, то значение функции на инверсном наборе <`a<sub>1</sub>,`a₂, …,`a_n> должно быть равно 1.

2. Из первого свойства вытекает, что число различных функций от n переменных равно 2^m, где m=2^n-1.

3. Таблица 4.11
   х	у	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

   Построим все функции от двух переменных. Их будет 4 в соответствии с возможными значениями на верхней половине таблицы: 00,01,10,11. Эти функции приведены в таблице 4.11. Как видно из таблицы, первые две функции совпадают с переменными, две последние – с инверсиями переменных. Отсюда следует свойство: самодвойственных функций, существенно зависящих ровно от двух переменных нет.

4. СДНФ самодвойственной функции будет иметь ровно 2^n-1 конъюнкций.

5. Суперпозиция самодвойственных функций будет функция самодвойственная. Множество самодвойственных функций образуют класс, который принято обозначать как D. Базисом класса является функция трёх переменных {x×`y Úx×`z Ú`y×`z}.

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

Рассмотрим класс функций, порождённый множеством F={x×y, xÅy, 1}.

Из того, что xÅ1=`х, следует, что в данном базисе реализуется инверсия, которая вместе с конъюнкцией даёт возможность построить любую функцию. Значит, данный базис порождает класс всех функций – класс С.

Сравним таблицы функции сложения по модулю два и дизъюнкции (табл.4.12).

Таблица 4.12

a	b	aÚb	aÅb
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	0

Из таблицы видно, что аÚb=(а Å b) Úа×b.

Если а и b такие, что имеет место равенство a×b=0, то такие переменные называются ортогональными. Для ортогональных переменных aÚb=(aÅb).

Если рассматривать СДНФ любой функции, то можно показать, что в ней любая пара конъюнкций ортогональна. Это приводит к следующему алгоритму построения записи функции в рассматриваемом базисе.

• записать функцию в СДНФ;

• заменить в СДНФ символы дизъюнкции на символы сложения по модулю два;

• заменить все инверсии по формуле `х =(хÅ1);

• раскрыть скобки, пользуясь свойством дистрибуции х×(yÅz)=x×yÅx×z;

• сделать сокращения, используя свойство хÅх=0, хÅ0=x.

В результате получается запись функции в форме, которую представим в общем виде

f=C₀ ÅC₁×x₁Å C₂×x₂ Å… ÅC_n×x_nÅ C(n+1)×x₁×x₂Å…ÅC_m×x₁×x₂×…×x_n , где С₀,С₁,С₂,…, принимают значения 0 или 1.

Это представление называется полиномом Жегалкина, а алгебра с сигнатурой {F={x×y, xÅy, 1}} – алгеброй Жегалкина.

Пример. Построим полином Жегалкина для функции импликации. По её таблице истинности запишем СДНФ этой функции

a®b =`a`b Ú`abÚ ab,

после замены дизъюнкций на сложение по модулю два имеем a®b = =`a`b Å`abÅ ab = (aÅ1)(bÅ1)Å(aÅ1)×bÅa×b = a×bÅaÅbÅ1Åa×bÅbÅa×b = = a×bÅaÅ1.

Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций. Общий вид линейной функции f = C₀ ÅC₁×x₁Å C₂×x₂ Å… ÅC_n×x_n.

Число различных линейных функций от не более чем n переменных определяется формулой N = 2ⁿ⁺¹.

Суперпозиция линейных функций есть функция линейная, следовательно, множество линейных функций образуют класс линейных функций, обозначаемый как L. Базисом класса L служит множество {xÅy, 1}.