Функциональная полнота базиса

 

Классы функций

Пусть задано некоторое множество функций M. Множество функций, которое может быть реализовано схемами в базисе M, называют классом, порожденным M, а само множество M называется порождающим множеством этого класса.

Рассмотрим некоторые классы функций.

Класс всех функций обозначим классом C. Порождающее множество этого класса называют функционально полным. В этих терминах поставленный выше вопрос можно сформулировать как вопрос о свойствах функционально полного множества элементов.

Монотонные функции

 

Определение. Два набора значений двоичных переменных a=<a1,a2,…,an> и b=<b1,b2,…,bn> назовём сравнимыми и будем писать a³ b, если "i i=1,…,n aI ³ bi. Здесь ³ понимается в обычном виде: 1>0.

Если a³ b и b³ a, наборы считаются несравнимыми.

Пример. Наборы a=<010111> и b=<010101> сравнимы и a³b. Набор a и c=<100111> несравнимы.

Определение. Функция f называется монотонной, если для любых двух наборов значений входных переменных a и b из того, что a³b, следует, что f(a)³f(b).

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

1. Нулевой набор значений сравним с любым набором и явля-ется меньшим любого из них. Значит, если монотонная функ-ция равна единице на этом наборе, то она равна единице и на любом наборе, т.е. равна константе. Точно так же, если на единичном наборе значений монотонная функция равна нулю, то она не может быть единицей ни на каком наборе, так как единичный набор больше всякого другого набора.

2. Пусть функция на наборе a, отличном от единичного, равна 1, и пусть значение I-й компоненты в нём равно 0. Это значит, что на наборе, который отличается только тем, что i-я пере-менная в нём равна 1, функция тоже примет единичное зна-чение. Это означает, что конъюнкции в ДНФ, соответствую-щие этим наборам, можно склеить по переменной xi. Точно так же, для набора со значением переменной 0 (т.е. с возмож-ным значением в конъюнкции переменной с инверсией) найдётся набор со значением переменной 1, что приведёт к склеиванию по этой переменной. Значит, в минимальной ДНФ монотонной функции нет переменных в инверсной форме.

Из этих свойств можно вывести, что:

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

2) базисом класса М будут обе константы и пара функций – конъюнкция и дизъюнкция, т.е. множество {x × y, x Ú y, 0,1}.

Задача. Докажите, что константы должны присутствовать в базисе.

 

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

Определение. Для функции 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. Самодвойственная функция полностью определяется своим видом на верхней половине таблицы истинности. Действительно, если, например, значение функции на наборе
< a1, a2, …, a n> равно 0, то значение функции на инверсном наборе < ` a1, ` a2, …, ` a n> должно быть равно 1.

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

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

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

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

 

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

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

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

Сравним таблицы функции сложения по модулю два и дизъюнкции (табл.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);

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

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

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

f=C0 Å C1 × x1 Å C2 × x2 Å … Å Cn × xn Å C(n+1) × x1 × x2 Å … Å Cm × x1 × x2 ×… × xn, где С0, С1, С2,…Cm принимают значения 0 или 1.

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

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

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

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

Общий вид линейной функции f = C0 Å C1 × x1 Å C2 × x2 Å… Å Cn × xn.

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

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

Базисом класса L служит множество { x Å y, 1}.

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: