Пред.Страница  След.Страница  Раздел  Содержание


8.4.2. Замкнутые классы ПФ и теорема о функциональной полноте



Определение: Рассмотрим некоторый класс А переключательных функций. Будем называть его замкнутым, если для всяких функций g(f1,...,fk) и f1,...,fk из А их суперпозиция g(f1,...,fk) также содержится в А.


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

Рассмотрим некоторые важные примеры замкнутых классов ПФ, используя для иллюстрации табл. 4.1. В правой части таблицы отмечена принадлежность каждой ПФ рассматриваемым замкнутым классам ПФ.



Определение: Функцию называют сохраняющей нуль, если она при нулевых значениях аргументов также равна нулю:

f(0,...,0,...,0) = 0.

Все сохраняющие нуль функции образуют класс Т0 – сохранения нуля. В табл. 4.1 функции, принадлежащие этому классу, имеют индексы от 0 до 7, что соответствует нулевому значению функции на наборе значений аргументов (0,0).


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

f(1,...,1,...,1) = 1.

Все сохраняющие единицу функции образуют класс Т1 – сохранения единицы. В табл. 4.1 функции, принадлежащие этому классу, имеют нечетные индексы, что соответствует единичному значению функции на наборе значений аргументов (1,1).


Определение: Функцию называют самодвойственной, если она удовлетворяет равенству f(x1,...,xn) = f(x1,...,xn).

Иначе говоря, функция самодвойственна, если для произвольного набора значений аргументов инверсия всех компонентов набора изменяет значение функции на противоположное. В табл. 4.1 это соответствует тому, что для самодвойственной функции значения функции в столбцах, соответствующих противоположным наборам, например (0,0) и (1,1), (0,1) и (1,0), будут противоположными (антисимметрия левой и правой частей таблицы).

Все самодвойственные функции образуют класс S. Среди функций двух переменных классу S принадлежат функции f3, f5, f10, f12.


Определение: Двоичный набор = (a1,...,an) называют предшествующим набору = (b1,...,bn) и записывают это как ≤ , если имеют место покомпонентные неравенства a1 ≤ b1,...,an ≤ bn. В этом случае наборы и называют сравнимыми по отношению ≤.

Это предшествование является отношением нестрогого порядка, устанавливающим на множестве двоичных наборов частичный порядок.

Например, набор (0,1) вступает в отношение ≤ с набором (1,1), так как 0 ≤ 1 и 1 ≤ 1, следовательно, наборы (0,1) и (1,1) сравнимы по отношению ≤. Однако тот же набор (0,1) не вступает в отношение ≤ с набором (1,0), так как 0 ≤ 1, но неравенство 1 ≤ 0 не выполняется, следовательно, наборы (0,1) и (1,0) не сравнимы по отношению.



Пред.Страница  След.Страница    Раздел    Содержание